Abstract
近年來，電腦科技的長足進步，影像資料被廣泛使用於各項應用，如電腦輔助教學，及全球資訊網上。。由於影像資料過於龐大，故有效的壓縮便成為重要的課題。 一個好的影像壓縮演算法必須要能夠兼顧壓縮比率以及還原影像的品質。在1992年制定了一項基於整數離弦轉換 (DCT)的壓縮標準，名為JPEG。除此之外，尚有許多影像壓縮演算法被提出，如小波轉換 (wavelet transform) ，碎形壓縮 (fractal imagecompression)，及向量量化(vector quantization)。向量量化是很有效的影像壓縮演算法。其最大的優點是即時解壓縮及簡單的解碼器，尤其適合一個編碼器對多個解碼器的影像系統。 1980年LBG演算法被提出，引發了對向量量化的研究熱潮。向量量化可以分為三個部份，亦即碼本生成、壓縮、及解壓縮。其中解壓縮只是個簡單的查表工作。 碼本扮演著最重要的角色，影像品質可以藉著一個好的碼本而得到改善。LBG 是最常被用來生成碼本的演算法，但是卻須要極長的工作時間。因此許多快速演算法被提出，如 pairwise nearest neighbor(PNN)，及DCT basedtree structure VQ (DCT-TSVQ)。另有一些演算法用來消除區塊效應(blocking effect)，如 classified VQ，和改善影像品質，如 similatedannealing 演算法。 壓縮是從碼本中搜尋出最相近的碼向量(codevector)。一些快速的搜尋演算法被提出，以降低搜尋時間，如partial distortion search(PDS)，triangular inequalityelimination(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 imagecompression. An new fast VQ scheme, called PCA-TSVQ, based onprincipal component analysis (PCA) is proposed. The proposedalgorithm uses the first principal components of trainingvectors to construct a binary tree classifier. A simplethresholding method on the first principal components is used tofind the split key on each nonterminal node. The centroid oftraining vectors belonging to the same leaf of the binary treeforms a codevector of the codebook. A modified scheme based onPCA-TSVQ is also developed. The modified scheme generates anadaptive codebook for a given image and encodes this imagesimultaneously as soon as the codebook is generated.Experimental results show that the new algorithm requirs about2.5 secodes on a Pentium-150 PC to encode a 512 × 512 graylevel image to archieve compression ratio 0.563bpp withsatisfactory image fidelity.