摘? 要: 生成帶調色板的圖像文件時,需要解決調色板索引匹配的問題。針對該問題,本文提出了一種增量序列的產生方法,并基于這種序列,給出了一種調色板索引匹配算法。
關鍵詞: 增量序列? 調色板? 索引值? 匹配算法
?
圖像處理時,經常需要生成帶有調色板的圖像文件。各種類型的圖像文件一般采用壓縮存儲方式,解壓后彩色圖像數據可表示為三基色的灰度值。圖像數據在轉換為帶調色板的圖像文件時,如果所占用的顏色空間小于調色板所能表示的顏色數目,則可以實現無失真的轉換;如果圖像數據的顏色空間大于調色板數目,則轉換過程需要舍棄部分顏色。為了使圖像達到較高的保真度,應將舍棄的顏色轉換為調色板中與之最相近的顏色。為此,本文提出了一種基于增量序列的調色板索引匹配算法。
1? 知識描述
BMP圖像文件是一種常用的圖像格式,圖像數據可采用壓縮、非壓縮2種方式存放,較多采用非壓縮方式。BMP圖像文件由三部分組成:文件頭、調色板數據和索引數據。調色板數據對不超過256色的圖像模式都要進行設置。調色板中紅、綠、藍三種基色數據的排列順序與其他圖像文件格式相反。對256色非壓縮方式而言,調色板由256項組成,每項代表一種顏色,其索引編號從0～255,圖像數據為象素點的索引。
圖像數據生成帶調色板的圖像時,如果圖像數據的顏色空間超過調色板空間,則會出現一些調色板中沒有的顏色。此時,可采用匹配算法,在調色板中找出與該顏色最接近的顏色索引。在匹配過程中按遞增順序修改該顏色灰度值,以找到最佳匹配項,并使該顏色灰度值的修改盡量小。匹配過程所用的增量序列滿足以下3個基本條件。
(1)整體有序。因為圖像變換要求基本維持原圖像的效果,所以大部分象素灰度值與調色板中某顏色的灰度值之差較小。匹配從最小項開始,可以較快找到對應索引,加快匹配速度。
(2)無重復項。有重復項時,會延長匹配時間,但不影響匹配結果。
(3)在給定差值范圍內包含所有組合。缺少某些組合,會使一些象素找不到對應索引而采用其他方法,例如使用前一個象素的索引。如果這種象素比較多,會使生成的圖像質量受到影響。
2?增量序列的產生方法
?
顏色分量最大絕對值為1(limit=1)時的序列如表1所示。
?
從部分結果來看,序列滿足以下3個基本條件。
(1)limit的限定,使產生的增量序列整體有序。
(2)由于限定新產生的項,至少包含一個分量為limit或-limit,所以,不產生重復項。
(3)除了缺少(0、0、0)項外,序列包含了絕對值小于33的所有組合,共有274624項,與65×65×65=274625差1。
由于匹配結果直接影響圖像質量,因此,序列中的分量變化范圍不能太大,本文選擇最大絕對值為32。如果匹配過程用完整個序列仍不能找到匹配的顏色,則可用其他方法獲得索引,如用前一個象素的索引代替。實驗結果表明,以這種方式處理,圖像效果比最大絕對值為64時要好。
3? 基于增量序列的調色板索引匹配算法
匹配算法中,待匹配顏色與調色板中的顏色逐個比較,若找到相同顏色,則保存該顏色的索引值,否則根據增量項修正待匹配的顏色值,重新與調色板中的顏色進行匹配,直至找到相同顏色或匹配完所有象素。
匹配算法的具體描述如下:
Step1:增量序列當前指針置0;
Step2:如有未匹配象素,讀取一個待匹配象素顏色值(B0,G0,R0),否則轉Step6;
Step3:掃描調色板,如果找到匹配顏色,則保存其索引值,轉Step1,否則繼續下一步;
Step4:若增量序列未結束,則從指針位置取一增量項(y1,y2,y3),否則,取前一象素的索引作為當前象素的匹配結果,轉Step1;
Step5:求出修正后的待匹配顏色(B,G,R)=(B0+y1,G0+y2,R0+y3),轉Step3;
Step6:輸出圖像文件,結束。
由于灰度值有確定的范圍,所以,Step5中要對修正后的待匹配顏色灰度值作出限制。當原灰度值為正且增量為負時,若得到的灰度值為負值,應設灰度值為0,否則負灰度值將識別為較大的正值,與原值產生很大的誤差,不能保證最佳匹配效果;若灰度值大于255,應設為255,否則計算機舍棄最高位,也會產生較大的誤差。
????增量序列與匹配過程的結合可以采用多任務方式或文件方式來實現。采用多任務方式時,由一個任務產生增量序列,并通過消息發送給匹配過程。匹配過程根據收到的增量項,產生用于匹配的新顏色,并進行匹配。采用文件方式時,用一個過程將增量序列寫入文件,匹配過程每次從文件中讀取一項進行匹配,這種方式的優點在于可一次性生成存儲增量序列的文件,不必每次匹配都重新生成該文件。
4? 實驗結果
利用增量序列對幾幅標準圖像進行匹配,給出了象素匹配的結果。實驗如下:選擇一個256色BMP圖像文件,生成三種基色的灰度值矩陣;每個矩陣做8×8分塊DCT變換,將每一子塊的部分交流系數置0后,做IDCT反變換,重新得到三種基色的灰度值矩陣;對全部象素查找調色板,找出最佳匹配項,生成文件。
將子塊3個最高頻系數置0的結果如表2所示;將子塊10個最高頻系數置0的結果如表3所示。表中的序列號與序列的最大絕對值有關,將最大絕對值分為9類:0、1、2、3、4、5、6～10、11～20、21～32,分別對應表中前9行,每行數字為使用增量序列各序號范圍的象素數,DiffNum為圖像匹配前后索引不同的象素數,百分比為DiffNum占整個圖像象素數的比例。
?
從實驗結果可以看出,變換前后圖像象素索引差別很小,不到1%,2幅圖像看不出明顯區別,這表明索引匹配算法的匹配效果良好。
5? 結束語
本文給出的增量序列與匹配過程進行有機結合,可以對圖像數據進行很好的匹配,匹配后的圖像能夠達到較好的效果。當圖像數據顏色與調色板顏色整體相差較大時,可以先調整調色板數據,再進行匹配。
?
參考文獻
1? 王峰,王向陽,楊紅穎.Windows環境下的邏輯調色板及其應用.計算機工程;1999;25(4)
2? 董韜,陸宗騏.C++ Builder環境下調色板的使用.現代計算機,2001;(4)
3? 張憬,劉云超,陳一民等.基于DCT變換的圖像中的數據隱藏技術及理論.計算機工程,2000;26(12)
4? 夏德深,傅德勝.現代圖像處理技術與應用.南京:東南大學出版社,2001
5? 晶臣工作室.最流行圖像格式實用參考手冊.北京:電子工業出版社,1998
6? 汪小帆,戴躍偉,茅耀斌.信息隱藏技術方法與應用.北京:機械工業出版社,2001