Image analysis – Image compression or coding
Reexamination Certificate
1998-11-24
2001-10-23
Johnson, Timothy M. (Department: 2623)
Image analysis
Image compression or coding
C382S297000
Reexamination Certificate
active
06307966
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to the color imaging arts. It finds particular application in digital color image copiers and will be described with particular reference thereto. It is to be appreciated, however, that the invention is applicable in other digital image processing applications (both color and monochrome) such as digital color scanners, printers, fax machines, plotters and the like, and in other environments and applications.
The generation of color documents can be thought of as a two-step process: first, a color image is generated by scanning an original document with a color image input terminal or scanner or, alternatively, creating a color image on a work station operated in accordance with a color image creation program; and second, printing the color image with a color printer in accordance with the colors defined by the scanner or computer generated image.
In a scanner, a color document is scanned line by line to acquire a full image of the document. The full image is represented as a two-dimensional data set of pixel information. The data set consists of line data in one dimension and column data in the other dimension. Due to the rastering motion of the particular input device in the scanner, a line of data is acquired relatively quickly. In contradistinction, each column of data, which is perpendicular to the line of data, is acquired relatively slowly. Accordingly, the axis of the image or acquired data set that is parallel to each line of data is called the fast-scan direction. Analogously, the axis of the image or acquired data set that is parallel to each column of data is called the slow-scan direction.
Scanner output is commonly transformed to a color space of tristimulus values, i.e., RGB (red-green-blue). Usually, these values are linearly transformed into standard XYZ coordinates of CIE color space, or a corrected transform of those values. An example of a CIE color space is the luminance-chrominance space termed CIE 1976 L*a*b* (CIELAB), where L* is lightness value, a* is a redness-greenness value, and b* is a yellowness-blueness value. These tristimulus values, which are essentially defined at the user interface, are independent of any particular device. Accordingly, the tristimulus information is referred to as being “device independent”.
Printers have an output which can be defined as existing in a color space called CMYK which stands for Cyan, Magenta, Yellow, and Key or black. The CMYK color space is uniquely defined for the printer by its capabilities and colorants. Printers operate by the addition of multiple layers of ink or colorants. The response of a printer tends to be relatively non-linear. These colors are defined for a particular device, and accordingly, reference is made to the information as being “device dependent”. While a printer receives information in a device-independent color space, it must convert that information to print in a device-dependent color space, which reflects the gamut or possible range of colors of the printer.
In a digital color copier having both a scanner and a printer, it is often desirable to electronically rotate an inputted image 180° before printing. However, such rotation provides many memory resource and allocation problems.
In a conventional method of 180° rotation, a dedicated contiguous page buffer must be created to store the rotated image data. To perform the rotation, the first pixel of line
1
of the data is transferred to the last pixel of the last line of the page buffer. Then, the second pixel of line one is transferred to the second to last pixel of the last line of the page buffer. The process is continued until last pixel of the last line is transferred to the first pixel of line
1
of the page buffer. The process is done by random addressing to memory which does not allow direct memory access (DMA) bursting in multi-master bus structures. To create the rotated image, a user must wait until the last pixel is read and written into the page buffer. Because of this, all operations must be done in an uncompressed format. Compression may be done only after the rotated image is written to the page buffer. On a 11×17 inch image at 1200×600 pixels, over 16.0 Megabytes of contiguous memory space must be dedicated as a page buffer. This is a major problem for software management of video memory in digital image processing system. Further, conventional rotation requires complicated page buffer address algorithms.
The present invention provides a new and improved method and apparatus for rotating a digital image which overcomes the above-referenced problems and others.
SUMMARY OF THE INVENTION
In accordance with one aspect of the present invention, a method of rotating an input image matrix of pixel data 180° to form an output image matrix of pixel data using a computer is provided. The input image matrix is divided into pre-rotated bands of image pixels. Groups of pixels of a first pre-rotated band are accessed beginning at a bottom end of the first band and ending at a top end of the first band. The order of the pixels within each group of pixels of the first band is then reversed. The groups of reordered pixels are written to a band memory to form a rotated band of pixel data. In the rotated band of pixel data, the order of the groups of pixels of the rotated band is in reverse order to the order of the groups of pixels in the first band. The steps of accessing, reversing, and writing steps are repeated for the other bands of image pixels. Finally, the rotated bands are combined in reverse order of the pre-rotated bands to form the output image matrix.
In accordance with another aspect of the present invention, an apparatus for electronically an input image matrix having pixel data rotating 180° to form an output image matrix of pixel data is provided. A loopback master sequentially accesses groups of pixels of a plurality of bands of the input image matrix. The loopback master begins at a lower end and ends at an upper end of each of the plurality of bands. The plurality of bands has a sequential order beginning at a top of the image matrix and extending to a bottom of the image matrix. A reorder buffer reverses the order of each of the accessed groups of pixels. A post-rotation memory receives each of the bands of reordered pixel data. A band order memory stores a reverse sequential order of the bands of reordered pixel data. A master accesses each of the bands in the post-rotation memory based on the reverse sequential order stored in the band order memory to form the output image matrix.
In accordance with a more limited aspect of the invention, a compression engine receives groups of reordered pixels from the reorder buffer and compresses the groups of pixels before they are stored in the post-rotation memory.
One advantage of the present invention is that it takes advantage of the bandwidth of high-performance busses in direct memory access systems to rotate and compress data in real-time.
Another advantage of the present invention is that it involves less data processing than other means of rotation.
Yet another advantage of the present invention is that it allows memory management software to work within its desired constructs.
Another advantage of the present invention is that it minimizes memory use and storage space.
Still further advantages of the present invention will become apparent to those of ordinary skill in the art upon reading and understanding the following detailed description of the preferred embodiments.
REFERENCES:
patent: 4947344 (1990-08-01), Hayashi et al.
patent: 5483354 (1996-01-01), Kessels et al.
patent: 5572601 (1996-11-01), Bloomberg
patent: 5751865 (1998-05-01), Micco et al.
patent: 6023556 (2000-02-01), Ledgard et al.
Fay Sharpe Fagan Minnich & McKee LLP
Johnson Timothy M.
Xerox Corporation
LandOfFree
180° rotation of digital images with concurrent compression does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with 180° rotation of digital images with concurrent compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 180° rotation of digital images with concurrent compression will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2617452