陳超輝，文志強 ，胡俊飛

　　(1. 湖南工業(yè)大學(xué) 計算機與通信學(xué)院, 湖南 株洲 412007；2.智能信息感知及處理技術(shù)湖南省重點實驗室, 湖南 株洲 412007)

       摘要：誤差擴散算法最早是由FloydSteinberg提出，并在當(dāng)時成為處理效果最好的算法之一。它可以輸出視覺效果良好的半色調(diào)圖像，因而得到了廣泛的推廣。為改善該傳統(tǒng)誤差擴散算法均易在中頻區(qū)域產(chǎn)生結(jié)構(gòu)性紋理現(xiàn)象，提出了一種基于跳躍掃描路徑的誤差擴散半色調(diào)算法。算法在對像素點進行掃描時會根據(jù)一定的條件進行跳躍掃描，直接處理若干像素點之后的像素，并將處理后的誤差擴散至相鄰但還未經(jīng)處理的像素點上。大量的實驗表明，合理的跳躍距離能夠幫助有效地抑制半色調(diào)圖像中的結(jié)構(gòu)性紋理，得到效果更好的半色調(diào)圖像，具有更深遠(yuǎn)的意義和實際應(yīng)用價值。

　　關(guān)鍵詞：跳躍掃描；誤差擴散；中頻區(qū)域；結(jié)構(gòu)性紋理

0引言

　　數(shù)字圖像半色調(diào)技術(shù)是基于人眼視覺系統(tǒng)低通濾波特性和圖形成像原理，利用數(shù)學(xué)、計算機及其他工具在二值或多值設(shè)備中模擬原灰度圖像再現(xiàn)的一門技術(shù)。它適用于所有工作原理為有限值記錄的設(shè)備，是數(shù)字印刷過程中的關(guān)鍵技術(shù)之一。研究表明，人眼視覺系統(tǒng)具有低通濾波特性，在相隔一定距離觀察物體時，會將物體在空間上較為接近的部分視為整體。通過這一特性，當(dāng)人眼觀察半色調(diào)結(jié)果圖像時，會從整體上形成連續(xù)色調(diào)的效果，但是傳統(tǒng)誤差擴散半色調(diào)算法得到的半色調(diào)圖像中存在明顯的結(jié)構(gòu)性紋理和“蠕蟲”現(xiàn)象。

　　誤差擴散半色調(diào)算法應(yīng)用范圍一直與人們的生活息息相關(guān)。1975年FLOYD R W和STEINBERG L首次提出了誤差擴散算法［1］，將誤差按照一定的權(quán)值擴散至鄰近的未經(jīng)處理的像素點上，實現(xiàn)了從單獨的點處理到單點及鄰域處理的轉(zhuǎn)變，算法復(fù)雜度低，輸出的半色調(diào)圖像效果好。但是在半色調(diào)圖像中仍然存在一定的不合理現(xiàn)象：輸入圖像中頻區(qū)域在對應(yīng)的半色調(diào)圖像區(qū)域中存在較多的結(jié)構(gòu)性紋理，在光亮和光暗部分容易出現(xiàn)波浪線即“蠕蟲”現(xiàn)象［2］。為解決這兩個問題，后來的研究人員對該傳統(tǒng)誤差擴散算法進行了諸多的改進。在ULICHNEY R A發(fā)現(xiàn)誤差擴散算法產(chǎn)生的半色調(diào)圖像視覺效果與半色調(diào)圖像中隱藏的藍噪聲特性有關(guān)之后，許多研究者依據(jù)藍噪聲特性一步改善了誤差擴散半色調(diào)算法［3］。VELHO L等人提出空間填充曲線的方法［4］，該方法雖然實驗效果較好，但算法復(fù)雜度高。

　　OSTROMOUKHOV V提出了在不同的灰度級上采用不同誤差擴散系數(shù)［5］，參考文獻［6］中通過改進誤差擴散濾波器系數(shù)來改善實驗效果［6］。受國際研究熱潮的影響，國內(nèi)逐漸從背景原理［7］入手，同時也跟緊潮流提出了各種改進的半色調(diào)算法［89］。近些年我國臺灣國立科技大學(xué)郭景明教授及其團隊一直致力于圖像半色調(diào)技術(shù)的研究，提出了多種半色調(diào)技術(shù)方法如：藍噪聲特性與誤差擴散濾波器結(jié)合［10］、多灰度級整體替換［11］、點擴散方法和誤差擴散模型結(jié)合等，這些新方法都不同程度上提高了半色調(diào)圖像的質(zhì)量。本文采用了一種通用的圖像質(zhì)量評價方法對半色調(diào)圖像質(zhì)量進行評價［12］。

　　雖然這些方法在一定程度上提高了半色調(diào)圖像的質(zhì)量，但是始終沒有擺脫半色調(diào)結(jié)果圖像中存在較多的非期望性紋理的問題，尤其是在某些特定的灰度級上存在較為明顯的結(jié)構(gòu)性紋理，高光、暗調(diào)區(qū)域存在明顯的波浪線。針對以上這些算法中存在的明顯問題及誤差擴散中算法中幾個關(guān)鍵因素（像素點掃描方式、誤差擴散濾波器模型、自適用閾值），提出了一種基于跳躍掃描路徑的誤差擴散半色調(diào)算法。該算法主要通過改變影響半色調(diào)圖像效果的掃描路徑，采用自適用閾值的方式來達到更好的實驗效果，該實驗過程中既采用傳統(tǒng)誤差擴散濾波器的模型又采用了新設(shè)計的誤差擴散濾波器模型。為了從客觀上評價各個實驗得到的半色調(diào)圖像質(zhì)量，采用通用圖像質(zhì)量評價指標(biāo)峰值信噪比(Peak Signal to Noise Ratio, PSNR)來進行判斷。

1傳統(tǒng)誤差擴散算法

　　誤差擴散算法由于算法復(fù)雜度低，實驗效果良好，因此一直是應(yīng)用最廣泛的算法之一。傳統(tǒng)誤差擴散算法的核心思想是將灰度圖像當(dāng)前像素點像素值與某一設(shè)定的閾值T相比較，若當(dāng)前像素點像素值大于T，則將當(dāng)前像素點像素值賦為255，并將誤差按照一定的方式擴散到周邊未經(jīng)處理的像素點上；反之則將當(dāng)前像素點的像素值賦0，同樣將誤差擴散到未經(jīng)處理的像素點上?，F(xiàn)假設(shè)P(m, n)為圖像像素點的原像素值，I(m, n)為誤差擴散后圖像像素點的像素值，Q［ ］為量化閾值，B(m, n)為輸出圖像的像素值，E(m, n)為點(m, n)處產(chǎn)生的誤差值，W(m, n)為誤差擴散濾波器的系數(shù)，T(m, n)為像素點(m, n)處對應(yīng)的閾值，在改進的算法中將采用自適應(yīng)方法獲取每個像素點對應(yīng)的閾值。

　　(1)用公式表示原理如下：

　　(2)原理框圖如圖1、圖2所示。

2跳躍掃描誤差擴散算法

　　相對傳統(tǒng)誤差擴散算法，本文提出的跳躍掃描誤差擴散數(shù)字半色調(diào)算法做了四點改變：(1)改變了掃描的方式，以跳躍掃描方式替代原來的光柵、蛇形掃描。(2)改變了閾值的計算方式，采用了自適應(yīng)閾值方法。(3)改變了誤差擴散的具體方式。

　　2.1掃描方式

　　研究表明半色調(diào)圖像質(zhì)量與像素點掃描方式有關(guān)，目前像素點掃描方式有光柵掃描、蛇形掃描［2］、空間填充曲線［4］，能在一定程度上改善半色調(diào)圖像質(zhì)量，但是在某些特定灰度級上始終存在結(jié)構(gòu)性文理。由圖3、4可知不論是光柵還是蛇形掃描方式，在處理同一行上的像素點時，誤差均只能朝一個方向擴散，這容易使得半調(diào)圖像中行與行之間產(chǎn)生紋理。本文提出一種跳躍掃描方式，使得同一行上產(chǎn)生的誤差同時朝左右兩個方向擴散，同時該方式也是一種蛇形掃描方式，能更有效降低半調(diào)圖像中紋理。其基本思想是：同一行分左右兩個處理過程，如圖5所示。

　　2.2基于自適應(yīng)的誤差擴散方式

　　(1)自適用閾值計算

　　式中N要根據(jù)當(dāng)前像素點的位置確定，表示當(dāng)前像素點周圍像素點的總個數(shù)。

　　(2)誤差擴散方式（從左至右掃描）

由于參考文獻［6］的誤差擴散系數(shù)能夠有效地去除輸入圖像在光亮和灰暗區(qū)域的線條，因此在高灰度和低灰度區(qū)域采用該誤差擴散濾波器。奇數(shù)行從左向右掃描，中頻區(qū)采用圖6(a)濾波器，非中頻區(qū)采用圖6(e)濾波器；奇數(shù)行從右向左掃描，若左邊的像素點已被處理，則中頻區(qū)和非中頻區(qū)均采用圖6(b)濾波器，若左邊的像素點沒被處理，則中頻區(qū)采用圖6(c)濾波器，非中頻區(qū)采用圖6(f)濾波器。偶數(shù)行從右向左掃描，中頻區(qū)采用圖6(c)濾波器，非中頻區(qū)采用6(f)濾波器。偶數(shù)行從左向右掃描，若右邊的像素點已被處理，則中頻區(qū)和非中頻區(qū)均采用圖6(b)濾波器，若右邊的像素點沒被處理，則中頻區(qū)采用圖6(a)濾波器，非中頻區(qū)采用圖6(e)濾波器。

3實驗結(jié)果分析

　　文中提到了多種誤差擴散算法，著重分析了三種傳統(tǒng)算法的原理和實現(xiàn)過程，并分析了各個算法的優(yōu)缺點。最后提出了基于跳躍掃描路徑的誤差擴散算法。為了驗證該算法的優(yōu)越性，選擇了大量的灰度圖像進行測試。實驗結(jié)果如圖7，8，9所示，評價指標(biāo)為PSNR，結(jié)果如表1，2，3所示。

　　表1是對圖7用各種算法計算出來的PSNR。 表2是對圖8用各種算法計算出來的PSNR。表3是對圖9用各種算法計算出來的PSNR。從表中可以得知各算法的優(yōu)略，其中JS(N)表示跳躍掃描算法，N表示跳躍距離（以像素為單位）。

4結(jié)論

　　通過實驗分析、對比表明，跳躍掃描誤差擴散半色調(diào)算法和傳統(tǒng)誤差擴散半色調(diào)算法復(fù)雜度相當(dāng)。就實驗效果而言，在一定跳躍距離范圍內(nèi)跳躍掃描誤差擴散算法優(yōu)于蛇形掃描誤差擴散算法，而蛇形掃描誤差擴散算法優(yōu)于光柵掃描誤差擴散算法。就跳躍掃描算法本身的各組實驗而言，d=5為最佳的跳躍距離。

　　參考文獻

　　［1］ FLOYD R W, STEINBERG L. An adaptive algorithm for spatial greyscale［C］. Proceedings of International Symposium of SID， 1976: 36 37.

　　［2］ ULICHNEY R A. Digital halftoning［M］. Cambridge: MIT Press, 1987.

　?。?］ ULICHNEY R A. Dithering with blue noise［J］. Proceedings of the IEEE, 1988, 76(1): 56 79.

　?。?］ VELHO L, GOMES J M. Digital halftoning with space filing curves［J］. Computer Graphics, 1991, 25(4):81 90.［5］ OSTROMOUKHOV V. A simple and efficient errordiffusion algorithm［J］. Proceedings of ACM Siggraph, 2001:567 572.

　?。?］ SHIAU J, FAN Z. A set of easily implementable cofficients in error diffusion with reduced worm artifacts［J］. Deviceindependent Color, Color Hard Copy and Graphics Arts Proc SPIE 2658, 1996,2658:222 225.

　?。?］ 張寒冰,袁昕. 數(shù)字半色調(diào)技術(shù)中的誤差擴散算法的研究［J］.計算機應(yīng)用,2010, 30(4): 925 928.

　?。?］ 葉玉芬,郭寶龍,馬佳. 基于視覺差的誤差擴散半色調(diào)算法［J］.計算機工程,2006,32(16): 195 198.

　　［9］ 田玉敏,柯麗芳,馬勇. 一種改進的基于藍噪聲的誤差分散算法［J］.計算機工程與應(yīng)用，2006,42（26）:60 62.

　?。?0］ FUNG Y H, CHAN Y H. Optimizing the error diffusion filter for blue noise halftoning with multiscale error diffusion［J］. IEEE Transactions on Image Processing, 2013, 22(1): 413 417.

　?。?1］ Guo Jingming, Chang Jiayu, Liu Yunfu,et al. Tonereplacement for multitoning［J］. IEEE Transactions on Image Processing, 2015, 24(11): 4312 4321.

　　［12］ Wang Zhou, BOVIK A C. A aniversal image quality index［J］. IEEE Transactions on Signal Processing Letters, 2002, 9(3):81 84.