非对称逆布局模式表示方法研究-智能与分布计算实验室

非对称逆布局模式表示方法研究

姓名	陈传波
论文答辩日期	2006.04.23
论文提交日期	2006.04.30
论文级别	博士
中文题名	非对称逆布局模式表示方法研究
英文题名	Study on A Non-symmetry And Anti-packing Pattern Representation Method（NAM）
导师1	卢正鼎
导师2
中文关键词	布局问题;模式表示;算法分析;位平面分解;图像复杂度
英文关键词	Packing problem;Pattern representation;Algorithm analysis;Bit-plane decomposition;Image complexity
中文文摘	非对称逆布局的模式表示模型（NAM）借助于Packing问题的思想，能够有效地表示多种类型模式，是一个通用型的模式表示方法。非唯一性定理和最优分割存在性定理证明了NAM表示的多样性和最优分割的存在性。NAM方法是全新的模式表示方法，旨在开拓一个全新的关于模式表示的研究领域，其理论价值在于它的可扩展性，其实际应用前景体现在它的数据压缩和表示上的可操作能力。非对称逆布局模式表示的抽象算法概括了NAM表示的全部思想，适用于图像模式、语音模式、文本模式、视频模式的表示，是一个一般性和具有指导性的抽象算法。算法的复杂度为，M为待逆布局模式的规模。 K码行程和矩形子模式算法是NAM表示的具体实例，算法时空复杂性都为O(Nf )，Nf为图像模式的总象素。图像复杂度是反映图像数据结构的复杂程度，用于数据量的分析。与流行的树型分层结构进行理论比较，从理论上证明了NAM的明显优势。从总数据量的理论分析来看，K码行程NAM表示的数据量低于线性四元树数据量的67％，矩形NAM的数据量低于线性四元树表示数据量的67％。实际情况由于子模式数比四元树的节点数要少得多，因此矩形NAM的数据量比线性四元树的数据量的67％还要小得多。 NAM上典型操作和运算的具体算法较之点阵表示的操作具有明显的优越性。矩形NAM表示的寻找近邻、搜索、计算区域的面积、以及交和并集合操作的具体算法较之线性四元树上的运算和操作有明显的优势。由于NAM表示上的操作和运算是针对图像子模式为最小单位而言的，相对于矩阵图像以像点（pixel）为最小单位的处理来说，其计算复杂度要低得多。即NAM表示上的操作和计算复杂度是子模式个数的函数，而矩阵表示的操作和计算复杂度是图像像点数的函数。在失真模式的NAM表示方面，定义了残渣模式和子模式的尺度，失真模式的NAM表示的编码和解码算法的复杂度和非失真NAM表示的复杂度是一样的。NAM失真表示相对于其它失真表示方法来说具有新的含义，传统的失真模式是去掉图像模式的中高频信息，NAM方法具有消除图像模式中噪音的能力，不仅数据压缩能力强，而且能够有效地保真。多值图像模式有两种NAM表示方法，即BPD方法和直接方法。BPD是一种位平面分解方法，三个定理阐明了位平面分解的具体方法和性质，证明了位平面分解能够降低原图像模式的复杂度，从而提高了图像模式NAM表示的效率。直接NAM表示和BPD的NAM表示的数据量和压缩比都与图像的复杂度有关。图像复杂度越低，则NAM表示的效率就越高。只要图像复杂度（直接方法）或（BPD方法），则其压缩比就大于1。实验数据表明，二值图像模式的矩形NAM方法的压缩因子是四元树的4.74到9.97倍，是行程编码的1.75到4.9倍，是K码行程的1.49到5.05倍。K码行程的压缩因子是四元树的1.97到3.27倍，和行程编码相当，对于具有块状性质的图像来说K码行程要优于行程编码。对多值图像来说，非失真情况下，直接矩形NAM表示的压缩因子是线性四元树的4.96到19.37倍，是行程编码的0.93到4.07倍，是位平面分解NAM表示的1.47到1.98倍。位平面分解NAM表示的压缩因子是线性四元树的2.52到9.77倍，是行程编码的0.51到2.05倍。失真情况下，直接矩形NAM表示的压缩因子是线性四元树的0.77到7.87倍，是位平面分解NAM表示的1.86到2.62倍。位平面分解NAM表示的压缩因子是线性四元树的0.29到3.62倍。虽然行程编码偶尔要好于NAM表示，但总体情况来说，NAM还是要好得多。在失真情况下，线性四元树也有好于NAM的情况，但是线性四元树的保真度很差，几乎难以接受。NAM方法不仅有高的压缩比，而且还有良好的保真度。无论是从理论到实验，还是从主观标准到客观标准，NAM是模式表示的良好方法。
英文文摘	patterns such as text, image, voice, and video and so on. The idea is described as: giving a pattern(a container) and N pre-definited sub-patterns(N objects with different shape), pick-up these sub-patterns(the objects) from the given pattern (container with the objects) and then represent the given pattern(the packed container) with the combination of the these sub-patterns(the objects). Two theorems are given to show that the NAM representation is not Exclusive and the existence of an optimal partition. The method is a new research area respect to the pattern representation and valuable for the theoretical research and business foreground. An algorithm is given for the representation of the non-symmetry and anti-packing pattern representation and the algorithm sums up the entire idea. It is suitable for the text, image, voice, and video patterns and is a general, abstract, and pioneer representation algorithm. The algorithm complexity is ,where M is the scale for packed pattern. The algorithm is useful for the subsequence researchers. The Kline NAM algorithm and the rectangle NAM algorithm are presented for the image pattern and both the algorithm’s complexities are O(Nf ),where Nf is the pixel number of the image. The image complexity is inducted for the data amount analysis. the comparison has been done to the popular tree-like hierarchical structure and it is proved that NAM method is more effective than the tree-like method. From the point of the total data amount(TDA), the TDA of square NAM representation is only 50% of the TDA of the quadtree representation and the TDA of rectangle NAM representation is below 67% of the TDA of the quadtree representation. In the practice, the TDA of rectangle NAM representation is far below 67% of the TDA because the number of the sub-patters is much smaller than the number of the nodes of the quadtree. The operations and the computations algorithms on NAM are presented. It has obvious advantages over the pixel representation. The adjacent finding, searching, area computing, and set operations(intersection and union) algorithms over NAM are given. The algorithm complexities are far lower than the traditional algorithms complexities because the traditional ones are based on the pixels but not the sub-patterns. in other words, the algorithm complexity over NAM is the function of the number of the sub-patterns and the algorithm complexity over pixel representation is the function of the number of the pixels. therefore, it is obvious for the operations and computing on the NAM. In the distortion non-symmetry and anti-packing pattern representation, the residual-pattern and sub-pattern measure are defined. The coding and decoding algorithms of the distortion NAM are given. The algorithm complexities are analyzed and the algorithm complexities are almost the same as the non- distortion NAM. Compared to other distortion representation methods, distortion NAM has new meaning. The traditional ones are related to high frequency but the distortion NAM is related to the noise. NAM has not only the compression ability but also has better reconstruction quality. Two multi-valued image NAM representation methods are given, those are BPD method and the direct method. The effectiveness, complexity, and the total data amount are analyzed in detail. BPD is a bit-plane decomposition method and three theorems are given for the BPD decomposition and some properties and the theorems ensure that the BPD can reduce the complexity of the image pattern. The TDA and the compression ratio of the direct NAM and the BPD NAM all related to the complexity of the image pattern. The lower the image complexity, the higher the NAM effectiveness. The compression ratio will be large than 1 if the image complexity (direct method) or (BPD method). With the experimental data, for the binary-valued images, the compression ratio of rectangle NAM is 4.74 to 9.97 times of that of quadtree, 1.75 to 4.9 times of that of run-length, and 1.49 to 5.05 times of that of Kline NAM. The compression ratio of Kline NAM is 1.97 to 3.27 times of that of quadtree, almost the same as run-length，and better than run-length for the block-like images. For the multi-valued images, under the non-distortion, the compression ratio of direct rectangle NAM(DRN) is 4.96 to 19.37 times of that of quadtree, 0.93 to 4.07 times of that of run-length，and 1.47 to 1.98 times of that of BPD NAM. The compression ratio of BPD NAM is 2.52 to 9.77 times of that of quadtree and 0.51 to 2.05 times of that of run-length. under the distortion, the compression ratio of DRN is 0.77 to 7.87 times of that of quadtree, 1.86 to 2.62 times of that of BPD NAM. The compression ratio of BPD NAM is 0.29 to 3.62 times of that of quadtree. Although run-length is a little better than NAM in some instance, generally speaking, NAM is much better than run-length in most cases. Sometimes Quadtree is better under distortion, but it is strongly distortion for Quadtree. However, NAM has not only the high compression ratio but also the better reconstruction quality. As discussed above, either from theoretical to experiment or from personality standard to impersonality standard, NAM is a better method to represent the patterns.