Advanced Image Compression Techniques by Triangular and Trapezoidal Segmentations

在近幾年的多媒體應用中，不規則形狀的影像壓縮已經變的越來越熱門。形狀自適應編碼的優點在於這種方法可以運用同一個不規則區塊中色彩強度的高相關性來對不規則形狀內的影像資訊做更好的壓縮，以達到更高的壓縮率。較於傳統基於方型區塊的影像壓縮，形狀自適應的影像編碼可產生相當少的區塊效應及變形失真的情形。這是由於基於方型區塊的影像壓縮忽略了影像的內容與特徵。因為傳統的不規則形狀的影像壓縮大多依賴格拉姆-施密特正交化演算法來取得每一個不規則形狀區塊的正交化基底，它的運算複雜度是相當龐大的。因此，我們在這邊論文裡提出了一個創新的概念 – 以三角形和梯形分割為基礎的二維正交離散餘弦轉換，其效能較傳統的不規則形狀的離散餘弦轉換來說，在運算複雜度上較為節省。由於一個不規則形狀的區域嚴格來說是一個多邊形，而一個多邊形可以被分解成很多三角形及梯形，本篇論文提出的方法是相當適用在對不規則形狀的區域做轉換。實驗結果顯示本篇論文提出的方法跟運用格拉姆-施密特演算法的方法都有一樣好的將能量集中在低頻的能力，而本篇論文提出的方法可以顯著的減少運算時間。另外，我們也可以運用本篇論文提出的方法產生可適於三角形和梯形的正交離散傅立葉基底、KLT基底、Legendre基底、Hadamard (Walsh)基底、及其他多項式基底。Coding of arbitrarily shaped image region is becoming more and more popular in today’s multimedia applications. The advantage of shape-adaptive coding is that it can employ the information of arbitrarily-shaped region to exploit the high correlation of the color values within the same image segment in order to achieve a superior compression rate. Compared to the conventional block-based image coding, shape-adaptive image coding produces significantly less blocking artifacts and distortions in other forms which typically emerges in block-based image coding since its negligence of the image content and characteristics. Because early shape-adaptive image coding relies on the Gram-Schmidt process to obtain orthogonal basis for each arbitrary region, its computational complexity could be enormous. Therefore, in this thesis, we present the two-dimensional orthogonal DCT expansion in triangular and trapezoid regions which is much more economical in terms of the complexity compared to the conventional shape-adaptive transforms. Since an arbitrarily shaped region literally is a polygon and a polygon can be decomposed into several triangular or trapezoidal regions, the proposed method is highly suitable for transforming arbitrarily shaped segments. esults show that the proposed method has the energy compact ability that is as good as the results of the Gram-Schmidt method, and significantly fast computation time. In addition, the proposed method can also be used for generating the 2-D complete and orthogonal DFT basis, KLT basis, Legendre basis, Hadamard (Walsh) basis, and polynomial basis in the trapezoid and triangular regions.CONTENTS試委員會審定書 #謝 iCKNOWLEGEMENTS iii文摘要 vBSTRACT viiONTENTS ixIST OF FIGURES xvIST OF TABLES xxihapter 1 Introduction 1hapter 2 Basic Still Image Compression Algorithm 5.1 Basic Image Compression Model 6.2 Transform Coding 7.2.1 Image Encoding Algorithm Using the Orthogonal Transform 7.2.2 Karhunen-Loeve Transform (KLT) 10.2.3 Discrete Cosine Transform (DCT) 15.3 The JPEG Still Picture Compression Standard 17.3.1 Processing Steps for DCT-Based JPEG Coding Modes 18.3.2 Predictive Lossless JPEG 22hapter 3 A Review of the Other Existing Compression Standards of Still Images 27.1 JPEG 2000 27.1.1 Fundamental Building Blocks 28.1.2 Wavelet Transform 30.2 JPEG-LS 33.2.1 Decorrelation/Prediction 33.2.2 Context Modeling 34.2.3 Coding Corrected Prediction Residuals 36.2.4 Run Length Coding in Uniform Areas 36.3 JBIG2 37.3.1 Text Image Data 38.3.2 Halftones 40.3.3 Arithmetic Entropy Coding 41.4 GIF 41.4.1 LZW Data Compression 41.4.2 Implementation Challenges of LZW Algorithm 45.4.3 Application of LZW Algorithm in Image Compression 47.5 PNG 48.5.1 Use of Huffman Coding in the Deflate Format 49.5.2 LZ77-Related Compression Algorithm Details 50.6 HD Photo (JPEG XR) 51.6.1 Data Hierarchy 52.6.2 The HD Photo Compression Algorithm 55.7 TIFF 6.0 55.7.1 Difference Predictor 55.7.2 PackBits Compression 56.7.3 Modified Huffman Compression 57hapter 4 Past Research on Shape-Adaptive Image Compression 59.1 Shape-Adaptive Orthogonal Transforms 60.2 Coding Using Shape-Independent Basis Functions 61.2.1 Discrete Linear Approximation 61.2.2 Orthogonal Basis Functions 62.2.3 Successive Approximation Using Shape-Independent Basis Functions 63.3 Adaptive Image Partitioning Compression Using Delaunay Triangulation 67.3.1 Different Techniques for Adaptive Image Partitioning 68.4 Segmentation-Based Image Compression 70hapter 5 Shape-Adaptive Image Compression 73.1 Morphological Segmentation Using Erosion 76.1.1 Modifications to Morphological Segmentation Algorithm 79.2 Shape-Adaptive Transform Algorithm 81.2.1 A Traditional Approach to Transform Arbitrarily-Shaped Image Segments 81.2.2 Transform Using Arbitrarily-Shape DCT Bases 81.2.3 Orthogonalization of the Shape-Projected Bases 85.3 Quantization of the Arbitrary-Shape DCT Coefficients 89.3.1 Adaptive Quantization of the Arbitrary-Shape DCT Coefficients 91.4 Coding Technique of the Image Segment 92.5 Simulation Results and Performance Comparison 94.5.1 Arbitrarily-Shaped Image Compression 94.5.2 Arbitrarily-Shaped Image Compression with the Erosion Operation 95.5.3 Performance Comparison to JPEG Standard 96.5.4 Arbitrarily-Shaped Image Compression with Both the Erosion Operation and Adaptive Quantization 97.5.5 Complexity Issues and Proposed Solution 103.6 Summary 104hapter 6 Huffman Coding 105.1 Instantaneous Codes 105.2 Huffman Codes 105.3 Inaccuracy in the Estimates of the Huffman Coding Probabilities 109hapter 7 Overview of the MPEG-4 Standard 111.1 Coding of Objects with Arbitrary Shapes 111.1.1 Shape Coding 113.1.2 Texture Coding 119.1.3 Sprite Coding 126.1.4 Shape Extraction and Segmentation 129.2 Coding of Objects with Arbitrary Shapes 130.2.1 Spatial Scalability 131.2.2 Temporal Scalability 132.2.3 Object-Based Scalability 132.2.4 Fine Granular Scalability 132hapter 8 Two-Dimensional Orthogonal DCT Expansion in Triangular and Trapezoid Regions 137.1 Complete and Orthogonal DCT Basis in the Trapezoid Region 139.2 Extending to Generalized Trapezoid, Triangular, and Polygonal Regions 145.3 Extending to Other Symmetric Orthogonal Basis 146.4 Applications in Image Compression and Signal Processing 148.5 Summary 151hapter 9 Geometric Progression Coding Theory 153hapter 10 Conclusions and Future Work 1590.1 Conclusions 1590.2 Future Work 160EFERENCES 16