臺灣博碩士論文加值系統

近年來，電腦科技的長足進步，影像資料被廣泛使用於各項應用，如
電腦輔助教學，及全球資訊網上。。由於影像資料過於龐大，故有效的壓
縮便成為重要的課題。 一個好的影像壓縮演算法必須要能夠兼顧壓縮
比率以及還原影像的品質。在1992年制定了一項基於整數離弦轉換 (DCT)
的壓縮標準，名為JPEG。除此之外，尚有許多影像壓縮演算法被提出，如
小波轉換 (wavelet transform) ，碎形壓縮 (fractal image
compression)，及向量量化(vector quantization)。向量量化是很有效
的影像壓縮演算法。其最大的優點是即時解壓縮及簡單的解碼器，尤其適
合一個編碼器對多個解碼器的影像系統。 1980年LBG演算法被提出，
引發了對向量量化的研究熱潮。向量量化可以分為三個部份，亦即碼本生
成、壓縮、及解壓縮。其中解壓縮只是個簡單的查表工作。 碼本扮演
著最重要的角色，影像品質可以藉著一個好的碼本而得到改善。LBG 是最
常被用來生成碼本的演算法，但是卻須要極長的工作時間。因此許多快速
演算法被提出，如 pairwise nearest neighbor(PNN)，及DCT based
tree structure VQ (DCT-TSVQ)。另有一些演算法用來消除區塊效應(
blocking effect)，如 classified VQ，和改善影像品質，如 similated
annealing 演算法。 壓縮是從碼本中搜尋出最相近的碼向量(
codevector)。一些快速的搜尋演算法被提出，以降低搜尋時間，如
partial distortion search(PDS)，triangular inequality
elimination(TIE)等等。 在本論文中回顧幾種主要的向量量化演算法
，並且提出一個使用主元素分析的快速向量量化演算法。此演算法採用一
個二元樹狀分群器，以達到大量降低運算量的目的。利用主元素分析法，
降低訓練向量的維度，淬取出最重要的特性。以訓練向量的第一主元素及
其限值為二元樹各非終端節點分群的依據。此二元樹建立完成後，各終端
節點中訓練向量的中心向量便組成碼本。 此外一個修改的架構，使得
碼本生成時，同時完成壓縮工作。實驗結果顯示新演算法的影像品質均一
致優於 fast PNN，及 DCT-TSVQ 演算法，接近 LBG 演算法。而碼本生成
時間除稍多於 DCT-TSVQ，也大幅低於 fast PNN 演算法。此演算法在
Pentium-150 的個人電腦上，須要大約2.5秒的時間去壓縮一張512×512
的灰階影像。壓縮比為0.563bpp，且得到令人滿意的影像品質。在未來更
快速的電腦上，只須要更少的時間。

Vector quantization (VQ) is an efficient technique for image
compression. An new fast VQ scheme, called PCA-TSVQ, based on
principal component analysis (PCA) is proposed. The proposed
algorithm uses the first principal components of training
vectors to construct a binary tree classifier. A simple
thresholding method on the first principal components is used to
find the split key on each nonterminal node. The centroid of
training vectors belonging to the same leaf of the binary tree
forms a codevector of the codebook. A modified scheme based on
PCA-TSVQ is also developed. The modified scheme generates an
adaptive codebook for a given image and encodes this image
simultaneously as soon as the codebook is generated.
Experimental results show that the new algorithm requirs about
2.5 secodes on a Pentium-150 PC to encode a 512 × 512 gray
level image to archieve compression ratio 0.563bpp with
satisfactory image fidelity.