Encoding apparatus and method

[0002] 1. Field of the Invention

[0003] The present invention relates to an image data encoding apparatus and an image data encoding method.

[0004] 2. Related Background Art

[0005] Included in an image, particularly a multi-valued image, is a great amount of information, and an enormous amount of space is required to store or transmit the data for such an image. Therefore, to facilitate the storage or transmission of image data, the amount of data that must be handled is reduced by using a high-efficiency encoding process whereby image redundancies are removed, or another one whereby the image data are compressed in such a manner that some data are lost, but the degree of loss is such that the resulting deterioration of the image quality is extremely difficult to detect visually.

[0006] One well known, high-efficiency encoding method is the JPEG compression encoding method. According to this method, a multi-valued image is divided into blocks and a DCT transform performed for each block, and the obtained frequency component is quantized for variable length coding.

[0007] A problem with coding that employs a DCT transform is that when a high compression rate is set distortion occurs in a block in a decoded image. Recently, to remove this distortion, a new encoding method using a wavelet transform has been proposed.

[0008] Further, variable length coding is frequently employed as a part of these various high-efficiency coding methods.

[0009] However, a simple process by which to employ a method for the variable length coding of a multi-valued image, and a circuit configuration by which variable length coding can be performed rapidly have not yet been established.

[0010] To resolve the conventional problems, it is one objective of the present invention to provide a configuration for easily and rapidly performing variable length coding for a multi-valued image, and in particular, for easily and rapidly performing a determination process for estimating coding efficiency and for determining, as needed, a parameters to be used for coding.

[0011] To achieve the above objective, according to the present invention, an encoding apparatus for an image processing apparatus, one which encodes a plurality of sets of multi-valued image data (corresponding to the quantized values for one sub-block in the preferred embodiments of this invention) to produce code having variable lengths (corresponding to Golomb code in the embodiments) based on the multi-valued image data and a parameter k (corresponding to parameter k in the embodiments), comprises:

[0012] a bit shift unit (corresponding to a unit 501ain the embodiments) for performing bit shifts for each of the multi-valued image data sets a different number of times (0 to a times in the embodiments) in accordance with the parameter k (corresponding to k=0 to a in the embodiments) and for outputting P sets ((a+1) sets in the embodiments) of data;

[0013] P accumulation adders (corresponding to those units labeled 502ato 502zin the embodiments) for accumulating the P sets of data in correlation with the parameter k, for each of the multi-valued data sets (for each sub-block in the embodiments); and

[0014] comparators (corresponding to those units labeled 503ato 503zin the embodiments) for comparing the results obtained by the accumulation adders to determine an optimal parameter k for each of the multi-valued image data sets.

[0015] In addition, to achieve the above objective, according to the present invention an encoding apparatus, which employs one of a plurality of coding parameters to encode a plurality of sets of multi-valued image data to obtain coded data having a fixed length code portion and a variable length code portion, comprises:

[0016] a calculation unit for calculating in parallel, for each of the coding parameters, the total amount of code that is obtained when the multi-valued image data are encoded;

[0017] a detection unit for detecting the smallest total amount of code provided by the calculation unit when calculating the total amounts of code; and

[0018] a holding unit for storing a value representing a coding parameter that corresponds to the smallest total amount of code identified by the detection unit.

[0019] Other objectives and features of the present invention will become obvious during the course of the following explanation of the preferred embodiments, given while referring to the accompanying drawings.

[0020] FIG. 1 is a block diagram employed for the individual preferred embodiments of the present invention;

[0021] FIGS. 2A, 2B and 2C are diagrams for explaining a discrete wavelet transform;

[0022] FIG. 3 is a diagram showing a quantizing step used for a frequency component (sub-block);

[0023] FIG. 4 is a diagram showing example variable length code obtained using Golomb coding;

[0024] FIG. 5 is a detailed diagram illustrating an encoding parameter selecting unit according to a first embodiment of the present invention;

[0025] FIG. 6 is a diagram showing variable length code obtained by using Golomb encoding and represented by using a bit plane;

[0026] FIG. 7 is a diagram showing the structure of a bit stream that is finally output;

[0027] FIG. 8 is a detailed diagram illustrating an encoding parameter selecting unit according to a second embodiment of the present invention; and

[0028] FIG. 9 is a detailed diagram illustrating an encoding parameter selecting unit according to a third embodiment of the present invention.

[0029] (First Embodiment)

[0030] A first embodiment of the present invention will now be described while referring to the accompanying drawings.

[0031] In this embodiment, monochrome image data of 8 bits each are encoded. It should be noted, however, that the coding performed by the present invention is not limited to data having this length, but can also be applied for a monochrome image wherein each pixel is represented by four bits, or a color, multi-valued image wherein each color component (RGB/Lab/YCrCb) of each pixel is represented by 8 bits. The present invention can also be applied for encoding multi-valued information wherein the state of each pixel constituting an image is represented; for example, for encoding a multi-valued index wherein the color of each pixel is represented. When the present invention is applied for the above encoding, only various types of multi-valued information need be encoded as monochrome image data, which will be described later.

[0032] FIG. 1 is a block diagram illustrating an image processing apparatus for carrying out the first embodiment of the present invention. The image processing apparatus comprises: an image input unit 101, a discrete wavelet transforming unit 102, a buffer 103, a coefficient quantizing unit 104, an encoding parameter selecting unit 105, a Golomb (Golomb-Rice) encoding unit 106, a bit plane order scanning unit 107, a buffer 108, a code output unit 109, and a frame buffer 110.

[0033] First, image data that constitute an image to be encoded are obtained by the image input unit 101 in the raster scan order. The image input unit 101 is, for example, a photographing device, such as a scanner or a digital camera; an image pickup device, such as a CCD; or an interface for a network line. The image input unit 101 may be a storage medium, such as a RAM, a ROM, a hard disk or a CD-ROM.

[0034] The discrete wavelet transforming unit 102 receives pixel data for one screen from the image input unit 101, and temporarily stores them in the buffer 103.

[0035] The discreet wavelet transforming unit 102 then performs a well known discrete wavelet transform for the pixel data for one screen stored in the buffer 103, and separates the data into a plurality of frequency bands. In this embodiment, the discrete wavelet transform for image data string x(n) is performed by using the following equation.

[0036] r(n)=floor {x(2n)+x(2n+1))/2}

[0037] d(n)=x(2n+2)−x(2n+3)+floor {−r(n)+r(n+2)+2)/4}

[0038] where r(n) and d(n) are transform coefficients: r(n) being a low frequency component, and d(n) being a high frequency component; and floor {X} denotes a maximum integer that does not exceed X. While this transform equation is for one-dimensional data, a two-dimensional transform can be performed by applying this transform in the horizontal direction and in the vertical direction, in the named order. Therefore, the image data string can be divided into four frequency bands (sub-blocks) LL, HL, LH and HH, as shown in FIG. 2A.

[0039] When the discrete wavelet transform is performed in the same manner for the obtained LL component, the LL component is divided to obtain seven frequency bands (sub-blocks), as shown in FIG. 2B. In this embodiment, the discrete wavelet transform is repeated one more time for the seven frequency bands to obtain the 10 frequency bands (sub-blocks) LL, HL3, LH3, HH3, HL2, LH2, HH2, HL1, LH1 and HH1 shown in FIG. 2C.

[0040] The transform coefficient is output to the coefficient quantizing unit 104 in the sub-block order, LL, HL3, LH3, HH3, HL2, LH2, HH2, HL1, LH1 and HH1, and in the raster scan order for each sub-block.

[0041] The coefficient quantizing unit 104 receives the wavelet transform coefficients from the discrete wavelet transforming unit 102, quantizes each coefficient at a quantizing step defined for each frequency component, and outputs the values obtained by quantization to the encoding parameter selecting unit 105 and the frame buffer 110.

[0042] When the coefficient value is X and the quantizing step for a frequency component to which this coefficient belongs is q, after quantization, coefficient value Q(X) is calculated using the following equation.

[0043] Q(X)=floor{(X/q)+0.5}

[0044] where floor {X} is a maximum integer that does not exceed X. FIG. 3 is a diagram showing the individual frequency components in this embodiment and corresponding quantizing steps. As is shown in FIG. 3, the quantizing step for a high frequency component (HL1, LH1 or HH1) is greater than is that for a low frequency component (LL, etc.).

[0045] The quantized values are stored in the frame buffer 110 until parameter k, which is required by the Golomb encoding unit 106 at the succeeding stage to encode the quantized values, is determined.

[0046] The encoding parameter selecting unit 105 employs a received quantized value to select the parameter k, which is used by the Golomb encoding unit 106 at the succeeding stage for Golomb encoding. This parameter k is a value representing the code length of a fixed length portion used to perform the variable length coding called Golomb encoding. In the explanation, for the sake of convenience an explanation will be given for the operation performed by the Golomb encoding unit 106 before one is given for the encoding parameter selecting unit 105.

[0047] Although the basic Golomb encoding method performed by the Golomb encoding unit 106 is well known, an explanation will now be given for the basic encoding operation and the characteristic portion of this invention.

[0048] First, a quantized value is received from the frame buffer 10. for each sub-block. This is done because the Golomb encoding unit 106 changes the parameter k for each sub-block to use it for the Golomb encoding.

[0049] The Golomb encoding unit 106 determines whether each of the received quantized values is a positive value or a negative value, and outputs a sign (code) (+or −). Specifically, when the quantized value is 0 or positive, a value of “1” is output as a sign bit. When the quantized value is negative, a value of “0” is output.

[0050] Next, the Golomb encoding is performed for the absolute value of each quantized value. When the absolute value of a quantized value to be encoded is V and the parameter applied for a sub-block to be processed is k, the Golomb encoding is performed in the following manner.

[0051] First, bit data representing V is shifted k bits to the right, and integer m in the decimal system, which is represented by the obtained bit data, is calculated. Based on the result, m “0”s are arranged in line, a “1” is sequentially located as a delimiter bit, and finally, the lower k bits representing the original V are arranged so that variable length code (Golomb code) is generated. FIG. 4 is a diagram showing one part of the variable length code obtained by performing the above Golomb encoding for k=0, 1 or 2.

[0052] That is, it can be easily estimated that the code length in bits of each of the variable length codes that is obtained from the absolute value of each quantized value and the parameter k is ((bit count m indicated by integer m)+(delimiter bit count 1)+(bit count k corresponding to the value of the parameter k)).

[0053] Further, as is apparent from FIG. 4, when the parameter k=0, in particular, the length of the Golomb code corresponding to the quantized value “0” is shorter than the length when the parameter k=1 or 2. This means that as the group of quantized values to be encoded is nearer 0, it is appropriate for the Golomb encoding to be performed with a smaller parameter k.

[0054] The Golomb encoding used here provides a result to the effect that encoding and decoding can be enabled by using a simple calculation, while in actuality the code table shown in FIG. 4 is required. Normally, for variable length coding such as Huffman coding, a table must be prepared for variable length code and a corresponding value that is to be encoded. In particular, the table is required to change switch a plurality of variable length codes in accordance with a state associated with a value to be encoded.

[0055] The encoded data, composed of a sign (+or −) bit for the received quantized value and the variable length code (Golomb code), is generated and is output to the bit plane order scanning unit 107 at the succeeding stage.

[0056] FIG. 5 is a diagram showing the detailed arrangement of the encoding parameter selecting unit 105 for generating the parameter k that is required by the Golomb encoding unit 106.

[0057] As is described above, usually, to generate the parameter k used for Golomb encoding, the deviation of a group of quantized values to be encoded is obtained by forming a histogram for images (quantized values) that are actually to be encoded.

[0058] However, a large memory capacity is required to generate such a histogram.

[0059] To resolve this problem, the arrangement shown in FIG. 5 is employed for this embodiment.

[0060] In FIG. 5, bit shift units 501a, 501b, 501c, . . . shift a received quantized value one bit to the right. Accumulation adders 502ato 502zstore initial values 2N to (a+2)N respectively, and add N values that are sequentially input. Each of the adders 502 includes and outputs ID information together with the value obtained by adding the N values. Each of the comparators 503ato 503zcompares the accumulated values received from two adders, and outputs the smaller accumulated added value and the ID information to the comparator at the succeeding stage. It should be noted that the comparator 503zat the last stage outputs only the ID information to the Golomb encoding unit 106.

[0061] The output of each of the accumulation adders 502ato 502zrepresents the total code length when the Golomb encoding is performed for the N quantized values based on the parameter k=0, 1, 2, . . . Each code portion has a length in bits of N×(1 (positive or negative sign bit)+1 (delimiter bit)+k (parameter k value)+ΣM_k(value obtained by subtracting lower k bits from absolute value V).

[0062] For example, the accumulated value output by the accumulation adder 502ais 2N +ΣM₀, the accumulated value output by the accumulation adder 502bis 3N+ΣM₁, and the accumulated value output by the accumulation adder 502zis (a+2)N+ΣM_a.

[0063] In this embodiment, the ID information value is the same value as the parameter value, and the Golomb encoding unit 106 can employ the received ID information to rapidly determine the parameter k.

[0064] It should be noted that for the explanation given while referring to FIG. 5, N quantized values are included in a sub-block. Thus, to determine the parameter k when it is used to encode a sub-block wherein M quantized values are included, the initial values for the adders 502ato 502zare changed and the values 2M to (a+2)M are used. Such a change in the initial values can be implemented by providing an initial value switching unit (not shown).

[0065] The bit plane order scanning unit 107 in FIG. 1 processes each of the frequency components (sub-blocks) described above. First, the bit plane order scanning unit 107 receives data encoded by the Golomb encoding unit 106, and stores the data for one frequency component (one of the sub-blocks LL to HH1) in the buffer 108.

[0066] The code (+or −) bit corresponding to each pixel generated by the Golomb encoding unit 106 is stored in a positive/negative sign plane; the first bit (MSB) of the Golomb code that corresponds to each pixel is stored in the first bit plane; the second bit is stored in the second bit plane; and the third and the following bits are stored in the third and the following bit planes. In this manner, encoded data corresponding to the individual pixels are stored in the buffer 108 as a plurality of bit planes.

[0067] When, for example, the data output by the Golomb encoding unit 106 is “0110”, “0” is stored in the positive/negative sign plane, “1” is stored in the first bit plane, “1” is stored in the second bit plane, and “0” is stored in the third bit plane. No bit information is stored in the fourth bit plane.

[0068] FIG. 6 is a diagram showing a table wherein a series, “3, 4, −2, −5, −4, 0, 1, . . . ”, of coefficient data values (quantized values) quantized for the HL3 component are encoded using the Golomb encoding unit 106, and the obtained data are stored as bit planes.

[0069] In FIG. 6, shaded portions represent locations for which, since the entry of coded data is terminated in the upper planes, no bit information is required, i.e., wherein no bit information is entered. The bit plane order scanning unit 107 receives from the Golomb encoding unit 106 all the code data representing one frequency component (one of the sub-blocks LL to HH1), and stores the data in the buffer 108, as described above. Then, the bit plane order scanning unit 107 reads the information from the bit planes in the raster scanning order and in the order represented by the sign bit plane, the first bit plane and the second bit plane, i.e., in the order beginning with the sign bit plane and continuing down to the lowest bit plane, and outputs it to the code output unit 109.

[0070] FIG. 7 is a diagram showing the format of the bit information that is extracted from the buffer 108 and output in the bit plane order.

[0071] The data are output hierarchically for each bit plane in the order of the sub-blocks for the low frequency components, LL, HL3, LH3, HH3, HL2, LH2, HH2, HL1, LH1 and HH1.

[0072] The code output unit 109 hierarchically outputs the obtained plurality of bit plane data sets. An interface for a public telephone network, a radio network or a LAN can be employed as the code output unit 109. The code output unit 109 may also be a storage device, such as a hard disk, a RAM or DVD, for storing the hierarchial data.

[0073] Since the images are hierarchically transmitted in order from the low frequency component to the high frequency component, the reception side can obtain the outline of an image hierarchically. Further, since data for the individual frequency components are also transmitted hierarchically for each bit plane, the reception side can also obtain the outline of each frequency component hierarchically. In addition, since each pixel (transform coefficient) is expressed by using a variable data length, the total amount of code can be reduced compared with the amount obtained when normal encoding is used for each bit plane.

[0074] It should be noted that information required by the decoding side, such as the image size, the bit count for each pixel, the quantizing step for each frequency component or the parameter k, is added as needed to the encoded data in the embodiment. For example, for the image processing for each line, for each block or for each band, information indicating the size of image is required.

[0075] (Second Embodiment)

[0076] Another arrangement for the encoding parameter selecting unit 105 in the first embodiment will now be described. The same reference numerals as are used in FIG. 5 are used to denote corresponding blocks in this embodiment.

[0077] In FIG. 8, bit shift units 501a, 501b, . . . shift a received quantized value one bit to the right. Initially, a value of 0 is held by each of the accumulation adders 502ato 502z, but upon receiving each of N values, accumulates a new value provided by adding K+2 to each of the N values. Held in each of the accumulation adders 502 is ID information that is output to the succeeding stage with the value obtained by accumulating N values. Comparators 503ato 503zcompare the accumulated values received from two adders, and output, to a succeeding comparator, the smaller of the two values and the ID information that corresponds to that value.

[0078] It should be noted that at the last stage the comparator 503zoutputs only ID information to the Golomb encoding unit 106. The output of the adders 502ato 502zrepresents the total code length obtained by performing the Golomb encoding of N quantized values based on parameter k=0, 1, 2 . . . The length of each code portion in bits is N×(1(positive or negative sign bit)+1 (delimiter bit)+k (parameter k value)+ΣM_k(value obtained by removing lower k bits from absolute value V).

[0079] For example, the accumulated value output by the accumulation adder 502ais 2N+ΣM₀, the accumulated value output by the accumulation adder 502bis 3N+ΣM₁, and the accumulated value output by the accumulation adder 502zis (a+2)N+ΣM_a.

[0080] In this embodiment, the ID information has the same value as the parameter value, and the Golomb encoding unit 106 can employ the received ID information to rapidly determine the parameter k.

[0081] It should be noted, for the explanation given while referring to FIG. 8, that N quantized values are included in a sub-block. Thus, to determine the parameter k used to encode a sub-block wherein M quantized values are included, in the adders 502ato 502zk+1 must only be added M times.

[0082] The processing performed at the preceding and succeeding stages of the encoding parameter selecting unit 105 is the same as that performed for the first embodiment.

[0083] (Third Embodiment)

[0084] In the second embodiment, a value of 2N is commonly included in the value output by the accumulation adders 502ato 502z. Since the comparators 503ato 503zcompare the amounts of code, the output of each accumulation adder need not always match the amount of code, and need only be a numerical value that represents a relative difference.

[0085] Therefore, the accumulation adder 502aadds received quantized values unchanged, the accumulation adder 502badds a value obtained by incrementing by one the value received from the bit shift unit 501a, and the accumulation adder 503cadds a value obtained by adding 2 to the value received from the bit shift unit 501b.

[0086] FIG. 9 is a diagram that briefly shows this operation.

[0087] The result obtained by linking the ID information with the obtained accumulated value is output to the succeeding comparator. The comparator performs the comparison, as in the second embodiment, to obtain ID information that corresponds to the parameter k for which the amount of code is the smallest.

[0088] The method used for comparing the accumulated values in this embodiment can also be applied for the first embodiment. The same effect as in the third embodiment can be obtained when, for example, the initial value held by the accumulation adder 502ain FIG. 5 is 0, the initial value held by the accumulation adder 502bis N, the initial value held by the accumulation adder 502cis 2N, the initial value held by the accumulation adder 502dis 3N, the initial value held by the accumulation adder 502eis 4N, . . .

[0089] (Other Embodiment)

[0090] In the above embodiments, the bit information for each bit plane is output unchanged. The present invention is, however, not limited to these embodiments. Instead of outputting the bit information unchanged to the code output unit, high-efficiency coding can be performed for the bit information that is finally output in the first embodiment, so that the total amount of code can be reduced. Run length coding or arithmetic coding can be employed as the high-efficiency coding, and higher-efficiency coding can be implemented. In the above embodiment, coding performed by using the discrete wavelet transform for an input image is employed. The present invention is not limited to the discrete wavelet transform used for these embodiments, and a different filter type or a different frequency division method may be employed. Furthermore, the present invention may be applied for encoding based on a transforming method, such as the DCT transform (discrete cosine transform), in addition to the discrete wavelet transform.

[0091] The method used for quantizing the frequency component or the variable length coding method is not limited to that used for the embodiments. For example, one frequency component (sub-block) can be sorted to several classes by identifying the local property of each block, and the quantizing step and the encoding parameter may be designated for each class.

[0092] (Modification)

[0093] The present invention may be applied as one part of a system that is constituted by a plurality of apparatuses (e.g., a host computer, an interface device, a reader and a printer), or as a part of an apparatus (e.g., a copier or a facsimile machine).

[0094] Further, the present invention is not limited to the apparatuses or the methods used to implement the above embodiments, but can also include a case where software program code for implementing the previous embodiments is supplied to a computer (or a CPU or an MPU) in an apparatus or in a system, and in consonance with the program, the computer in the system or in the apparatus can operate various devices to accomplish the above embodiments.

[0095] In this case, the program code read from the storage medium performs the functions assigned to the embodiments, and the program code and the means for supplying the program code to the computer, specifically, the storage medium on which such program code is recorded, constitutes the present invention.

[0096] A storage medium for supplying such program code can be, for example, a floppy disk, a hard disk, an optical disk, a magneto-optical disk, a CD-ROM, a magnetic tape, a nonvolatile memory card or a ROM.

[0097] In addition, the present invention includes not only the case where the functions in the previous embodiments can be performed by the computer reading and executing program code, but also the case where, in accordance with an instruction in the program code, an OS (Operating System) running on the computer performs part, or all, of the actual processing.

[0098] Furthermore, the present invention includes a case where program code, read from a storage medium, is written in a memory that is mounted on a function expansion board inserted into a computer, or inserted into a function expansion unit connected to a computer, and in consonance with a program code instruction, a CPU mounted on the function expansion board, or in the function expansion unit, performs part, or all, of the actual processing in order to implement the functions included in the above described embodiments.

[0099] As is described above, according to the present invention a configuration can be provide that can easily and quickly perform variable length coding for a multi-valued image. In particular, the process for estimating coding efficiency and for determining, as needed, a parameter to be used for coding, can be easily and quickly performed.