TWI290305B - Digital halftoning technique based on 1-D multi-scale dot assignment - Google Patents

Description

.1290305 九、發明說明： 【發明所屬之技術領域】 本發明係關於 驟 ’種線型半色調方法，其包含以下步 a·對輸入影像之一列像素 b.進行半色調演算法，及 I f $八+ 以產生對應的輸出列。

半色调决异法3有—個主要階段· A /•一個自上向下的網點分配（top-down Dot ^gnment)階段，其中以小波分析dew analysis) 為基礎为配一新亮度值予一網點；及 枯* I誤差擴散階段’其中網點分配係與原始亮度 :相比較，且量化誤差係擴散至下一或若干線 素0 於網點分配階段中，所揭示之半色調架構係採用 一種模仿來自1—D小波分析之結果之網點分配方式。 此與大。卩分現存半色調演算法中之逐像素網點分配方 式不同。 於誤差擴散階段中，網點分配係與原始亮度值相 比較且里化誤差係擴散至下一或若干線（即目前線之 下方的線）中之像素，作為局部回饋機制，俾進一步改 良視覺品質。 最後’使用後處理技術以去除人工圖案。 【先前技術】 數位半色調係為一種對於僅可代表有限數目輸出 色調的印刷或顯示裝置提供連續色調影像效果之技 1290305 術。為了代表每一灰階，半色調演算法產生紋理的圖 案，當被觀看的人察知時此圖案具有固定灰階之外 觀。此等圖案被局部地調整為以自然地代表影像的細 節。 於設計半色調演算法之過程中，必須進行以下改 良： A.良好的視覺效果。所產生的影像由觀看者看 起來必須儘可能地與連續色調原始影像相同。再者， 於不同的細節等級下（Level of details，LoD)(相當於印

刷或顯示裝置之不同解析度），應獲致良好的視覺效 果。 B·有效率的實現。為了在實體裝置中進行，重要 的是演算法的計算複雜性和記憶體空間需求是低的。 現存的數位半色調技術可分類為三個主要範_ ·· (1)反覆式優化（iterative optimization)、（2)抖動 (dithering)及（3)誤差擴散（error diffusi〇n)。此等技術 之每一者以及技術的組合具有其自己的優點及缺點。 一般而言，由於反覆式優化技術需要遠較高的計算成 本，故其主要為學術性利益所用。抖動及誤差擴散係 為二種更為人所廣泛研究作為實際工業實施方式之範 疇。可進一步改良二種方式以成為適應性半色調技 術。於適應性半色調（adaptive halft〇ning)中，可根據 輸入像素值來調整門檻及濾波器權重。此三種技術的 簡略回顧如下。 A.反覆式優化 反覆式優化方法嘗試使根據某些基礎方法，例如 人類視覺系統(HVS)，連續色調影像與半色調影像間之 ‘1290305 ί知誤差ί到最小。誤差通常係藉加權最小平方法計 算。以計算複雜性為代價，由此類技術導出之 影像通常具有高品質。一種實例為直接二元搜尋，^ 揭示於 D· J· Lieberman 及 j· ρ Allebach ,，，用於直接 二，元搜尋之雙重詮釋以及其對於色調重現及紋理品 質，IEEE Transaction of Image Processing ,第 g 卷， 第 1352-1366 頁，2000 年 11 月。 B·抖動及篩選

_抖動提供另一類型之半色調技術，其係於量化之 刖將雜訊加入影像中。導入雜訊以破壞固定灰階區中 之誤差累積的單調性，使得半色調影像更類似於原來 的影像。其方法係顯示於圖1中。 雖然白色雜訊（white noise)係為一種於隨機程序 (random process)中通常已知類型的雜訊，但卻未使用 於半色調技術中，因為其產生成簇網點（clustered dots)，此將降低半色調影像的視覺品質。藍色雜訊及 綠雜訊通常於抖動文獻中選擇，尤其藍雜訊。藍色雜 訊的一種特性在於，其係為專有高頻率藍色雜訊。由 於人眼的低通本性，高頻率藍色雜訊最不能由人類觀 察者看到者（凊參照R· A. Ulichney，’’數位半色調技 術’’，㈣，1987 ;及 R· A· Ulichney，，，具藍雜訊 之钤動”，Proceedings of IEEE，％ Ί6 卷，第 56—Ί9 頁，1988年1月）。然而，具藍色雜訊之抖動對於無 法逐點再現網點之裝置而言（例如雷射印表機），效果 並不好。取而代之地，如闡釋於D. L. Lau，G. R. Aree 及N. C. Gallagher，”綠色雜訊數位半色調技術，，， 〇//五五五，第 86 冊，第 2424—2444 頁，1998

1290305 年12月，綠色雜訊係由中等頻率之訊號所構成。其他 細節係揭示於 D· L· Lau，R. Ulichney 及 G· R· Arce，，， 藍及綠雜訊半色調模型”，/五五五尸⑺“川·叹 ，第 28-38 頁，2003 年 7 月。 實務上，於半色調之前加入雜訊不是有效率的實 施方法’因為需要虛擬亂數（必須線上產生或儲存）。 基於此理由，於工業上以直接雜訊加入法實施抖動是 罕見的。取而代之地，抖動係適合做為一種供瞭解的 模式’並且必須藉其他獲致相當效果之演算法實施。 就另一方面而論，篩選（screening)係為一種在實 際上普遍實施的半色調法。該篩選是一個週期性地施 加於影像之臨界值矩陣（thresholds matrix)。為了同時 利用篩選技術以及藍色和綠色雜訊，可使用藍色雜訊 遮罩（mask)及綠色雜訊遮罩，如揭示於例如T· Mitsa 及Κ· J. Parker，”使用藍色雜訊遮罩之數位半色調技 術 ”，/· Opi· 5W. ，第 9 卷，第 1920—1929 頁， 1998; Κ· E. Spaulding，R· L. Miller 及 J. Schildkraut，，， 產生用於數位半色調之藍色雜訊抖動矩陣之方法，，，又 /maghg，第 6 卷，第 2 號，第 208-230 頁， 1997 ;以及 D· L. Lau，G· R. Arce 及 N. C. Gallagher，，， 經由綠色雜訊遮罩之數位半色調，，，丄 乂wer.，第 16 卷，第 1575 —1586 頁，1999 年 7 月。空 洞和群集法（void_and-cluster method)為產生遮罩之最 有名的方法’如揭示於r· A· Ulichney，’’用於抖動陣 列產生之空洞和群集法’，，山叹SP/五，//“爪㈣ Vision, Visual Processing, Digital Displays IV9 % 1913 卷，第332 - 343頁，1993。由於筛選係為低複雜性的 半色調技術，故其常見於工業中（請參見美國專利第 5,726,772 號）。

1290305 c·誤差擴散 誤差擴散方式係首先由R W Fl〇yd及L Steinberg揭示於“空間性灰階用之適應性演算法”， Proceedings of Society of Information Display International Symposium Digest of Technical Papers ^ 第36-37頁’ 1975年3月。基本構想在於使用自身校 正的回饋系統來處理引入量化程序中之誤差。誤差擴 散至未處理的相鄰像素。誤差擴散法係顯示於圖2中。 當人類檢視時，經由誤差擴散所產生的半色調影 像似乎更類似原來的樣子。紋理更平順。然而，誤差 擴散確實留下一些人為缺陷，例如波紋圖案（m〇ir6 patterns)及方向磁滯。波紋圖案是將規則圖案重疊於 一影像上之結果。為了克服不美觀的波紋圖案，可放 大誤差擴散濾波器的大小，以及分配不同的權重數 值’如揭示於例如J· jarvis及C. Roberts，，，一種於二 階顯示器上顯示連續色調影像之新穎技術，，，/五五五 Transactions on Communications ^ % 891-898 頁，1 976 年 8 月；J· Jarvis，C· Judice 及 W· Ninke，”於二階顯 示器上顯示連續色調圖像之技術調查”，

Graphics and Image Processing、第 5 ，專 13—40 頁， 1976;以及P. Stucki，’’用於二階硬拷貝複製之Meccaxa 多誤Μ:梭正計算演算法”，Research Report RZi060， IBM Research Laboratory，1981。另一種降低人為缺 陷之方式為使用蛇行掃描代替光柵掃描，如揭示於R. A· Ulichney，”具藍色雜訊之抖動” ，Proceedings of /五五五，第76卷，第56-79頁，1988年1月）；以及 Witten及R· Neal，”使用皮亞諾（peano)曲線於二階顯 示連績色 Μ 影像 ”，IEEE Computer Graphics and ‘1290305

Applications，第 47—5 1 頁，1982 年 5 月。 D.適應性技術 目前抖動、篩選及誤差擴散已增強為適應影像的 内容。一般來說，係藉著使臨界值及濾波器權重可變 來達成適應性。為了獲致適應性，需考量若干因素： (1)像素值、（2)邊緣表現（edge behaviors)以及（3)人類 視覺系統（HVS)。

由於半色調將灰階影像改變為二值化影像，介於 輸入與輸出影像之間的邊緣表現變為不同。因此，一 致性已成為適應性半色調技術領域之研究焦點。經由 測試由誤差擴散所採用之不同濾波器，Ζ· Fan及F. Li (誤差擴散之邊緣表現”，尸山·

International Conference on Image Processing，第 1 13-116頁，1995年10月）發現，當提加強部分時間 邊緣時，其有時是模糊不清的。因此，其揭示一種非 線性邊緣增強技術，並使用HVS因子以便利用人眼的 低通特性。 有一種關於以最小平方誤差標準為基準之適應性 半色調的工作（使用HVS)。於此情形下，根據局部像 素值調整半色調，如揭示於，，適應性模式基礎、的半色調 合併影像増強”，proceedings 〇了 J5th Internati〇nal C〇nference on Pattern Rec〇gniti〇n，第 $ 卷第 $⑽一 頁、’ 2000年9月。於美國專利第6,76〇，126號揭示之 方法中，像素係以二種不同的罩幕抖動二次，並且具 有一個暫時輸出，其係根據邊緣活性及抑制參數而合 =。依此方式，此方法適用於具低和高活性二者之影 。由於抖動並不是主流半色調技術，文獻中對於適 應性抖動有相當少的作品。 1290305 有較多以若干固定濾波器或以色調濾波器進行適 應性誤差擴散之研究。美國專利第5,737,453及 6,356,362號揭示一種根據灰階值應用若干不同矩陣 之方法，例如針對極度灰階之二項矩陣以及針對中色 調之四項矩陣。中色調至極度灰階過渡之矩陣係藉内 差法而得。誤差擴散方式係以HVS及邊緣表現為基準 而增強，如揭示於美國專利第6,563,957號以及ρ· Li 及J. P. Allebach，，，依色調而定的誤差擴散”，/五五五

Transactions on Image Processing、％ 春、專 2 览、

第201-215號’ 20 04年2月。已發展出依色調而定的 臨界值，故可降低邊緣效應及啟動延遲。 亦已採用具有可變權重之平行掃描 ........丨文W 人馬 缺陷。P.W. Wong (“適應性誤差擴散及其於多解析表 現今之籐用”，IEEE Transaction on Image ，第 5 卷，第 1184一1196 頁，1996 年 7 月） 考$到超過一種固定誤差擴散濾波器，其中係於半色 調過程中調整濾波器。其目的為使誤差達到最小，並 且使用最小平均平方（LMS)演算法自適應性信號處理 進行執行。於P. W. Wong，“適應性誤差擴散及其於多 解析表現中之應用”，Trcmsacti〇n 第 5 卷’第 1 184-1 196 頁，1996 年 7 月， ，揭示之P.D. Wong的研究的另一優點在 供 多解析表現。 /、』杈供 2使用抖動或誤錢散技術會產生—些缺點。 :美國專利第5,970，178號中揭示之半色調方 JJ，二種方法的優點。首先藉某些方法評估。灼 =區域’，忙碌，，及’，豐富，’，亦即具有精細的資訊1 = 擴散法。否則就使用平坦抖動法。使用可變 見，，占尺寸亦可獲致具誤差擴散之適應性抖動，如於美

1290305 國專利第6,778,299號中所揭示。 有一些針對適應性臨界值的研究，例如於N. Damera-Venkata及B· L· Evans，，，用於誤差擴散半色 调之適應性臨界值調整^/五五五^㈣〜以化似㈣/所吓泛

ProawMg，第 1〇 卷，第 i 號，第 1〇4一 116 頁，2001 年1月；以及美國專利第5,268,774號中所揭露的内 容。於Damera-Venkata及Evans的文章中，量化處理 (quantization process)已暗示性地被模型化，因此可使 用廣泛類型的量化器。於美國專利第5,268,774號所 揭示之方法中係使用抖動圖案、像素值及邊緣增強技 術來決定臨值。針對使用不同臨界值調整架構之誤差 擴散改良之調查係揭示於R. Eschbach，Z. Fan，K. T. Knox及G. Marcu，”於誤差擴散中之閾值調整及安定 性”，IEEE Signal Processing Magazine，第 39 一 5〇 頁， 2003年7月。 雖然適應性半色調技術提供更舒適的視覺結果， 但其真實效果係隨印表機而不同。這是因為印表機具 有不同的印刷能力、網點大小及網點形狀。舉例來說， 某些雷射印表機隨著彼此不同而於一致性印網點方面 具有問題。大部分印刷裝置之其他常見的問題為網點 重疊及網點擴大。印表機可產生一些與相鄰者重疊的 圓網點，此係稱為網點重疊效應。再者，印表機可產 生似乎比所需者為大之網點，此係稱為網點擴大。此 等概念係闡釋於圖3中。因此，研究以印刷模式為基 準之半色調技術是重要的，如揭示於美國專利第 5,592,592 號；T. N. Pappas 及 Neuhoff，”最小平方模 式基礎的半色調 ”，IEEE Transactions on lmage 尸roca以wg，第 8 卷，第 1102-11 16 頁，1999 年 § 月； 以及 Τ· N· Pappas，J_ P. Allebach 及 D. L. Neuhoff，，， 12

1290305

模式基礎的數位半色調” M

MagazMe，第 14—27 頁，2003 年 7 月。 E.彩色半色調 除了上述針對灰階影像之半色調技術外，針對彩 色影像之半色調技術亦是重要的。有超過一種彩色影 像系統，每一者係具有多色平面，例如CMYK (青綠 色、品紅色、黃色及黑色）或RGB (紅色、綠色及藍色） 系統。針對灰階半色調所發展之誤差擴散技術可直接 地應用於彩色影像，因為人眼對於不同頻率之不同著 色平面具有不同的敏感性。因此，當應該分開地考量 每一著色通道（colorant channel)時，亦必須檢視不同 通道之間的交互作用。彩色半色調之議題係描述於j. L· Mitchell，G· Thompson 及 C. W. Wu，“多階彩色半 色調，，’ ’ 2001 年 12 月；美國專 利第6,501，564號，2002年12月；以及n Damera-Venkata，B. L· Evans,及 V· Monga，“彩色誤 轰嫌散年色調”，IEEE Signal Processing Magazine， 第51 -58頁，2003年7月。 F·多解析法 半色調技術之最後二種範疇為小波基礎 (wavelet-based)及多解析基礎（multi-resolution-based) 的半色調技術。小波轉換已用於逆半色調（reverse halftoning)技術中，如揭示於 ζ· Xi0ng，m.T. Orchard 及Κ· Ramchandran，”使用小波之逆半色調”，

Transaction on Image Processing，第 8 卷，第 U)號， 第 1479—1483 頁，1999 年 10 月；R· Neelamani，R·

Nowak 及 R· Baraniuk，”使用小波-vagueiette 逆卷積 13 .1290305 運算之模式基礎逆半色調” ’ ProceW/wgs 0/2000 International Conference on Image Processing，第 3 卷，第 973—976 頁，2000 年 9 月；a&C.Kuo，A· Ravishankar Rao及G. Thompson，”小波基礎的半色調 分割反除網過濾設計”，Proceedings of 2001 IEEE International Conference on Acoustics，Speech，and Signal Processing (ICASSP)、％ 卷，％ \5Ί2> — \5Ί6

頁，2001年5月。逆半色調係將二色調影像轉換為連 續色調影像。一種使用非正交小波達到逆半色調之新 方法係揭示於 Ζ. Xiong，Μ.Τ. Orchard及 Κ. Ramchandran ’ IEEE Transaction on Image 尸roc〜sMg，第 8 卷，第 10 號，第 1479—1483 頁，1999 年10月。此技術有時稱為除網或無網（請參照美國專 利第 5,799，112 及 6,738,524 號）。 小波轉換亦用於預處理階段，如揭示於H. Szu，Y. Zhang，Μ· Sun及C.-C. Li，”以小波轉換預處理為基礎 之神經網絡適應性數位影像篩選半色調（digital image screen halftoning ，dish)”，SPIE Proceedings % 2243 卷，第 963—966 頁，1994 年 4 月；以及 H· Szu，Y. Zhang， Μ· Sun及C.-C· Li，’’以小波轉換預處理為基礎之神經 網絡適應性數位影像篩選半色調（dish)，，，尸⑺Cee山、以 of 1993 International Joint Conference on Neural (7/CWA9 ,第 2 卷，第 1215-1218 頁，1993 年10月。由於小波轉換提供一種獲致空間及局部定位 之機制，所以是一種用於影像分析之良好工具。使用 小波轉換被用來尋找頻率資訊，然後進一步用來控制 篩選功能。 於Szu等人之文章中所揭示的方法是使用二維小 波轉換以及神經網絡技術。因此，其需要大的貯存空

1290305 間及大量的計算。本發明亦使用小波分析，但此方法 與其非常不同。僅一維小波轉換應用於本發明之演算 法。再者，本發明之小波分析是用在網點分配，而不 是篩選功能控制。 有一些針對多解析半色調之報告，包含pw. Wong ’ “適應性誤差擴散及其於多解析表現中之應 用 ” ’ IEEE Transaction on Image Processing，第 5 卷’ 第 1 184-1 196 頁 ’ 1996 年 7 月；以及 I· Katsavounidis 及C_-C. Jay Kuo，’’用於數位半色調之多階誤差擴散 技#ί ” ， IEEE Transaction on Image Processing » 第 6 卷，第3號，第483-490頁，1997年3月。多解析半 色調概念已被引入以產生半色調，且多階誤差擴散方 法係於 H. Szu，Y· Zhang，M. Sun 及 C._C. Li，，，以小波 轉換預處理為基礎之神經網絡適應性數位影像筛選半 色調（dish)”，*S/7五尸 roceWMg，第 2242 卷，第 963—966 頁’ 1994年4月’以及於Katsa^vounidis及Kuo的文 章中被提出。首先，其需要大記憶體空間的二維處理。 其次’其使用不是非常有效率的逐像素網點分配架構 (pixel-by-pixel dot assignment scheme)。 本發明之演算法使用小波轉換及多階網點分配概 念。然而，本發明和習知的研究在以下幾個方面有所 不同。半色調方法係為線型的（line-based)，並且係以 自上向下方式分配網點。亦採用誤差擴散法來微調半 色調影像及補償因為隱式量化所產生的誤差。一維處 理使得實施容易，而自上向下的多階網點分配可產生 多解析半色調影像，提供良好的多階原型近似效果。 【發明内容】 15

!29〇3〇5 覺效S有ΐί:第一目的為提供一種可提供良好視 率執行之半色調方法，*中所產生的影 者而S儘可能類似連續色調的原始影像。 明第二目的為提供一種半色調方法，其可於 對應於印刷或顯示裝置之不同解析 級下〇eVeUfdetail，LGD)獲致良好的視 ，，，第三目的為提供一種半色調方法，其中演 异法之计异複雜性及記憶體空間需求是低的。 、 =發明之半色調技術使用小波分析以設定網點分 用-種vrr分配階段中，所揭示的半色調架構係採 =仿來自一維小波分析之結果之網點分配方 分現存半色調演算法中之逐像素網點分 配万式不同。 此外，本發明之半色調技術包含誤差擴散階段。 於誤差擴散階段階段中’網點分配係與原始亮度值相 比較’且量化誤差係擴冑至下一或若干線（即目前線之 下方的線）中之像素，作為局部回饋機制，俾進一 良視覺品質。 最後，於網點分配階段及/或選擇誤差擴散階段之 後，可使用後處理技術去除人工圖案。 使用小波分析設計新穎半色調演算利用獲得輸入 信號之空間及頻率域資訊的能力之優點。輸出半色調 影像保留輸入影像的低頻分量。此時，亦可妥善地保 留局部區域中之輸入影像的細節，例如邊緣及二理y 較佳實施例揭示一種非常類似小波係數之網點分配機 制，使得網點密度（或墨水密度）於不同規模下與小波 係數的大小呈正比。 Μ 【實施方式】

1290305 通則 本發明係關於一種線型半色調方法，其包含以下步 驟：對輸入影像之一列像素進行小波分析；及進行一 半色調演算法，以產生對應的輸出列。 如圖4所示，本發明較佳實施例之半色調方法包 3、自上向下的網點分配階段，於此階段中以小波分 析為基礎來分配一新亮度值予網點。此外，較佳實施 例可包含一個選用的誤差擴散階段，於此階段中的網 點分配係藉由與原始亮度值相比較並將量化誤差擴散 至下一或若干線中之像素而達成。 熟習本技藝之人士當可明白，較佳方法所用之小 波轉換及多階網點分配概念就一般而言是已知的。然 而，本發明之方法與使用小波分析及多階網點分配之 先前技術的不同在於半色調法係為線型且以自上向下 方式分配網點。雖然基於此目的可使用除了誤差擴散 外之方法，本實施例中採用誤差擴散法來對半色調影 像進行微調並補償因隱式量化所產生的誤差，但也可 使用其它的誤差擴散方法來達成同樣的目的。一維處 理使得實施容易，而自上向下的多階網點分配可產生 多解析半色調影像，並於多階中提供良好的原型近似 效果。 於圖4所示之方法中，使用厂以代表大小从 之輸入灰階影像，其中影像大小係以像素數目定義（即 輸入影像於一列具有％像素及於一行具有私像素）。 每一像素具有正規化（normalized)灰階，其數值可為介 於0與1之間之任一數目，其中〇係對應最亮的灰階 (純白）且1為最暗的灰階（純黑）。 就另一方面而論，使用代表大小射。之輸 17 1290305 出半色調影像。於輸出影像中之每一像素僅採用〇或 1之一元數值。為了喷墨印表機之實施，適用於作 為控制一系列喷墨頭之喷嘴之準則。當。wi(z·，y) = i 時，喷嘴係於位置（/，y)處噴出一滴黑墨水（或一網 點），g仏《心·，y) = 〇時’無墨水喷出。因此，數位半 色調法可視為近似法，係、用以產生輸出具有類似輸入 灰階影像的灰階密度之網點密度分布之二值影像 F out ° 一般而§，輸出影像大小係大於輸入影像大小， 即I»%。不失一般性地，可假設你一 軋且I == %，因為通常可内插輸入影像，俾使輸入和 輸出影像具有相同的影像尺度。 較佳半色調法之許多步驟的詳細討論如下。铁 而，熟習本技藝之人士當可明白，以下所述之特殊: 波分析、網點分配及誤差擴散技術僅為 實施例，且其 係涵蓋於本發明之範圍内，俾改變可實現相同整球 月之此專技術或替代技術。

輸出及出入影侔宕義

於所示之方法中，使用代表大小Μ, χΛ^·之於A

灰階影像，其中影像大小係以像素數目定義（即輪I 像於一列具有％像素及於一行具有从像素）。每一: 素具有常態化灰階，其數值可為介於〇與丨之間 一數目，其中0係對應最亮的灰階（純白）且丨 的灰階（純黑）。 取1暗 就另一方面而論，使用尸_代表大小 出半色調影像。於輸出影像中之每一像素僅採用^ 】

1之二元數值。為了噴墨印表機之實施〜適 ： 為控制一系列喷墨頭之喷嘴之準則。當乃L 18

1290305 時’喷嘴係於位置G·，y)處噴出一滴黑墨水（或一網 點），當力=0時，無墨水喷出。因此，數位半 色調法可視為近似法，係用以產生輸出具有類似輸入 灰p自衫像的灰階密度之網點密度分布之二值影像 F〇ut ° 一般而言’輸出影像大小係大於輸入影像大小， 即< >> Μ,.且乂 >> μ。不失一般性地，可假設= Μ且a = Μ，因為通常可内插輸入影像，俾使輸入和 輸出影像具有相同的影像尺度。 [波分柄 、 根據本發明之較佳實施例，藉由以一維小波轉換 為基礎近似（approximating)多解析度原始影像的灰階 密度可實質上降低計算複雜性。 就長度爪之一維（1-D)空間信號go(相當於第量列 輸入灰階影像）而言，1-D小波分析係由最多1〇g2#階 所構成。根據圖4中所示之方法，自以開始，藉著以 近似（approximate)用之低通濾波器l〇—d以及細節 (detail)用之高通濾波器Hi—D對進行go卷積 (convolving)，半色調演算法得到二組大小為队;2之係 數（亦即近似係數c山及細節係數cR)，接著進行二元 取樣（dyadic decimation)。接著，使用相同架構將近似 係數_分為二部分从及Cj〇2，並且以取代厂(）。 接著’如圖5所示，反覆地將此分析應用於〇 \ + 驟中。 2 v 網點分配 較佳半色調法所用之半色調演算法的第— 為自上向下分配階段，其中以小波分析為基礎 階段係 之新亮 19

1290305 度值分配網點。此階段使用網點分配演算法自最高層 至最低層計算網點密度。 於網點分配階段之第一步驟是針對輸入列進行小 波轉換以得到小波係數。於第k階段之近似係數的重 建數值，灸=log2#)代表整列像素之平均網點密 度。因此，可得到該列所需之網點的總數。由於網點 數目為整數，必須量化平均密度至最接近的整數。接 者將整列分為一個次區間，而於第k階段之細節係 數的重建數值（cA，灸=log2#)是代表此二個次區間之 間的網點密度。只要細節係數被包含及用於重建，則 將目前的區間分為二個次區間，並可獲得此等次區間 之間之網點密度差。反覆地進行此方法，直到達到含 有單一像素之最低層為止。明顯地，當移到較低細微 階層時’量化效果將變得愈來愈嚴格。 圖7顯示相較於圖6所示之線及哈爾（Haar)小波 (睛看圖8)之網點分配的小波分析結果。為了簡單說 明’假設如上述之輸出影像具有與輸入影像相同之大 小（礼=M,· = 5 12，％ = % = 5 12)。圖4中之低通和高 通據波係數係關於針對分析選用之小波函數。為了簡 化，選擇哈爾小波。然而，適用其他基礎函數也可行 的。 圖9顯示獲得網點密度分布之重建及區間分開法 的首先四個步驟。我們可以根據該區間之網點密度及 長度來分配每一區間的網點數目。此網點分配從最粗 略階層（僅僅有一區間）開始至最細微階層（即一像素 長度）被反覆處理。圖1 〇說明根據圖9之網點密度分 佈之網點分配樹。 假&輸出影像具有與原始影像相同的解析度（即 I = ’則網點分配的基本構想是在不同的階（scale) 1290305 近似巧〉的網點密度。首先，以多層細節來建構次區 間。總共有log2#層。於每一層中，將像素陣列分 為相同長度的二元區間。於第j層處（〇 < y < 1〇g2#)， 有2y個長度各為ν/2;之區間。/^代表第j層之第k區 間。再者，/)八及％分別代表用於輸入及輸出影像之 仏的強度準位。

應注意的是，可經由小波轉換以自下向上 (bottom-up)方式從最細微階層而被算出。於最細微階 層中，每一區間僅含有一像素，且=之(〇⑷。為了找 到以為全部j•及A:近似化，必須具有

Nk 輸入強度：ZV= X矸)㈣ (1) i 匁〇 ㈣!，;=〇 ,m=] 輸出強度：

，其他 (2)

其中[·]代表達到最接近整數之捨入運算。根據方 程式（2)，網點分佈由從最粗略階層（第〇層）至最細微 階層（第1〇82#層）而被遞歸（recursively)計算，其中每 一區間僅含有一像素。最終的結果集合 = 為在第i列之輸出像素陣列g。 誤差擴散 於誤差擴散階段，半色調像素數列與相同列之原 始像素數列相比較，並且將量化誤差擴散至下一列之 相鄰像素。 於數學上，量化誤差可寫為： 21 (3)1290305 E.=F(i)^G. 1 in ^ 列 接著，可使用以下遮罩將誤差擴散於下一像素陣 〇 0 0 〇 H= 0 0 0 〇 0·1 0.2 0.4 0.2 0 0令 0.1 目前的處理列

熟習本技藝者當可明白，以上提供之遮罩僅 施例，且不同遮罩可用於特殊方面。一般而言，哈 錯誤法對於選擇最佳遮罩而言是必要的。/ § ° 此外，熟習本技藝者當可明白，發展出_種 遍擴散架構以將量化誤差擴散於多列中亦是可能的。曰

後處理 一種有關以上演算法之問題為，有時可於輸出今 像中觀察到簇區（cluster*)(亦即一些連續黑色或白色= 素可能定期地出現於局部區域）。為了處理此問題，網 點分配處理可藉著應用以下的除簇技術在第二 ;; . 不 取細破 層y = i〇g2iV-i而被加強。也就是說，就藉由分開區間 仏所產生之二元區間及/(川)(叫而言^‘ ’則此方法需要，丄臨 界值Γ設定為7^=0.1。 複雜性分折 茲分析所揭示之半色調法的計算複雜性如下。就 維度Μ及iV之影像而言’必須對每一區間厂々μ 程式（2)，其中〇句·幺log2#且1幺灸< 2y。囡^ 鼻方 J 因此，方程 22 式（2)需要£2，=〇(ΛΓ)次之複雜性 7=0 此外

1290305 必須對全部區 間計算£)八。當觀察到 = 可建立且有以n ^ SB U 〇 + /)(2^7)乃(川）（2幻時， J : 〇/為根且以Uu，為葉之二 ★、:母一像素严㈨僅涉及一加法。因此，總共有“Μ 人加法。為了完成除簇技術，、- 層0。，中之區Μ，並且修飾第二最、階 ^為複人雜性_的次數後，於輸入影像中有M 歹J故王4影像的計算複雜性為0(M7V)。 一接著，本案發明人考量到記憶體需求。由於所揭 不的半色調演算法一次處理一列輸入影像，故目前分 配的緩衝區可再度使用於下一列。必須儲存量化誤 差，以用於擴散程序。因此，記憶體需求將等於幾列， 且總記憶體需求為。 、、，發明已藉由較佳具體實施例特別地顯示及描 述，熟習本技藝之人士將很容易地理解本案得由熟悉 本技藝之人士為諸般改變及修飾，然皆不脫本發明之 精神及範圍。 舉例來說，可藉其他技術取代以上詳述之小波分 析、強度或網點密度計算及誤差擴散技術。此外，應 理解誤差擴散階段是選擇使用的，並且可由其他微調 方法取代。 因此’發明不欲受以上說明或附圖限制，但僅受 如附申請專利範圍界定。 23

1290305 【圖式簡單說明】 圖1為習知的抖動法之示意圖。 圖2為習知的誤差擴散法之示意圖。 圖3說明一些習知印表機所遇到之網點重疊及網 點擴大效果。 圖4為提供本發明半色調法概觀之示意圖。 圖5為小波分析之第一步驟的示意圖。 圖6(a)為多階小波濾波器組之示意圖。 圖6(b)為一輸入序列之樹形分解小波係數之示意 圖。 圖7(a)顯示將應用本發明半色調技術之輸入影 像。 圖7(b)為自圖6(a)之輸入影像取出之一列。 圖8為小波分析應用於圖7(b)之列之示意圖。 圖9為說明哈爾（Haar)小波之圖。 圖10(a)至i〇(d)顯示個別網點密度分布係為較佳 半色調法之前四個步驟重建。 圖11為根據圖10(a)至10(d)之網點密度分布應用 於圖7(b)之列的網點分配示意圖。 24

Claims (1)

1290305 十、申請專利範圍： a.對輸入影像之一列像素進行小 b·進行一半色調演算法，以產=耠 其中該半色調演算階段包含-自i向下 =段’其中以小波分析為基礎分配一新亮度值予; 2、如申請專利範圍第丨項所述之方法， 分析之該步驟包含，自輪入與儋 ^ 進订小沾 自輸入衫像f之第i列開始·· 〜a.藉由以近似係數之低通濾波器l〇 d及 =係數之高通遽波器Hi_D與彻而得到… H N/2之係數，近似係數从及細節係數、、， 者進行二元取樣； ^ 及 b·使用相同架構將該近似係數 ，並且以c山取代 <);以及 分為二部分cd2 c·反覆地重複步驟&及b達（l〇g2Ar)次。 h如申請專利範圍第2項所述之方法，其中用於該小 波刀析之該小波係為哈爾（Haar)小波。 4如申請專利範圍第1項所述之方法，其中針對相當 於第i列輸入灰階影像之長度％的一維空間信號，二 網點分配階段包含以下步驟： a.針對該輸入列進行小波轉換，以得到小波係數； ^ b•基於第k階層之近似係數的重建數值為而獲 知讀列所需之網點總數，其中灸=log2#且代表整 列像素之平均網點密度； e·量化平均密度至最接近的整數； d·將該列分為二個次區間； e.將第k階段之細節係數的重建數值作為此二 25 l29〇3〇5 次區間之間之網點密度差；及 f·反覆地重複步驟a至e，直到 之最細微層為止。 建幻3有早一像素 申請專利範圍第4項所述之方法，其中用 波为析之該小波係為哈爾（Haar)小波。八 ；w小 6、如中請專利範圍第4項所述之方法， 粗略層(第0層)至其中每-區：堇 7 > t νίΙΐΐ'Γ ^1〇827V 申明專利範圍第6項所述之方法，更包含A傻 陣列驴形式之輸入函數在不同岬、^更匕3為像素 驟·· / 由数在不冋階近似網點密度之步 建構具有多階層細節之次區間； …，每一階層巾’將該像素陣列#，分為相同長度的 二使得於第j階層處(0。、10㈣有2y個長 ΐ λ/抽之區間’並且針對全部7.及“十算輸出強 度Λ^·，俾近似化輸入強度。 如申請專利範圍帛7項所述之方法，纟中該輸入及 輸出強度係根據以下二式計算而得：

輸出強度： D, D N 其他 （2) 0-1) [f] 其中[·]代表達到最接近整數之捨入運算，仏代表 第j階層之第k區間，且及％分別代表用於該輸 入及輸出影像之/^的強度階層。 26 1290305

於第二最細微層y = i〇g2#-1施加除簇技術之後處理步 驟：就藉由分開區間所產生之二元區間+ 及 + 而言， 如果|2化，則設定 义摩=ZV2，且臨界值Γ設定為卜0·1。 28