In this paper, the deformation technology of color images is discussed, and a two-dimensional deformation algorithm with satisfactory speed and accuracy is given.

I. Introduction

In the application of image processing, the boundary of the area covered by general images is a regular rectangle. In order to obtain a special effect, it is often necessary to transform an image into a two-dimensional region with arbitrary irregular boundaries or map it into a three-dimensional space surface. In short, this is the so-called image morphing technology. This paper focuses on the deformation of arbitrary two-dimensional polygon region, and gives a feasible color image deformation algorithm. In the case of three-dimensional, it belongs to the scope of texture veneer in computer graphics, and generally involves three-dimensional graphics blanking, shading and other technologies, which are more complicated, and this paper has not made in-depth discussion.

Second, the principle of transformation

The two-dimensional deformation problem discussed in this paper can be formalized as follows: the image is defined on the rectangular area ABCD, and the source polygon area P=p 1p2…pnp 1(Pi is the vertex, I = 1, 2, …n) is completely contained in the ABCD; The transformation is to transform the image on P into the target polygon area Q=Q 1Q2…QnQ 1(Qi is the vertex, i= 1, 2, …n) through transformation F, where P corresponds to each vertex in Q one by one, that is, QI = F (PI) (I = 65438). Figure 1 is a simple example of deformation: the source polygon area in the figure is rectangular area ABCD, and the target polygon is arbitrary quadrilateral EFGH. The change of shadow before and after transformation clearly shows the effect of deformation.

@@T5S 13200。 GIF map 1@

So, how should the transformation be carried out?

A direct way of thinking is to find the expression of transformation f explicitly, and there are two ways to realize f; One is the forward transformation method, that is, any pixel in P is transformed into Q by F, and the original pixel value is displayed. Because the number of pixels contained in P and Q is generally different, or even quite different, the pixels in Q are either not assigned, forming an annoying hole, or assigned for many times, which wastes time and the overall effect is not ideal. Secondly, every pixel in q is inversely transformed to the corresponding point in p by using the inverse transformation f- 1. Generally, this point has real coordinates, so its pixel value can be determined by interpolation. In this way, each pixel in the resulting image is given a unique value, which not only improves the accuracy, but also avoids unnecessary assignment, and the use effect is good.

The above idea of showing transformation (or inverse transformation) expression is more accurate, but it often involves the solution of complex multivariate equations, which is not easy to complete. Another idea given in this paper is that because each vertex in P and Q corresponds to each other to form a transformation pair, that is, any vertex Pi(i= 1, 2…n) in the source polygon P is transformed into a vertex Qi(i= 1, 2…n) in the destination polygon Q, then the inverse transformation point of Qi must also be Pi. In this way, for each pixel point A (including the boundary) in Q, the inverse transformation point B can be approximately obtained by bilinear interpolation technology by using the coordinate values of the inverse transformation point of each vertex; Then the coordinate values of point B are used to interpolate in the source image, and finally the pixel value of display A is obtained. ..

The second method avoids the explicit solution of the transformation expression on the premise of retaining a certain accuracy, and is simple to implement. Based on this idea, this paper designs a fast deformation algorithm. In addition, the algorithm also draws lessons from the idea of scanning the polygon area by scanning line algorithm, and realizes efficient scanning of each pixel in Q. In the following, this paper first introduces interpolation technology and incremental calculation technology, and then gives the detailed steps of two-dimensional deformation algorithm.

Third, interpolation technology.

Given the transformation coordinate values of each vertex Qi(i= 1, 2…n) of the destination polygon Q, how to find the inverse transformation coordinate of any pixel in Q? Bilinear interpolation is a simple and fast approximation method. Specifically, the inverse transformation coordinates of the intersection of the current scanning line and each side of the polygon are linearly interpolated with the inverse transformation coordinates of the polygon vertex Qi(i= 1, 2…n), and then the inverse transformation coordinates of each pixel on the section where the scanning line is located in the polygon are linearly interpolated for later calculation. After the scan lines are processed one by one, the inverse transformation coordinate values of each pixel in Q are also obtained. As shown in fig. 2, the scanning line y (ordinate =Y) intersects with the polygon at two points A and B, and D is any point on the scanning line in the AB section of the polygon. It is known that the inverse transformation coordinates of three vertices qi (I = 1, 2, 3) of a polygon are (RXI, ryi);

Let the inverse transformation coordinates of a, b and d be (RXa, RYa), (RXb, RYb) and (RXd, RYd) respectively. RXp can be calculated by the following formula:

Rxa = urx 1+(1-u) rx2 formula1.

Rxb = vrx1+(1-v) rx3 formula 2

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

Where u=|AQ2|/|Q 1Q2|, v=|BQ3|/|Q 1Q3|, t=|DB|/|AB|,

Called interpolation parameters.

The value of RYd can also be obtained completely similarly, even if the calculation of interpolation parameters is not changed. (Rxd, Ryd) is the approximate coordinate of the point corresponding to point D in the original image.

@@T5S 1320 1。 GIF figure 2@

The above bilinear interpolation process can improve the speed through incremental calculation. In the horizontal direction, the inverse transformation coordinates of each pixel on each section in the polygon can be calculated incrementally from left to right along the scanning line. Or take the x coordinate after inverse transformation as an example. As shown in fig. 2, on the scanning line y, c and d are two adjacent pixel points. For point C, the interpolation parameter tc=|CB|/|AB|, and for point D, td=|DB|/|AB|, then the difference of interpolation parameters △t=|CD|/|AB|, because C and D are adjacent and on the same scanning line, |CD. According to equation 1 ~ equation 3, it is not difficult to deduce the relationship between the inverse transformation x coordinate Rxd of point d and the inverse transformation x coordinate Rxc of point c as follows:

Rxd=Rxc+(Rxa-Rxb) △t=Rxc+△Rxx

Because △Rxx is still a constant on AB section, the inverse transformation X coordinate of each pixel point on AB section can be obtained by sequentially increasing Rxa of point A, and the incremental solution of inverse transformation Y coordinate is the same. In this way, the calculation of inverse transformation coordinate values of each pixel on AB section is simplified to two additions, which saves amazing time. In fact, in the vertical direction, each edge can also calculate the inverse transformation coordinates of its intersection with the scanning lines incrementally between adjacent scanning lines. As shown in fig. 2, the edge Q 1Q2 intersects with two adjacent scanning lines Y and Y- 1 at points A and E, respectively. Then the difference of interpolation parameters between two points △u=|AE|/|Q 1Q2|, the included angle between the side of Q 1Q2 and the scanning line is fixed as θ, and the difference of y coordinates of a and e is 1, then |AE|= 1/Sinθ is Q65438.

rxa = Rxe+(rx 1-Rx2)△u = Rxe+△Rxy

Obviously, the edge of △Rxy along Q 1Q2 is also a constant, so it can be seen that the inverse transformation coordinates of the intersection of adjacent scanning lines and each edge only need two floating-point additions. In this way, the inverse transformation of each pixel in the region can be completed efficiently by incremental calculation, which greatly improves the speed of the whole deformation algorithm.

In addition, as mentioned above, the points after inverse transformation generally have real coordinates, so the color values cannot be obtained directly in the original image. However, we know that the essence of the so-called digital image is to carry out discrete sampling on continuous images at grid points with integer coordinates, so the color values of points with arbitrary coordinates in the region can be obtained by interpolation. Interpolation refers to the approximate calculation of the color value of any coordinate point by using the color values of several pixels around it (with integer coordinate values and determined color values) according to a certain interpolation formula. Generally, there are interpolation methods such as nearest neighbor method, bilinear interpolation method and cubic spline function method. Because of the compromise between accuracy and speed, bilinear interpolation is suitable for most applications. In particular, the three primary color components of a color should be interpolated separately, instead of directly using the color index number obtained by reading pixel points. See reference [1] for a detailed discussion.

Fourth, the algorithm details

Next, a two-dimensional morphing algorithm for color images will be given. This algorithm is based on the scanning line algorithm of polygon area scanning transformation, and uses similar data structures to efficiently scan the target polygon area point by point, and at the same time realizes various technologies discussed above.

First, the data structure described in C language is given:

Structural edge {

Floating x; The x coordinate of the lower endpoint of the/* edge is indicated in the classification table ET of the edge; Edge activated chain

In the table AEL, the x coordinate of the intersection of the edge and the scan line is indicated; */

The reciprocal of the slope of the float dx/* edge; That is, the incremental value */

Y coordinate of the upper endpoint of int Ymax/* edge */

Floating rx; /* indicates the lower endpoint of an edge in ET */

Inverse transformation coordinates of float Ry/*; In AEL, it represents the inverse transformation coordinate * of the intersection of the edge and the scan line.

/

The table floats dRx/* in the direction between scan lines, and it changes reversely */

Floating dry; /* coordinate increment value (Rx, Ry) */

Struct Edge * next/* pointer to the next edge */

}; /* Information about polygon edges */

struct Edge * ET[y resolution]；

/* Classification table of edges, pointer array for classifying non-horizontal edges according to the ordinate y of the lower endpoint of the edge.

The edges with the lower endpoint equal to I are classified into class I, and in the same class, the edges are arranged in the order of increasing values of x and △ X; Y resolution is the number of scan lines */

Structure edeye * AEL；;

The active linked list of table/* edges is composed of all polygon edges intersecting with the current scan line, and the intersection order of polygon edges and the current scan line is recorded. */

Structural polygon {

Int npts/* number of vertices of polygon */

Structure point * Pts

/* Vertex sequence of polygon */

}; /* Polygon information */

Structure point {

int X；

int Y； /* Vertex coordinates */

Floating rx;

Float Ry/* Inverse transformation coordinates of vertices */

}; /* Information of each vertex of the polygon */

Note that the lower endpoint of the middle edge in the above note refers to the end with smaller ordinate value, and the other end is the upper endpoint.

The following are the detailed steps of the algorithm:

1. data preparation

For each non-horizontal edge Qi+ 1, let the coordinates of Qi and Qi+ 1 be (,yi) respectively.

And (x

i+ 1，Yi+ 1)； Its inverse transformation coordinates are (Rxi, Ryi) and (RXi+ 1, RYi+ 1).

Then fill in the fields of the information structure here according to the following types:

X=Xi, Yi Yi+1

RX=RXi，YiYi+ 1

RY=RYi，YiYi+ 1

Dx=(xi-xi+ 1)/ (yi-yi+1)

Ymax=max(yi，yi+ 1)

DRx=(Rxi-Rxi+ 1)/ (Iraq-Iraq+1)

dRy =(Ryi-Ryi+ 1)/(yi-yi+ 1)

Then insert the linked list ET[min(yi, yi+ 1)]. Activate the edge workbench AEL and leave it blank.

The ordinate y of the current scanning line is taken as 0, which is the minimum serial number.

2. Scan conversion

Repeat the following steps until y equals YResolution.

(1) If ET[y] is not empty, insert all the edges in it into AEL.

(2) If AEL is not empty, arrange edges from small to large according to the values of X and dx, and then (3); Otherwise turn.

(3) Match the edges in the AEL in turn. Then several horizontal intervals [xLeft, xRight] are formed along the current scanning line y, and the inverse transformation coordinates of the left and right endpoints are (lRx, lRy) and (rRx, rRy) respectively. For each such time interval, the following steps are performed:

dRxx=(lRx-rRx)/(xleft-xRight)

dRyx=(lRy-rRy)/(xleft-xRight)

Assume that the original image has been read into the two-dimensional array image. Let xX = xleft, rxy = lrx and ryx = lry, then for each pixel whose coordinates satisfy xLeft≤xx≤xRight (xx, y), its inverse transformation coordinates (rxy, ryx) can be calculated in the following increments:

Rxx=Rxx+dRxx

Ryx=Ryx+dRyy

Interpolation with (Rxx, Ryx) is used in the array image (see reference [1]), and pixels are displayed according to the obtained color values. Then the edge x=x+ 1 and the next pixel is calculated.

(4) Delete the edges in the AEL that satisfy y=Ymax, and then adjust the information of each edge in the AEL according to the following formula.

X=X+dx

Rx=Ry+dRx

Ry=Ry+dRy

(5)y=y+ 1, and repeat the next point.

Discussion on verbs (abbreviation of verb)

The above algorithm provides a simple and fast implementation scheme for two-dimensional deformation of color images. As for three-dimensional deformation, it is more complicated because it usually involves the elimination of hidden surfaces. However, in some cases, the blank problem can be avoided. For example, the shape of the target surface is relatively simple, and after being projected on the screen, all parts will not overlap, so there is no need to use blanking technology, and direct projection is enough.