基于跳躍掃描誤差擴散半色調算法研究*

陳超輝，文志強 ，胡俊飛

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

?

基于跳躍掃描誤差擴散半色調算法研究*

陳超輝，文志強 ，胡俊飛

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

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

跳躍掃描；誤差擴散；中頻區域；結構性紋理

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

0　引言

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

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

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

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

1　傳統誤差擴散算法

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

(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誤差擴散原理

圖2　F-S誤差擴散濾波器

2　跳躍掃描誤差擴散算法

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

2.1掃描方式

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

圖3　F-S光柵掃描

圖4　F-S蛇形掃描

2.2基于自適應的誤差擴散方式

(1)自適用閾值計算

(5)

式中N要根據當前像素點的位置確定，表示當前像素點周圍像素點的總個數。

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

圖5　跳躍掃描

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

3　實驗結果分析

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

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

4　結論

通過實驗分析、對比表明，跳躍掃描誤差擴散半色調算法和傳統誤差擴散半色調算法復雜度相當。就實驗效果而言，在一定跳躍距離范圍內跳躍掃描誤差擴散算法優于蛇形掃描誤差擴散算法，而蛇形掃描誤差擴散算法優于光柵掃描誤差擴散算法。就跳躍掃描算法本身的各組實驗而言，d=5為最佳的跳躍距離。

圖7　baboon原圖及各實驗結果

圖8　peppers原圖及各實驗結果

圖9　lena原圖及各實驗結果

表1　各實驗PSNR(baboon)(dB)

表2　各實驗PSNR(peppers)　(dB)

表3　各實驗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] 張寒冰,袁昕. 數字半色調技術中的誤差擴散算法的研究[J].計算機應用,2010, 30(4): 925-928.

[8] 葉玉芬,郭寶龍,馬佳. 基于視覺差的誤差擴散半色調算法[J].計算機工程,2006,32(16): 195-198.

[9] 田玉敏,柯麗芳,馬勇. 一種改進的基于藍噪聲的誤差分散算法[J].計算機工程與應用，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

國家自然科學基金(61170102)

TP751.1

ADOI： 10.19358/j.issn.1674- 7720.2016.18.014

2016-06-29)

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

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

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