JPH07121065B2 - Encoding / decoding device - Google Patents

Description

Description: TECHNICAL FIELD The present invention relates to a coding / decoding in a hierarchical coding system in which an image decimated in a first stage is coded, and an image complementing the interval is sequentially coded in a second stage and thereafter. It relates to the device.

2. Description of the Related Art With the diversification of facsimile communication, it has been considered to use a facsimile terminal in combination with a display terminal for interactive image communication and image database search. As a coding method suitable for such interactive image communication, in contrast to conventional coding methods such as MR method for sequentially coding from the top to the bottom of an image according to scanning lines,
A method of performing hierarchical encoding processing such as a sequential reproduction encoding method (for example, Japanese Patent Laid-Open No. 60-127875) has been proposed.

The sequential reproduction coding method performs coding in the following procedure.

(1) Run by connecting every ΔX = 2 ⁿ (n = integer) pixels in the horizontal (main scanning) direction and ΔY = 2 ⁿ (n = integer) lines in the vertical (sub-scanning) direction. Performs length coding.

(2) Next, the pixel located at the center surrounded by the rectangle of the four adjacent coded pixels is set to 5 states according to the number of black devices of the reference pixels with these 4 pixels as reference pixels. The pixels are classified, and pixels corresponding to each state are connected to perform run-length coding.

(3) Next, the pixel located at the center surrounded by the four adjacent coded pixels surrounded by the rhombus is set to 5 states according to the number of black pixels of the reference pixels with these 4 pixels as reference pixels. The pixels are classified, and pixels corresponding to each state are connected to perform run-length coding.

(4) The encoding of (2) and (3) is repeated until all the pixels are encoded.

FIG. 7 is a diagram showing the concept of the coding order in the sequential reproduction coding method in the case of ΔX = ΔY = 4. First, the pixels marked with ⊚ are coded. Next, the circled pixels are the already coded circled pixels, and the four nearest neighbors surrounding the circled pixels are used as reference pixels, and are coded according to the number of black pixels of the reference pixels. Next, the Δ-marked pixels are the already-encoded ◎ -marked and ◯ -marked pixels, and the four nearest neighbors surrounding the Δ-marked pixels in the diamond shape are used as reference pixels, and are coded by the number of black pixels of the reference pixels To do. Next, the x-marked pixels are the already coded ◎ -marked, ◯ -marked and Δ-marked pixels, and the four nearest neighbors surrounding the x-marked pixel in the rectangle are used as reference pixels, and the number of black pixels of the reference pixels is set. Encode separately. Finally, the pixel of the mark is the already coded pixel of the ◎ mark, the ○ mark, the Δ mark and the X mark, and the nearest 4 pixels that surround the pixel of the mark in a diamond shape.
One of the reference pixels is used as a reference pixel, and the reference pixels are encoded according to the number of black pixels.

When configuring a device that performs encoding / decoding, reference pixels,
Reading and writing the coded pixel and the decoded pixel in parallel with the memory storing the pixels leads to an improvement in the processing speed.
In the above sequential reproduction coding method, it is desirable to handle reference pixels, coded pixels, and decoded pixels in parallel in a state where only necessary pixels are sampled every 2 ⁱ (i = integer) with respect to the original pixels.

On the other hand, prepare 2 ^j memories that can independently give addresses,
2 ^{j + k} pixels are set as one block, and within this block, 1 /
A data storage method has been proposed in which 2 ^j- bit data reduced to 2 ⁱ (0 ≦ i ≦ k) can be accessed at one time.

This method, when grouping the 2 ^{j + k-number} results data sampled according to the reduction ratio of each 2 ^j number in each block, 2 ^j-number of data in each group can operate in parallel a 2 ^j-number of memory decompose defines a method for storing 2 ^{j + k} pieces of data to be stored (e.g., JP-60-
3039, JP-A-60-81661).

By using the memory device using the above storage method as a memory for storing pixels in the above sequential reproduction coding method, only pixels necessary for the original pixels are sampled every 2 ⁱ (i = integer). In this state, the reference pixel, the code pixel and the decoded pixel can be handled in parallel.

Problems to be Solved by the Invention In the sequential reproduction coding method described above, when first extracting pixels, ΔX = 2 ⁿ (n = integer) pixels in the horizontal direction and ΔY = 2 ⁿ ( ^{n in the} vertical direction). A memory using the above storage method can be used because ΔX and ΔY are exponentiated to 2 for each (n = integer) line.

However, ΔX and ΔY do not have to be powers of 2 by modifying a part of the above algorithm. FIG. 2 is a diagram showing the concept of the encoding order and its pixels when ΔX = ΔY = 5. In the figure, the sequence up to the encoding of the pixel indicated by-is the same as that shown in FIG. Next, the pixels marked with * are the already-encoded pixels marked with ◎, ○, Δ, ×, and ・, and the four nearest neighbors surrounding the pixel marked with ※ are used as reference pixels, and are referred to. Encoding is performed for each number of black pixels. Finally, the pixel marked with ▽ is the already coded ◎, ○
Among the pixels of the mark, Δ mark, × mark, · mark, and * mark, the four nearest neighbors surrounding the ▽ mark pixel are set as reference pixels, and the pixels are coded according to the number of black pixels of the reference pixels.

In the encoding / decoding in this case, the sampling of pixels necessary for the original pixel is not every power of 2, and the memory device using the above storage method cannot be used. It becomes impossible to read and write in parallel to the memory in a state where only the necessary pixels are sampled, and the processing speed decreases.

The present invention has been made in view of the above circumstances, and provides a coding / decoding device for performing coding / decoding processing on a pixel extracted for each pixel that is not an exponentiated power of 2 in the main scanning direction. It is an object.

Means for Solving the Problems In order to solve the above-mentioned problems, the present invention provides, in the main scanning direction,
When the encoding / decoding process is performed on the pixels extracted for each ΔX pixel that is not a power of 2, the image signal is moved in the main scanning direction.
It is multiplied by 2 ⁿ / ΔX (2 ⁿ > ΔX, n = integer), and the pixels obtained by extracting the converted image signal every 2 ⁿ pixels are subjected to encoding / decoding processing.

Action The image signal that is multiplied by 2 ⁿ / ΔX in the main scanning direction will be subjected to encoding / decoding processing for the pixels extracted every 2 ⁿ pixels,
By using the memory device using the above-described storage method that can access 2 ^j- bit data reduced to 1/2 ⁱ (0 ≦ i ≦ k) at a time, a pixel portion necessary for the original pixel can be obtained. Can be read and written in parallel to the memory in a sampled state, so that the processing speed in the encoding / decoding device is improved.

Embodiment FIG. 1 is a block diagram showing an embodiment of an encoding / decoding device of the present invention. In the figure, 1 is a single-screen memory that stores an image to be encoded and a decoded image, 2 is a conversion circuit that performs enlargement conversion and reduction conversion, and 3 is 1/2 ⁱ (0 ≦ i ≦
A reduction memory 4 capable of accessing the 2 ^j- bit data reduced to k) at a time is a code / decoding circuit for generating code data from code pixels and reference pixels and reproducing decoded pixels from the code data and reference pixels.

The encoding will be described by taking the case of encoding in the order shown in FIG. 2 (when first extracting pixels, ΔX = 5 pixels in the horizontal direction and ΔY = 5 pixels in the vertical direction) as an example. The image to be encoded in FIG. 2 is stored in the single screen memory 1. Since the pixels extracted every ΔX = 5 pixels in the horizontal direction will be subjected to the encoding process, the image stored in the one-screen memory 1 is enlarged in the horizontal direction by the conversion circuit 2 to 8/5 times. And writes it in the reduced memory 3. If the parallel bit number of the reduced memory 3 is 8 bits, 8-bit data reduced to 1/2 ⁱ (0 ≦ i ≦ 3) will be written to the reduced memory 3 by a storage method that can be accessed at one time. FIG. 3 is a diagram showing an image written in the reduction memory 3 by being enlarged 8/5 times in the horizontal direction, and an image with a minus sign is don't care.

First, the encoding / decoding circuit 4 reads out the pixel marked with ⊚ from the reduction memory 3 and encodes it. In each line, the code pixel is stored in the reduction memory 3 every 8 pixels.
The decoding circuit 4 accesses the reduced memory 3 to reduce the data to 1/8 to read only the code pixels in each line for 8 bits at a time and encode them.

Next, the pixels marked with a circle are encoded. The encoding / decoding circuit 4 reads out this pixel and the reference pixel (pixels marked with ⊚) from the reduction memory 3 and encodes them. For example, the reference pixels of the code pixel 22 are pixels 00, 05, 50, 55. In each line, the code pixel and the reference pixel are stored in the reduction memory 3 for every 8 pixels, so that the encoding / decoding circuit 4 has 1/8 of the reduction memory 3.
By accessing the data reduced to, only each pixel in each line is read out and encoded for 8 bits at a time.

Next, the pixels marked with Δ are encoded. The encoding / decoding circuit 4 reads out and encodes this pixel and the reference pixel (pixels marked with ⊚ and ◯) from the reduction memory 3. For example, the reference pixels of the code pixel 25 are pixels 05, 22, 27, 55. Since the code pixels and the reference pixels on each line are stored in the reduced memory 3 every 8 pixels, the encoding / decoding circuit 4 accesses the reduced memory 3 by reducing the data to 1/8. , 8 bits of each pixel are read out at once in each line and encoded.

Next, the pixels marked with X are encoded. The encoding / decoding circuit 4 reads out and encodes this pixel and reference pixels (pixels marked with ⊚, ◯ and Δ) from the reduction memory 3. For example, the reference pixels of the code pixel 11 are pixels 00, 02, 20, 22. Since the code pixels and the reference pixels on each line are stored in the reduced memory 3 for every 8 pixels, the encoding / decoding circuit 4 accesses the reduced memory 3 by reducing the data to 1/4. , 8 bits of each pixel are read out at once in each line and encoded.

Next, the pixel of the mark is encoded. The encoding / decoding circuit 4 receives this pixel and the reference pixel (⊚, ○, Δ, ×) from the reduction memory 3.
(The pixel of the mark) is read and encoded. For example, code pixel 12
The reference pixels of 0 are pixels 02, 11, 13, 22, and the reference pixels of the code pixel 15 are pixels 05, 13, 16, 25. In each line, the code pixel and the reference pixel are stored in the reduced memory 3 for every 4 pixels.
By accessing the data reduced to 4, only each pixel in each line is read out 8 bits at a time,
Encode.

Next, the pixels marked with * are encoded. The encoding / decoding circuit 4 reads out and encodes this pixel and the reference pixel (pixels marked with ⊚, ×, ...) from the reduction memory 3. For example, reference pixels of the code pixel 44 are pixels 33, 35, 53, 55, and reference pixels of the code pixel 49 are pixels 38, 3A, 58, 5A. In each line, the code pixel is stored in every 8 pixels in the reduction memory 3, and the necessary reference pixel is stored in every 2 pixels at the finest place in the reduction memory 3. Access is performed so that the finest part can be read at the same time (access of data reduced to 1/2). As a result, on each line, the pixels including the required code pixels and the reference pixels are read out in 8 bits at a time, and the encoding / decoding circuit 4 encodes using only the required pixels.

Next, the pixel marked with ∇ is encoded. The encoding / decoding circuit 4 receives this pixel and the reference pixel (⊚, Δ, ×,
・ Pixel marked with * is read and encoded. For example, the reference pixels of the code pixel 45 are pixels 35, 44, 49, 55, the reference pixels of the code pixel 46 are pixels 36, 44, 49, 56, and the reference pixels of the code pixel 54 are pixels 44, 53, 55, 94. is there. In each line, the code pixels may be stored in the reduced memory 3 every 8 pixels or in every 2 pixels, and the necessary reference pixels are stored in every 2 pixels at the finest place in the reduced memory 3. Therefore, the encoding / decoding circuit 4 can access the reduced memory 3 at the same time to read the finest part (1/2
Access the reduced data). As a result, on each line, pixels including necessary code pixels and reference pixels are read out at once in 8 bits, and the encoding / decoding circuit 4 encodes using only the necessary pixels.

A case of decoding the data encoded in the order shown in FIG. 2 will be described.

When the pixels are first extracted, since the encoding processing is performed for each ΔX = 5 pixels in the horizontal direction, the decoding processing is performed by assuming an image that is magnified 8/5 times in the horizontal direction.

First, the encoding / decoding circuit 4 decodes the pixel marked with ⊚ from the encoded data. Since the decoded pixels in each line are multiplied by 8/5 in the horizontal direction, it suffices to store every 8 pixels in the reduced memory 3, so that the encoding / decoding circuit 4 has 1/8 of the reduced memory 3.
By accessing the data reduced to, only the decoded pixels are written in 8 bits at a time in each line.

Next, the encoding / decoding circuit 4 reads the reference pixel (pixel marked with ⊚) from the reduction memory 3 and decodes the pixel marked with ∘ from the coded data based on this pixel. Since the decoded pixels are multiplied by 8/5 in the horizontal direction in each line, it is sufficient to store every 8 pixels in the reduced memory 3, and the reference pixel in each line is the reduced memory 3.
Since the data is stored in every 8 pixels in, the encoding / decoding circuit 4 accesses the reduced memory 3 by reducing the data to 1/8 so that only each pixel in each line is 8 bits at a time. Read and write.

Hereinafter, the same applies to the decoding of the pixels marked with Δ. Also,
The decoding of the pixels marked with X and .circle-solid. Is the same except that the data reduced to 1/4 is accessed to the reduced memory 3.

When decoding the pixels marked with *, the coding / decoding circuit 4 reads the reference pixels (pixels marked with ◎, ×, ...) from the reduction memory 3 and decodes the pixels marked with * from the coded data based on these pixels. To do. In each line, the decoded pixel is multiplied by 8/5 in the horizontal direction, so
It suffices to store every 8 pixels in the reduction memory 3, and since the reference pixel required in each line is stored in every 2 pixels at the finest part in the reduction memory 3, the encoding / decoding circuit 4 is set to the reduction memory 3 By performing an access (access of the data reduced to 1/2) at the same time for the finest part, a pixel including a reference pixel and a decoded pixel required for each line is read and written at 8 bits at a time. When decoding the pixels marked with ▽,
The decoding circuit 4 receives the reference pixels (⊚, Δ,
The pixels marked with ×, ·, * are read out, and the pixels marked with ▽ are decoded from the coded data based on these pixels. Decoded pixels in each line are multiplied by 8/5 in the horizontal direction, so 8
It may be stored for each pixel or for every two pixels. Since the reference pixel required for each line is stored for every two pixels at the finest point in the reduction memory 3, the encoding / decoding is performed. The circuit 4 accesses the reduced memory 3 so that the finest part can be read and written at the same time (access of data reduced to 1/2), so that the pixels including the reference pixel and the decoded pixel required for each line are 8 bits at a time. Read and write.

In the writing, when the access to every 8 pixels is good to the access to every 2 pixels, the extra data is written in the reduced memory 3 at the don't care (-mark), so that the decoded pixel is not collapsed.

By the above decoding processing, the image shown in FIG. 3 is decoded in the reduction memory 3. Since this image is scaled by 8/5 in the horizontal direction, the original image is reproduced by reducing the size in the horizontal direction by 5/8 in the conversion circuit 2 and writing it in the one-screen memory 1.

FIG. 4 is a diagram showing the concept of the encoding order and the pixels in the case of ΔX = ΔY = 3, and the encoding is ⊚, Δ, and ×.
The mark and the pixel of the mark are in order. In this case, the original image may be multiplied by 4/3 in the horizontal direction and similarly encoded and decoded. FIG. 5 is a diagram showing an image in which the image of FIG. 4 stored in the single screen memory 1 is laterally enlarged by 4/3 times in the conversion circuit 2 and written in the reduced memory 3. Image is do
n't care.

In the above description, only the horizontal direction is enlarged, but the vertical direction is also enlarged so that the lines to be extracted are every exponentiation of 2, and the address calculation in the vertical direction can be simplified. FIG. 6 is a diagram showing an image in which the image of FIG. 4 stored in the one-screen memory 1 is enlarged by 4/3 times in the horizontal and vertical directions in the conversion circuit 2 and written in the reduced memory 3. Images marked with-are don't care.

EFFECTS OF THE INVENTION According to the present invention, when the extraction unit of the horizontal code pixels or the like is not the exponentiation power of 2, expansion conversion is performed so that the extraction unit is the exponentiation power of 2, so that 1/2 ⁱ (0 ≦ 2 ^j reduced to i ≦ k)
It becomes possible to use a memory device that uses a storage method capable of accessing bit data at one time. This allows the encoding / decoding circuit to read and write in parallel to the memory while sampling the necessary pixel portion for the original pixel, so compared to reading and writing data from the memory without sampling. The number of access circuits to the memory is reduced, and the processing speed in the encoding / decoding device can be improved.

[Brief description of drawings]

FIG. 1 is a block diagram showing a coding / decoding device according to an embodiment of the present invention, FIG. 2 is a diagram showing a concept of a coding order and pixels thereof when ΔX = ΔY = 5, and FIG. Two
FIG. 4 is a diagram showing an image obtained by multiplying the image in the figure by 8/5 in the horizontal direction, FIG. 4 is a diagram showing the concept of the encoding order and its pixels in the case of ΔX = ΔY = 3, and FIG. 5 is the image of FIG. Figure 4 shows an image obtained by multiplying 4/3 in the horizontal direction, Figure 6 shows an image obtained by multiplying the image in Figure 4 by 4/3 in the horizontal and vertical directions, and Figure 7 shows ΔX = ΔY.
4 is a conceptual diagram of an encoding order in the sequential reproduction encoding method when = 4. 1 ... One screen memory, 2 ... Conversion circuit, 3 ... Reduction memory, 4 ... Encoding / decoding circuit.

Front page continuation (72) Inventor Toshiaki Endo 2-23 Nakameguro, Meguro-ku, Tokyo International Telegraph and Telephone Corporation (72) Inventor Hisaharu Kato 2-12-23 Nakameguro, Meguro-ku, Tokyo International (72) Inventor, Neiichi Nishino, 1006, Kadoma, Kadoma City, Osaka Prefecture, Matsushita Electric Industrial Co., Ltd. (72) Inventor, Hiroshi Kusao, 1006, Kadoma, Kadoma City, Osaka Prefecture (in Matsushita Electric Industrial Co., Ltd. 72) Inventor Akira Hirasawa 1006 Kadoma, Kadoma City, Osaka Prefecture Matsushita Electric Industrial Co., Ltd. (72) Inventor Hiroshi Miki 2-3-3 Shimomeguro, Meguro-ku, Tokyo Matsushita Electric Transmission Co., Ltd. (72) Inventor Asaba Shoji 2-3-8 Shimo-Meguro, Meguro-ku, Tokyo Matsushita Dentsu Co., Ltd.

Claims (2)

[Claims] 1. An encoding / decoding process is performed for pixels extracted from ΔP pixels in the main scanning direction and ΔY lines in the sub-scanning direction from pixels forming an image signal.
When ΔX is not an exponential power of 2, the image signal is moved in the main scanning direction.
2 ⁿ / ΔX (2 ⁿ > ΔX, n = integer) times, and 2 in the main scanning direction
An encoding / decoding device characterized by being configured to perform encoding / decoding processing on pixels extracted for every ⁿ pixels. 2. If ΔY is not an exponential power of 2, the image signal is 2 ^m / ΔY (2 ^m > ΔY, m = integer) even in the sub-scanning direction.
The encoding / decoding apparatus according to claim 1, wherein the encoding / decoding processing is performed on pixels extracted every 2 ^m lines in the sub-scanning direction.