Apparatus for Altering the Spatial Characteristics of a Digital Image by Polynomial Interpretation Using Sets of Arithmetic Processors

This invention relates generally to the display of digital images and more particularly the invention relates to an improved means for establishing new pixel values for new pixel locations from an image having established pixel locations and values. The new pixel locations could be chosen, for example, to magnify, minify, translate or distort the original image.

The display of a digital image, for example on a video screen or photographic film, is controlled by a memory which stores values for picture elements or pixels. In a video display, an electron beam is scanned across the phosphor-coated surface of the display screen, and the current of the electron beam is controlled in accordance with the stored values to thus control the light intensity of each pixel element as the electron beam impinges on the phosphor material. Alternatively, the digital image can be transferred to photographic film by scanning a laser beam across the film and modulating the intensity of the laser beam in accordance with the stored pixel values.

In any of the image processing tasks mentioned above, values for pixels at locations different than the original pixel locations must be derived. The simplest technique for doing this is to use, for each output pixel, the value of the nearest input pixel. Minification is then performed by selectively deleting pixels while to magnify some or all of the pixel values are replicated. The resulting image quality is often not satisfactory. Values for the new pixel locations can be arrived at using linear interpolation in both directions. However, images magnified using this method are blurry and structured noise is sometimes visible.

Improved fidelity and sharpness can be realized if the interpolation of new pixel values is a higher order polynomial interpolation. For example, in a third order interpolation of a pixel value in a new matrix to be described, the values of sixteen adjacent pixels in the old matrix are used. Generally, the higher the order of the polynomial used, the more fidelity and sharpness the new image will have. However, as the order of the polynomial interpolation increases, more computations are required in determining the new pixel values.

Disclosed in copending application Ser. No. 672,609 filed Nov. 19, 1984, is an efficient method and apparatus for implementing polynomial interpolation of pixel values in a new matrix using pixel values of an old matrix. The polynomial interpolation is implemented by a weighted combination of the input pixels. A table of coefficients for the polynomial interpolation of pixel values in a new matrix is employed which is based on one dimensional (e.g., x or y) incremental spacing from pixels in an old matrix.

Briefly, the pixels in the new pixel matrix are mapped in the old pixel matrix to obtain x and y offsets from old pixels. The offset for each new pixel in one dimension (e.g., x dimension) is determined and values for interim pixels are interpolated or obtained using values of a plurality of old pixels adjacent to each new pixel in the one dimension. The final pixel values are then obtained by polynomial interpolation in the other dimension (e.g., y dimension) using the calculated values of interim pixels. Importantly, the weighting coefficients for the one dimensional interpolations are precalculated for given incremental values. Thus, the time consuming tasks of calculating polynomial coefficients and evaluating polynomials are not required during the calculation of new pixel values.

The present invention is directed to apparatus for implementing high speed image calculations necessary for higher order polynomial interpolation such as disclosed in copending application Ser. No. 672,609, supra. The apparatus includes sets of arithmetic processors which operate in parallel in executing identical algorithms for assigned pixels of an image. Each set includes a first processor and a second processor. The first processor performs the arithmetic manipulation of the pixel data in calculating the final pixel values. The second processor is assigned the tasks of addressing source image data, addressing destination image data, calculating weighting constants to be used by the first processor, and functioning as system controller for the image interpolation.

The multiprocessor sets can be expanded to include any number of processors operating in parallel on assigned pixels. In one embodiment using two multiprocessor sets for odd and even pixel locations, respectively, image interpolation was up to forty times faster than image interpolation using a single main frame computer.

The invention and objects and features thereof will be more readily apparent from the following detailed drawings, in which:

FIG. 1 is an illustration of a portion of a matrix of known pixel values and a matrix of pixels whose values are to be calculated.

FIG. 2 is a functional block diagram of computer apparatus for determining new pixel values using higher order polynomial interpolation.

FIG. 3 is a program flow diagram for calculating new pixel values using higher order polynomial interpolation.

FIG. 4 is a schematic diagram of one embodiment of apparatus to carrying out the order in accordance with the present invention.

FIGS. 1-3 illustrate the method of high speed image calculation for higher order polynomial interpolation disclosed in copending application Ser. No. 672,609, supra.

FIG. 1 illustrates a portion of a matrix 10 of pixels of known value such as the pixels 11, 12, 13 and 14 in one horizontal row of the matrix. Assume that a new matrix of pixels is mapped on the old matrix 10 and the new pixel 15 is in the new matrix. As illustrated, the pixel 15 is offset from pixel 12 by a horizontal distance, x, and a vertical distance, y.

In general, the value of a new pixel 15 is arrived at by treating the region of the image in the neighborhood of pixel 15 as some function f (x,y) the details of which depend on the values of neighboring pixels. The value assigned to pixel 15 is then the value of the function f (x,y) at the position of pixel 15. This process is repeated for all the output pixels to arrive at the interpolated image. In polynomial interpolation, the function f (x,y) is a polynomial function of x and y. The process of calculating the output pixel value then involves calculating the polynomial coefficients using input pixels neighboring the output pixel and then evaluating the polynomial. Typically, the number of input pixels used is equal to the number of polynomial coefficients of f (x,y) that must be determined. For example, suppose we wish to use as a model the polynomial:

Suppose we want to compute the value for a pixel to be located at (x, y). Coefficients a.sub.o, a.sub.1 . . . a.sub.8 such that f (x,y) exactly matches the values of nine input pixels surrounding (x,y) are calculated.

For the model of Equation 1 this is done by solving a system of nine equations (one for each input pixel) with nine unknowns (the coefficients). The coefficients are then used to calculate the output pixel value:

If the two dimensional polynomial model contains all terms up to nth order in either variable, where n is any integer, then the two dimensional interpolation process can be broken down into one-dimensional interpolations. For example, the first step would interpolate in the x direction and arrive at interim pixel values for pixels (x, y.sub.e) where y.sub.e takes on the values of y for rows neighboring the desired output pixel. Then, an interpolation in y is used, using the interim pixel values as inputs, to compute the output pixel value for the desired pixel at (x, y). It will now be shown that for polynomials that include terms to nth order in either coordinate the two dimensional interpolation can be simplified into two one-dimensional interpolation steps. The polynomial model we use is: ##EQU1## In a (n+1) square array of pixels surrounding the desired output location (x, y) x will take on values {x.sub.o x.sub.1, . . . , x.sub.n } while y will take on values y.sub.o, y.sub.1 . . . , y.sub.n. Let v (x.sub.k, y.sub.1) be the value for the pixel at (x.sub.k, y.sub.e). We need to arrive at a value for a new pixel at (x, y). The classical way to do this is to generate a set of coefficients {a.sub.i, j} such that ##EQU2## is true for all the (n+1).sup.2 pixels in the square region surrounding (x, y), and then using these to calculate the desired output ##EQU3## Consider an interim pixel location at (x, y.sub.e). Define b.sub.ie by: ##EQU4## Note that the coefficients b.sub.ie depend on the y coordinate y.sub.e but are independent of x. We can now rewrite Equation 4 as: ##EQU5## and Equation 5 for the interim pixel becomes: ##EQU6## Equation 7 and 8 define an nth order one-dimensional polynomial interpolation in x along the row y=y.sub.e, to arrive at a value for the interim pixel at (x, y.sub.e). It is clear, though, that the value arrived at for this interim pixel by one dimensional interpolation is exactly the value that would be arrived at by the two-dimensional process. This is true for all pixel positions along rows of the old matrix. This can be understood intuitively by noting that for any fixed value of y, Eq. 3 is an nth order polynomial in x, as is the one dimensional model, and if the two agree at (n+1) points along the row, they will agree everywhere along the row.

Suppose that values for interim pixels (x, y.sub.e) for the (n+1) rows surrounding the pixel of interest have been calculated by nth order (n+1) polynomial interpolation. Again, the interim pixel values agree with what the full two-dimensional method would have given at those locations. Define ##EQU7## The set {c.sub.j } can be computed by finding the coefficients for which ##EQU8## is true for all the interim pixels. Eq. 5 now becomes: ##EQU9## Equations 10 and 11 define one dimensional nth order polynomial interpolation in the y direction along the column defined by the interim pixels and which also contains the output pixel (x,y). Again, since both equations 5 and 11 are nth order polynomials and since they agree at (n+1) points (the interim pixels) they must give the same value at (x,y). Thus, the two dimensional interpolation can be implemented using simpler one dimensional interpolation steps. Further, it will be clear to those skilled in the art that many of the interim pixel values needed to calculate one output pixel can be stored and used to calculate other output pixels.

We can restrict outselves to dealing with one dimensional interpolation. It will now be shown that the interpolated output value can be calculated as a linear combination of the input pixel values, where the combination coefficients depend on the relative position of the output point with respect to the input points.

We use as a model: ##EQU10## Again, the coefficients a.sub.i are arrived at by forcing ##EQU11## to be true for the (n+1) pixels surrounding the output location, where {x.sub.k } and {v.sub.k } are the input pixel locations and values respectively. There are (n+1) equations like Equation 13 which we can write in matrix form:

A is a row vector containing the polynomial coefficients, X is a square matrix containing the x values raised to the appropriate powers, and V is a row vector containing the pixel values. We solve for A by:

and then find the desired output pixel value by

where X is a column vector containing X raised to the appropriate powers. Substituting Equation 15 into Equation 16 and regrouping we get

which shows that the output value is a linear combination of the values of the surrounding input pixels. The combination coefficients are given by (X.sup.-1 X) and depend on the relative position of the output pixel within the input array. Once the combination coefficients are known, the interpolation requires (n+1) multiplications and n additions.

If the input pixels are equally spaced, the combination coefficients depend only on the normalized distance of the output pixel from the pixel to its left. We define this normalized distance by: ##EQU12## where x.sub.k is the pixel location just to the left of x and p is the spacing between pixels.

One advantage of using an odd number for the polynomial order n is that the number of input points used for each output point, (n+1), is even. Thus, the input points can be symmetrically located about the output. Following is a derivation of the combination coefficients for a third order interpolation (n=3).

The model for this third order interpolation is:

Since X.sub.k is the pixel location just to the left of X, the four pixels to be used have values V.sub.k-1, V.sub.k, V.sub.k+1 and V.sub.k+2 and their respective X as values are -1, 0, 1, and 2 respectively. Using Equation 19, the four equations used to calculate the polynomial coefficients a.sub.i are:

Equation 20B defines a.sub.o. Adding Equations 20a and 20c yields:

Substituting Equation 20b and regrouping gives an expression for a.sub.2 :

Subtracting Equation 20a from Equation 20c gives:

Substituting Equations 20b and 22 into Equation 20d and regrouping gives:

Equations 23 and 24 can be solved for a.sub.1 and a.sub.3 :

Substituting Equations 20b, 22, 25 and 26 into Equation 19 and combining like terms yields:

where ##EQU13## Thus, to perform the cubic interpolation, it is not necessary to solve a system of equations for the polynomial coefficients and then to evaluate the cubic polynomial at the desired location. Instead, the combination coefficients for the four points surrounding the output location can be calculated using Equations 26 and 28 and then used with Equation 27 to calculate the output value.

Even with this method, there are many arithmetic operations involved in the interpolation since there are many operations needed to generate the combination coefficients for a given (.DELTA.X). However, this latter computational burden (the operations involved in generating the coefficients) can be eliminated. This is done by precalculating the coefficients for a set of values of .DELTA.x, and storing these in a table. When coefficients for a particular value of .DELTA.x are needed, the coefficients for the nearest table entry are used. Alternatively, linear interpolation between table entries could be used.

It has been found that for a particular application cubic interpolation using 128 sets of precalculated combination coefficients performs very well. Following is a table of combination coefficients for cubic interpolation at 128 equally spaced values of .DELTA.x: ##SPC1##

In this method of interpolation, then, for a desired output pixel location x, the first pixel to the left, x.sub.k, is identified, .DELTA.x is calculated using Equation 26 (note that the pixel spacing p is usually normalized to unity so no dimension is necessary), the four combination coefficients for the table entry with a value of .DELTA.x closest to the calculated value are found, and these coefficients are used along with the values for the four pixels surrounding x in Equation 28 to calculate the output value.

Referring again to FIG. 1, a value for the interim pixel 16 is first calculated using .DELTA.x and the values of the four adjacent old pixels 11, 12, 13, and 14 (for a third order polynomial). Similarly, values for interim pixels 17, 18 and 19 are calculated. A final pixel value is obtained for pixel 15 from the polynomial interpolation along the y-axis using the values of the pixels 15, 17, 18, and 19 and the offset .DELTA.y.

This procedure is illustrated in the computer system of FIG. 2. The new pixel 15 from FIG. 1 is located in the matrix map 20 using the matrix 10 of FIG. 1. The x-offset (.DELTA.x) is located at 22, and the y-offset (.DELTA.y) is located at 24. The interim pixel value is then determined at 26 using the x-offset, .DELTA.x, coefficients from the table of coefficients 28, and the values of the four adjacent pixels. The final pixel value of pixel 15 is obtained at 30 using the interim pixel values 26 and the y-offset, .DELTA.y.

FIG. 3 is a flow diagram of the program for obtaining the interim pixel values and the final pixel values. The new pixel values x.sub.0, the x-offset, .DELTA.x, and the number of new pixels, n, are provided as inputs along with the old pixel values, IN(j), at 40.

Next, each pixel, k, is taken in turn and the mapped position, x.sub.0, is specified. The y/x incremental distance is then determined at 44. Coefficients from the table of coefficients 46 are retrieved and applied in the polynomial equation using the values of the 16 adjacent old pixels as shown in 48 to obtain the interim pixel values. The interim pixel values are then used with the appropriate weighting constants, determined by .DELTA.y, to calculate the new pixel value. The procedure is repeated until all new pixel values are determined.

The described method of calculating image data using polynomial interpolations has been implemented using a data general S140 computer. However, in accordance with one embodiment of the present invention using two multiprocessor sets, or four arithmetic processors, image interpolation has been realized which is four to forty times faster than the single main frame computer.

FIG. 4 is a function block diagram of the embodiment using two multiprocessor sets for operating on odd and even numbered pixels, respectively. The even data set includes a first processor 50 for performing the arithmetic manipulation of the pixel data and calculating final pixel value and a second processor 52 for addressing source image data in a buffer memory 54, addressing the display memory 56, and determining and addressing the weighting constants in memory 58 for use in the arithmetic manipulation. Similar elements are employed in the odd data set as designated by the prime numbers.

In operation, unmagnified (or unminified) image data is generated by a scanning system such as the General Electric CT 9800 computerized tomographic scanning system (not shown) and stored in buffer memories 54 and 54', the two buffers cooperatively storing data for a full image. Data is read from the buffer memories 54, 54' and applied to processors 50, 50' along with the requisite interpolation weighting constants from memories 58, 58' under control of processors 52, 52'. The new data calculated by processors 50, 50' is then stored in the display memories 56, 56' under control of processors 52, 52'. The system then accesses the display memories for display refresh with the odd and even pixel data from the memory being multiplexed at 60 and applied through a digital to analog converter 62 to control display 64.

The embodiment illustrated in FIG. 4 has been implemented using TMS 320 processors for use with the GE CT 9800 system which includes a Z80 microprocessor. The TMS 320 processors operated in accordance with the interpolation algorithm disclosed in copending application Ser. No. 672,609, supra. Attached hereto and incorporated by reference are the program listings for controlling processor 50 and processor 52, respectively.

While the invention has been described with reference to an embodiment including two multiprocessor sets for operating on odd and even pixel data, respectively, the description is illustrative of the invention and is not to be construed as limiting the invention. Obviously greater calculation speed can be realized by employing additional multiprocessor sets for operating on smaller groups of image pixel data. Thus, while the invention has been described with reference to a specific embodiment the description is illustrative of the invention and is not to be construed as limiting the invention. Various modifications and applications may occur to those skilled in the art without departing from the true spirit and scope of the invention as defined by the appended claims.