陳超輝，文志強(qiáng) ，胡俊飛

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

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

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

0引言

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

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

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

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

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

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

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

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

2跳躍掃描誤差擴(kuò)散算法

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

　　2.1掃描方式

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

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

　　(1)自適用閾值計(jì)算

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

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

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

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

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

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

4結(jié)論

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

　　參考文獻(xiàn)

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

　?。?］ 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.

　　［6］ 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ù)中的誤差擴(kuò)散算法的研究［J］.計(jì)算機(jī)應(yīng)用,2010, 30(4): 925 928.

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

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

　　［10］ 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.

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