適用於角點與輪廓之無損與有損壓縮技術

Abstract

形狀對於物體識別、模板匹配、影像分析等領域皆是很重要的特徵，為了有效率地描繪出形狀，如何用很低的資料量來儲存形狀的兩大特徵─「角點」與「輪廓」將是一大課題。因此，在本篇論文中提出了三種資料壓縮技術，分別對角點與輪廓資訊做有效率的壓縮。 在角點壓縮中，我們將一連串角點先依距離資訊來重新排序，接著使用一個主動式矩陣來儲存角點的位置，並且運用了適應性算術編碼與內文模型的技術來提升編碼效率，除此之外，我們也提出二元特徵點其他資訊的壓縮方法，角度部份有參考特徵點距離資訊的關聯性，而描述子的部分則提出非對稱選擇參考點的方式，以增加預測編碼的成效。 在無損失的輪廓壓縮中，演算法起初會讓輪廓做些微的型態學變形，以縮小需要處理的輪廓，接著運用與弗利曼角度鏈碼有相近的概念，但是會分為主鏈碼與副鏈碼，因為根據觀察，一條鏈碼在串接時，絕大部分是會沿著原來的方向，或是偏左或右45度，為了降低符號的多樣性，在主鏈碼的其他方向會由同一符號來表示、副鏈碼中才來區別這些方向，主鏈碼還有做符號替換的動作，主要是精簡兩種數位輪廓下易產生的符號組合，接著利用機率統計的方式轉換成霍夫曼編碼以做為中介碼，並利用分布轉換來改變兩位元(0與1)的分布，除了增加同種位元的聚集性，也提升0出現的機率，最後再利用內文模型提升適應性算術編碼的壓縮效率。 在有損失的輪廓壓縮中，演算法的精髓是使用多項式曲線連結一些重要的頂點來近似出原始形狀，而這些頂點又被稱作主特徵點，其找尋方式是先使用曲度來做第一次篩選，在找出初代主特徵點後，利用三階多項式搭配最佳化來對原始形狀做近似，並計算其與原始形狀的誤差，如果誤差過大，則在適當位置給予一新主特徵點直到誤差可以容忍，接著對主特徵點的八連通區域做一次鄰居搜尋，如果有更佳的位置，則將主特徵點移至該鄰居，並調整三階多項式參數。在主特徵點的記錄上，我們使用類似角點壓縮的概念，而三階多項式參數，我們也有發現其之間的相關性，最後利用改良後的適應性算術編碼，能有效降低所需的資料量。

Shape is an important feature for object recognition, template matching, and image analysis. To represent it efficiently, the techniques for encoding the corners and the contours with very low bit rate are necessary. Therefore, in this thesis, three data compression techniques are proposed in order to reduce the data size requirement for corners and contours. For corner compression, we rearrange the corners based on the distance information and use an active matrix to encode the position of corners. Moreover, the techniques of adaptive arithmetic coding and context modeling are also adopted to improve the efficiency. Besides, the techniques to compress the other information in binary feature point are also proposed. To encode the angles, the correlation between the distance information of feature points is considered. For descriptors, an asymmetric reference point selection scheme is proposed to improve the predictive coding. For lossless contour compression, the proposed algorithm first applies the morphology operation to shrink the contour slightly, and then uses similar concept to the Angle Freeman chain code. However, the chain code will be split into main-chain code and sub-chain code. From observation, the angles between consecutive directions are mostly 0 degree and 45 degrees to the right or left. To decrease the symbol diversity, the angles except for 0, 45, -45 degrees are represented as the same symbol in main-chain code, and are distinguished in another chain code. Moreover, there is some symbol substitution in main-chain code to simply the most common symbol combination owing to digital contour. After that, Huffman code is used to the main-chain code as an intermediate code according to the probability statistics of symbols, and to improve compression efficiency, the distribution transform is applied to alter the distribution of zeros and ones. Not only does the distribution of the same bit become denser, but the probability of zeros also gets higher. At last, by adaptive arithmetic coding and context modeling, the data size of the contour reduces considerably. The central concept of the proposed lossy contour compression is to approximate the original shape by a combination of vertices and polynomial curves. The vertices, which are also called dominant points, are found by the following steps. First, the initial dominant points will be chosen according to the curvature measure, and then 3rd order polynomial with optimization will be used to approximate the original contour. After calculating the error between the approximated contour and the original contours, new dominant points will be iteratively added in suitable positions until the error is tolerated. By employing the tuning around the eight-connected neighbor of dominant points, the dominant points and the polynomial coefficients will be replaced if there is some better position. When encoding the coordinates of dominant points, the concept similar to the proposed corner compression techniques is adopted. We found there is some correlation between polynomial coefficients, where the data size can be significantly decreased by improved adaptive arithmetic coding.