基于改進模擬退火算法的LUT逆半調模板選擇

盧永樂，文志強，李建飛

（湖南工業大學計算機與通信學院，湖南株洲412007）

基于改進模擬退火算法的LUT逆半調模板選擇

盧永樂，文志強，李建飛

（湖南工業大學計算機與通信學院，湖南株洲412007）

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

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

0 引言

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

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

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

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

1 LUT逆半調算法的基本思想

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

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

LUT逆半調分為2個階段，即建表階段和逆半調階段。

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

2）逆半調階段。采用與建表時相同的LUT模板對半調圖進行遍歷，將LUT[i]取代當前像素值。

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

2 改進模擬退火算法與LUT逆半調模板選擇

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

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

2）在尋找最優解的過程中，模擬退火算法是以一定的概率接受較差的解，這是該算法全局尋優的關鍵，然而，該環節可能把當前的最優解忽略掉，這樣既浪費了搜索時間，又影響了求解效果。

本文針對LUT逆半調模板的最優化選取問題，提出了一種結合改進模擬退火算法尋求最優模板的方法。模擬退火算法的改進如下：

1）設計具有自適應功能的溫度更新函數。如果某一溫度下的狀態被接受的次數較多，這時可以加大溫度的下降幅度。反之，則減小溫度的下降幅度。

2）搜索過程中增加記憶功能。記住搜索過程中當前的最優解，并隨著搜索的進行實時更新。

改進后的模擬退火算法是一種智能算法。

2.1 灰度圖像LUT逆半調模板選擇

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

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

圖2 狀態編碼示意圖Fig.2 Schematic diagram of state coding

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

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

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

4）狀態接收概率函數。狀態接收概率函數用于判斷新狀態（即新LUT模板）被接受的概率。若新狀態被接受，則將當前狀態更新為新狀態。本文以式（3）作為狀態接收概率函數。

5）溫度更新函數。設置初始化溫度T0，溫度按更新函數逐漸下降，最終達到穩定。根據當前溫度下狀態被接受的次數自動調節溫度下降幅度，設計式（4）～（5）為溫度更新函數。

式（4）～（5）中：為退火因子；N′為Tm溫度下的內循環次數；n為當前溫度下狀態被接受的次數，0＜n≤N′。

基于改進的模擬退火算法求取LUT逆半調模板算法的具體步驟描述如下。

Step 1設定初始值：初始狀態LUT0（即初始模板LUT0）、初始溫度T0、終止溫度Tmin、內循環次數N′。利用LUT0對P幅半調圖像及其對應連續色調圖像進行訓練、建表，并對訓練集中的半調圖像進行逆半調恢復。利用式（1）計算當前狀態LUT0的目標函數值。

Step 2對當前狀態LUT0進行擾動，產生新狀態LUT1。按照Step 1中的計算方式，得到新狀態的目標函數值。再利用式（2）得到ΔE。

Step 3通過式（3）得到P(ΔE)。當新狀態被接受（即ΔE≥0且P(ΔE)＞r，其中，r為隨機浮點數）時，則LUT0=LUT1=。

Step 4在當前溫度下，重復N′次執行Step 2和Step 3，統計該溫度下狀態被接受的次數n。

Step 5根據式5緩慢降低溫度。

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

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

圖3 基于改進的模擬退火算法的最優LUT逆半調模板選擇算法流程圖Fig.3 The flowchart for optimal LUT inverse halftoning template selection based on improved simulated annealing algorithm

2.2 彩色圖像LUT逆半調模板選擇

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

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

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

為了得到最佳彩色逆半調LUT模板，本文在前述的改進模擬退火算法求取LUT最佳模板算法的基礎上進行改進。

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

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

該算法在訓練、建表、逆半調時，均按照模板考慮3個通道的鄰域像素，充分利用了彩色圖像3通道之間的相關性。實驗結果證明了該方法恢復的彩色逆半調圖像具有較好的去噪效果，較高的重建質量，恢復的色彩給人眼視覺效果較好。

3 實驗結果分析

為驗證利用改進模擬退火算法求取最佳LUT模板算法的有效性，本文在VS 2010和Matlab 7.0環境下進行了實驗驗證。由于訓練樣本的數量和內容會影響實驗結果，因此本實驗的訓練樣本來源于網絡http://pan.baidu.com/s/1bnGkLqf圖像庫。

3.1 灰度圖像逆半調實驗

進行灰度圖像逆半調實驗時，選用圖像庫中的60幅512×512的連續色調圖及其對應采用Jarvis,Stucki,Floyd-Steinberg算法產生的誤差分散半調圖。將本文算法與文獻[9]中的傳統模板選擇算法分別對灰度圖像進行逆半調，計算60幅逆半調圖像的平均峰值信噪比[10]。本文算法的參數設置如下：T0=100 000，Tmin=1，N′=40，P=60，N=5，Npixel=19。實驗求得的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幅半調圖像進行逆半調的平均峰值信噪比如表1所示。分析表1中的數據可知，對3類誤差分散半調圖像進行逆半調，本文算法求得的LUT模板的PSNR效果比傳統模板選擇算法的更好。這說明了本文算法比傳統模板選擇算法優越。

表1 模板優劣性對比表Table 1Comparison of different templates

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

圖8 2種算法對Lena半調圖的逆半調結果圖Fig.8 Lena Inverse halftoning results produced by 2 different algorithms

圖9 2種算法對Pepper半調圖的逆半調結果圖Fig.9 Pepper Inverse halftoning results produced by 2 different algorithms

3.2 彩色圖像逆半調實驗

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

利用傳統19鄰域模板（見圖2）與本文的彩色圖像最佳LUT模板對Orange,Little Girl 2幅彩色半調圖像的逆半調結果如圖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半調圖的逆半調結果圖Fig.13 Color orange inverse halftoning results produced by 2 different algorithms

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

利用本文模板對Orange,Little Girl彩色半調圖進行逆半調的峰值信噪比分別為27.070 400,25.119 600，而傳統19鄰域LUT模板對Orange,Little Girl彩色半調圖進行逆半調的峰值信噪比分別為26.762 500和24.743 100。可見，與傳統19鄰域LUT模板相比，利用本文LUT模板對半調圖進行逆半調，結果圖給人眼視覺上的效果更好，色彩還原效果更真實。

4 結語

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

參考文獻：

[1]孔月萍. 圖像逆半調及其質量評價技術研究 [D]. 西安：西安電子科技大學，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]姚莉. 數字半調技術及其評價方法研究[J]. 計算機工程與應用，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]黃麗君，文志強，胡柳. 一種基于 LUT 的圖像逆半調改進算法[J]. 計算機技術與發展，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]. 計算機學報，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，Fu 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]馮起芹，曹小龍，單武揚，等. 印刷品水印圖像的半色調算法比較[J]. 包裝學報，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.

（責任編輯：鄧 彬）

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

國家自然科學基金資助項目（61170102），湖南省自然科學基金資助項目（11JJ3070），湖南省教育廳科研基金資助項目（12A039）

盧永樂（1989-），男，湖南江永人，湖南工業大學碩士生，主要研究方向為數字圖像處理，E-mail：luyongle520@163.com

10.3969/j.issn.1673-9833.2015.01.014