(3) Summary of the invention
The following presents a simplified summary of the invention in order to provide a basic understanding of some aspects of the invention. This summary is not an extensive overview of the invention. It is not intended to identify key/critical elements of the invention or to delineate the scope of the invention. Its sole purpose is to present some concepts of the invention in a simplified form as a prelude to the more detailed description that is presented later.
The present invention provides a system and method of digital image compression that uses a multi-resolution lapped transform that can receive input values (e.g., from a color space mapper) and provides an improved presentation. The multi-resolution lapped transform utilizes a layered lapped biorthogonal transform, which mitigates the "grouping artifacts" associated with many conventional image compression systems (such as JPEG) that use Discrete Cosine Transforms (DCT). Furthermore, the use of the biorthogonal lapped transform mitigates significant "ringing artifacts" as compared to conventional DCT-based image compression systems.
One particular aspect of the invention provides an image compression system having a color space mapper, a multi-resolution lapped transform, a quantizer, a scanner, and/or an entropy encoder. The multi-resolution lapped transform outputs transform coefficients, such as a first transform coefficient and a second transform coefficient. The multi-resolution representation may be obtained using second transform coefficients of the multi-resolution lapped transform. A color space mapper maps the input image onto a color space representation of the input image (e.g., YUV and/or YC)OCG). The color space representation of the input image is then provided to a multi-resolution lapped transform. The quantizer receives the first transform coefficient and/or the second transform coefficient and provides an output of the quantized coefficients for use by the scanner and/or the entropy encoder. A scanner scans the quantized coefficients to produce a one-dimensional vector for an entropy encoder. The scanner may utilize a Peano type scan command. The entropy encoder encodes the quantized coefficients received from the quantizer and/or scanner, ultimately resulting in data compression. The entropy encoder may utilize an adaptive run-length encoder.
Another aspect of the invention provides an image compression system having a color space mapper, a lossless transform, and an entropy encoder. The lossless transform receives input values from the color space mapper and utilizes a lossless transform (e.g., a hierarchical Hadamard transform).
Yet another aspect of the present invention provides an image decompression system having an entropy decoder, an inverse transform, and an inverse color space mapper. An entropy encoder receives a bitstream (e.g., produced by a corresponding entropy encoder) and decodes the bitstream. The entropy decoder may utilize an adaptive run-length decoder.
The inverse transform receives input values from the entropy decoder and utilizes an inverse transform (e.g., inverse layered overlapping biorthogonal or inverse layered hadamard). The inverse transform provides the output values to an inverse color space mapper. The inverse color space mapper converts the input values (e.g., YUV and/or YC)OCG) Mapping onto the RGB output image.
Another aspect of the present invention provides an image compression system that may be used in a wide array of document image applications including, but not limited to, segmented layered imaging systems, photocopiers, document scanners, optical character recognition systems, personal digital assistants, facsimile machines, digital cameras, digital camcorders, and/or video games.
Other aspects of the invention provide methods of data compression/encoding, data decompression/decoding, scanning chunk coefficients, color mapping, and inverse color mapping. Also provided are computer-readable media having computer-usable instructions for an image compression system and computer-readable media having computer-usable instructions for an image decompression system. There is still further provided a data packet adapted for transmission between two or more computer processes, the computer processes comprising information facilitating data compression, the information comprising first transform coefficients of an overlapping bi-orthogonal transform based at least in part on an input value and second transform coefficients of a hierarchical hadamard transform based at least in part on at least one first transform coefficient. There is further provided a data packet transmitted between two or more computer elements to facilitate data compression, comprising a data field containing a hierarchical hadamard transform based at least in part on an input value, and a second transform coefficient based at least in part on the hadamard transform of at least one first transform coefficient.
The implementation mode of the invention is as follows:
first, there is provided an image compression system including: receiving a first lapped biorthogonal transform of an input value, the first lapped biorthogonal transform providing an output comprising first transform coefficients, the first transform coefficients being based at least in part on the lapped biorthogonal transform of the input value; and receiving a second lapped biorthogonal transform of the at least one first transform coefficient from the first lapped biorthogonal transform, the second lapped biorthogonal transform providing an output comprising a second transform coefficient, the second transform coefficient based at least in part on the lapped biorthogonal transform of the at least one first transform coefficient.
Second, the present invention provides a photocopier using the above image compression system.
Third, the present invention provides a document scanner using the above image compression system.
Fourth, the present invention provides an optical characteristic recognition system using the above image compression system.
Fifth, the present invention provides a personal digital assistant using the above image compression system.
Sixth, the present invention provides a facsimile machine using the image compression system described above.
Seventh, the present invention provides a digital camera using the above image compression system.
Eighth, the present invention provides a digital video camera using the above image compression system.
Ninth, the present invention provides a segmented layered image system using the above image compression system.
Tenth, the present invention provides a video game machine using the above image compression system
Eleventh, the present invention provides an image compression system comprising: a color space mapper for mapping the input image to a color space representation; receiving a lossless transform of the input values from the color space mapper, the lossless transform providing an output comprising coefficients of the lossless transform, the lossless transform coefficients being based at least in part on a hierarchical hadamard transform of the input values; and an entropy encoder that digitally entropy encodes the lossless transformed coefficients.
Twelfth, an image decompression system of the present invention includes: an entropy decoder that digitally entropy-decodes an input bitstream; an inverse transform element that receives input values from the entropy decoder, the inverse transform element providing parameters that comprise an inverse transform that is based at least in part on an inverse hierarchical overlapping bi-orthogonal transform of the input values; and an inverse color space mapper that maps the output values from the inverse transform element to an RGB output image.
Thirteenth, the present invention provides an image decompression system comprising: an entropy decoder that digitally entropy-decodes an input bitstream; an inverse transform element that receives input values from the entropy decoder, the inverse transform element providing parameters that comprise an inverse transform, the inverse transformed parameters based at least in part on an inverse hierarchical hadamard transform of the input values; and an inverse color space mapper that maps the output values from the inverse transform element to an RGB output image.
Fourteenth, the present invention provides a method of image data compression/encoding, comprising: providing first transform coefficients of a bi-orthogonal lapped transform based at least in part on input values; and providing second transform coefficients based at least in part on a biorthogonal lapped transform of the first transform coefficients.
Fifteenth, the present invention provides a method of image data decompression/decoding, comprising: decoding the coefficients; providing second transform coefficients based at least in part on an inverse bi-orthogonal lapped transform of the decoded coefficients; and providing a first transform coefficient based at least in part on the second transform coefficient and an inverse biorthogonal lapped transform of the decoded coefficient.
Sixteenth, the present invention provides a method of image data compression/encoding, comprising: providing first transform coefficients of a hierarchical hadamard transform based at least in part on input values; and providing a second transform coefficient based at least in part on a hierarchical hadamard transform of the first transform coefficient.
Seventeenth, the present invention provides a method of image data decompression/decoding, comprising: decoding the coefficients; providing second transform coefficients based at least in part on an inverse hierarchical hadamard transform of the decoded coefficients; and providing a first transform coefficient based at least in part on the second transform coefficient and an inverse hierarchical hadamard transform of the decoded coefficient.
Eighteenth, the present invention provides a method of scanning quantized multi-resolution lapped transform coefficients of a block of data, comprising: scanning at least one second transform coefficient for each large packet in the chunk, wherein the second transform coefficient is based at least in part on the first transform coefficient; scanning the remaining second transform coefficients for the large packet; and scanning each packet within each large packet for a second group of first transform coefficients.
Nineteenth, the present invention provides an image compression system comprising: means for mapping the input image to a color space representation; means for performing a multi-resolution lapped transform of the color-space representation and providing first transform coefficients and second transform coefficients, wherein the second transform coefficients are based at least in part on the first transform coefficients; means for quantizing the first transform coefficient and the second transform coefficient; means for scanning the first transform coefficient and the second transform coefficient; means for entropy coding the first transform coefficient and the second transform coefficient digitally.
To the accomplishment of the foregoing and related ends, certain illustrative aspects of the invention are described herein in connection with the following description and the annexed drawings. These aspects are indicative, however, of but a few of the various ways in which the principles of the invention may be employed and the subject invention is intended to include all such aspects and their equivalents. Other advantages and novel features of the invention may become apparent from the following detailed description of the invention when considered in conjunction with the drawings.
(5) Detailed description of the preferred embodiments
The present invention is now described with reference to the drawings, wherein like reference numerals are used to refer to like elements throughout. In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the present invention. It may be evident, however, that the present invention may be practiced without these specific details. In other instances, well-known structures and devices are shown in block diagram form in order to facilitate describing the subject invention.
As used in this application, the term "computer element" is intended to refer to a computer-related entity, either hardware, a combination of hardware and software, or software in execution. For example, a computer element can be, but is not limited to being, a process running on a processor, an object, a command, a thread, a program, and/or a computer. By way of illustration, both an application running on a server and the server can be a computer element. There may be one or more computer elements residing within a process and/or thread of execution and an element may be located on one computer and/or distributed between two or more computers.
Referring to fig. 1, an image compression system 100 in accordance with an aspect of the present invention is illustrated. As described above, the system 100 of the present invention provides for improved performance and mitigation of packet artifacts and ringing artifacts through the use of multi-resolution lapped transforms 120 as compared to many conventional compression systems. The image compression system 100 includes a color space mapper 110, a multi-resolution lapped transform 120, a quantizer 130, a scanner 140, and an entropy encoder 150.
The color space mapper 110 maps the input image onto a color space representation of the input image. The color space representation of the input image is then provided to a multi-resolution lapped transform 120. In one example, the color space mapper 110 maps the input image onto a YUV representation (e.g., represented by red, green, and blue components) of an RGB input image. The YUV representation uses a luminance component indicated by Y, a red chrominance indicated by U, and a blue chrominance indicated by V.
In another example, the color space mapper 110 maps the input image to YCoCgShown above. The YCoCgIndicating use of luminance indicated by Y, indicated by CoOrange color number and CgGreen color of the representation. RGB input components are mapped to YC using the following transformationoCgAbove (e.g., as an alternative to conventional YUV described above):
notably, YCoCgOne advantage of color space mapping is that integer arithmetic can be used to achieve RGB to YCoCgMapping and slave YCoCgInverse transformation to RGB, thereby reducing computational overhead. Further, the inverse transform may be implemented without multiplication. YCoCgColor space representation may result in a significant improvement in compression performance over the popular YUV because it is a better approximation of the statistically optimal space obtained by principal component analysis of modern digital image data.
It is appreciated that many other color space representations related to the subject invention that facilitate data compression with multi-resolution lapped transforms are contemplated. Any suitable color space representation in relation to the present invention is intended to be within the scope of the appended claims. Furthermore, any suitable computer process may be performed with color space mapper 110 (e.g., integer and/or floating point) in accordance with the invention.
The multi-resolution lapped transform 120 receives input values, for example, from the color space mapper 110. The multi-resolution lapped transform 120 can allow the image compression system 100 to have an improved performance. The multi-resolution lapped transform 120 uses a bi-orthogonal transform that is layered lapped. By using lapped transforms, the "grouping artifacts" of conventional image compression systems (such as JPEG) using Discrete Cosine Transforms (DCT) can be reduced. Furthermore, the use of overlapping biorthogonal transforms reduces significant "ringing artifacts" compared to conventional DCT-based image compression systems.
Referring briefly to fig. 2, there is illustrated an overlapped bi-orthogonal transform (LBT)200 in accordance with an aspect of the present invention. The LBT 200 includes a first DCT-like transform 210 (e.g., similar to, but not identical to, a DCT) having four inputs x (0), x (1), x (2), and x (3) associated with a first set of data. The LBT 200 also contains a second DCT-like transform 210 having four inputs x (0), x (1), x (2), and x (3) associated with a second set of data. The LBT 200 has four outputs 230, X (0), X (1), X (2) and X (3). As illustrated in fig. 2, data is processed from left to right in direct transformations (e.g., data compression/encoding) and from right to left in inverse transformations (e.g., data decompression/decoding). The scaling factors of the direct (D) transform and the inverse (I) transform may be different.
To complete the overlapping portion of the transform, the output 230 of a set of data input into the second DCT-like transform 220 depends on the previous set of data input into the first DCT-like transform 210. The input values of the first DCT-like transform 210 cannot be fully determined in the absence of a previous set of data inputs (e.g., at initialization and/or at corners of the image). Especially if the first DCT-like transform 210 is the first of a row or column, x (0) and x (1) will exceed the image boundaries. In this case, an exemplary solution is to use even symmetric extensions by setting x (1) ═ x (2) and x (0) ═ x (3). A similar symmetric reflection is applied to the last DCT-like transform 210 of an image row or column. In both cases it can be easily seen that the first and last DCT-like transforms 210 of a row or column can be replaced by simple 2 x 2 operators (e.g., two distinct inputs, two distinct outputs).
In one example, substantially all computations within LBT 200 may be performed using unique integer operations without requiring multiplication. For example, for a given value z, a new value z/2 can be achieved with a right shift: z > 1. Furthermore, a value of 1.25z may be achieved by adding the right-shifted z twice and adding the value to z (e.g., z + (z > 2)). Although this implementation may result in small truncation errors resulting from the shift (as long as the data is properly scaled), it is worth noting that the implementation is generally processor independent, as the result remains the same regardless of the processor used to implement the transform. Thus, unlike conventional data compression systems such as JPEG, MPEG, and other standards, substantially all implementations of the systems and methods of the present invention can result in substantially similar compressed files for the same original image bitmap.
Referring briefly to fig. 3, a multi-resolution lapped transform 300 in accordance with an aspect of the present invention is illustrated. The multiresolution lapped transform 300 includes a first initial LBT 3101To the S initial LBT 310SAnd S is an integer greater than or equal to one. The first initial LBT 3101To the S initial LBT 310SMay be collectively referred to as initial LBT 310. The multi-resolution lapped transform 300 also includes a two-level LBT 320. For example, the multi-resolution lapped transform 120 may use the multi-resolution lapped transform 300.
Initial LBT 310 receives input values (e.g., from color space mapper 110). The initial LBT 310 processes the input value and outputs a first transform coefficient of an overlapping biorthogonal transform based at least in part on the input value. For example, the initial LBT 310 may use the exemplary LBT 200 set forth above.
First initial LBT 3101To the S initial LBT 310SIs provided as an input to the two-stage LBT 320. In one example, initial LBT 310 provides low frequency coefficients (e.g., DC) to secondary LBT 320. Secondary LBT 320 processes the first transform coefficient and outputs a second transform coefficient that is based at least in part on an overlapped biorthogonal transform of the input first transform coefficient. For example, secondary LBT 320 may use the exemplary LBT 200 set forth above.
A multi-resolution representation may be obtained with the second transform coefficients of the two-level lapped biorthogonal transform 320. For example, a bitmap reconstructed by applying only the inverse hierarchical LBT of the second level can recover an image bitmap representing the original in a 4 x downsampled form, which can be compared to the results produced by a conventional bi-cubic downsampling filter.
Referring briefly to fig. 4, a multi-resolution lapped transform 400 in accordance with an aspect of the present invention is illustrated. The transformation 400 includes a first initial LBT 4101Second initial LBT 4102Third initial LBT 4103Fourth initial LBT 4104And secondary LBT 420. First initial LBT 4101Second initial LBT 4102Third initial LBT 4103Fourth initial LBT 4104Is provided as an input to the two-stage LBT 420. For example, the multi-resolution lapped transform 120 may use the multi-resolution lapped transform 400.
Referring next to fig. 5, a multi-resolution lapped transform 500 in accordance with an aspect of the present invention is illustrated. The transform 500 includes an initial LBT 510 and a secondary LBT 520. The low frequency coefficient output of the initial LBT 510 is then provided to the secondary LBT 520. Once sufficient low frequency output is received from the initial LBT 510, the secondary LBT 520 provides a second transform coefficient output. For example, the multi-resolution lapped transform 120 may use the multi-resolution lapped transform 400.
For processing the image a two-dimensional transformation is used. To implement the two-dimensional transformation, the LBT discussed above may be applied to rows and columns of input values (e.g., Y, C received from color space mapper 110oAnd CgOf each of the). In one example, an entire column is not processed in order to reduce computational overhead, since each column access spans almost the entire bitmap array, which requires interrupting cached memory accesses. Alternatively, in accordance with the present invention, an internal "rolling buffer" approach may be used, where a partial column transform is performed after every four rows are processed. In this manner, the two-dimensional transformation can be computed by scanning the original bitmap only once.
Referring again to fig. 1, the quantizer 130 receives the first transform coefficient and/or the second transform coefficient and provides a quantized coefficient output for the scanner 140 and/or the entropy encoder 150. The quantizer 130 typically introduces a loss of information into the image compression system 100. This loss results from the quantization of the coefficients, since for the transformed value Y, its quantized version is typically represented by r-int [ (Y + f)/s]Given that where s is the step size of quantizer 130, | f | is generally equal to s/2 and sign (f) sign (y). Thus, as the step distance s increases, the corresponding dynamic range of r decreases to the point where r equals zero. During decompression (e.g., decoding), an approximation of Y is typically madeTo resume. Thus, the smaller the step s, the closer the approximation isAs stride increases, data compression is generally more efficient; however, also cause large losses. In one example, to reduce computational overhead, quantizer 130 uses integer arithmetic, e.g., scaling a value by an integer factor Z and approximating Z/s by an integer.
The scanner 140 scans the quantized coefficients to produce a one-dimensional vector for the entropy encoder 150. In one example, the scanner 140 uses line scanning, while in another example, the scanner 140 uses line scanning. In yet another example, the scanner 140 uses a sawtooth pattern, such as in a conventional JPEG data compression system.
In a fourth example, the quantized coefficients are scanned with a different, but still fixed (data independent) pattern (e.g., to avoid random data access). Referring briefly to fig. 6, a 4 by 4 coefficient grouping in accordance with an aspect of the present invention is illustrated. Referring next to fig. 7, a Peano-type scan pattern for a 16 by 16 data large packet (a group of L packets, where L is 4) is illustrated, in accordance with an aspect of the present invention. Fig. 8 illustrates a scan pattern of 4 by 4 groupings of second transform coefficients (such as those produced by the two-level lapped transform of 320,420, 520) in accordance with an aspect of the present invention.
For each large packet (e.g., resulting from a hierarchically concatenated 4 x 4 transform), the transform values are read into one of six coefficient groups. The continuous values of each group are read from M consecutive large packets ("chunks"), the six groups being concatenated as a 256M length vector that is sent to the entropy coder. Thus, each chunk can be encoded independently. Independent encoding allows each chunk to be decoded independently, allowing only a portion of the image bitmap to be decoded if desired.
The scanning patterns presented in fig. 7 and 8 are a combination of a scan of the DC coefficients for space-frequency ordering (e.g., subjected to two levels of LBT) and Peano plus a scan of the AC coefficients for space-frequency ordering (e.g., subjected to only the first level of LBT). A Peano element (shaded arrows in fig. 7) is used to bring each adjacent group of AC coefficients within a particular group from an adjacent 4 x 4 grouping.
Thus, group 0 contains a specific second stage DC coefficient that goes through the second stage LBT of each large group. Each large packet with a scan of group 1 through group 5 may then be scanned for group 1 through group 5, followed by a scan of group 1 through group 5 for the next large packet, and so on. For large packets, group 1 contains the remaining DC coefficients of the second stage LBT that go through the large packet. For each LBT packet of the large packet, group 2 contains the coefficient values described. For each LBT packet of the large packet, group 3 contains the coefficient values described. For each LBT packet of the large packet, group 4 contains the coefficient values described. For each LBT packet of the large packet, the group 5 contains the coefficient values mentioned.
Referring back to fig. 1, the entropy encoder 150 encodes the quantized coefficients received from the quantizer 130 and/or the scanner 140. The color space mapper 110, multi-resolution lapped transform 120, quantizer 130, and/or scanner 140 convert the raw pixel data into integer vectors with reduced dynamic range and long runs of zeros-despite no data compression. The entropy encoder 150 encodes these quantized coefficients, resulting in data compression.
In one example, encoder 150 uses an adaptive run-length encoder. Each bit-plane of the input vector is processed in order, starting with the Most Significant Bit (MSB) and ending with the least significant bit. For each coefficient, it is marked "valid" if no non-zero bits have been encoded, and "cleared" if the significant bits of the coefficient have been encoded. The clear bits are likely to be equal to zero or one, so they are copied unmodified to the bitstream. Significant bitMost likely equal to zero, so they are encoded by an adaptive and efficient run-length encoder, which produces symbols according to the rules described in table 1.
| Code word | Input bit sequence |
| 0 | 2KComplete operation of zeros |
| 1c0 | c＜2KA partial operation of zeros, followed by a 1, and the coincidence of the coefficients "+" (c is a number of k bits) |
| 1c1 | c＜2KA partial operation of zero followed by a 1, the coincidence of coefficients ═ c " |
Table 1: the run-length coding rule of the significant bits, with the parameter k.
The parameter k controls the compression efficiency of the run-length encoder. The larger the value of k, the longer the string of zeros that can be represented by a codeword containing a single bit 0 and thus the higher the degree of compression. The parameter k may be "tuned" to the statistics of the data such that 2KApproximately equal to the length of the string of zero characters.
In conventional run-length encoding, the parameter k may be either fixed or periodically updated and added to the bitstream (since the decoder needs to know any change in k). Although both methods result in significant performance loss for two reasons. First, the input data carries statistics that typically vary, so k needs to be changed to track these variations. Second, updating the value of k by copying it into the bitstream adds significant overhead, since several bits are required to represent the value of k. Therefore, the backward adaptation rule of k is used in the adaptive run-length encoder of this example. Backward means that k is adjusted according to the encoded symbol, not according to the input data. Therefore, the value of k need not be sent as long as the encoder and decoder use the same adaptation rules. The basic adaptation rules are simple. If the codeword is zero, which means that one run of zeros was just observed, more runs of zeros can be expected and k is thus increased. If the codeword starts with 1, which means that an incomplete run of zeros has just been observed, fewer runs of zeros can be expected and k is thereby reduced.
An increase of the integer within k would cause too fast adaptation, which leads to a loss of compression performance. Thus, k may be adjusted by a fractional value (e.g., by increasing or decreasing a proportional form of k).
The run-length encoded symbols may be terminated at the end of each bit-plane and a field containing the encoded data length of each bit-plane may be added. Thus, the bitstream can be parsed and the least significant bit planes can be eliminated, if desired. This is equivalent to re-encoding the data with half a stride. Thus, recompression of data can be accomplished by simply parsing out some bits from the compressed file. As such, scalability in fidelity may be achieved.
It will be appreciated that many other entropy encoding techniques (e.g., adaptive arithmetic coding) are contemplated that facilitate data compression using multi-resolution lapped transforms in connection with the subject invention. The use of any suitable entropy encoding technique in connection with the present invention is within the scope of the appended claims.
Although fig. 1 is a block diagram illustrating elements of an image compression system 100, as that term is defined herein, it is understood that the color space mapper 110, the multi-resolution lapped transform 120, the quantizer 130, the scanner 140, and/or the entropy encoder 150 may be implemented as one or more computer elements. Accordingly, computer-executable components operable to implement the image compression system 100, the color space mapper 110, the multi-resolution lapped transform 120, the quantizer 130, the scanner 140, and/or the entropy coder 150 may be stored on computer-readable media including, but not limited to, an ASIC (application specific integrated circuit), a CD (compact disc), a DVD (digital versatile disc), a ROM (read only memory), a floppy disk, a hard disk, an EEPROM (electrically erasable programmable read only memory), and a memory stick in accordance with the present invention.
Turning next to FIG. 9, a lossless image compression system 900 in accordance with an aspect of the present invention is illustrated. The image compression system 900 includes a color space mapper 110, a lossless transform 910, and an entropy encoder 150.
For example, lossless transform 910 receives input values from color space mapper 110. The lossless transform 910 uses a lossless transform. No lapped transform need be used for lossless coding because there are no grouping artifacts (because quantization is not involved). For example, the lossless transform 910 may use a hierarchical hadamard transform. Referring briefly to fig. 10, a hierarchical transform structure 1010 may be used, but the 4 x 4 transform module must be implemented by a lossless hadamard structure 1020. As the terms are defined herein, it is understood that the lossless transform 1010 may be implemented as one or more computer elements.
Turning to fig. 11, an image decompression system 1100 in accordance with an aspect of the present invention is illustrated. The system 1100 includes an entropy decoder 1110, an inverse scanner 1120, an inverse quantizer 1130, an inverse transform element 1140, and an inverse color space mapper 1150.
The entropy decoder 1110 receives and decodes a bitstream (e.g., produced by a corresponding entropy encoder). In one example, the entropy decoder 1110 uses an adaptive run-time decoder, which operates similarly to the decoder 150 described above.
The inverse scanner 1120 inversely scans the entropy-decoded input bitstream received from the entropy decoder 1110. Inverse scanner 1120 provides the quantized first transform coefficient and/or the quantized second transform coefficient to inverse quantizer 1130.
In one example, the inverse scanner 1120 uses a row-wise reverse scan, while in another example, the inverse scanner 1120 uses an inverse column-wise scan. In yet another example, the inverse scanner 1120 uses a sawtooth pattern, such as in a conventional JPEG data compression system. In a fourth example, the quantized coefficients are scanned with a different, but still fixed (data independent) pattern (e.g., to avoid random data access), such as an inverse Peano-type scanning pattern.
Inverse quantizer 1130 inverse quantizes the quantized first transform coefficient and/or the quantized second transform coefficient received from inverse scanner 1120. Inverse quantizer 1130 provides an unquantized coefficient output (e.g., a first transform coefficient and/or a second transform coefficient).
Inverse transform element 1140 receives the output values from inverse quantizer 1130. In one example, inverse transform element 1140 uses an inverse hierarchical lapped biorthogonal transform and provides output values to inverse color mapper 1150. For example, inverse transform element 1140 may use the inverse of the multi-resolution lapped transform of fig. 2 (e.g., from right to left). In another example, inverse transform element 1140 uses an inverse lossless transform (e.g., an inverse layered hadamard transform) to decode the image bitmap originally encoded by the lossless encoding system 900. For example, the inverse transform (e.g., lossless) can essentially reverse the computations in the lossless module 1020 (e.g., in reverse order).
Inverse color space mapper 1150 maps the input values to an RGB output image. In one example, an inverse color space mapper 1150 maps the YUV representation to an RGB output. In another example, inverse color space mapper 1150 passes YCoCgThe representation maps to an RGB output. It will be appreciated that many other color space representations are contemplated that facilitate data decompression using an inverse hierarchical biorthogonal lapped transform in connection with the subject invention. The use of any suitable color space representation in connection with the present invention is intended to be within the scope of the appended claims. In addition, an inverse color space mapper 1150 in accordance with the present invention (e.g.,integer and/or floating point) to implement any suitable computer process.
It is to be appreciated that the entropy encoder 1110, inverse scanner 1120, inverse quantizer 1130, inverse transform 1140, and/or inverse color space mapper 1150 can be computer elements.
In view of the exemplary systems shown and described above, methodologies that may be implemented in accordance with the present invention may be better appreciated with reference to the flow charts of fig. 12, 13, 14, 16, and 17. While, for purposes of simplicity of explanation, the methodologies are shown and described as sequential blocks, it is to be understood and appreciated that the present invention is not limited by the order of the blocks, as some blocks may, in accordance with the present invention, occur in different orders and/or concurrently with other blocks from that shown and described herein. Moreover, not all illustrated blocks may be required to implement a methodology in accordance with the present invention.
The invention may be described generally in terms of computer-executable instructions, such as program modules, executed by one or more components. Generally, program modules include routines, programs, objects, data structures, etc. that perform particular tasks or implement particular abstract data types. The functionality of the program modules may generally be combined or distributed as desired in various embodiments.
Turning to fig. 12, a method 1200 of data compression/encoding is illustrated in accordance with an aspect of the present invention. At 1210, per-packet transformation is performed for each large packet. In one example, a biorthogonal lapped transform (e.g., lossy mode) is used. In another example, a lossless hadamard transform is used (e.g., lossless hadamard structure 1020, lossless mode). At 1220, a transform is performed on the low frequency coefficients of the packet. In one example, a biorthogonal lapped transform (e.g., lossy mode) is used. In a second example, a lossless hadamard transform (e.g., lossless hadamard structure 1020, lossless mode) is used. Next, at 1230, the coefficients are quantized. At 1240, the coefficients are scanned. At 1250, the quantized coefficients are encoded.
Referring to fig. 13, a method 1300 of image decompression/decoding is illustrated in accordance with an aspect of the present invention. At 1310, the coefficients are decoded. At 1320, for each large packet, an inverse transform is performed on the low frequency coefficients of each packet. In one example, an inverse biorthogonal lapped transform (e.g., lossy mode) is used. In another example, an inverse lossless hadamard transform is used (e.g., lossless hadamard structure 1020, lossless mode). At 1330, an inverse transform is performed on the coefficients of each packet. In one example, an inverse biorthogonal lapped transform (e.g., lossy mode) is used. In a second example, an inverse lossless hadamard transform (e.g., lossless mode) is used.
Referring next to FIG. 14, a methodology 1400 for scanning chunk coefficients in accordance with an aspect of the present invention is illustrated. At 1410, one second order coefficient (e.g., DC element) of each large group in the chunk is scanned. Next, at 1420, for each large packet in the chunk, the remaining two-level coefficients of the large packet are scanned. At 1430, the group 2 level one coefficients (e.g., AC elements) for each of the large packets are scanned. At 1440, the group 3 level coefficients of each of the large packets are scanned. At 1450, the group 4 level coefficients for each of the large packets are scanned. At 1460, the group 5 level coefficients of each of the large packets are scanned. If there are large packets in the chunk that have not been scanned, scanning continues at 1420. Six transform coefficient groups (groups 0 to 5) are generated in the exemplary scanning method just described. While such scanning and grouping schemes are believed to produce good compression results, any other suitable scanning and grouping pattern may be used, for example, if compression performance can be sacrificed for faster processing. The use of any such scanning/grouping patterns in connection with the present invention is within the scope of the appended claims.
Turning to fig. 15, a forward mapper element 1510 (e.g., used by the color mapper 110) is illustrated. The forward mapper element 1510 provides the mapping to spatial YCOCGThe original RGB input components (e.g., in a scaled version of equation (1)). This scaling is divided by 2 (indicated by the arrow labeled 1/2) and can be accomplished by the right shift described previously. Initially, these wereErrors resulting from the shift may appear unrecoverable. However, in the reverse mapper element 1520, the output of the forward mapper element 1510 is applied in reverse order, so that truncation by shifting occurs (e.g., the same as within the forward mapper element 1510), but now their effect is mitigated (indicated by the arrow labeled-1/2), allowing recovery of the original data. Thus, the inverse mapper element 1520 may be selected from YCOCGThe components restore the original RGB input components (e.g., exactly).
Referring next to fig. 16, a method 1600 of color space mapping is illustrated. For example, the forward mapper element 1510 may use the method 1600.
An RGB input (containing R, G, and B components) is received at 1610. A Y-channel output containing an average light intensity (luminance) representation of the RGB input is provided 1620. The Y channel may be provided according to transformation (1) above (e.g., Y is at least partially according to R +2G + B). In one example, the Y channel may be provided with information relating to the RGB input in increments and/or shifts- -without multiplication.
At 1630, a near orange directional C is provided that contains the color information representation (chromaticity) of the RGB inputoAnd (6) outputting the channel. The C may be provided according to the above transformation (1)oChannel (e.g., C)oAt least in part according to 2R-2B). In one example, the C may be provided in increments and/or shifts of information related to RGB inputoChannel-no multiplication is required.
Providing C in the near green direction at 1640 containing a color information representation (chroma) of the RGB inputgAnd (6) outputting the channel. The C may be provided according to the above transformation (1)gChannel (e.g., C)gAt least in part according to-R + 2G-B). In one example, the C may be provided in increments and/or shifts of information related to RGB inputgChannel-no multiplication is required.
In another example, YC provided according to method 1600 can be usedoCgInverse mapping of the channelRecovering the R component, G component and/or B component.
Referring next to fig. 17, a method 1700 of inverse color space mapping is illustrated. For example, the inverse mapper element 1520 may use the method 1700.
At 1710, YC is receivedoCgAn input containing a Y-channel representing average light intensity, color information representing a nearby orange direction, and color information representing a nearby green direction. Providing at 1720 a signal based at least in part on the YCoCgThe input R component. The R component may be provided according to transformation (1) above (e.g., R is at least partially according to Y + Co-Cg). In one example, YC may be usedoCgThe relevant information increments and/or shifts are entered to provide the R component-no multiplication is required.
Providing, at 1730, a signal based at least in part on the YCoCgThe input G component. The G component may be provided according to transformation (1) above (e.g., G is at least partially according to Y + Cg). In one example, YC may be usedoCgThe relevant information is entered in increments and/or shifts to provide the G component-no multiplication is required.
Providing at 1740 a signal based at least in part on the YCoCgAnd inputting the component B. The B component may be provided according to transformation (1) above (e.g., B is at least partially according to Y + Co-Cg). In one example, YC may be usedoCgThe relevant information increment and/or shift is entered to provide the B component-no multiplication is required.
It will be appreciated that the system and/or method of the present invention may be used in an overall compression system that facilitates the compression of text, scripts, drawings, pictures, and the like. Further, those skilled in the art will recognize that the system and/or method of the present invention may be used in an array of a large number of document image applications, including, but not limited to, photocopiers, document scanners, light characterization systems, PDAs, facsimile machines, digital cameras, digital video cameras, and/or video games.
In order to provide additional context for various aspects of the present invention, FIG. 18 and the following discussion provide a brief, general description of a suitable operating environment 1810 in which the various aspects of the present invention can be implemented. FIG. 19 provides an additional and/or alternative operating environment in which the present invention can operate. While the invention is generally described in the context of computer-executable instructions, such as program modules, executed by one or more elements, those skilled in the art will recognize that the invention also can be implemented in combination with other program modules and/or as a combination of hardware and software. Generally, however, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular data types. Operating environment 1810 is only one example of a suitable operating environment and is not intended to suggest any limitation as to the scope of use or functionality of the invention. Other well known computer systems, environments, and/or configurations that may be suitable for use with the invention include, but are not limited to, personal computers, hand-held or portable devices, multiprocessor systems, microprocessor-based systems, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include the above systems or devices, and the like.
With reference to FIG. 18, an exemplary environment 1810 for implementing various aspects of the invention includes a computer 1812. The computer 1812 includes a processor unit 1814, a system memory 1816, and a system bus 1818. The system bus 1818 couples system components including, but not limited to, the system memory 1816 to the processing unit 1814. The processing unit 1814 may be any of various available processors. Dual microprocessors and other multiprocessor architectures also can be employed as the processing unit 1814.
The system bus 1818 can be any of several types of bus structures including the memory bus or memory controller, a peripheral bus or external bus, and/or a local bus using a variety of available bus architectures including, but not limited to, 18-bit bus, Industrial Standard Architecture (ISA), micro-channel architecture (MSA), Extended Industry Standard Architecture (EISA), intelligent drive circuit (IDE), VESA Local Bus (VLB), Peripheral Component Interconnect (PCI), universal serial bus architecture (USB), ] Accelerated Graphics Port (AGP), personal computer memory card international association bus (PCMCIA), and Small Computer Systems Interface (SCSI).
The system memory 1816 includes volatile memory 1820 and nonvolatile memory 1822. The basic input/output system (BIOS), containing the basic routines to transfer information between elements within the computer 1812, such as during start-up, is stored in nonvolatile memory 1822. By way of illustration, and not limitation, nonvolatile memory 1822 can include Read Only Memory (ROM), programmable ROM (prom), electrically programmable ROM (eprom), electrically erasable ROM (eeprom), or transitory memory. Volatile memory 1820 includes Random Access Memory (RAM), which acts as external cache memory. By way of illustration and not limitation, RAM is effective in many forms, such as Synchronous RAM (SRAM), Dynamic RAM (DRAM), Synchronous DRAM (SDRAM), double data rate SDRAM (DDR SDRAM), Enhanced SDRAM (ESDRAM), Synchlink DRAM (SLDRAM), and direct bus RAM (DRRAM).
The computer 1812 also includes removable/non-removable, volatile/nonvolatile computer storage media. FIG. 18 illustrates an example of a disk storage 1824. Disk storage 1824 includes, but is not limited to, devices like a magnetic disk drive, floppy disk drive, tape drive, Jazz drive, Zip drive, LS-100 drive, flash memory card, or memory stick. In addition, disk storage 1824 can include storage media separately or in combination with other storage media including, but not limited to, an optical disk drive such as a compact disk ROM device (CD-ROM), CD recordable drive (CD-R drive), CD rewritable drive (CD-RW drive) or a digital versatile disk ROM drive (DVD-ROM). To facilitate connection of the disk storage devices 1824 to the system bus 1818, a removable or non-removable interface is typically used such as interface 1826.
It is to be appreciated that the software described in FIG. 18 may be used as an intermediary between users and the basic computer resources described in suitable operating environment 1810. Such software includes an operating system 1828. Operating system 1828, which can be stored on disk storage 1824, acts to control and allocate resources of the computer system 1812. System applications 1830 take advantage of the management of resources by operating system 1828 through program modules 1832 and program data 1834 stored either in system memory 1816 or on disk storage 1824. It is to be appreciated that the subject invention can be implemented with various operating systems or combinations of operating systems.
A user enters commands or information into the computer 1812 through input device(s) 1836. Input devices 1836 include, but are not limited to, a pointing device such as a mouse, trackball, stylus, touch pad, keyboard, microphone, joystick, game pad, satellite dish, scanner, TV converter card, digital camera, digital video camera, web camera, and the like. These and other input devices connect to the processing unit 1816 through the system bus 1818 via interface port(s) 1838. Interface port(s) 1838 include, for example, a serial port, a parallel port, a game port, and a Universal Serial Bus (USB). The output device 1840 uses some of the same ports as the input device 1836. Thus, for example, a USB port may be used to provide input to computer 1812, and to output information from computer 1812 to an output device 1840. Output adapter 1842 is provided to illustrate that there are some output devices 1840 that require special adapters, such as monitors, speakers, and printers among other output devices 1840. The output adapters 1842 include, by way of illustration and not limitation, video and sound cards that provide a means of connection between the output device 1840 and the system bus 1818. Notably, other devices and/or systems of devices provide both input and output capabilities such as remote computer 1844.
The computer 1812 may operate in a networked environment using remote computers 1844. It uses logical connections to one or more remote computers. The remote computer(s) 1844 can be a personal computer, a server, a router, a network PC, a workstation, an application based microprocessor, a peer device or other common network node and the like, and typically includes many or all of the elements described relative to the computer 1812. For purposes of brevity, only a memory storage device 1846 of remote computer(s) 1844 is illustrated. Remote computer(s) 1844 is logically connected to computer 1812 through a network interface 1848 and then physically connected via communication connection 1850. Network interface 1848 encompasses communication networks such as local-area networks (LAN) and wide-area networks (WAN). LAN technologies include Fiber Distributed Data Interface (FDDI), Copper Distributed Data Interface (CDDI), Ethernet/IEEE 1502.3, token Ring/IEEE 1502.5, and the like. WAN technologies include, but are not limited to, point-to-point links, circuit-switched networks like Integrated Services Digital Networks (ISDN) and variations thereon, packet-switched networks, and Digital Subscriber Lines (DSL).
Communication connection(s) 1850 refers to the hardware/software employed to connect the network interface 1848 to the bus 1818. While communication connection 1850 is shown for illustrative clarity inside computer 1812, it can also be external to computer 1812. The hardware/software necessary for connection to the network interface 1848 includes, for exemplary purposes only, internal and external technologies such as DSL modems, ISDN adapters, and ethernet cards, including regular telephone grade modems, cable modems and DSL modems.
FIG. 19 is a functional block diagram of an exemplary computing environment 1900 with which the present invention can interact. The system 1900 includes one or more client(s) 1910. The client(s) 1910 can be hardware and/or software (e.g., threads, processes, computing devices). The system 1900 also includes one or more server(s) 1930. The server(s) 1930 can also be hardware and/or software (e.g., threads, processes, computing devices). The server 1930 can perform the conversion by favoring threads using the present invention, for example. One possible communication between a client 1910 and a server 1930 can be in the form of a data packet adapted to be transmitted between two or more computer processes. The system 1900 includes a communications framework 1950 that can be employed to facilitate communications between the client(s) 1910 and the server(s) 1930. The client(s) 1910 are operatively connected to one or more client data store(s) 1960, which data store(s) 1960 can be employed to store information to local client(s) 1910. Likewise, the server(s) 1930 are operatively connected to one or more server data store(s) 1940, which server data store(s) 1940 can be employed to store information to local servers 1930.
The above description includes examples of the present invention. It is, of course, not possible to describe every conceivable combination of components or methodologies for purposes of describing the present invention, but one of ordinary skill in the art may recognize that many further combinations and permutations of the present invention are possible. Accordingly, the present invention is intended to embrace all such alternatives, modifications and variances which fall within the spirit and scope of the appended claims. Furthermore, to the extent that the term "includes" is used in either the detailed description or the claims, it is intended to be inclusive in a manner similar to the term "comprising" as "comprising" is interpreted when employed as a transitional word in a claim.