JP2651209B2 - Image encoding method and apparatus - Google Patents

Description

Description: BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an image encoding method and apparatus for encoding an image.

[Conventional technology]

In a facsimile device that is a typical example of a conventional still image communication device, an image is scanned sequentially,
A scheme is used in which an image is encoded and transmitted using MH, MR encoding or the like.

In this method, it is necessary to transmit all of the image data in order to grasp the entire image of the image. Therefore, it takes a long time to transmit the image data, and it is necessary to quickly determine the image such as an image database service video tex. It has been difficult to apply to image communication services.

Therefore, as an encoding method applicable to this service, for example, a pixel of interest is predicted from a plurality of peripheral pixels in the vicinity of the pixel of interest to be coded, such as arithmetic coding, and the predicted pixel is compared with the actual pixel of interest. It has been proposed to encode an image based on the match or mismatch of.

According to this, it is possible to achieve simpler and more efficient encoding than a conventional configuration such as MH and MR encoding.

[Problems to be solved by the invention]

However, in such encoding, parameters necessary for predicting a target pixel based on peripheral pixels are predetermined using a standard image, and a predictive predictive value is different for an image having characteristics different from the standard image. However, the coding efficiency is deteriorated, and sometimes the encoded data becomes longer than the original data.

[Means for solving the problem]

The present invention has been made in view of the above points, and an object of the present invention is to provide an image encoding method and an encoding device that efficiently predictively encode an image. A reference step of referring to the plurality of pixels referred to, and holding of a parameter indicating a predicted value of a pixel of interest of the encoding target image and a probability of occurrence of the predicted value corresponding to a state of the plurality of referred pixels. An encoding step of encoding a pixel of interest of the image to be encoded based on the stored prediction value and the parameter, wherein the pixel of interest of the encoded image to be encoded is a dominant symbol Or the updating step of updating the stored predicted value and the parameter according to whether the symbol is a less-than symbol, further comprising a plurality of parameters, and A setting step of setting a plurality of tables in which the plurality of parameters included at each change at a different change rate; and determining whether a pixel of interest of the encoded image to be encoded is a superior symbol or an inferior symbol. Selecting one of the plurality of tables on the basis of the plurality of tables, and in the updating step, updating the stored parameters based on the plurality of parameters included in the selected table. The present invention also provides an encoding method of an image characterized by: a reference unit that refers to a plurality of predetermined pixels of an image to be encoded; and a state corresponding to a plurality of pixels that are referred to by the reference unit. Holding means for holding a prediction value of a pixel of interest of the encoding target image and a parameter indicating a probability of occurrence of the prediction value; and Encoding means for encoding the pixel of interest of the image to be encoded based on the prediction value and the parameter held, and the pixel of interest of the image to be encoded encoded by the encoding means is dominant Updating means for updating the predicted value and the parameter held in the holding means depending on whether the symbol is a symbol or a lesser symbol, the updating means, each including a plurality of parameters, and Storage means for storing a plurality of tables in which each of the plurality of parameters included in each of the plurality of parameters changes at a different change rate. Whether the pixel of interest of the encoding target image encoded by the encoding means is a dominant symbol. One of the plurality of tables is selected based on whether the symbol is the inferior symbol, and stored in the holding unit based on the plurality of parameters included in the selected table. It is an object of the present invention to provide an image coding apparatus characterized by updating the stored parameters.

〔Example〕

 FIG. 1 shows an embodiment of an encoder to which the present invention is applied.

First, original image data I _1, which is binary data indicating white / black of each pixel of the original image, is stored in the first frame memory 10.
Next, the first low-pass filter 11 performs a smoothing process, and the first comparator 12 performs binarization again. The first low-pass filter 11, is inputted parameters C ₁ to adjust the degree of smoothness, also, the first comparator 12 threshold T ₁ is inputted, the image quality of these values is required, and reference numeral It is determined by the controller 9 based on the conversion efficiency. Next, the first sub-sampling 13 generates a signal 101 representing an image thinned out vertically and horizontally by half. This signal 101 is stored in the second frame memory 14.

On the other hand, the signal 101 is likewise the second low-pass filter 1.
5, the second comparator 16 and the second sub-sampling 17 generate a signal 102 representing a quarter image. This signal 102 is stored in the third frame memory 18. Also, as described above,
Reference numeral 102 denotes a signal 1 representing an image having a size of 1/8 by the third low-pass filter 19, the third comparator 20, and the third sub-sampling 21.
03 is obtained. This signal 103 is stored in the fourth frame memory 22. The second and third low-pass filters have parameters C ₂ and C ₃ , respectively, and the second and third comparators have thresholds T ₂ and C ₂ , respectively.
T ₃ is input by the controller 9.

The signal 103 is encoded by the first encoder 23 and
It is transmitted as a stage signal 104.

The second encoder 24 performs encoding while referring to the data in the fourth frame memory 22 and the third frame memory 18, and
The stage signal 105 is transmitted. Similarly, the third encoder 25 performs encoding with reference to the data in the third frame memory 18 and the second frame memory 14, and transmits the signal 106 at the third stage. Similarly, the fourth encoder 26 performs encoding while referring to the data of the second frame memory 14 and the data of the first frame memory 10, and transmits the signal 107 at the fourth stage. As described above, the first to fourth encoders encode image data having different resolutions.

As described above, the image data from the first stage to the fourth stage are coded and transmitted in order from the image data having the lower resolution, so that the receiving side can quickly identify the entire image of the image before transmitting the image data having the higher resolution. If the data is unnecessary, it is possible to stop transmission of the subsequent high-resolution image data. As a result, the communication time for unnecessary data can be reduced, and an efficient image communication service can be provided.

 FIG. 2 shows an embodiment of a decoder to which the present invention is applied.

The first-stage signal 104, which is set to 1/8 by the encoder, is decoded by the first decoder 27 and stored in the fifth frame memory 31. This signal is converted into high-resolution data by an eight-fold interpolation process by the first interpolator 35, and is then stored in the video memory 39 by switching the selector 38 by the controller 42. The video memory 39 is composed of a two-port memory that can input and output in parallel. Therefore, the image decoded on the receiving side is displayed on the monitor 40 at any time.

Further, the second stage signal 105 encoded by the decoder based on the 1/4 and 1/8 images is decoded by the second decoder 28 with reference to the data of the fifth frame memory 31, Sixth
It is stored in the frame memory 32. This data is
A quadruple interpolation process is performed by the interpolator 36, and the selector 38 is switched to be stored in the video memory 39.

Similarly, a third stage signal 106 encoded based on the 1/2 and 1/4 images by the encoder and a fourth stage signal encoded based on the original image and the 1/2 image. After the signal 107 is decoded by the third and fourth decoders 29 and 30 and the seventh and eighth frame memories 33 and 34 and the third interpolator 37, the signal 107 is stored in the video memory 39 and displayed on the monitor 40. .

On the other hand, the signal of the eighth frame memory 34, which is the decoded image signal of the fourth stage, is output to the printer 41 to obtain a hard copy.

FIG. 3 shows filter coefficients of a low-pass filter having a 3 × 3 pixel size used as the first, second and third low-pass filters used in the encoder shown in FIG. The weighting coefficient of 2 is assigned to the four pixels closest to the center pixel, and the weighting coefficient of 1 is assigned to the pixel closest to the center pixel.

Thereby, the value of the center pixel is set to D _ij (i = 1 to M, j = 1 to
Assuming that N: M and N are the horizontal and vertical pixel sizes, the average density W is W = (D _{i−1, j−1} + 2D _ij−1 + D _{i + 1j−1} + 2D _i−1j + cD _ij) + 2D _{i + 1j} + D _{i−1, j + 1} + 2D _{ij + 1} + D _{i + 1, j + 1} ).

In the first, second and third comparators, this value W is set to a threshold value. Is set as a standard setting value).

The corresponding relationship is given.

FIG. 4 is a block diagram of a low-pass filter and a comparator for performing the above operation. The input signals are latches 44a, b, c
Are held with a delay of one pixel clock. Also,
The line memories 43-a, b hold the input signals delayed by one line, respectively, and latches 44d, e, f and latches 43d, e, f.
In g, h, i, signals corresponding to the latches a, b, c and the pixel positions are obtained. As a result, data of nine pixels shown in FIG. 3 is obtained. The output signals from the latches 44a, c, g, and i are summed up by an adder 45a, and a multiplication by a constant (× 1) is performed by a multiplier 46a.

The output signals from the latches 44b, d, f, h are added to an adder 45b.
, And is multiplied by a constant (× 2) in the multiplier 46b.
The output signal from the latch 44e, which is the median value, is multiplied by a constant (× C) by the multiplier 46c. The value of C can be set by an external controller 9, but the standard value is C = 4.

The output signals of the multipliers 46a, b, c are summed by an adder 47 and then compared with a threshold T by a comparator 48. When the sum is larger than the threshold T, it is 1; Signal. This threshold value T can also be set from the external control unit 9, but takes a value of T = (12 + C) / 2 as a standard value as described above.

FIG. 5 is an explanatory diagram of the subsampling operation used in the encoder shown in FIG. 1 in each of main scanning and sub-scanning directions
By taking out pixel data indicated by hatching in the figure at every other timing, a sub-sampled image of 1/2 size (1/4 in area) is formed. This can be easily realized by adjusting the latch timing of the image data.

Next, encoding by the encoders 23 to 26 shown in FIG. 1 will be described. In the present embodiment, encoding is performed using an arithmetic code, the value of the pixel of interest is predicted from the surrounding pixels, and the symbol when the prediction is consistent is the superior symbol (1), and the symbol when the prediction is out is the inferior symbol (0). , P is the probability of occurrence of the inferior symbol, and coding is performed using this information. For arithmetic coding, refer to Nikkikan Kogyo, “Signal Processing of Images for FAX and OA,” by Kibukibuki.

That is, the binary arithmetic code represented by the code sequence s is represented by C (S),
If the auxiliary amount is A (S), However, the coding is advanced by the arithmetic operation of A (null) = 0.11...

Incidentally, by approximating p (S) = 2- ^{Q (S)} , the multiplication is completed only by the binary shift. Q is called a skew value, and by changing this parameter, an arithmetic code can be dynamically used.

In decoding, the binary signal sequence S is set to S'xS ". When the sequence is restored to S ', C (S) is compared with C (S') + A (S'0), and C (S)> C (S ' ) + A (S'0), x =
1. Decode as X = 0 otherwise.

In the present embodiment, dynamic encoding is realized by dynamically determining the above-mentioned skew value Q and the superior symbol m (or the inferior symbol l) based on previously encoded data. As an encoding for this method,
There is dynamic coding in which the values of Q and m are determined in advance from a standard image, and the two have different characteristics.

A configuration for achieving the above encoding will be described below.

FIG. 6 is a block diagram of a circuit portion for predicting a target pixel in the second, third, and fourth encoders shown in FIG.

The frame memory A51 is a memory that stores image data to be encoded for at least one screen. Further, the frame memory B52 stores at least one screen of image data obtained by subsampling the image of the frame memory A51, which is the image sent one stage before, by half.
Each memory is composed of a two-dimensional memory. the clock of the x address and φ _1, the clock of the y address φ
Assuming that ₂ , the frame memory A51 has φ ₁ , φ ₂ ,
Frame in the memory B52 1/2 [phi ₁ 1/2 frequency, 1/2 [phi ₂ is provided, thereby to 1 pixel of the frame memory B52, the pixel of the frame memory A51 corresponds to four pixels of 2 × 2.

Each data becomes data delayed one line at a time in the line memories 53a, b and 54a, b.
Entered in 6. In this latch, data delayed one pixel at a time is held. If the output of each latch corresponds to the pixel position in FIG. 7, the pixel of interest (*) is the output of the latch 55j (pixel pixel signal D301), FIG. 7 is the output of the latch 55i, and FIG. No. 3 is the output of the latch 55h, No. 4 is the output of the latch 55f, No. 5 is the output of the latch 55e, No. 6 is the output of the latch 55b, and No. 7 is the output of the latch 55d.

8, the pixel positions of No. 8 are the latch 56e, No. 9 is the latch 56f, No. 10 is the latch 56d, No. 11 is the latch 56c, No.
12 is Latch 56h, No. 13 is Latch 56g, No. 14 is Latch 56i
Output.

The pixel of No. 8 in FIG. 8 is a pixel including the pixel of interest, and which position of the pixel of interest is No. 8 (upper left, upper right,
A 2-bit pixel position signal 59 for identifying the four states (lower left and lower right) is generated by the counter 60 based on the clocks φ ₁ and φ ₂ .

The pixel signals from the pixel position signal 59 and the latches 55 and 56 are input to an LUT (lookup table) 57, and a group signal G300 indicating the group number of each state (pattern) is input.
Is output.

 This grouping is performed according to the following three policies.

(1) Patterns with similar predicted matching rates are collected.

(2) Put together patterns having similar pattern shapes.

(3) Collect characteristic image patterns.

First, a predicted matching rate k for each state (pattern) is obtained from a standard image according to the method (1), and the prediction matching rate k is divided into N groups according to the value of k. Among them, the prediction pixels (mps) are divided into N × 2 groups, with white as 0 and black as 1.

Next, according to the above policy (2), a pattern in which all the pixels indicated by the circles have the same value (excluding the states of other pixels) is extracted from the prediction pattern as shown in FIG. And group A. Next, all the pixels shown in FIG. 7B except for the group A and having the same extraction pattern are referred to as the group B. Further, according to the above-mentioned policy (3), a pattern such as that shown in FIG. 10C (characters marked with a circle and pixels marked with an opposite value) have the same characteristics as those shown in FIG. , A group other than the B group is a C group. Also, patterns other than A, B, and C are set as a D group.
FIG. 11 shows such a grouping.
G ₁ , G ₂ ,..., G _8N are the group numbers of each pattern. K _i (i = 1 to n) is the probability at the division point. The number of groups and the similar pattern shape shown here are not limited to the present embodiment.

As described above, not only the prediction match probability but also grouping based on pattern similarity, characteristic pattern separation, and the like, it is possible to adaptively encode an image other than the standard image.

The prediction circuit in the first encoder 23 shown in FIG.
In the illustrated configuration, line memories 54a, b, latches 56a-i, and a counter 60 for processing the output of the frame memory B52.
Is removed.

FIG. 13 is a block diagram of a dynamic adaptation circuit for dynamically changing the skewness Q and the inferior symbol in the encoder. The group signal G300 and the pixel signal of interest D301 output from the prediction circuit unit shown in FIG. 6 are input to the group occurrence frequency counter 90 and the inferior symbol counter 91, respectively. In these counters, internal counters are easily provided by the number of groups so as to perform a counting operation for each group, and are switched by a group signal G.

The occurrence frequency counter 90 counts how many times the state of the group has occurred for each group, and outputs an update signal 303 when the count value of each group exceeds the set value S302. The number of inferior symbols generated between the time when the previous update signal is generated and the time when the next update signal is generated is counted by the counter 91 for each group, and is output as a count value lc304. That is, based on the output of the counter 91, it is shown that lc out of S occurrences of a certain group are inferior symbols. In the following description, S
= 16 will be described as a representative.

In LUT92, for the occurrence of lc inferior symbols,
Next encoding parameter, Q _G 305 and previous mps
An inverted signal 306 for inverting the (dominant symbol) value and data called a zero count (CT) 307 are stored in advance.

The zero count is a value indicating the number of times in the past where 0 is not generated in S inferior symbols lc, and represents the number of consecutive occurrences of superior symbols.
That is, in principle, if CT = 0 is initially set, CT is updated to 1 when the state of lc in S is 0, and then CT = 2, CT = 3 when it is repeated two or three times. It will be updated.

 FIG. 14 shows an example of the LUT 92.

In the initial state, CT = 0 is set, and a new Q _G and a next CT value are obtained from the respective values of lc. For example, CT =
When 0 and lc = 0, Q _G = 4 and CT = 1. Then update signal 30
When 3 comes, CT = 1 and when lc =, Q _G = 5 and CT = 2.

When CT = 0 and lc = 1, Q _G is updated to 4, and CT = 1.

The formula to create this table is In equation (2), Q _G is the exponent when the probability of occurrence of the inferior symbol generated when (CT + 1) S states continue is approximated by a power of 2.

In equation (3), the CT ^calculates the occurrence of the inferior symbol by 1/2 ^QG
Is assumed, the number of S lc = 0 sets is recalculated. Since 2 ^QG is the number of dominant symbols, the value obtained by dividing this by S is CT.

Also, when CT = 0 Is treated as a special case, an mps inversion signal is output, and the value that has been used as the conventional inferior symbol is inverted (that is, the operation of setting it to 1 is performed. Thereafter, CT = 0, In other cases, the encoding process is performed normally without changing the inferior symbol.

In FIG. 13, a latch 93 stores a conventional Q _G 305, an mps inverted signal 306, and a CT 307.
The output of the LUT 92 is latched and updated to a new state by the update signal 303 from.

The count signal lc of the inferior symbol and the CT value 307 indicating the number of the still superior symbol are input to the input of the LUT 92.
The Q _G and CT updated according to the table shown in the figure and the mps inverted signal as required are output. The mps holder 95 holds the dominant symbol (0 or 1) used in the encoding up to now, and this state is inverted by the mps inversion signal. The mps / ▲ ▼ signal output from the retainer 95 is sent to the inferior symbol counter 91,
Counts pixel data D corresponding to the inferior symbol represented by the mps / ▲ ▼ signal as inferior symbols.

Here determined the Q _G and mps / ▲ ▼ the coding is to be performed.

FIG. 9 is a block diagram of the arithmetic encoder. Assuming that Q _G 305 from the latch 93 shown in FIG. 13 is a skew value, Q
By giving _G 305 and MPS / ▲ 308, the arithmetic operation shown in equation (1) is performed on the target pixel data D301 by the encoder 190, and encoded data 192 is obtained.

In this way, the skew value Q, which is an encoding parameter, and the dominant symbol are dynamically determined based on previously encoded data, and the encoding operation is performed. Can also achieve efficient encoding.

FIG. 10 shows the first, second, third and fourth decoders 27, 28 and 2 shown in FIG.
It is a block diagram of 9,30. The decoder is also provided with a prediction circuit and a dynamic adaptation circuit as shown in FIGS. 6 and 13 which are similar to the encoder, and the skew value Q _G d9 on the decoder side is provided.
4 and lesser symbol LPSd197 from LUT and received data 195
The decoding operation is performed in the decoder 191 by the
Get.

As another method for determining the content of the LUT 92 shown in FIG. 13, lc / S is obtained from the number of inferior symbols lc in the S pixel,
Some method of determining the new Q _G from the relationship shown in FIG. 15.
The initial value is Q _G = 1, and Q _G is updated with the value of lc / S. Sequentially Q _G the second and subsequent use the Q _G and lc / S which has been updated
Will be determined. The updated value Q _G ′ is Calculation is performed using a calculation formula such as that described above and stored in a table.
In addition, when Q = 1 and lc / S> 1/2, at 500, the superior and inferior symbols are inverted.

Figure 16 inputs the Q _G signal 305 in the exemplary dynamic adaptive circuit when using the LUT into LUT 92, will determine the update Q _G.

Further, in the present embodiment, a dynamic arithmetic code has been described as an encoding method, but the present method can be applied to a method using dynamic parameters in other encoding methods.

〔The invention's effect〕

As described above, according to the present invention, with reference to a plurality of predetermined pixels of an encoding target image, a prediction value of a target pixel of the encoding target image and its prediction value corresponding to a state of the plurality of pixels are provided. In the configuration in which the parameter indicating the probability of occurrence of the target pixel is held and the pixel of interest of the image to be coded is encoded based on the prediction value and the parameter, the pixel of interest of the coded image to be coded is the superior symbol or the inferior symbol Since the prediction value and the parameter are updated depending on whether the symbol is used, it is possible to dynamically and adaptively execute the encoding using the prediction value and the parameter suitable for the content (property) of the image to be encoded. It is possible to improve the coding efficiency, and furthermore, a plurality of tables are provided, each of which includes a plurality of parameters, and in which each of the plurality of parameters changes at a different change rate. Selecting one of a plurality of tables based on whether the pixel of interest of the encoded image to be encoded is a superior symbol or an inferior symbol, and sets a parameter based on a plurality of parameters included in the selected table. Since the table is updated, a plurality of tables are switched and used according to the occurrence state of the superior symbol and the inferior symbol, so that the parameters used for the dynamic and adaptive coding are adapted to the occurrence state of the superior symbol and the inferior symbol. And the coding efficiency can be further improved.

[Brief description of the drawings]

FIG. 1 is a block diagram of an embodiment of an encoder, FIG. 2 is a block diagram of an embodiment of a decoder, FIG. 3 is a diagram showing coefficients of a low-pass filter, and FIG. 4 is a block diagram of an embodiment of a low-pass filter. FIG. 5 is an explanatory diagram of sub-sampling, FIG. 6 is a block diagram of a prediction circuit, FIG. 7 is an explanatory diagram of a reference pixel on a code plane, and FIG. 8 is an explanatory diagram of a reference pixel of an image one stage before. , FIG. 9 is a block diagram of an arithmetic code encoder, FIG. 10 is a block diagram of an arithmetic code decoder, FIG. 11 is a diagram showing an example of a table for grouping, and FIG. FIG. 13 is a diagram showing an example of a pattern, FIG. 13 is a block diagram of a circuit for dynamically determining coding parameters Q and l, FIG. 14 is a diagram showing an example of a table for determining parameters, and FIG. FIG. 16 shows an example of a table used in the embodiment. FIG. 16 shows a second embodiment. Is a diagram showing, LU is the frame memory A, 52 is a frame memory B, 57 51
T and 90 are occurrence frequency counters, 91 is an inferior symbol counter, and 92 is an LUT.

 ────────────────────────────────────────────────── ─── Continuation of the front page (56) References JP-A-63-76525 (JP, A) JP-A-63-164575 (JP, A) IEEE TRANSACTIONS ON COMMUNICATIONS Vol. COM-29 [6] (1981) 858-867

Claims (4)

(57) [Claims] A reference step of referring to a plurality of predetermined pixels of an encoding target image; and a prediction value of a pixel of interest of the encoding target image corresponding to a state of the referenced plurality of pixels. A holding step of holding a parameter indicating a probability of occurrence of a predicted value; an encoding step of encoding a target pixel of the encoding target image based on the held predicted value and the parameter; An updating step of updating the stored predicted value and the parameter according to whether the pixel of interest of the image to be encoded is a superior symbol or an inferior symbol, further comprising: A setting step of setting a plurality of tables including parameters, wherein the plurality of parameters included in each of the plurality of tables change at different change rates; and Selecting one of the plurality of tables based on whether the pixel of interest of the image to be converted is a dominant symbol or a dominant symbol, and in the updating step, And updating the stored parameters based on a plurality of parameters. 2. The image processing apparatus according to claim 1, further comprising a forming step of forming a low-resolution reduced image from the image to be encoded, wherein the formed reduced image is encoded as an image to be encoded. 2. The image encoding method according to 1., 3. A reference unit for referring to a plurality of predetermined pixels of an encoding target image, and prediction of a target pixel of the encoding target image corresponding to a state of the plurality of pixels referred to by the reference unit. Holding means for holding a value and a parameter indicating the probability of occurrence of the predicted value; coding means for coding a target pixel of the coding target image based on the predicted value and the parameter held by the holding means And updating the prediction value and the parameter held in the holding unit according to whether the pixel of interest of the encoding target image encoded by the encoding unit is a superior symbol or an inferior symbol. Updating means, wherein the updating means includes a plurality of tables, each of which includes a plurality of parameters, and wherein the plurality of parameters included in each of the tables change at different change rates. A storage unit for storing, wherein one of the plurality of tables is selected based on whether a pixel of interest of the image to be encoded encoded by the encoding unit is a superior symbol or an inferior symbol. An image encoding apparatus for updating the parameters stored in the storage unit based on the plurality of parameters included in the table. 4. The image processing apparatus according to claim 1, further comprising forming means for forming a low-resolution reduced image from said coding target image, wherein said reduced image formed by said forming means is coded as a coding target image. The image encoding device according to claim 3.