1. Field Of The Invention
The present invention relates generally to an apparatus and method for image processing. More particularly, the present invention relates to an image processing apparatus and method for converting an input matrix of input picture elements into an output matrix of output picture elements, where the number of input picture elements is greater than the number of output picture elements.
2. Related Art
A scanning device is an input device for a computer. The scanning device generates an n-dimensional digital representation from an n-dimensional image. Ordinarily, n is two. The digital representation comprises an n-dimensional matrix of picture elements (pixels). The value of each pixel indicates the amount of light reflected from the portion of the image that the pixel represents.
Resolution means the number of pixels used to represent an image. Accordingly, the resolution of a matrix is the number of pixels in the matrix.
FIG. 4 shows an example of a matrix for a 2-dimensional image. The input image 402 is of two perpendicular bars. From the input image 402, the scanning device would generate an input matrix 404. In the example, the pixels are binary. Zeros represent much light reflected and ones represent little or no light reflected.
The resolution of the input matrix 404 often exceeds the resolution of the printers, CRT's and other devices which will process it. Such devices require that an image processor first reduce the resolution. An image processor generates an output matrix which is a digital representation of the input image but which has a lower resolution (fewer pixels).
A first conventional image processor operates by performing a process called binary rate multiplication on each input row of the input matrix to generate the lower resolution output rows of the output matrix. Note that it could instead, or additionally, reduce the resolution in the vertical direction by reducing the number of rows in a similar manner.
Binary rate multiplication is a process of partitioning a set of elements into a number of mutually exclusive subsets, each having a different number of elements. The lower resolution output row consists of the unique combination of subsets in which the total number of pixels equals the desired resolution. (The desired resolution is the number of pixels in the first conventional output row 512.)
Specifically, the first subset consists of every second element of the set, the second subset consists of every fourth element of the set and, in general, the i.sup.th subset consists of every 2.sup.(-i)th element of the set. The first element of a subset is the first element of the set which is in no larger subset.
FIG. 1 shows a set 102 of elements and the subsets that it would be partitioned into by binary rate multiplication. The set 102 consists of eight elements. A first subset 104 consists of the first, third, fifth and seven elements of the set 102. A second subset 106 consists of the second and sixth elements of the set 102. A third subset 108 consists of the fourth element of the set 102. A fourth subset 110 consists of the eighth element of the set 102.
In the first conventional image processor, the set of elements is an input row. An output row includes a subset if the number of pixels in the subset plus the sum of the number of pixels in all larger subsets does not exceed the desired output resolution.
FIG. 5 shows a four row, four column input matrix 504 and a four row, three column output matrix 502 of a first conventional image processor.
The image represented by the input matrix 504 is similar to the input image 402, except that the darkness of the horizontal bar decreases from left to right. The value of each pixel is inversely proportional to the amount of light reflected by the portion of the image which it represents.
The first conventional image processor generates a first conventional output row 512 of the first conventional output matrix 502 from an input row 510 of the input matrix 504 by performing binary rate multiplication to partition the input row 510 into mutually exclusive subsets. The first subset consists of the first and third pixels 106 and 108, respectively, of the input row 510. Because the number of pixels in the subset (two) plus the sum of the number of pixels in all larger subsets (zero) does not exceed the desired output resolution (three), the first subset is included in the first conventional output row 512.
The second subset consists of the second pixel 114 of the input row 510. The number of pixels in the subset (one) plus the sum of the number of pixels in all larger subsets (two) equals the desired output resolution (three). Therefore, the first conventional output row 512 consists of the first and second subset.
A disadvantage of the first conventional image processor is that when binary rate multiplication is used to eliminate more than a small percent of pixels in the input matrix, the output matrix will substantially distort the input image.
A second conventional image processor uses pixel replication and two-dimensional convolution to generate an intermediate matrix having a resolution which is an integer multiple of the resolution of both the input matrix and the output matrix. It then generates the output matrix by selecting from the intermediate matrix a subset of pixels which are evenly spaced from one another. The number of pixels between each pixel of the subset is one less than the ratio of the resolution of the intermediate matrix to the resolution of the output matrix.
The text Digital Image Processing, by Rafael C. Gonzales and Paul Wintz (Addison-Wesely Publishing Co., pages 136-154 (1977)) discusses two-dimensional convolution in detail and is hereby incorporated by reference.
FIG. 6 shows example of how the second conventional image processor generates a three row, three column output matrix 602 from the four row, four column input matrix 504 of FIG. 5. First, the second conventional image processor performs pixel replication on the input matrix 504 to generate a twelve row, twelve column intermediate matrix 604. In the example, pixel replication involves replacing each input pixel (such as the first input pixel 106) with a three row, three column sub-matrix (such as the sub-matrix 610). Each pixel in the sub-matrix 610 has the value of the input pixel 106. Second, the second image processor performs two-dimensional convolution to modify pixel values in the intermediate matrix 604 so as to smooth the borders between the sub-matrices. Finally, the second conventional image processor generates the output matrix 602 by selecting the subset of the intermediate matrix 604 consisting of every fourth pixel in each row and every fourth pixel in each column of the intermediate matrix 604. In other words the subset consists of the pixels separated from one another by three pixels.
The second conventional image processor produces more accurate output matrices than the first conventional image processor. However, two-dimensional convolution requires excessive computation time. Therefore, the second image processor would be impractical for many applications.
Therefore, there is a need for an accurate, high performance image processor.