彩色圖象管理

前言：本站為你精心整理了彩色圖象管理范文，希望能為你的創作提供參考價值，我們的客服老師可以幫助你提供個性化的參考范文，歡迎咨詢。

摘要該文討論了彩色圖像的變形扭曲技術，并針對二維變形給出了一個速度、精度均令人滿意的算法。

一、引言

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

二、變換原理

本文所要討論的二維變形問題可以形式化說明如下:圖像定義在矩形區域ABCD之上，源多邊形區域P=p1p2…pnp1(Pi為頂點，i=1，2，…n)完全包含在ABCD內；變形就是通過變換f，將P上的圖像變換到目的多邊形區域Q=Q1Q2…QnQ1(Qi為頂點，i=1，2，…n)，其中，P與Q中的各頂點一一對應，即有:Qi=f(Pi)(i=1,2…n)。圖1是變形的一個簡單例子:圖中的源多邊形區域是矩形區域ABCD，目的多邊形為任意四邊形EFGH，陰影部分在變換前后的變化清楚地說明了變形的效果。

@@T5S13200.GIF;圖1@@

那么，變換應該如何進行呢?

一種直接的思路是顯式地求出變換f的表達式。而f的實施又分兩種方法；其一為正向變換法，即用f將P內的任一像素點變換到Q內，取原像素值加以顯示。由于P與Q所包含像素點的數目一般不相同，甚至相差很大，造成Q中的像素點或者未被賦值，形成令人討厭的空洞，或者被多次賦值，浪費了時間，總的效果不理想；其二利用f的反變換f-1，將Q內的每一像素點反變換至P內的對應點，一般此點具有實數坐標，則可以通過插值，確定其像素值，這樣，結果圖像中的每一像素點均被賦值唯一的一次，既提高了精度，又可以避免不必要的賦值，使用效果較好。

上述顯示求變換(或反變換)的表達式的思路，比較精確，但是這往往牽涉到復雜的多元方程求解問題，并非輕易可以完成。本文所給出的另外一條思路是:既然P與Q中各頂點一一對應，組成變換對，即源多邊形P中的任一頂點Pi(i=1,2…n)經過變換f，得到目的多邊形Q中的頂點Qi(i=1,2…n)，則Qi的反變換點也必為Pi。這樣，對Q內(包括邊界)的各像素點A，可以利用各頂點的反變換點的坐標值通過雙線性插值技術近似求出其反變換點B；再用點B的坐標值在源圖像中進行插值，最終求得結果像素值，用于顯示A。

第二種方法在保留一定精度的前提下，避免了變換表達式的顯式求解，實現簡便。本文基于此思想，設計了一個快速變形算法；另外，算法中還借鑒了多邊形區域掃描轉換的掃描線算法的思路，以實現對Q內各像素點的高效掃描。以下，本文首先介紹了插值技術及增量計算技術，然后將給出二維變形算法的詳細步驟。

三、插值技術

已知目的多邊形Q各頂點Qi(i=1,2…n)的變換坐標值，如何求出Q內任一像素的反變換坐標呢?雙線性插值法是一種簡單快速的近似方法。具體做法是:先用多邊形頂點Qi(i=1,2…n)的反變換坐標線性插值出當前掃描線與多邊形各邊的交點的反變換坐標，然后再用交點的反變換坐標線性插值出掃描線位于多邊形內的區段上每一像素處的反變換坐標值用于以后的計算。逐條掃描線處理完畢后，Q內每一像素點的反變換坐標值也就均求出來了。如圖2中所示，掃描線Y(縱坐標=Y)與多邊形相交于點A和B兩點，D則是位于掃描線上位于多邊形內的區段AB上的任一點。已知多邊形的3個頂點Qi(i=1,2，3)的反變換坐標為(RXi,RYi)；

又令A、B及D各點的反變換坐標分別是(RXa,RYa),(RXb,RYb)和(RXd,RYd)。則RXp可按以下公式求出:

RXa=uRX1+(1-u)RX2式1

RXb=vRX1+(1-v)RX3式2

RXd=tRXa+(1-t)RXb式3

其中，u=|AQ2|/|Q1Q2|，v=|BQ3|/|Q1Q3|，t=|DB|/|AB|，

稱為插值參數。

RYd的值亦可完全類似地求出，甚至不必改變插值參數的計算。(Rxd,Ryd)即是D點在原圖像中對應點的坐標近似值。

@@T5S13201.GIF;圖2@@

上述的雙線性插值過程可以通過增量計算方法提高速度。其中，在水平方向上，位于多邊形內的各區段上的各像素的反變換坐標可以沿掃描線從左至右遞增計算。仍以反變換的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+△Rxx

由于△Rxx在AB區段仍為常數，故AB區段上各像素點的反變換X坐標均可由A點的Rxa依次遞增求得，而反變換Y坐標的遞增求法亦是相同。這樣，AB區段上各像素點的反變換坐標值的計算簡化為兩次加法，時間的節省是驚人的。事實上，在垂直方向，每條邊也可在相鄰掃描線間遞增計算其與掃描線交點的反變換坐標。如圖2中的Q1Q2邊，其與相鄰的兩條掃描線Y與Y-1分別交于A點和E點。則兩點的插值參數之差△u=|AE|/|Q1Q2|，而Q1Q2邊與掃描線交角固定為θ，且A和E兩點的Y坐標之差為1，則有:|AE|=1/Sinθ，對于Q1Q2邊而言是常量，因此△u對此邊也是常量，于是推得兩點反變換X坐標關系如下:

Rxa=Rxe+(Rx1-Rx2)△u=Rxe+△Rxy

顯然，△Rxy沿Q1Q2邊亦是常數，故而可知，相鄰掃描線與各邊交點的反變換坐標也只要兩次浮點加法的計算量。這樣，區域內每一像素點的反變換均可通過增量計算高效地完成，這大大提高了整個變形算法的速度。

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

四、算法細節

下面將要給出的彩色圖像的二維變形算法以多邊形區域掃描轉化的掃描線算法為框架，且使用相仿的數據結構，對目的多邊形區域高效地進行逐點掃描，同時實現前面討論的各種技術。

首先給出的是用C語言描述的數據結構:

structEdge{

floatx;/*在邊的分類表ET中表示邊的下端點的x坐標；在邊的活化鏈

表AEL中則表示邊與掃描線的交點的x坐標；*/

floatdx;/*邊的斜率的倒數；即沿掃描線間方向X的增量值*/

intYmax;/*邊的上端點的y坐標*/

floatRx;/*在ET中表示邊的下端點*/

floatRy;/*的反變換坐標；在AEL中則表示邊與掃描線交點的反變換坐標*

/

表floatdRx;/*沿掃描線間方向，反變*/

floatdRy;/*換坐標(Rx,Ry)的增量值*/

structEdge*next;/*指向下一條邊的指針*/

};/*多邊形的邊的信息*/

structEdge*ET[YResolution];

/*邊的分類表，按邊的下端點的縱坐標Y對非水平邊進行分類的指針數組。

下端點的Y值等于i的邊歸入第i類，同一類中，各邊按X值及△X的值遞增順序排列；YResolution為掃描線數目*/

structEdye*AEL;

表/*邊的活化鏈表，由與當前掃描線相交的所有多邊形的邊組成，記錄了多邊形邊沿當前掃描線的交點序列。*/

structPolygon{

intnpts;/*多邊形頂點數*/

structPoint*Pts;

/*多邊形的頂點序列*/

};/*多邊形信息*/

structPoint{

intX;

intY;/*頂點坐標*/

floatRx;

floatRy;/*頂點的反變換坐標*/

};/*多邊形各頂點的信息*/

注意以上注釋中邊的下端點指縱坐標值較小的一端，另一端即為上端點。

以下則為算法的詳細步驟:

1.數據準備

對于每一條非水平邊QiQi+1，設Qi與Qi+1的坐標分別為(Xi,Yi)

及(X

i+1,Yi+1)；其反變換坐標為(Rxi,Ryi)及(RXi+1,RYi+1)。

則按以下各式對此邊的信息結構各域進行填寫:

X=Xi,Yi＜Yi+1

Xi+1,Yi＞Yi+1

RX=RXi,Yi＜Yi+1

RXi+1,Yi＞Yi+1

RY=RYi,Yi＜Yi+1

RYi+1,Yi＞Yi+1

dx=(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)

然后將其插入鏈表ET[min(yi，yi+1)]中?；罨叡鞟EL置空。

當前掃描線縱坐標y取為0，即最小序號。

2.掃描轉換

反復作以下各步，直到y等于YResolution

(1)若ET[y]非空，則將其內所有邊插入AEL。

(2)若AEL非空，則將其按X及dx的值從小到大排列各邊，接(3)；否則轉

(3)將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則對于每個滿足xLeft≤xX≤xRight的坐標為(xx,y)的像素，其反變換坐標(Rxy,Ryx)可按下式增量計算:

Rxx=Rxx+dRxx

Ryx=Ryx+dRyy

用(Rxx,Ryx)在數組Image之中插值，(參見文獻[1])，按所得顏色值顯示該像素。然后邊x=x+1，計算下一像素。

(4)將AEL中滿足y=Ymax的邊刪去，然后按下式調整AEL中各邊的信息。

X=X+dx

Rx=Ry+dRx

Ry=Ry+dRy

(5)y=y+1,重復下一點。

五、討論

上述算法針對彩色圖像的二維變形問題，給出了一個簡單快速的實現方案。至于三維變形，由于一般會牽涉到隱藏面消除等問題，比較復雜。但在一些情況下，可以避開消隱問題，如目的曲面形狀比較簡單，投影到屏幕后，各部分均不發生重疊，也就沒有必要使用消隱技術，直接投影就可以了。這時就仍然可以利用本文介紹的二維變形技術，進行處理。方法是:

將曲面用許多小平面多邊形進行逼近，再將各個小多邊形投影到屏幕上，形成二維多邊形。

在確定了小多邊形到原圖像各部分的對應關系之后，三維問題就轉化成了二維問題，速度比較快，也能達到一定的效果。若掌握了消隱技術之后，則可以處理任意的曲面變形了，思路同上。

參考文獻

[1]向輝壽標“真實感圖像的顏色插值及其應用”，計算機世界月刊，1992年10月