JPH07264591A - Original image data scanning method - Google Patents

Abstract

(57) [Summary] (Modified) [Objective] To provide an original image data scanning method capable of improving the compression rate by utilizing the correlation of images at the time of Huffman coding in still image data compression. According to an original image data scan program 1a in a control unit 1, when a block of 8 × 8 pixels as a compression unit is read from an original image memory, the original image data is scanned horizontally from the upper left block to the right, When it reaches the right end, the next block line is an original image data scanning method in which horizontal scanning is performed leftward from the right end block, and rightward scanning and leftward scanning are alternately repeated, and according to the original image data scanning program 1b. In the original image data scanning method, a zigzag scan is performed alternately from the block at the upper left end of the original image in the diagonal direction of the original image data in the left-right direction around the diagonal line.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an original image data scanning method for reading and compressing image data in an image data compression / expansion processing apparatus for compressing / decompressing digital still image data, and more particularly to an image data scanning method. The present invention relates to an original image data scanning method capable of improving the data compression rate by utilizing the correlation.

[0002]

2. Description of the Related Art As a conventional image data compression / expansion processing device, a JPEG (Joint Photograhs) for performing encoding for compressing and transmitting image data and decoding for image expansion is provided.
There was a phic Expert Group) type image data compression / decompression processing device. A JPEG image data compression / expansion processing device will be described with reference to FIG. Figure 6 shows the JPE
It is a block diagram of a configuration of a G system image data compression / expansion processing device.

A JPEG image data compression / expansion processing apparatus includes a DCT-based encoder 10 and a DCT.
20 based decoder, a memory (a) 32 on the encoder 10 side, and a memory (b) 33 on the decoder 20 side.
A transmission path 34 for transmitting compressed data from the memory (a) 32 to the memory (b) 33, a quantization table 35 used for quantization, and an encoding table used for encoding / decoding. And 36.

Further, in the encoder 10, a DCT (Disc
rete cosine transform) DCT calculation means 1 for performing calculation
1, a quantizer 12 for performing quantization, and an entropy encoder 13 for performing entropy encoding are provided.

Further, in the decoder 20, an entropy decoder 23 for entropy decoding compressed data is provided.
, A quantizer 22 for inverse quantization, and an inverse DCT (IDC
T) IDCT calculation means 21 for performing calculation is provided.

The operation of the image data compression / expansion processing apparatus is as follows.
The DCT calculation means 11 in 0 performs DCT calculation, the quantizer 12 performs quantization using the quantization table 35, and the entropy encoder 13 uses the encoding table 36 to perform entropy coding (here, Huffman). (Encoding) is performed, and the parameters and code data are stored in the memory (a) 32. Then, the parameters and the code data are transmitted from the transmission side memory (a) 32 to the reception side memory (b) 33 via the transmission path 34 and stored in the memory (b) 33.

On the receiving side, the parameters and the coded data are taken into the decoder 20, and the entropy decoder 23
, Entropy decoding is performed using the encoding table 36, and the decoded data is inversely quantized by the quantizer 22 using the quantization table 35.
Inverse DCT (IDCT) operation is performed in order to reproduce an image (Interface "International standard encoding system for color still images" Toshiaki Endo December 1991 p1
60-p182).

Next, DCT conversion and Huffman coding in the image data compression / expansion processing apparatus having the above configuration will be described with reference to FIGS. 7 and 8. In the image data compression / expansion processing device of the JPEG system, the Huffman coding system is used as the entropy coding system. Figure 7 shows the DCT
FIG. 8 is an explanatory diagram of conversion, and FIG. 8 is an explanatory diagram of Huffman encoding.

The original image data read in block units of 8 × 8 pixels is the DC of the image data compression / expansion processing device.
In the T calculation means 11, DCT calculation is performed and converted into DCT conversion data. As shown in FIG. 7, the block of the original image data is converted into an 8 × 8 array of an average value (DC component) of 64 pixels and a difference (AC component) from the average value. In the block shown in FIG. 7, the DC component is 260.

Next, the entropy encoder 13 quantizes the DCT-converted data to obtain a plurality of D's.
Huffman coding is performed to replace the CT conversion data with a bit pattern of 2 to 16 bits. For the DC component,
From the previous (previous block) DC component value (A) to the current DC
A value obtained by subtracting the component value (B), that is, AB (difference DC
Value) is used to perform Huffman coding. In general, a still image has a characteristic that the average value with respect to an adjacent block does not change greatly, so that the difference DC value is close to zero. Also, the smaller the difference DC value, the better the compression efficiency.

Next, a conventional original image data scanning method when the original image data is taken into the image data compression / expansion processing apparatus having the above-mentioned configuration will be specifically described with reference to FIG. FIG. 9 is a block diagram showing the configuration of a conventional original image data scanning means. Conventional original image data scanning means,
The original image data is output to the image data compression / expansion processing device 4 in units of 8 × 8 pixel blocks, and the original image memory 3 temporarily stores the original image data and the data from the original image memory 3. Image input unit 2 that reads the image and the order in which the image data is read into the image input unit 2 (scan method)
And a control unit 1 for instructing.

The control unit 1 also includes an original image data scan program 1c which defines a method for scanning original image data.
The image input unit 2 is controlled by activating the original image data scan program 1c.

That is, the original image data read by a scanner or the like is temporarily stored in the original image memory 3, and the control unit 1 activates the image data scan program 1c to issue an instruction to the image input unit 2. The image input unit 2 obtains 8 × original image data from the original image memory 3 according to the address order defined by the image data scan program 1c.
Each block of 8 pixels is loaded into the image data compression / expansion processing device and the above compression processing is performed.

Here, the image data scanning program 1
An outline of the conventional original image data scanning method defined by c will be described with reference to FIG. FIG. 10 is an explanatory diagram showing a conventional original image data scanning method. As shown in FIG. 10, the conventional original image data scanning method reads data in blocks horizontally from the upper left block of the original image, and when all blocks in the first column have been read, The block in the second row was read from the left end, and in the same way, the blocks in the lower right row in the bottom row were sequentially read in the horizontal direction.

Next, the processing flow of the original image data scanning program 1c in the conventional original image data scanning method will be described with reference to FIGS. Figure 11
12 is an explanatory diagram showing a block configuration of original image data scanned by a conventional original image data scanning method, and FIG.
FIG. 12 is a flowchart showing a processing flow of an original image data scan program 1c for scanning the original image data of FIG. 11 using a conventional original image data scanning method. In FIGS. 11 and 12, it is assumed that the original image data is composed of m × n blocks Bi, j (1 ≦ i ≦ m, 1 ≦ j ≦ n), and the number of blocks m and n is set in advance. It is described as being done.

In the conventional original image data scanning method, first, the numbers m and n of blocks are read (100) and 1 is substituted for i (102). Next, 1 is substituted for j (110),
The block Bi, j is read (120), 1 is added to j (122), j and n are compared (124), and when j is n or less, the process returns to the process 120 and block reading is repeated. On the other hand, in the process 124, if j is larger than n, 1 is added to i (130). If i is m or less, the process returns to the process 110 and the reading of the next block line is repeated, and i is larger than m. Then, the scanning process of the original image data is finished.

[0017]

However, in the above-described conventional image data scanning method, as shown in FIG. 10, the rightmost block (e) of a certain column and the leftmost block (f) of the next column are separated from each other. Since they are not adjacent to each other, there is no correlation. From the DC value of block (e) to the DC value of block (f)
The difference DC value obtained by subtracting the value does not become a small value, and further, a phenomenon in which the correlation is lost each time scanning of one row is completed appears, so that there is a problem that the compression efficiency of image data is reduced.

The present invention has been made in view of the above circumstances, and by always reading adjacent blocks, it is possible to improve the compression efficiency of image data by utilizing the correlation of images. Data scanning method.

[0019]

According to a first aspect of the present invention for solving the problems of the above-mentioned conventional example, the original image data is scanned in block units from a storage unit storing the original image data, and An original image data scanning method for reading original image data is characterized in that blocks of the original image data in the storage unit are alternately scanned in a specific direction and a direction opposite to the specific direction.

According to a second aspect of the present invention for solving the problem of the conventional example, the original image data is read in block units by scanning the original image data from a storage unit in which the original image data is stored. The image data scanning method is characterized by scanning the blocks of the original image data in the storage unit in a diagonal direction and zigzag right and left around the diagonal line.

[0021]

According to the first aspect of the present invention, the original image data scanning method reads the original image data block by block by alternately scanning the blocks of the original image data in the storage section in the specific direction and the opposite direction. The adjacent blocks can be continuously read, and the difference in the original image data between the adjacent blocks is small, so that the compression efficiency at the time of encoding in the image compression process by the JPEG system can be improved.

According to the second aspect of the invention, the original image data is read block by block by scanning the blocks of the original image data in the storage unit in a diagonal direction and zigzag right and left around the diagonal line. Since the scanning method is used, adjacent blocks can be read continuously, and the difference in the original image data between adjacent blocks is small, so the compression efficiency during encoding in the image compression process by the JPEG method is improved. Can be made.

[0023]

DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of the present invention will be described with reference to the drawings. FIG. 1 is a configuration block diagram of an original image data scanning means for realizing an original image data scanning method according to an embodiment of the present invention. It should be noted that parts having the same configuration as in FIG.

The original image data scanning means of this embodiment is
As shown in FIG. 1, a control unit 1, an image input unit 2, and an original image memory (storage unit) 3 are provided as the same portion as the conventional configuration. The image data scan programs 1a and 1b are different from the conventional original image data scan program 1c shown in FIG. 9, and are programs for performing the scan processing shown in FIG. 2 or 3.

Since each part of the original image data scanning means of this embodiment is almost the same as the conventional original image data scanning means shown in FIG. 9, the original image data scanning program 1a, which is a characteristic part of this embodiment, The processing in 1b will be mainly described, and description of other parts will be omitted. The 8 × 8 pixel glock read from the image input unit 2 is taken into the image data compression / expansion processing device shown in FIG.

Before specifically describing the original image data scanning programs 1a and 1b of the present embodiment, an outline of the original image data scanning methods of the first and second embodiments will be described with reference to FIGS. explain. 2 is an explanatory diagram showing an original image data scanning method by the original image data scanning program 1a (original image data scanning method of the first embodiment), and FIG. 3 is an original image data by the original image data scanning program 1b. It is explanatory drawing which shows a scanning method (original image data scanning method of a 2nd Example).

First, in the original image data scanning methods of the first and second embodiments, as shown in FIGS. 2 and 3, all blocks of 8 × 8 pixels are continuously formed without intermittently adjoining adjacent blocks. It is something to read.

The image data obtained by the original image data scanning method of the first and second embodiments is compressed / expanded by the image data compression / expansion processing device shown in FIG. The decompressed image data also needs to be written in the image memory for displaying in block units in the same order as the scan order of the first and second embodiments. This makes it possible to obtain an image having the same structure as the image before compression.

As shown in FIG. 2, according to the original image data scanning method of the first embodiment, the image data in the original image memory 3 is set to 8 × 8 pixels as one block, and the image input means 2 horizontally moves in block units. Scan the original image data by scanning in one direction (rightward in the figure), and after reading the blocks in the horizontal direction, move the block vertically in the vertical direction (downward in the figure) to move horizontally. In the opposite direction (to the left in the figure)
Scan the original image data, and after reading the blocks in the horizontal direction, move one block in the vertical direction (downward in the figure) and scan in the horizontal direction (rightward in the figure). The original image data is read. The subsequent processing is a repetition of the above processing.

Specifically, referring to FIG. 11, B1,1, B of the block (Bi, j) of the original image data are
Scanning 1,2, B1,3, ..., B1, n, then B
Scan with 2, n, B2, n-1, ..., B2,1 and then B3,1
, B3,2, B3,3, ..., B3, n, and if the last block is an even number (m: even number), then Bm, n, Bm, n
n-1, ..., Bm, 1 are scanned.

According to the original image data scanning method of the first embodiment, for example, adjacent block (a) in FIG.
And the block (b) are continuously scanned so that the difference value of the DC component obtained by subtracting the DC component of the block (b) from the DC component of the block (a) is reduced to a small value during DC Huffman coding. Therefore, since the difference value of the DC component can be used for encoding, the amount of data to be compressed can be suppressed, and JPEG
There is an effect that the compression efficiency of the still image data of the method can be improved.

In the original image data scanning method of the first embodiment, the horizontal scanning is basically performed, and the horizontal scanning is alternately performed in the forward and reverse directions, but the vertical scanning is performed. Based on the above, the vertical scanning may be alternately performed in the forward direction and the reverse direction.

As shown in FIG. 3, according to the original image data scanning method of the second embodiment, the image data in the original image memory 3 is set as one block of 8 × 8 pixels, and the image input means 2 is arranged in block units. The original image data is read while performing a zigzag scan from the upper left of the center to the lower right of the figure in the diagonal direction to the left and right around the diagonal.

Specifically, with reference to FIG. 11, for the block (Bi, j) of the original image data, B1,1, B
1,2, B2,1, B3,1, B2,2, B1,3, B1,4, ...
Bm-1, n, Bm, n-1, and Bm, n are scanned in this order.

According to the original image data scanning method of the second embodiment, for example, adjacent block (c) in FIG.
And the block (d) are scanned so as to be continuously read, the difference value of the DC component obtained by subtracting the DC component of the block (d) from the DC component of the block (c) is reduced to a small value during DC Huffman coding. Therefore, since the difference value of the DC component can be used for encoding, the amount of data to be compressed can be suppressed, and JPEG
There is an effect that the compression efficiency of the still image data of the method can be improved.

Next, the processing contents of the original image data scanning program for realizing the original image data scanning methods of the first and second embodiments will be described. First, the processing flow of the original image data scanning program 1a in the original image data scanning method of the first embodiment will be described with reference to FIGS.
Will be explained. FIG. 4 is a flow chart showing the processing flow of the original image data scanning program 1a for scanning the original image data of FIG. 11 using the original image data scanning method of the first embodiment. Note that, in FIG. 4, the number of blocks m and n is described as being preset in the same manner as in the conventional case.

In the original image data scanning method of the first embodiment, as shown in FIG. 4, first, the numbers of blocks m and n are read (200) and 1 is substituted for i (202). next,
As a process of scanning to the right, 1 is substituted for j (2
10), read the block Bi, j (220), 1 for j
Is added (222), and it is determined whether j is larger than n (224). If j is not larger than n, the process returns to step 220 to repeat the scan to the right. If j is larger than n, i 1 is added to (230).

Then, it is determined whether or not i is larger than m (232). If i is larger than m, the scanning process of the original image data is terminated, and if i is m or less, the process of scanning to the left is performed. Substituting n for j (240),
The block Bi, j is read (250) and 1 is subtracted from j (252). Next, it is determined whether j is smaller than 1 (254). If j is 1 or more, the process returns to step 250 and the leftward scanning is repeated. When j becomes smaller than 1, 1 is added to i (260). ). Then, it is determined whether i is larger than m (262). If i is smaller than m, the process returns to step 210 to scan the next block line to the right, and if i is larger than m, the original image data The scanning process ends.

Next, the processing flow of the original image data scanning program 1b in the original image data scanning method of the second embodiment will be described with reference to FIGS.
FIG. 5 is a flow chart showing the processing flow of the original image data scanning program 1b for scanning the original image data of FIG. 11 using the original image data scanning method of the second embodiment. Note that, in FIG. 5, the block numbers m and n are described as being preset in the same manner as in the conventional case.

In the original image data scanning method of the second embodiment, first, the block numbers m and n are read (300),
1 is substituted for i, j (302), and the block Bi, j is read (304). Next, as a process of scanning one block to the right, j is incremented by 1 (310) and j is compared with n (312). If j is n or less, block Bi,
Read j (314).

Next, it is judged whether the value of i is 1 (31
6) When i is 1, as a process of scanning in the lower left direction, 1 is added to i and 1 is subtracted from j (320).
And m are compared (322), and when i is m or less, j and 1 are further compared (324). When j is 1 or more, the block Bi, j is read (326), and the process 320 is performed. Return and repeat the scan in the lower left direction.

In the process 322, if i is larger than m, the scan position has reached the lower end of the original image data. Therefore, 1 is subtracted from i and 1 is added to j (328) to scan. The position is returned, the process jumps to step 310, and the process moves to the block to scan one block to the right.

When j is smaller than 1 in the process 324, the scan position has reached the left end of the original image data. Therefore, 1 is subtracted from i and 1 is added to j (329). The scan position is returned, the process jumps to step 340, and the process proceeds to scan one block downward.

When i is not 1 in the process 316, 1 is subtracted from i, 1 is added to j as a process of scanning in the upper right direction (330), and i and 1 are compared (332). , I is 1 or more, j and n are further compared (334), and when j is n or less, the block Bi, j is read (336), the process returns to the process 330 and the scanning to the upper right direction is repeated.

In the process 332, if i is smaller than 1, it means that the scan position has reached the upper end of the original image data. Therefore, 1 is added to i and 1 is subtracted from j (338) to scan. The position is returned, the process jumps to step 310, and the process moves to the block to scan one block to the right.

When j is larger than n in the processing 334, the scan position has reached the right end of the original image data. Therefore, 1 is added to i and 1 is subtracted from j (339) scan. The position is returned, and the process jumps to step 340 to move downward one block.

Then, in the process 312, when j is larger than n, it means that the scan position has reached the right end of the original image data. Therefore, 1 is subtracted from j (313) to return the scan position, and then, As a process of scanning one block in the downward direction, 1 is added to i (340), i and m are compared (342), and if i is larger than m, the scan process of the original image data ends.

On the other hand, in process 342, if i is less than or equal to m, block Bi, j is read (344), and j is 1
In the case of, the process jumps to the process 330 and the process moves to the upper right direction, and if j is not 1, the process jumps to the process 320 to move the process to the lower left direction.

According to the original image data scanning method of this embodiment, adjacent blocks having a correlation are continuously read by the scanning method shown in FIGS. 2 and 3 and compression processing is performed by the JPEG method. , DC in the compression process
Since the difference value of the DC component can be made small at the time of Huffman coding, there is an effect that the compression efficiency can be improved.

[0050]

According to the first aspect of the present invention, there is provided an original image data scanning method in which a block of original image data in a storage section is alternately scanned in a specific direction and in the opposite direction to read the original image data in block units. Since adjacent blocks can be continuously read, and the difference in the original image data between adjacent blocks is small, the compression efficiency at the time of encoding in the image compression process by the JPEG method can be improved. There is an effect that can be done.

According to the second aspect of the invention, the original image data is read in block units by scanning the blocks of the original image data in the storage section in a diagonal direction and zigzag right and left around the diagonal line. Since the scanning method is used, adjacent blocks can be read continuously, and the difference in the original image data between adjacent blocks is small, so the compression efficiency during encoding in the image compression process by the JPEG method is improved. There is an effect that can be made.

[Brief description of drawings]

FIG. 1 is a configuration block diagram of an original image data scanning unit according to an embodiment of the present invention.

FIG. 2 is an explanatory diagram showing an original image data scanning method according to the first embodiment.

FIG. 3 is an explanatory diagram showing an original image data scanning method according to a second embodiment.

FIG. 4 is a flowchart showing a processing flow of an original image data scanning program 1a for scanning the original image data of FIG. 11 using the original image data scanning method of the first embodiment.

FIG. 5 is a flow chart diagram showing a processing flow of an original image data scan program 1b for scanning the original image data of FIG. 11 using the original image data scanning method of the second embodiment.

FIG. 6 is a configuration block diagram of a JPEG image data compression / expansion processing device.

FIG. 7 is an explanatory diagram of DCT conversion.

FIG. 8 is an explanatory diagram of Huffman coding.

FIG. 9 is a configuration block diagram of a conventional original image data scanning means.

FIG. 10 is an explanatory diagram showing a conventional original image data scanning method.

FIG. 11 is an explanatory diagram showing a block configuration of original image data scanned by a conventional original image data scanning method.

FIG. 12 is a flowchart showing a processing flow of an original image data scanning program 1c for scanning the original image data of FIG. 11 using a conventional original image data scanning method.

[Explanation of symbols]

1 ... Control unit, 1a, 1b, 1c ... Original image data scan program 2 ... Image input unit, 3 ... Original image memory,
4 ... Image data compression / expansion processing device, 10 ... Encoder, 11 ... DCT calculation means, 12 ... Quantizer, 1
3 ... Entropy encoder, 20 ... Decoder, 21
Inverse DCT calculation means, 22 ... Quantizer, 23 ... Entropy decoder, 32 ... Memory (a), 33 ... Memory (b), 34 ... Transmission path, 35 ... Quantization table, 36 ... Encoding table

─────────────────────────────────────────────────── ─── Continuation of the front page (51) Int.Cl. ⁶ Identification code Office reference number FI technical display location // H03M 7/30 A 8842-5J 7/40 8842-5J

Claims (2)

[Claims] 1. An original image data scanning method for reading the original image data by scanning the original image data in block units from a storage unit storing the original image data, and specifying a block of the original image data in the storage unit. An original image data scanning method, characterized in that scanning is performed alternately in a direction and in a direction opposite to the specific direction. 2. An original image data scanning method for scanning the original image data by scanning the original image data from a storage unit in which the original image data is stored and reading the original image data, wherein a block of the original image data in the storage unit is a diagonal line. A method for scanning original image data, comprising scanning in a zigzag direction from side to side around the diagonal line in a direction.