盧永樂，文志強(qiáng)，李建飛

（湖南工業(yè)大學(xué)計(jì)算機(jī)與通信學(xué)院，湖南株洲412007）

基于改進(jìn)模擬退火算法的LUT逆半調(diào)模板選擇

盧永樂，文志強(qiáng)，李建飛

（湖南工業(yè)大學(xué)計(jì)算機(jī)與通信學(xué)院，湖南株洲412007）

針對影響LUT逆半調(diào)圖像質(zhì)量的模板選擇問題，提出了一種基于改進(jìn)模擬退火算法求取最優(yōu)LUT逆半調(diào)模板算法。該算法能對灰度圖像逆半調(diào)，還擴(kuò)展至彩色圖像逆半調(diào)。彩色圖像逆半調(diào)時，充分考慮彩色圖像R,G,B 3通道之間的相關(guān)性，將單通道模板擴(kuò)展為3通道。實(shí)驗(yàn)結(jié)果表明：本算法尋得的模板具有全局最優(yōu)性；與傳統(tǒng)模板選擇算法相比，利用本算法對灰度圖像和彩色圖像進(jìn)行逆半調(diào)的結(jié)果圖在人眼視覺效果上更佳，平均峰值信噪比更高。

逆半調(diào)；模擬退火算法；模板選擇；查找表；彩色圖像

0 引言

半調(diào)是一種將連續(xù)色調(diào)圖像編碼為二值圖像等觀感半色調(diào)圖像）的技術(shù)[1]。由于人眼視覺的低通濾波特性，在一定視覺距離外，人眼觀測到的半調(diào)圖像會與原始連續(xù)色調(diào)圖像相近[2-3]。因此，半調(diào)技術(shù)被廣泛應(yīng)用于圖像的打印、印刷、顯示等領(lǐng)域，其可降低圖像的再現(xiàn)成本，還解決了某些打印、顯示設(shè)備只能處理黑白二值圖像的問題。從原始連續(xù)色調(diào)圖到半調(diào)二值圖是多對一映射關(guān)系，半調(diào)操作是對原始像素值進(jìn)行二值量化，而這樣引入了量化噪聲，因此，半調(diào)過程是圖像退化的過程[4]。

逆半調(diào)是半調(diào)的逆過程，即將二值半調(diào)圖重建為連續(xù)灰度圖。如果直接對二值半調(diào)圖像進(jìn)行圖像放大、壓縮、增強(qiáng)等操作，則會降低圖像質(zhì)量，因此，需對其進(jìn)行逆半調(diào)操作。由于圖像逆半調(diào)是一對多的映射過程，因此半調(diào)圖像無法完美重建。目前，逆半調(diào)技術(shù)主要分為3類：濾波法、最優(yōu)化估值法與機(jī)器學(xué)習(xí)法。其中，濾波法包括高斯低通濾波法、小波變換、FIR（finite impulse response）濾波、非線性濾波技術(shù)等[5]。濾波法主要考慮半調(diào)噪聲在圖像中的分布情況，濾除中、高頻噪聲，但低通濾波法在濾除噪聲的同時，圖像的邊緣和細(xì)節(jié)信息也會損失，使圖像變得模糊。小波變換能夠很好地保留邊緣與細(xì)節(jié)信息，但需要進(jìn)行三層平穩(wěn)小波變換，其算法的空間、時間復(fù)雜度高[6]。最優(yōu)化估值法包括近似迭代、MAP（maximum a posteriori）估計(jì)、POCS（projection onto convex sets）估計(jì)、ED（error diffusion）核估計(jì)法等。最優(yōu)化估值法要求半調(diào)誤差分散核已知或需要根據(jù)一定的先驗(yàn)知識，而在實(shí)際應(yīng)用中很難獲得誤差分散核，且先驗(yàn)知識較為復(fù)雜[1]，因此，基于估值算法的操作難度較高。

LUT（look-up table）逆半調(diào)是一種通過查找索引表來完成圖像重建的方法，是一種典型的機(jī)器學(xué)習(xí)方法，通過分析半調(diào)圖像與連續(xù)色調(diào)圖之間的統(tǒng)計(jì)特征，生成一組從半調(diào)模式到逆半調(diào)值的映射表。該算法無需任何線性濾波器，對半調(diào)圖像的半調(diào)類型無任何要求，具有通用性。該算法只需對訓(xùn)練集進(jìn)行一次訓(xùn)練、建表，且逆半調(diào)過程中只進(jìn)行查表操作，將當(dāng)前像素值替換成連續(xù)值，而不涉及任何復(fù)雜的濾波計(jì)算，因此，其處理速度明顯優(yōu)于其它算法，并且能夠得到較好的圖像重建效果。

LUT模板的大小、形狀以及如何對模板進(jìn)行分塊直接影響了圖像的重建質(zhì)量。近幾年，國內(nèi)外研究學(xué)者提出了多種改進(jìn)的LUT逆半調(diào)算法，如利用圖像紋理信息、神經(jīng)網(wǎng)絡(luò)等。而對直接影響LUT逆半調(diào)質(zhì)量的模板選擇問題卻很少研究。2001年 M. Mese等[9]提出了一種基于貪心算法的LUT模板選擇方法。自此，LUT模板的選擇一直沿用該方法，但該方法并不能求得全局最優(yōu)模板，存在一定缺陷。本文針對選擇最佳LUT模板問題，提出了基于改進(jìn)模擬退火算法的LUT逆半調(diào)最優(yōu)模板選擇算法，以提升LUT逆半調(diào)質(zhì)量。

1 LUT逆半調(diào)算法的基本思想

LUT逆半調(diào)算法的基本思想是：以一組原始連續(xù)圖像及其對應(yīng)的半調(diào)圖像作為訓(xùn)練集，以固定的LUT模板遍歷半調(diào)圖像及其對應(yīng)的連續(xù)圖，遍歷過程中半調(diào)圖像LUT模板中的鄰域像素值與原始圖像中當(dāng)前像素點(diǎn)的連續(xù)值對應(yīng)，從而建立索引表，原理如圖1所示。圖中，半調(diào)圖的LUT模板，a表示的像素點(diǎn)，O表示中心像素點(diǎn)；LUT映射表中，索引值為LUT模板的半調(diào)值（0或1），該索引值對應(yīng)的當(dāng)前連續(xù)值即為逆半調(diào)值。

圖1 LUT逆半調(diào)算法思想示意圖Fig.1 Schematic diagram of LUT inverse halftone algorithm

LUT逆半調(diào)分為2個階段，即建表階段和逆半調(diào)階段。

1）建表階段。初始化LUT[]=0,N[]=0，LUT[]用于存儲半調(diào)模式值到多級連續(xù)值的映射表，N[]用于存儲同一半調(diào)值所對應(yīng)不同多級連續(xù)值的個數(shù)。選擇合適的LUT模板（圖1為傳統(tǒng)rect-16鄰域模板）對每對半調(diào)圖像及其連續(xù)色調(diào)圖像按照從左至右、從上至下的順序進(jìn)行滑動，提取半調(diào)模式與其對應(yīng)連續(xù)色調(diào)值，并將其記錄于LUT表中，即N[i]=N[i]+1,LUT[i]=LUT[i]+g[i]，其中i為一串二進(jìn)制數(shù)值， 即訓(xùn)練模板在半調(diào)圖像中所對應(yīng)的像素值。訓(xùn)練完成后，執(zhí)行LUT[i]=LUT[i]/N[i]，并進(jìn)行空值估計(jì)。

2）逆半調(diào)階段。采用與建表時相同的LUT模板對半調(diào)圖進(jìn)行遍歷，將LUT[i]取代當(dāng)前像素值。

LUT逆半調(diào)算法主要受3個因素影響：訓(xùn)練樣本數(shù)量、空值估計(jì)的準(zhǔn)確度和LUT模板。訓(xùn)練樣本的數(shù)量影響了LUT表的空值率，空值是指在逆半調(diào)過程中遇到了訓(xùn)練樣本中從未出現(xiàn)過的半調(diào)模式值，即沒有連續(xù)色調(diào)值與其索引值對應(yīng)。無限增大訓(xùn)練樣本數(shù)量并不能確?？罩挡怀霈F(xiàn)，反而增加了訓(xùn)練時間，因此，應(yīng)適當(dāng)選取訓(xùn)練樣本數(shù)量?？罩倒烙?jì)可以解決查找表中出現(xiàn)的空值問題，是根據(jù)查找表中的鄰近值或其它數(shù)學(xué)特征確定該索引值對應(yīng)的連續(xù)值的方法。對于空值估計(jì)算法，國內(nèi)外已有一些研究，如高斯低通濾波法、漢明距法和最佳線性估計(jì)法等。LUT模板的大小、形狀以及如何對模板進(jìn)行分塊直接影響了圖像的重建質(zhì)量，國內(nèi)外對LUT逆半調(diào)的改進(jìn)研究中大多結(jié)合紋理信息、模式識別等。而對直接影響LUT逆半調(diào)質(zhì)量的模板選擇問題研究較少，因此，本文針對如何選擇最佳LUT模板，提出了一種全局最優(yōu)模板選擇算法。

2 改進(jìn)模擬退火算法與LUT逆半調(diào)模板選擇

模擬退火算法是一種全局優(yōu)化算法，在局部搜索過程中引入了隨機(jī)擾動機(jī)制[7]。與貪心算法相比，模擬退火算法是以一定的概率接受一個比當(dāng)前解要差的解，因此，有可能跳出局部最優(yōu)到達(dá)全局最優(yōu)解。與遺傳算法相比，采用模擬退火算法求取LUT逆半調(diào)模板可以避免遺傳算法“過早收斂”的缺陷，即由于優(yōu)良個體急劇增加使種群失去了多樣性，從而進(jìn)化個體過早成熟，達(dá)不到全局最優(yōu)解。但直接使用傳統(tǒng)的模擬退火算法求取LUT逆半調(diào)最佳模板存在以下缺點(diǎn)：

1）初始溫度值的確定和溫度下降幅度的控制較難。如果設(shè)置的初始溫度值太大，則退火時溫度下降速度很慢，雖然這樣能夠得到最好解，但是搜索時間較長。反之，則會出現(xiàn)搜索過早結(jié)束，無法找到全局最優(yōu)模板。

2）在尋找最優(yōu)解的過程中，模擬退火算法是以一定的概率接受較差的解，這是該算法全局尋優(yōu)的關(guān)鍵，然而，該環(huán)節(jié)可能把當(dāng)前的最優(yōu)解忽略掉，這樣既浪費(fèi)了搜索時間，又影響了求解效果。

本文針對LUT逆半調(diào)模板的最優(yōu)化選取問題，提出了一種結(jié)合改進(jìn)模擬退火算法尋求最優(yōu)模板的方法。模擬退火算法的改進(jìn)如下：

1）設(shè)計(jì)具有自適應(yīng)功能的溫度更新函數(shù)。如果某一溫度下的狀態(tài)被接受的次數(shù)較多，這時可以加大溫度的下降幅度。反之，則減小溫度的下降幅度。

2）搜索過程中增加記憶功能。記住搜索過程中當(dāng)前的最優(yōu)解，并隨著搜索的進(jìn)行實(shí)時更新。

改進(jìn)后的模擬退火算法是一種智能算法。

2.1 灰度圖像LUT逆半調(diào)模板選擇

利用改進(jìn)后的模擬退火算法求最佳Npixel鄰域LUT模板，部分操作如下。

1）狀態(tài)編碼及狀態(tài)初始化。由于LUT最優(yōu)模板的求解屬于非連續(xù)值問題，因此首先需要對改進(jìn)的模擬退火算法的狀態(tài)（對應(yīng)為LUT模板）進(jìn)行編碼。本文采用二進(jìn)制編碼，LUT模板的像素0表示該點(diǎn)未被選入模板，像素1表示該點(diǎn)被選入模板。規(guī)定LUT模板在一矩形框內(nèi)，假定矩形框?yàn)镹×N，每個編碼中1的個數(shù)保證為Npixel個，即模板大小為Npixel個像素點(diǎn)。模板中心為當(dāng)前待處理像素點(diǎn)，該點(diǎn)的值固定為1。初始化模板時，可將中心點(diǎn)置為1，其余位置隨機(jī)置為0或1，但需保證模板中1的個數(shù)為Npixel個。例如：N=5,Npixel=1 6，則狀態(tài)編碼“1111111111111110111000100”對應(yīng)的LUT模板如圖2所示。圖2為傳統(tǒng)19鄰域LUT逆半調(diào)模板，其中，1的位置可以在5×5框的任意位置，但需要保證中心點(diǎn)為1，且模板像素的大小（即1的個數(shù)）為16個。LUT模板用N×N二維數(shù)組存儲。

圖2 狀態(tài)編碼示意圖Fig.2 Schematic diagram of state coding

2）目標(biāo)函數(shù)。LUT模板的優(yōu)劣主要表現(xiàn)在逆半調(diào)圖像質(zhì)量的好壞。如僅針對某一半調(diào)圖像的重建質(zhì)量，則無法體現(xiàn)該模板的普適性。因此，選擇對P幅半調(diào)圖像進(jìn)行逆半調(diào)處理，再計(jì)算該模板恢復(fù)的圖像的平均峰值信噪比（peak signal to noise ratio，PSNR）。設(shè)計(jì)式（1）作為判斷模板優(yōu)劣的目標(biāo)函數(shù)。

式中：xl,yl分別為第l（l=1,2,…,P）幅圖像的高與寬；Cl(i,j)為第l幅連續(xù)色調(diào)圖像在（i,j）處的像素值；為使用當(dāng)前模板恢復(fù)的第l幅逆半調(diào)圖像在（i,j）處的像素值。

3）新狀態(tài)產(chǎn)生方式。在計(jì)算完當(dāng)前狀態(tài)的目標(biāo)函數(shù)值后，需要對當(dāng)前狀態(tài)進(jìn)行擾動，使其產(chǎn)生新狀態(tài)。對于連續(xù)數(shù)值問題，可以選擇臨近值作為新狀態(tài)。LUT模板屬于離散組合問題，本文對新狀態(tài)的產(chǎn)生按如下方式進(jìn)行：在N×N大小的LUT模板框中隨機(jī)選取一個像素，該點(diǎn)記為A（為方便逆半調(diào)操作，中心像素點(diǎn)不在選取之列）；如果A值為1（0），則再在模板中隨機(jī)選取一個值為0（1）的像素，該點(diǎn)記為B；最后，將A,B 2點(diǎn)位置對換，產(chǎn)生新狀態(tài)。

4）狀態(tài)接收概率函數(shù)。狀態(tài)接收概率函數(shù)用于判斷新狀態(tài)（即新LUT模板）被接受的概率。若新狀態(tài)被接受，則將當(dāng)前狀態(tài)更新為新狀態(tài)。本文以式（3）作為狀態(tài)接收概率函數(shù)。

5）溫度更新函數(shù)。設(shè)置初始化溫度T0，溫度按更新函數(shù)逐漸下降，最終達(dá)到穩(wěn)定。根據(jù)當(dāng)前溫度下狀態(tài)被接受的次數(shù)自動調(diào)節(jié)溫度下降幅度，設(shè)計(jì)式（4）～（5）為溫度更新函數(shù)。

式（4）～（5）中：為退火因子；N′為Tm溫度下的內(nèi)循環(huán)次數(shù)；n為當(dāng)前溫度下狀態(tài)被接受的次數(shù)，0＜n≤N′。

基于改進(jìn)的模擬退火算法求取LUT逆半調(diào)模板算法的具體步驟描述如下。

Step 1設(shè)定初始值：初始狀態(tài)LUT0（即初始模板LUT0）、初始溫度T0、終止溫度Tmin、內(nèi)循環(huán)次數(shù)N′。利用LUT0對P幅半調(diào)圖像及其對應(yīng)連續(xù)色調(diào)圖像進(jìn)行訓(xùn)練、建表，并對訓(xùn)練集中的半調(diào)圖像進(jìn)行逆半調(diào)恢復(fù)。利用式（1）計(jì)算當(dāng)前狀態(tài)LUT0的目標(biāo)函數(shù)值。

Step 2對當(dāng)前狀態(tài)LUT0進(jìn)行擾動，產(chǎn)生新狀態(tài)LUT1。按照Step 1中的計(jì)算方式，得到新狀態(tài)的目標(biāo)函數(shù)值。再利用式（2）得到ΔE。

Step 3通過式（3）得到P(ΔE)。當(dāng)新狀態(tài)被接受（即ΔE≥0且P(ΔE)＞r，其中，r為隨機(jī)浮點(diǎn)數(shù)）時，則LUT0=LUT1=。

Step 4在當(dāng)前溫度下，重復(fù)N′次執(zhí)行Step 2和Step 3，統(tǒng)計(jì)該溫度下狀態(tài)被接受的次數(shù)n。

Step 5根據(jù)式5緩慢降低溫度。

Step 6重復(fù)Step 2～Step 5，直至溫度T＜Tmin。

基于改進(jìn)的模擬退火算法求取LUT逆半調(diào)模板的算法流程如圖3所示。本算法的特點(diǎn)是：該算法增加了記憶功能，保存搜索過程中當(dāng)前出現(xiàn)的最優(yōu)模板，并與新狀態(tài)進(jìn)行對比，更新模板；內(nèi)循環(huán)N′次的目的是，使選擇模板達(dá)到該特定溫度下的平衡；外循環(huán)中，隨著溫度的降低，較差解被接受的概率也會降低，當(dāng)溫度趨近于Tmin（本文Tmin為0）時，不再接受較差解，算法收斂到全局最優(yōu)解。

圖3 基于改進(jìn)的模擬退火算法的最優(yōu)LUT逆半調(diào)模板選擇算法流程圖Fig.3 The flowchart for optimal LUT inverse halftoning template selection based on improved simulated annealing algorithm

2.2 彩色圖像LUT逆半調(diào)模板選擇

當(dāng)前大多數(shù)逆半調(diào)算法主要是針對灰度半調(diào)圖像，而較少涉及彩色半調(diào)圖像[8]。由于彩色半調(diào)圖像在R,G,B 3通道的噪聲和邊緣并非完全獨(dú)立分離，單獨(dú)分析某一通道割離了彩色圖像的整體性，因此，采用針對灰度圖像的逆半調(diào)算法對彩色半調(diào)圖進(jìn)行逆半調(diào)的效果不佳?？紤]彩色圖像各通道之間具有高度相關(guān)性的特點(diǎn)，本文提出了改進(jìn)的彩色圖像LUT逆半調(diào)算法。在LUT訓(xùn)練、建表、逆半調(diào)恢復(fù)階段，通過綜合考慮彩色圖像R,G,B 3通道的像素，預(yù)測彩色逆半調(diào)圖中某一特定通道的連續(xù)色調(diào)值。

本算法先要確定利用哪些彩色通道的哪些像素對當(dāng)前通道的像素進(jìn)行逆半調(diào)恢復(fù)，即明確LUT模板的形式及模板中像素點(diǎn)的分布。將單通道的LUT模板擴(kuò)展至R,G,B 3通道，逆半調(diào)重建X通道（即R或G或B通道），需用到一個N×N×3的模板，N為模板所處的矩形框大小。例如：對R通道進(jìn)行逆半調(diào)，可用圖4所給出的19鄰域LUT模板，該鄰域包括了G,B通道，對G,B通道進(jìn)行逆半調(diào)時，也是采用圖4的LUT模板。因此，該算法除需遍歷3通道外，不會加大LUT逆半調(diào)算法的時間復(fù)雜度。

圖4 R通道的19鄰域LUT逆半調(diào)模板示例Fig.4 Example of R channel 19 neighborhood LUT inverse halftone template

為了得到最佳彩色逆半調(diào)LUT模板，本文在前述的改進(jìn)模擬退火算法求取LUT最佳模板算法的基礎(chǔ)上進(jìn)行改進(jìn)。

1）模板像素的選取及中心點(diǎn)的確定。初始狀態(tài)的產(chǎn)生方式是在N×N×3的矩形框任意位置選取Npixel個像素作為LUT模板像素（需保證中心點(diǎn)為被選之列）。若求取X通道的最佳LUT逆半調(diào)模板，則設(shè)定模板的中心點(diǎn)為N×N×3矩形框中X通道的中心位置（即第3行第3列）。

2）新狀態(tài)的產(chǎn)生方式。在N×N×3的LUT模板框中隨機(jī)選取2個像素，分別記為A,B（中心像素點(diǎn)不在選取之列）。如果A點(diǎn)位置值為1（0），則再在模板中隨機(jī)選取一個值為0（1）的像素點(diǎn)（B點(diǎn)和中心點(diǎn)除外），該點(diǎn)記為C，將A,C 2點(diǎn)位置對換。同理，如果B點(diǎn)位置值為1（0），則再在模板中隨機(jī)選取一個值為0（1）的像素點(diǎn)（A點(diǎn)、C點(diǎn)和中心點(diǎn)除外），該點(diǎn)記為D，將B ,D 2點(diǎn)位置對換，新狀態(tài)產(chǎn)生。該方式旨在加速退火算法的搜索速度，更快接近最優(yōu)解。

該算法在訓(xùn)練、建表、逆半調(diào)時，均按照模板考慮3個通道的鄰域像素，充分利用了彩色圖像3通道之間的相關(guān)性。實(shí)驗(yàn)結(jié)果證明了該方法恢復(fù)的彩色逆半調(diào)圖像具有較好的去噪效果，較高的重建質(zhì)量，恢復(fù)的色彩給人眼視覺效果較好。

3 實(shí)驗(yàn)結(jié)果分析

為驗(yàn)證利用改進(jìn)模擬退火算法求取最佳LUT模板算法的有效性，本文在VS 2010和Matlab 7.0環(huán)境下進(jìn)行了實(shí)驗(yàn)驗(yàn)證。由于訓(xùn)練樣本的數(shù)量和內(nèi)容會影響實(shí)驗(yàn)結(jié)果，因此本實(shí)驗(yàn)的訓(xùn)練樣本來源于網(wǎng)絡(luò)http://pan.baidu.com/s/1bnGkLqf圖像庫。

3.1 灰度圖像逆半調(diào)實(shí)驗(yàn)

進(jìn)行灰度圖像逆半調(diào)實(shí)驗(yàn)時，選用圖像庫中的60幅512×512的連續(xù)色調(diào)圖及其對應(yīng)采用Jarvis,Stucki,Floyd-Steinberg算法產(chǎn)生的誤差分散半調(diào)圖。將本文算法與文獻(xiàn)[9]中的傳統(tǒng)模板選擇算法分別對灰度圖像進(jìn)行逆半調(diào)，計(jì)算60幅逆半調(diào)圖像的平均峰值信噪比[10]。本文算法的參數(shù)設(shè)置如下：T0=100 000，Tmin=1，N′=40，P=60，N=5，Npixel=19。實(shí)驗(yàn)求得的LUT模板如圖5～7所示。

圖5 Floyd-Steinberg最佳19鄰域LUT模板Fig.5 Floyd-Steinberg 19 neighborhood optimal LUT template

圖6 Jarvis最佳19鄰域LUT模板Fig.6 Jarvis 19 neighborhood optimal LUT template

圖7 Stucki最佳19鄰域LUT模板Fig.7 Stucki 19 neighborhood optimal LUT template

2種算法分別對60幅半調(diào)圖像進(jìn)行逆半調(diào)的平均峰值信噪比如表1所示。分析表1中的數(shù)據(jù)可知，對3類誤差分散半調(diào)圖像進(jìn)行逆半調(diào)，本文算法求得的LUT模板的PSNR效果比傳統(tǒng)模板選擇算法的更好。這說明了本文算法比傳統(tǒng)模板選擇算法優(yōu)越。

表1 模板優(yōu)劣性對比表Table 1Comparison of different templates

對2種算法進(jìn)行了測試，比較逆半調(diào)效果，即對由Floyd-Steinberg誤差分散算法產(chǎn)生的Lena和Pepper 2幅半調(diào)圖進(jìn)行逆半調(diào)，效果圖如圖8～9所示。本文模板逆半調(diào)恢復(fù)Lena與Pepper半調(diào)圖的峰值信噪比分別為32.125 500,31.812 700，而采用傳統(tǒng)模板選擇算法逆半調(diào)恢復(fù)Lena與Pepper半調(diào)圖的峰值信噪比分別為31.398 000，30.741 900。可見，本文算法比傳統(tǒng)模板選擇算法的峰值信噪比更高，且人眼視覺上逆半調(diào)圖像的邊緣細(xì)節(jié)恢復(fù)更好。

圖8 2種算法對Lena半調(diào)圖的逆半調(diào)結(jié)果圖Fig.8 Lena Inverse halftoning results produced by 2 different algorithms

圖9 2種算法對Pepper半調(diào)圖的逆半調(diào)結(jié)果圖Fig.9 Pepper Inverse halftoning results produced by 2 different algorithms

3.2 彩色圖像逆半調(diào)實(shí)驗(yàn)

彩色圖像逆半調(diào)實(shí)驗(yàn)時，本文選取了70幅256× 256的彩色半調(diào)圖（由Floyd-Steinberg算法產(chǎn)生）及其對應(yīng)的逆半調(diào)圖。本文算法參數(shù)設(shè)置如下：T0=100 000,Tmin=1,N′=40,P=70,N=5,Npixel=19。利用本文算法求得的彩色圖像最佳19鄰域LUT逆半調(diào)模板如圖10～12所示。

利用傳統(tǒng)19鄰域模板（見圖2）與本文的彩色圖像最佳LUT模板對Orange,Little Girl 2幅彩色半調(diào)圖像的逆半調(diào)結(jié)果如圖13～14所示。

圖10 R通道LUT模板Fig.10 LUT template for R channel

圖11 G通道LUT模板Fig.11 LUT template for G channel

圖12 B通道LUT模板Fig.12 LUT template for B channel

圖13 2種算法對彩色Orange半調(diào)圖的逆半調(diào)結(jié)果圖Fig.13 Color orange inverse halftoning results produced by 2 different algorithms

圖14 2種算法對Little Girl彩色半調(diào)圖的逆半調(diào)結(jié)果圖Fig.14 Little girl color inverse halftoning results produced by 2 different algorithms

利用本文模板對Orange,Little Girl彩色半調(diào)圖進(jìn)行逆半調(diào)的峰值信噪比分別為27.070 400,25.119 600，而傳統(tǒng)19鄰域LUT模板對Orange,Little Girl彩色半調(diào)圖進(jìn)行逆半調(diào)的峰值信噪比分別為26.762 500和24.743 100?？梢?，與傳統(tǒng)19鄰域LUT模板相比，利用本文LUT模板對半調(diào)圖進(jìn)行逆半調(diào)，結(jié)果圖給人眼視覺上的效果更好，色彩還原效果更真實(shí)。

4 結(jié)語

本文針對影響LUT逆半調(diào)質(zhì)量的重要因素—模板選擇問題進(jìn)行了研究，提出了一種基于改進(jìn)模擬退火算法的最佳LUT模板選擇算法，同時，將該算法進(jìn)一步應(yīng)用到彩色圖像LUT逆半調(diào)中，充分考慮彩色像素3通道間的高度相關(guān)性，對彩色LUT模板進(jìn)行了創(chuàng)新設(shè)計(jì)，使其擴(kuò)展到3通道。由于模板鄰域像素?cái)?shù)量保持不變，因此不會增加查找表的空間存儲量及逆半調(diào)操作的時間復(fù)雜度。本文算法對灰度圖像和彩色圖像進(jìn)行逆半調(diào)恢復(fù)的圖像質(zhì)量都能達(dá)到令人滿意的效果。

參考文獻(xiàn)：

[1]孔月萍. 圖像逆半調(diào)及其質(zhì)量評價(jià)技術(shù)研究 [D]. 西安：西安電子科技大學(xué)，2008. Kong Yueping. A Study of Inverse Halftoning and Quality Assessment Schemes[D]. Xi’an：Xidian University，2008.

[2]Liu Yunfu，Guo Jingming，Lee Jiann Der. Inverse Halftoning Based on the Bayesian Theorem[J]. IEEE Transactions on Image Processing，2011，20(4)：1077-1084.

[3]姚莉. 數(shù)字半調(diào)技術(shù)及其評價(jià)方法研究[J]. 計(jì)算機(jī)工程與應(yīng)用，2010，46(3)：4-8.Yao Li. Review on Digital Halftoning and Quality Assessment Schemes[J]. Computer Engineering and Applications，2010，46(3)：4-8.

[4]黃麗君，文志強(qiáng)，胡柳. 一種基于 LUT 的圖像逆半調(diào)改進(jìn)算法[J]. 計(jì)算機(jī)技術(shù)與發(fā)展，2013，23(6)：35-37.Huang Lijun，Wen Zhiqiang，Hu Liu. An Improved Image Inverse Halftoning Algorithm Based on LUT[J]. Computer Technology and Development，2013，23(6)：35-37. [5]Huang Y H，Chung K L，Dai B R. Improved Inverse Halftoning Using Vector and Texture-Lookup Table-Based Learning Approach[J]. Expert Systems with Applications，2011，38(12)：15573-15581.

[6]Xiong Z，Orchard M T，Ramchandran K. Inverse Halftoning Using Wavelets[J]. IEEE Transactions on Image Processing，1999，8(10)：1479-1483.

[7]張德富，彭煜，朱文興，等. 求解三維裝箱問題的混合模擬退火算法[J]. 計(jì)算機(jī)學(xué)報(bào)，2009，32(11)：2147-2156. Zhang Defu，Peng Yu，Zhu Wenxing，et al. A Hybrid Simulated Annealing Algorithm for the Three-Dimensinal Packing Problem[J]. Chinese Journal of Computers，2009，32(11)：2147-2156.

[8]Zhong Yunfei，F(xiàn)u Lujing，Zhou Tao. Based on Median Pyramid Transform of the Color Image Inverse Halftoning [J]. Applied Mechanics and Materials，2012，200：724-729.

[9]Mese M，Vaidyanathan P P. Look-Up Table(LUT) Method for Inverse Halftoning[J]. IEEE Transactions on Image Processing，2001，10(10)：1566-1578.

[10]馮起芹，曹小龍，單武揚(yáng)，等. 印刷品水印圖像的半色調(diào)算法比較[J]. 包裝學(xué)報(bào)，2012，4(3)：34-38. Feng Qiqin，Cao Xiaolong，Shan Wuyang，et al. Comparison Study of Halftoning Algorithm for Printed Watermarking Image[J]. Packaging Journal，2012，4(3)：34-38.

（責(zé)任編輯：鄧 彬）

Template Selection for LUT Inverse Halftoning Based on Improved Simulated Annealing Algorithm

Lu Yongle，Wen Zhiqiang，Li Jianfei
（School of Computer and Communication，Hunan University of Technology，Zhuzhou Hunan 412007，China）

In view of template selection problems which affected the LUT inverse halftone image quality,puts forward a solution to an optimal LUT inverse halftone template based on improved simulated annealing algorithm. The algorithm can be used for grayscale image inverse halftoning and is extended to color image. As for color image halftoning,the correlation between 3 channels of R,G,B color image is considered,and the template is extended from single to triple. The experimental result shows that the proposed algorithm finds template with global optimality,and compares with traditional template selection algorithm,the result picture adopting the optimal template for grayscale and color image inverse halftone restoraion gets better effect in human vision system(HSV) and the average peak signal to noise ratio is higher.

inverse halftoning；simulated annealing algorithm；template selection；look-up table；color image

TP393

A

1673-9833(2015)01-0076-07

2014-11-11

國家自然科學(xué)基金資助項(xiàng)目（61170102），湖南省自然科學(xué)基金資助項(xiàng)目（11JJ3070），湖南省教育廳科研基金資助項(xiàng)目（12A039）

盧永樂（1989-），男，湖南江永人，湖南工業(yè)大學(xué)碩士生，主要研究方向?yàn)閿?shù)字圖像處理，E-mail：luyongle520@163.com

10.3969/j.issn.1673-9833.2015.01.014