【作者】 郑运平；

【导师】 陈传波；

【作者基本信息】 华中科技大学 ， 计算机应用技术， 2008， 博士

【摘要】 图像表示是计算机图形学、计算机视觉、机器人、图像处理和模式识别等领域里的一个重要问题。有效的图像表示方法不仅能节省存储空间,而且还能提高图像处理的速度。随着数字化信息时代的到来和多媒体计算机技术的发展,使得人们所面对的各种图像数据量剧增,由于图像信息所具有的大量性,其快速、实时传输的要求得不到满足已成为制约Interact发展的一个难题。因此,图像表示方法的研究就变得非常重要,它是目前最活跃的研究领域之一。非对称逆布局模型(NAM)适用于图像模式、语音模式、文本模式、视频模式的表示,是一个通用型的模式表示模型。针对图像的有损表示,扩展了著名的Gouraud阴影法,研究了一种基于Gouraud阴影法的NAM图像表示方法,简称NAMC表示方法,并与目前流行的STC表示方法进行了比较。具体给出了灰度图像的NAMC表示算法,该算法编解码部分的时间复杂度分别为O(n log n)和O(n),其中n为灰度图像的像素数。以图像处理领域里惯用的标准’Lena’灰度图像作为典型测试对象,理论分析和实验结果均表明:在保持图像质量的前提下,与STC表示方法和目前已经商业化了的JPEG方法相比,NAMC表示方法具有更低的比特率和更少的块数,从而具有更高的表示效率和更快的处理速度,是图像模式的一种更优的有损表示方法。NAMC图像表示方法有两重目的,一是体现在数据量上的优越性,二是体现在图像处理上的优越性。图像处理中的一些原子操作和运算(如:寻找近邻、搜索、计算区域的面积、集合操作等)在复杂算法中是经常用到的。具体研究了NAMC表示方法在图像处理中应用的一个例子,即:基于NAMC表示的快速矩计算算法。该算法的时间复杂度为O(N),其中N为灰度图像用NAMC表示时的同类块的总数。以图像处理领域里惯用的标准’Lena’、’F16’和’Peppers’等灰度图像作为典型测试对象,理论分析和实验结果均表明:与流行的基于STC表示的矩计算算法相比,基于NAMC表示的矩计算算法具有更快的计算速度。针对图像的无损表示,研究了一种基于多子模式的NAM图像表示方法和一种基于光栅扫描的NAM编码优化策略。通过对典型多子模式(三角形和矩形)进行分析,给出了一种基于三角形和矩形的NAM图像表示方法,简称为NAMTR表示方法,并与经典的线性四元树(LQT)表示方法从理论上进行了比较。具体研究了基于NAMTR的二值、灰度和彩色图像表示算法,且对算法的存储结构、数据量以及时间和空间复杂度进行了详细分析。给出了2种多值图像(灰度和彩色图像)的NAMTR表示方法,即直接方法和间接方法,且对这2种方法进行了比较,其中间接方法是一种位平面分解方法,能够有效降低原图像模式的复杂度,从而提高图像模式的表示效率。直接方法和间接方法表示的数据量和压缩比都与图像的复杂度有关,图像复杂度越低,则NAMTR表示的效率就越高。以图像处理领域里惯用的标准’Lena’、’F16’和’Peppers’等图像作为典型测试对象,理论分析和实验结果均表明:与经典的LQT表示方法、目前新提出的矩形NAM图像表示方法及流行的紧凑四元树(CQT)表示方法相比,NAMTR表示方法在子模式(节点数)和数据存储空间上具有明显的优势,是图像模式的一种更优的无损表示方法。NAMTR图像表示方法同样有两重目的,一是体现在数据量上的优越性,二是体现在图像处理上的优越性。作为NAMTR图像表示方法在图像处理中应用的一个例子,研究了一种基于NAMTR表示的二值图像的快速面积计算算法。该算法的时间复杂度为O(N),其中N为二值图像用NAMTR表示时的子模式总数。以图像处理领域里惯用的标准’Lena’、’F16’和’Peppers’等二值图像作为典型测试对象,理论分析和实验结果均表明:与流行的基于CQT表示的面积计算算法相比,基于NAMTR表示的面积计算算法具有更快的计算速度。总之,NAMC和NAMTR表示方法可以应用于图像表示和图像处理的各个方面,在降低存储空间、加快传输速度、提高模式匹配效率等方面具有良好的理论参考意义和实际应用价值。更多还原

【Abstract】 Image representation is an important issue in computer graphics, computer vision, robotics, image processing and pattern recognition. Efficient image representations can save space and facilitate the manipulation of the acquired images. With the advent of the digital information era and the development of the computer multimedia technology, all kinds of image data are dramatically increasing. Due to mass data of image information, the fact that the demands of the fast and real-time transmission for images have failed to meet the development of the Internet has become a difficult problem. Therefore, the study on image representation method becomes increasingly important, and it is one of the hottest research fields at present. The Non-symmetry and Anti-packing Model (NAM) is suitable for representations of image pattern, audio pattern, video pattern, and text pattern, and it is a general pattern representation model.With respect to the lossy image representation, by extending the famous Gouraud shading method, a novel gray image representation using the NAM and shading approach called the NAM Coding (NAMC) approach is proposed and is compared with the popular S-Tree Coding (STC) approach. The encoding can be performed in O(n log n) time and the decoding can be performed in O(n) time, where n denotes the number of pixels in the gray images. By taking the idiomatic standard gray image ’Lena’ in the field of image processing as a typical test object, the theoretical and experimental results show that the proposed NAMC approach can reduce the bits per pixel and the number of the homogeneous blocks in the gray images much more effective than the popular STC approach and the traded JPEG approach on the premise of remaining the image quality, and therefore it is a better method to represent the lossy image pattern.Not only can the NAMC approach save storage space, but also it can facilitate the image manipulations. Some image manipulations, such as neighbor finding, searching, area computing, and set operations, are often used in some complex algorithms in the field of image processing. As a representative of applications, a fast algorithm for computing the lower order moments is proposed on the NAMC representation directly, which takes O(N) time where N is the number of NAMC blocks. By taking three idiomatic standard gray images ’Lena’, ’F16’, and ’Peppers’ in the field of image processing as typical test objects, and by comparing the proposed NAMC approach for computing lower order moments with the popular STC approach, the theoretical and experimental results show that the former is faster than the latter with respect to the computing speed.With respect to the lossless image representation, a novel NAM image representation method based on the multi-subpattern is proposed. Also, an optimization strategy of the NAM encoder using raster scanning is presented. By taking a typical multi-subpattern (the combination of the triangle and the rectangle subpatterns) as an example, a novel image representation method by using the Non-symmetry and Anti-packing Model with Triangles and Rectangles (NAMTR) is proposed. Also, Some concrete algorithms of the NAMTR representation for binary, gray, and color images are proposed and the storage structures, the total data amount, and the time and space complexities of these proposed algorithms are analyzed in detail. As far as multi-valued images, i.e., the gray and color images, are concerned, two kinds of representation methods are put forward. One is the direct representation of the NAMTR, and the other is indirect representation of the NAMTR, i.e., the representation of the Binary-bit Plane Decomposition (BPD). The BPD method can effectively reduce the complexity of multi-valued images and achieve high representation efficiency. The total data amount and the compression ratios of the two representation methods for multi-valued images have relations with the image complexity. The lower the image complexity is, the higher the representation efficiency of the NAMTR is. By taking some idiomatic standard images, such as ’Lena’, ’F16’, and ’Peppers’, in the field of image processing as some typical test objects, and comparing the algorithm of NAMTR with those of the classic linear quadtree (LQT), the latest NAM, and the popular compact quadtree (CQT), the theoretical and experimental results show that the former is obviously superior to the latters with respect to the numbers of subpatterns (nodes) and the data storage, and therefore it is a better method to represent the lossless image pattern.Not only can the NAMTR approach save storage space, but also it can facilitate the image manipulations. As a representative image manipulation, a fast algorithm for computing the area of a binary image is proposed on the NAMTR representation directly, which takes O(N) time where N is the total subpattern number. By taking some idiomatic standard binary images, such as ’Lena’, ’F16’, and ’Peppers’, in the field of image processing as some typical test objects, and by comparing the proposed NAMTR approach for computing the area of the binary image with the popular CQT approach, the theoretical and experimental results show that the former is faster than the latter with respect to the computing speed.In a word, the proposed NAMC and the NAMTR approaches for the image representation and manipulation, as envisaged in this paper, show a very strong promise and have good potential in business applications dealing with image processing, such as reducing storage room, increasing transmission speed, and improving pattern match efficiency.更多还原