Abstract
現今仍有許多彩色輸出設備，如顯示器及彩色印表機，無法適當地使用全彩影像。這有幾個原因：第一，在很多電腦系統中，記憶體儲存裝置的大小仍嫌不足，或者CPU的速度不夠快。第二，有些軟體必須使用較少的顏色數來增進其效能，例如要在影像資料庫中搜尋某張圖片時，我們可以先在資料庫的索引中預覽其256色的圖示，如此可減少搜尋時間。多媒體應用程式和遊戲軟體也需使用較少的顏色以加快程式的執行速度，並使其更順暢。第三，Internet 的發展日漸蓬勃，但目前的網路頻寬不足，以致常常造成網路壅塞。因此，若使用較少顏色數的圖形檔，即可減輕網路傳輸的壅塞問題。因此我們提出了一個新的方法，可以快速地從全彩影像選取最佳之256色或更少的顏色。為降低搜尋時間及複雜度，我們使用二元樹的結構和採用 RGB 彩色座標系統。當然也可以適用於其它座標系統。選色時我們使用調色盤及失真度 (Palette-Distortion) 的方法。而失真的計算，我們先使用總和平方錯誤(Total Square Error)，後來為了改善程式，又套用了人類視覺系統 (Human Visual System) 來計算失真。最後，為了達到區域最小化的目標，我們在演算法的一開始加上分類的觀念，也就是先把顏色值相近的分在同一個群組中。把這個觀念和人類視覺系統組合在一起，由實驗結果證明如此的確會使產生的彩色影像有較好的品質及較低的失真。對於較少的顏色數，可以加上簡單的錯誤分散(Error Diffusion) 方法來處理影像。若能仔細地設計分類的方法，將會對我們的選色演算法產生神奇的影響，甚至在低於256色的情況下也會有不錯的品質，而不需要使用錯誤分散的方法。Most color output devices use the frame buffer architecture.Even if thesize of the memory storage is very large and thespeed ofthe CPU is very fast, such that the computer canmanipulate true colorimage, some applications, on computergames and the Internet still needsto use K ( K<=256 ) colors.Here we propose a fast method of color imagequantization basedon palette-distortion theory. It can generate highquality colorimage very fast. To utilize theproperties of the HumanVisualSystem (HVS), the distortion is measured in theluminance-chrominance color space. Besides, we use a grouping method toacheivethe goal of local minimum such that it will result ingood color imagequantization. Error diffusion is adopt toimprove the quality of fewer levelquantization.