Facsimile and static presentation processing – Static presentation processing – Memory
Reexamination Certificate
1998-10-27
2002-01-22
Evans, Arthur G. (Department: 2622)
Facsimile and static presentation processing
Static presentation processing
Memory
Reexamination Certificate
active
06341017
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The invention relates to the conversion of data from one format to another format. More particularly, the invention relates to the conversion of interleaved data to a planar data format, for example the conversion of interleaved CMYK image data to planar image data.
2. Description of the Prior Art
Color separation is used, for example, in color printing where each of three colors (i.e. cyan, magenta, yellow) and black are printed from separate print heads. Each print head receives data from a separate portion of the printer memory, such that four copies of an image are retained in memory. That is, a separate copy of the image to be printed is retained in memory for each color, where each copy contains only the information necessary to print a particular layer of the image. This technique is referred to as CMYK or planar printing because each color layer comprises a separate plane of the resultant image.
Color separation can also be effected by generating a word of data for each pixel in the image, where such data word contains all four layers of color information for that pixel. This technique is referred to as interleaved printing because each color layer is interleaved with each other color layer to produce a word of composite color information for each pixel.
Either of the above approaches produces data that correspond to a color image and that can be stored in a memory.
Often color images are input pixel by pixel, i.e. interleaved. That is, when an image is scanned, all the information for each pixel is scanned simultaneously because the scanner physically sees one pixel first and then the next pixel in sequential order. Thus, there is a physical motivation for using the interleaved format.
On the other hand, an obvious way of storing an image for multi-pass printing is by separating the different colors over four different color planes, e.g. cyan, magenta, yellow, and black. For example, a color laser printer prints in multiple passes, where there is a printing pass for each color plane. Thus, the printer may print a first pass in cyan. It prints a next pass in magenta, and then in yellow.
Thus, it can be seen that a scanner often produces image information in an interleaved format, while a four-pass laser printer prefers such information in a planar format.
Accordingly, in such devices as color copiers, which comprise both a color scanner for capturing a color image and a color printer for recording the image on paper, there is a need for efficiently and quickly converting from an interleaved format to a planar format. It is therefore desirable to provide a technique to process the two four-color data formats, while meeting the format needs of various input and output devices, where such input and output devices use some combination of these two formats
One way of performing such conversion is to provide additional storage space, i.e. more memory, where an adequate buffer is available for each plane. Thus, the interleaved data are readily sorted in sequential order, for example in an interleaved CMYK color system, to four separate buffers, where there is one buffer for each color plane. While this approach is simple, a system having 128 MB total RAM storage capacity in which an image requires 117 MB of such storage, does not provide sufficient capacity to perform the foregoing calculation. The cost and space required to add additional memory for such calculation, e.g. an additional 117 MB of RAM, makes the implementation of such simple scheme prohibitively expensive.
It would be advantageous to provide a scheme that allows for data format conversion, e.g. between an interleaved data format and a planar data format, without significantly increasing the form factor, processor speed, or RAM memory requirements of the target device, e.g. a color copier or color laser printer.
SUMMARY OF THE INVENTION
The invention provides a technique for converting interleaved data to a planar format. The herein disclosed technique requires minimal processing power and only a small amount of additional memory. The invention comprises an algorithm that follows “map cycles” throughout a frame buffer. Such map cycles result from iterating a function that maps planar addresses to CMYK addresses as follows:
Let i=index of a planar byte in the frame buffer, then:
C(i)=index of CMYK value that belongs in planar byte i
=4i, for 0<=i<N,
=4(i−N)+1, for N<=i<2N,
=4(i−2N)+2, for 2N<=i<3N,
=4(i−3N)+3, for 3N<=i<4N,
where N=the number of pixels in the frame buffer (4N=number of bytes).
The preferred method of planarizing the frame buffer is:
1. Start at an index n that has not yet been converted. Set another index i equal to the index n.
2. Save the value at i.
3. Copy the value of C(i) to i.
4. Set the index i to the next index in the cycle, which is C(i).
5. If the new index i is not the same as the index n (from 1.), then go to 3.
6. Copy the saved value (from 2.) to the most recent i (from 5) that was not equal to n.
7. The cycle starting at n is now planarized.
8. Go to 1., unless the whole file is finished. A cycle is finished when 4N copies have been made.
A key aspect of the invention involves finding the next i in step
1
. Thus, C(i) is written as:
C(i)=(4i) mod Q, where Q=4N−1 (and its inverse is C
−1
(i)=(Ni) mod Q)
Using this form, it can be proven that:
All cycle lengths divide the 1-Cycle's length evenly (and therefore no cycle is longer than the 1-Cycle);
If a cycle is shorter than the 1-Cycle, then its lowest index is a multiple of a factor of Q; and
If the 1-Cycle includes index i, then any j-cycle includes index (ij mod Q);
where, an i-Cycle is the cycle which contains index i, and a cycle's length is equal to the number of distinct indices in the cycle.
Other factors taken into account include:
Indices 0 and 4N−1 are stationary (C(i)=i);
Indices Q/3 and 2Q/3 are stationary if 3 divides Q;
If {Q/(4
n
)<=i<=Q/((4
n
)−1)}, then C
n
(i) <=i, and i is not the lowest index in its cycle.
Because there are no quick ways to determine whether a new index i is part of a cycle that has already been converted, the formula above with regard to C
n
(i) must be evaluated for every n, such that it is no different than iterating C(i) directly. Also, the structure of these cycles varies chaotically with N. A letter page sized buffer has only six cycles, each of length 10 million. If N is a pure power of four, it has the shortest possible cycles, and the greatest number of cycles. Values of N just one away from a power of four tend to have only a few cycles. Fortunately, typical page sizes tend to have few cycles.
There are three phases to the preferred algorithm according to the invention. The first two phases are order N, but the third phase takes an unpredictable amount of time. For a large value N, the third phase usually can be skipped or does not take long because the pathological N values that require significant amounts of Phase III time become increasingly spread out as N increases.
In phase I, the 1-Cycle is processed and all of its member indices that are <=MAX_HIT are saved in the array firstHit[] .
In phase II, all indices between 1 and MAX_HIT are visited, skipping any indices that have already been in a cycle (as recorded by the array firstHit[]). As each cycle is converted, any hits to indices between 1 and MAX_HIT are directly recorded in the array hit[], so that indices that have been used are quickly skipped when searching for future cycles.
Phase III is skipped unless there are still some copies left to process.
In phase III, there is no more space for recording every hit individually, so the rules noted above are invoked. When looking for new cycles, only indices that are not multiples of anything in the 1-Cycle are considered. Also, once the remaining
Electronics for Imaging, Inc.
Evans Arthur G.
LandOfFree
Interleaved-to-planar data conversion does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Interleaved-to-planar data conversion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interleaved-to-planar data conversion will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2866999