JPH0586697B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Technical Field of the Invention] The present invention relates to a multi-gradation image signal encoding device that can efficiently transmit or store multi-gradation image signals.

[Technical background of the invention and its problems]

Conventionally, in facsimile machines, image signals obtained by scanning a document are converted into black and white binary signals, and then encoded based on various encoding methods to reduce the amount of information to be transmitted and transmit it efficiently. method is implemented. The encoding method is MH, which is recommended by the CCITT (Consultative Committee for International Telegraph and Telephone).
(ModifiedHuffman) encoding method and MR
(Modified Read) encoding method is well known.

These encoding systems were developed to compress the signal band while keeping the amount of information equivalent by focusing on the probability distribution characteristics of the signal obtained by digitizing a black and white binary original.

In recent years, however, there has been a demand for processing documents and color images containing multiple gradations, such as photographs. However, if the MH encoding method or MR encoding method developed for binary signal encoding is applied to multi-gradation images, a problem arises in that sufficient signal compression efficiency cannot be obtained.

On the other hand, in display devices or recording devices that can only reproduce black and white binary levels, the dither method and the density pattern method are known as methods for reproducing halftones in a pseudo manner. The density pattern method uses 1 N x N dots.
In the dither method, each dot on the display device is treated as one pixel in the halftone image, and each dot corresponds to one pixel in the halftone image. It is.

In the dither method, a multi-gradation image signal obtained by scanning an original image is compared with a predetermined threshold value corresponding to each pixel position, and white or black is determined depending on the magnitude of the signal. That is, if the density level of each pixel obtained by scanning is Xij (however, it indicates the ij pixel position), and the predetermined threshold is Cij, then if the density level Xij is larger than the threshold Cij, the density level at that position is 1 is substituted for the output pixel Yij, and 0 is substituted and displayed if it is equal or smaller.

In this way, the image signal binarized by the dither method is usually represented by a signal sequence of 1 or 0, but since the length of consecutive 1 or 0 is short,
Conventional MH encoding systems and MR encoding systems have a problem in that the overall transmission code length cannot be sufficiently compressed and an efficient code structure cannot be obtained.

[Purpose] This invention was made in order to solve the above-mentioned problems, and aims to reduce transmission time by efficiently transmitting multi-gradation image signals, and to significantly reduce the amount of memory in an image file device. An object of the present invention is to provide a multi-gradation image signal encoding device that can encode a multi-gradation image signal.

[Summary of the invention]

The present invention is an apparatus for encoding a multi-gradation image signal, which compares the multi-gradation image signal with a standard pattern having a predetermined image signal distribution for a plurality of pixels, and detects coincidence or mismatch of the image signals. By transmitting information about the multi-gradation image signal determined to be inconsistent, the information of the multi-gradation image signal can be compressed.

〔Effect of the invention〕

According to the present invention, the information of the multi-gradation image signal consisting of a huge amount of information can be compressed to a large extent by encoding appropriately according to the multi-gradation image signal determined to be a mismatch, so that the information can be efficiently and This enables high-speed transmission to remote locations, allowing effective use of transmission equipment. Furthermore, since the amount of memory for the image file device can be greatly reduced, the device can be made smaller and more economical than conventional devices.

[Embodiments of the invention]

Hereinafter, one embodiment of the present invention will be described with reference to the drawings.

FIG. 1 shows a schematic configuration of an encoding device that realizes the halftone image encoding method according to the present invention by microcomputer control.
only memory) 2, RAM (Random access)
memory) 3, D/A converter (Digital to
4, a line memory 5, a line memory control section 6, a dither pattern ROM 7, a standard pattern ROM 8, and a P/S (parallel-serial) converter 9.

The CPU 1 controls the entire device and executes encoding processing by referring to the contents of the ROM 2, and here a CPU 1 having an 8-bit data bus is used. The ROM 2 stores control software for encoding processing. The RAM 3 is used to temporarily store data required during the encoding process by the CPU 1. The D/A converter 4 inputs a multi-gradation image signal obtained by scanning each pixel constituting an N-dot pixel matrix using an external scanner in synchronization with an image signal clock supplied from the outside.
The density information of each pixel is quantized as a 4-bit (16-level) image signal. The line memory 5 is composed of four line memories 5a to 5d, and is controlled by a line control section 6 to be described later.
It writes the image signal digitized by the A converter 4, for example, the number of pixels per line is 2048.
In terms of pixels, it has a capacity of 2048 pixels x 4 bits x 4 lines. The line memory control unit 6 performs control to write the image signal digitized by the D/A converter 4 into the line memories 5a to 5d in synchronization with the image signal clock according to a write instruction from the CPU 1, and when the writing is completed. at the time
It has a function to notify the CPU 1 of the end of input by using, for example, an interrupt function. dither pattern
ROM7 is 1 pixel 4 input from line memory 5
A table that stores threshold levels for binarizing bit image signals, as shown in Figure 2.
16 types of threshold values from 1 to 16 are stored in the x4 block. Here, the density level Xij of the image signal read out by CPU1 and the dither pattern ROM
By sequentially comparing the pixel positions corresponding to the 7 threshold values Cij, a binary signal string can be obtained from the multi-tone image signal. The standard pattern ROM 8 stores a pattern of a binary signal sequence obtained when the density level of each pixel in a 4×4 block is almost uniform, and has density levels 0 to 16 as shown in FIG.
17 standard binary signal patterns are stored. Here, the CPU 1 compares the standard pattern Pij and the binary signal sequence Yij obtained by dithering with respect to the average density level of each block, and detects and counts mismatched bit positions. P/S (parallel)
The serial) converter 9 outputs the code encoded by the CPU 1 to the outside, and converts the code output from the CPU 1 in 8-bit units into a serial signal in synchronization with the output clock.

The operation of this device will be explained below.

4a, b, and c are flowcharts of the encoding processing control software stored in the ROM 2. FIG. First, as shown in the flowchart of FIG. 4a, when a write instruction is issued from the CPU 1 to the line memory controller 6, a multi-gradation image signal from an external scanner is digitized by the D/A converter After that, the data is written into the line memories 5a to 5d under the control of the line memory control section 6. line memory 5
When the writing of a to 5d is completed, the encoding process is started by a writing end interrupt from the line memory control unit 6. Here, the CPU 1 first inputs four image signals from the beginning of each line memory 5a to 5d. As a result, 4× corresponding to a specific positional relationship
The density of each pixel in the 4-dot pixel matrix is
For example, input is made as shown in FIG. 5a. next,
CPU1 is the density level Xij of each pixel in each block.
The average density level is calculated by calculating the sum of 16 pixels and dividing it by the number of pixels, 16. In the case of the first block, the density level of all pixels is 0 (white), so the average density level is 0, in the case of the second block, the average density level is 6, and in the case of the third block, the average density level is 0. The concentration level will be 12. This average density level is temporarily stored in RAM3.

Next, the CPU 1 compares the density level Xij of each pixel of the block 1 with the threshold value of the dither pattern ROM 7, and binarizes the multi-gradation image signal. From now on, this 1
Binarizing the multi-gradation image signal of a block is called dithering. This dithering will be explained using the flowchart of FIG. 4b. In the figure, the reference pixel address (i, j) within one block is (O,
Dithering is performed sequentially from 0). Dithering is performed using the density level Xij of each pixel of one input block.
Compare the magnitude of threshold value Cij of dither pattern ROM 7 with
In this case, the binary signal Yij is set to 1, and the pixel address ij is incremented, and when it reaches ij (4, 4), the dithering is completed.

Next, the predetermined standard pattern Pij for each average density level shown in FIG. 5b is compared with the dithered binary signal sequence Yij shown in FIG. 5c, and mismatched bit positions are detected and counted. Do the following. Then, after separating the data into a plurality of states according to the number of mismatched bits, it is encoded as appropriate according to each state.

Next, comparison and encoding of the standard pattern Pij and the binary signal sequence Yij will be explained using the flowchart of FIG. 4c. First, standard patterns Pij and 2
The value signal sequences Yij are compared and separated into a first state in which all pixels match and a second state in which there are mismatched pixels. As a result, the average density level is encoded for the first state, and the average density level and the position of the mismatched pixel are encoded for the second state. This is the first method, and its operation will be explained in detail below.

In FIG. 4c, the reference pixel addresses (i, j) within one block are sequentially compared from (O, 0) with the count value n of the mismatch pixel counter set to 0. and a third block corresponding to the average density level of each block.
2 obtained by dithering with the standard pattern Pij shown in the figure
Take out the value signal sequence Yij from RAM3 in order, and set Pij≠
At the time of Yij, the mismatched pixel counter n is incremented by 1, and the pixel addresses i and j at that time are stored in the RAM 3.

In the case of the first block, as shown in Fig. 5b and c, the standard pattern Pij and the binary signal sequence Yij are all 0, and as a result of comparison, all pixels match, so the coefficient value of the mismatched pixel number counter is 0. becomes. In the case of the second block, as a result of comparing the standard pattern Pij shown in FIG. 5b with the binary signal sequence Yij obtained by dithering the second block shown in FIG. Since the indicated pixel position 7 does not match, the count value of the mismatched pixel number counter becomes 1. In the case of the third block, the standard pattern Pij shown in Fig. 5b and the standard pattern Pij shown in Fig. 5c
As a result of comparing the binary signal sequence Yij obtained by dithering the third block shown in Fig. 1, pixel positions 6 and 14 indicated by circles in Fig. It becomes 2.

Here, the CPU 1 encodes the first block, second block, and third block in this order. FIGS. 6a and 6b show a list of symbols used in this embodiment. Figure a shows the result of comparing the binary signal sequence Yij and the standard pattern Pij, and the mode codes M ₀ and M 1 are used to distinguish between the first state in which all pixels match and the second state in which they do not match _completely . show. Figure b
are density level codes _L0 to _L15 indicating the average density level within the block, pixel number codes N0 _{to N15} indicating the number of mismatched pixels within the block, and pixel position code _A0 specifying the position of the mismatched pixel. ~ _A15 is shown.

First, the CPU 1 refers to the count value n of the mismatch pixel coefficient counter obtained by comparing the binary signal sequence Yij obtained by dithering with the standard pattern Pij of that block, and calculates the case where the count value n=0. When n > 0, the encoding flow is divided into two. As a result, the count value of the mismatched pixel counter is n =
In the case of 0, the mode code M ₀ (01) for all pixels matching
and the average density level code L of that block is encoded. For example, in the case of the first block, the first block in FIG.
As shown in the block code string, the mode M ₀ (01) and the average density level K code L ₀ (0000) are output from the CPU 1 to the P/S converter 9. In addition, when there is one mismatched pixel as in the second block, the mode code M ₁ (10) and the average density level code L ₆ (0110) are used as shown in the code string of the second block in FIG. Continuing, the count value n of the mismatched pixel counter at this time =
The pixel number code N ₀ (0000), which represents 1, and the pixel position code A ₇ (0111), which specifies the position of the mismatched pixel, are
1 to the P/S converter 9. Similarly, when there are two mismatched pixels as in the third block, the mode code M ₁ (10) and the average density level code L ₁₂ are set as shown in the code string of the third block in FIG.
(1100), a pixel number code N ₁ (0001) representing the count value 2 of the mismatched pixel counter at this time, and 2
Pixel position code that identifies the position of a mismatched pixel
A ₆ (01110) and A ₁₄ (1110) are output from the CPU 1 to the P/S converter 9.

In the same way, each block is encoded repeatedly.
For example, if one line has 2048 pixels, it will be divided into 512 blocks, so the same process is repeated for 512 blocks, and this encoding process is repeated in the sub-scanning direction from the top to the bottom of the document in units of 4 lines. By doing so, it is possible to encode one page of the manuscript.

By the way, since multi-gradation image signals such as photographs generally have many parts where the change in density level is relatively gradual, the binary image signal sequence obtained by dithering is
60% of the blocks match the standard pattern of the design, and most of the blocks that do not match the standard pattern have a high probability of mismatching one pixel or several pixels, so conventional MH encoding method, MR encoding method, etc. The encoding efficiency can be significantly improved compared to the above. Moreover, in facsimile devices and the like, transmission efficiency is improved, and in file devices and the like, the size of the device can be reduced by reducing the amount of memory.

Two different embodiments will be described below regarding the comparison and encoding of the standard pattern Pij and the binary signal sequence Yij.

FIG. 8 is a flowchart of control software stored in the ROM 2 that performs encoding processing using the second method. Referring to this flowchart, compare the standard pattern Pij and the binary signal sequence Yij to find a first state in which all pixels match, a second state in which they differ by one pixel, and a third state in which they differ by two or more pixels. so that for the first state the average density level is encoded, for the second state the average density level and the position of the mismatched pixel is encoded, and for the third state 2 The operation of encoding the value signal sequence Yij will be explained. Incidentally, since the process up to the dithering process for binarizing one block of multi-gradation image signals is the same as in the above-described embodiment, the operations up to this point will be omitted here.

In FIG. 8, the reference pixel addresses (i, j) within one block are sequentially compared from (0, 0) with the count value n of the mismatch pixel counter set to 0. and a third block corresponding to the average density level of each block.
2 obtained by dithering with the standard pattern Pij shown in the figure
Take out the value signal sequence Yij from RAM3 in order, and set Pij≠
The mismatched pixel counter n at the time of Yij is incremented by 1, and the pixel addresses i and j at that time are stored in the RAM 3.

In the case of the first block, as can be seen from Figures 5b and 5c, the binary signal sequence Yij and the standard pattern Pij are all 0, and as a result of the comparison, the count value of the mismatched pixel counter becomes 0, indicating the first state. show. In the case of the second block, the standard pattern Pij shown in Figure 5b and the standard pattern Pij shown in Figure 5c
As a result of comparing the binary signal sequence Yij obtained by dithering the second block shown in Figure 2, the pixel position 7 marked with a circle in Figure c is a mismatch, so the count value of the mismatch pixel counter becomes 1. A second state is shown. In the case of the third block, as a result of comparing the standard pattern Pij shown in FIG. 5b with the binary signal sequence Yij obtained by dithering the third block shown in FIG. Since pixel positions 6 and 14 shown by do not match, the count value of the mismatch pixel counter becomes 2, indicating the third state.

Here, the CPU 1 encodes the first block, second block, and third block in this order. FIGS. 9a and 9b show code reference tables used in this embodiment. Figure a shows the results of comparing the binary signal sequence Yij and the standard pattern Pij: a first state in which all pixels match, a second state in which only one pixel differs, and two states.
Mode codes M ₀ , M ₁ , and M ₂ are shown for identifying a third state that differs by more than a pixel. Figure b shows the density level code L ₀ ~ indicating the average density level within the block.
L ₁₅ and pixel position codes A ₀ to _{A 15} specifying the positions of mismatched pixels within the block.

First, the CPU 1 refers to the count value n of the mismatch pixel count counter obtained by comparing the binary signal sequence Yij obtained by dithering with the standard pattern Pij of that block, and if the count value n=0, If n=1,
In the case of n>1, the encoding flow is divided into three.

As a result, the count value n of the mismatched pixel number counter is
0 (first state), the mode code M ₀ (01) and the average density level code L ₀ (0000) are transmitted from the CPU 1 to P/P as shown in the code string of the first block in FIG.
It is output to the S converter 9. In addition, when the count value n of the mismatched pixel number counter is 1 as in the second block (second state), the mode code M ₁ (10) as shown in the code string of the second block in FIG. , a density level code L ₆ (0110) indicating the average density level of the second block, and a pixel position code A ₇ (0111) specifying the position of the mismatched pixel at this time are sent from the CPU 1 to the P/S converter 9. Output. Furthermore, as in the third block, the count value n> of the mismatch pixel number counter
1 (third state), the mode code M ₂ (11) as shown in the code string of the third block in FIG.
and the 16-pixel binary signal sequence that makes up the third block.
Yij is output from the CPU 1 to the P/S converter 9.

Therefore, in this second method, the standard pattern
By comparing and encoding Pij and the binary signal sequence Yij, the conventional
Compared to the MH encoding method, MR encoding method, etc., encoding efficiency can be significantly improved. Furthermore, facsimile devices and the like are superior in transmission efficiency, and file devices can be downsized by reducing the amount of memory.

On the other hand, FIG. 11 is a flowchart of control software stored in the ROM 2 and performing encoding processing by the third method. Referring to this flowchart, the standard pattern Pij and the binary signal sequence Yij are compared to determine a first state in which all pixels match, and a second state in which the number of mismatched pixels is in a relationship of 1≦n<3. , into a third state in which the number of mismatched pixels is n≧3, and as a result, the average density level is encoded for the first state, and the average density level and block are encoded for the second state. The number of mismatched pixels and the position of mismatched pixels in the state are encoded, and for the third state 2
The operation of encoding the value signal sequence Yij will be explained. Note that the dither processing for binarizing one block of multi-gradation image signals is the same as described above, so the operations up to this point will be omitted here.

In FIG. 11, the reference pixel addresses (i, j) within one block are sequentially compared from (0, 0) with the count value n of the mismatch pixel counter being set to 0. and a third block corresponding to the average density level of each block.
2 obtained by dithering with the standard pattern Pij shown in the figure
Take out the value signal sequence Yij from RAM3 in order, and set Pij≠
The mismatched pixel counter n at the time of Yij is incremented by 1, and the pixel address ij at that time is stored in the RAM3. At this time, as shown in FIG. 12a, the average density level of the first block is 0, the average density level of the second block is 13, and the average density level of the third block is 7, and the binary image signal sequence of each block is Yij is the 12th
Assume that the shape is as shown in Figure c.

In the case of the first block, as can be seen from FIGS. 12b and 12c, Pij and Yij are all 0, and as a result of the comparison, all pixels match, so the count value of the mismatched pixel number counter becomes 0. In the case of the second block, the standard pattern Pij shown in Fig. 12b and the second pattern shown in Fig. 12c are used.
As a result of comparing the binary signal sequence Yij obtained by dithering the block, the pixel position 4 indicated by the circle in c in the same figure.
and 14 do not match, so the count value of the mismatch pixel number counter becomes n=2. In the case of the third block, a binary signal sequence obtained by dithering the standard pattern Pij shown in Fig. 12b and the third block shown in Fig. 12c is used.
As a result of comparing Yij, pixel positions 1, 2, 4, 7, 9, 10, 13, and 15 indicated by circles in c in the same figure are inconsistent, so the count value of the inconsistent pixel number counter is n = 8. becomes.

Next, CPU1 executes the first block, second block,
Encoding is performed in the order of the third block. FIGS. 13a and 13b show a list of symbols used in this embodiment. Figure a shows the results of comparing the binary signal sequence Yij and the standard pattern Pij: a first state in which all pixels match, a second state in which the number of mismatched pixels is in a relationship of 1≦n<3, and a state in which there are no mismatched pixels. Mode code for identifying the third state in which the number is n≧3
M ₀ , M ₁ , M ₂ are shown. Figure b shows density level codes L ₀ to L ₁₅ indicating the average density level within the block;
Pixel number code N ₀ indicating the number of mismatched pixels in the block
~ _N15 , pixel position codes _N0 to _N15 that specify the position of the mismatched pixel, and pixel position codes _A0 to _A15 that specify the position of the mismatched pixel.

First, the CPU 1 refers to the count n of the mismatch pixel count counter obtained by comparing the dithered binary signal Yij and the standard pattern Pij of the block, and determines whether the count value n=0 or n <3 and
In the case of n≧3, the encoding flow is divided into three.
As a result, the count value of the mismatched pixel number counter is n=
In the case of 0, the mode code M ₀ of all pixels matching,
The average density level code L of the block is encoded. For example, in the case of the first block, the average density level code L of the block is encoded.
As shown in the code string of the block, the mode code M ₀
(01) and average density level code L ₀ (0000) are CPU1
is output to the P/S converter 9. Also, if there are two mismatched pixels like in the second block,
As shown in the code string of the second block in FIG. 14, the mode code M ₁ (10) and the average density level code L ₁₃
(1101), followed by a pixel number code N ₁ (0001) representing the count value n = 2 of the mismatched pixel counter at this time.
Then, a pixel position code (0100) and A ₁₄ (1110) specifying this mismatched pixel position are output from the CPU 1 to the P/S converter 9. Furthermore, when there are three or more mismatched pixels as in the third block, the mode code is changed as shown in the code string of the third block in FIG.
M ₂ (11) and 2 of the 16 pixels that make up the third block
A value signal sequence Yij is output from the CPU 1 to the P/S converter 9.

Therefore, in this third method, the standard pattern
By comparing and encoding Pij and the binary signal sequence Yij, it switches between encoding the pixel position and encoding the dithered binary signal sequence Yij according to the number of mismatched pixels in the block. be able to. As a result, especially if the original contains characters with relatively large changes in density level,
Since the number of blocks in which more than half of the pixels are unmatched increases, encoding efficiency can be greatly improved compared to conventional MH encoding methods, MR encoding methods, etc. Furthermore, facsimile devices are superior in transmission efficiency, and file devices can be downsized by reducing the amount of memory.

Note that the present invention is not limited to the above-mentioned embodiments, and can be implemented with various modifications without changing the gist.

For example, in the above embodiment, a case was described in which a multi-gradation image signal is quantized with 4 bits per pixel and divided into 4×4 blocks, but this invention is particular about the number of quantization bits and the number of pixels in a block. It's not a thing.

In addition, in the above embodiment, the result of comparing the binary signal string obtained by dithering with the standard pattern is separated into two states and three states, but it is further separated into a large number of states and coded appropriately according to each state. It can also be converted into

Further, the arrangement of threshold values and the assignment of codes when dithering are not limited to the above embodiments. For example, in the third method described above, the number of mismatched pixels n is in the relationship n≧m. In the state, the binary signal sequence can also be combined with other encoding methods such as MH encoding method or MR encoding method.

Furthermore, although the above embodiment describes the case of a black and white multi-gradation image, the present invention is not limited to this. can be applied.

[Brief explanation of the drawing]

FIG. 1 is a block diagram showing an embodiment of the present invention, FIG. 2 is an explanatory diagram showing a threshold table for binarizing an image signal used in the embodiment, and FIG. An explanatory diagram showing the standard binary signal pattern of the density level; FIGS. 4a, b, and c are flowcharts showing the operating order of the same embodiment; FIGS.
b, c are explanatory diagrams showing multi-gradation image signals, standard patterns, and dithered binary signal sequences obtained by the same example, and Fig. 6 a, b are explanatory diagrams showing the symbols used in the same example. 7 is an explanatory diagram showing the encoding obtained by the same embodiment, and FIG. 8 or 11 is a comparison and encoding of a standard pattern and a binary signal string, respectively, showing another embodiment of the present invention. Flowchart for explaining the operating sequence of FIGS. 9a and 9b
13a and 13b are explanatory diagrams showing the codes used in these embodiments; FIG. 10 or 14 are explanatory diagrams showing the encoding obtained by these embodiments; and FIG. 12a, b and c are explanatory diagrams showing a multi-gradation image signal, a standard pattern, and a dithered binary signal sequence obtained by the embodiment of FIG. 11; 1...Microcomputer, 2...ROM,
3...RAM, 4...D/A converter, 5, 5a~
5d...Line memory, 6...Line memory control unit, 7...Dither pattern ROM, 8...Standard pattern ROM, 9...P/S converter.

Claims (1)

[Scope of Claims] 1. Means for calculating an average density for a multi-gradation image signal in block units, and comparing the multi-gradation image signals in block units with a predetermined threshold value for each pixel position. means for converting into a binary signal group; means for storing a standard pattern in block units having a binary signal distribution according to the density; reading out the standard pattern corresponding to the average density from the means; It is characterized by comprising means for detecting a match or mismatch by comparing a group of binary signals, and an encoding means for using information on the match or mismatch detected by this means as a code for the block. Multi-gradation image signal encoding device. 2. The encoding means uses the average density when a match is detected, and uses the average density, the number of mismatched pixels, and the mismatched pixel position when a mismatch is detected, to code the block. A multi-gradation image signal encoding device according to claim 1. 3. The encoding means uses the average density and the mismatched pixel position when a mismatch of one pixel is detected, and uses the binary signal group of the block when a mismatch of two or more pixels is detected. A multi-gradation image signal encoding apparatus according to claim 2. 4. The encoding means uses the average density, the number of mismatched pixels, and the mismatched pixel position when a mismatch of one or two pixels is detected, and uses the binary signal of the block when a mismatch of three or more pixels is detected. 3. The multi-gradation image signal encoding device according to claim 2, wherein a group is used to generate a code.