基于誤差擴散的Dither算法研究與實現

夏 禹，王亞雄

(浙江大學電氣工程學院VLSI研究所，浙江杭州 310007)

1 基于誤差擴散的Dither處理方法

由于受成本等因素的限制，部分低成本液晶的點陣驅動顯示設備的彩色達不到16 777 216(24 bit)種。如果用這樣的顯示設備顯示真彩色，將會出現由于數據地位丟失造成的灰度級合并和彩色失真。要解決顏色壓縮以及壓縮后的顏色失真問題，Dither是一種有效的方法，可大幅提高圖像的顯示質量。誤差擴散法是將當前點的初始值和前邊點擴散后的誤差相加，得到的結果舍去低位后輸出到顯示器，而被丟棄的低位數據作為誤差擴散給后邊的點，從而保證圖像質量。

半影調技術是用兩種顏色顯示出灰度效果的方法。半影調圖案法中，灰度可以用一定比例的黑白點組成的區域表示，從而達到整體圖像的灰度感，黑白點位置的選取稱為圖案化。如圖1中2×2的圖案可以表示5級灰度。

圖1 五級灰度表示圖

同理，如要儲存256級灰度的圖案，就需要16×16的二值點陣，假設灰度級繼續增大，是較為不利的。與此相比，還有一種較好的方法是儲存一個整數矩陣，稱為標準圖案如圖2(a)所示，其中每個點均可取值0～255中的數字。圖像的實際灰度如圖2(b)和圖2(a)標準圖案矩陣中的每個值進行比較，當標準圖案中點的值大于等于實際灰度值時，對應點標注黑點，否則標注白點，圖2為一個25級灰度圖案示例。

圖2 25級灰度圖

目前惟一的問題就是標準圖案矩陣的確定。先以一個2×2的矩陣開始，通過遞歸關系，設矩陣均為方陣，而且其中元素均為1。根據該算法，可得到16級灰度的標準圖案。同理，其也為2×2的方陣，稱為Bayer抖動表。

根據以上算法，如利用一個像素需要用的圖案表示，則原本一幅圖將變換大小。而自然的設想是能否在保持圖像大小不變的情況下利用圖案化技術。其中一種方法是重新取樣，如果利用陣，則將原圖中每點中取一點，然后再應用圖案化技術，就可保持原圖大小不變。實際操作中，該方法并不可行，首先要考慮應該如何取點較為合適，另外間隔過大，取不同點得到的結果差別同樣較大。為解決這一問題，文中采用了以下方法:假設原圖是256級灰度，利用Bayer抖動表，作如下處理。

其中，x，y代表原圖的像素坐標以及該點的實際灰度。以上處理首先將灰度右移兩位變成64級，然后將x和y作模8運算，找到Bayer表中的對應點并將兩者相比較。該算法稱為規則抖動(Regular Dithering)，其特點是，算法簡單且容易實現，缺點是圖案化較為明顯。如圖3(a)和圖3(b)所示。

圖3 灰色原圖與規則抖動后對比圖

2 Floyd－Steinberg抖動

規則抖動中，進行的是圖像點值與標準圖案上點值的比較，這一方法效果并不理想，容易產生較大誤差，而解決的方法可利用誤差擴散，將誤差擴散到鄰近像素。Floyd－Steinberg是一種較為經典的基于誤差擴散的抖動算法，其誤差就是轉換前后像素顏色的差別值，具體的擴散方法如下。

(1)為每個像素尋找最接近的新色彩:1)如果是灰度圖到黑白圖的抖動，此步操作就是簡單的閥值操作。2)如果是更為復雜的，假如從24位色到16位色的抖動，則應該將RGB分開處理，為每個分量分別尋找最接近的值。

(2)計算新色彩與原色彩之間的誤差，即分割誤差成多份，并將誤差擴散到與當前像素鄰近且未被訪問過的元素上。在這些步驟中，最關鍵的步驟就是擴散誤差，最經典的分割誤差比例是其中已被訪問過的像素，X是當前像素，誤差被分割成16份，其中3份分入左下的像素，5份分入下方的像素，1份分入右下的像素，7份分入右方的像素。

另外，誤差的擴散方向同樣需要考慮。因為像素是按照某個方向逐個掃描而來，而誤差不可擴散給已經訪問過的元素，當水平掃描時就存在從左向右掃描和從右向左掃描兩種方式。在實際應用時，文中采用交叉掃描進行，也就是一行從左向右掃描，下一行從右向左掃描。這樣可有效地防止流水效應，即兩行像素因色彩極為接近，在同向擴散時一些色彩突出的像素將出現在同一列附近，如圖4(a)與圖4(b)所示。

圖4 灰度原圖與Floyd－steinberg抖動處理后對比圖

從以上程序得到的圖像可知，運用 Floydsteinberg抖動所得的圖像要明顯優于使用Bayer表抖動所得圖像，誤差擴散可提高圖像的質量。

3 動態閥值

誤差擴散是一種調頻半色調技術，但該技術在圖像高光和暗調以及階調平滑區域會產生“蠕蟲”，同時噪聲較多，導致半色調圖像的邊緣不清晰。在Floyd和Steinberg的誤差擴散算法的基礎上，設計一種新的基于平均閾值和改變掃描路徑的誤差擴散算法——閾值采用平均值法，通過優化平均閾值方法中的γ值得到最優的半色調圖像。

在誤差擴散半色調技術過程中，量化閾值影響對圖像中輪廓邊緣的影響較大。由于半影調圖像只有兩個色調并無中間其他色調，圖像紋理輪廓的形成決定于量化閾值判定各像素的色調。當然這也將受到鄰域傳遞的誤差值影響，但適合的量化閾值可使得半影調圖像的邊緣輪廓較為清楚。文中的誤差擴散算法的閾值量化器中量化閾值為常數127.5，此處采用動態閾值的方法來選擇閾值T(m，n)。由同理可得到動態閥值的24位色向16位色進行Floyd－Steinberg抖動的方法。

4 圖像評價

文中使用的圖像評價指標為峰值信噪比(PSNR)。如認為標準參考影像為信息，且處理結果影像與標準參考影像的差異為噪聲，那么定義結果影像峰值信噪比(PSNR)表達式為其中，M和N分別為影像的寬和高;以Rij和Fij分別為標準影像和結果影像在對應的像素點(i，j)處的灰度值。實驗結果表明，該方法可較好地評價圖像的帶噪和模糊情況，正常情況下，其仍然是評價圖像質量的首選指標。

以4組照片對算法的優劣進行比較，分別計算峰值信噪比。如圖5(a)～圖5(d)所示。

圖5 峰值信噪比計算與對比圖

表1是對以上各圖峰值信噪比(PSNR)的計算結果比較。

表1 峰值信噪比(PSNR)的計算結果

從以上比較可知，對于顏色漸變圖而言，無抖動的峰值信噪比最佳，動態閾值的FS抖動次之，固定閾值的FS抖動PSNR最差，但從直觀的圖像可看出無抖動的圖像顏色突變較為嚴重，而應用FS抖動的兩種處理方式效果較好。

盡管從上述圖像中無法直觀看出動態閾值的優化作用，動態閾值的FS抖動比固定閾值的FS抖動模糊，但其顏色分布較為平滑，且從峰值信噪比同樣可以看出動態閥值優于固定閥值，可推斷假設使用更為合適的選取動態閾值的方法從而得到最優動態閾值，在一定情況下可以優化圖像。

［1］閆敬文.數字圖像處理［M］.北京:國防工業出版社，2007.

［2］徐濤，李冠章.基于小波變換的彩色圖像自適應細節增強算法［J］.計算機應用與軟件，2011(3):246 －248，301.

［3］張寒冰，袁昕.數字半色調技術中的誤差擴散法的研究［J］.計算機應用，2010(4):925 －928.

［4］江玉珍，朱映輝.基于調色板分析及誤差擴散抖動的迷彩仿造［J］.計算機工程與應用，2011(9):1－6.

［5］張寒冰，袁昕.數字半色調技術中的誤差擴散算法的研究［J］.計算機應用，2010(4):75－78.