JP2008099134A - Data decoding apparatus and program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To facilitate parallel decoding processing on variable-length coded data. <P>SOLUTION: One code data 100 is divided into two parts and decoded in parallel by two decoders. The first decoder starts decoding from the top of the code data 100. The second decoder starts decoding from a starting point A1 in the middle of the code data 100. If decoding is failed, decoding is started again from other starting points A2, A3, .... Thus, a starting point A5 when the second decoder completes decoding to the end of the code data 100 without fail, is reported to the first decoder as a successful point. The first decoder performs decoding to successful point A5. Decoding results of the first decoder and the second decoder are then combined to obtain a decoding result corresponding to the overall code data. <P>COPYRIGHT: (C)2008,JPO&INPIT

Description

  The present invention relates to decoding of variable length encoded data.

  A variable-length encoding technique is often used for an image encoding method such as JPEG (Joint Photographic Experts Group). In variable-length coding, a code data file is configured by assembling codewords having different bit lengths. Therefore, in order to correctly extract the information of the Nth code word, it is necessary to sequentially interpret the first to (N−1) th code words. For this reason, in decoding of code data generated by variable-length coding, it is common to sequentially decode from the first code word. If it says from another angle, it can be said that the random access of the code data by which variable-length encoding was carried out is difficult in principle. Since random access is difficult, it is also difficult to divide code data into a plurality of pieces and decode them in parallel.

  In the method shown in Patent Document 1, one page of compressed image data composed of M (horizontal direction) × N (vertical direction) compressed packets is stored in each of the four MCUs in the horizontal direction constituting each compressed packet. A data block in which “MCU group G (n)” in which a restart marker or an EOI marker is added to a block (ECS, entropy-coded segment) of a bit stream in which a line (row) is Huffman encoded is arranged as a unit The number of vertical pixels (8 pixels) of one MCU is continuously arranged for 4N lines as one line. This facilitates parallel processing. However, since this data format is not a standard JPEG format, it cannot be decoded unless it is a decoder adapted to this method.

  The image processing apparatus disclosed in Patent Document 2 receives one page of JPEG compressed image data in which a restart marker is inserted for each block of a minimum coding unit (MCU). For the input image data, a group consisting of a minimum coding units and inserted restart markers is taken as one block, and the image packets are rearranged in units of the compressed blocks. 1 page image is reconstructed into a collection of M image packets in the horizontal direction and N in the vertical direction. Thereafter, parallel image processing is performed as an image packet. However, since this data format is not a standard JPEG format, it cannot be decoded unless it is a decoder adapted to this method.

JP 2003-189109 A JP 2003-348355 A

  Although the above prior art has been related to image coding, the problem of difficulty in parallelizing decoding processing generally applies to data coding techniques including variable length coding.

  The present invention enables or facilitates parallelization of decoding processes in a system using a variable-length coding technique.

  (1) In one aspect of the present invention, the first decoding unit that performs decoding from the first start point that is the head of the code data to be decoded, and the k-th provided for each integer k that is greater than or equal to 2 and less than or equal to N A decoding unit that attempts decoding from the k-th start point located after the (k-1) start point in the middle of the code data, and if the decoding fails, the position of the k-th start point is changed The (k-1) th decoding is performed with the kth decoding unit that tries decoding again and the Nth starting point when the Nth decoding unit finishes decoding without failing to the end of the code data. When the (k-1) th starting point when the part finishes decoding without failing to the kth successful point is the (k-1) th successful point, the code for each k of 2 or more and N or less The (k-1) th decoding part of the data from the (k-1) th success point to the k th success point A decoding result generation unit that generates a decoding result corresponding to the entire code data based on the result of the signal and the decoding result of the N-th decoding unit for the portion from the Nth success point to the end of the code data; A data decoding apparatus comprising:

  (2) In one aspect, in the above configuration (1), each of the decoding units performs Huffman decoding in JPEG decoding, and each of the decoding units from the second decoding unit to the N-th decoding unit includes: When the quantized DCT coefficient obtained by Huffman decoding overflows a block defined by JPEG, it is determined that decoding has failed.

  (3) In another aspect, in the configuration (1), each decoding unit performs Huffman decoding in JPEG decoding, and each decoding unit from the second decoding unit to the N-th decoding unit includes: If Huffman decoding is performed according to a code allocation rule including a code bit string for failure detection that is not associated with a quantized DCT coefficient, and the code bit string for failure detection included in the code allocation rule is detected, decoding fails. It is determined that

  (4) In still another aspect, in the configuration (1), each of the decoding units performs Huffman decoding in JPEG decoding, and the i-th decoding unit (i is 1 or more and (N−1) or less). DC component correction unit that corrects the decoding result of the (i + 1) -th decoding unit based on the DC component of the last block obtained when decoding from the i-th success point to the (i + 1) -th success point Are further provided.

  (5) In still another aspect, in the configuration (1), when the decoding fails, the k-th decoding unit (k is an integer not less than 2 and not more than N) sets a position next to the failed position as a new position. Decoding continues with k starting point.

  (6) In another aspect of the present invention, the first decoding unit that performs decoding from the beginning of the code data to be decoded and the decoding is attempted from a starting point in the middle of the code data, and starts when decoding fails A second decoding unit that tries decoding again by changing the position of the point, and when the second decoding unit finishes decoding without failure to the end of the code data as a success point, The code data based on the decoding result of the first decoding unit for the part from the beginning of the code data to the success point and the decoding result of the second decoding unit for the part from the success point to the end of the code data There is provided a data decoding device including a decoding result generation unit that generates an entire decoding result.

  (7) In another aspect of the present invention, the first decoding unit executes decoding from the first start point that is the head of the code data to be decoded, and the first decoding unit is provided for each integer k of 2 or more and N or less. The k decoding unit is caused to try decoding from the kth start point located after the (k−1) th start point in the middle of the code data, detects a decoding failure of the kth decoding unit, and the kth decoding unit When the decoding failure is detected, the position of the kth starting point is changed and the kth decoding unit tries again, and the Nth decoding unit finishes decoding without failing to the end of the code data. The (k-1) th starting point when the Nth starting point is the Nth successful point and the (k-1) th decoding unit finishes decoding without failing to the kth successful point is the (k-1) th. In the case of success points, for each k of 2 to N, the kth component from the (k-1) th success point of the code data. The code data based on the decoding result of the (k−1) th decoding unit for the part up to the point and the decoding result of the Nth decoding unit for the part from the Nth successful point to the end of the code data A program for generating a decoding result corresponding to the whole and causing a computer to execute processing is provided.

  (8) In another aspect of the present invention, the first decoding unit is caused to perform decoding from the beginning of the code data to be decoded, and the second decoding unit is caused to try decoding from a starting point in the middle of the code data, When the decoding failure of the second decoding unit is detected, and when the decoding failure of the second decoding unit is detected, the position of the start point is changed and the second decoding unit tries again, and the second decoding unit The decoding result of the first decoding unit for the portion from the beginning of the code data to the success point when the start point of the trial when the decoding is completed without failure to the end of the code data, A program for causing a computer to execute a process for generating a decoding result of the entire code data based on the decoding result of the second decoding unit from the success point to the end of the code data is provided.

  According to the above configuration (1) or (7), variable-length encoded code data can be decoded at high speed by parallel decoding by N decoding units.

  According to the configuration (2), it is possible to easily detect a decoding failure using the properties of JPEG.

  According to the configuration (3), the possibility of detecting a decoding failure can be increased by using the failure detection code.

  According to the configuration (4), it is possible to correct the DC component in the decoding result of each decoding unit after the second decoding unit.

  According to the configuration (5), when decoding fails, decoding can be continued without changing the position to be decoded.

  According to the above configuration (6) or (8), variable-length-coded code data can be decoded at high speed by parallel decoding by two decoding units.

  Embodiments of the present invention will be described below with reference to the drawings. In the drawings, the same or similar components are denoted by the same reference numerals, and redundant description is omitted.

  In the following, description will be made by taking the decoding of an image compressed and encoded by the JPEG method as an example. However, as can be understood by those skilled in the art from the following description, the method of the present embodiment is not limited to the JPEG method, but can be applied to code data generally encoded by an encoding method including variable length encoding. Further, the present invention can be applied not only to images but also to other types of data.

  First, with reference to FIG. 1, the principle of the parallel decoding implementation method in this embodiment will be described. FIG. 1 shows an example in which code data 100 is decoded in parallel by two decoding units. In the present embodiment, the first decoding unit of the two decoding units starts decoding from the beginning of the code data 100, and the other second decoding unit starts from the start point A1 selected from the middle of the code data 100. Start decryption. Since the first decoding unit performs decoding from the top of the code data 100, in principle, decoding can proceed correctly. On the other hand, since the second decoding unit starts decoding from the starting point in the middle of the code data, the decoding is not always successful and generally fails. This is because of the following.

  That is, for example, when an adjacent MCU (Minimum Coded Unit. For example, when sub-sampling a full color image with Y (luminance): Cb (color difference): Cr (color difference) = 4: 1: 1, the MCU is an area of 16 pixels × 16 pixels. The second decoding unit 12-2 can also correctly proceed decoding from a starting point that satisfies a specific condition, such as a position on the code data 100 corresponding to the boundary position between the starting points. On the other hand, in the present embodiment, since the position on the code data 100 that satisfies such a condition is not given as prior knowledge, such an appropriate starting point cannot be determined. Since it has been decrypted, there is a high possibility that the decryption will eventually fail.

  The decoding failure in the second decoding unit can be detected by several methods described in detail later. Although it is not an appropriate starting point, a pattern that coincides with the correct code sequence from that starting point may accidentally continue for some time, and decoding failure cannot be detected while such a pattern continues. However, such a coincidence does not continue for a long time, and if the starting point is not appropriate, failure will be detected as the decoding progresses to thousands, tens of thousands, and millions of bits.

  When the decoding failure is detected in this way, the second decoding unit moves the position of the start point to a new position and tries decoding again from the new position.

  However, for the same reason as described above, decoding does not always succeed even if the decoding is started from the moved new starting point. If it fails, the start point is moved again and decoding is attempted from the new start point. By repeating the trial while changing the starting point in this way, an appropriate starting point is eventually found, and decoding can be completed without failure to the end of the code data. In the present embodiment, when the decoding of the second decoding unit is completed without detecting a failure from the certain starting point to the end of the encoded data 100, it is determined that the decoding of the second decoding unit is successful.

  If the decoding fails, the start point may be moved by, for example, a method of selecting a new start point one bit after the previous start point on the code data. Thus, instead of moving the starting point backward, the starting point may be moved forward. The amount of movement is not limited to 1 bit, and may be 2 bits or more, and the amount of movement may be changed for each movement. If it is a boundary between adjacent MCUs, it can be found by trial within the number of bits of the code corresponding to the MCU if it is moved bit by bit in a certain direction.

  As another method, a method of selecting the next bit at the position of the code data when a failure is detected as a new start point can be used. In the above method, when decoding fails, it is necessary to return to the vicinity of the previous start point, and a jump of the decoding position occurs. However, in this method, even if decoding fails, it is sufficient to simply proceed with decoding, and simply record It only changes the position of the starting point. Even with this method, it is possible to find an appropriate starting point that can be decoded without failure to the end as the decoding progresses to thousands or tens of thousands of bits.

  The example of FIG. 1 shows an example in which the latter method is used. In this example, no failure is detected at the beginning when the second decoding unit starts decoding from the first start point A1, but a decoding failure is detected when the decoding reaches A2. At this time, the second decoding unit tries decoding again with the next bit at the position where the failure is detected as a new start point, but in the example of FIG. 1, this attempt fails immediately. In this example, A2 to A3 are a range 110 where a decoding failure is detected. When the second decoding unit repeats the decoding trial and the starting point reaches A3, the failure is not detected again, but the failure is detected again thereafter. Finally, after the start point reaches A5, decoding is completed up to the end of the code data 100 without detecting failure. Thus, in the example of FIG. 1, the decoding of the second decoding unit finally succeeds in the trial from the start point A5.

  In the present embodiment, the starting point when the decoding of the second decoding unit is successful is set as the “success point”, and the first decoding unit that decodes from the top of the code data 100 performs the decoding up to this success point. Make it. Since the first decoding unit decodes from the top, this decoding is successful.

  Then, the decoding apparatus according to the present embodiment decodes the decoding result of the first decoding unit for the part from the beginning of the code data 100 to the success point (A5 in FIG. 1) and the second decoding for the part from the success point to the end. The decoding result for the entire code data 100 is obtained by combining the decoding results of the units.

  As described above, in the present embodiment, the second decoding unit in charge of decoding the second half of the code data finds a success point that can be decoded without failure to the end of the code data by trial and error, and the first half is decoded. The decoding unit is made to perform decoding from the head of the code data to the success point. And the decoding result corresponding to the whole code data is calculated | required by combining the decoding result of both these decoding parts. According to such a mechanism, parallel decoding by two decoding units can be realized without prior knowledge about the code data 100.

  An image decoding apparatus according to an embodiment that implements the above mechanism will be described with reference to FIG. The code file 10 decoded by this apparatus does not need to include special information for parallel decoding, and is generated by encoding image data with a general encoding apparatus compliant with the JPEG method. A typical JFIF or Exif file. The code file 10 includes code data obtained by encoding image data and information on encoding parameters such as a Huffman table used for the encoding. At the time of decoding, the code file 10 is loaded on a memory included in the image decoding device.

  The image decoding apparatus illustrated in FIG. 2 includes two decoding units, a first decoding unit 12-1 and a second decoding unit 12-2. Hereinafter, when it is not necessary to distinguish between them, both are collectively referred to as a decoding unit 12. The decoding unit 12 performs JPEG decoding processing.

  As is well known, in JPEG encoding, when target image data is divided into MCUs and a sub-sampling ratio is specified for the color difference component, the color difference component of the pixel group included in the MCU is determined as the ratio. Subsample with. Then, from the MCU, a block of 8 pixels × 8 pixels is configured for the luminance component and each color difference component. Then, discrete cosine transform (DCT) is performed for each block, each obtained DCT coefficient is quantized, and the obtained quantized DCT coefficient is subjected to Huffman coding which is a kind of variable length coding. Obtain code data. In JPEG decoding, the reverse process of the encoding is performed. That is, Huffman decoding is performed on the code data, the resulting quantized DCT coefficient is inversely quantized, and the inversely quantized result is inversely DCT transformed to reproduce the original image data.

  The decoding unit 12 is a module that executes at least Huffman decoding in such JPEG decoding processing. The decoding unit 12 can be realized by causing a processor to execute a program for decoding, or can be realized as a hardware circuit.

  The first result storage unit 14-1 and the second result storage unit 14-2 store the image data of the decoding results of the first decoding unit 12-1 and the second decoding unit 12-2, respectively. The first result accumulation unit 14-1 and the second result accumulation unit 14-2 can be secured in the memory space of the main memory of the image decoding device, for example.

  The decoding control unit 16 is a functional module that controls parallel decoding by the first decoding unit 12-1 and the second decoding unit 12-2. When the decoding of the code file 10 is instructed from an upper system (for example, an application program), the decoding control unit 16 sets the first address of the code data in the code file 10 to the first decoding unit 12-1, the second address. The decoding unit 12-2 designates an intermediate address of the code data as a starting point of the decoding process, and starts decoding. Here, as the starting point of the second decoding unit 12-2, for example, the address of the central position of the code data may be designated. In addition, the decoding control unit 16 passes the information of the Huffman table and the quantization table included in the code file 10 to the first decoding unit 12-1 and the second decoding unit 12-2 so that the decoding process can be performed. The decoding control unit 16 can be realized as software or a hardware circuit.

  By such control of the decoding control unit 16, the first decoding unit 12-1 starts decoding from the head of the code data toward the back, and the second decoding unit 12-2 starts from the start point in the middle of the code data. Decoding will be started toward. Here, since the first decoding unit 12-1 performs decoding from the head of the code data, in principle, decoding can be performed correctly. On the other hand, since the second decoding unit 12-2 starts decoding from the starting point in the middle of the code data, the decoding is not always successful.

  The second decoding unit 12-2 includes a failure detection unit 124. When the failure detection unit 124 detects that the decoding performed by the second decoding unit 12-2 has failed, the second decoding unit 12-2 Move the start point one bit behind the previous position, or move it to the next bit after the position where the failure was detected, and start decoding from that new position. To do. If this retry fails, the starting point is moved again and the trial is repeated. From the start point to the end of the code data, such trial and error is repeated until the failure detection unit 124 completes decoding without detecting failure. When the failure detection unit 124 detects a failure in decoding, the second decoding unit 12-2 may delete the decoding result that has been stored in the second result storage unit 14-2 so far.

  The starting point management unit 122 stores the position of the starting point that is changed every time decoding fails. Then, when the second decoding unit 12-2 finally completes the decoding from the certain starting point to the end of the code data without failure, the starting point managing unit 122 finally detects the position information of the starting point (in the memory space). (E.g., the address of) is transmitted to the decoding control unit 16. The decoding control unit 16 transmits the position information of the successful point to the first decoding unit 12-1, and the first decoding unit 12-1 performs decoding up to the successful point. Note that the information on the success point of the second decoding unit 12-2 may be directly acquired by the first decoding unit 12-1 instead of via the decoding control unit 16.

  When the decoding of the first decoding unit 12-1 is completed, the decoding control unit 16 instructs the decoding result combining unit 18 to combine decoding results. Upon receiving this instruction, the decoding result synthesis unit 18 stores the decoding result from the beginning of the code data 100 stored in the first result storage unit 14-1 to the success point, and the second result storage unit 14-2. The decoding result from the success point to the end of the code data 100 is combined to generate a decoding result of the entire code data 100. The decoding result synthesis unit 18 can be realized as software or a hardware circuit.

  In the above example, when the decoding of the second decoding unit 12-2 fails, the second decoding unit 12-2 itself moves the starting point and reattempts decoding, but instead, when decoding fails. The second decoding unit 12-2 may notify the decoding control unit 16 to that effect, and the decoding control unit 16 may move the start point and record the start point after the movement.

  The configuration of the image decoding device according to the embodiment has been described above. Next, an example of a decoding failure detection method of the failure detection unit 124 will be described.

  As an example, there is a method using the number of DCT coefficients in one block (in other words, the number of pixels in one block) in the JPEG system. A failure detection method using this method will be described with reference to FIGS.

  In the JPEG encoding method, DCT is performed on an 8 × 8 pixel block of an original image to obtain 64 DCT coefficients per block, and these coefficients are quantized using a quantization table. The 8 × 8 quantized DCT coefficients obtained in this way are zigzag scanned from a low frequency to a high frequency to obtain a one-dimensional array. This array is called the DC (direct current) component having the lowest frequency, and the difference from the DC component of the immediately preceding block is Huffman encoded. Other components are called AC (alternating current) components, and there are many components that have a value of 0 due to quantization, so a set of consecutive zeros (zero run) followed by non-zero component values is Huffman coded Is done.

  Examples of the results of Huffman decoding of code data encoded by such a method are shown in FIGS. 3 to 5, in FIG. 3, in the Huffman decoding result, the quantized DCT coefficient at the beginning of the block is 0th and the last is 63rd.

  As shown in FIGS. 3 to 5, the decoding result of the first code word of the block is regarded as a DC component value, and the decoding result of the subsequent code word is regarded as a set of zero run and non-zero AC component values. . That is, for the AC component, the decoding result of one codeword is a set of a series of zeros followed by a non-zero value. For example, in the example of FIG. 3, the decoding result of the third codeword is a combination of one “0” followed by one non-zero value. If the Huffman decoding proceeds from the beginning of the block, if the decoding is successful, the non-zero value obtained when decoding some codewords is the 63rd of the block as shown in FIG. come. Also, in JPEG, when all the AC components in the block to the end are 0, they are converted into a special code called EOB (end of block). Therefore, as shown in FIG. Decoding can also be considered successful if 0 comes in the 63rd position of the block. On the other hand, in the example shown in FIG. 5, the result of Huffman decoding of a certain code word does not reach the 63rd block, and the non-zero AC component after the zero run obtained when the next code word is decoded. The value is behind the 63rd. If the decoding is successful, the decoding result does not overflow from the block in this way. Therefore, when this occurs, it can be determined that decoding has failed.

  A processing procedure of the image decoding apparatus when such a failure detection method is used will be described with reference to FIGS.

  As illustrated in FIG. 6, the first decoding unit 12-1 starts decoding from the head position of the code data 100 assigned from the decoding control unit 16. The first decoding unit 12-1 decodes the code data for one MCU (S11), and then the position of the code data that the first decoding unit 12-1 reads for decoding is the success of the second decoding unit. It is determined whether or not the point has been reached (S12). When the success point has not been reached, if the second decoding unit 12-2 has not found a success point, the determination result is No, and the first decoding unit 12-1 continues the decoding process. Then, when the determination result in step S12 is Yes, the first decoding unit 12-1 ends decoding.

  Here, when the second decoding unit 12-2 starts decoding from the central position of the code data 100, when the decoding of the first decoding unit 12-1 reaches the central position, the decoding of the second decoding unit 12-2. Is likely to reach the end of the code data 100 and the success point has been determined. If the starting point to be initially assigned to the second decoding unit is set to be somewhat later than the center position of the code data 100, the second decoding unit 12 will be required until the decoding of the first decoding unit 12-1 reaches the starting point. -2 success points can be established.

  When the first decoding unit 12-1 knows the position of the success point of the second decoding unit 12-2, the position decoded by the first decoding unit 12-1 exceeds the success point The first decoding unit 12-1 may complete the decoding. In this case, the image data stored in the first result storage unit 14-1 includes a portion after the success point, and an overlapping portion is formed with the image data stored in the second result storage unit 14-2. However, since the size of the image of the decoding result can be known from the information in the code file 10, even if there is such an overlapping portion, the original image data can be decoded by correctly combining the image data.

  Next, the processing procedure of the second decoding unit 12-2 will be described with reference to FIG. The second decoding unit 12-2 starts Huffman decoding from the start point designated by the decoding control unit 16, and decodes the code word read first as a DC component (S21). The second encoding unit 12-2 includes a counter that counts the number of quantized DCT coefficients obtained by Huffman decoding within the block, and sets the counter value to 0 when the decoding of the DC component is completed. This indicates that the 0th DCT coefficient in the block has been decoded. The second decoding unit 12-2 decodes the next codeword as an AC component (S22). Here, it is determined whether or not the code word read at that time is an EOB code (S23). If the code word is an EOB code, the block has been successfully decoded, and the counter is cleared (S28). Then, it is determined whether or not the decoding has been completed up to the end of the code data (S29). If not, the process returns to step S21 to perform the remaining decoding.

  If the code word decoded by AC decoding (S22) is not EOB (S23), the second decoding unit 12-2 increments the value of the counter according to the decoding result (S24). For example, when three 0s and one non-zero coefficient subsequent thereto are obtained as a result of decoding, the counter value is incremented by four. Then, the value indicated by the incremented counter is compared with “63” (S25). If the counter value is less than 63, it means that all the AC components in the block have not been decoded, so the process returns to step S22 to continue the remaining decoding. If the counter value is equal to 63, this corresponds to the case shown in FIG. 4 and the decoding has succeeded up to the end of the block. In this case, the second decoding unit 12-2 clears the counter (S28), and returns to step S21 if decoding has not been completed to the end of the code data.

  If the counter value exceeds 63 in step S25, this corresponds to the case shown in FIG. 5, and the decoding has failed. In this case, the second decoding unit 12-2 clears the counter (S26), changes the position of the start point (S27), returns to step S21, and tries decoding again from the changed start point. Note that the change of the starting point in step S26 may be any of the methods described above. The starting point management unit 122 records the changed starting point.

  As the above processing is repeated, a starting point is found where the end of the code data can be decoded without failure. If such a starting point is found, decoding proceeds without failure. When it is determined in step S29 that decoding has been completed up to the end of the code data, the second decoding unit 12-2 records the start point as a success point (S30). The information on this successful point is notified to the first decoding unit 12-1.

  Next, another method for detecting a failure in decoding by the failure detection unit 124 will be described with reference to FIGS. In this method, a code word for failure detection is used in addition to a code word corresponding to information to be encoded in code word allocation in Huffman coding. Then, when a code word for failure detection is detected in decoding, it is determined that decoding has failed.

  For example, when Huffman coding is performed on the original data consisting of eight types of information A to H, if the maximum length of the code word is 6, code word allocation as shown in FIG. In this example, for example, code word “0” is assigned to information “A”, and code word “10” is assigned to information “B”. The code allocation rule as shown in FIG. 8 is used in encoding and decoding in the form of a Huffman table.

  Here, when one code for failure detection is further added to the eight pieces of information A to H and the codeword assignment is performed with the maximum codeword length set to 6, the code assignment rule as shown in FIG. can get. In this code assignment rule, a code word of a bit string “1110” is assigned as a failure detection code. In this example, there is one failure detection code, but it is of course possible to use a plurality of codes. The failure detection code may be incorporated into a DC component Huffman table or an AC component Huffman table. Moreover, you may incorporate in both of them.

  When this failure detection method is used, a device that encodes an image performs encoding according to a code allocation rule including a failure detection code. Then, when the second decoding unit 12-2 of the image decoding apparatus detects the failure detection code in the Huffman table in the file when decoding the code file, the second decoding unit 12-2 may determine that the decoding has failed.

  FIG. 10 shows the processing procedure of the second decoding unit 12-2 when both the failure detection method and the failure detection method due to block overflow described above are used. This procedure is an example when a failure detection code is incorporated in the AC component Huffman table.

  The procedure in FIG. 10 is obtained by adding step S40 to the procedure in FIG. In step S40, it is determined whether or not the result of AC component decoding (S22) is a failure detection code. If the result is a failure detection code, it is determined that decoding has failed, and the process proceeds to step S26. If it is not a failure detection code, the process proceeds to step S23 to determine whether or not the decoding result is EOB. The execution order of steps S40 and S23 may be reversed.

  In the image decoding apparatus described above, the second decoding unit 12-2 performs decoding from the starting point in the middle of the code data 100. However, since the DC component of the block immediately before the starting point is unknown, Ingredients may not be correct. In order to deal with such a problem, the decoding result of the second decoding unit 12-2 may be corrected using the DC component of the last block of the decoding result of the first decoding unit 12-1. The correction of the decoding result of the second decoding unit 12-2 may be performed by a method of adding the DC component of the last block of the first decoding unit 12-1 to the data of each pixel obtained by the inverse DCT process. . As another method, the same correction can be achieved by adding the DC component of the last block of the first decoding unit 12-1 to the quantized DCT coefficient of the DC component of each block obtained by Huffman decoding. Is possible. In the case of a color image, the last block DC component of the decoding result of the first decoding unit 12-1 is obtained for each component of the luminance component and each color difference component, and thereby the decoding result of the second decoding unit 12-2 is obtained. What is necessary is just to correct | amend a luminance component and each color difference component.

  An example of the configuration of the image decoding apparatus including this correction processing is shown in FIG. In the example of FIG. 11, the combination of the Huffman decoding unit 41-1 and the inverse DCT unit 42-1 corresponds to the first decoding unit 12-1 of the apparatus configuration of FIG. 2, and is the reverse of the Huffman decoding unit 41-2. The combination of the DCT unit 42-2 corresponds to the second decoding unit 12-2. Note that the functional modules corresponding to the start point management unit 122 and the failure detection unit 124 of the second decoding unit 12-2 are not shown in order to avoid complexity.

  The Huffman decoding unit 41-1 performs Huffman coding with the beginning of the code data in the code file 10 as a starting point. The inverse DCT unit 42-1 inversely quantizes the result of the Huffman decoding, and performs inverse DCT on the inverse quantization result. Thereby, the image information is restored. Information on the pixel value of each pixel output from the inverse DCT unit 42-1 is accumulated in the first result accumulation unit 43-1. Further, the Huffman decoding unit 41-1 stores the DC component of the last block when decoding is performed up to the successful point of the second decoding unit 12-2 in the first result storage unit 43-1.

  The Huffman decoding unit 41-2 performs Huffman decoding from a designated starting point in the middle of the code data, and the inverse DCT unit 42-2 performs inverse quantization and inverse DCT on the Huffman decoding result. The output of the inverse DCT unit 42-2 is accumulated in the second result accumulation unit 43-2. When the Huffman decoding unit 41-2 detects a decoding failure using the above-described method, the position of the start point is changed, and the Huffman decoding unit 41-2 tries decoding again.

  The decoding result combining unit 44 combines the image information stored in the first result storage unit 43-1 and the second result storage unit 43-2 to generate an image of the decoding result corresponding to the entire code data. Here, when the decoding result synthesis unit 44 synthesizes the image information accumulated in the first result accumulation unit 43-1 and the second result accumulation unit 43-2, each pixel of the second result accumulation unit 43-2. Is corrected by the DC component of the last block stored in the first result storage unit 43-1. The correction can be performed by adding the DC component of the last block accumulated in the first result accumulation unit 43-1 to the value of each pixel in the second result accumulation unit 43-2. Such a correction calculation can be implemented by a combination of an adder and a selector (data selection switch).

  The post-processing unit 46 performs post-processing according to the purpose on the image of the decoding result output from the decoding result combining unit 44. Post-processing includes, for example, FIR (finite impulse response) filter processing, image enlargement or reduction, resolution conversion, color correction, and the like. The output unit 48 is a device that outputs an image of the processing result of the post-processing unit 46, and is, for example, a printer or a display device. The output unit 48 may be a device that writes image data to a file. In the case of an apparatus that does not require post-processing, the post-processing unit 46 is not necessary.

  Next, another example of an image decoding device that corrects a DC component will be described with reference to FIG. In FIG. 12, the same elements as those shown in FIG.

  In the apparatus of FIG. 12, the post-processing unit 46a executes correction of the DC component of the decoding result of the second decoding unit, not the decoding result combining unit 44a. The decoding result synthesizing unit 44a simply assembles the image data of the first result accumulation unit 43-1 and the second result accumulation unit 43-2 without correcting the DC component, and generates the decoding result corresponding to the entire code data. Generate an image. When the post-processing unit 46 performs post-processing on the image, the value of each pixel of the part acquired from the second result storage unit 43-2 in the image is stored in the first result storage unit 43-1. Is corrected using the last DC component. When the processing performed by the post-processing unit 46 is FIR filter processing, enlargement / reduction, resolution conversion, color correction, or the like, the post-processing unit 46 can correct the DC component in this way. If the post-processing is pixel-based processing, the post-processing unit 46 can correct the DC component.

  Next, another example of an image decoding device that corrects a DC component will be described with reference to FIG. In FIG. 13, the same elements as those shown in FIG.

  In the apparatus of FIG. 13, intermediate information as decoding results of the Huffman decoding units 41-1 and 41-2 is stored in the first result storage unit 45-1 and the second result storage unit 45-2, respectively. Then, the intermediate information corresponding to the entire code data is obtained by synthesizing the accumulated intermediate information by the decoding result synthesizing unit 47, and inverse DCT is performed on the intermediate information by the inverse DCT unit 42a. Here, in the configuration of FIG. 13, the inverse DCT unit 42a corrects the decoding result of the Huffman decoding unit 41-2 by the DC component of the final block of the Huffman decoding unit 41-1. This correction may be performed, for example, by correcting the DC component of each block of the decoding result of the Huffman decoding unit 41-2 with the DC component of the final block. Alternatively, the value of each pixel corresponding to the output of the second decoding unit (Huffman decoding unit 41-2) in the inverse DCT result may be corrected by the DC component of the final block.

  In the above, the image decoding apparatus provided with the two decoding parts 12 was illustrated. Next, an example of an image decoding device including three or more decoding units will be described.

  As shown in FIG. 14, the image decoding apparatus of this example includes N (N is an integer of 3 or more) decoding units 12. Among these, the 2nd decoding part 12-2-the Nth decoding part 12-N are provided with the starting point management part 122 and the failure detection part 124. FIG. The functions of the start point management unit 122 and the failure detection unit 124 may be the same as those in the example of FIG. The decoding control unit 16 controls parallel decoding by the first decoding unit 12-1 to the Nth decoding unit 12-N. When decoding the code file 10, as shown in FIG. 15, the decoding control unit 16 designates the starting point SPi (i is an integer from 1 to N) of the decoding process for each decoding unit 12, and starts decoding. Instruct. The start point SP1 assigned to the first decoding unit 12-1 is the head address of the code data in the code file 10. The k-th start point SPk assigned to the k-th decoding unit 12-k (k is an integer of 2 or more and N or less) becomes a later position (ie, a position closer to the end) in the code data as k increases. For example, each division point when the code data is equally divided into N pieces may be assigned as the k-th start point SPk.

  Similar to the first decoding unit 12-1 in the example of FIG. 2, the first decoding unit 12-1 may perform decoding from the head of the code data to the success point of the second decoding unit 12-2. The processing procedure may be the same as that shown in FIG. The processing procedure of the last decoding unit, that is, the N-th decoding unit 12-N is the same as that of the second decoding unit 12-2 in the example of FIG. Repeat decoding attempts while moving the starting point. The processing procedure may be as shown in FIG. 7 or FIG. The starting point when the Nth decoding unit 12-N completes decoding without failure to the end of the code data is referred to as the Nth success point.

  The k-th decoding unit 12-k (k is an integer of 2 or more and (N-1) or less) is decoded without failure until the (k + 1) th successful point obtained by the trial by the (k + 1) -th decoding unit 12- (k + 1). The decoding attempt is repeated while moving the k-th starting point until the k-th starting point to be finished is found. The k-th start point when the decoding is completed without failure up to the (k + 1) -th success point is referred to as the k-th success point. With the above processing, the kth success point is determined in the direction of decreasing the number from the Nth success point.

  An example of the processing procedure of the k-th decoding unit 12-k (k is an integer of 2 or more and (N-1) or less) is shown in FIG. This procedure is an example in which failure detection is performed due to block overflow, and can be regarded as a modification of the procedure of FIG. In the procedure of FIG. 16, steps that perform the same processing as the steps of the procedure of FIG. Note that the method using the failure detection code (see FIG. 10) can be modified in the same manner to be the processing procedure of the k-th decoding unit.

  In the procedure of FIG. 16, the k-th decoding unit 12-k starts decoding from the designated k-th starting point. If a decoding failure is detected in step S25, the counter for counting the decoded quantized DCT coefficients is cleared (S26), and the position of the k-th starting point is moved (S27a). As a method of moving the k-th starting point, various methods can be used as in the example of FIG. When it is detected in step S23 that EOB has been detected or in step S25 that decoding has been completed up to the end of the block, the k-th decoding unit 12-k clears the counter (S28) and (k + 1) -th. It is checked whether the decoding has been completed up to the success point (S29a). If not completed, the process returns to step S21 to continue the decoding. When the decoding is completed up to the (k + 1) th successful point, the kth starting point at that time is set as the kth successful point, and information on the kth successful point is notified to the (k-1) th decoding unit 12- (k-1). Process to do.

  The decoding results of the first decoding unit 12-1 to the N-th decoding unit 12-N obtained in this way are accumulated in the first result accumulation unit 14-1 to the N-th result accumulation unit 14-N, respectively. . The decoding result synthesis unit 18 synthesizes the partial decoding results stored in the first result storage unit 14-1 to the Nth result storage unit 14-N, and obtains a decoding result corresponding to the entire code data.

  The embodiment has been described above. Each example of the image decoding apparatus described above can be incorporated into, for example, a printer or a digital multi-function peripheral. When the image is reproduced from the code file and printed, the above-described technology of the image decoding device can be applied. In addition, what was illustrated above is only an example of the application field of each embodiment.

  In the above embodiment, the JPEG encoding method is taken as an example, but other image encoding / decoding methods using variable length encoding (for example, other than the method using the JPEG specific property among the methods of the embodiment (for example, (MPEG, JPEG2000, etc.).

  In each of the above embodiments, Huffman coding is taken as an example of the variable length coding method. However, the method of each of the above embodiments can be applied even when other coding methods such as arithmetic coding are used. In addition, since the method of the above embodiment is not based on the contents represented by data in principle, it can be applied to data other than images.

  Further, the detection method of the decoding failure in the failure detecting unit 124 is not limited to the above-described example, and various methods can be used.

  When the image decoding apparatus according to the above-described embodiment is realized by software, a program describing the function of each functional module may be executed by a computer. The computer has a circuit configuration in which a CPU (central processing unit) 50, a memory (primary storage) 52, various I / O (input / output) interfaces 54, and the like are connected via a bus 56 as shown in FIG. Further, a hard disk drive 58 and a disk drive 60 for reading various types of portable non-volatile recording media such as a CD, a DVD, and a flash memory are connected to the bus 56 via, for example, an I / O interface 54. . Such a drive 58 or 60 functions as an external storage device for the memory. A program describing the processing contents of the embodiment is stored in a fixed storage device such as the hard disk drive 58 via a recording medium such as a CD or DVD or via a network, and is installed in a computer. The program stored in the fixed storage device is read into the memory and executed by the CPU, whereby the processing of the embodiment is realized. Each decoding unit 12 may be realized as a hardware circuit, and the decoding control unit 16 and / or the decoding result synthesis unit 18 that controls them may be realized as a program.

It is a figure for demonstrating the system of the parallel decoding in embodiment. It is a figure which shows the structural example of the image decoding apparatus of embodiment. It is a figure which shows an example of the Huffman decoding result when decoding has not failed. It is a figure which shows an example of the Huffman decoding result when decoding has not failed. It is a figure which shows an example of a Huffman decoding result when decoding has failed. It is a flowchart which shows the example of the process sequence of a 1st decoding part. It is a flowchart which shows the example of the process sequence of a 2nd decoding part. It is a figure which shows notionally the example of normal code allocation. It is a figure which shows notionally the example of the code allocation containing the code for failure detection. It is a flowchart which shows the example of the process sequence of the 2nd decoding part in the case of performing decoding failure detection by the code for failure detection. It is a figure which shows an example of an apparatus structure which correct | amends DC component. It is a figure which shows another example of the apparatus structure which correct | amends DC component. It is a figure which shows another example of the apparatus structure which correct | amends a DC component. It is a figure which shows the structural example of the image decoding apparatus containing a 3 or more decoding part. It is a figure for demonstrating the starting point allocated initially to each decoding part in the image decoding apparatus containing 3 or more decoding parts. It is a flowchart which shows the process sequence of each decoding part except the head and the end in the image decoding apparatus containing 3 or more decoding parts. It is a figure which shows the example of the hardware constitutions of a computer.

Explanation of symbols

  DESCRIPTION OF SYMBOLS 10 Code file, 12-1 1st decoding part, 12-2 2nd decoding part, 14-1 1st result storage part, 14-2 2nd result storage part, 16 decoding control part, 18 decoding result synthetic | combination part, 100 Code data.

Claims (8)

A first decoding unit that performs decoding from a first start point that is a head of code data to be decoded;
K-th decoding unit provided for each integer k of 2 or more and N or less, attempting decoding from the k-th start point located after the (k-1) start point in the middle of the code data, A k-th decoding unit that attempts to decode again after changing the position of the k-th starting point when decoding fails;
The Nth starting point when the Nth decoding unit completes decoding without failing to the end of the code data is set as the Nth success point, and the (k−1) th decoding unit without failing to the kth success point. The (k-1) th success point of the code data for each k of 2 or more and N or less when the (k-1) th start point when decoding is finished is the (k-1) th success point. Based on the decoding result of the (k−1) th decoding unit for the part from the first to the kth successful point and the decoding result of the Nth decoding unit for the part from the Nth successful point to the end of the code data. A decoding result generation unit that generates a decoding result corresponding to the entire encoded data;
A data decoding apparatus comprising: Each decoding unit performs Huffman decoding in JPEG decoding,
Each of the decoding units from the second decoding unit to the N-th decoding unit determines that decoding has failed when the quantized DCT coefficient obtained by Huffman decoding overflows a block defined in JPEG. The data decoding device according to claim 1. Each decoding unit performs Huffman decoding in JPEG decoding,
Each of the decoding units from the second decoding unit to the N-th decoding unit performs Huffman decoding according to a code allocation rule including a code bit string for failure detection that is not associated with a quantized DCT coefficient. 2. The data decoding apparatus according to claim 1, wherein when a failure detection code bit string is detected, it is determined that decoding has failed. Each decoding unit performs Huffman decoding in JPEG decoding,
Based on the direct current component of the last block obtained when the i th decoding unit (i is an integer of 1 to (N−1)) from the i th successful point to the (i + 1) th successful point, A DC component correction unit that corrects the decoding result of the (i + 1) th decoding unit;
The data decoding apparatus according to claim 1, further comprising:   The k-th decoding unit (k is an integer of 2 or more and N or less), and when decoding fails, continues decoding using a position next to the failed position as a new k-th starting point. The data decoding device according to 1. A first decoding unit that performs decoding from the beginning of code data to be decoded;
A second decoding unit that attempts decoding from a starting point in the middle of the code data, and if decoding fails, changes the position of the starting point and tries decoding again;
The first decoding of the portion from the top of the code data to the success point when the second decoding unit has successfully completed the decoding to the end of the code data without success A decoding result generation unit that generates a decoding result of the entire code data, based on the decoding result of the unit and the decoding result of the second decoding unit from the success point to the end of the code data;
A data decoding apparatus comprising: Causing the first decoding unit to perform decoding from the first start point that is the head of the code data to be decoded;
Causing the k-th decoding unit provided for each integer k of 2 or more and N or less to try decoding from the k-th start point located after the (k-1) start point in the middle of the code data;
Detecting a decoding failure of the k-th decoding unit,
When the decoding failure of the k-th decoding unit is detected, the position of the k-th starting point is changed, and the k-th decoding unit is tried again,
The Nth starting point when the Nth decoding unit completes decoding without failing to the end of the code data is set as the Nth success point, and the (k−1) th decoding unit without failing to the kth success point. The (k-1) th success point of the code data for each k of 2 or more and N or less when the (k-1) th start point when decoding is finished is the (k-1) th success point. Based on the decoding result of the (k−1) th decoding unit for the part from the first to the kth successful point and the decoding result of the Nth decoding unit for the part from the Nth successful point to the end of the code data. A decoding result corresponding to the entire code data is generated,
A program that causes a computer to execute processing. Let the first decoding unit perform decoding from the beginning of the code data to be decoded,
Let the second decoding unit try decoding from the starting point in the middle of the code data,
Detecting a decoding failure of the second decoding unit;
If a failure in decoding by the second decoding unit is detected, the position of the starting point is changed and the second decoding unit tries again,
The first decoding of the portion from the top of the code data to the success point when the second decoding unit has successfully completed the decoding to the end of the code data without success Generating a decoding result of the entire code data based on a decoding result of a part and a decoding result of the second decoding unit from the success point to the end of the code data;
A program that causes a computer to execute processing.

Images