彩色图象的二维变形(1)(2)
2014-12-15 01:05
导读：@@T5S13201.GIF;图2@@ 上述的双线性插值过程可以通过增量计算方法提高速度。其中，在水平方向上，位于多边形内的各区段上的各像素的反变换坐标可以沿扫
@@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]。
（科教作文网http://zw.ΝsΕac.cOM编辑） 四、算法细节
下面将要给出的彩色图像的二维变形算法以多边形区域扫描转化的扫描线算法为框架，且使用相仿的数据结构，对目的多边形区域高效地进行逐点扫描，同时实现前面讨论的各种技术。
首先给出的是用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; /*顶点的反变换坐标*/
