Nonconstant-Size-Factor Mapping

So far only situations that perform an entire mapping with a constant size factor have been discussed. If the size factor, and hence INSFAC, are varied for each new output pixel, any arbitrary mapping of contiguous pixel values can be achieved.

Figure 10 is a one-dimensional example of a mapping with a size factor that halves for each output pixel.

Figure 10. Example with varying size factor.

Limited-Time Performance

For contiguous mappings of consecutive input pixels into consecutive output pixels, a maximum time limit can be established. The nature of the interpolation algorithm is such that every cycle is either completing an output pixel or using up an input pixel. This includes zero cycles (see Figure 4). If there are 512 input pixels and a range of 512 possible output pixels, and if pretransform clipping is performed to ensure that only output pixels that fall within the output line are generated by the algorithm, then the algorithm will not use up more than 512 input pixels nor generate more than 512 output pixels. Any arbitrary contiguous mapping can be guaranteed to occur in 1024 cycles. A worst case, interestingly enough, is a size factor of 1.0 where, for instance, 512 output pixels are generated directly from the corresponding input pixel and 512 zero cycles are generated to get the next input pixel. A size factor of slightly less than 1.0 uses 1024 cycles with no zero cycles. This ability to deterministically bound the computation, plus the simplicity of the computation, makes the algorithm ideal for real-time implementation.

A Two-Dimensional Transform

Two-dimensional images can be spatially transformed by combining a series of one-dimensional interpolations in two passes over the image. The first pass, which we will consider to be the vertical pass, maps all input pixels into their correct vertical orientation and creates an intermediate image. The second, or horizontal, pass maps all the pixels from the intermediate image into their correct horizontal orientation to create the final output image. A technique of mapping to four target corner points to achieve size, translation, and rotation of an image can be used.

Four-Corner-to-Four-Corner Mapping Procedure

This procedure operates on an input image residing in a bounded image plane and maps the input image into a bounded output image plane. Line and column extents XBEG, XEND, YBEG, and YEND specify the bounds and the four corner points of the input image to be mapped. Four target corner points specify the corner points of the mapping in the output image plane. These target corner points can be computed by applying standard coordinate transforms to the input corner points.

Both input and output images use a fractional-valued coordinate system overlaying the discrete grid of pixels, as shown in Figure 11. All computations are in relation to this reference system. The origin is at the upper-left corner, X values increase to the right and Y values increase downward.

Figure 12 illustrates the four-corner transform. The input image corner points are labeled 1, 2, 3, 4, and the target corner points corresponding to the input points are similarly labeled. The figure shows the mapping from the input image to the intermediate image and the intermediate image to the output image.

The first, or vertical, pass maps all intensities into their correct vertical orientation column by column. Corner I must be mapped to Y1, and corner 4 must be mapped to Y4; therefore, the correct vertical orientation for the first, or leftmost, column of the input image is between Y1 and Y4. The correct vertical orientation for the last, or rightmost, column is between Y2 and Y3. The correct vertical orientation for all intervening columns is along uniformly interpolated positions between the first and last column.

Figure 11. Real-valued coordinate system over image.

Figure 12. Four-corner-to-four-corner mapping technique.

The real output location (ROTLOC) and size factor (SIZFAC) for the first column are:

ROTLOC = Y1

SIZFAC = ( Y4-Y1)/( YEND-YBEG + I)

The size factor for a rectangular output transform is a constant for all columns, but the output location varies. This variation is linear and can be accommodated by adding an increment (LOCDLT) to ROTLOC for each successive column. This increment is:

LOCDLT = ( Y2- Y1)/(XEND-XBEG)

The value of ROTLOC will be incremented by LOCDLT for each successive column one less time than the number of columns, and the output location (ROTLOC) for the last column will equal Y2. For nonrectangular output mappings, an increment can be similarly applied to the size factor.

The values to initialize the interpolation algorithm for each column are:

SIZFAC = SIZFAC

INSFAC = I/SIZFAC

INSEG = 1.0

OUTSEG = INSFAC * (1.0 - fraction (ROTLOC) )

OUTLOC = Integer (ROTLOC)

INLOC = YBEG

If ROTLOC is less than 0.0, clipping must be performed by projecting the left edge of the zero output pixel into the input line. The input line offset (INOFF) is:

INOFF = -ROTLOC * INSFAC

The values to initialize the interpolation algorithm for clipped columns are:

SIZFAC = SIZFAC

INSFAC = 1.0 /SIZFAC

INSEG = 1.0 - fraction (INOFF)

OUTSEG = INSFAC

OUTLOC = 1

INLOC = YBEG + Integer (INOFF)

After the interpolation process has operated on each column of the input image, an intermediate image is produced, as shown in Figure 12. The next step is to transform the intermediate image row by row into the output image.

The extents of the intermediate image are from XBEG to XEND and from Integer (Y2) to Integer (Y4). This bounding rectangle is the input to the second pass. The triangular areas in the rectangle outside the intermediate image must be set to zero.

The second pass basically maps the 4-1 edge of the inter- mediate image into the 4-1 edge projected through Y2 of the output image with a size factor such that the 2-3 edge of the intermediate image maps to the 2-3 edge of the output image.

Beginning at the top, the output location for the first row is the intersection of the 1-4 edge with Y = Y2.

ROTLOC = ((( Y2 - Y4) * (X1 - X4)) / ( Y1 - Y4)) + X4

The intermediate image line must be stretched a little to fit between ROTLOC and X2. The size factor is:

SIZFAC = (X2-ROTLOC) / (XEND - XBEG + 1)

The last ROTLOC must equal X4 after Integer ( Y4) - Integer ( Y2) increments, so the location delta is:

LOCDLT = (X4 - ROTLOC) / (Integer ( Y4) - Integer ( Y2))

The values to initialize the interpolation process for each row are:

SIZFAC = SIZFAC

INSFAC = 1/ SIZFAC

INSEG = 1.0

OUTSEG = INSFAC * (1.0 - fraction (ROTLOC) )

OUTLOC = Integer (ROTLOC)

INLOC = YBEG

These are identical to the values for the first pass. Clipping is also performed exactly as in the first pass.

Mapping of the first row, which consists mostly of zeros, begins at the initial ROTLOC with the proper size factor such that the data at corner 2 of the intermediate image maps into corner 2 of the output image. As for each successive row, ROTLOC moves along the 4-1 edge of the output image the 2-3 edge of the intermediate image is mapped to the 2-3 edge of the output image. The internal data of the image follows with these edge mappings through both passes and is itself correctly and proportionally mapped.