1. Field of the Invention
The present invention relates to technology for decoding image data that has been encoded in units of blocks.
2. Description of the Related Art
Many digital cameras that have become widely used in recent years employ JPEG as technology for performing compression-coding on still images that have been captured.
The following is a brief description of JPEG encoding technology. First, image data that is to be encoded is divided into units of blocks that are each 8×8 pixels. Discrete cosine transformation (DCT) is then performed on the blocks to generate transform coefficient blocks. Thereafter, transform coefficients in the transform coefficient blocks are quantized. The post-quantization transform coefficients are then scanned in a given order, and encoding is performed by assigning variable length code to pairs of the number of transform coefficients that are a series of zeroes and a transform coefficient that is a value other than zero. This processing is executed for each block, thus generating JPEG encoded image data (hereinafter, called “JPEG image data”).
When decoding JPEG image data, there are cases in which there is a desire to rotate the image by a predetermined angle. For example, in an imaging device included in a digital camera, the number of pixels in the horizontal direction is generally higher than the number of pixels in the vertical direction, and in JPEG encoding processing, raster scanning is performed in units of 8×8-pixel blocks before encoding. However, in a case of printing using a printer, the recordable width is the short side of the largest recordable recording sheet in order to prevent an increase in the size of the apparatus (to reduce cost). In other words, in a case of printing using a printer, JPEG image data that has been captured by a digital camera is rotated 90 degrees before print processing is performed thereon. Alternatively, depending on the margin (cutoff line) setting of the recording sheet, the JPEG image data may be output in a 180-degree or 270-degree rotated condition.
One easily conceivable method for meeting such a demand involves first decoding all of the targeted JPEG image data, and then performing rotating processing for rotating the image by a predetermined angle.
However, this method is problematic due to not only requiring a high-capacity memory for temporarily holding the entirety of the decoded image, but also due to the fact that there is an increase in the time required to perform the rotating processing since the rotating processing is performed on a large amount of image data.
Japanese Patent Laid-Open No. 2001-86318 is an example of a document disclosing technology for solving such problems.
According to this document, provisional decoding processing is first performed on encoded image data in order from the beginning, and a table holding decoding information necessary for decoding a predetermined origin block in the original image (hereinafter, called the “decoding table”) is generated. Thereafter, the encoded image data is decoded from the origin block using the decoding table, and the decoded image data is rotated by a predetermined angle and output to an image buffer. By performing the above processing, the original image is rotated by a predetermined angle, and in this condition, the image data can be decoded in order beginning with a block positioned at the head of the recording sheet feed, and the result of such decoding can be output.
The decoding information necessary to decode the predetermined origin block is a file pointer indicating the origin block and a prediction value that is necessary to decode the origin block. In the JPEG encoding scheme, the prediction value that is necessary is the DC component value of a block positioned immediately before the origin block.
In general, code called RST markers used in recovery from data errors and EOI markers indicating the end of encoded image data are appended to encoded image data typified by, for example, the JPEG encoding scheme. Note that in the following description, such code is called “marker code”.
Marker code is inserted at byte boundaries in encoded image data. Also, in order to prevent the emulation of marker code, predetermined byte values are inserted in encoded data strings expressing image data. For example, in the JPEG encoding scheme, the marker code is code that begins with “0xFF” (“0x” indicates hexadecimal notation). The RST marker code is “0xFFD0” to “0xFFD7”, and the EOI marker code is “0xFFD9”. If “0xFF” appears at a byte boundary in a data string expressing image data, “0x00” is inserted after “0xFF” in order to prevent emulation of such a marker code. Note that in the following description, “0x00” that is inserted after “0xFF” is called an “emulation prevention byte”.
A specific method for processing emulation prevention bytes is not clear in conventional technology. For example, consider the case of a JPEG image that, as shown in FIG. 4A, has been divided into four pixel blocks in the horizontal direction and three pixel blocks in the vertical direction (each block including 8×8 pixels). The numerals noted in the sections in FIG. 4A indicate the order in which the pixel blocks were encoded. In the JPEG image shown in FIG. 4A, if the width of the area to be output is set to a unit of two blocks in the horizontal direction, it is necessary to obtain the positions (file pointers) indicated by “0” to “e” in FIG. 4B. In other words, it is necessary to create the decoding table shown in FIG. 4C.
However, if positions (“b” and “e” in FIG. 5B) immediately before emulation prevention bytes are set, “0xFF” is not input to an image decoding apparatus, and “0x00” is set as the encoded image data start point corresponding to the origin block. In this case, the image decoding apparatus cannot determine whether “0x00” that has been input is an emulation prevention byte or a code word.
However, a specific solution for setting the positions indicated by “a” to “e” in FIG. 4B as file pointers indicating origin blocks is not disclosed in conventional technology.
Consider a case of processing emulation prevention bytes with use of an image decoding apparatus having the structure shown in FIG. 14. In FIG. 14, reference numeral 401 denotes an encoded image data input unit that inputs encoded data in bit order. Reference numeral 402 denotes a shifter that cues encoded image data. Reference numeral 403 denotes a 00 determination unit that determines whether an emulation prevention byte exists. Reference numeral 404 denotes a code table for performing decoding and outputting a code word length. Reference numeral 405 denotes a counter that counts the number of decoded transform coefficients and determines whether the end of a block has been decoded. Reference numeral 406 denotes a code length accumulation unit that accumulates code lengths from the code table.
In order to set file pointers at the positions indicated by “0” to “e” in FIG. 4B, first the counter 405 determines whether the end of a block has been decoded. It is necessary for the 00 determination unit 403 to determine whether an emulation prevention byte exists immediately after the code word at the end of the block, and for the shifter 402 to cue the encoded image data based on the determination result. According to this structure, in the case of implementation in an LSI, the critical path becomes too long, and high-speed operation at a high frequency becomes difficult, which is a problem.
A specific method for processing marker code is not clear in conventional technology. Consider a case in which file pointers for encoded image data shown in FIG. 11A are set as shown in FIG. 11B, and therefore the file pointers positioned immediately before marker code is registered in a decoding table as shown in FIG. 11C. If the blocks positioned immediately after the marker code “0xFFD1” and “0xFFD3” (block (7) and block (13) in FIG. 11A) are set as origins and decoding is performed in parts, the marker code is decoded again, thereby leading to an increase in the decoding processing time.
USPTO Backgrounds
USPTO Backgrounds