摘? 要: 生成帶調(diào)色板的圖像文件時,需要解決調(diào)色板索引匹配的問題。針對該問題,本文提出了一種增量序列的產(chǎn)生方法,并基于這種序列,給出了一種調(diào)色板索引匹配算法。

　　關鍵詞: 增量序列? 調(diào)色板? 索引值? 匹配算法

?

　　圖像處理時,經(jīng)常需要生成帶有調(diào)色板的圖像文件。各種類型的圖像文件一般采用壓縮存儲方式,解壓后彩色圖像數(shù)據(jù)可表示為三基色的灰度值。圖像數(shù)據(jù)在轉(zhuǎn)換為帶調(diào)色板的圖像文件時,如果所占用的顏色空間小于調(diào)色板所能表示的顏色數(shù)目,則可以實現(xiàn)無失真的轉(zhuǎn)換;如果圖像數(shù)據(jù)的顏色空間大于調(diào)色板數(shù)目,則轉(zhuǎn)換過程需要舍棄部分顏色。為了使圖像達到較高的保真度,應將舍棄的顏色轉(zhuǎn)換為調(diào)色板中與之最相近的顏色。為此,本文提出了一種基于增量序列的調(diào)色板索引匹配算法。

1? 知識描述

　　BMP圖像文件是一種常用的圖像格式,圖像數(shù)據(jù)可采用壓縮、非壓縮2種方式存放,較多采用非壓縮方式。BMP圖像文件由三部分組成:文件頭、調(diào)色板數(shù)據(jù)和索引數(shù)據(jù)。調(diào)色板數(shù)據(jù)對不超過256色的圖像模式都要進行設置。調(diào)色板中紅、綠、藍三種基色數(shù)據(jù)的排列順序與其他圖像文件格式相反。對256色非壓縮方式而言,調(diào)色板由256項組成,每項代表一種顏色,其索引編號從0～255,圖像數(shù)據(jù)為象素點的索引。

　　圖像數(shù)據(jù)生成帶調(diào)色板的圖像時,如果圖像數(shù)據(jù)的顏色空間超過調(diào)色板空間,則會出現(xiàn)一些調(diào)色板中沒有的顏色。此時,可采用匹配算法,在調(diào)色板中找出與該顏色最接近的顏色索引。在匹配過程中按遞增順序修改該顏色灰度值,以找到最佳匹配項,并使該顏色灰度值的修改盡量小。匹配過程所用的增量序列滿足以下3個基本條件。

　　(1)整體有序。因為圖像變換要求基本維持原圖像的效果,所以大部分象素灰度值與調(diào)色板中某顏色的灰度值之差較小。匹配從最小項開始,可以較快找到對應索引,加快匹配速度。

　　(2)無重復項。有重復項時,會延長匹配時間,但不影響匹配結(jié)果。

　　(3)在給定差值范圍內(nèi)包含所有組合。缺少某些組合,會使一些象素找不到對應索引而采用其他方法,例如使用前一個象素的索引。如果這種象素比較多,會使生成的圖像質(zhì)量受到影響。

2?增量序列的產(chǎn)生方法

?

　　顏色分量最大絕對值為1(limit=1)時的序列如表1所示。

?

　　從部分結(jié)果來看,序列滿足以下3個基本條件。

　　(1)limit的限定,使產(chǎn)生的增量序列整體有序。

　　(2)由于限定新產(chǎn)生的項,至少包含一個分量為limit或-limit,所以,不產(chǎn)生重復項。

　　(3)除了缺少(0、0、0)項外,序列包含了絕對值小于33的所有組合,共有274624項,與65×65×65=274625差1。

由于匹配結(jié)果直接影響圖像質(zhì)量,因此,序列中的分量變化范圍不能太大,本文選擇最大絕對值為32。如果匹配過程用完整個序列仍不能找到匹配的顏色,則可用其他方法獲得索引,如用前一個象素的索引代替。實驗結(jié)果表明,以這種方式處理,圖像效果比最大絕對值為64時要好。

3? 基于增量序列的調(diào)色板索引匹配算法

　　匹配算法中,待匹配顏色與調(diào)色板中的顏色逐個比較,若找到相同顏色,則保存該顏色的索引值,否則根據(jù)增量項修正待匹配的顏色值,重新與調(diào)色板中的顏色進行匹配,直至找到相同顏色或匹配完所有象素。

　　匹配算法的具體描述如下:

　　Step1:增量序列當前指針置0;

　　Step2:如有未匹配象素,讀取一個待匹配象素顏色值(B0,G0,R0),否則轉(zhuǎn)Step6;

　　Step3:掃描調(diào)色板,如果找到匹配顏色,則保存其索引值,轉(zhuǎn)Step1,否則繼續(xù)下一步;

　　Step4:若增量序列未結(jié)束,則從指針位置取一增量項(y1,y2,y3),否則,取前一象素的索引作為當前象素的匹配結(jié)果,轉(zhuǎn)Step1;

　　Step5:求出修正后的待匹配顏色(B,G,R)=(B0+y1,G0+y2,R0+y3),轉(zhuǎn)Step3;

　　Step6:輸出圖像文件,結(jié)束。

　　由于灰度值有確定的范圍,所以,Step5中要對修正后的待匹配顏色灰度值作出限制。當原灰度值為正且增量為負時,若得到的灰度值為負值,應設灰度值為0,否則負灰度值將識別為較大的正值,與原值產(chǎn)生很大的誤差,不能保證最佳匹配效果;若灰度值大于255,應設為255,否則計算機舍棄最高位,也會產(chǎn)生較大的誤差。

????增量序列與匹配過程的結(jié)合可以采用多任務方式或文件方式來實現(xiàn)。采用多任務方式時,由一個任務產(chǎn)生增量序列,并通過消息發(fā)送給匹配過程。匹配過程根據(jù)收到的增量項,產(chǎn)生用于匹配的新顏色,并進行匹配。采用文件方式時,用一個過程將增量序列寫入文件,匹配過程每次從文件中讀取一項進行匹配,這種方式的優(yōu)點在于可一次性生成存儲增量序列的文件,不必每次匹配都重新生成該文件。

4? 實驗結(jié)果

　　利用增量序列對幾幅標準圖像進行匹配,給出了象素匹配的結(jié)果。實驗如下:選擇一個256色BMP圖像文件,生成三種基色的灰度值矩陣;每個矩陣做8×8分塊DCT變換,將每一子塊的部分交流系數(shù)置0后,做IDCT反變換,重新得到三種基色的灰度值矩陣;對全部象素查找調(diào)色板,找出最佳匹配項,生成文件。

　　將子塊3個最高頻系數(shù)置0的結(jié)果如表2所示;將子塊10個最高頻系數(shù)置0的結(jié)果如表3所示。表中的序列號與序列的最大絕對值有關,將最大絕對值分為9類:0、1、2、3、4、5、6～10、11～20、21～32,分別對應表中前9行,每行數(shù)字為使用增量序列各序號范圍的象素數(shù),DiffNum為圖像匹配前后索引不同的象素數(shù),百分比為DiffNum占整個圖像象素數(shù)的比例。

?

　　從實驗結(jié)果可以看出,變換前后圖像象素索引差別很小,不到1%,2幅圖像看不出明顯區(qū)別,這表明索引匹配算法的匹配效果良好。

5? 結(jié)束語

　　本文給出的增量序列與匹配過程進行有機結(jié)合,可以對圖像數(shù)據(jù)進行很好的匹配,匹配后的圖像能夠達到較好的效果。當圖像數(shù)據(jù)顏色與調(diào)色板顏色整體相差較大時,可以先調(diào)整調(diào)色板數(shù)據(jù),再進行匹配。

?

參考文獻

1? 王峰,王向陽,楊紅穎.Windows環(huán)境下的邏輯調(diào)色板及其應用.計算機工程;1999;25(4)

2? 董韜,陸宗騏.C++ Builder環(huán)境下調(diào)色板的使用.現(xiàn)代計算機,2001;(4)

3? 張憬,劉云超,陳一民等.基于DCT變換的圖像中的數(shù)據(jù)隱藏技術及理論.計算機工程,2000;26(12)

4? 夏德深,傅德勝.現(xiàn)代圖像處理技術與應用.南京:東南大學出版社,2001

5? 晶臣工作室.最流行圖像格式實用參考手冊.北京:電子工業(yè)出版社,1998

6? 汪小帆,戴躍偉,茅耀斌.信息隱藏技術方法與應用.北京:機械工業(yè)出版社,2001