基于跳躍掃描誤差擴(kuò)散半色調(diào)算法研究*

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

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

?

基于跳躍掃描誤差擴(kuò)散半色調(diào)算法研究*

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

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

誤差擴(kuò)散算法最早是由Floyd-Steinberg提出，并在當(dāng)時成為處理效果最好的算法之一。它可以輸出視覺效果良好的半色調(diào)圖像，因而得到了廣泛的推廣。為改善該傳統(tǒng)誤差擴(kuò)散算法均易在中頻區(qū)域產(chǎn)生結(jié)構(gòu)性紋理現(xiàn)象，提出了一種基于跳躍掃描路徑的誤差擴(kuò)散半色調(diào)算法。算法在對像素點(diǎn)進(jìn)行掃描時會根據(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)用價值。

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

引用格式：陳超輝，文志強(qiáng) ，胡俊飛. 基于跳躍掃描誤差擴(kuò)散半色調(diào)算法研究[J].微型機(jī)與應(yīng)用，2016,35(18)：48-51.

0　引言

數(shù)字圖像半色調(diào)技術(shù)是基于人眼視覺系統(tǒng)低通濾波特性和圖形成像原理，利用數(shù)學(xué)、計(jì)算機(jī)及其他工具在二值或多值設(shè)備中模擬原灰度圖像再現(xiàn)的一門技術(shù)。它適用于所有工作原理為有限值記錄的設(shè)備，是數(shù)字印刷過程中的關(guān)鍵技術(shù)之一。研究表明，人眼視覺系統(tǒng)具有低通濾波特性，在相隔一定距離觀察物體時，會將物體在空間上較為接近的部分視為整體。通過這一特性，當(dāng)人眼觀察半色調(diào)結(jié)果圖像時，會從整體上形成連續(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]。為解決這兩個問題，后來的研究人員對該傳統(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]入手，同時也跟緊潮流提出了各種改進(jìn)的半色調(diào)算法[8-9]。近些年我國臺灣國立科技大學(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ì)量評價方法對半色調(diào)圖像質(zhì)量進(jìn)行評價[12]。

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

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

(1)

B(m,n)=T[I(m,n)]

(2)

E(m,n)=B(m,n)-I(m,n)

(3)

(4)

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

圖1　F-S誤差擴(kuò)散原理

圖2　F-S誤差擴(kuò)散濾波器

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)時，誤差均只能朝一個方向擴(kuò)散，這容易使得半調(diào)圖像中行與行之間產(chǎn)生紋理。本文提出一種跳躍掃描方式，使得同一行上產(chǎn)生的誤差同時朝左右兩個方向擴(kuò)散，同時該方式也是一種蛇形掃描方式，能更有效降低半調(diào)圖像中紋理。其基本思想是：同一行分左右兩個處理過程，如圖5所示。

圖3　F-S光柵掃描

圖4　F-S蛇形掃描

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

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

(5)

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

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

圖5　跳躍掃描

由于參考文獻(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)過程，并分析了各個算法的優(yōu)缺點(diǎn)。最后提出了基于跳躍掃描路徑的誤差擴(kuò)散算法。為了驗(yàn)證該算法的優(yōu)越性，選擇了大量的灰度圖像進(jìn)行測試。實(shí)驗(yàn)結(jié)果如圖7，8，9所示，評價指標(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為最佳的跳躍距離。

圖7　baboon原圖及各實(shí)驗(yàn)結(jié)果

圖8　peppers原圖及各實(shí)驗(yàn)結(jié)果

圖9　lena原圖及各實(shí)驗(yàn)結(jié)果

表1　各實(shí)驗(yàn)PSNR(baboon)(dB)

表2　各實(shí)驗(yàn)PSNR(peppers)　(dB)

表3　各實(shí)驗(yàn)PSNR(lena)　(dB)

[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.

[3] ULICHNEY R A. Dithering with blue noise[J]. Proceedings of the IEEE, 1988, 76(1): 56-79.

[4] 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.

[7] 張寒冰,袁昕. 數(shù)字半色調(diào)技術(shù)中的誤差擴(kuò)散算法的研究[J].計(jì)算機(jī)應(yīng)用,2010, 30(4): 925-928.

[8] 葉玉芬,郭寶龍,馬佳. 基于視覺差的誤差擴(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.

[11] 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.

Study on halftone algorithm of error diffusion based on jump-scanning

Chen Chaohui， Wen Zhiqiang， Hu Junfei

(1.School of Computer and Communication, Hunan University of Technology, Zhuzhou 412007, China; 2.Key Laboratory of Intelligent Information Perception and Processing Technology (Hunan Province), Zhuzhou 412007, China)

The algorithm of error diffusion is first proposed by Floyd-Steinberg and has become one of the best algorithms of dealing result at that time. It can output a better visual halftone picture, so it is extended widely. To improve the phenomenon that traditional error diffusion causes structure texture easily in the mid-frequency, a halftone algorithm of error diffusion based on jump-scanning is put forward. When the algorithm is scanning the pixel point, it will jump to the point which is behind several points according to some certain condition, deals with the current pixel point and diffuse the dealing error to the around pixel point that is not coped. A number of experiments show that reasonable jumping distance can help repress the structure texture effectively and have better half tone dealing result, and can have more reality significance.

jump scanning; error diffusion; mid-tone area; structure texture

國家自然科學(xué)基金(61170102)

TP751.1

ADOI： 10.19358/j.issn.1674- 7720.2016.18.014

2016-06-29)

陳超輝(1989-),通信作者,男,在讀碩士研究生,主要研究方向：圖像處理。E-mail:1433692592@qq.com。

文志強(qiáng)(1973-)，男，教授，主要研究方向：圖像處理、人工智能。

胡俊飛(1990-)，男，在讀碩士研究生，主要研究方向：圖像處理。