Single-pass warping engine

[0002] This invention is generally related to digital image processing and more particularly to methodologies for warping an input image using affine and perspective transformations.

[0003] A digital image is an electronic representation of a scene using a collection of picture elements (“pixels”). In a two-dimensional (2-D) image, each pixel may be identified by a pair of numbers or “coordinates” written in the form (u,v) of a Cartesian coordinate system, and is assigned one or more intensity values for one or more colors (abbreviated here as “color values”).

[0004] Spatial transformations, also referred to as warping, can transform an input, 2-D image into an output image, by scaling upwards or downwards, rotating, translating (moving), and/or shearing the input image. These transformations are known as affine transformations. Another type of spatial transform is a perspective transformation in which the image is transformed so that its edges converge to one or both axes of the output image's coordinate system.

[0005] Image warping is used to enhance image quality and correct images in a variety of different applications, including computer graphics, computer vision, medical imaging, and remote sensing. In addition, image-based modeling and rendering (IBMR), where three-dimensional (3-D) images are created from 2D images or photographs, makes extensive use of 2-D warping to transform several reference images and then composite them for a desired 3-D view. The use of IBMR in 3-D video applications, such as computer games and computer-animation, calls for fast warping, due to the fast image rendering required for depicting complex and rapidly changing scenes.

[0006] Warping may be viewed as a mapping of the input image coordinate system (u,v) into the coordinate system (x,y) of the output image. This may be depicted by a matrix equation [x′,y′,w]^T=matrixW *[u,v,1]^Tin which the coordinates (u,v) of a pixel in the input image are mapped to coordinates (x=x′/w,y=y′/w) by performing the matrix multiply operation and a perspective divide. The matrix W is a 3×3 matrix known as a concatenated warping matrix whose elements define the affine and perspective transformations.

[0007] Some scanline warping methodologies have been developed that operate only along rows and columns of the input image and one or more intermediate images, to exploit simplifications in digital filtering and memory access. See e.g. Catmull, Edwin and Alvy Ray Smith, “3-D Transformations of Images in Scanline Order,” Computer Graphics, (SIGGRAPH '80 Proceedings), vol. 14, no. 3, pp. 279-285, July 1980. The latter is a “two-pass” technique in which the first pass through the input image applies a transform to each row to yield an intermediate result, and then a second pass applies another transform to each column of the intermediate result image to yield the output image.

[0008] Some of the problems with the two-pass technique referred to above include the provision of a special case for rotations of 90 degrees (due to a singularity in the transform applied in the first pass). This makes the technique more complicated in a hardware-only implementation. In addition, the two passes through the input and intermediate images may not be the most efficient way to utilize hardware parallelism. Finally, reconstruction of aliasing holes require yet another pass through the output image, thereby further increasing the time needed to warp the input image.

[0009] The invention is illustrated by way of example and not by way of limitation in the figures of the accompanying drawings in which like references indicate similar elements. It should be noted that references to “an” embodiment in this disclosure are not necessarily to the same embodiment, and they mean at least one.

[0010] FIGS. 1-7 show various examples of warping that can be accomplished by a single-pass warping engine.

[0011] FIG. 8 shows sections of the input and output images during an embodiment of a single-pass warping process.

[0012] FIG. 9 illustrates a flow diagram of operations in an embodiment of the warping process.

[0013] FIG. 10 depicts a hardware block diagram of an embodiment of an image processor that contains the warping engine.

[0014] An embodiment of the invention is directed to a digital image warping methodology that avoids the singularities of the two-pass warping technique described above. In addition, the warping methodology executes in a single pass of the input image and it performs any needed image reconstruction simultaneously in the single pass, to yield the output image without any aliasing holes. The methodology may prove to be particularly effective in hardware-only implementations, which provide a greater speed of execution than software being executed by a general purpose processor. Examples of warping that can be accomplished by the methodology are shown in FIGS. 1-7 which are based upon a square, upright image of a mandrill.

[0015] An embodiment of the warping methodology will be described with reference to FIG. 8 in which an input image 104 is made up of an array of input pixels 110 that are identified by their (u,v) coordinates in the u-v coordinate system. An output image 108 from a warping transformation is defined as having an array of pixels where each pixel is identified by a pair of coordinates (x, y) in the x-y coordinate system. Each input pixel 110 of the input image 104 is defined as having color values P₁(U,V), P₂(U,V) . . . where (U,V) identifies the input pixel 110 by its location. This input pixel 110 is then warped into an output pixel 112 which has the same color values as the input pixel 110 but at different coordinates (X,Y).

[0016] The general form of the warping matrix W is given in FIG. 8 as a nine element 3×3 matrix. R₁₁-R₂₂are rotation parameters (where R₁₁=cos θ, R₁₂=−sin θ, R₂₁=sin θ R22=cos θ) and, S_xand S_yare scaling parameters in the x and y directions, respectively, Sh_xand Sh_yare shear parameters in the x and y directions, respectively, T_xand T_yare translation parameters, and Vp_xand Vp_yare vanishing points for the perspective transformation. Aliasing artifacts may appear in the output image 108 following a warping transformation, because, in general, the transformation is not a one-to-one mapping in image space. Such artifacts may be caused by, for instance, transforming a square input pixel into a rectangular one. Artifacts may also occur due to overlapping pixels. One type of overlapping occurs when the image is folding over itself, where the warping transformation has resulted in two pixels occupying the same space. The warping functions of minification, scaling downwards by less than 1, and rotation often produce overlapping pixels.

[0017] Yet another type of aliasing occurs when magnifying or scaling an image upwards and rotating the image. These transformations produce “holes”, i.e. pixel locations to which no input pixels have been mapped by the warping transformation, in the output image. These holes can be filled by linear or bilinear interpolation of the neighboring pixels to have an acceptable quality output image.

[0018] According to an embodiment of the invention, the single pass warping methodology begins with the upper left most pixel at (u=0, v=0), and proceeds from left to right until each scanline (in this example, row) of the input image 104 has been processed, and then moves to the next immediately adjacent scanline. Each transformed scanline is called a ‘pixel sequence’. For example, scanlines v=0 and v=1 are transformed into sequences 114 and 116, respectively.

[0019] Each pixel 110 of the input image 104 is processed by being multiplied by a warping transformation matrix W, resulting in a new set of coordinates, (x,y). Thus, it can be seen that input pixels at (u=0, v=0) and (u=1, v=0) are translated into adjacent pixels beginning at the upper left hand corner of the output image 108. However, the scanline's third input pixel at (u=2, v=0) is transformed into a pixel which is not adjacent to the previously transformed one at (u=1, v=0). The empty location between the transformed (1,0) and (2,0) input pixels is known as a hole that has no color value. The distinction between holes (pixels with no mapped color values) and transformed pixels in FIG. 8 is made by the absence and presence, respectively, of a right-pointing triangle in the pixel location.

[0020] Magnified holes may be a result of magnification in the warping matrix, i.e. S_x>1 and/or S_y>1. Such a hole may be filled, e.g. interpolated, based upon the color values of the neighboring pixels of the output image 108.

[0021] A pixel sequence may skip a hole not only in the x direction but also in the y direction. Thus, the first scanline 114 is shown as stepping in the y direction at the fourth pixel of the scanline, namely input pixel (u=3, v=0). The resulting output pixel lies in the second row of the output image. This transition to a different row is termed a “barricade” pixel. The output pixel that is immediately prior to the barricade pixel is termed a “previous” or “last” pixel. This stepping of the transformed pixel sequence in the y direction may create holes in the rows of the output image 108 that contain the last pixel and the barricade pixel. These holes may be due to rotation in the warping transformation, such that they are termed rotation holes in FIG. 8. The rotation may also cause holes in the same row as the last pixel beyond which there are no transformed pixels in the same row. These holes are termed orphaned holes. To provide an acceptable image quality, all holes resulting from the warping transformation, including rotation holes, orphaned holes, and magnified holes, are to be filled. However, unlike the two-pass technique described above in the Background section, the filling of these holes occurs, in a particular embodiment of the invention, simultaneously with the transformation in scanline order, such that all of the pixels in the output image are defined following a single pass through the input image 104.

[0022] FIG. 8 shows a number of pixel sequences, including references 114 and 116 as well as others successive thereto, which are in effect transformed scanlines (here, rows) from the input image 104. The warping transformation responsible for producing such pixel sequences included a rotation of 15 degrees and a magnification of 1.5. What is not shown therefore is the effect of a warping transformation that includes minification. In that case, it may be expected that the transformed scanlines behave differently than shown in FIG. 8 such that certain pixels of the transformed scanline overlap, i.e. have the same (x,y) coordinates as previously transformed pixels of the same scanline. In that case, the overlapping pixels need to be adjusted, such as by performing a weighted average as further described below, to yield an output image of acceptable quality.

[0023] In another scenario not shown in FIG. 8, overlapping pixels may appear across two transformed scanlines if, for instance, the image is rotated and strongly magnified. In that case, certain pixels of a transformed scanline will overlap pixels previously computed for one or more previously transformed scanlines. Once again, these overlapping pixels need to be addressed by being adjusted according to various mathematical formulas.

[0024] As mentioned above, the scanning of the array of pixels in the input image 104 may start at u=0, v=0, and the input coordinates are transformed one at a time until reaching the last pixel at uRes−1 and vRes−1, by incrementing column and row indeces in scanline order. Variables uRes and vRes are the maximum u and v resolutions of the input image, respectively. The remaining operations in an embodiment of the warping methodology are now described, using reference numerals as follows.

[0025] 1. The scanline processing of the input image may be implemented, for instance, using two embedded “for” statements in the C programming language as:

[0026] 2. Inside the loops of the for—statements above, the vector equation shown in FIG. 8 is calculated to spatially transform each input pixel into the coordinates (x,y) of the output pixel. As mentioned above, this warping transformation may result in holes for which no input pixels have been mapped, such that these holes have no color values. Thus, some of the remaining operations of the methodology determine where the holes and overlapping pixels are located, while moving along each scanline. Once the coordinates of these holes are known, the methodology, for instance, linearly or bilinearly interpolates the pixel colors to fill a hole. If an overlapping pixel has been located, the methodology, according to one embodiment, averages the overlapped pixels.

[0027] 3. The transformed scanlines (or sequences) are stored in cache memory. Thus, a new cache address is computed as:

[0028] cacheAddress=CacheBias+row*pReg−>SrcWidth+column;  (8)

[0029] Each newly transformed pixel is stored in the cache using the variable thisPixel, i.e. the current pixel in the sequence;

[0030] Cache[cacheAddress]=thisPixel;  (9)

[0031] A mask array for the current transformed sequence is created. The pixel mask for this pixel is then set to one, mask[index][(int) thisPixel.x], indicating that this pixel is filled with color values.

[0032] 4. Variables that represent changes in the x and y coordinates are calculated based upon the location of the current pixel (thisPixel[X,Y]) and the last pixel (lastPixel[X,Y]) of the current transformed scanline (see FIG. 8, where green represents last pixels):

[0033] deltaX=abs((int) thisPixel.x−(int)lastPixel.x);  (10)

[0034] deltaYperPixel=abs((int) thisPixel.y−(int) lastYperPixel);  (11)

[0035] The absolute value function applied to the x coordinate prevents negative values of deltaX when the x coordinate wraps around to the beginning locations of the next row (such as when deltaX=−S_x*cos θ*pReg−>SrcWidth). The variable deltaYperPixel will normally be zero if the transformed scanline stays along one row in the x-y coordinate system. However, when there is rotation or foreshortening as in a perspective effect, this variable may occasionally have a value greater than zero which, as stated above, may result in rotation holes as well as orphaned holes in the output image 108.

[0036] 5. A variable representing the change in the y direction from the last transformed scanline is then computed. This represents a change in the y coordinate of the current pixel as compared to a last pixel in a previous transformed scanline:

[0037] deltaYperScanline=(int) thisPixel.y−(int) lastYperScanline;  (12)

[0038] The variable lastYperScanline is set to the last value of y, at the beginning of each row of the output image 108. This is because the processing of the input pixels is occurring in scanline order and the defined change in the y coordinate of an output pixel may be greater than one if there is magnification in the y axis.

[0039] 6. If both deltaX and deltaYperPixel are zero, the current pixel is overlapping the last pixel. In that case, a weighted linear interpolation may be performed between thispixel.color and lastPixel.color. For instance, the weight used may be 0.5 which results in taking the average of the color values of the current pixel and the previous pixel.

[0040] 7. If (mask[lastMask][Dst.V.x]==1) then a pixel “collision” has occurred in which the location of the current output pixel in the current transformed scanline overlaps with that of an output pixel in a previous transformed scanline. To address this situation, a two scanline pixel mask is created, in which a bit is set for each pixel that has been assigned a color value, and a bit is cleared everywhere else. The overlapping pixel's cache address is computed and its coordinates are fetched. If the Y values of the pixel in cachePixel.V.y and this pixel.V.y match, i.e. the overlapping pixels are in the same row, a weighted linear interpolation is performed between the cached pixel's color values and the current pixel's color values, for instance using a weight value of 0.5 which corresponds to a simple averaging.

[0041] 8. Image magnification occurs when the scaling parameters of the warping matrix are greater than one, i.e. S_x>1.0 and/or S_y>1.0.

[0042] 8.1 If ((deltaX>1) and (deltaX≦┌S_x┐)) where the symbol ┌ ┐ represents a rounding up to the nearest integer, then fill the hole with a linear weighted average between the color values of the last pixel in the same row of the output image as the current pixel.

[0043] 8.2 If ((deltaYperScanline>1) and (deltaYperScanline≦┌Sy┐), fill the hole with a linear weighted average between the color values of the last vertical pixel and that of the current pixel.

[0044] 8.3 If both 8.1 and 8.2 are true, then fill the hole with a bilinear weighted average between the color value of the last pixel and that of the current pixel.

[0045] 9. If the variable deltaYperPixel is greater than zero and less than ┌Sy┐, than the rest of the row in the output image may be “blocked” from this position to the end of the transformed scanline. In such a situation, a copy of the current pixel's color values and coordinates are pushed into a first in first out (FIFO) buffer where it can be retrieved at a later time when processing the next scanline. This pushing of barricade pixels onto the FIFO buffer continues along the scanline whenever deltaYperPixel is greater than zero.

[0046] In addition, while proceeding along the scanline, if deltaYperPixel is greater than zero, a previously pushed barricade pixel is popped from the FIFO buffer. This popped barricade pixel would normally be from a previous transformed scanline; if the Y coordinate of the popped barricade pixel matches the Y coordinate of the current transformed scanline, as determined from the Y value of the last pixel in the current transformed scanline, this indicates the presence of holes between the popped barricade and the last pixel in the current transformed scanline that are in the same row of the output image.

[0047] 9.1 In a particular embodiment, the barricade pixel which has been popped from the FIFO buffer is verified to determine whether its Y coordinate matches that of the current pixel. If not, the Y coordinate of the popped barricade is compared to that of the last pixel, i.e. the previous pixel in the current transformed scanline. If there is still no match, the barricade pixel is discarded.

[0048] 9.2 If there is a match in the Y coordinate with either the current pixel or the last pixel, a fragment length is computed. For instance, if the match is with the last pixel, then the fragment length is given by

[0049] fragmentLength=Barricade.x−lastPixel.x.  (13)

[0050] This fragment length is then used as a limit on an index for interpolating pixels between the last pixel and the barricade pixel that has just been popped from the FIFO buffer. In a particular embodiment, a weighted linear interpolator needs a pixel weight to fill the holes. Thus, for instance,

[0051] weight=index/fragmentLength.  (14)

[0052] The hole color is then given by

[0053] hole.color=LinearInterpolation (thisPixel.color, lastPixel.color, weight)

[0054] where the function LinearInterpolation (thisPixel.color, lastPixel.color, weight) may be defined according to known interpolation schemes. In addition, the coordinates of the hole are calculated as follows:

[0055] hole.x=Barricade.x−index  (15)

[0056] hole.y=lastPixelt.y  (16)

[0057] With the above information, not only can the hole be identified, but also its color values can be determined.

[0058] A special area of cache memory may be dedicated for filling holes in the output image as follows:

[0059] ExtraCacheAddress=pReg−>CacheBaseAddress+pReg−SrcHeight*pReg−>SrcWidth; Cache[ExtraCacheAddress}=hole  (17)

[0060] Once the hole has been identified and filled in this manner, the pixel mask for the hole is set, i.e. mask[index][(int) thisPixel.x]=1.

[0061] If there are remaining pixels to be transformed in the input image 104, then the appropriate indices are incremented, the pixel mask is reset to zero for the currently transformed scanline, and steps 2-10 above are executed for the next pixel of the scanline in the input image 104. On the other hand, if the filled hole was the last pixel in the transformed scanline, then the contents of the cache which include the transformed scanline and the filled holes, are transferred into an output buffer for further processing. Thus, the entire input image is processed in this manner in scanline order, where each transformed scanline including its filled holes and those between it and a previous scanline are transferred to an output buffer, before the next scanline is processed, to generate the entire output image one scanline portion at a time.

[0062] FIG. 2 illustrates a flow diagram for an embodiment of the single pass warping methodology. Operation begins as indicated in block 204 in which the coordinates of the next pixel in a scanline of the input image are fetched and transformed, according to steps 1 and 2 described above. The flow then proceeds with block 208 in which the coordinates of the transformed pixel and its color values are stored in cache memory, as in step 3 described above. This is followed by the operations of block 212 in which deltaX and deltaY are computed according to steps 4 and 5. A decision block 216 is then reached where deltaX and deltaY per pixel are evaluated to determine whether there are any overlapping pixels, according to steps 6 and 7. If there are, these are more likely than not minify overlap pixels which may be then averaged and saved in an external or separate cache memory area, as in operation 218. Operation continues with another decision block 220 in which horizontally oriented holes are detected, as in step 8.1. These holes may be caused by image magnification and may be filled, as in operation 219, by interpolating with the last pixel and saving the interpolated color values and coordinates of the hole in a separate area of the cache memory.

[0063] A further decision block 224 determines whether the change in the Y coordinate of this pixel as compared to a previous scanline is greater than 1, which means that holes between the current transformed scanline and a previous transformed scanline have been detected, as provided, for instance, by step 8.2 described above. If so, then these holes, which may also be caused by image magnification, are interpolated as in operation 222 using for instance linear weighted averaging of this pixel and a last pixel in the previous transformed scanline. Once again, the interpolated color values and location of the filled hole are saved in cache memory.

[0064] The decision block 228 detects holes that are in the same row as a last pixel of the current transformed scanline, in response to a change in the Y coordinate of the current pixel, according to step 9. After popping a barricade pixel from the barricade FIFO, these holes, which may be caused by a rotation, are filled in accordance with steps 9.2, 9.3, and 9.4 described above and as referenced in operation 223. The methodology then loops back to fetch the coordinates of the next input pixel of the scanline and resumes operation at block 204.

[0065] FIG. 10 illustrates an exemplary hardware architecture that may be used for supporting image-based rendering. The logic circuitry includes a warping engine 304 which may be configured to perform the scanline order operations described above for warping an input image into an output image. The warping engine 304 includes a number of functional units (not shown) including hole detection logic, overlap detection logic, adjusting logic, and interpolation logic, all designed to perform the operations described above for an embodiment of the single-pass warping methodology. An alternative implementation would be software-based, with instructions that are stored in a wide range of machine-readable media (including solid state memories, magnetic, and optical disks) and which, when executed by a processor, cause any one of the above-described embodiments of the single-pass warping methodology to be performed. A warping engine FIFO 316 is provided to allow fast access to the pixel sequences (transformed scanlines) by the warping engine 304. The warping engine 304 has a separate path to the cache memory 308 via a bus 312. The input image is initially obtained, from either a sensor or other source for image data (not shown) by a mapping engine 324 which controls the imaging tasks of the different hardware modules. The transformed scanlines that are stored in the cache 308 are read by the mapping engine 324 and provided as an output via the mapping engine FIFO 328. The mapping engine 324 may also be coupled to control a geometry pipeline (not shown) that contains a texture processor module which may be given access to the cache bus 312, for texturing the warped images on to some arbitrary surface.

[0066] Various embodiments of the invention have been described that are directed to an improved technique for performing a digital warping transformation. In the foregoing specification, the invention has been described with reference to specific exemplary embodiments thereof. It will, however, be evident that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention as set forth in the appended claims. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.