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

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

?

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

1? 知識(shí)描述

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

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

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

　　(2)無(wú)重復(fù)項(xiàng)。有重復(fù)項(xiàng)時(shí),會(huì)延長(zhǎng)匹配時(shí)間,但不影響匹配結(jié)果。

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

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

?

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

?

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

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

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

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

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

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

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

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

　　Step1:增量序列當(dāng)前指針置0;

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

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

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

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

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

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

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

4? 實(shí)驗(yàn)結(jié)果

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

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

?

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

5? 結(jié)束語(yǔ)

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

?

參考文獻(xiàn)

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

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

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

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

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

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