彩色图象的二维变形
彩色图象的二维变形 彩色图象的二维变形 彩色图象的二维变形 摘 要 该文讨论了彩色图像的变形扭曲技术，并针对二维变形给出了一个速度、精度均令人满意的算法。
一、引言
在图像处理的应用中，一般图像所覆盖区域边界是规则的矩形。为获得某种特殊效果，常常需要将图像变换到具有任意不规则边界的二维区域或映像到三维空间曲面，简单地说，这就是所谓的图像变形技术。本文重点讨论了其中的任意二维多边形区域的变形问题，并针对彩色图像给出一个切实可行的算法。而三维情况下，则属于计算机图形学中的纹理贴面范围，一般均会牵涉到立体图形消隐、明暗处理等技术，比较复杂，本文未作深入探讨。
二、变换原理@@T5S13200.GIF;图1@@
那么，变换应该如何进行呢?
一种直接的思路是显式地求出变换f的表达式。而f的实施又分两种方法；其一为正向变换法，即用f将P内的任一像素点变换到Q内，取原像素值加以显示。由于P与Q所包含像素点的数目一般不相同，甚至相差很大，造成Q中的像素点或者未被赋值，形成令人讨厌的空洞，或者被多次赋值，浪费了时间，总的效果不理想；其二利用f的反变换f-1，将Q内的每一像素点反变换至P内的对应点，一般此点具有实数坐标，则可以通过插值，确定其像素值，这样，结果图像中的每一像素点均被赋值唯一的一次，既提高了精度，又可以避免不必要的赋值，使用效果较好。第二种方法在保留一定精度的前提下，避免了变换表达式的显式求解，实现简便。本文基于此思想，设计了一个快速变形算法；另外，算法中还借鉴了多边形区域扫描转换的扫描线算法的思路，以实现对Q内各像素点的高效扫描。以下，本文首先介绍了插值技术及增量计算技术，然后将给出二维变形算法的详细步骤。
三、插值技术又令A、B及D各点的反变换坐标分别是(RXa,RYa),(RXb,RYb)和(RXd,RYd)。则RXp可按以下公式求出:RXb=vRX1+(1-v)RX3式2
RXd=tRXa+(1-t)RXb 式3称为插值参数。
RYd的值亦可完全类似地求出，甚至不必改变插值参数的计算。(Rxd,Ryd)即是D点在原图像中对应点的坐标近似值。上述的双线性插值过程可以通过增量计算方法提高速度。其中，在水平方向上，位于多边形内的各区段上的各像素的反变换坐标可以沿扫描线从左至右递增计算。仍以反变换的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-Rx
2)△u=Rxe+△Rxy另外，前面提到，经过反变换后的点一般具有实数坐标，无法直接在原图像中获得颜色值。但我们知道，一幅所谓数字图像，其实质是对连续图像在整数坐标网格点上的离散采样，因而可以用插值的方法，得到区域内具有任意坐标的点的颜色值。插值即是对任意坐标点的颜色值，用其周围的若干像素(具有整值坐标值，颜色值确定)的颜色值按一定插值公式近似计算。一般有最近邻点法、双线性插值法及3次样条函数法等插值方法，出于精度与速度的折衷要求，选用双线性插值方 法对绝大多数的应用场合是适宜的。需特别指出的是，应该对颜色的3原色分量分别进行插值，而不要直接使用读像素点得到的颜色索引号。详细讨论见文献[1]。
四、算法细节
下面将要给出的彩色图像的二维变形算法以多边形区域扫描转化的扫描线算法为框架，且使用相仿的数据结构，对目的多边形区域高效地进行逐点扫描，同时实现前面讨论的各种技术。
首先给出的是用C语言描述的数据结构:
struct Edge {
float x; /*在边的分类表ET中表示边的下端点的x坐标；在边的活化链
表AEL中则表示边与扫描线的交点的x坐标；*/
float dx; /*边的斜率的倒数；即沿扫描线间方向X的增量值*/
int Ymax; /*边的上端点的y坐标*/
float Rx; /*在ET中表示边的下端点*/
float Ry; /*的反变换坐标；在AEL中则表示边与扫描线交点的反变换坐标*
/
表float dRx; /*沿扫描线间方向，反变*/
float dRy; /*换坐标(Rx,Ry)的增量值*/
struct Edge *next;/*指向下一条边的指针*/
}; /*多边形的边的信息*/
struct Edge *ET[YResolution];
/*边的分类表，按边的下端点的纵坐标Y对非水平边进行分类的指针数组。
下端点的Y值等于i的边归入第i类，同一类中，各边按X值及△X的值递增顺序排列；YResolution为扫描线数目*/
struct Edye *AEL;
表 /*边的活化链表，由与当前扫描线相交的所有多边形的边组成，记录了多边形边沿当前扫描线的交点序列。*/
struct Polygon {
int npts; /*多边形顶点数*/
struct Point *Pts;
/*多边形的顶点序列*/
}; /*多边形信息*/
struct Point {
int X;
int Y; /*顶点坐标*/
float Rx;
float Ry; /*顶点的反变换坐标*/
}; /*多边形各顶点的信息*/
注意以上注释中边的下端点指纵坐标值较小的一端，另一端即为上端点。
以下则为算法的详细步骤:
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)]中。活化边表AEL置空。
当前扫描线纵坐标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月