JPH0740294B2 - Pattern reduction method - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Outline] The present invention relates to an improvement of a pattern reduction method, and an object thereof is to provide a pattern reduction method capable of increasing the fidelity to an original pattern as much as possible and reducing the processing time. , Which is image data on a line adjacent on the display, and is read out from the image memory in word units or byte units.
For the image data of a row, by dividing the dots of each row into small areas of n bits each, a plurality of matrices consisting of small areas of n columns × n dots are formed, and each matrix has the same position on each row. A representative dot row is generated by taking a majority vote with a certain number of n dots, and further, n rows of shift dot rows are generated by shifting the representative dot row by 0 to n-1 dots by the shift means, respectively. Dots that belong to the same matrix, and
In the shift dot row of the row, a majority decision is made with n dots at the same position, and the representative dot in the matrix is decided.

[Industrial application field]

The present invention relates to a pattern reduction method for reducing a figure or the like displayed on a display, for example.

For example, when the figure displayed on the display is to be output by a printer or inserted in a sentence, it is sometimes desired to reduce the size of the figure.

For this reason, various pattern reduction methods have been conventionally proposed.

[Prior art and its problems]

Conventionally, in order to reduce a pattern in which a set of dots is arranged two-dimensionally or three-dimensionally, sampling by thinning or dot counting has been performed. That is, for example, when reducing to 1/3, 3 × 3 dots are represented by one dot, and when thinning out, fixed rows and columns, for example, dots in the first row and the first column Is extracted as a representative of the nine, so high-speed processing is possible, but the fidelity cannot be expected so much because the information of the eight dots that are not extracted is not reflected. On the other hand, in the case of dot counting, the dot having the maximum number in terms of color, density, etc. is extracted as one dot representing 9 dots. For example, if the dot takes a binary value of white or black. It can be said that the fidelity is relatively good because the black and white of the representative dot can be determined depending on whether there are five or more blacks or less.

However, since 9 dots are arranged two-dimensionally, when pattern information is stored in the memory device which is read out by assigning addresses in word or byte units, the address set and the address Since it is necessary to calculate the bit position in, there is a problem that the processing time is remarkably increased as compared with the above-described decimation.

Therefore, it is an object of the present invention to provide a pattern reduction method capable of improving fidelity and processing speed as compared with the above two cases. Especially, a pattern reduction method which is convenient to be applied to an information processing apparatus having a memory device in which an ordinary word or byte address is assigned without using a special memory device for assigning an address in bit units. The purpose is to provide.

[Means and Actions for Solving Problems]

According to the present invention, the image data on the adjacent line on the display screen, and n read in byte units or word units
For the image data of a row, a representative dot is determined by n dots at the same position in each row, and the majority of these representative dots is determined to determine the overall representative dot, thereby reducing the fidelity. I try to be better than that. Further, since the determination process of the column representative dots is the same (uniform) operation for each column, since parallel processing is naturally performed by AND, OR, EXOR operation instructions in word or byte units, it is more than in the case of every dot. Is processed at high speed.

FIG. 1 shows the principle of the present invention by taking as an example a system in which 1/3 reduction is assigned in 16-bit units (word units) and a binary pattern of white (0) and black (1) is stored in the memory. It is for explanation.

In this example, 5 sets of 1-bit information are calculated from 9 bits surrounded by a dotted line.
(1) to (3) are the original pattern information for 3 words,
(4 is 1-word pattern information obtained by performing a majority operation on 3 bits in each column for these words. The majority operation for binary information of the three parties is expressed by a logical expression as follows. Is like.

x = (a + b) * c + a * b Therefore, it can be decomposed into four basic logical operations and processed. Next, as shown in (5) and (6), the pattern information of one word obtained by this majority decision is shifted by 1 bit and 2 bits, respectively. Furthermore, (7) is
The bit shift data shown in (4), (5), and (6) represent only the representative bit positions of the pattern information obtained by performing the majority operation on (1) to (3). is there. In this case, the shift operation can be performed twice and the basic logic operation can be performed four times.

Since 16 is not a multiple of 3, a 1-bit remainder is generated, and since this 1-bit remainder cannot be ignored in the overall reduction, it is necessary to use the edge shift in the processing of the next word. However, it is not necessary to worry about the misalignment of the end portions by performing the above-mentioned processing with 3 words (48 bits) as one set.

As described above, according to the present invention, the majority decision can be processed by a combination of bit shifts, so that the reduction can be performed at high speed and with high fidelity.

〔Example〕

 Hereinafter, detailed description will be given according to examples.

FIG. 2 is a circuit block diagram showing an embodiment of the present invention, and FIG. 3 is a diagram showing a positional relationship between a memory address and a display surface. In the figure, 1 is a memory assigned addresses in units of words or bytes, and 2a, 2b, 2c are consecutive 3 rows of dots in the pattern information in the memory M and corresponding portions are read and stored for each row. Registers,
4,5,10,11 performs logical AND operation on the output of registers 2a, 2b, 2c, 8a, 8b, 8c, or the bit group of word or byte unit which is the output of the OR circuit in parallel. AND circuit, 3,6,9,12 are also OR circuits for performing OR operation, 7a, 7
b is a shift circuit for shifting the output of the OR circuit 6 bit by bit, 8a, 8b and 8c are OR circuits 6 and shift circuits 7a and 7b
Is a register for storing the output of the OR circuit 12, 13 is a register for storing the output of the OR circuit 12 which is the majority operation result of the registers 8a, 8b, 8c, and 14 is the first bit which is valid bit information from the output of the register R7. , 4th bit, 7th bit, etc., a logical unit for extracting the bit of a multiple of 1 + k (k is the reciprocal of the reduction ratio) and repacking without delay, 15 stores the output of the logical unit , A register for writing the contents in the memory as a part of the reduced pattern. Although not shown, the original pattern information in the memory 1 is
A control for changing the address one after another for reading while scanning by word or three bytes, a means for controlling the address for writing the reduced pattern, and a means for controlling the operation timing of each circuit or unit. Of course there is.

The operation will be described. First, from the memory 1 to (1) in FIG.
.. (3) The pattern information consisting of a binary bit group as shown in (3) is read in parallel to the registers 2a to 2c in 16-bit units.

Memory 1 is assigned addresses in units of 2 bytes (16 bits),
If the dots on the display surface consist of 720 horizontal dots and 540 vertical dots, the bits at each address on the memory correspond to those on the display surface as shown in FIG.

Therefore, at the beginning, the bits at addresses 0, 45, 90 (each of which is a relative address) of the memory 1 are read,
It is set in registers 2a, 2b, 2c, respectively.

Next, the logical story of the contents of the registers 2a and 2b is the OR circuit 3.
, And the logical product of both contents is obtained by the AND circuit 4.
The logical product of the contents of both the register 2c and the output of the OR circuit 3 is taken by the AND circuit 5 and corresponds to the bit group as shown in FIG. 1 (4) which is the majority decision of the output contents of the registers 2a, 2b, 2c. The contents to be performed are respectively output by the OR circuit 6. Therefore, the register 8a has the contents shown in FIG. 1 (4), the register 8b has the contents shown in FIG. 1 (5) via the shift circuit 7a, and the register 8c has the shift circuit 7
The contents as shown in FIG. 1 (6) are respectively stored via a and 7b. As shown in the figure, since the connection configuration of the AND circuits 10 and 11 and the OR circuits 9 and 12 is the same as the connection configuration of the AND circuits 4,5 and the OR circuits 3 and 6, the register 13 is shown in FIG. As shown in 7), the majority operation results of the registers 8a, 8b, 8c are stored. Here, looking at the contents of register 13,
The 4th, 7th, 10th, and 13th bits are representative values corresponding to the desired 5 9-bit groups, but the other bits of register R7 are 9 bits different from the desired group allocation. It can be seen that it is unnecessary for reduction because it corresponds to. Therefore, when writing the reduced pattern to the memory 1,
A logic unit 14 for correcting the contents of the register 13 to a form in which unnecessary bits are reduced is interposed, and if the bit capacity of each register is the same, the quantity for one register is completed in three times. Is stored in the register 15. In the above example, the 16th bit of each address is not used because it cannot be divided by 3. A specific example of the logic unit 14 will be described with reference to FIG.

The logic unit 14 comprises a register 14a for setting the output from the register 13 in parallel and a register 14b for stuffing and outputting the output of the register 14a.

To explain the operation, the output of the register 13 is set in the register 14a in parallel. Since only the 1st, 4th, 7th, 10th, and 13th bits of each bit set in the register 14a are required, the 1st bit of the register 14a is set to 1 of the register 14b.
The fourth bit of the register 14a is the second bit of the register 14b, the seventh bit of the register 14a is the third bit of the register 14b, and so on. The 13th bit is input to the 4th and 5th bits of the register 14b.

In this way, only the necessary representative bits are taken out and output to the register 15.

Another embodiment of the present invention will be described with reference to FIGS.

In the example of FIG. 2, the 16th bit of the majority voting output in the vertical direction is ignored, but in the present embodiment, the 16th bit is used.

For this purpose, the 16th bit of the vertical majority decision output of the bits at addresses 0, 45 and 90 shown in FIG. 5 (a),
The majority decision can be made between the first and second bits of the vertical majority decision outputs at the addresses 1, 46 and 91 shown in FIG. 5 (b). By doing this, (b)
As shown in the figure, the 15th and 16th bits of the vertical majority decision output at the 1st, 46th, and 91th addresses are the same as the 2nd and 47th addresses shown in (c). ,
Use the first bit of the vertical majority output at address 92, and so that the majority vote can be taken.

For this reason, regarding the majority decision output shown in (a),
As shown in (d), (e), and (f), the shifter 26, 27 shifts the output from the majority decision circuit 20 by one bit, and inputs it to the majority decision circuit 23, as shown in FIG.

Also, regarding the output of the majority decision circuit 21 shown in FIG.
28 shifts to the right by 1 bit, replaces the 1st bit with the 16th bit of the output (a), and outputs as a bit string shown in (g). Further, the output (d) is input as it is to the majority circuit 24 without being shifted so that the majority of the 16th bit of the output (a) and the 1st and 2nd bits of the output (b) can be obtained. The bit string (i) obtained by shifting the output (b) to the left by one bit by the shifter 29 is input to the majority decision circuit 24.

As a result, since the bit positions are aligned as shown in (g), (h), and (i), the majority decision can be made by using the 16th bit of the output (a).

Also, in order to take a majority decision using the 15th and 16th bits of the output (b), the output (c) of the majority decision circuit 22 is:
The first bit of the bit string shifted right by one bit by the shifter 32 and the first bit of the output (b) from the register 34
The 16th bit is replaced with the output (h), and the output (h) is further shifted to the right by 1 bit by the register 31, and the 1st bit of this shifted bit string is changed to the 16th bit from the shifter 30. They are exchanged and input to the majority circuit 25 as outputs (j), respectively.

As a result, the 15th bit of the output (b) and the first bit position of the output (c) are aligned, so that all bits can be used for the output (b).

Here, the 16th bit of the output (c) corresponds to the 48th bit when combined with the outputs (a) and (b), and is divisible by 3, so that all bits of the output (c) can be used.

The outputs of the majority decision circuits 23, 24, 25 are set in parallel in the registers 35, 36, 37, respectively.

Then, bit positions are clogged by the logic unit 38 similar to that shown in FIG. 4 and output. That is, each register 3
A total of 48 bits of 16 bits from 5,36,37 are input in parallel (1,4,7,10,13,17,20,23,26,29,33,36,39,42,4
After extracting the 5th and 48th bits, it is packed in 1/3 and output to the memory as 16-bit parallel data.

The circuit configurations of the majority circuits 20 to 25 are the same as those of the majority circuit shown in FIG.

In the above-mentioned embodiment, one dot of the pattern information is described as a binary value, but the present invention is not limited to this, and an average value, a median value, a maximum value, or the like may be adopted in the case of three or more values. Further, it is extremely easy to divide and share the registers, AND circuits, and OR circuits separately in time without providing them individually, or to substitute them with a general-purpose processor. Furthermore, the pattern information is not limited to two-dimensional, and may be a three-dimensionally arranged pattern or a pattern that is distributed in a higher dimension, and is of course not limited to 1/3 reduction. If you want to reduce to a natural number such as 4,1 / 5, select two or more representative values, or allow the groups to partially overlap. It can also be applied to reductions such as 5.

As described above, according to the present invention, the image data read in units of words or bytes is subjected to a majority decision of n bits, and then the majority output of the majority decision is made of m bits. Alternatively, since the access to the memory addressed in byte unit may be performed in word unit or byte unit as it is, the access time is short and a majority decision is made, so that the fidelity to the original image is also good.

[Brief description of drawings]

FIG. 1 is a diagram showing the principle of the present invention, FIG. 2 is a diagram showing an embodiment of the present invention, FIG. 3 is a diagram showing a bit at each address of the memory and a corresponding positional relationship on the display surface, and FIG. FIG. 5 is a diagram showing an example of a logic unit for packing bits, FIG. 5 is a diagram showing an operation of another embodiment of the present invention, and FIG. 6 is a diagram showing another embodiment of the present invention. In the figure, 1 is an image memory, 2a, 2b, 2c, 8a, 8b, 8c, 13, 15 are registers, 3, 6, 9, 12 are OR gates, 4,5, 10, 11 are AND gates, 14 is a logic unit. Is.

Claims (1)

[Claims] 1. Regarding image data of n columns read from an image memory in word units or byte units, which are image data on adjacent lines on a display, a dot in each column is a small area for every n bits. By dividing the matrix into a plurality of matrixes each consisting of a small region of n columns × n dots, a majority dot is taken from n dots at the same position on each column in each matrix to generate a representative dot column, Further, the representative dot row is shifted by 0 to n-1 dots by the shift means to generate n shift dot rows, which are dots belonging to the same matrix before the shift and A pattern reduction method, characterized in that a majority decision is made by n dots at the same position in a shift dot row, and a representative dot in the matrix is decided.