1、 .反走樣技術的研究摘要反走樣技術是提高光柵圖形顯示質量的重要技術之一。研究如何消除或減緩走樣現象，給人視覺上產生更舒適光滑的圖形，在圖形界面已成為人機交互主流方式的今天，具有一定的應用價值。在查閱了大量文獻資料的基礎上，本文從現有的反走樣技術（如普通區域取樣、普通過取樣、加權過取樣）入手，對反走樣的理論基礎和實現技術進行了分析研究。普通區域取樣是將直線看成具有一定寬度的狹小矩形，當直線與像素相交時，求出兩者相交區域的面積，然后根據相交區域的面積來確定像素的亮度值，從而達到反走樣效果。而過取樣是在提高分辨率下用點取樣方法計算，然后對幾個像素的屬性進行平均得到較低分辨率下的像素屬性。由于需要對每

2、個像素進行處理，因此速度比區域取樣明顯慢了很多。普通區域取樣和過取樣都是在整數坐標上進行的,而WU像素反走樣算法采用了非整數坐標改進,視覺效果比前兩者更好。本文的研究重點在直線段反走樣、曲線反走樣和圖像處理速度方面進行了研究和改進。為了提高過取樣的速度，充分利用直線段像素可能存在的多段相似性，算法對其中的一段進行反走樣處理后，其余各段只要簡單地復制即可，比普通過取樣算法明顯具有優勢，速度提高了很多，也為并行處理提供了可能。在現有的反走樣文獻中，對曲線反走樣提及較少，本文對圓的反走樣算法及實現進行了分析探討，充分利用圓的八對稱性，以加權過取樣算法為基礎在畫圓的同時進行反走樣。第三方面的工作是如何

3、提高編程實現速度，常用的一種技術是利用Pixels方法，它通過對像素點逐個進行處理，分別對紅色、綠色、藍色分量進行處理來實現圖形的反走樣。這個方法雖然簡單、直觀，但處理速度緩慢。通過對Delphi圖像處理機制的分析及實驗，提出了利用Scnaline方法的改進方案，使處理速度提高到Pixels方法的50倍左右。關鍵詞:反走樣，區域取樣，過取樣本文由天空樂園大學生旅游網整理分享 一、研究背景光柵圖形顯示器是目前使用最廣泛的圖形顯示器，因為它具有以下優點：光柵掃描顯示器具有固定的刷新順序，掃描從屏幕的左上角開始，從左到右，從上到下的順序進行刷新，從而刷新控制部件得以簡化，節約了成本。在光柵顯示系統中

4、，構成圖形的最小圖形元素是像素，這樣只要計算屏幕上位于給定區域以內的所有像素，并且賦予一定的顏色，就完成了圖形的繪制。光柵顯示器中的圖形由像素構成，而每一個像素又可呈現出多級灰度或不同的顏色值，顏色豐富，顯示出來的圖形具有更好的視覺效果。光柵掃描顯示器是一個畫點設備，與圖形的復雜度無關，刷新頻率固定，因此不會象隨機掃描顯示器那樣出現閃爍現象，人眼看上去更舒服。但光柵顯示器也有它的缺陷，圖形信號是連續的，而光柵顯示系統中用來表示圖形的卻是一個個離散的像素。用離散的像素來表示連續的圖形時會出現失真，也就稱為走樣，如圖1.1所示。圖1.1鋸齒狀邊界光柵顯示系統為何會出現走樣呢？光柵圖形顯示器是一個畫

5、點設備，被顯示的線段、字符、圖形及背景色都按像素點一一存儲在幀緩沖存儲器中。當我們要畫一條直線時，它通常不可能完全精確地從一個可編址的像素點畫一條直線到另一個可編址的像素點，只可能用盡可能靠近這條直線路徑的像素點集來近似地表示這條直線。顯然只有畫水平線、垂直線時，像素點集在直線路徑上的位置才是準確的，其他情況下的直線均或多或少地存在階梯狀（鋸齒狀）的現象。光柵圖形的走樣現象除了上述鋸齒狀邊界外，還有圖形細節失真，狹小圖形遺失等現象。圖1.2 圖形細節失真在光柵顯示器上顯示如圖1.2(a)所示的細長矩形時，出現了圖形細節失真，其結果如圖1.2(b)所示，原細長的矩形被顯示成了加寬的矩形。圖1.3

6、 狹小圖形的遺失由于光柵系統中表示圖形的最小單位是一個像素，圖形中那些比像素更窄的細節丟失了，這就出現了圖形細節失真現象。在圖1.3中，一些狹小的圖形分布在兩條掃描線之間，由于它不覆蓋任何一個像素中心，故不會被顯示出來。當這些狹小的圖形進行運動時，覆蓋像素中心時被顯示出來，不覆蓋像素中心時不被顯示出來。這樣在運動的過程中時隱時現，產生閃爍。為了提高圖形的顯示質量，需要減少或消除上述走樣現象。用于減少或消除這種走樣現象的技術，稱為反走樣（Antialiasing）。研究如何消除或減緩這類走樣現象，給人視覺上產生更舒適光滑的圖形，在圖形界面已成為人機交互主流方式的今天，具有一定的應用價值。反走樣技

7、術能提高圖形的顯示質量，因此在很多畫圖軟件中也采用了這種技術。優軟電腦有限公司設計推出的新一代繪畫程序-優軟精靈畫筆2.0，在原有的各種繪畫功能上，添加了一系列全新設計的繪畫工具；可以打開外來JPG，TAG，TIFF，GIF，BMP文件；更新三維立體窗口系統；對壓力感應筆高效率支持，速度和流暢度達到專業軟件水準，讓用戶的體會更加細膩逼真。它的精妙之處在于具有細筆尖反走樣功能，所以使細筆畫更細致更漂亮。反走樣技術不僅能提高圖形顯示質量,而且在反走樣漢字方面也有很好的效果。由于漢字的筆畫很多,而且大多數非水平非垂直,也會產生較嚴重的走樣現象。圖1.4中第1 個字為追蹤出的輪廓,第2 個為顯示的原始

8、矢量字符。第3 個為反走樣處理后的矢量字符。圖1.4矢量字體輪廓的反走樣由此可見，反走樣技術在實際應用中有十分重要的意義。另外, 在處理紋理圖形, 以及在動畫中閃爍的細小物體圖形等問題中反走樣技術都得到了廣泛運用。二、反走樣技術概述在光柵顯示器上顯示圖形時，直線段或圖形邊界或多或少會呈鋸齒狀。原因是圖形信號是連續的，而在光柵顯示系統中，用來表示圖形的卻是一個個離散的象素。這種用離散量表示連續量引起的失真現象稱之為走樣(aliasing)，走樣是伴隨著光柵顯示系統而出現的，也是數字化的必然產物。用于減少或消除這種效果的技術稱為反走樣(antialiasing)。第一章中已經介紹了光柵圖形的走樣現

9、象除了階梯狀的邊界外，還有圖形細節失真(圖形中的那些比象素更窄的細節變寬)，狹小圖形遺失等現象。常用的反走樣方法主要有：提高分辨率、區域采樣和加權區域采樣等。下面將對他們進行介紹。2.1 過取樣技術 反走樣的方法很多，一種簡單的反走樣方法是以較高的分辨率顯示對象，如圖2.1。假設把顯示器分辨率提高一倍，直線經過兩倍的象素，鋸齒也增加一倍，但同時每個階梯的寬度也減小了一倍，所以顯示出的直線段看起來就平直光滑了一些。這種反走樣方法是以4倍的存儲器代價和掃描轉換時間獲得的。因此，增加分辨率雖然簡單，但是不經濟的方法，而且它也只能減輕而不能消除鋸齒問題。但是它的思想給我們以后的反走樣方法一定的啟示。圖

10、2.1 提高顯示分辨率一種可行的反走樣方法：在較高分辨率下用點取樣方法計算，然后對幾個像素的屬性進行平均得到較低分辨率下的像素屬性。這種技術稱為過取樣（Supersampling），或后濾波（Postfiltering）。該技術是把顯示器看成是比實際更細的網格來增加取樣率，然后根據這種更細的網格使用取樣點來確定每個屏幕像素合適的亮度等級。 反走樣的另一種方法是根據圖形對象在每個像素點上的覆蓋程度率來確定像素點的亮度，這種計算覆蓋率的反走樣技術稱為區域取樣（Area Sampling），或前濾波（Prefiltering）。2.1.1 提高分辨率方法過取樣方式的一個簡單實現是用較高的分辨率進行計

11、算，如圖2.2，在x方向和y 方向上把分辨率提高一倍，使每個像素都對應4個子像素，然后掃描轉換求得各子像素的顏色亮度，在對4個像素的顏色亮度進行平均，得到較低分辨率下的像素顏色亮度。由于像素中可供選擇的子像素最大數目是4，因此，該例中提供的亮度等級數是5。如圖2.2中，編號為1和7的像素亮度級別是1，編號為2，3，4，5和6的像素亮度是2。通過這個方法為圖中的每個像素設定不同的灰度值，可以使顯示出來的直線看起來平滑一些，達到減少走樣現象。6753412圖2.2 簡單的過取樣方式2.1.2基于加權模板的過取樣另一種過取樣方式（重疊過取樣），如圖2.3，假設顯示器分辨率為m*n，其中m=4，n=3

12、，首先把顯示窗口劃分為（2m+1）*（2n+1）個像素，然后通過掃描轉換求得各子像素的顏色值，在對為于子像素中心及四周的9個子像素的顏色值進行平均，最后得到顯示像素的顏色亮度值。 由于接近像素區域中心的子像素在決定像素的顏色亮度值中發揮著重要的作用，因此過取樣算法中采用了加權平均的方法來計算顯示像素的顏色亮度值（基于加權模板的過取樣）。圖2.4示出了3*3像素分割常采用的加權模板。中心子像素的權是角子像素的4倍，是其他子像素的2倍，中心子像素的加權系數是1/4，頂部和底部及兩側子像素的加權系數是1/8，而角子像素的加權系數是1/16。000000000000121242121 圖2.3 另一種

13、過取樣方式圖 圖2.4 加權模板2.1.3過取樣算法過取樣的一種簡單方法就是在較高的分辨率下進行計算，掃描轉換求得各子像素的顏色亮度，然后對子像素的顏色亮度進行平均，得到較低分辨率下的像素顏色亮度。由于接近像素區域中心的子像素在決定像素的顏色亮度值中發揮著重要的作用，因此過取樣的另一種算法采用了加權平均的方法來計算顯示像素的顏色亮度值。不管是哪一種方法都需要在內存中建立一個比現在大幾倍的圖，便于對像素取樣，取得像素的亮度值。2.2區域取樣2.2.1簡單的區域取樣直線段掃描轉換算法均假定像素是數學上的一個點，像素顏色是由對應于像素中心的圖形中一點的顏色決定的；并且直線段是數學上抽象的直線段，它的

14、寬度是0。但實際上像素不是一個點，而是一個有限區域。屏幕上所畫的直線不是數學意義上的無寬度的理想線段，而是一個寬度至少為一個像素單位的線條。算法中所假定的條件和實際情況之間的差距是造成走樣的原因之一。為了減少走樣，必須改變直線段的模型，從而得到了簡單區域取樣的方法，這個方法的具體步驟是：（1）將直線看成具有一定寬度的狹小矩形；（2）當直線與像素相交時，求出兩者相交區域的面積；（3）根據相交區域的面積，確定像素的亮度值； 圖2.5 具有一定寬度的直線 圖2.6 灰度與面積成比例通過將每個像素亮度設置成與線條部分重疊的區域面積成正比，可以完成對直線的區域取樣。若一個像素與線條部分重疊，根據重疊區域

15、面積的大小來選擇不同的灰度。重疊面積大的像素黑一點，重疊面積小的像素白一點。這種方法將產生模糊的邊界，以次來減輕鋸齒效應。圖2.5是待顯示的直線段，圖2.6是采用簡單區域取樣方法繪制的結果。這個方法中，起關鍵作用的是直線段與像素相交區域面積的計算。那么相交區域如何計算呢？假設一條直線的斜率是m，若規定它的顯示寬度是一個像素，那么直線和像素的相交有如下三種情況，如圖所示。其中（c）的計算可轉化為正方形面積減去兩個三角形面積。接下來介紹（a）和（b）兩種情況。 （a） （b） （c）圖2.7 直線段與像素相交的三種情況在圖2.7（a）中，假設三角形x方向上的邊長為D，則y方向上的邊長為mD，從而三

16、角形的面積為.在圖2.7（b）中，假設梯形左底邊長為D，則右底邊長為D-m，從而梯形的面積為；所得到的面積介于0，1之間的實數，用它乘以像素的最大灰度值，即可得到像素實際顯示的灰度值。上面的計算十分的麻煩，為了簡化計算，可以采用下面的離散方法：(圖2.8) （1）將屏幕像素分割成n個更小的子像素；（2）計算中心點落在直線內的子像素的個數，記為k；（3）k/n為線段與像素相交區域的近似值；圖2.8 n=16，k=3，近似面積為3/16綜上所述，非加權區域采樣方法具有下面三條性質： （1）直線對一個像素亮度的貢獻與兩者相交區域的面積成正比，從而和直線與像素中心點的距離成反比。因為直線距像素中心越遠

17、，相交區域的面積越小。 （2）當直線和一個像素不相交時，它對該像素的亮度沒有影響。 （3）相同面積的相交區域對像素的亮度貢獻相同，而與這個相交區域落在像素內什么位置無關。2.2.2 加權區域取樣簡單區域取樣由于相同面積重疊區域對像素的貢獻相同，但是這樣仍然會出現走樣現象，接下來介紹的加權區域取樣對此進行了改善，使得相交區域對像素亮度的貢獻依賴于該區域與像素中心的距離。對于相同面積的相交區域，當它距離像素中心近時，它對像素亮度的貢獻大，當它距離像素中心遠時，對像素亮度貢獻小。這種方法更符合人的視覺系統對圖象信息的處理方式。 加權區域取樣的特點：一是接近理想直線的像素將被分配更多的灰度值；二是相鄰

18、兩個像素的濾波器相交，所以直線條經過該相交區域時，將對這兩個像素都分配給適當的灰度值，這樣就縮小了直線條上相鄰像素的灰度差。加權區域取樣方法的具體步驟如下：（1）求直線段與過濾器底面的重疊區域S。（2）計算 的值，其中f（x，y）是過濾函數，S是過濾器的底面，且有 =1 。（3）上面得到的值介于0和1之間，用它乘以像素的最大灰度值，即得到該像素顯示灰度值。求積分的運算量是很大的，為了方便計算，可以利用加權區域取樣的離散計算方法：（1） 將屏幕像素均勻分割成n個子像素，Siin=1，則每個子像素的面積為 ，計算每個子像素對原像素亮度的貢獻， 將fi=1保存在加權表中。（2）求出所有中心落在直線段

19、內的子像素的集合F。（3）計算所有這些子像素對原像素亮度的貢獻之和。該值乘以像素的最大灰度值即為像素的顯示灰度值。 根據上面的討論，fi是一個經驗值，因此我們可以根據經驗直接設定fi的值。例如，我們將屏幕像素劃分為n=3*3=9個子像素，加權表可取作2.2.3簡單區域取樣算法的實現 有些反走樣方法把像素當作是數學上的一個點，像素顏色是由對應于像素中心的圖形中一點的顏色決定的；而區域取樣認為像素不是一個點，而是一個有面積的區域,因此我們在區域取樣時要計算直線段與像素相交區域的面積,然后根據相交區域面積來確定像素的亮度值。由于直線與像素相交的形式有三種，那么我們如何來判斷直線與像素相交的形式呢？圖

20、2.9 區域取樣示意圖如圖2.9所示，設直線段與某像素縱列相交區域下頂點的y坐標為yl，m為該直線的斜率，y5是掃描線y+0.5。如果yl+m>y5，則說明直線和像素的相交區域是由上中下三個相鄰像素中的兩個三角形和一個四邊形組成，否則相交區域是由上下兩個相鄰像素中的兩個梯形組成。然后計算出相交區域的面積就可以得到每個像素的亮度，從而達到反走樣直線，而且反走樣的效果也十分的好。2.3 WU像素反走樣2.3.1 WU反走樣普通的Breshenham算法畫線很快,但并不是很精細.通常的整數畫線因為只能在整數坐標上繪圖,所以產生難看的鋸齒.介紹的WU像素反走樣算法就采用了非整數坐標改進它,效果也

21、十分的好。 一條經過wu反走樣的直線要比一條普通的直線要好,產生光滑的邊界,。如圖2.10所示。 圖2.10 普通直線和WU反走樣直線的對比在WU反走樣算法中，有一個重要的概念就是WU像素。WU像素具有兩個屬性：1、繪制的所有像素的亮度的總和等于原始的粒子的亮度。2、WU像素的中心亮度被定位在原始粒子的非整數位置。根據WU像素的這兩個屬性我們就可以實現WU反走樣直線。2.3.2 WU反走樣直線算法理想的反走樣算法將計算每條線覆蓋的精確區域，從區域可以得到像素的灰度值，從而達到反走樣的效果。WU反走樣直線不是這樣做，而是跨騎著直線繪制一對像素。一個主循環將沿著直線的長度畫一對像素,端點的像素對將

22、被分別計算處理，如圖2.11所示。   圖2.11 跨騎著直線的像素對 圖2.12 亮度設置跨騎直線的像素對中，兩個像素的亮度應該都是1,中心點的亮度就是理想直線的亮度。直線上的像素的亮度必須于(1-a)成比例,線下面的像素的亮度必須與(1-b)成比例。也就是說越靠近直線的像素應該越亮。沿著直線長度畫這樣的像素對,就可以得到一條WU反走樣直線。在畫完了中間端點后，我們要畫起始端點和終結端點，如圖2.12所示。可以看到直線的一個端點,用紅色的點來表示，藍色的點表示像素的中心點。你可以看到,頂點不在像素的中心點上，那么如何計算直線端點的兩個像素的正確亮度呢？方法就是把直線延長(向后或向前

23、)到最近的整數x坐標(p)，像計算直線上普通的像素對的亮度一樣計算這些像素對。然后,因為直線只是覆蓋這個像素的很小一部分xgap,直線將降低它的亮度，所以亮度應該乘上xgap。因此,當整條直線向右移動, xgap將變小,使得這個像素對平滑的變暗，按照這個方法可以畫出兩個端點。上面講的是abs(xd)>abs(yd)的情況，其實abs(xd)<abs(yd)和它類似只需要改變x和y的位置即可。WU反走樣算法思路清晰，速度也比較快，而且采用了像素的灰度處理，在反走樣兩像素寬度的直線效果上還好，因此在計算機圖形學中得到了廣泛應用。2.4 點取樣點取樣的原理很簡單，就是對被取樣的連續信號通

24、過取樣脈沖函數一個點一個點進行采樣，最后來確定該像素的顏色。但這個取樣方法不夠科學，最后顏色的設定不一定就能反映像素的真實顏色值。因為點采樣技術只考慮到單一的采樣點中心，而沒有考慮對像素灰度產生影響的多邊形區域部分，這樣的話仍然會使圖形走樣，我們可使用像素細分技術。像素細分技術的基本思想是將發生圖形混淆的像素細胞分為四個子像素，分別對子像素進行光線跟蹤。若子像素仍有圖形混淆，則繼續細分子像素直到最后確定整個像素亮度為止。這在前面介紹的方法中已經介紹到了，在此不多做介紹。2.5 像素移相在可以對屏幕網格內的子像素位置編址的光柵系統上，可使用像素移相來反走樣圖形。將電子束移動（微定位）到更接近由物

25、體幾何指定的近似位置，可光滑沿線路徑或物體邊界的階梯狀。加入這種技術的系統，單個像素位置可根據像素直徑的小數部分來移動。典型地，電子束根據像素直徑的1/4，1/2，3/4移動來畫接近于線或物體邊真實路徑的點。有些系統也允許對單個像素的尺寸進行調整。三、反走樣算法的改進3.1 多段直線反走樣算法3.1.1 概述直線是最基本的圖形元素，是構成復雜圖形的基礎，人們在設計和改進直線生成算法方面已經進行了較深的研究。其中Bresenham算法是最著名的，它在繪制線段的過程當中只涉及整數的加法和符號的判斷，是一種簡單、高效的算法。但不管是Bresenham算法還是別的直線生成算法都會使直線產生鋸齒狀邊界。

26、在第二章已經介紹并實現了幾種反走樣算法,但是它們都需要對直線上的每一個像素進行反走樣處理，我們研究的多段反走樣直線算法利用直線段像素可能存在的多段相似性，大大提高反走樣速度，節省了反走樣時間。3.1.2算法的設計思想設平面直線l的方程為y=kx+b，根據斜率為k的取值范圍，可將平面直線分為5類： （1）0k1；（2）1k；（3）-k-1； （4）-1k0；（5）k=0，|k|=1，|k|=；根據數字圖形的特點，對第（5）類直線不必反走樣掃描轉換就可簡單地生成直線。而對第（2），（3），（4）類直線，只要在反走樣掃描轉換時通過簡單地交換x和y，或改變其增量的符號就可變換到第（1）類的反走樣直線。

27、設x0，y0，xn，yn為整數，不妨設x0xn，y0yn，對于以（x0，y0）和（xn，yn）為端點的直線段l，記dy=yn- y0，dx= xn-x0，則斜率k=，因為0k0，所以0dydx。記m為dy，dx的最大公約數，即m=gdc（dx，dy），則存在互質的正整數p和q，使得 k=，0qp。例如，如圖3.1所示，（x0，y0）=（0，0），（xn，yn）=（15，12），m=gdc（15，12）=3，p=5，q=4。設計思想1反走樣直線段l掃描轉換生成的像素序列（xi，yi）|i=0，1，2，n可被劃分成具有相同形狀的m個片段：l1，l2，lm加終點像素，每個片段含p個像素，每個片段的第

28、一個像素精確地落在l上，且在整個像素序列中有且僅有m+1個像素精確地落在l上（如圖3.1所示）。圖3.1 分段掃描示意圖設計思想2若反走樣直線段l掃描轉換生成的像素序列為（xi，yi）|i=0，1，2，n,則該序列的y坐標值關于線段l的中點對稱,即yn-i=yn-yi+y0(i=0,1,2,，n/2)。 3.1.3 計算效率分析本算法需要通過計算獲取的掃描轉換像素個數最多為dx的一半：若m>1，則僅需計算dx/m個像素后就會出現dk=0；若計算達到dx的一半時仍未遇到精確落在直線上的像素，則由性質1可知m=1，從而利用性質2進行對稱復制。這樣的話比普通的反走樣直線算法明顯具有優勢,速度提

29、高了很多。3.2圓反走樣算法3.2.1算法思想圓反走樣算法只需考慮圓心位于坐標原點的圓弧反走樣，對于圓心為任意點的圓弧，可以先將其平移到原點，然后反走樣，再平移到原來的位置上。圓心位于原點的圓有四條對稱軸x=0，y=0，x=y，x=-y，如圖3.2所示。因此只要知道圓弧上的一點（x，y）就可以得到它的七個對稱點，也稱為圓的八對稱性。因此我們只要反走樣八分之一圓弧其余的都可以對稱得到反走樣。圓的每一個八分之一圓弧都是由一段段的水平線段組成，因此圓弧反走樣的問題就是反走樣一段段小的水平線段的問題。 圖3.2圓的八對稱性3.2.2算法算法首先分析圓的特殊性，也就是圓具有八對稱性，在畫圓的同時進行反走

30、樣。總之，算法充分利用圓的八對稱性，以加權過取樣算法基礎下圖3.3是圓反走樣算法的部分效果實現圖：圖3.3圓反走樣效果3.3 位圖反走樣3.3.1實現原理對位圖進行反走樣，原理很簡單，就是將原圖放大三倍以后進行像素點間的平均操作，也就是目標像素點周圍的8個像素點加上自己這個像素點共9個像素點的紅色分量的總和，然后取平均值，在賦給目標像素中的紅色分量。同理，綠色分量和藍色分量也類似處理。在這里用了兩種方法可以實現此操作，一個就是直接用像素點進行操作，另一個就是Scanline方法。雖然這兩種方法的實現原理是一樣的，但是在速度上改進的Scanline方法明顯要比直接用像素點進行操作的方法快。3.3.2實現方法1）利用Pixels方法的實現技術這是直接通過像素點的操作，對像素點逐個進行處理，分別得到紅色、綠色、藍色分量來反走樣圖形。這個方法雖然實現十分簡單，但是處理的速度十分的慢，需要相當長的一段時間。2）利用Scnaline方法的的實現技術 用Scnaline方法大大提高了速度，一般是直接像素點操作的50倍左右。3.2.3效果分析Pixels方法是采用直接對每個像素點進行操作，在反走樣的過程中逐個像素點反走樣，它實現的時間是2003毫秒。而采用Scanline方法是逐行對像素進行操作，它實現的時間是30毫秒，