1、彩色圖象的二維變形彩色圖象的二維變形 彩色圖象的二維變形 彩色圖象的二維變形 摘 要 該文討論了彩色圖像的變形扭曲技術，并針對二維變形給出了一個速度、精度均令人滿意的算法。一、引言在圖像處理的應用中，一般圖像所覆蓋區域邊界是規那么的矩形。為獲得某種特殊效果，常常需要將圖像變換到具有任意不規那么邊界的二維區域或映像到三維空間曲面，簡單地說，這就是所謂的圖像變形技術。本文重點討論了其中的任意二維多邊形區域的變形問題，并針對彩色圖像給出一個實在可行的算法。而三維情況下，那么屬于計算機圖形學中的紋理貼面范圍，一般均會牽涉到立體圖形消隱、明暗處理等技術，比較復雜，本文未作深化討論。二、變換原理T5S13

2、200.GIF;圖1那么，變換應該如何進展呢?一種直接的思路是顯式地求出變換f的表達式。而f的施行又分兩種方法；其一為正向變換法，即用f將P內的任一像素點變換到Q內，取原像素值加以顯示。由于P與Q所包含像素點的數目一般不一樣，甚至相差很大，造成Q中的像素點或者未被賦值，形成令人討厭的空洞，或者被屢次賦值，浪費了時間，總的效果不理想；其二利用f的反變換f-1，將Q內的每一像素點反變換至P內的對應點，一般此點具有實數坐標，那么可以通過插值，確定其像素值，這樣，結果圖像中的每一像素點均被賦值唯一的一次，既進步了精度，又可以防止不必要的賦值，使用效果較好。第二種方法在保存一定精度的前提下，防止了變換表

3、達式的顯式求解，實現簡便。本文基于此思想，設計了一個快速變形算法；另外，算法中還借鑒了多邊形區域掃描轉換的掃描線算法的思路，以實現對Q內各像素點的高效掃描。以下，本文首先介紹了插值技術及增量計算技術，然后將給出二維變形算法的詳細步驟。三、插值技術又令A、B及D各點的反變換坐標分別是(RXa,RYa),(RXb,RYb)和(RXd,RYd)。那么RXp可按以下公式求出:RXb=vRX1+(1-v)RX3式2RXd=tRXa+(1-t)RXb 式3稱為插值參數。RYd的值亦可完全類似地求出，甚至不必改變插值參數的計算。(Rxd,Ryd)即是D點在原圖像中對應點的坐標近似值。上述的雙線性插值過程可以

4、通過增量計算方法進步速度。其中，在程度方向上，位于多邊形內的各區段上的各像素的反變換坐標可以沿掃描線從左至右遞增計算。仍以反變換的X坐標為例。如圖2所示，在掃描線Y上，C與D是相鄰兩像素點，對C點，插值參數tc=|CB|/|AB|，對D點，td=|DB|/|AB|，那么插值參數之差t=|CD|/|AB|，由于C與D相鄰，且在同一掃描線上，|CD|=1，即t=1/|AB|，在AB區段上為常數。根據式1式3，不難推得D點的反變換X坐標Rxd與C點的反變換X坐標Rxc之間的關系如下:Rxd=Rxc+(Rxa-Rxb)·t=Rxc+RxxRxa=Rxe+(Rx1-Rx2)u=Rxe+Rxy另

5、外，前面提到，經過反變換后的點一般具有實數坐標，無法直接在原圖像中獲得顏色值。但我們知道，一幅所謂數字圖像，其本質是對連續圖像在整數坐標網格點上的離散采樣，因此可以用插值的方法，得到區域內具有任意坐標的點的顏色值。插值即是對任意坐標點的顏色值，用其周圍的假設干像素(具有整值坐標值，顏色值確定)的顏色值按一定插值公式近似計算。一般有最近鄰點法、雙線性插值法及3次樣條函數法等插值方法，出于精度與速度的折衷要求，選用雙線性插值方 法對絕大多數的應用場合是適宜的。需特別指出的是，應該對顏色的3原色分量分別進展插值，而不要直接使用讀像素點得到的顏色索引號。詳細討論見文獻1。四、算法細節下面將要給出的彩色

6、圖像的二維變形算法以多邊形區域掃描轉化的掃描線算法為框架，且使用相仿的數據構造，對目的多邊形區域高效地進展逐點掃描，同時實現前面討論的各種技術。首先給出的是用C語言描繪的數據構造:struct Edge float x; /*在邊的分類表ET中表示邊的下端點的x坐標；在邊的活化鏈表AEL中那么表示邊與掃描線的交點的x坐標；*/float dx; /*邊的斜率的倒數；即沿掃描線間方向X的增量值*/int Ymax; /*邊的上端點的y坐標*/float Rx; /*在ET中表示邊的下端點*/float Ry; /*的反變換坐標；在AEL中那么表示邊與掃描線交點的反變換坐標*/表float dRx

7、; /*沿掃描線間方向，反變*/float dRy; /*換坐標(Rx,Ry)的增量值*/struct Edge *next;/*指向下一條邊的指針*/; /*多邊形的邊的信息*/struct Edge *ETYResolution;/*邊的分類表，按邊的下端點的縱坐標Y對非程度邊進展分類的指針數組。下端點的Y值等于i的邊歸入第i類，同一類中，各邊按X值及X的值遞增順序排列；YResolution為掃描線數目*/struct Edye *AEL;表 /*邊的活化鏈表，由與當前掃描線相交的所有多邊形的邊組成，記錄了多邊形邊沿當前掃描線的交點序列。*/struct Polygon int npts

8、; /*多邊形頂點數*/struct Point *Pts;/*多邊形的頂點序列*/; /*多邊形信息*/struct Point int X;int Y; /*頂點坐標*/float Rx;float Ry; /*頂點的反變換坐標*/; /*多邊形各頂點的信息*/注意以上注釋中邊的下端點指縱坐標值較小的一端，另一端即為上端點。以下那么為算法的詳細步驟:1.數據準備對于每一條非程度邊QiQi+1，設Qi與Qi+1的坐標分別為(Xi,Yi)及(Xi+1,Yi+1)；其反變換坐標為(Rxi,Ryi)及(RXi+1,RYi+1)。那么按以下各式對此邊的信息構造各域進展填寫:X=Xi,YiYi+1Xi

9、+1,YiYi+1RX=RXi,YiYi+1RXi+1,YiYi+1RY=RYi,YiYi+1RYi+1,YiYi+1dx=(xi-xi+1)/(yi-yi+1)Ymax=max(yi，yi+1)dRx=(Rxi-Rxi+1)/(yi-yi+1)dRy=(Ryi-Ryi+1)/(yi-yi+1)然后將其插入鏈表ETmin(yi，yi+1)中。活化邊表AEL置空。當前掃描線縱坐標y取為0，即最小序號。2.掃描轉換反復作以下各步，直到y等于YResolution(1)假設ETy非空，那么將其內所有邊插入AEL。(2)假設AEL非空，那么將其按X及dx的值從小到大排列各邊，接(3)；否那么轉(3)將

10、AEL內各邊按排列順序兩兩依次配對。那么沿當前掃描線Y組成假設干程度區間xLeft,xRight，其左右端點的反變換坐標分別為:(lRx,lRy)，(rRx,rRy)。那么對于每一個這樣的區間作以下各步:dRxx=(lRx-rRx)/(xleft-xRight)dRyx=(lRy-rRy)/(xleft-xRight)又設原圖像已讀入二維數組Image之中。令XX=xleft, Rxy=lRx, Ryx=lRy那么對于每個滿足xLeftxXxRight的坐標為(xx,y)的像素，其反變換坐標(Rxy,Ryx)可按下式增量計算:Rxx=Rxx+dRxxRyx=Ryx+dRyy用(Rxx,Ryx)

11、在數組Image之中插值，(參見文獻1)，按所得顏色值顯示該像素。然后邊x=x+1，計算下一像素。(4)將AEL中滿足y=Ymax的邊刪去，然后按下式調整AEL中各邊的信息。X=X+dxRx=Ry+dRxRy=Ry+dRy(5)y=y+1,重復下一點。五、討論上述算法針對彩色圖像的二維變形問題，給出了一個簡單快速的實現方案。至于三維變形，由于一般會牽涉到隱藏面消除等問題，比較復雜。但在一些情況下，可以避開消隱問題，如目的曲面形狀比較簡單，投影到屏幕后，各部分均不發生重疊，也就沒有必要使用消隱技術，直接投影就可以了。這時就仍然可以利用本文介紹的二維變形技術，進展處理。方法是:將曲面用許多小平面多邊形進展逼近，再將各個小多邊形投影到屏幕上，