JPH0221632B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION Field of the Invention The present invention relates to various types of compression, particularly to an information compression method and circuit that can perform high-speed compression of image information.

Conventional configurations and their problems In recent years, editing processes such as image enlargement and reduction, which used to be performed on large computers and expensive dedicated systems, have become necessary in the field of inexpensive personal computers.

Conventional image compression will be explained below.

Compression means extracting elements corresponding to "1" in mask pattern p from original image X of length n to generate Xa, and compressing this to create compressed image Y. It's something you get.

In order to perform the above operation, an image compression circuit as shown in FIG. 2 can be considered.

In FIG. 2, 1 is a shift register that stores the original image X, and when a clock signal a is applied,
It is shifted to the left by one element, and due to the shift, the leftmost value is sent out as the output signal c. Reference numeral 2 denotes a shift register that stores the mask pattern p, and when the clock signal a is applied, it is shifted by one element to the left, and the leftmost value is sent out as the output signal d. 3 is a shift register in which the compression results are stored, and when an output signal f of an AND gate, which will be described later, is applied, each element is shifted to the left by one. 4 is a 1-bit register which takes in signal d in synchronization with clock signal b and also receives signal e.
Output. 5 is an AND gate that performs logical product. Note that the clock signals a and b have the same frequency but a phase difference.

The operation of the image compression circuit configured as above will be described below.

It is assumed that the elements of the original image X and the mask pattern p shown in FIG. 1 are stored in shift registers 1 and 2 in order from the left, respectively. First, the output signal d of the shift register 2 is synchronized with the clock signal b.
(“1” at this point) is taken into the register 4 and becomes the signal e. Next, shift registers 1 and 2 are shifted in synchronization with clock signal a. At this time, if the signal e just before being shifted is "1", AND
The output of gate 5 also becomes “1” and shift register 3
A clock signal f is supplied to the shift register 1, and an output signal c of the shift register 1 is taken into the shift register 3.
On the other hand, if the output signal l immediately before being shifted is "0", the clock signal f is not supplied to the shift register 3 and no shift operation is performed, so the output signal c that was output from the shift register 1 is disappear. Such an operation causes clock signals a, b
A compressed image can be generated in the shift register 3 by performing the same number of compressed images as the number of elements in the shift register 1 in synchronization with .

However, since the method described above is performed in synchronization with each clock signal, high-speed operation requires a correspondingly high-speed clock, making it difficult to implement into an LSI, and furthermore, it is difficult to create an image like the one shown in the table. When compressing, if there is frame information of a table in an element that is not extracted, the frame information is lost.

Purpose of the Invention The present invention solves the above-mentioned conventional problems, and provides an information compression method that is suitable for LSI implementation, performs high-speed information compression, and does not eliminate frame information even when compressing an image such as a table. and its circuit.

Structure of the Invention The information compression method of the present invention is based on the information to be compressed x ₁ ,
x ₂ , ..., x _o (where n is an integer of n≧2), there are reference mask patterns p ₁ , p ₂ , ..., p _o consisting of at least binary information, and the compression When moving the power information x ₁ , x ₂ , ..., x _o from the nth row to the first row in the matrix A consisting of n rows and n columns, the reference mask pattern p _i (however, i is an integer with 1≦i≦n) is the first information, then the information x _i located at a _i,i of matrix A and a _i,i-1
Performs a logical sum operation with the information x located at , moves the result to a _{i-1, i-1} of matrix A, and
a _i,j of matrix A (where, j is (i+1)≦j
≦n) and a _i,u (where u is an integer of 1≦u≦i− ₂ )
and a _i-1,u respectively, and on the other hand, if the reference mask pattern p _i is second information, it is located at a _i,v (where v is an integer of 1≦v≦n) of matrix A. The above objective is achieved by moving the information x to the position a _i-1,v of the matrix A.

On the other hand, the information compression circuit of the present invention has a matrix A of n rows and n columns (where n is an integer of n≧2) _.
(However, k and l are integers of 3≦k≦n, 1≦l≦k-2), and an information transmission means is provided at the position,
a _n,q of the matrix A (however, m, q are 1≦
An information selection means is provided at a position where m≦n, an integer of 0<m-1≦q≦n), and information to be compressed x ₁ , x ₂ , . . .
..., x _o from the nth row to the first row, the information transmission means provided in the nth row is the information transmission means provided in the n-1th row, or The information selection means sends the information x so that it can be input, and the rth row (where r is 3
≦r≦n-1 (an integer of The information selection means provided in the matrix A determines whether or _not the information to be compressed
The information selection means provided at the position a _n-1,q responds to the control signal corresponding to the reference mask pattern by the information selection means provided at the position a _n,q+1 of the matrix A. Select whether to input the output information x of the matrix A or the output information x of the information transmission means or information selection means provided at positions a _n,q of the matrix A, and then The information selection means provided at positions _{a n-1, n-2} and a _{o, o-1} selects the information from the matrix A.
The output information of the information selection means provided at the position a _{n,n-1 of} the matrix A and the a _n, Calculating means for performing calculations between the output information of the information transmitting means provided at the position _{n-2 and} between _the information In response to a control signal corresponding to a pattern, the output information of the information transmission means provided at positions a _n,n-2 of the matrix A is input, or the output information of the calculation means in the information selection means is input. Input and Information x _o-1 Input
The above objective is achieved by selecting whether to input the output information of the calculation means for x _o and x _o-1 .

DESCRIPTION OF EMBODIMENTS An information compression method according to an embodiment of the present invention will be described below. For convenience of explanation, here 8
It is a matrix with 8 rows and 8 columns, and the subscript values are expressed as 0 to 7.

First, the original image X is divided into x ₀ , x ₁ , x ₂ , x ₃ , x ₄ , x ₅ , x ₆ ,
x ₇ or reference mask pattern p to 1, 0,
Consider the case of 1, 0, 0, 0, 1, 0.

As shown in FIG. 3, each element of the matrix is designated by M _i,j with a subscript i in the vertical direction and j in the horizontal direction. The original image X initially exists in the row i=7, and is moved within the matrix in the direction from the i-th row to the i-1th row to obtain compressed images Y=x ₀₁ , x ₂₃₄₅ , x ₆₇ . When moving from the i-th row to the i-1th row, if the reference mask pattern p _i is 0, the element M _ij of i=j
All elements to the right are shifted one element to the left. At this time, a logical sum is taken between the element M _ij of i=j and the element M _ij-1 . One side reference mask pattern
If p _i is 1, all elements of the i-th row at that time are i-
Move it to the first line. This operation is performed for each element in the row with i=0 to obtain the compressed image Y as output from the matrix.

If we apply the actual values according to the above principle and look at how they are compressed, we get the following.

(1) Since p ₇ =0 in the row where i=7, x ₇ is ORed with x ₆ , and as a result, M _6,6 becomes x ₆ + x ₇ . In this example, there is no element M _7,8 to the right of M _7,7 , so M _6,7 is empty. Therefore, the row of i=6 becomes x ₀ , x ₁ , x ₂ , x ₃ , x ₄ , x ₅ , x ₆ +x ₇ .

(2) Since p ₆ = 1 in the row with i=6, all elements of this row are moved to the row with i=5, so the row with i=5 has x ₀ , x ₁ , x ₂ , x ₃ , x ₄ , x ₅ , x ₆ + x ₇ .

(3) In the row where i=5, p ₅ =0, so x ₅ is ORed with x ₄ , and all elements to the right of j=5 are shifted to the left. Therefore, the row of i=4 has x ₀ , x ₁ ,
x ₂ , x ₃ , x ₄ , x ₅ , x ₆ + x ₇ .

By similarly processing the rows from i=4 to 0, the output from the matrix becomes Y=x ₀ +
x ₁ , x ₂ + x ₃ + x ₄ + x ₅ + x ₆ + x ₇ .

By assuming that there is an element of 0 in the column j=8, it is possible to set 0 to the empty portion of the matrix.

Next, an information compression circuit according to an embodiment of the present invention will be described.

FIG. 4 shows the wiring of an information compression circuit in one embodiment of the present invention.

In FIG. 4, ₁₀₀ to 107 are information input terminals to which image information _{x0 to x7 to} be compressed are applied, and ₁₁₀ to
11 ₇ is 2 according to the reference mask pattern p ₀ to _{p 7}
a control signal input terminal, 12, to which a value control signal is applied;
₀ to ₁₂₇ are inverters. 13 is provided at the position of element M _j,k (where j and k are both integers, 2≦j≦7, O≦k≦j≦-2) of a matrix with 8 rows and 8 columns, and An information transmission means for transmitting information downward, and may simply be a signal line. 14 is an element of the matrix
M _s,t (both s and t are integers, 0≦s≦7,
s≦t≦7), and
A control signal a _s corresponding to the reference mask pattern p _s sent through the control signal input terminal 11 _S ,
_b An information selection means for selecting either the information located in the matrix element M _s+1,t+1 or the information located in the matrix element M _s+1,t according to s, as shown in FIG.
Logic elements 14a, 14b, 14c, as shown in FIG.
14d. However, the information selection means located in the j=7 column of the matrix M is provided only to select whether or not to truncate image information _x7 . 16 is an element of the matrix
The element M of the matrix is determined in response to the control signals a _i and b _i corresponding to the reference mask pattern p _i provided at the position M i, _i-1 and sent out via the control signal input terminal 11 _i . The result of the logical sum of _i+1,i and the information located at M _i+1,i-1 or the element of the matrix
Information selection means for selecting one of the information located at M _{i+1, i-1} , which uses a logic element 16 as shown in FIG.
It is composed of a, 16b, 16c, 16d, and 16e. The information selection means 16 inputs the logical sum of information d and c instead of the information c to the information selection means 14. 15 ₀ to 15 ₇ are output terminals from which compressed image information Y is obtained.

The information selection means 14 will be described below with reference to FIG.
The configuration will be explained in more detail.

As shown in FIG. 6, the control signal input terminal _11s
When the control signal a _s sent through is “0” and the control signal b _s is “1”, that is, (a _s , b _s )=(0,
In case 1), the information selection means 14 selects the matrix.
The information selection means 16 selects the information c located at M _s+1,t+1.
The logical sum of information e and f located at M _s+1,t and M _s+1,t-1 is input, while the control signal a _s is "1" and the control signal b _s
When is "0", that is, when (a _s , b _s ) = (1, 0), the information selection means 14 selects the information d located at M _s+1,t of the matrix from the matrix M Information f located at _{s+1, t-1} is selectively input.

The operation of the above configuration will be explained below.

Note that the reference mask pattern p is 1, 0, 1, 0,
0, 0, 1, 0, and finally compressed information x ₀ + x ₁ ,
Assume that we obtain x ₂ + x ₃ + x ₄ + x ₅ and x ₆ + x ₇ .

First, as shown in FIG. 7a, the information input terminal 10
The original image information _x0 to _x7 is sent to the information transmitting means ₁₃₀ to ₁₃₅ and the information selecting means ₁₆₀ and ₁₄₀ via the information transmitting means 130 to 135 and the information selecting means ₁₆₀ and ₁₄₀ . At this time, since (a ₇ , b ₇ )=(0, 1) is applied as a control signal via the control signal input terminal 11 ₇ , the information selection means 14 ₀ receives the information on the line C side as an input signal. , the information selection means 16
₀ selects the logical sum of the E and F signals x ₆₇ =x ₆ +x ₇ . (Hereinafter, the result of the logical sum of information x ₁ , x ₂ , ..., x _i will be written as x ₁₂ ...i) Next, as shown in FIG.
The original image information _x0 to _x4 from ₀ to ₁₃₄ is sent to information transmission means ₁₆₆ to ₁₃₁₀ . On the other hand, since (a ₆ , b ₆ )=(1, 0) is applied as a control signal to the information selection means 14 ₁ , 16 ₁ via the control signal input terminal 11 ₆ , the information selection means 14 ₁ is connected to the line D
Since the information on the line F side is selected, the information selection means ₁₆₁ inputs the original image information x ₆₇ and the information x ₅ on the line F side.

Next, as shown in FIG. 7c, the information transmission means 13
The original image information _x0 to _x3 from ₆ to ₁₃₉ are sent to information transmission means ₁₃₁₁ to ₁₃₁₄ . On the other hand, since (a ₅ , b ₅ ) = (0, 1) is applied as a control signal to the information selection means 14 ₂ , 16 ₂ via the control signal input terminal 11 ₅ , the information selection means 14 ₂ is connected to the line C. Select the side information, so enter the original image information x ₆₇ ,
Information selection means 16 ₂ is the logical sum of information on lines E and F x ₄₅
Select.

Next, as shown in FIG. 7d, the information transmission means 13
The original image information _x0 to _x2 from ₁₁ to ₁₃₁₃ is sent to information transmission means ₁₃₁₅ to ₁₃₁₇ . On the other hand, since (a ₄ , b ₄ )=(0, 1) is applied as a control signal to the information selection means 14 ₃ , 16 ₃ via the control signal input terminal 11 ₄ , the information selection means 14 ₃ is To select the information on the line C side, input the original image information x ₆₇ , and the information selection means 16 ₃ is the logical sum of lines E and F.
Select _x345 .

Next, as shown in FIG. 7e, the information transmission means 13
The original image information x ₀ , x ₁ of ₁₅ and 13 ₁₆ is sent to information transmission means 13 ₁₈ , 13 ₁₉ . On the other hand, since (a ₃ , b ₃ )=(0, 1) is applied as a control signal to the information selection means 14 ₄ , 16 ₄ via the control signal input terminal 11 ₃ , the information selection means 14 ₄ is connected to the line Select the information on the C side, so enter the original image information x ₆₇ ,
The information selection means ₁₆₄ selects the logical sum x ₂₃₄₅ of lines E and F.

Next, as shown in FIG. 7f, the information transmission means 13
₁₈ original image information _x0 is sent to the information transmission means ₁₃₂₀ . On the other hand, information selection means 14 ₅ , 14 ₆ , 16 ₅
Since (a ₂ , b ₂ )=(1, 0) is applied as a control signal via the control signal input terminal 11 ₂ , the information selection means 14 ₅ and 14 ₆ are connected to the line, respectively.
Since information on D ₁ and D ₂ side is selected, original image information x ₂₃₄₅ ,
Input x ₆₇ respectively, information selection means 16 ₅ is line F
To select side information, enter original image information x ₁ .

Next, as shown in FIG. 7g, the information selection means 14
₇ , 14 ₈ , 16 ₆ are applied with (a ₁ , b ₁ )=(0, 1) as control signals via the control signal input terminal 11 ₁ , so that the information selection means 14 ₇ , 1
4 ₈ selects the information on the lines C ₁ and C _2, respectively, so input the original image information x ₂₃₄₅ and x ₆₇ , respectively, and the information selection means 16 ₆ selects the logical sum x ₀₁ of the information on lines E and F. .

Finally, as shown in FIG. 7h, the information selection means 14 ₉ , 14 ₁₀ , _{14 11} sends (a ₀ , b ₀ )=(1,
0) is applied, D ₁ ,
Since the information on the D ₂ and D ₃ side is selected, the original image information
Enter x ₀₁ , x ₂₃₄₅ , x ₆₇ . By extracting the information selection means 14 ₉ , 14 ₁₀ , 14 ₁₁ as the final output, compressed information Y can be obtained.

As described above, according to this embodiment, the circuit configuration in which the information transmitting means 13 and the information selecting means 14 and 16 are arranged in a matrix eliminates the need for a clock even when high-speed compression is required. Moreover, since it has a regular circuit configuration, it is suitable for LSI implementation. Furthermore, when compressing the original image information, by taking the logical sum of adjacent information, the information of logic "1" will not disappear. Therefore, the frame of the table created with logic "1" will be It never goes away. Further, other compressed information Y can be easily obtained by simply changing the control signal applied to the control signal input terminal 11.

In this embodiment, the information transmission means 13 is provided for convenience of explanation, but as described above, the information transmission means 1
3 may be a simple wiring, so the circuit in Figure 4 is the 8th one.
It may be as shown in the figure.

Further, in this embodiment, a logical sum is used as the calculation for compression, but other calculations can easily be used. Further, in this embodiment, only image information has been described, but other information may be applied to the present invention, and it can also be used for information sampling, etc.

Effects of the Invention As described above, the present invention can compress information at high speed without using a clock by processing information to be compressed using a matrix. By taking the logical sum of the information, the information of logic "1" is not lost.Therefore, the frame of the table created with logic "1" does not disappear due to compression. Also, because the circuit is regular, it is suitable for LSI implementation, and its value is great.

[Brief explanation of drawings]

FIG. 1 is a diagram showing image compression, FIG. 2 is a block diagram of a conventional image compression circuit, FIG. 3 is a diagram explaining an information compression method in an embodiment of the present invention, and FIG. 4 is a diagram of the present invention. A wiring diagram of an information compression circuit in an embodiment of the invention, FIG. 5 is a circuit diagram of the information selection means, FIG. 6 is a wiring diagram of the same means, and FIG. 7 is a wiring diagram showing the operation of the information compression circuit. FIG. 8 is a wiring diagram of an information compression circuit in another embodiment of the present invention. 13... Information transmission means, 14... Information selection means.

Claims (1)

[Claims] 1 Information to be compressed x ₁ , x ₂ , ..., x _o (however, n
has _a reference _mask pattern _{p 1} , p ₂ , . _o to n
When moving from the nth row to the first row in the matrix A consisting of rows and n columns, the reference mask pattern p _i (where i is an integer of 1≦i≦n)
is the first information, the information x _i located at a _{i,i of matrix A} and the information x located at a _i,i-1 are operated, and the result is a _i-1,i of matrix A. _-1 , and matrix A's a _i,j (where, j is (i+1)≦j≦n) and a _i,u (however, u is 1≦u
≦i-2 integer) is moved to a _i-1,j-1 and a _i-1,u of matrix A, respectively,
On the other hand, if the reference mask pattern p _i is second information, a _i,v of matrix A (where v is 1≦v≦
The information x located at
An information compression method characterized by moving to a _i-1,v position. 2 a _k,l of matrix A with n rows and n columns (where n is an integer of n≧2) (however, k and l are 3≦k≦n, 1
≦ _l ≦k-2 (an integer of
m _, q are integers of 1≦m≦n, 0<m- ₁ ≦q≦n), and an information selection means is provided at the position _of When moving in the direction of the first row from The information transmitting means provided in the r-th row (where r is an integer of 3≦r≦n-1) transmits the information so that the information The selection method is information x
On the other hand, the information selection means provided in the n-th column determines whether or not to truncate the information to be compressed x _o in accordance with a control signal corresponding to the reference mask pattern; The information selection means provided at the position a _n-1,q of the matrix A responds to the control signal corresponding to the reference mask pattern by selecting the information selection means provided at the position a _n,q+1 of the matrix A. Output information x of information selection means
or input the output information x of the information transmission means or information selection means provided at the position a _n,q of the matrix A,
Furthermore, the information selection means provided at positions a _{n-1, n-2} and a _{o, o-1} of the matrix A selects the information provided at positions a _{n-1, q} of the matrix A. The selection means includes the output information of the information selection means provided at position a _n,n-1 of the matrix A and the output information of the information transmission means provided at position a _n,n-2 of the matrix A. Between output information and information x _o
x _o-1 , and the information selection means selects the matrix A according to a control signal corresponding to the reference mask pattern.
Whether to input the output information of the information transmission means provided at the position a _n,n-2 or the output information of the calculation means in the information selection means, and the information
An information compression circuit characterized in that it selects whether to input x _o-1 or output information of a calculation means of information x _o and x _o-1 . 3. The information compression circuit according to claim 2, wherein the information transmission means is a wiring.