JP4956304B2 - Image encoding apparatus, control method therefor, computer program, and computer-readable storage medium - Google Patents

Description

The present invention relates to encoding technology for image data.

  Patent Document 1 discloses a technique for compressing a multi-value image in which a character / line image and a natural image are mixed. In this document, after dividing an input image into blocks that are units of orthogonal transformation at the time of encoding, it is assumed that a mode value having the highest appearance probability in a block is a character or a line drawing. Then, the pixel data of the color information or density information of the mode value is selected. Then, the most frequent pixel data is extracted from the block, and the extracted color and the identification information indicating whether the pixel is the extracted pixel (hereinafter, these two pieces of information are collectively referred to as resolution information) are run. Lossless encoding such as length encoding is performed. Then, the value of each pixel of the natural image after extracting the character and line drawing information is replaced with the average value of the block excluding the pixels extracted as the character line drawing. Then, irreversible encoding such as JPEG is performed on the replaced natural image.

  Here, extraction of the color information will be described by taking pixel data of a 4 × 4 pixel block shown in FIG. 12 as an example. In the pixel data of the block in FIG. 12, it is considered that a part of a natural image having an average level of “66” is overwritten with (part of) a character having a level of “240”. Normally, a natural image is generated through an analog input device such as a scanner or a digital camera, so that pixel values vary due to noise or the like. On the other hand, in digitally generated characters, noise does not enter, so the same value should be continuous. From such an assumption, the mode value of the block of interest is detected and extracted from the block as a character / line drawing. In the block of FIG. 12, since the mode value is “240”, this is the extracted color. Therefore, the identification information indicating the position of the extracted pixel is as shown in FIG. The extracted color of the character / line drawing and the identification information are compressed by lossless encoding.

  On the other hand, since the average value of the pixel data with the identification information “0” is “66”, the pixel data in the region with the identification information “1” is replaced with the average value. The pixel data (gradation information) after the replacement is as shown in FIG. This is compressed by lossy encoding.

In addition, a technique is known in which a multi-valued image is separated into a plurality of components and encoded separately (for example, Patent Document 2, Patent Document 3, and Patent Document 4).
Japanese Patent Laid-Open No. 04-326669 Japanese Patent Laid-Open No. 03-254573 Japanese Patent Laid-Open No. 04-040074 JP 2002-077631 A

  The above-mentioned Patent Document 1 is an effective method for improving the coding efficiency when the overwritten character color has the same value as in the block shown in FIG. However, on the other hand, when a character with gradation (hereinafter referred to as gradation character) is overwritten on a natural image, the pixel values of the character / line drawing part also vary. The same applies when an image including a character / line image is taken through an analog input device such as a scanner or a digital camera. As described above, there is a problem that it is difficult to increase the compression rate when the pixel values of the characters / line drawings are varied.

  This situation will be described by taking pixel data of a 4 × 4 pixel block shown in FIG. 15 as an example.

  In the pixel data shown in FIG. 15, characters are overwritten on a part of a natural image whose average level is “66”, and values “231”, “233”, “235”, “239”, and “240” are used. An example. In the conventional method, since the mode value having the highest appearance probability in the block is the extracted color, the extracted color in the above example is “65”, and the identification information indicating the pixel position at this time is shown in FIG. It becomes like. Since the average value of the pixel data with the identification information “0” is “144”, the pixels with the identification information “1” are replaced with the average value, as shown in FIG. Gradation information). This gradation information has hardly reduced the edge component of the pixel data shown in FIG. 15, and as a result, the compression rate cannot be increased.

  Further, even when a histogram in a block is obtained and a character part is extracted by generating a threshold value from the histogram, a replacement pixel (a pixel that is “1” in the identification information) is replaced with an extraction color at the time of decoding. End up. Therefore, it is difficult to reproduce the gradation in a block having gradation such as gradation characters.

  The present invention has been made in view of the above problems, and provides a technique for encoding an image in which a plurality of types of images are mixed with high quality and a high compression rate. In particular, the present invention includes pixel values that vary to some extent. Even if the gradation character / line drawing is mixed with the natural image, the gradation of the gradation character / line drawing can be reproduced with sufficient quality, and a technique with high coding efficiency can be provided.

In order to solve this problem, for example, an image encoding device of the present invention has the following configuration. That is,
Input means for inputting multi-valued image data in units of blocks composed of a plurality of pixels;
Each pixel in the block which is the input, as well as classified into first and second groups according to the value of each of the pixels, generating identification information which each pixel for generating identification information for identifying belongs to any group Means,
The average value of the first value of the pixel belonging to the group, the average value of the values of the pixels belonging to the second group, and, calculating means for calculating a difference value between the two averages,
The difference value is added to the value of each pixel belonging to the first group so that the difference between the average value of the first group and the average value of the second group becomes small, or the first group and by subtracting the difference value from the value of each pixel replacement means for replacing the values of the pixels belonging to the first group belonging to,
Coding means for coding the value of each pixel in the block after replacement, the difference value, and the identification information and outputting coded data of the block of interest.

  According to the present invention, an image in which a plurality of types of images are mixed can be encoded with high quality and a high compression rate. In particular, even gradation images and line drawings composed of pixel values that vary to some extent and natural images are mixed, gradations of gradation characters and line drawings can be reproduced with sufficient quality, and encoding efficiency can be improved. Highly encoded data can be generated.

  Hereinafter, embodiments according to the present invention will be described in detail with reference to the accompanying drawings.

<First Embodiment>
FIG. 1 is a block configuration diagram of an encoding apparatus according to the first embodiment.

  In the figure, reference numeral 251 denotes an input terminal for inputting a multi-valued image, and 203 denotes a buffer for temporarily storing pixel data when the multi-valued image is blocked as an input unit. 204 is identification information for determining pixel data to be extracted from the multi-valued image in the block (hereinafter referred to as “extracted color”) and identifying whether each pixel is a pixel to be extracted or a non-extracted pixel. This is an extraction unit for generating (one-bit determination information per pixel). In other words, the extraction unit 204 classifies each pixel in the input block into one of a first group that is a pixel value replacement target and a second group that is a non-replacement target. It functions as an identification information generation unit that generates identification information for identifying whether it belongs to the group. This identification information is determined according to the value of each pixel and is generated in association with each pixel position. Details of the extraction unit 204 will be described later.

  Reference numeral 206 denotes an average difference value generation unit for calculating an average value of pixel data for each region indicated by the identification information and outputting difference values (hereinafter referred to as average difference values) of a plurality of average values obtained there. is there. Reference numeral 207 denotes a replacement color generation unit for generating pixel data after replacement of the pixel to be extracted (hereinafter referred to as replacement color). Reference numeral 208 denotes a selector that selects and outputs one of the input multi-value image data and replacement color data. Reference numeral 209 denotes a first encoding unit for encoding the identification information such as run length. Reference numeral 210 denotes a second encoding unit for encoding the average difference value. These encoding units 209 and 210 generate lossless encoded data. Reference numeral 211 denotes a third encoding unit that encodes an output value of the selector 208 (hereinafter referred to as gradation information). The encoding unit 211 may be reversible, but is an irreversible encoding unit suitable for natural images such as JPEG in the embodiment. Reference numeral 212 denotes a multiplexing unit for packing each encoded data so as to be easily stored in a subsequent memory and outputting the encoded data as encoded data. Reference numeral 252 denotes an output terminal for outputting the encoded data.

  FIG. 18 shows the data structure of the encoded data file 1800 output from the multiplexing unit 212. As shown in the figure, the encoded data file 1800 includes a file header for storing information necessary for decoding such as image data size information (number of pixels in the horizontal and vertical directions), the number of color components, and the number of bits of each color. The encoded data of each block is stored following the file header. The encoded data of one block is either the block data 1801 or the block data 1802 shown in the figure. The block data 1801 has a block header indicating the corresponding type, and subsequently the encoded data of the identification information generated by the encoding unit 209 and the code of the average difference value generated by the encoding unit 210. Encoded data and gradation information encoded data generated by the encoding unit 211 are stored. Another block data 1802 has a block header indicating that it is of the corresponding type, and subsequently, data obtained by encoding the input multi-value image data by the encoding unit 211 is stored. The reason for this structure will be clarified from the following description.

  Next, the operation of the encoding apparatus in FIG. 1 will be described. In order to simplify the description, it is assumed that the multi-value image data to be encoded in the embodiment is a monochrome multi-value image, and each pixel has 8 bits (256 gradations), and the value indicates the density. To do.

  The multi-value image input from the input terminal 251 is temporarily stored in the buffer 203 and then sequentially read out in units of blocks, and the extraction unit 204, the average difference value generation unit 206, the replacement color generation unit 207, and the selector Sent to 208.

  The extraction unit 204 determines an extraction pixel and generates identification information for identifying whether each pixel in the block is an extraction pixel or a non-extraction pixel. Specifically, the extraction unit 204 generates identification information by binarizing the multi-valued image read in block units with a threshold value TH0. Here, “1” in the identification information indicates an extraction target pixel, and “0” indicates a non-extraction target pixel.

  Hereinafter, the operation of the extraction unit 204 will be described assuming that the input multi-valued image is 4 × 4 pixels shown in FIG. 15.

  Assuming that the threshold TH0 for determining the extraction target is “200”, pixel data of “200” or more among the above-mentioned pixel data is “1”, and pixels having a value less than that are binary “0”. It becomes. As a result, binary data data of 0 or 1 is generated for each pixel position in the block. FIG. 2 shows identification information of one block (4 × 4 pixels) binarized as described above. Here, the threshold value TH0 is obtained from a value set by a CPU or the like (not shown), or a block average value or a block histogram.

  In the average difference value generation unit 206, the average value (AVE1) of the pixel group whose identification information is “1” and the average value (AVE2) of the pixel group whose identification information is “0” are output from the extraction unit 204. Is calculated. The average difference value generation unit 206 calculates a difference value (difference information) between the two calculated average values, that is, an average difference value (D = AVE1-AVE2). Thus, the average difference value generation unit 206 supplies the calculated two average values (AVE1, AVE2) and the average difference value (D = AVE1-AVE2) to the replacement color generation unit 207 and the encoding unit 210.

  If the absolute value of the average difference value (D) is equal to or smaller than a predetermined threshold value, it is determined that it is not necessary to extract, and both the average difference value and the identification information are cleared to zero. Alternatively, even if the average difference value is set to 0, a replacement process described later substantially does not operate, so that only the average difference value may be cleared to 0. As a result, when the absolute value of the average difference value is equal to or smaller than the predetermined value, the encoded data of the block is only the encoded data of the gradation information as indicated by the block encoded data 1802 in FIG.

  Hereinafter, the operation will be described with reference to FIG. 3 showing the configuration of the average difference value generation unit 206.

  The multi-value image input from the input terminal 451 is sent to the ““ 1 ”region average value generation unit 401” and the ““ 0 ”region average value generation unit 402”.

  The identification information output from the extraction unit 204 is also input from the input terminal 452, and the value is inverted by the ““ 1 ”region average value generation unit 401” and the inversion circuit 404. Value generation unit 402 ".

  The ““ 1 ”region average value generation unit 401” calculates an average value (AVE1) of pixel data corresponding to “1” of the identification information.

  FIG. 4 is a diagram illustrating a configuration example of the ““ 1 ”region average value generation unit 401”. The operation will be described below with reference to FIG.

  In FIG. 4, reference numeral 551 denotes an input terminal for inputting identification information output from the extraction unit 204. Identification information input via the input terminal 551 is supplied to the selector 501 and the counter 502.

  The selector 501 includes input terminals 552 and 553. A fixed value “0” is preset in the input terminal 552. In addition, pixel data of a multi-value image input from the input terminal 451 is input to the input terminal 553. When the identification information (determination information) input to the input terminal 551 is “1”, the selector 501 selects and outputs the data of the input terminal 553, that is, pixel data. On the other hand, when the identification information is “0”, the selector 501 selects and outputs the fixed value “0” set in the input terminal 552.

  The accumulator 503 cumulatively adds the output values from the selector 501 and supplies the cumulative addition result to the divider 504.

  On the other hand, the counter 502 counts the number of identification information “1” for one block and supplies the count result to the divider 504. As described above, the identification information is composed of “1” or “0”.

  The output value of the accumulator 503 immediately after the final data of one block is input is the sum of the pixel values corresponding to the identification information “1” in the block of interest. The output value of the counter 502 is the number of identification information “1”. Therefore, the divider 504 divides the output value of the accumulator 503 by the output value of the counter 502, thereby obtaining the average value of the area where the identification information is “1”, that is, the average value (AVE1) of the extracted pixel data. Can do. The average value (AVE1) of the extracted pixels is output from the terminal 555. When the output value of the counter 502 is “0”, “0” is output from the output terminal 555.

  Further, since the average value (AVE1) is calculated for each block, it is necessary to clear the counter 502 and the accumulator 503 before inputting the head data of each block. For this purpose, the control unit (not shown) clears (resets) the counter 502 and the accumulator 503 via the initialization signal 554 when starting to calculate the average value (AVE1) of the extracted pixels in the block.

  Returning to FIG. 3, the “1” area average value (AVE1) that is the output value of the “1” area average value generation unit 401 ”is sent to the subtractor 403.

  The ““ 0 ”region average value generation unit 402” has the same configuration as the ““ 1 ”region average value generation unit 401” described with reference to FIG. 5 and performs the same operation. However, the identification information inverted by the inverting circuit 404 is input to the input terminal 551. Therefore, the output value of the ““ 0 ”region average value generation unit 402” is the region where the identification information input from the input terminal 452 is “0”, that is, the “0” region average that is the average value of pixel data that is not extracted pixels. Value (AVE2). The “0” area average value (AVE2) is sent to the subtractor 403.

  The subtractor 403 outputs the result (D = AVE1-AVE2) obtained by subtracting the “0” region average value (AVE2) from the “1” region average value (AVE1) to the output terminal 453.

  Hereinafter, a specific operation of the average difference value generation unit 206 will be described assuming that the 4 × 4 pixel block multi-value image data shown in FIG. 15 and the identification information shown in FIG. 2 are input.

  The pixel data of the multi-value image corresponding to the identification information “1” is “235”, “239”, “240”, “233”, “235”, “231”. Therefore, the average value “235” of the pixel data becomes the output value of the “1” area average value generation unit ”, that is, the“ 1 ”area average value (AVE1).

  Similarly, the pixel data of the multi-value image corresponding to the identification information “0” is “65”, “68”, “64”, “66”, “65”, “65”, “64”, “66”. "68" and "67". Therefore, the average value “65” of the pixel data becomes the output value of the “0” area average value generating unit, that is, the “0” area average value (AVE2). Therefore, the output value of the average difference value generation unit 206, that is, the average difference value (D) is “170” obtained by subtracting the “0” area average value from the “1” area average value by the subtractor 403.

  Returning to FIG. 1, the replacement color generation unit 207 calculates the average difference value (D) output from the average difference value generation unit 206 from the pixel data of each multilevel image in the block output from the buffer 203. Subtract. The result is output as a replacement color. However, if the result of subtraction is negative, the replacement color generation unit 207 clips the replacement color of the pixel of interest to “0” (boundary value) and outputs it.

  As an example of the operation of the replacement color generation unit 207, the input multi-value image is the pixel data of the 4 × 4 pixel block shown in FIG. 15, and the input average difference value (D) is the operation of the average difference value generation unit 206. The explanation will be made assuming that the average difference value “170” when an example is shown.

  The replacement color generation unit 207 subtracts the average difference value “170” from all the pixel data in the block. If the subtracted value is negative as described above, the replacement color value is output as 0. As a result, the replacement color generation unit 207 outputs the 4 × 4 pixel data shown in FIG. 5 as a replacement color.

  When the input identification information (determination information) is “0”, the selector 208 selects pixel data of the input multivalued image corresponding to the position of the identification information. On the other hand, when the identification information is “1”, the pixel data of the replacement color output by the replacement color generation unit 207 corresponding to the position of the identification information is selected. The gradation information of the block of interest can be obtained by repeating the above processing up to the block end pixel.

  For example, the 4 × 4 pixel block multi-valued image shown in FIG. 15 and the 4 × 4 pixel block replacement color shown in FIG. 5 are input to the selector 208 and the 4 × 4 pixel block shown in FIG. Is input to the selector 208 as a control signal. In the present embodiment, the difference between the average value (AVE1) of the pixel group whose identification information is “1” and the average value (AVE2) of the pixel group whose identification information is “0” is reduced. In addition, the value of one pixel group is replaced. Specifically, pixel data of a multi-value image is selected for a pixel corresponding to “0” in the identification information, while pixel data of the replacement color is selected for a pixel corresponding to “1” of the identification information. . As a result, the gradation value information of the 4 × 4 pixel block shown in FIG. 6 is output as the output value of the selector 208. As shown in the drawing, the pixel value at the position determined as the character / line drawing is almost the same as the pixel value of the non-character / line drawing. That is, a natural image that does not include a character line drawing is generated.

  The gradation information shown in FIG. 6 is compressed (lossy encoding) by the encoding unit 211 using, for example, JPEG encoding. Note that this lossy encoding method is not limited to JPEG, and other encoding suitable for natural images may be applied.

  On the other hand, the identification information output from the extraction unit 204 is compressed (losslessly encoded) by the encoding unit 209 using run-length encoding. This lossless encoding may be applied to other encoding suitable for encoding binary data. Similarly, the average difference value (D) output from the average difference value generation unit 206 is compressed (losslessly encoded) by the encoding unit 210. Note that the encoding by the encoding unit 209 and the encoding unit 210 greatly affects the image quality, so lossless encoding is desirable. On the other hand, since the encoding unit 211 is expected to have a high compression rate, lossy encoding is desirable, but lossless encoding may be used as long as the target compression rate is achieved.

  The multiplexing unit 212 combines the encoded data from the encoding unit 209, the encoded data from the encoding unit 210, and the encoded data from the encoding unit 211 so as to be easily stored in the subsequent memory, Is output from the output terminal 252. The multiplexing unit 212 has a memory that stores in advance pattern data indicating encoded data having all identification information “0”, and the encoded data and pattern data of the identification information output from the encoding unit 209 are stored in the memory. It is determined whether or not they match. If they do not match, that is, if the encoded data of the identification information output from the encoding unit 209 indicates that there is at least one identification information “1”, the encoding units 209, 210, The encoded data from 211 is combined to generate and output encoded data of the type of block data 1801 in FIG. On the other hand, if the encoded data of the identification information output from the encoding unit 209 matches the pattern data, that is, the encoded data output from the encoding unit 209 is all identification information “0”. In the case shown, the multiplexing unit 212 discards the encoded data from the encoding units 209 and 210, and uses the encoded data from the encoding unit 211 to convert the encoded data of the type of the block data 1802 in FIG. Generate and output. In this way, an encoded data file composed of the block encoded data 1801 or 1802 of FIG. 18 is generated as described above.

  In the above description, the multiplexing unit 212 compares the encoded data from the encoding unit 209 with the pattern data. However, the present invention is not limited thereto. For example, when the extraction unit 204 generates identification information for one block, the extraction unit 204 supplies a signal indicating whether or not all of the identification information is “0” to the multiplexing unit 212. The multiplexing unit 212 may generate one of the block data 1801 and 1802 in accordance with this signal from the extraction unit 204.

  Next, the image decoding process in this embodiment is demonstrated. FIG. 7 is a block configuration diagram of the image decoding apparatus in the embodiment.

  In the figure, reference numeral 851 denotes an input terminal for inputting encoded data read from a memory (not shown), and reference numeral 801 denotes identification information obtained by encoding the encoded data, an encoded average difference value (D), and a code. The separation unit separates the converted gradation information. Reference numeral 802 denotes a first decoding unit for decoding the identification information, 803 denotes a second decoding unit for decoding the average difference value (D), and 804 denotes the gradation information. Is a third decryption unit for decrypting. Reference numeral 805 denotes an image restoration unit that restores a multi-valued image and outputs the restoration result.

  One block decoding processing in the above configuration will be described below.

  The encoded data for one block input from the input terminal 851 is equal to the encoded data output from the output terminal 251 in FIG.

  Therefore, the separation unit 801 analyzes the block header of the encoded data for the input target block, and determines whether the encoded data of the target block is the type of the block data 1801 or 1802 in FIG. When it is determined that the target block is the type of the block data 1801, the encoded data of the identification information, the encoded data of the average difference value, and the encoded data of the gradation information that follow the block header are separated and separated. Each encoded data is supplied to corresponding decoding sections 802, 803, and 804.

  The separating unit 801 has a memory that stores in advance the pattern data of encoded data having all identification information “0” and the pattern data of encoded data having an average difference value “0”. If it is determined that the encoded data of the block of interest is the type of the block data 1802, the separating unit 801 decodes the pattern data of the encoded data having all identification information “0” stored in advance in its own memory. Output to the encoding unit 802, and also outputs to the decoding unit 803 the pattern data of the encoded data having an average difference value “0” stored in its own memory. Then, the separation unit 801 outputs the encoded data of the gradation information subsequent to the input block header to the decoding unit 804.

  The decoding unit 802 decodes the input coding identification information and outputs the result to the image restoration unit 805. The decoding unit 802 corresponds to the encoding unit 209 in FIG. 1 and performs lossless decoding. Therefore, the identification information output from the decoding unit 802 completely matches the identification information output from the extraction unit 204 in FIG.

  The decoding unit 803 corresponds to the encoding unit 210 in FIG. 1 and performs lossless decoding. Therefore, the average difference value decoded by the decoding unit 803 completely coincides with the average difference value (D) before encoding output from the average difference value generation unit 206 of FIG.

  The decoding unit 804 decodes the input gradation information for one block. Since the decoding unit 804 in the embodiment decodes lossy encoded data, the gradation data output from the selector 208 in FIG. 1 is not completely the same, but the gradation with moderate gradation maintained. Information can be restored.

  The image restoration unit 805 outputs the gradation information output from the decoding unit 804 as it is for the area of “0” in the identification information output from the decoding unit 802. Further, the image restoration unit 805 outputs, from the decoding unit 803, the gradation information output from the decoding unit 804 for the area “1” of the identification information (determination information) output from the decoding unit 802. The average difference value (D) is added and output.

  For example, the input to the image restoration unit 805 is the average information calculated when the identification information (determination information) of the 4 × 4 pixel block shown in FIG. 2 and the operation example of the average difference value generation unit 206 shown in FIG. It is assumed that the difference value “170” is the gradation information of the 4 × 4 pixel block shown in FIG. In this case, the image restoration unit 805 adds the average difference value “170” to the gradation information corresponding to the region “1” of the identification information, and thus one block output from the image restoration unit 805. As the image data, a 4 × 4 multi-valued image shown in FIG. 9 is restored.

  As described above, according to the present embodiment, even if an image block as shown in FIG. 15 is input, in the lossy encoding process, as shown in FIG. Key information. For this reason, entropy at the time of gradation information encoding is greatly reduced, and encoding efficiency is greatly improved.

  On the other hand, since the identification information) and the average difference value (D) are losslessly encoded, even in a multi-value image in which characters, line drawings, and natural images are mixed, image quality deterioration hardly occurs.

  Furthermore, since the gradation of the extracted pixels is almost restored by the gradation information, image quality deterioration is hardly detected even in a multi-value image in which characters that do not fit in one level such as gradation characters and a natural image are mixed.

  In the above embodiment, when the separating unit 801 determines that the encoded data of the block of interest is the type of the block data 1802, the separating unit 801 transmits the encoded data (pattern data) of dummy identification information to the decoding unit 802. The dummy average difference value encoded data (pattern data) is output to the decoding unit 803. However, this does not limit the present invention. For example, it may be as follows.

  The separation unit 801 analyzes the block header, determines whether the encoded data of the block of interest is the block data 1801 or 1802, and outputs a signal indicating the determination result to the image restoration unit 805. If the separating unit 801 determines that the encoded data of the block of interest is the type of the block data 1802, the separating unit 801 outputs only the encoded data of the gradation information subsequent to the block header to the decoding unit 804. The image restoration unit 805 performs the above process when a signal indicating that the block of interest is of the block data 1801 type is input. On the other hand, when a signal indicating that the block of interest is of the block data 1802 type is input, only the decoding result from the decoding unit 804 is selected and output. Even if it does as mentioned above, the result similar to the said embodiment can be obtained.

  In the above embodiment, the pixel having the identification information “1” is the extraction pixel, but the pixel having the identification information “0” may be the extraction pixel. In this case, the replacement pixel is also a pixel whose identification information is “0”, and all the identification information when the absolute value of the average difference value (D) is equal to or smaller than a predetermined value is cleared to 1. Further, even if the average difference value is set to 0, the replacement process substantially does not operate. Therefore, instead of clearing all the identification information to “1”, the average difference value (D) may be cleared to 0.

  In the above embodiment, one block has a 4 × 4 pixel size. However, if the encoding unit 211 performs JPEG encoding processing, it is desirable that the size is 8 × 8 or an integer multiple thereof. It should be noted that the 4 × 4 size shown in the embodiment is an example for simple explanation.

  In addition, the present invention is not particularly limited to the case where the character portion and the other portion are separated. The present invention can be appropriately used in a situation where a high value group and a low value group exist within a block in a certain area and these are encoded.

<Modification of First Embodiment>
The first embodiment may be realized by a computer program. An example of this will be described below.

  FIG. 19 is a block diagram of an information processing apparatus (such as a personal computer) applied in the present modification.

  In the figure, 1901 is a CPU that controls the entire apparatus, and 1902 is a ROM that stores a boot program and BIOS. Reference numeral 1903 denotes a RAM used as a work area for the CPU 1901. Reference numeral 1904 denotes a large-capacity external storage device such as a hard disk, which stores an OS (operating system) and various data files including the application program of this modification. Reference numeral 1905 denotes a keyboard, and 1906 denotes a mouse which is a pointing device. Reference numeral 1907 denotes a display control unit, which includes a video memory, a drawing process in the video memory, and a controller that outputs an image from the video memory as a video signal to the outside. Reference numeral 1908 denotes a display device (CRT, liquid crystal display device or the like) that receives and displays a video signal from the display control unit 1907. Reference numeral 1909 denotes a network interface, 1910 denotes a scanner interface, and 1911 denotes an image scanner.

  In the above configuration, when the power of the apparatus is turned on, the CPU 1901 loads the OS from the external storage device 1904 to the RAM 1903 according to the boot program of the ROM 1902 so that the apparatus functions as an information processing apparatus. Thereafter, when the activation of the application of this modification is instructed by the keyboard 1905 or the mouse 1906, the CPU 1901 loads the corresponding application from the external storage device 1904 to the RAM 1903 and executes it. As a result, the apparatus functions as an image processing apparatus.

  The following shows the processing procedure executed by the CPU 1901 after this application is activated. Here, an example will be described in which a document image is read from the image scanner 1911, compressed and encoded, and saved as a file in the external storage device 1904.

  When the application is executed, a buffer for temporarily storing image data read by the image scanner 1911 and an area for storing various variables are secured in the RAM 1903. In order to simplify the description here, it is assumed that the image scanner 1911 is set to read a document in a monochrome multi-value mode (8 bits per pixel). Image data read by the image scanner 1911 is a luminance value. Note that this has the opposite meaning to the density of the first embodiment, and 0 and 1 when binarizing also have the opposite meaning. That is, the difference in brightness and density is not an essential difference. This is because, in the present invention, it is only necessary to separate pixels of character / line drawing and non-character / line drawing.

  FIG. 20 is a flowchart illustrating an image encoding processing procedure of the application according to the present modification. In the following description, it is assumed that image data read by the image scanner 1911 is stored in an input buffer in the RAM 1903. Also, description will be made assuming that the header information of the file to be written to the external storage device 1904 has already been generated.

  First, in step S1, one block of image data is read from the input buffer. In this modification, the size of one block is 8 × 8 pixels. The input image data for one block is expressed as IM (i, j) (i, j = 0, 1, 2,... 7).

  Next, in step S2, each input pixel value in one block is compared with a preset threshold value TH0 and binarized. Similar to the first embodiment, this binarization result is called identification information and is represented by B (i, j).

In step S3, the sum of the pixel values IM (i, j) for which B (i, j) = 1 is calculated, and the average value AVE1 is calculated. If an arithmetic expression is shown, it can be expressed by the following expression.
AVE1 = {ΣB (i, j) × IM (i, j)} / ΣB (i, j)
Here, Σ is a summation function of i, j = 0, 1,. When ΣB (i, j) = 0, AVE = 0.

  It will be apparent that the process of step S3 corresponds to the process of the “1” area average value generation unit 401 in FIG.

In step S4, the sum total of the pixel values IM (i, j) where B (i, j) = 0 is calculated, and the average value AVE2 is calculated.
AVE2 = {Σ (1-B (i, j)) × IM (i, j)} / Σ (1-B (i, j))
It can be calculated by When Σ (1-B (i, j)) = 0, AVE2 = 0.

  It will be apparent that the process of step S4 corresponds to the process of the “0” area average value generation unit 401 in FIG.

  In step S5, the difference value D is obtained by subtracting AVE2 from AVE1. That is, it corresponds to the processing of the subtracter 403 in FIG.

  In step S6, it is determined whether or not the absolute value of the difference value D is equal to or less than a preset threshold value TH1. When the determination in step S6 is Yes, all pixel values existing in the block of interest have substantially the same value. Therefore, for the block of interest, the process proceeds to step S7, and JPEG encoding (lossy encoding) is performed. That is, the encoded data of the block of interest is the block encoded data 1802 in FIG.

On the other hand, if the determination in step S6 is No, that is, if it is determined that the absolute value of the difference value D exceeds the threshold, the process proceeds to step S8, and from the pixel value for which B (i, j) = 1, Substitution processing is performed by subtracting the difference value D. The gradation pixel value after the post-replacement processing is expressed as T (i, j) as follows.
When B (i, j) = 1, T (i, j) = IM (i, j) −D
However, if T (i, j) <0, T (i, j) = 0.
When B (i, j) = 0, T (i, j) = IM (i, j)

  In step S9, the gradation pixel value T (i, j) obtained by the replacement process is JPEG-encoded (lossy encoding).

  Next, in step S10, the binary identification information B (i, j) is losslessly encoded, and in step S11, the difference value D is also losslessly encoded.

  Thereafter, the process proceeds to step S12, and the generated encoded data is output as a part of the file. Incidentally, the encoded data of the block of interest after the processes of steps S8 to S11 are in the format of the block encoded data 1801 in FIG.

  Thereafter, in step S13, it is determined whether or not the encoding process has been completed for all the blocks. If not, the processes in and after step S1 are repeated.

  As a result, encoded data similar to that in the first embodiment can be generated.

  Next, the decoding processing procedure of this modification will be described with reference to the flowchart of FIG. It is assumed that the encoded data file to be decoded is displayed by displaying an appropriate GUI screen on the display device 1908 and the user operates the mouse 1906 to select it.

  First, in step S21, one block of encoded data is input from the selected file. In step S22, the block header is analyzed, and it is determined which format is the data of blocks 1801 and 1802 in FIG.

  If it is determined that the input encoded data is composed only of the block data 1802 format, that is, encoded data of gradation information, the process proceeds to step S23 to perform JPEG decoding processing.

  On the other hand, when it is determined that the input encoded data is composed of the block data 1801 format, that is, encoded data of identification information, encoded data of difference values, and encoded data of gradation information The process proceeds to step S24.

In step S24, the binary identification information B (i, j) is decoded, and in step S25, the difference value D is decoded. In step S26, the gradation information T (i, j) is decoded. Thereafter, reverse replacement processing is performed in step S27. If the image data after the reverse replacement processing is IM ′ (i, j), it is as follows.
When B (i, j) = 1, IM ′ (i, j) = T (i, j) + D
When B (i, j) = 0, IM ′ (i, j) = T (i, j)

  In step S28, the image data for one block obtained by decoding in step S23 or step S27 is output. If the output destination is a display device, it may be output to the display control unit 1907. If the decoded image data is stored as a file, the external storage device 1904 may be used.

  Thereafter, the process proceeds to step S29, where it is determined whether or not the decoding process for all blocks has been completed. If not, the processes in and after step S21 are repeated.

  As described above, like the present modification, the same operational effects as those of the first embodiment described above can be obtained by a computer program.

<Second Embodiment>
In the second embodiment, functions are added in order to obtain further effects from the first embodiment described above.

  FIG. 10 shows a block configuration diagram of an encoding apparatus according to the second embodiment.

  The configuration in FIG. 10 is the same as the configuration in FIG. 1 according to the first embodiment except that a low-pass filter unit 1101 is added.

  In the first embodiment, the encoding unit 211 directly encodes the output value of the selector 208 in FIG. On the other hand, in the second embodiment, as shown in FIG. 10, the output value of the selector 208, that is, the high frequency component of the gradation information is suppressed using the low-pass filter unit 1101. Then, the encoding unit 211 encodes the image data (gradation information) in which the high-frequency component after the low-pass filter processing is suppressed. The merit of performing the low-pass filter processing (hereinafter referred to as LPF) is not only removing the noise component, but also smoothing the boundary between the extracted pixel (the pixel whose identification information is “1”) and the non-extracted pixel. Therefore, further improvement in compression efficiency can be expected. In addition, as described above, the edge in the block has already been extracted by the subtraction process using the average difference value (D), and the edge of the restored image is lost even if a low-pass filter is applied. I can't. On the contrary, since the edge damaged at the time of input remains as an edge in the gradation information after the extraction (replacement) processing, the damaged edge is removed by this low-pass filter processing, and the sharp edge at the time of restoration is removed. There is also an effect.

  Hereinafter, a specific example in which the edge is improved will be described.

  FIGS. 11A to 11F are waveform examples showing the operation of the second embodiment.

  FIG. 11A shows an input waveform, which is an 8 × 1 one-dimensional block here. This waveform (block) is divided into regions by a predetermined threshold (here, block average value), and identification information is extracted as shown in FIG. Using this identification information, an average value for each region is obtained ((C) in the figure), and an average difference value is obtained.

  11D is obtained by subtracting this average difference value from the input waveform (“1” region (pixels whose identification information is “1”) in FIG. 11A). If the result of subtraction is negative, it is clipped to 0 as described above, and this tone information is subjected to LPF and compressed and decompressed, resulting in the waveform shown in FIG. The original waveform (block) is restored as shown in FIG. 11F by adding the average difference value to the “1” region (the pixel whose identification information is “1”) in FIG. As shown by the arrow in FIG. 11F, it can be seen that the edge of the boundary portion of the “1” region is steep.

  As described above, according to the second embodiment, in addition to the operational effects of the first embodiment (and its modifications), the noise component can be removed and a sharp edge can be obtained during restoration. Become.

  Obviously, the processing corresponding to the second embodiment can be realized by a computer program.

  In the first and second embodiments, the pixel group with the identification information “1” is the extraction target, and the pixel group with the identification information “0” is the non-extraction target. Then, the difference average value is subtracted from the value of each pixel included in the extraction target pixel group. However, this may be reversed. That is, a pixel group having identification information “0” may be extracted, and the average difference value may be added to the value of each pixel included in the pixel group. In this case, when the range that the input pixel can take is exceeded due to addition of the average difference, clipping is performed to the upper limit value (boundary value). In short, the difference average value may be added or subtracted so that the average value of each of the extraction target pixel group and the non-extraction pixel group becomes small.

<Third Embodiment>
In the first embodiment, when generating a replacement color, the average difference value is subtracted from each multi-valued image data in the block, and if the result is negative, the replacement color is clipped to “0” (lower limit value). And output. This is the simplest and most effective countermeasure for the case where the encoding unit 211 has to input a positive value as in the JPEG encoder. This is based on the fact that even if there are pixels clipped in the replacement color, if the number of pixels is small and the clip width is small, the image quality after restoration will not be greatly affected (reference example: figure). 11).

  However, although it is extremely rare, depending on the input image or depending on the threshold value used to generate the identification information in the extraction unit 204, the image quality after restoration may be affected. Hereinafter, a specific example will be described with reference to FIG. FIG. 22A shows an input waveform, which is a one-dimensional block of 8 × 1 pixels here. Identification information is generated by performing region decomposition on the waveform (block) with a predetermined threshold ((B) in the figure). Then, an average value for each region is obtained using the identification information ((C) in the figure), and the obtained average difference value is subtracted from the pixel data of the “1” region. Depending on the threshold and the input waveform, the subtraction result may be negative. Normally, even if the pixel value is clipped to “0” as described in the first embodiment, the image quality is not greatly affected. However, as shown in FIG. 4D, there are many negative pixels, or they may continue. In this case, after the compression / expansion (FIG. (E)), the average difference is added, and as shown in the restored output waveform (FIG. (F)), there is a gradation in the input waveform (FIG. (A)). Will be lost.

  In the third embodiment, functions are added in order to solve such problems.

  FIG. 23 shows a block configuration diagram of an encoding apparatus according to the third embodiment.

  The configuration of FIG. 23 is different from the configuration of FIG. 1 according to the first embodiment in that a replacement color generation unit 2301 is provided instead of the replacement color generation unit 207, and a replacement color generation unit 2302, a comparison unit 2303, and a selector. The difference is that 2304 is added. Other parts are the same as those in the first embodiment.

  The replacement color generation unit 2301 further includes a clip counter that functions as a first counting unit described later, in addition to the replacement color generation unit 207 of FIG. 1 described in the first embodiment. The clip counter is incremented when the identification information is “1” and the result obtained by subtracting the average difference value (D) from the pixel data of each multi-valued image in the block output from the buffer 203 is negative. . The replacement color generation unit 2301 outputs the replacement color (a) by the same method as the replacement color generation unit 207, and outputs the value of the clip counter as the clip count value (a). After the replacement color (a) and the clip count value (a) of the reference block are output, the clip counter is cleared to “0”.

  The clip count value (a) represents the number of pixels clipped to “0” (lower limit value) among the replacement color pixels whose identification information in the block corresponds to “1”.

  When the input identification information (determination information) is “0”, the selector 208 selects and outputs pixel data of the input multivalued image corresponding to the position of the identification information. On the other hand, when the identification information is “1”, the selector unit 208 selects and outputs the pixel data of the replacement color (a) output from the replacement color generation unit 2302 corresponding to the position of the identification information. By repeating the above processing up to the block end pixel, the gradation information (a) of the block of interest can be obtained.

  A specific operation of the replacement color generation unit 2301 and the selector 208 will be described on the assumption that multi-value pixel data of a 4 × 4 pixel block shown in FIG. 24 is input.

  In the illustrated case, since the block average value is “76”, the identification information is as shown in FIG. 24 and 25, the average difference value (D) is “200”.

  The replacement color generation unit 2301 subtracts the average difference value “200” from all the pixel data in the block. Similar to the replacement color generation unit 207 described in the first embodiment, the replacement color generation unit 2301 clips and outputs the replacement color value to 0 when the subtracted value is negative. If the identification information at that time is “1” indicating the extracted pixel, the clip counter is incremented. In this operation example, since there are two pixels corresponding to this, the clip counter indicates “2”. As a result, the replacement color generation unit 2301 outputs 4 × 4 pixel data as the replacement color (a) shown in FIG. 26, and outputs the clip counter value “2” as the clip count value (a). .

  In the selector 208, among the pixels of the replacement color (a) shown in FIG. 26, among the pixels corresponding to “1” of the identification information shown in FIG. 25, and among the pixels of the multivalued image shown in FIG. A pixel corresponding to the identification information “0” is selected and output. As a result, the selector 208 outputs the gradation information (a) shown in FIG. As shown in the drawing, the pixel value at the position determined as the character / line drawing is almost the same as the pixel value of the non-character / line drawing.

  The replacement color generation unit 2302 adds the average difference value (D) output from the average difference value generation unit 206 from the pixel data of each multi-valued image in the block output from the buffer 203. The result is output as a replacement color (b). However, if the addition result exceeds the range that can be taken by the pixel data, it is clipped to the upper limit value (boundary value).

  Further, the replacement color generation unit 2302 includes a clip counter that functions as a second counting unit, like the replacement color generation unit 2301. However, the clip counter of the replacement color generation unit 2302 is different from the clip counter of the replacement color generation unit 2301. That is, the clip counter of the replacement color generation unit 2302 has the identification information “0” and the result of adding the average difference value (D) to the pixel data of each multi-valued image in the block output from the buffer 203. It is incremented when the upper limit (boundary value) of the range that pixel data can take is exceeded. The value of the clip counter is output as a clip count value (b). After the replacement color (b) of the reference block and the clip count value (b) are output, the clip counter is cleared to “0”.

  The clip count value (b) represents the number of pixels clipped to the upper limit value (boundary value) among the replacement colors whose identification information in the block is “0”.

  The selector 2304 has the same function as the selector 208. However, since the identification information (determination information) is inverted and input to the selector 2304, when the identification information (determination information) is “1”, the pixel data of the input multivalued image corresponding to the position of the identification information is selected. And output. On the other hand, when the identification information is “0”, the selector 2304 selects and outputs the pixel data of the replacement color (b) output by the replacement color generation unit 2302 corresponding to the position of the identification information. By repeating the above processing up to the block end pixel, the gradation information (b) of the block of interest can be obtained.

  As described above, the selector 208 functions as a first replacement unit, and the selector 2304 functions as a second replacement unit.

  Specific operations of the replacement color generation unit 2302 and the selector 2305 will be described on the assumption that multi-value pixel data of a 4 × 4 pixel block shown in FIG. 24 is input.

  At this time, since the block average value is “77”, the identification information is as shown in FIG. 24 and 25, the average difference value (D) is “200”. However, since the inverted identification information is input to the replacement color generation unit 2302, a pixel “1” in the identification information is a non-extracted pixel and “0” is an extracted pixel.

  The replacement color generation unit 2302 adds the average difference value “200” to all the pixel data in the block. When the added value is the upper limit value (255 in this case), the replacement color generation unit 2302 clips the replacement color value to “255” and outputs it. If the identification information at that time is “0” indicating the extracted pixel, the clip counter is incremented. In this operation example, there is no corresponding pixel, and the clip counter indicates “0”. As a result, the replacement color generation unit 2302 outputs the 4 × 4 pixel data shown in FIG. 28 as the replacement color (b), and outputs the clip counter value “0” as the clip count value (b). .

  In the selector 2304, among the pixels of the replacement color (b) shown in FIG. 28, among the pixels corresponding to the identification information “0” shown in FIG. 25 and the pixels of the multivalued image shown in FIG. A pixel corresponding to identification information “1” is selected and output. As a result, the gradation information (b) output from the selector 2302 is as shown in FIG. As shown in the drawing, the pixel value at the position determined as a non-character / line drawing is almost the same as the pixel value of the character / line drawing.

  The comparison unit 2303 compares the clip count value (a) output from the replacement color generation unit 2301 with the clip count value (b) output from the replacement color generation unit 2302 at the end of processing of one block. . Then, the comparison unit 2303 outputs “0” as the determination signal SEL when the clip count value (a) is the same as or smaller than the clip count value (b), and “1” otherwise.

  The selector 2305 has a block buffer (not shown). When the SEL signal is “0” in synchronization with the determination signal of the comparator 2303, the gradation information (a) input from the selector 208 is received. Select and output. On the other hand, the selector 2305 selects and outputs the gradation information (b) input from the selector 2304 when the SEL signal is “1”. That is, the selector 2305 selects the gradation information with the smaller number of clipped pixels.

  The gradation information output from the selector 2305 is compressed (lossy encoded) by the encoding unit 211 using the same compression method as in the first embodiment. Further, the identification information output from the extraction unit 204 and the average difference value output from the average difference value generation unit 206 are compressed by the encoding unit 209 and the encoding unit 210, respectively, in the same manner as in the first embodiment. It is compressed (lossless encoding) by the method.

  The multiplexing unit 2306 includes the encoded data compressed by the encoding unit 209, the encoding unit 210, and the encoding unit 211, and the type of gradation information encoded by the encoding unit 211 (gradation information ( The above SEL signal (selection information) for notifying the composite unit of a) or gradation information (b)) is combined so as to be easily stored in the subsequent memory, and is output from the output terminal 252.

A sign bit may be added to the average difference value instead of the SEL signal, and the average difference value may be stored in the memory as a negative value when the SEL signal is “1”. In this case, at the time of decoding, the decoding method is not switched by the SEL signal, but the image can be restored by adding the average difference value to the pixels whose identification information is “1”. In the above case, it is not always necessary
Note that the pixel value of the identification information “1” is not necessarily greater than the pixel value of the identification information “0” (the relationship is reversed when the average difference value is negative).

  As described above, according to the third embodiment, since the occurrence of clipping due to the replacement operation is almost eliminated, it is possible to restore an image with no gradation collapse.

  Obviously, the processing corresponding to the third embodiment can be realized by a computer program.

  It goes without saying that the same effect can be obtained even if the low-pass filter shown in the second embodiment is applied to the third embodiment.

<Fourth Embodiment>
In the third embodiment, a difference value identification (selection) signal is required. In the fourth embodiment, the pixel value after the replacement becomes negative without the identification (selection) signal by devising the setting of the difference value (so that the minimum value of the region 1 does not become negative). To solve the problem.

  FIG. 30 shows a block configuration diagram of an encoding apparatus according to the fourth embodiment.

  The configuration of the fourth embodiment in FIG. 30 is different from the configuration of FIG. 1 in the first embodiment in that an average difference value replacement unit 2301 is added, and the other portions are the same as those in the first embodiment. It is the same as the form. Only the parts different from the first embodiment will be described below.

  The average difference value replacement unit 2301 outputs the minimum value of the pixel corresponding to “1” of the identification information output from the extraction unit 204 in the block output from the buffer 203 and the average difference value generation unit 206. The difference value is compared, and the smaller value is selected and output. Hereinafter, the value selected and output by the average difference value replacement unit 2301 is referred to as a correction value.

  Details of the average difference value replacement unit 2301 will be described below.

  FIG. 31 is a block diagram of the average difference value replacement unit 2301.

  The minimum value detection unit 2401 receives the pixel data of each multi-value image in the block output from the buffer 203, and determines the minimum value of the pixel data corresponding to “1” of the identification information output from the extraction unit 204. Output. The comparison unit 2402 compares the minimum value with the difference value output from the average difference value generation unit 206. If the difference value is smaller than the minimum value, the comparison unit 2402 sets “0”, otherwise Outputs “1” as a selection signal. Based on the selection signal, the selection unit 2403 selects a smaller one of the minimum pixel value and the difference value of the multi-valued image, and outputs the selected value as a correction value.

  Next, the operation of the average difference value replacement unit 2301 will be described. When the input multi-value image is the pixel data of the 4 × 4 pixel block shown in FIG. 24, the difference value (D) is “200” and the identification information is as shown in FIG.

  At this time, the minimum value of the pixel data corresponding to the identification information “1” is “104”, and the minimum value is smaller when the minimum value is compared with the difference value (D). Therefore, the average difference value replacement unit 2301 outputs the minimum value “104” having a small comparison result as a correction value.

  Subsequent processing is the same as in the first embodiment. However, the replacement color generation unit 207 subtracts the replacement value output from the average difference value generation unit 206 from the pixel data of each multi-valued image in the block output from the buffer 203. At this time, the result of subtraction may be negative. This is because when it becomes negative, the selector 208 does not select the value.

  FIG. 32 is a diagram for explaining the effect of the fourth embodiment.

  FIG. 32A shows an input waveform, which is an 8 × 1 one-dimensional block here. The waveform (block) is subjected to region decomposition with a threshold value (for example, block average value) to generate identification information ((B) in the figure). Then, the average value for each area is obtained using the identification information ((C) in the figure), and the obtained temporary average difference value is compared with the pixel data that is the minimum value of the “1” area. The smaller one is used as an average difference value ((D) in the figure) and subtracted from the input waveform. As a result of the subtraction, there is no negative pixel as shown in FIG. Therefore, the gradation is not lost as in the output waveform (FIG. (G)) restored by adding the average difference after compression / expansion (FIG. (F)).

  In the above description, the correction value is subtracted from the pixel value “1” of the identification information. However, the correction value may be added to the pixel value of the identification information “0”. In the latter case, the average difference value replacement unit 2301 obtains the maximum pixel value of the pixel corresponding to “0” of the identification information output from the extraction unit 204 in the block output from the buffer 203. Then, the average difference value replacement unit 2301 compares the difference between the maximum pixel value and the upper limit value (“255” in the embodiment) that the pixel value can take with the average difference value output from the average difference value generation unit 206. Then, the smaller one is output as a correction value. The replacement color generation unit 207 adds the replacement value output from the average difference value generation unit 206 to the pixel data of each multi-valued image in the block output from the buffer 203. At this time, the added value may exceed the upper limit value. This is because when the upper limit value is exceeded, the selector 208 does not select that value.

  As described above, according to the fourth embodiment, no clip is generated due to the replacement operation, so that an image without gradation collapse can be restored.

  Obviously, the processing corresponding to the fourth embodiment can be realized by a computer program.

  It goes without saying that the same effect can be obtained even if the low-pass filter shown in the second embodiment is applied to the fourth embodiment.

  In each of the above embodiments, the block size is described as 4 × 4 (or 8 × 1) for ease of explanation, but normally encoding for compressing gradation information (eg, orthogonal transform size). It is more desirable to match. For example, when JPEG is used, an integer multiple of the DCT block size (8 × 8) is preferable. For example, if 8 × 16 pixels are one block, there are two 8 × 8 pixels in this block. Therefore, the encoding unit 211 may perform DCT transform, quantization, and entropy encoding processing on two 8 × 8 pixel blocks.

  Further, as in the modification of the first embodiment, the present invention can be realized by a computer program. Usually, the computer program is stored in a computer-readable storage medium such as a CD-ROM. The medium can be executed by setting it in a computer reader (CD-ROM drive or the like) and copying or installing it in the system. Therefore, it is obvious that such a computer readable storage medium falls within the scope of the present invention.

It is a block block diagram of the encoding apparatus in 1st Embodiment. It is a figure which shows the identification information of a 4x4 pixel block when threshold value TH0 in 1st Embodiment is set to "200". It is a block block diagram of the average difference value production | generation part of FIG. It is a block block diagram of the "1" area average value generation part of FIG. It is a figure which shows the example of an output value of the replacement color production | generation part of FIG. It is a figure which shows the example of an output of the selector of FIG. It is a block block diagram of the image restoration apparatus in 1st Embodiment. It is a figure which shows the example of the gradation information of the 4x4 pixel block input into the image restoration part of FIG. FIG. 8 is a diagram illustrating an example of pixel data of a 4 × 4 pixel block restored by the image restoration apparatus in FIG. 7. It is a block block diagram of the encoding apparatus in 2nd Embodiment. It is an example of a waveform for explaining operation of a 2nd embodiment. It is a figure which shows the example of the pixel block of the encoding target in a prior art. It is a figure which shows the identification information in the prior art of FIG. It is a figure which shows the example of the gradation information after the pixel replacement in a prior art. It is a figure which shows the example of the pixel block of the encoding object in embodiment. It is a figure for demonstrating the problem of a prior art. It is a figure for demonstrating the problem of a prior art. It is a figure which shows the data structure of the encoding data produced | generated with the encoding apparatus in embodiment. It is a block block diagram of the apparatus in the modification of 1st Embodiment. It is a flowchart which shows the encoding process sequence of the apparatus of FIG. It is a flowchart which shows the decoding processing procedure of the apparatus of FIG. It is a figure for demonstrating the malfunction by a replacement process. It is a block diagram of the encoding apparatus in 3rd Embodiment. It is a figure which shows the example of the pixel data of a 4x4 pixel block input into the replacement color production | generation part of FIG. It is a figure which shows the example of the identification information of a 4x4 pixel block input into the replacement color production | generation part of FIG. It is a figure which shows the example of the replacement color of a 4x4 pixel block output from the 1st replacement color production | generation part of FIG. FIG. 24 is a diagram illustrating an example of gradation information of a 4 × 4 pixel block output from the first selector of FIG. 23. It is a figure which shows the example of the replacement color of a 4x4 pixel block output from the 2nd replacement color production | generation part of FIG. It is a figure which shows the example of the gradation information of the 4x4 pixel block output from the 2nd selector of FIG. It is a block diagram of the encoding apparatus in 4th Embodiment. It is a block diagram which shows the example of the average difference value replacement part of FIG. It is a figure which shows the effect of the encoding apparatus in 4th Embodiment.

Claims (20)

Input means for inputting multi-valued image data in units of blocks composed of a plurality of pixels;
Identification information generation for classifying each pixel in the input block into first and second groups according to the value of each pixel and generating identification information identifying which group each pixel belongs to Means,
Calculating means for calculating an average value of the pixels belonging to the first group, an average value of the pixels belonging to the second group, and a difference value between the two average values;
The difference value is added to the value of each pixel belonging to the first group so that the difference between the average value of the first group and the average value of the second group becomes small, or the first group Substituting means for substituting the value of pixels belonging to the first group by subtracting the difference value from the value of each pixel belonging to
An image encoding apparatus comprising: encoding means for encoding the value of each pixel in the block after replacement, the difference value, and the identification information, and outputting encoded data of the block of interest.   The replacement means sets the upper limit value when the value of the pixel of interest after replacement exceeds the upper limit value of the range that the pixel can take, and sets the lower limit value when the value is lower than the lower limit value of the range that the pixel can take. The image encoding device according to claim 1, wherein the image encoding device is set. Furthermore, it comprises low pass filter processing means for executing low pass filter processing on the block replaced by the replacement means,
The image encoding apparatus according to claim 1, wherein the encoding unit encodes a pixel value in the block after the low-pass filter processing.   The image encoding apparatus according to claim 1, wherein the encoding unit performs lossless encoding on the difference value and the identification information.   5. The image encoding apparatus according to claim 4, wherein the encoding unit performs lossy encoding on the value of each pixel in the block after being replaced by the replacement unit.   6. The image encoding apparatus according to claim 5, wherein the size of the input unit block of the input unit is an integral multiple of the size of the block to be lossy encoded by the encoding unit. A determination unit that determines whether an absolute value of the difference value calculated by the calculation unit is equal to or less than a preset threshold value;
When the determination means determines that the absolute value of the difference value is equal to or less than the threshold value, the replacement means is not replaced, and the pixels in the block input by the input means are encoded instead of the encoding means. 7. The image encoding apparatus according to claim 1, further comprising: a second encoding unit configured to generate and output.   A computer program that causes a computer to function as each unit of the image encoding device according to any one of claims 1 to 7 when the computer reads and executes the computer program.   A computer-readable storage medium storing the computer program according to claim 8. A control method for an image encoding device, comprising:
An input step in which the input means inputs multi-value image data in units of blocks composed of a plurality of pixels;
The identification information generating means classifies each pixel in the input block into the first and second groups according to the value of each pixel and identifies which group each pixel belongs to An identification information generation step for generating
A calculating step in which the calculating means calculates an average value of the values of the pixels belonging to the first group, an average value of the values of the pixels belonging to the second group, and a difference value between the two average values;
The replacement means adds the difference value to the value of each pixel belonging to the first group so that the difference between the average value of the first group and the average value of the second group becomes small, or A replacement step of substituting the value of the pixels belonging to the first group by subtracting the difference value from the value of each pixel belonging to the first group;
The encoding means includes an encoding step of encoding the value of each pixel in the replaced block, the difference value, and the identification information, and outputting encoded data of the block of interest. A control method of an image encoding device. Input means for inputting multi-value image data in units of blocks composed of a plurality of pixels;
Identification information generation for classifying each pixel in the input block into first and second groups according to the value of each pixel and generating identification information identifying which group each pixel belongs to Means,
Calculating means for calculating an average value of the pixels belonging to the first group, an average value of the pixels belonging to the second group, and a difference value between the two average values;
The difference value is added to the value of each pixel belonging to the first group so that the difference between the average value of the first group and the average value of the second group becomes small, and the first group First replacement means for generating a block in which the value of each pixel belonging to is replaced;
Second replacement means for generating a block by subtracting the difference value from the value of each pixel belonging to the second group and replacing the value of each pixel belonging to the second group;
Selecting means for selecting either the block output from the first replacement means or the block output from the second replacement means;
The block of interest is encoded by encoding a value of each pixel included in the block selected by the selection unit, the difference value, the identification information, and selection information indicating which block the selection unit has selected. An image encoding device comprising: encoding means for outputting the encoded data. Each of the first replacement means and the second replacement means is configured such that the upper limit value and the value of the pixel of interest after replacement are set when the value of the pixel of interest after replacement exceeds the upper limit value of the range that the pixel can take. 12. The image encoding device according to claim 11 , wherein when the pixel value falls below a lower limit value of a possible range of the pixel, the lower limit value is set as a pixel value after replacement. The selection means includes
First counting means for counting the number of pixels in which the value of the pixel after replacing the value of each pixel belonging to the first group of the block of interest exceeds a possible range of the pixel;
Second counting means for counting the number of pixels in which the value of the pixel after replacing the value of each pixel belonging to the second group of the block of interest exceeds a possible range of the pixel;
If the value counted by the first counting means is equal to or smaller than the value counted by the second counting means, the block output from the first replacing means is selected, otherwise The image encoding apparatus according to claim 12 , wherein the block output from the second replacement unit is selected. A control method for an image encoding device, comprising:
An input step in which the input means inputs multi-valued image data in units of blocks composed of a plurality of pixels;
The identification information generating means classifies each pixel in the input block into the first and second groups according to the value of each pixel and identifies which group each pixel belongs to An identification information generation step for generating
A calculating step in which the calculating means calculates an average value of the values of the pixels belonging to the first group, an average value of the values of the pixels belonging to the second group, and a difference value between the two average values;
The first replacement means adds the difference value to the value of each pixel belonging to the first group so that a difference between the average value of the first group and the average value of the second group becomes small. A first replacement step of generating a block in which the values of the pixels belonging to the first group are replaced;
A second replacement step in which a second replacement means subtracts the difference value from the value of each pixel belonging to the second group and generates a block in which the value of each pixel belonging to the second group is replaced; ,
A selection step in which the selection means selects either the block output in the first replacement step or the block output in the second replacement step;
The encoding means includes a value of each pixel included in the block selected in the selection step, the difference value, the identification information, and selection information indicating which block is selected in the selection step. And a coding process for coding and outputting the coded data of the block of interest. Input means for inputting multi-valued image data in units of blocks composed of a plurality of pixels;
According to the value of each pixel, each pixel in the input block is
Classification information generating means for generating identification information for classifying each pixel to belong to a group value of pixels belonging to the first group> a value of pixels belonging to the second group;
Calculating means for calculating an average value of the pixels belonging to the first group, an average value of the pixels belonging to the second group, and a difference value between the two average values;
Comparing means for comparing the difference value with a minimum pixel value of pixels belonging to the first group and outputting the smaller one as a correction value;
The correction value obtained by the comparing means is calculated from the value of each pixel belonging to the first group so that the difference between the average value of the first group and the average value of the second group becomes small. A substituting means for subtracting and generating a block in which the values of the pixels belonging to the first group are replaced;
An image encoding apparatus comprising: encoding means for encoding the value of each pixel in the block after replacement, the correction value, and the identification information, and outputting encoded data of the block of interest. A control method for an image encoding device, comprising:
An input step in which the input means inputs multi-value image data in units of blocks composed of a plurality of pixels;
The identification information generating means determines each pixel in the input block according to the value of each pixel.
An identification information generating step for classifying the pixel values to belong to the first group> the values of the pixels belonging to the second group, and generating identification information for identifying which group each pixel belongs to;
A calculating step in which the calculating means calculates an average value of the values of the pixels belonging to the first group, an average value of the values of the pixels belonging to the second group, and a difference value between the two average values;
A comparison step in which a comparison unit compares the difference value with a minimum pixel value of pixels belonging to the first group, and outputs a smaller one as a correction value;
The replacement means is obtained by the comparison step from the value of each pixel belonging to the first group so that the difference between the average value of the first group and the average value of the second group becomes small. A replacement step of subtracting the correction value to generate a block in which the values of the pixels belonging to the first group are replaced;
The encoding means includes an encoding step of encoding the value of each pixel in the replaced block, the correction value, and the identification information, and outputting encoded data of the block of interest. A control method of an image encoding device. Input means for inputting multi-valued image data in units of blocks composed of a plurality of pixels;
According to the value of each pixel, each pixel in the input block is
Classification information generating means for generating identification information for classifying each pixel to belong to a group value of pixels belonging to the first group> a value of pixels belonging to the second group;
Calculating means for calculating an average value of the pixels belonging to the first group, an average value of the pixels belonging to the second group, and a difference value between the two average values;
Comparing means for comparing the difference value with a difference value between a maximum pixel value of pixels belonging to the second group and an upper limit value that the pixel value can take, and outputting a smaller one as a correction value;
The correction value obtained by the comparison unit is added to the value of each pixel belonging to the second group so that the difference between the average value of the first group and the average value of the second group becomes small. A replacement means for adding and generating a block in which the values of the pixels belonging to the second group are replaced;
An image encoding apparatus comprising: encoding means for encoding the value of each pixel in the block after replacement, the correction value, and the identification information, and outputting encoded data of the block of interest. By computer executes read, the computer claims 11 to 13, 15, 17 a computer program for causing to function as each unit of the image coding apparatus according to any one of. A computer readable storage medium storing the computer program according to claim 18 . A control method for an image encoding device, comprising:
An input step in which the input means inputs multi-value image data in units of blocks composed of a plurality of pixels;
The identification information generating means determines each pixel in the input block according to the value of each pixel.
An identification information generating step for classifying the pixel values to belong to the first group> the values of the pixels belonging to the second group, and generating identification information for identifying which group each pixel belongs to;
A calculating step in which the calculating means calculates an average value of the values of the pixels belonging to the first group, an average value of the values of the pixels belonging to the second group, and a difference value between the two average values;
A comparison step in which the comparison unit compares the difference value with a difference value between a maximum pixel value of pixels belonging to the second group and an upper limit value that the pixel value can take, and outputs a smaller value as a correction value;
The replacement means obtains the value of each pixel belonging to the second group in the comparison step so that the difference between the average value of the first group and the average value of the second group becomes small. A replacement step of adding the correction values and generating a block in which the values of the pixels belonging to the second group are replaced;
The encoding means includes an encoding step of encoding the value of each pixel in the replaced block, the correction value, and the identification information, and outputting encoded data of the block of interest. A control method of an image encoding device.

Images