JP2008211527A - Image encoding device, image decoding device, and control method of them - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To obtain high compression performance even in the case of encoding image data having a biased frequency distribution, such as a CG image and a limited color image, while maintaining encoding performance of a natural image, or the like, as much as possible. <P>SOLUTION: The number of colors determining part 107 determines the number Nc of colors included in four neighborhood pixels located near a pixel under consideration. When the number of colors is four, an encoding selecting/combining part 103 selects and outputs only predictive encoded data of each component of the pixel under consideration obtained by a component value predictive encoding part 111. A neighborhood coincidence determining part 101 compares the pixel under consideration with the next pixel and with the neighborhood pixels and outputs neighborhood coincidence information Vp and noncoincidence information Ep. When the number of colors is three or less, the encoding selecting/combining part 103 selects and outputs only encoded data of the neighborhood coincidence information Vp from a coincidence pixel position encoding part 102 or combines the encoded data of the neighborhood coincidence information Vp with the component value predictive encoding part 111 and outputs the result data. <P>COPYRIGHT: (C)2008,JPO&INPIT

Description

  The present invention relates to image encoding and decoding techniques, and more particularly to lossless encoding and decoding techniques for images.

  2. Description of the Related Art Conventionally, there is one based on predictive coding as one method for configuring an image processing apparatus that performs image coding and decoding. The predictive coding apparatus includes a sequence conversion unit that converts image data into a prediction error by predictive conversion. The predictive encoding apparatus also includes an entropy encoding unit that converts the prediction error output from the sequence conversion unit into encoded data with less redundancy using entropy encoding such as Huffman encoding. .

  JPEG (ITU-T T.81 | ISO / IEC10918-1), which is recommended by ISO and ITU-T as an international standard still image coding method, defines a lossless process based on predictive coding as a lossless process. Has been. Hereinafter, this is referred to as a JPEG lossless encoding mode. In the JPEG lossless encoding mode, seven prediction formulas are defined as methods for predicting the value of the pixel of interest from neighboring pixels, and the prediction method can be selected according to the image.

  FIG. 2 is a block diagram of a conventional image processing apparatus that performs image coding. The figure is an example of an apparatus for reversibly compressing an image in accordance with the above-described JPEG lossless encoding mode. In the figure, 201 is a buffer, 202 is a component value prediction unit, 203 is a subtractor, 204 is a Huffman table memory, 205 is a prediction error encoding unit, 209 is a code string forming unit, and 206, 207, and 208 are signals. Is a line.

  The Huffman table memory 204 stores a Huffman table used in the prediction error encoding unit 205. Here, it is assumed that the Huffman table shown in FIG. 6 is stored.

  A flow of processing for encoding an RGB color image in which each component is expressed by 8 bits by a conventional image processing apparatus will be described with reference to FIG.

First, a prediction formula selection signal m for selecting a prediction formula used in the component value prediction unit 202 is input from the signal line 208. This prediction formula selection signal m is fixed during the encoding process of one image. The prediction formula selection signal m is one of values 0 to 7, and a different prediction formula is associated with each. The correspondence between the prediction formula used and the prediction formula selection signal m is as shown in FIG. When the prediction formula selection signal m is 0, there is no prediction formula. This means that the prediction conversion is not performed and each component is encoded as it is. Symbols Xa, Xb, and Xc in the figure indicate pixels adjacent to the target pixel. FIG. 3 shows relative positions of adjacent pixels Xa, Xb, Xc, and Xd with respect to the pixel of interest X _i . Since each pixel is encoded in the raster scan order, when encoding pixel X _i in FIG. 3, adjacent pixels Xa, Xb, Xc, Xd already means a code already pixels.

  Now, image data is sequentially input from the signal line 206. The input order of image data is the raster scan order. Each pixel is composed of three components R, G, and B, and is input in this order. R, G, and B are defined as component numbers 0, 1, and 2, respectively, and the component number C of the pixel at the horizontal pixel position x and the vertical pixel position y with the upper left corner of the image as the origin coordinate (0, 0). The value is represented as P (x, y, C). For example, if the pixel at the position (x, y) = (3,4) has a value of (R, G, B) = (255, 128, 0), P (3,4, 0) = 255, P (3,4,1) = 128 and P (3,4,2) = 0.

  The buffer 201 stores image data input from the signal line 206 for two lines.

When the component value prediction unit 202 obtains the predicted value p of the target component value C of the target pixel X _i , the component value prediction unit 202 reads the same component of the neighboring pixel used in the prediction formula selection signal m in the buffer 201. When the target component value C of the target pixel X _i is expressed as P (x, y, C), the component value prediction unit 202 is P (x−1, y, C) of the pixel immediately before the target pixel, one line before. P (x, y-1, C) of the pixel Xb and P (x-1, y-1, C) of the pixel Xc diagonally upper left are read to calculate the predicted value p.

When the target pixel X _i is on the first line of the image data to be encoded, only the component value of the immediately preceding pixel Xa is used as the predicted value p. Further, when the target pixel position is at the head of each line, the component value of the head pixel Xb one line before is used as the predicted value. However, 128 is the predicted value p for the first pixel of the image (the first pixel of the first line).

  The subtractor 203 obtains a difference value between the component value of the pixel to be encoded and the predicted value p, and outputs it as a prediction error e.

  The prediction error encoding unit 205 first classifies the prediction error e supplied from the subtractor 203 into a plurality of groups, and generates a group number SSSS and additional bits having a bit length determined for each group. FIG. 5 shows the relationship between the prediction error e and the group number SSSS. The additional bit is information for specifying a prediction error within the group, and the bit length is given by the group number SSSS. When SSSS = 16, the bit length is exceptionally 0 (however, when the accuracy of each component is 8 bits, SSSS = 16 does not occur). If the prediction error e is positive, the lower SSSS bits of the prediction error e are additional bits, and if it is negative, the lower SSSS bits of e-1 are additional bits. The most significant bit of the additional bits is 1 if the prediction error e is positive, and 0 if the prediction error e is negative. The encoding process first outputs encoded data corresponding to the group number SSSS with reference to the Huffman table stored in the memory 204. If SSSS is not 0 or 16, then additional bits are output with a bit length determined by the group number.

  The code string forming unit 209 includes a prediction formula selection signal m input via the signal line 208, additional information such as the number of pixels in the horizontal / vertical direction of the image, the number of components constituting the pixel, and the accuracy of each component. Based on the encoded data output from the prediction error encoding unit 205, a code string in a format compliant with the JPEG standard is formed and output to the signal line 207.

  Now, it is assumed that image data with a biased frequency distribution of each component, such as a CG image (computer graphics image) or a limited color image, is encoded using the above-described conventional image processing apparatus. In this case, the occurrence frequency of the prediction error after the above-described series conversion may also be biased toward some specific prediction error values.

  In the case of such an image, although a short code length is assigned as a code length by entropy coding, there may be a prediction error that hardly or not occurs, and as a result, a high compression rate is not obtained. There was a problem.

Conventionally with respect to such a problem, a method of determining whether or not the frequency distribution of occurrence of a prediction error is discrete, and changing the encoded data corresponding to the prediction error according to the determination result (for example, a patent) Reference 1) has been proposed. In addition, a method of determining whether an encoding target image is composed of discrete pixel values and correcting a predicted value according to the determination result (for example, see Patent Document 2) has been proposed.
JP-A-10-004551 Japanese Patent Laid-Open No. 10-004557

  In order to increase the encoding efficiency, it is necessary to grasp the generation status of the component value of each pixel or the generation status of the prediction error. However, this increases the processing load. In addition, when each component is predictively encoded using a block code such as a Huffman code, at least one bit is required for each component. Therefore, encoding efficiency is low for image data with low entropy such as characters, line drawings, and CG images. There was still room for improvement.

  The present invention has been made in view of the above-mentioned problems, and has a simple configuration and high compression rate for image data having a biased frequency distribution as seen in CG images, limited color images, and the like. It is intended to provide a lossless encoding technique and a decoding technique thereof.

In order to solve this problem, for example, an image encoding device of the present invention has the following configuration. That is,
An image encoding device for losslessly encoding image data,
Input means for inputting image data in raster order;
Color number determination means for determining the number of colors included in a plurality of neighboring pixels that have been encoded and are located in the vicinity of the target pixel Xi to be encoded in the input image;
A first lossless encoding means for reversibly encoding the pixel of interest Xi and generating encoded data when the number of colors determined by the color number determination means is equal to or greater than a predetermined color number Cn;
A pixel number determination unit that determines the number of pixels to be encoded for generating one encoded data when the number of colors determined by the color number determination unit is less than the predetermined color number Cn;
When the number of pixels to be encoded determined by the pixel number determining means is defined as n (n ≧ 1), each of the n pixels Xi, Xi + 1,. For each of the n pixels, it indicates whether or not a pixel of the same color exists in the plurality of neighboring pixels, and if there is a pixel of the same color, the position of the neighboring pixel that is the same color Vector information generating means for generating vector information indicating
Vector information encoding means for encoding vector information generated by the vector information generation means and generating encoded vector data;
A second lossless encoding means for losslessly encoding each of the pixels in the n pixels determined to have no pixel of the same color among the plurality of neighboring pixels;
When the number of colors determined by the color number determination unit is equal to or greater than the predetermined number of colors Cn, the encoded data generated by the first lossless encoding unit is output,
When the number of colors determined by the color number determination means is less than the predetermined number of colors Cn, the encoded vector data generated by the vector information encoding means and the second lossless encoding means are obtained. Output means for outputting the encoded data.

  According to the configuration of the present invention, high compression performance can be obtained even when encoding image data with a biased frequency distribution, such as a CG image or a limited color image, while maintaining the encoding performance of natural images as much as possible. be able to.

  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 diagram of an image encoding apparatus (image processing apparatus) according to this embodiment.

  The image encoding apparatus according to the present embodiment includes a control unit 100 that controls the entire apparatus, a proximity match determination unit 101, a match pixel position encoding unit 102, a code selection combining unit 103, a code string forming unit 104, and a color number determination. Unit 107, line buffer 108, component value prediction unit 202, subtractor 203, Huffman table memory 204, and prediction error encoding unit 205. In the figure, reference numerals 206, 207, 105 and 106 denote signal lines. Blocks that operate in the same manner as the processing blocks of the conventional image coding apparatus in FIG.

  Hereinafter, with reference to FIG. 1, the encoding process of the image encoding device according to the present embodiment will be described.

  The image data to be encoded by the image encoding apparatus according to the present embodiment is color image data composed of three components R, G, and B. Each component constituting one pixel is 8 bits (brightness in the range of 0 to 255). It is assumed that the image data to be encoded is a pixel arrangement in the raster scan order, and the components of each pixel are arranged dot-sequentially. That is, it is assumed to be composed of an array of R, G, B, R, G, B,. In addition, in order to simplify the explanation, in the embodiment, it is assumed that the image data to be encoded is composed of horizontal W pixels and vertical H pixels.

  Next, the processing content of each part in the image coding apparatus of this embodiment is demonstrated.

  The encoding target image data is sequentially input from the signal line 206. As described above, the input order of the image data is the raster scan order, and is the order of R, G, B, R, G, B. Note that the generation source of the image data to be encoded may be a computer, an image file stored in a storage medium, an input via a network, or an image scanner, and the type thereof is not limited.

  The luminance values R, G, and B of the pixel components are defined as component numbers 0, 1, and 2, respectively, and the horizontal pixel position x and the vertical pixel position y with the upper left corner of the image as coordinates (0, 0). The value of the component number C of the pixel in is represented as P (x, y, C). For example, the values of the R, G, B components of the pixel at the horizontal pixel position “10” and the vertical pixel position “25” are P (10, 25, 0), P (10, 25, 1), P (10, 25, 2). When pixel values are expressed as a group of components, they are expressed as a vector X having R, G, and B component values as elements. For example, a pixel X whose R, G, and B component values are r, g, and b is described as X = (r, g, b).

  The image encoding apparatus generates encoded data from data of one or two pixels sequentially input from the signal line 206, and outputs the encoded data from the code string forming unit 104.

The line buffer 108 has a capacity for storing two lines of image data, and sequentially stores the image data input from the signal line 206. As described above, in the image data, component values are input in the order of raster for each pixel and in the order of R, G, and B for each pixel. From the line buffer 108, as shown in FIG. 3, the data of the pixel to be encoded (hereinafter referred to as the pixel of interest) X _{i in the image} and the surrounding four pixels indicated by the neighboring pixels Xa, Xb, Xc, and Xd are stored. It is read out and output to the neighborhood match determination unit 101 and the component value prediction unit 202.

Here, the value of P of the component number C of the target pixel X _i (C is either 0,1,2) (x, y, C ) when the, neighboring pixels Xa, Xb, Xc, Xd component number The values of C are P (x-1, y, C), P (x, y-1, C), P (x-1, y-1, C), and P (x + 1, y-1, C). I can express. When the position of the pixel of interest X _i is on the first line of the image or at the beginning or end of each line, some of the neighboring pixels Xa, Xb, Xc, Xd are outside the image. Will be located. In this embodiment, when a neighboring pixel exists outside the image, each component value of the neighboring pixel is assumed to be “0” for processing. However, other than this, for example, the intermediate value “128” may be used. The point is that the pixels outside the image should be set to have a common value on the encoding side and the decoding side.

  When image data for one line is stored in the line buffer 108, encoding processing for each pixel in the line is started.

  First, the color number determination unit 107 will be described.

The number-of-colors determination unit 107 reads, from the line buffer 108, four pixels of neighboring pixels Xa, Xb, Xc, and Xd shown in FIG. 3 for each component of the pixel of interest X _i that is to be encoded.

When the position of the pixel of interest X _{i in} the image to be encoded is (x, y) and X _i , X a, X b, X c, X d are expressed using this, each pixel data is as follows.
X _i = (P (x, y, 0), P (x, y, 1), P (x, y, 2))
Xa = (P (x-1, y, 0), P (x-1, y, 1), P (x-1, y, 2))
Xb = (P (x, y-1, 0), P (x, y-1, 1), P (x, y-1, 2))
Xc = (P (x-1, y-1, 0), P (x-1, y-1, 1), P (x-1, y-1, 2))
Xd = (P (x + 1, y-1, 0), P (x + 1, y-1, 1), P (x + 1, y-1, 2))

  The color number determination unit 107 detects the number of colors Nc included in the pixels Xa, Xb, Xc, and Xd and outputs the detected number of colors Nc. Although details will be described later, the color number Nc is also information for determining the number of pixels to be encoded, so the color number determination unit 107 also functions as a pixel number determination unit. The following is an example of how to determine the number Nc in the color embodiment.

Consider six combinations for extracting a pair of two pixels from four pixels of Xa, Xb, Xc, and Xd. If one pair is represented by {,}, the six pairs are as follows.
{Xa, Xb}
{Xa, Xc}
{Xa, Xd}
{Xb, Xc}
{Xb, Xd}
{Xc, Xd}
From the count value obtained by counting how many pairs of the same color among the above six pairs, the number of colors Nc included in the four pixels can be determined. That is, if the count value is “0”, it indicates that all of Xa, Xb, Xc, and Xd are different from each other, and therefore the number of colors Nc can be determined to be “4”. If the count value is “1” (when only one pair is equal to each other), the number of colors Nc can be determined to be “3”. If the count value is “2” or “3”, the number of colors Nc is “2”. If the count value is “6”, the number of colors Nc can be determined to be “1”. Note that the count value cannot be 4 or 5. It will be understood that the above can be realized with simple hardware.

  The number-of-colors determination unit 107 outputs the number of colors Nc (= 1, 2, 3, or 4) obtained as described above to the neighborhood match determination unit 101 and the match pixel position coding unit 102. .

Next, the neighborhood match determination unit 101 in the embodiment will be described. In the following description, the encoding target pixel located next to the target pixel X _i (next pixel) conveniently expressed as X _{i + 1.} When the pixel of interest X _i is (x, y), the pixel X _{i + 1} can be expressed as follows.
X _{i + 1} = (P (x + 1, y, 0), P (x + 1, y, 1), P (x + 1, y, 2))
The proximity match determination unit 101 reads the next pixel X _{i + 1} by accessing the line buffer 108 when the number of colors Nc is 2 or less. If the target X _i is the end pixel of the line, the processing is performed assuming that X _{i + 1} = X _i .

Now, the neighborhood matching determination unit 101 in the embodiment, based on the color number Nc, compared to the target pixel X _i and the next pixel X _{i + 1} thereof, four neighboring pixels Xa of the target pixel X _i, Xb, Xc, and Xd Then, the neighborhood match information Vp and the mismatch pixel information Ep are generated. Then, the neighborhood match determining unit 101 outputs the generated neighborhood match information Vp to the matched pixel position encoding unit 102 via the signal line 106. Also, the neighborhood match determination unit 101 outputs the generated mismatch pixel information Ep to the component value prediction encoding unit 111 and the code string generation unit 102 via the signal line 105.

  Hereinafter, the generation processing of the neighborhood match information Vp and the mismatch pixel information Ep performed by the neighborhood match determination unit 101 will be described separately for each color number Nc.

<When the number of colors Nc is 4>
“Nc = 4” indicates that neighboring pixels Xa, Xb, Xc, and Xd of the pixel of interest X _i all have different pixel values (colors). When this condition is satisfied, the proximity match determination unit 101 outputs the mismatch pixel information Ep as “5” on the signal line 105. Further, the neighborhood match information Vp may be any value. Although details will be described later, since the neighborhood match information Vp is an integer of 0 to 8, any of them may be used. The reason is that when the mismatch pixel information Ep is “5”, the neighborhood match information Vp is not used in the subsequent processing. When Nc = 4, the neighborhood match determination unit 101 does not read the next pixel X _{i + 1} .

<When the number of colors Nc is 1>
“Nc = 1” indicates that the neighboring pixels Xa, Xb, Xc, and Xd of the pixel of interest X _i all have the same pixel value (the same color). When Nc = 1, the target pixel X _i has a high probability of being the same color as the neighboring pixel Xa (= Xb = Xc = Xd). The next pixel X _{i + 1} is also likely to be the same as the neighboring pixel Xa of the pixel of interest X _i . Therefore, the neighborhood match determination unit 101 reads not only the target pixel X _i but also the next pixel X _{i + 1} from the line buffer 108. Then, the neighborhood match determination unit 101 compares the target pixel X _i , the next pixel X _{i + 1,} and the comparison target pixel Xa (= Xb = Xc = Xd), and generates neighborhood mismatch pixel information Ep as follows. And output.
When X _i = X _{i + 1} = Xa, Ep = “0”;
When X _i = Xa and X _{i + 1} ≠ Xa, Ep = “1”;
When X _i ≠ Xa and X _{i + 1} = Xa, Ep = “2”;
When X _i ≠ Xa and X _{i + 1} ≠ Xa, Ep = “3”;
When the number of colors Nc is “1”, the neighborhood match information Vp and the mismatch pixel information Ep are set to the same value.

<When the number of colors is 2>
“Nc = 2” indicates that the number of colors included in the neighboring pixels Xa, Xb, Xc, and Xd of the target pixel is two. Nc = 2 is the case where, for example, Xa = Xb ≠ Xc = Xd, Xa ≠ Xb = Xc = Xd, Xa = Xc = Xd ≠ Xb, and the like.

  The neighborhood coincidence determination unit 101 obtains the first pixel X1 and the second pixel X2 that are two comparison target pixels with Nc = 2. Specifically, first, the search is performed in the order of Xa, Xb, Xc, and Xd, and the first pixel value (color) X1 and the second pixel value X2 are obtained each time a different color is found.

  For example, when Xa = Xb ≠ Xc = Xd, X1 = Xa and X2 = Xc. When Xa = Xc ≠ Xb = Xd, X1 = Xa and X2 = Xb. When Xa = Xb = Xc ≠ Xd, X1 = Xa and X2 = Xd. Note that X1 is always Xa.

When the proximity match determination unit 101 obtains the two pixel values (colors) X 1 and X 2 as described above, the data of the next pixel X _{i + 1} subsequent to the pixel of interest X _i is read from the line buffer 108. In the case of Nc = 2, although not as much as Nc = 1, it is because the probability that the next pixel X _{i + 1} is also equal to either X1 or X2 is high. Then, the neighborhood match determination unit 101 determines and outputs neighborhood match information Vp and mismatch pixel information Ep as follows.
When X _i = X _{i + 1} = X ₁ , Vp = 0, Ep = 0;
If X _i = X _{i + 1} = X 2 then Vp = 1, Ep = 0;
If X _i = X ₁ and X _{i + 1} = X 2 then Vp = 2, Ep = 0;
When X _i = X ₁ and X _{i + 1} ≠ X ₁ and X _{i + 1} ≠ X 2, Vp = 3, Ep = 1;
When X _i = X 2 and X _{i + 1} = X ₁ , Vp = 4, Ep = 0;
When X _i = X 2 and X _{i + 1} ≠ X ₁ and X _{i + 1} ≠ X 2, Vp = 5, Ep = 1;
When X _i ≠ X 1 and X _i ≠ X 2 and X _{i + 1} = X ₁ , Vp = 6, Ep = 2;
When X _i ≠ X 1 and X _i ≠ X 2 and X _{i + 1} = X 2, Vp = 7, Ep = 2;
When X _i ≠ X 1 and X _i ≠ X 2 and X _{i + 1} ≠ X ₁ and X _{i + 1} ≠ X 2, Vp = 8, Ep = 3;

<When the number of colors is 3>
“Nc = 3” indicates that the number of colors in the pixels Xa, Xb, Xc, and Xd in the vicinity of the target pixel is three (only two of the four pixels have the same color). The proximity match determination unit 101 obtains the first pixel value X1, the second pixel value X2, and the third pixel value X3 in the order of the pixels Xa, Xb, Xc, and Xd. For example, when only Xb and Xc are the same color, X1 = Xa, X2 = _Xb , and X3 = _Xd . When Nc = 3, the probability that the target pixel X _i is the same as X1, X2, and X3 is high, but the probability that the next pixel X _{i + 1} is the same as X1, X2, and X3 is low. Therefore, the proximity match determination unit 101 does not read the next pixel X _{i + 1} .

When the neighborhood match determination unit 101 obtains the pixel values X1, X2, and X3 as described above, the neighborhood match information Vp and the mismatch pixel information Ep are generated and output as follows.
When X _i = X 1, Vp = 0, Ep = 0;
When X _i = X 2, Vp = 1, Ep = 0;
When X _i = X 3, Vp = 2, Ep = 0;
When X _i ≠ X 1 and X _i ≠ X 2 and X _i ≠ X 3, Vp = 3, Ep = 4;

  The processing contents of the neighborhood match determination unit 101 in the embodiment are as described above.

Although details will be described later, the image encoding device in the embodiment generates encoded data from data of two pixels of the pixel of interest X _i and the next pixel X _{i + 1} when the number of colors Nc = 1 or 2, Output. When the number of colors Nc = 3 or 4, encoded data is generated only from the pixel of interest X _i and output.

Here, the number Nc of colors input by the neighborhood match determination unit 101, the pixel of interest X _i and the next pixel X _{i + 1} , the state of the neighborhood of the pixel of interest, and the relationship between the neighborhood match information Vp and the mismatch pixel information Ep to be generated are summarized. The table shown in FIG.

  Hereinafter, the meanings of the neighborhood match information Vp and the mismatch pixel information Ep will be described with reference to FIG.

In the mismatch pixel information Ep, when attention is paid to the two pixels of the target pixel X _i and the next pixel X _{i + 1} , each pixel does not match the four pixels of the neighboring pixels Xa, Xb, Xc, and Xd, and the pixel value It can be said that this is index information indicating whether or not transmission is necessary.

  For example, let us focus on Nc = 1 or 2.

“Unmatched pixel information Ep = 0” under this condition indicates that both the target pixel X _i and the next pixel X _{i + 1} are equal to any of the neighboring pixels Xa, Xb, Xc, and Xd. Further, "Ep = 1" is the target pixel X _i is the neighboring pixels Xa, consistent Xb, Xc, and either Xd, indicates that the near pixels to match the next pixel X _{i + 1} does not exist. Further, "Ep = 2" is no neighboring pixel having the same color as the target pixel X _i, indicating that the neighboring pixels to match the next pixel X _{i + 1} exists. “Ep = 3” indicates that neither the target pixel X _i nor the next pixel X _{i + 1} matches any of the neighboring pixels.

  Also, pay attention to the case of Nc = 3.

“Unmatched pixel information Ep = 0” under this condition indicates that the pixel of interest X _i is equal to any of the neighboring pixels Xa, Xb, Xc, and Xd. “Ep = 4” indicates that the pixel of interest X _i does not match any of the neighboring pixels Xa, Xb, Xc, and Xd.

On the other hand, in the case of Nc = 1 or 2, the neighborhood match information Vp indicates whether the same color as the pixel of interest X _i and the next pixel X _{i + 1} exists in the neighborhood pixels Xa, Xb, Xc, Xd, and the same. When there is a color pixel, it can be said that the pixel information specifies which direction the neighboring pixel of the pixel of interest X _i is. That is, the neighborhood match determination unit 101 functions as a vector information generation unit that generates vector information (neighbor match information Vp).

For example, as an example of Nc = 2, it is assumed that Xa = Xb = Xc ≠ Xd. In this case, it is uniquely determined that the pixel value X1 is equal to the color of the pixel Xa and the pixel value X2 is equal to the color of the pixel Xd. In this state, “neighbor matching information Vp = 4” is X _i = X 2 and X _{i + 1} = X ₁ from FIG. 7, so that the target pixel X _i is the upper right pixel after all. It can be specified that the next pixel X _{i + 1} is the same color as Xd, and the next pixel X _{i + 1} is the same color as the pixel Xa (or Xb or Xc) on the left of the pixel of interest.

  Note that the mismatch pixel information Ep can be uniquely obtained from the neighborhood match information Vp and the number of colors Nc (see FIG. 7). Therefore, it should be noted that each processing unit that inputs the mismatch pixel information Ep may input and process the neighborhood match information Vp and the number of colors Nc.

  Next, the matched pixel position encoding unit 102 in the embodiment will be described.

  The matching pixel position encoding unit 102 encodes the neighboring pixel matching information Vp input from the signal line 106, generates encoded data (encoded vector data), and outputs the encoded data to the code generation unit 1305. That is, the matching pixel position encoding unit 102 functions as a vector information encoding unit. The matching pixel position encoding unit 102 in this embodiment is selected from the three encoding tables shown in FIGS. 12A, 12 </ b> B, and 12 </ b> C according to the number of colors Nc output from the color number determination unit 1301. One is selected, and encoded data of the neighboring pixel match information Vp is generated.

  When the number of colors Nc is “4”, the matching pixel position encoding unit 102 does not output encoded data. This is the reason why the neighborhood match determination unit 101 may output any neighborhood match information Vp when the number of colors Nc is “4” as described above.

  12A to 12C show an encoding table used by the matching pixel position encoding unit 102. FIG.

FIG. 12A shows an encoding table when Nc = 1. In the case of Nc = 1, as can be seen from FIG. 7, there are four possible values of the neighboring pixel match information Vp, 0, 1, 2, and 3. Therefore, the encoding table has four encoded data as shown in the figure. Is stored. Further, when Nc = 2, there are nine possible values of the neighboring pixel matching information Vp, from 0 to 8, and therefore, the encoding table stores nine encoded data as shown in FIG. 12B. Further, when Nc = 3, there are four possible values of the neighboring pixel matching information Vp, from 0 to 3, so that the encoding table stores four encoded data as shown in FIG. Here, when the number of colors Nc = 1, 2, the pixel of interest X _i and the next pixel X _{i + 1} have a high probability of occurrence of the same color in the neighboring pixels Xa, Xb, Xc, Xd. Accordingly, the data length of the encoded data is set to be large. Further, when the number of colors Nc = 3, there is a higher possibility that the same color as that of the pixel of interest X _i is included in the neighboring pixels, so that the shortest code length is assigned to Vp = 3.

  Next, the component value predictive encoding unit 111 in the embodiment will be described. The component predictive encoding unit 111 itself is substantially the same as the process of the prior art, except that the process according to the mismatch pixel information Ep output from the neighborhood match determination unit 101 is performed. The processing contents will be described below.

<When Ep = 0>
When the mismatch pixel information Ep output from the neighborhood match determination unit 101 is “0”, the component value prediction encoding unit 111 does not perform the encoding process. However, the encoding process may be performed. This is because the code generation unit 103, which will be described later, ignores the output from the component value prediction encoding unit 111 when the mismatch pixel information Ep is “0”.

<When Ep = 1>
As is apparent from the table of FIG. 7, when the mismatch pixel information Ep is “1” (also in the case of Nc = 1 or 2), the same color as the pixel of interest X _i has neighboring pixels Xa, Xb, Xc, Xd. It is promised to exist within. On the other hand, the same color as the next pixel X _{i + 1} does not exist in the neighboring pixels Xa, Xb, Xc, and Xd of the pixel of interest X _i . Therefore, the component value prediction encoding unit 111 encodes each component value of the next pixel X _{i + 1} by the component value prediction unit 202, the subtracter 203, and the prediction error encoding unit 205, and the encoded data Is output to the code generation unit 103.

At this time, the reference pixels when calculating a predicted value p of the next pixel X _{i + 1,} a neighboring pixel corresponding to the next pixel X _{i + 1.} That is, the coordinates of the next pixel X _{i + 1} are (x + 1, y), and neighboring pixels Xa ′, Xb ′, Xc ′, and Xd ′ that are referred to in order to obtain the predicted value can be defined as follows.
Xa ′ = (P (x, y, 0), P (x, y, 1), P (x, y, 2)) = X _i
Xb ′ = (P (x + 1, y−1, 0), P (x + 1, y−1, 1), P (x + 1, y−1, 2))
Xc ′ = (P (x, y−1, 0), P (x, y−1, 1), P (x, y−1, 2))
Xd '= (P (x + 2, y-1, 0), P (x + 2, y-1, 1), P (x + 2, y-1, 2))
<When Ep = 2>
As is apparent from the table of FIG. 7, when the mismatch pixel information Ep is “2” (also in the case of Nc = 1 or 2), at least the same color as the pixel of interest X _i has the neighboring pixels Xa, Xb, Xc, It will not exist in Xd. Therefore, the component value prediction encoding unit 111 encodes each component value of the pixel of interest X _i by the component value prediction unit 202, the subtracter 203, and the prediction error encoding unit 205, and encodes the encoded data. The data is output to the generation unit 103. In addition, when Ep = 2, the component value predictive encoding unit 111 may or may not perform the predictive encoding process for the next pixel X _{i + 1} . This is because, as will be described later, the code selective combining unit 103 ignores the prediction encoded data of the next pixel X _{i + 1} from the component value predictive encoding unit 111 when EP = 2.

<When EP = 3>
The component value prediction encoding unit 111 encodes each component value of the pixel of interest X _i and the next pixel X _{i + 1} by the component value prediction unit 202, the subtracter 203, and the prediction error encoding unit 205.

<When EP = 4 or 5>
The component value prediction encoding unit 111 encodes each component value of the pixel of interest X _i using the component value prediction unit 202, the subtracter 203, and the prediction error encoding unit 205.

  Next, the code selective combining unit 103 in the embodiment will be described.

  The code selection combining unit 103 selects one of the encoded data from the matched pixel position encoding unit 102 and the encoded data from the component value predictive encoding unit 111 according to the mismatch pixel information Ep from the neighborhood match determination unit 101, Alternatively, the two encoded data are combined and output. Hereinafter, the process of the code selection combining unit 103 for each value of the mismatch pixel information Ep will be described.

<When EP = 0>
As can be seen from FIG. 7, Nc = 1 or the the Ep = 0 in 2, both of the target pixel X _i and the next pixel X _{i + 1} is the neighboring pixels Xa of the target pixel X _i, Xb, Xc, It represents that it is the same value (color) as any of Xd. Further, Ep = 0 at Nc = 3 indicates that the pixel of interest X _i has the same value (color) as any of the neighboring pixels Xa, Xb, Xc, and Xd.

  Therefore, the code selection / combining unit 103 selects and outputs only the encoded data from the coincident pixel position encoding unit 102. FIG. 8A shows encoded data output from the code generation unit 103 when Ep = 0.

  It should be noted that when Nc = 1 or 2, the encoded data in FIG. 8A indicates encoded data for two pixels, and when Nc = 3, the encoded data in FIG. Data is a point indicating encoded data for one pixel.

<When Ep = 1>
When Ep = 1 (therefore, Nc = 1 or 2), the target pixel X _i has the same value (color) as any of the neighboring pixels Xa, Xb, Xc, Xd, and the next pixel X _{i + 1} is the target pixel neighboring pixels Xa of X _i, is not equal Xb, Xc, with any of Xd (see FIG. 7).

When Ep = 1, the component value predictive encoding unit 111 predictively encodes each component value of the next pixel X _{i + 1} and generates encoded data thereof.

Therefore, the code selection combining unit 103 combines the encoded data of the next pixel X _{i + 1} output from the component value predictive encoding unit 111 with the encoded data from the coincident pixel position encoding unit 102 and outputs the combined data. . FIG. 8B shows encoded data output from the code selective combining unit 103 when Ep = 1.

<When Ep = 2>
When EP = 2 (thus, Nc = 1 or 2), the target pixel X _i is different from any of the neighboring pixels Xa, Xb, Xc, and Xd, and the next pixel X _{i + 1} is the neighboring pixel Xa of the target pixel X _i. , Xb, Xc, and Xd (see FIG. 7).

Further, when Ep = 2, the component value predictive encoding unit 111 predictively encodes each component value of the pixel of interest X _i and generates encoded data thereof.

Therefore, the code selection combining unit 103 combines the encoded data of the pixel of interest X _i output from the component value predictive encoding unit 111 with the encoded data from the coincident pixel position encoding unit 102 and outputs the combined data. FIG. 8C shows encoded data output from the code selective combining unit 103 when Ep = 2.

<When EP = 3>
In the case of EP = 3 (accordingly, Nc = 1 or 2), this indicates that both the target pixel X _i and the next pixel X _{i + 1} are different from the neighboring pixels Xa, Xb, Xc, Xd.

When Ep = 3, the component value predictive encoding unit 111 predictively encodes each component value of the pixel of interest X _i and the next pixel X _{i + 1} and generates encoded data thereof.

Therefore, the code selection combining unit 103 adds the encoded data of the pixel of interest X _i and the next pixel X _{i + 1} output from the component value predictive encoding unit 111 to the encoded data from the matching pixel position encoding unit 102. Combine and output. FIG. 8D shows encoded data output from the code generation unit 103 when Ep = 3.

<Ep = 4>
Ep = 4 only when Nc = 3. In this situation, the component value predictive encoding unit 111 predictively encodes each component value of the pixel of interest X _i and generates encoded data thereof. That is, the component value predictive encoding unit 111 does not perform predictive encoding processing of the next pixel X _{i + 1} .

Therefore, the code selection combining unit 103 combines the encoded data of the pixel of interest X _i output from the component value predictive encoding unit 111 with the encoded data from the coincident pixel position encoding unit 102 and outputs the combined data. The data structure of the encoded data to be output is the same as that in FIG.

  It should be noted that the data format of FIG. 8C has different meanings for Ep = 2 and Ep = 4. That is, when the number of colors Nc = 1 or 2, the encoded data in FIG. 8C represents encoded data for two pixels. When Nc = 3, the encoded data in FIG. 8C represents encoded data for one pixel.

<When Ep = 5>
Ep = 5 is obtained only when Nc = 4. In this situation, the component value predictive encoding unit 111 predictively encodes each component value of the pixel of interest X _i and generates encoded data thereof. That is, the component value predictive encoding unit 111 does not perform predictive encoding processing of the next pixel X _{i + 1} .

The code selecting / combining unit 103 selects only the encoded data of the pixel of interest X _i output from the component value predictive encoding unit 111 and outputs it without selecting the encoded data from the coincident pixel position encoding unit 102. . FIG. 8E shows the encoded data output from the code selective combining unit 103 when Ep = 5.

  Next, the code string forming unit 104 in the embodiment will be described.

  The code string forming unit 104 outputs the encoded data to a storage device (not shown). In the embodiment, a losslessly encoded image file is generated in this storage device.

  Specifically, at the start of the image data encoding process, the code string forming unit 104 determines the prediction expression selection signal m, the number of pixels in the horizontal / vertical direction of the image, the number of components constituting the pixel, A file header composed of additional information such as accuracy is generated. When the encoding process is started and encoded data is output from the code selective combining unit 103, the encoded data is output as data subsequent to the file header. When the output of all the encoded data of the image data to be encoded is completed, the file that has been opened for output is closed, and the lossless encoded image file is completed. FIG. 9 shows the structure of an image file generated in the embodiment. The data following the header in the figure represents data in any of the formats shown in FIGS. In addition, in the image coding apparatus of this embodiment, since the prediction formula selection signal m is a fixed value, it can be removed from the header. Further, the file format of FIG. 9 is an example, and other formats may be used.

  Next, the configuration and operation of an image decoding apparatus that decodes the encoded image data generated by the image encoding process in the embodiment will be described.

  FIG. 13 is a block configuration diagram of an image decoding apparatus according to the embodiment.

  The image decoding apparatus basically performs processing reverse to that of the image encoding apparatus described above, and the image decoding apparatus inevitably has a configuration having the same function as the image encoding apparatus. In order to simplify the description, the same components as those of the image encoding device in the image decoding device are denoted by the same reference numerals, and the description thereof is omitted.

  As shown in FIG. 13, the image decoding apparatus includes a control unit 2000 that controls the entire apparatus, a buffer 201, a color number determination unit 107, a header analysis unit 1102, a matching pixel position decoding unit 1701, a selector 1702, a switch 1106, And a prediction decoding unit 1704. The prediction decoding unit 1704 includes a component value prediction unit 202, an adder 1111, a Huffman table memory 204, and a prediction error decoding unit 1702. In the figure, reference numerals 1107, 1108, 1109 and 1110 are signal lines.

Hereinafter, with reference to FIG. 13, the lossless decoding process of the image decoding apparatus according to the present embodiment will be described. The buffer 201 has a capacity for storing decoded pixel data for two lines. In addition, when the target pixel X _i to be decoded is at the boundary of the image, some of the neighboring pixels Xa, Xb, Xc, and Xd may be outside the image. In the present embodiment, as in the image encoding device, each component value of neighboring pixels located outside the image is assumed to be “0” for processing.

  Now, lossless encoded data to be decoded is temporarily stored in the code buffer 1101 in this apparatus via the signal line 1107. The header analysis unit 1102 analyzes the stored header and obtains the size of the original image (the number of pixels in the horizontal direction and the vertical direction) and the prediction formula selection signal m. The obtained prediction formula selection signal m is supplied to the component value prediction unit 202.

The color number determination unit 107 reads pixel data of already decoded pixels Xa, Xb, Xc, and Xd in the vicinity of the pixel of interest X _i from the buffer 201, detects (calculates) the number of colors Nc included therein, The result is output to the matching pixel position decoding unit 1701. Since the method of obtaining the number of colors Nc may be the same as that of the encoding device, description thereof is omitted.

  First, the process of the matching pixel position decoding unit 1701 will be described.

  When the number of colors Nc output from the number-of-colors determination unit 107 is any one of 1, 2, and 3, the matching pixel position decoding unit 1701 is any one of FIGS. 12 (a), (b), and (c). Select one table. The matching pixel position decoding unit 1701 regards the data to be decoded next stored in the encoding buffer 1101 as one of FIGS. 8A to 8D, and decodes the neighborhood matching information Vp. That is, the matching pixel position decoding unit 1701 functions as a vector information decoding unit that decodes vector information. The matching pixel position decoding unit 1701 outputs the decoded neighborhood matching information Vp to the selector 1105 via the signal line 1109. Since the coincidence pixel position decoding unit 1701 reads the encoded data of the neighborhood coincidence information Vp from the encoding buffer 1101, the bit position to be read next is updated by the number of bits of the encoded data.

  Further, the matching pixel position decoding unit 1701 generates mismatching pixel information Ep based on the decoded neighborhood matching information Vp and the color number Nc from the color number determination unit 107 with reference to the table of FIG. Then, the matched pixel position decoding unit 1701 outputs the generated mismatched pixel information Ep to the prediction error decoding unit 1702 and the switch 1106 via the signal line 1108.

  Here, when the number of colors Nc is “1”, the neighborhood match information Vp and the mismatch pixel information Ep are the same value as shown in FIG. When the number of colors Nc is “2”, as shown in FIG. 7, the neighborhood match information Vp is any value in the range of 0 to 8, and the mismatch pixel information EP is any of 0 to 3. Value. When the color number Nc is “3”, the neighborhood match information Vp is any value from 0 to 3, and the mismatch pixel information Ep is either 0 or 4.

  On the other hand, when the number of colors Nc input from the number-of-colors determination unit 107 is “4”, the matching pixel position decoding unit 1701 does not perform the decoding process of the neighborhood matching information Vp as shown in FIG. Information Ep = 5 is generated and output to each signal line 1108. When Nc = “4”, the coincidence pixel position decoding unit 1701 does not perform the decoding process of the neighborhood coincidence information Vp. The matching pixel position decoding unit 1701 may output any value of the neighborhood matching information Vp. When Nc = 4, the matching pixel position decoding unit 1701 does not perform update processing of the bit position to be read next.

  As a result of the above, the matching pixel position decoding unit 1701 refers to the number of colors Nc, generates the neighborhood matching information Vp and the mismatching pixel information Ep shown in FIG. 7 from the encoded data, and outputs them.

  Next, the component value predictive decoding unit 1704 will be described. The component value predictive decoding unit 1704 performs a decoding process for one pixel or two pixels according to the value of the mismatch pixel information Ep from the match pixel position decoding unit 1701. Specifically, it is as follows.

<When Ep = 0>
The component value predictive decoding unit 1704 does nothing.

<When Ep = 1>
Component value prediction decoding unit 1704, the encoded data to be decoded next in the coded buffer 1101, and what is the next pixel X _{i + 1} of the encoded data of the pixel of interest X _i, performs a decoding process. This is easy to understand if the prediction encoded data in FIG. 8B is decoded. Although details will be described later, the component value prediction decoding unit 1704 outputs pixel data (three component data) obtained by decoding at a timing when the switch 1106 selects a decoding result of the next pixel X _{i + 1.} To do. Further, the component value predictive decoding unit 1704 performs a process of advancing the bit position to be read next by the number of bits of the encoded data used in the decoding process.

<When Ep = 2>
The component value predictive decoding unit 1704 assumes that the encoded data to be decoded next in the encoding buffer 1101 is the encoded data of the pixel of interest X _i and performs a decoding process. This can be easily understood if the predicted encoded data in FIG. 8C is decoded. The component value predictive decoding unit 1704 outputs pixel data (three component data) obtained by decoding at a timing when the switch 1106 selects a decoding result of the pixel of interest X _i . Further, the component value predictive decoding unit 1704 performs a process of advancing the bit position to be read next by the number of bits of the encoded data used in the decoding process.

<When Ep = 3>
The component value predictive decoding unit 1704 assumes that there is predictive encoded data for two pixels from the encoded data to be decoded next in the encoding buffer 1101, and performs each decoding process. This can be easily understood if the predictive encoded data in FIG. 8D is decoded.

The component value predictive decoding unit 1704 outputs the pixel data obtained by decoding as pixel data X _i and X _{i + 1} . The component value predictive decoding unit 1704 outputs the pixel of interest X _i and the next pixel X _{i + 1 in accordance} with the selection timing of the switch 1106 described later. Also, the component value predictive decoding unit 1704 performs a process of advancing the bit position to be read next by the number of bits of encoded data for two pixels used in the decoding process.

<When Ep = 4 or 5>
The component value predictive decoding unit 1704 assumes that the encoded data to be decoded next in the encoding buffer 1101 is the encoded data of the pixel of interest X _i and performs a decoding process. In the case of Ep = 4, the decoding of the neighborhood matching pixel information Vp in FIG. 8C has already been completed. Therefore, the component value predictive decoding unit 1704 has the codeword of the neighborhood matching pixel information Vp in FIG. Each component encoded data from the next position is decoded. When Ep = 5, the encoded data to be decoded has the data structure shown in FIG.

The component value predictive decoding unit 1704 outputs pixel data (three component data) obtained by decoding at a timing when the switch 1106 selects a decoding result of the pixel of interest X _i . Also, the component value predictive decoding unit 1704 performs a process of advancing the bit position to be read next by the number of bits of encoded data for one pixel used in the decoding process.

The component value predictive decoding unit 1704 outputs pixel data obtained by decoding as pixel data X _i . Also, the component value predictive decoding unit 1704 outputs the target pixel X _i together with the selection timing of the switch 1106 described later.

  Note that the predictive decoding process in the component value predictive decoding unit 1704 may be performed in reverse to the encoding process. Briefly described is as follows.

  The prediction error decoding unit 1702 refers to the Huffman table stored in the Huffman table memory 204, acquires necessary code data from the code buffer 1101, and decodes the prediction error of the pixel component of interest. The component value prediction unit 202 generates and outputs a prediction value p for the component value of interest using the prediction formula selected by the prediction formula selection signal m, similarly to the case of encoding. The adder 1111 adds the prediction error e decoded by the prediction error decoding unit 1104 to the prediction value p output from the component value prediction unit 202, and restores and outputs the component value of interest. By performing this process for three components, one pixel data can be decoded.

  Next, processing contents of the selector 1703 in the embodiment will be described.

The selector 1703 surrounds the pixel of interest X _i read from the buffer 201 according to the color number Nc output from the color number determination unit 107 and the neighborhood match information Vp input from the match pixel position decoding unit 1701 via the signal line 1109. One of the component values of the pixels Xa, Xb, Xc, and Xd is selected once or twice, and each component data for one pixel or two pixels is selectively output. Here, the timing for selecting the first pixel data among the two pixels is defined as T1, and the timing for outputting the second pixel data is defined as T2. At timing T1, the decoding result of the pixel of interest X _i is selected. At timing T2, the decoding result of the next pixel X _{i + 1} is selected. As is clear from the above description, one piece of encoded data is generated from one pixel when the number of colors Nc is 3 or 4. That is, when the color number Nc is 3 or 4, the decoded data for one pixel is output from the encoded data for one pixel. For convenience, the timing for outputting decoded data for one pixel from encoded data for one pixel is also T1.

  FIG. 10 shows pixels that the selector 1703 selects at timings T1 and T2 based on the number of colors Nc and the neighborhood match information Vp. In the figure, X1, X2, and X3 are pixel values obtained by a process similar to that performed by the neighborhood match determination unit 101 in the image coding apparatus.

In FIG. 7, for example, when the number of colors Nc = 1 and Vp = 0, both the target pixel X _i and the next pixel X _{i + 1} are the neighboring pixels Xa (= Xb = Xc = Xd) as can be seen from FIG. It shows that it is the same color. Accordingly, the selector 1703 selects and outputs the pixel Xa at both timings T1 and T2.

The color number Nc = 2 and Vp = 6 from Figure 7, the target pixel X _i and the same color neighboring pixels Xa, Xb, Xc, not present in the Xd, the next pixel X _{i + 1} is the pixel X1 It shows that it is the same color. Accordingly, the selector 1703 selects and outputs the pixel X1 at the timing T2, as shown in the figure.

  In FIG. 10, the “-” mark indicates that the selector 1703 does not perform processing, or the selector 1703 may or may not select any of the neighboring pixels Xa, Xb, Xc, and Xd. . This is because the switch 1106 to be described later does not select the terminal b for inputting data from the selector 1703 at the timing indicated by the “−” mark.

  Next, the switch 1106 will be described. The switch 1106 can be easily understood from the description of FIG. That is, in FIG. 10, at the timing of “−”, the terminal a is selected to select the decoding result decoded by the component value predictive decoding unit 1704, and is output from the selector 1702 except for “−”. The terminal b may be selected to select pixel data.

  In the embodiment, the mismatch pixel information Ep is supplied to the switch 1106. FIG. 11 shows the selection conditions of the terminals a and b at the timings T1 and T2 in the switch 1106.

  The discrepancy pixel information Ep is a value in the range of 0 to 5, as is apparent from the above description.

Here, in the case of Ep = 0 in FIG. 7, both the target pixel X _i and the next pixel X _{i + 1} are equal to any of the neighboring pixels Xa, Xb, Xc, and Xd of the target pixel X _i. Promised. Therefore, when Ep = 0, the switch 1106 selects the terminal b at both timings T1 and T2.

When Ep = 1, as can be seen from FIG. 7, the pixel of interest X _i is equal to one of the neighboring pixels Xa, Xb, Xc, and Xd, and the next pixel X _{i + 1} is predicted to be encoded by the prediction error. Show. That is, the next pixel X _{i + 1} is none other than being decoded by the component value predictive decoding unit 1704. Accordingly, the switch 1106 selects the terminal b at the timing T1, and selects the terminal a at the timing T2.

Further, when Ep = 2, as can be seen from FIG. 7, the pixel of interest X _i is different from any of the neighboring pixels Xa, Xb, Xc, and Xd, indicating that it is predictively encoded. Further, it is indicated that pixels having the same color as the next pixel X _{i + 1} exist in the neighboring pixels Xa, Xb, Xc, Xd. Accordingly, the switch 1106 selects the terminal a at the timing T1, and selects the terminal b at the timing T2.

Further, in the case of Ep = 3, as can be seen from FIG. 7, both the target pixel X _i and the next pixel X _{i + 1} are encoded with the prediction error. Accordingly, the switch 1106 selects the terminal a at the timings T1 and T2, selects the decoded data from the component value prediction decoding unit 1704, and outputs it.

  As described above, when Ep = 0, 1, 2, and 3, the switch 1106 selects the encoded data for two pixels at the timings T1 and T2. When Ep = 4 or 5, encoded data for one pixel is decoded and output. That is, the switch 1106 needs to operate only at the timing T1.

When Ep = 4 or 5, as can be seen from FIG. 7, the pixel of interest X _i is encoded with a prediction error. That is, one piece of encoded data indicates one piece of pixel data. Accordingly, the switch 1106 may select the terminal a, select the decoded data from the component value predictive decoding unit 1704, and output it at the timing T1.

  As can be seen from the above description, if the number of colors Nc and the neighborhood match information Vp are known, the mismatch pixel information Ep can be uniquely determined. Accordingly, Ep may be supplied to the selector 1703 instead of supplying Nc and Vp. For the same reason, Nc and Vp may be supplied to the switch 1106.

According to the present embodiment as described above, in the vicinity of the target pixel X _i of the encoding target, already encoded pixels Xa, Xb, Xc, the color count Nc contained Xd extracted (detected) , Nc is 1 or 2, the pixel of interest X _i and the next pixel X _{i + 1} are grouped to generate encoded data. Thereby, the reversible compression performance of image data, such as a character, a line drawing, and a CG image, which is highly likely to have pixels of the same color around the pixel of interest can be greatly improved.

  In particular, when Nc is 1 or 2, it is possible to generate encoded data of 1 bit at the shortest for two pixels to be encoded. When one pixel is composed of three components and each component is 8 bits, two pixels of the original image are represented by 8 × 3 × 2 = 48 bits. Since this can be expressed by 1 bit, it can be understood how good the encoding efficiency is.

  When Nc is 4, that is, when Xa, Xb, Xc, and Xd are all different colors, the encoded data of the neighboring pixel matching information Vp is not added, and each component of the pixel of interest is predicted. It encodes (FIG.8 (e)). As a result, even when encoding image data having a low matching probability with surrounding pixel values such as a natural image, it is possible to maintain the same code amount as in the prediction error encoding process. In this embodiment, when Nc is 4, that is, only when the number of neighboring reference pixels matches the number of colors, the neighboring pixel matching information is not encoded, and each component of the pixel of interest is predicted code. It was set as the structure which becomes. However, even when the number of colors and the number of surrounding reference pixels are different, if it is considered that encoding using the neighboring pixel matching information is not efficient, each component of the pixel of interest may be encoded. For example, when the number of surrounding pixels to be referenced is increased and compared with the surrounding 6 pixels, if Nc is 5 or more, the neighborhood matching pixel information is not used and each component of the pixel of interest is encoded. I do not care.

  In addition, since whether or not to apply the encoding of the neighborhood matching information Vp is switched in units of pixels, it is possible to obtain a good compression performance for an image in which characters, photographs, and the like are mixed.

[Modification of First Embodiment]
An example in which the first embodiment is realized by a computer program will be described below as a modification of the first embodiment.

  FIG. 14 is a block configuration diagram of an information processing apparatus (for example, a personal computer) in the present modification.

  In the figure, reference numeral 1401 denotes a CPU which controls the entire apparatus using programs and data stored in a RAM 1402 and a ROM 1403 and executes application programs for image encoding processing and decoding processing described later. A RAM 1402 includes an area for storing programs and data downloaded from the external device via the external storage device 1407, the storage medium drive 1408, or the I / F 1409. The RAM 1402 also includes a work area used when the CPU 1401 executes various processes. Reference numeral 1403 denotes a ROM which stores a boot program, a setting program for the apparatus, and data. Reference numerals 1404 and 1405 denote a keyboard and a mouse, respectively. Various instructions can be input to the CPU 1401.

  A display device 1406 includes a CRT, a liquid crystal screen, and the like, and can display information such as images and characters. Reference numeral 1407 denotes a large-capacity external storage device such as a hard disk drive device. The external storage device 1407 stores an OS (operating system), a program for image encoding and decoding processing described later, image data to be encoded, encoded data of an image to be decoded, and the like as files. The CPU 1401 loads these programs and data into a predetermined area on the RAM 1402 and executes them.

  A storage medium drive 1408 reads programs and data recorded on a storage medium such as a CD-ROM or DVD-ROM and outputs them to the RAM 1402 or the external storage device 1407. In addition, a program for image encoding and decoding processing described later, image data to be encoded, encoded data of an image to be decoded, and the like may be recorded on the storage medium. In this case, the storage medium drive 1408 loads these programs and data into a predetermined area on the RAM 1402 under the control of the CPU 1401.

  Reference numeral 1409 denotes an I / F, which connects an external device to the present apparatus through the I / F 1409 and enables data communication between the present apparatus and the external apparatus. For example, image data to be encoded, encoded data of an image to be decoded, and the like can be input to the RAM 1402, the external storage device 1407, or the storage medium drive 1408 of this apparatus. A bus 1410 connects the above-described units.

  In the above configuration, when the power of this apparatus is turned on, the CPU 1401 loads the OS from the external storage device 1407 to the RAM 1402 in accordance with the boot program stored in the ROM 1403. As a result, the keyboard 1404 and the mouse 1405 can be input, and the GUI can be displayed on the display device 1406. When the user operates the keyboard 1404 or the mouse 1405 to instruct the activation of the image processing application program stored in the external storage device 1407, the CPU 1401 loads the program into the RAM 1402 and executes it. As a result, this apparatus functions as an image processing apparatus.

  Hereinafter, an image encoding process procedure when the program is executed will be described with reference to the flowchart of FIG.

  In the following description, an example in which image data to be encoded is a color image data file stored in the external storage device 1407 and the encoding result is stored as a file in the external storage device 1407 will be described. However, the type of image data to be encoded and the output destination of the encoding result are not limited. For example, the source of the image data to be encoded may be an image scanner, and the output destination may be a network. In the following description, the buffer 108 shown in FIG. 1 and various necessary tables (including the Huffman table) are assumed to be secured in a memory such as the RAM 1402. Furthermore, when the pixel of interest to be encoded is at the edge position of the image, among the neighboring pixels Xa, Xb, Xc, and Xd, there are pixels that are located outside the image. In this way, each component value of a pixel outside the image is regarded as “0” and encoding is performed.

  First, in step S1, the CPU 1401 analyzes the header of the image data file to be encoded, generates a header of the file to be encoded and outputs it. At this time, the header of the output file includes information necessary for decoding, such as the size of the image data (the number of pixels W in the horizontal direction, the number of pixels H in the vertical direction), and the prediction formula selection signal m. Note that the prediction formula selection signal m may be appropriately selected by a user from a GUI (not shown). When the image data from the image scanner is encoded, the above W and H can be obtained based on the document size and the reading resolution of the image scanner. From then on, the encoded data generated by the encoding process is stored so as to follow the created header.

  Next, in step S2, a variable (counter) y that holds the vertical position of the pixel of interest is set to 0. In step S3, data for one line indicated by the variable y is read from the image data to be decoded. Include. Then, a variable (counter) x that holds the horizontal position of the pixel of interest is set to 0 (step S4). Here, the range that the variable y can take is 0 ≦ y ≦ W−1, and the range that the variable x can take is obviously 0 ≦ x ≦ H−1.

Next, in step S5, when the coordinate (x, y) is the pixel of interest X _i , the neighboring pixels Xa, Xb, Xc, Xd are read, and the number of colors Nc included in the neighboring pixels is calculated (or detected). . As described above, the pixel data of the neighboring pixels Xa, Xb, Xc, and Xd can be defined as follows.
Xa = (P (x-1, y, 0), P (x-1, y, 1), P (x-1, y, 2))
Xb = (P (x, y-1, 0), P (x, y-1, 1), P (x, y-1, 2))
Xc = (P (x-1, y-1, 0), P (x-1, y-1, 1), P (x-1, y-1, 2))
Xd = (P (x + 1, y-1, 0), P (x + 1, y-1, 1), P (x + 1, y-1, 2))

As described above, when the target pixel is at the edge position of the image, there are pixels in the neighboring pixels that are located outside the image. Each component of the pixels outside the image is treated as having the same value as that of the image encoding device (in the embodiment, each component is “0”).

  In step S6, it is determined whether or not the calculated color number Nc is “4”. If the color number Nc is any one of 1 to 3, the process proceeds to step S7, the same processing as in the first embodiment is performed, and the neighborhood match information Vp and the mismatch pixel information Ep of the neighborhood match determination unit 101 are processed. Generate the data. In step S8, the neighborhood match information Vp is encoded and output. That is, based on the number of colors Nc, one table is selected from FIGS. 12A to 12C, the code word of the neighborhood match information Vp is selected and output with reference to the selected table. Then, the process proceeds to step S10.

  On the other hand, if it is determined in step S6 that the calculated color number Nc is “4”, the process proceeds to step S9, the mismatch pixel information Ep is set to “5”, and the process proceeds to step S10. That is, the encoding process of the neighborhood match information Vp is not performed.

  As a result, when the number of colors Nc is “3” or less, encoded data of the neighborhood match information Vp is generated as shown in FIGS. Further, the value of the mismatch pixel information Ep is determined. However, when the color number Nc is “4”, the encoded data of the neighborhood match information Vp is not added as shown in FIG.

When the process proceeds to step S10, the CPU 1401 determines whether the mismatched pixel information Ep is 2, 3, 4, or 5. The discrepancy pixel information Ep is one of 2, 3, 4, 5, as can be seen from FIG. 7, the prediction error encoding each component of the pixel of interest X _i represented by the coordinates (x, y) It is shown that.

Therefore, when the mismatch pixel information Ep is any of 2, 3, 4, and 5, the process proceeds to step S11, and each component of the pixel of interest X _i is subjected to prediction error encoding, and the generated encoded data is output. Then, the process proceeds to step S12.

  If it is determined in step S9 that the mismatch pixel information Ep is 0 or 1, the process proceeds to step S12 without performing the process in step S11.

In step S12, it is determined whether or not the mismatch pixel information Ep is 1 or 3. The non-matching pixel information Ep is 1 or 3, as can be seen from FIG. 7, predictive error coding is performed for each component of the next pixel X _{i + 1} of the pixel of interest X _i indicated by coordinates (x, y). It is shown that.

Accordingly, when the mismatch pixel information Ep is 1 or 3, the process proceeds to step S13, and each component of the next pixel X _{i + 1} is subjected to prediction error encoding, and the generated encoded data is output. Then, the process proceeds to step S14.

  If it is determined in step S12 that the mismatched pixel information Ep is any of 0, 2, 4, and 5, the process proceeds to step S14 without performing the process in step S13.

  As a result, the generation and storage of the encoded data in FIGS. 8A to 8E are completed. In particular, when Ep = 0, the predictive encoding in steps S11 and S13 is not performed, and as a result, as shown in FIG. 8A, encoded data of only the neighborhood match information Vp is generated.

  In step S14, the variable x is updated. Specifically, when the number of colors Nc is 1 or 2, encoded data of 2 pixels is generated, so “2” is added to the variable x. When the number of colors Nc is 3 or 4, since only the pixel of interest is encoded, “1” is added to the variable x.

  In step S15, it is determined whether or not encoding has been completed up to the end pixel of one line. This may be determined based on whether or not the relationship between the variable x and “W” is “x ≧ W”. If it is determined that the encoding of one line is incomplete, the processes after step S5 are repeated.

  If it is determined in step S15 that the encoding process for one line has been completed, the process proceeds to step S16, and the variable y is increased by “1”. Then, in step S17, it is determined whether or not the encoding process for the final line has been completed by comparing the variables y and H. If it is determined that y <H, the processes after step S3 are performed.

  If it is determined in step S17 that y = H, the series of image data encoding processing (encoding processing for one page) ends.

  As described above, according to the present modification, the same processing as that of the image encoding device in the first embodiment described above can be realized by a computer program, and the same operational effects can be achieved. Become.

  Next, the processing procedure of the computer program for decoding the encoded image data will be described with reference to the flowcharts of FIGS. This process is performed when an encoded image data file stored in the external storage device 1407 is selected using a GUI (not shown), and an input of a decoding start instruction is detected using the GUI. Since the decoding result is displayed on the display device 1406, the image data obtained by decoding is stored in the RAM 1402. Of course, the output destination may be the external storage device 1407, and the type is not limited.

  First, in step S21, the header of the file to be decrypted is analyzed, and information necessary for decryption is acquired. Here, the main process is to obtain the horizontal pixel count W, vertical pixel count H, and prediction formula selection signal m. The prediction formula selection signal m is used to determine a calculation formula for the predicted value p of the pixel of interest when performing the prediction error decoding process.

  Next, in step S22, a variable (counter) y that holds the vertical position of the pixel of interest is set to 0. In step S23, a variable (counter) x that holds the horizontal position of the pixel of interest is set to 0. Set to. Here, the range that the variable y can take is 0 ≦ y ≦ W−1, and the range that the variable x can take is obviously 0 ≦ x ≦ H−1.

In step S24, when the coordinate (x, y) is the pixel of interest X _i , the neighboring pixels Xa, Xb, Xc, Xd are read from the decoded image data (RAM 1402), and the number of colors Nc included in the neighboring pixels is calculated. (Or detect). The principle of calculating the number of colors Nc is as already described. Since x = 0 and y = 0 in the initial state, the neighboring pixels Xa, Xb, Xc, and Xd are all pixels outside the image. In this way, each component value of the pixel located outside the image is regarded as 0, and the number of colors Nc is calculated.

  In step S25, it is determined whether or not the calculated number of colors Nc is “4”. If Nc = 4, the process proceeds to step S26, where the mismatch pixel information Ep is set as “5”, and the process proceeds to step S29.

  On the other hand, if it is determined that the color number Nc is any one of “1”, “2”, and “3”, the process proceeds to step S27, and what is to be decoded is the encoded data of the neighborhood match information Vp. The neighborhood match information Vp is decoded. Then, in step S28, the table as shown in FIG. 7 is referred to, and the mismatch pixel information Ep is calculated based on the number of colors Nc and the neighborhood match information obtained by decoding, and the process proceeds to step S29. .

  In step S29, it is determined whether or not the value of the mismatch pixel information Ep is “0”. If Ep is “0”, the process proceeds to step S30. If Ep is other than “0”, the process proceeds to step S37 (FIG. 17).

  Here, first, a case where the mismatch pixel information Ep is “0” and the process proceeds to step S30 will be described.

  When the mismatch pixel information Ep is “0”, the encoded data has a data structure shown in FIG. As described in the first embodiment, the encoded data in FIG. 8A indicates that the encoded data is for two pixels when the number of colors Nc = 1 or 2. On the other hand, when the number of colors Nc = 3, the encoded data in FIG. 8A is encoded data for one pixel.

Therefore, in step S30, it is determined whether or not the number of colors Nc is “3”. If it is determined that the number of colors Nc is other than “3”, that is, Nc = 1 or 2, the process proceeds to step S31. In step S31, referring to the table of FIG. 7, the target pixel X _i and the next pixel X _{i + 1} are determined from the neighboring pixels according to the neighborhood matching information Vp and the color number Nc obtained by decoding, and output. To do.

If it is determined in step S30 that the number of colors Nc is “3”, the process proceeds to step S32, where the number of colors Nc and the neighborhood matching information Vp obtained by decoding are used to determine the number of neighboring pixels. From this, the target pixel X _i is determined and output.

  On the other hand, if it is determined in step S29 that the mismatch pixel information Ep is other than “0”, the process proceeds to step S37.

In this step S37, it is determined whether or not the mismatch pixel information Ep is “1”. Ep = 1 indicates that the encoded data has the data structure shown in FIG. Also, there 7, equal to either the neighboring pixels the target pixel X _i is also indicated that the next pixel X _{i + 1} are predictive coding.

Therefore, if it is determined that Ep = 1, first, in step S38, the pixel of interest X _i is determined from the neighboring pixels based on the decoded neighborhood matching information Vp and output. In step S39, the predictive encoded data of each component is used to predictively decode the next pixel X _{i + 1} and output it. Then, the process proceeds to step S33.

  If it is determined in step S37 that the mismatch pixel information Ep is other than “1”, that is, the mismatch pixel information Ep is “2” or more, the process proceeds to step S40.

In this step S40, it is determined whether or not the mismatch pixel information Ep is “2”. Ep = 2 indicates that the encoded data has the data structure shown in FIG. Further, from FIG. 7, are predictive encoding different from the one of the neighboring pixels the target pixel X _i is next pixel X _{i + 1} indicates that equal to one of the neighboring pixels.

Therefore, if it is determined that Ep = 2, first, in step S41, the pixel of interest X _i is predictively decoded from the prediction encoded data and output. Next, in step S42, the next pixel X _{i + 1} is determined from the neighboring pixels of the pixel of interest X _i based on the decoded neighborhood matching information Vp and output. Then, the process proceeds to step S33.

  If it is determined in step S40 that the mismatch pixel information Ep is other than “2”, that is, the mismatch pixel information Ep is “3” or more, the process proceeds to step S43.

When Ep = 3, 4, and 5, it indicates that the encoded data has one of the data structures shown in FIGS. 8C, 8D, and 8E. The common point of the structure of these encoded data is that the pixel of interest X _i is predictively encoded. Therefore, in step S43, the target pixel X _i is decoded and output using the predicted encoded data.

Next, in step S44, it is determined whether or not the mismatch pixel information Ep is “3”. When Ep = 3, the encoded data has the data structure shown in FIG. Accordingly, in step S45, the next pixel X _{i + 1} is predictively decoded and output. Then, the process proceeds to step S33.

If it is determined in step S44 that the mismatched pixel information Ep is “4” or “5”, the encoded data is one of FIGS. 8C and 8E, and the target pixel X _i is Since it has already been decoded in step S43, the process proceeds to step SS33 without performing the process of step S45.

  As described above, when one pixel or two pixels are decoded based on the mismatch pixel information Ep, the process proceeds to step S33 (FIG. 16).

  In step S33 (FIG. 16), the variable x is updated. In step S33, when two pixels are decoded and output from one encoded data, that is, when the processes of steps S31, S39, S42, and S45 are performed, “2” is added to the variable x. Further, when one pixel is decoded and output from one encoded data, that is, when Steps S32 and S44 are No, “1” is added to the variable x.

  In step S34, it is determined whether or not the decoding process for one line has been completed. This determination may be made by determining whether or not the variable x ≧ W. When it is determined that the decoding process for one line is incomplete (x <W), the processes after step S24 are performed. If it is determined that the decoding process for one line has been completed (x ≧ W), the process proceeds to step S35 and the variable y is incremented by “1”. In step S36, it is determined whether or not the decoding process for all lines has been completed, in other words, whether or not y = H. If it is determined that the decoding process for all lines is incomplete (y <H), the process from step S23 is performed. If it is determined that the decoding process for all lines is complete (y = H), it is assumed that the decoding process for one page of images has been completed, and this process ends.

  As described above, according to this modification, processing equivalent to that of the first embodiment described above can be realized by a computer program, and the same effect as that of the first embodiment can be achieved.

[Other Embodiments]
In the above embodiment, when the number of colors Nc is “3”, the value of the neighborhood match information Vp has a value of 0 to 3 (see FIG. 7). Then, as shown in FIG. 12C, a code word of 1 to 3 bits is assigned to the value of the neighborhood match information Vp. Although it depends on the type of target image, if the number of colors Nc is “3” and a high probability that the pixel of interest X _i matches a neighboring pixel cannot be expected, the code word of the neighborhood matching information Vp is 3 bits. Probability is high.

  Therefore, when the number of colors Nc = 3, it is possible to determine whether the first pixel value X1 and the second pixel value X2 match / mismatch, and not to determine matching / mismatch with the third pixel X3. .

That is, Vp = 0 when the pixel of interest X _i = X1, and Vp = 1 when X _i = X2. In the case of X _i ≠ X 1 and X _i ≠ X 2, a symbol that takes three values of 0, 1, 3 such as Vp = 3 (a process of comparing the neighborhood match information Vp and Nc is considered and “2 May be encoded). Since there are only three symbols, if 0, 10, and 11 are assigned as binary codewords, the neighborhood match information Vp can be 2 bits at the maximum.

  In the embodiment, X1, X2, and X3 are determined in the order of neighboring pixels Xa, Xb, Xc, and Xd. However, the present invention is not limited to this. For example, Xa, Xb, Xc, and Xd may be rearranged depending on the number of colors Nc.

  In addition, as a method of encoding neighborhood match information, a method using a code word determined in advance assuming a probability distribution has been shown. However, a code word different from the above example may be used, or a code different from an arithmetic code or the like may be used. You may apply a conversion method.

  In addition, as a prediction method of a component value to be focused on, several prediction methods may be prepared and switched adaptively, or a component that focuses on an average value of prediction errors generated in each encoded component value It is also possible to use non-linear prediction such as feedback to the prediction.

  Although an example in which Huffman coding is used as the entropy coding of the component value prediction error is shown here, other entropy coding such as Golomb coding may be used.

Further, although an example in which Xa, Xb, Xc, and Xd are referred to as the surrounding pixel values of the pixel of interest X _i has been shown, more pixels may be referred to, or the number of reference pixels may be set such as only Xa and Xb. You can reduce it.

  In the embodiment, the RGB image data is the encoding target, but an image in a color space other than this may be used. For example, image data composed of a plurality of components, such as YMC images, Lab images, and YCrCb images, can be applied.

  In the embodiment and its modification, the number of colors Nc included in the four neighboring pixels is obtained. When the number of colors Nc = 1 or 2, one encoded data is generated from two pixels. When the number of colors Nc = 3 or 4, one encoded data is generated from one pixel.

  This is because the smaller the number of colors Nc, the higher the probability that pixels having the same color will continue. In other words, when the number of colors Nc is equal to or less than a threshold (in the embodiment, “2”), one piece of encoded data is generated from a plurality of pixels, and when the number of colors Nc exceeds the threshold, 1 This is nothing but generating one piece of encoded data from a pixel.

  Further developing this, when the number of colors Nc = 1, one encoded data is generated from three pixels, and when the number of colors Nc = 2, one encoded data is generated from two pixels. In the case of the number Nc = 3 or 4, one encoded data may be generated from one pixel. That is, the number of neighboring pixels is assumed to be M, and is defined as the number of colors Nc included therein, and a function f (Nc) (or table) that returns a larger value (integer) as Nc is smaller is prepared. One encoded data may be generated from (Nc) pixels. At this time, if f (Nc) = M, that is, if the number of colors Nc matches the number of neighboring pixels, it is not necessary to encode the neighborhood matching information Vp. However, it should be noted that as the number of pixels that can be encoded at a time increases, the range of possible values of the neighborhood match information Vp increases, and the number of bits of the codeword of the neighborhood match information Vp increases. It is.

  Further, as described in the embodiments, the present invention can also be realized by a computer program. Usually, the computer program is stored in a computer-readable storage medium such as a CD-ROM, and can be executed by setting it in a reader provided in the computer 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 image coding apparatus in embodiment. It is a block block diagram of the conventional prediction encoding apparatus. It is a figure which shows the relative positional relationship of an encoding object pixel and its vicinity pixel. It is a figure which shows the prediction formula corresponding to the prediction formula selection signal m. It is a figure which shows a response | compatibility with the prediction error e and group number SSSS. It is a figure which shows the table which shows a response | compatibility with group number SSSS and a code word. It is a figure which shows the correspondence with the number of colors Nc, proximity | contact matching information Vp, and mismatching pixel information Ep. It is a figure which shows the data structure of the encoding data produced | generated with the encoding apparatus of embodiment. It is a figure which shows the data structure of the encoding image data file produced | generated with the encoding apparatus of embodiment. It is a figure which shows the table for demonstrating the operation | movement content of the selector of the decoding apparatus in embodiment. It is a figure which shows the table for demonstrating the operation | movement content of the switch of the decoding apparatus in embodiment. It is a figure which shows the table used at the time of encoding and decoding of the near match information Vp. It is a block block diagram of the image decoding apparatus in embodiment. It is a block block diagram of information processing apparatus. It is a flowchart which shows the process sequence at the time of implement | achieving the encoding process of image data with a computer program. It is a flowchart which shows the process sequence at the time of implement | achieving the decoding process of image data with a computer program. It is a flowchart which shows the process sequence at the time of implement | achieving the decoding process of image data with a computer program.

Claims (12)

An image encoding device for losslessly encoding image data,
Input means for inputting image data in raster order;
Color number determination means for determining the number of colors included in a plurality of neighboring pixels that have been encoded and are located in the vicinity of the target pixel Xi to be encoded in the input image;
A first lossless encoding means for reversibly encoding the pixel of interest Xi and generating encoded data when the number of colors determined by the color number determination means is equal to or greater than a predetermined color number Cn;
A pixel number determination unit that determines the number of pixels to be encoded for generating one encoded data when the number of colors determined by the color number determination unit is less than the predetermined color number Cn;
When the number of pixels to be encoded determined by the pixel number determining means is defined as n (n ≧ 1), each of the n pixels Xi, Xi + 1,. For each of the n pixels, it indicates whether or not a pixel of the same color exists in the plurality of neighboring pixels, and if there is a pixel of the same color, the position of the neighboring pixel that is the same color Vector information generating means for generating vector information indicating
Vector information encoding means for encoding vector information generated by the vector information generation means and generating encoded vector data;
A second lossless encoding means for losslessly encoding each of the pixels in the n pixels determined to have no pixel of the same color among the plurality of neighboring pixels;
When the number of colors determined by the color number determination unit is equal to or greater than the predetermined number of colors Cn, the encoded data generated by the first lossless encoding unit is output,
When the number of colors determined by the color number determination means is less than the predetermined number of colors Cn, the encoded vector data generated by the vector information encoding means and the second lossless encoding means are obtained. And an output means for outputting the encoded data.   The image coding apparatus according to claim 1, wherein the predetermined number of colors Cn is the number of the plurality of neighboring pixels.   3. The image encoding apparatus according to claim 1, wherein the number-of-colors determination unit sets the n to a larger value as the number of colors included in the plurality of neighboring pixels is smaller. When the coordinates of the pixel of interest Xi are defined as (x, y) and the data of the pixel of interest Xi is defined as P (x, y),
The plurality of neighboring pixels are the following four pixels Xa, Xb, Xc, Xd,
Xa = P (x-1, y)
Xb = P (x, y-1)
Xc = P (x-1, y-1)
Xd = P (x + 1, y-1)
The pixel number determining means determines that the number of pixels to be encoded is 2 when the number of colors determined by the color number determining means is 1 or 2, and the number of colors determined by the color number determining means is 3 In this case, it is determined that the number of pixels to be encoded is 1. The image encoding device according to claim 3,   The vector information encoding means has a plurality of encoding tables, selects one of the plurality of encoding tables according to the number of colors determined by the number of colors determination means, and selects the selected encoding table. The image encoding apparatus according to claim 1, wherein the vector information is encoded using the image encoding apparatus.   6. The image encoding apparatus according to claim 1, wherein the first and second lossless encoding units are prediction error encoding units. A control method for an image encoding device that performs lossless encoding of image data,
An input process for inputting image data in raster order;
A color number determination step for determining the number of colors included in a plurality of already-encoded neighboring pixels located in the vicinity of the target pixel Xi to be encoded in the input image;
When the number of colors determined in the number-of-colors determination step is equal to or greater than a predetermined number of colors Cn, the first lossless encoding step of reversibly encoding the pixel of interest Xi and generating encoded data;
When the number of colors determined in the number-of-colors determination step is less than the predetermined number of colors Cn, a number-of-pixels determining step for determining the number of pixels to be encoded for generating one encoded data;
When the number of pixels to be encoded determined in the pixel number determining step is defined as n (n ≧ 1), each of the n pixels Xi, Xi + 1,. For each of the n pixels, it indicates whether or not a pixel of the same color exists in the plurality of neighboring pixels, and if there is a pixel of the same color, the position of the neighboring pixel that is the same color A vector information generating step for generating vector information indicating:
A vector information encoding step for encoding vector information generated in the vector information generation step and generating encoded vector data;
A second lossless encoding step of losslessly encoding each of the pixels in the n pixels determined to have no pixel of the same color among the plurality of neighboring pixels;
When the number of colors determined in the number-of-colors determination step is equal to or greater than the predetermined number of colors Cn, the encoded data generated in the first lossless encoding step is output,
When the number of colors determined in the color number determination step is less than the predetermined number of colors Cn, the encoded vector data generated in the vector information encoding step and the second lossless encoding step are obtained. An image encoding device control method comprising: an output step of outputting encoded data.   A computer program that causes a computer to function as the image encoding device according to any one of claims 1 to 6 when the computer reads and executes the computer program. An image decoding apparatus for decoding encoded data generated by the image encoding apparatus according to claim 1,
Input means for inputting encoded image data encoded in raster order;
Storage means for storing the decoded pixel data in a memory;
Color number determination means for determining the number of colors located in the vicinity of the pixel of interest Xi to be decoded and included in a plurality of already decoded neighboring pixels in the memory;
When the number of colors determined by the number-of-colors determination unit is equal to or greater than a predetermined number of colors Cn, the first target pixel is decoded by assuming that the encoded data to be decoded is lossless encoded data of the target pixel. Lossless decoding means;
When the number of colors determined by the number-of-colors determination unit is smaller than the predetermined number of colors Cn, the encoded data to be decoded is regarded as encoded vector data, and the encoded vector data is decoded to generate vector information Vector information decoding means,
Based on the number of colors and the vector information, n indicating the number of encoded pixels is determined, and among the n pixels Xi, Xi + 1,..., Xn, the same color in the plurality of neighboring pixels is determined. For the pixel, the pixel data at the position specified by the vector information among the plurality of neighboring pixels is output as a decoding result,
Among the n pixels Xi, Xi + 1,..., Xn, for the pixels that do not match any of the plurality of neighboring pixels, the lossless encoded data input subsequent to the encoded vector data is reversible. And a second lossless decoding means for decoding and outputting the image decoding apparatus. A control method for an image decoding device for decoding encoded data generated by the image encoding device according to claim 1, comprising:
An input step of inputting encoded image data encoded in raster order;
A storage step of storing the decoded pixel data in a memory;
A color number determination step for determining the number of colors included in a plurality of already decoded neighboring pixels in the memory, located in the vicinity of the target pixel Xi to be decoded;
When the number of colors determined in the number-of-colors determination step is equal to or greater than a predetermined number of colors Cn, it is assumed that the encoded data to be decoded is lossless encoded data of the target pixel, and the first pixel that decodes the target pixel A lossless decoding process;
When the number of colors determined in the color number determination step is smaller than the predetermined number of colors Cn, the encoded data to be decoded is regarded as encoded vector data, and the encoded vector data is decoded to generate vector information A vector information decoding step,
Based on the number of colors and the vector information, n indicating the number of encoded pixels is determined, and among the n pixels Xi, Xi + 1,..., Xn, the same color in the plurality of neighboring pixels is determined. For the pixel, the pixel data at the position specified by the vector information among the plurality of neighboring pixels is output as a decoding result,
Among the n pixels Xi, Xi + 1,..., Xn, for the pixels that do not match any of the plurality of neighboring pixels, the lossless encoded data input subsequent to the encoded vector data is reversible. And a second lossless decoding step of decoding and outputting the control method.   A computer program that causes a computer to function as the image decoding device according to claim 9 by being read and executed by the computer.   A computer-readable storage medium storing the computer program according to claim 8 or 11.

Images