彩色图象的二维变形
摘 要 该文讨论了彩色图像的变形扭曲技术，并针对二维变形给出了一个速度、精度均令人满意的算法。
一、引言
在图像处理的应用中，一般图像所覆盖区域边界是规则的矩形。为获得某种特殊效果，常常需要将图像变换到具有任意不规则边界的二维区域或映像到三维空间曲面，简单地说，这就是所谓的图像变形技术。本文重点讨论了其中的任意二维多边形区域的变形问题，并针对彩色图像给出一个切实可行的算法。而三维情况下，则属于计算机图形学中的纹理贴面范围，一般均会牵涉到立体图形消隐、明暗处理等技术，比较复杂，本文未作深入探讨。
二、变换原理
本文所要讨论的二维变形问题可以形式化说明如下:图像定义在矩形区域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边亦是常数，故而可知，相邻扫描线与各边交点的反变换坐标也只要两次 《彩色图象的二维变形》
本文链接地址：http://www.oyaya.net/fanwen/view/171915.html
一、引言
在图像处理的应用中，一般图像所覆盖区域边界是规则的矩形。为获得某种特殊效果，常常需要将图像变换到具有任意不规则边界的二维区域或映像到三维空间曲面，简单地说，这就是所谓的图像变形技术。本文重点讨论了其中的任意二维多边形区域的变形问题，并针对彩色图像给出一个切实可行的算法。而三维情况下，则属于计算机图形学中的纹理贴面范围，一般均会牵涉到立体图形消隐、明暗处理等技术，比较复杂，本文未作深入探讨。
二、变换原理
本文所要讨论的二维变形问题可以形式化说明如下:图像定义在矩形区域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边亦是常数，故而可知，相邻扫描线与各边交点的反变换坐标也只要两次 《彩色图象的二维变形》
★读了本文的人也读了：