JPH0137066B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION Field of Industrial Application The present invention relates to various types of compression, particularly to an information compression method 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,
The leftmost value is shifted by one element to the left, and 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 a clock signal a is applied, it is shifted by one element to the left, and the leftmost value is sent out as an 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 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”
The output of the AND gate 5 also becomes "1", the clock signal f is supplied to the shift register 3, and the output signal c of the shift register 1 is taken into the shift register 3. On the other hand, if the output signal e 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. Compressed images can be generated in the shift register 3 by performing such operations in synchronization with the clock signal a for the number of elements in the shift register 1.

However, since the above method is performed in synchronization with each clock signal, high-speed operation requires a correspondingly high-speed clock, which has the disadvantage that it is difficult to implement into an LSI.

OBJECTS OF THE INVENTION The present invention solves the above conventional problems, and aims to provide an information compression method and circuit thereof that are suitable for LSI implementation and can compress information at high speed.

Configuration of the Invention The information compression method of the present invention provides information to be compressed x ₁ ,
For x ₂ ,...x _o (where n is an integer of n≧2),
It has reference mask patterns P ₁ , P ₂ , ... P _o consisting of at least binary information, and the information to be compressed x ₁ ,
When moving x ₂ , _... ≦n), a _i,j of the matrix A (where j is i≦j≦n)
If _the reference mask pattern P _i is the first information, the information means at the position _a On the other hand, if the reference mask pattern P _i is second information, an information selection element that moves the information to be compressed at the position a _i+1,j to the position a _i-1,j . and a _i,k of the matrix A (where k is 1≦
The information means at the position of k<i) includes the information to be compressed at the position of a _i+1,k , regardless of whether the reference mask pattern P _i is the first or second information. The above objective is achieved by arranging the information transmission element to be moved to the position a _i-1,k .

DESCRIPTION OF EMBODIMENTS An information compression method according to an embodiment of the present invention will be described below.

First, the original image X is divided into x ₀ , x ₁ , x ₂ , x ₃ , x ₄ , x ₅ , x ₆ ,
x ₇ , and the reference mask pattern P is 1, 0, 1,
Consider the case of 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 moves 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, the element at i=j is discarded if the reference mask pattern P _i is 0, and all elements to the right of i=j are shifted to the left by one element. be done. On the other hand, if the reference mask pattern P _i is 1, all elements of the i-th row at that time are moved to the i-1 row. This operation is performed for each element in the row with i=0 to obtain a compressed image Y as an 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) In the row where i=7, P ₇ =0, so x ₇ is discarded. In this example, there is no element M _7,8 to the right of M _7,7 , so M _6,7 is empty. Therefore i=
The row number 6 is x ₀ , x ₁ , x ₂ , x ₃ , x ₄ , x ₅ , x ₆ .

(2) Since P ₆ = 1 in the row with i=6, all elements in this row are moved to the row with i=5, so i=5
The rows are x ₀ , x ₁ , x ₂ , x ₃ , x ₄ , x ₅ , x ₆ .

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

By similarly processing the rows from i=4 to 0, the output from the matrix is Y=x ₀ ,
x ₂ and x ₆ .

By considering that there is an element of 0 in the column j = 8, 0 is added to the empty part of the matrix.
can be set.

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

FIG. 4 shows the connections of an information compression circuit that implements the information compression method 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 ₇
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 _k,l (where k and l are both integers, 1≦k≦7, 0<k) of a matrix with 8 rows and 8 columns, and information sent from above. It is an information transmission means for transmitting information downward, and may simply be a signal line. 14 is the matrix element M _s,t (however,
s and t are both integers and are provided at positions where 0≦s≦7, s≦t), and a control signal corresponding to the reference mask pattern P _s sent through the control signal input terminal 11 _s . Information selection means for selecting either the information located at the matrix element M _s+1,t+1 or the information located at the matrix element M _s+1,t according to a s _and b _s ; It is composed of logic elements 14a, 14b, 14c, and 14d as shown in the figure. However, the information selection means located in the 7th column of the matrix M is provided only to select whether or not to truncate the image information _x7 . 15
₀ to ₁₅₇ 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, when the control signal a _s sent through the control signal input terminal 11 _s is "0" and the control signal b _s is "1", the information selection means 14 selects (a _s , b _s ) = (0, 1), the matrix
When the information c located at M _s+1,t+1 is input, and the control signal a _s is "1" and the control signal b _s is "0", that is, (a _s , b _s )=(1, 0), the matrix
Selectively input information d located at M _s+1,t .

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 ₂ ,
The assumption that x ₆ is obtained is the same as the explanation shown in FIG.

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 ₁₄₀ via the information transmitting means ₁₃₀ to 136 and the information selecting means ₁₄₀ . At that time, the information selection means 14 ₀ sends ( _{a 7 ,} b ₇ )=
Since (0, 1) is applied, the information selection means ₁₄₀ selects the information on the line C side as an input signal, so the original image information _x7 is truncated.

Next, as shown in FIG. 7b, the information transmission means 13
The original image information _x0 to _x5 from ₀ to ₁₃₅ is sent to information transmission means ₁₃₇ to ₁₃₁₂ . On the other hand, the information selection means 14 ₁ is a control signal input terminal 11 ₆ as a control signal.
Since (a ₆ , b ₆ )=(1, 0) is applied via , the information on the line D side is selected, so the original image information x ₆ is input.

Next, as shown in FIG. 7c, the information transmission means 13
The original image information x ₀ to _{x 4} from ₇ to 13 ₁₁ is sent to information transmission means 13 ₁₃ to 13 ₁₇ . On the other hand, the information selection means 14 ₂ is a control signal input terminal 1 as a control signal.
Since (a ₅ , b ₅ )=(0, 1) is applied through 1 5, the information on the _line C side is selected, so the original image information x ₆ is input.

Next, as shown in FIG. 7d, the information transmission means 13
The original image information x ₀ to x ₃ from ₁₃ to 13 ₁₆ are sent to information transmission means 13 ₁₇ to 13 ₂₀ . On the other hand, the information selection means 14 ₃ is a control signal input terminal 1 as a control signal.
Since (a ₄ , b ₄ )=(0, 1) is applied through 1 4 , the information on _the line C side is selected, so the original image information x ₆ is input.

Next, as shown in FIG. 7e, the information transmission means 13
The original image information x ₀ to x ₂ from ₁₇ to 13 ₁₉ are sent to information transmission means 13 ₂₁ to 13 ₂₂ . On the other hand, the information selection means 14 ₄ is a control signal input terminal 1 as a control signal.
Since (a _{3 ,} b ₃ )=(0, 1) is applied through 1 3 , the information on the line C side is selected, so the original image information x ₆ is input.

Next, as shown in FIG. 7f, the information transmission means 13
The original image information x ₀ and x ₁ of ₂₁ and 13 ₂₂ are sent to information transmission means 13 ₂₄ and 13 ₂₅ . On the other hand, since (a ₂ , b ₂ )=(1, 0) is applied as a control signal via the control signal input terminal 11 to the information selection means 14 ₅ and 14 ₆ , the information selection means 14 5 and 14 6 are connected to the lines D ₁ and D ₂ , respectively. input the original image information x ₂ and x ₆ , respectively.

Next, as shown in FIG. 7g, the information transmission means 13
₂₄ and the original image information x ₀ are sent to the information transmission means 13 ₂₆ . On the other hand, the information selection means 14 ₇ , 14 ₈ input ( _{a 1 ,}
Since b ₁ )=(0, 1) is applied, the information on the lines C ₁ and C ₂ is selected, so the original image information x ₂ and x ₆ are input, respectively.

_{Finally ,} as _{shown in FIG .}
0) is applied, D ₁ ,
Since the information on the D ₂ and D ₃ side is selected, the original image information x ₀ ,
Enter x ₂ and x ₆ . and information selection means 14 ₉ ,
By extracting 14 ₁₀ and 14 ₁₁ as final outputs, 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 are arranged in a matrix eliminates the need for a clock even when high-speed compression is required. In addition, the regular circuit configuration makes it suitable for LSI implementation. 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, 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, and since the circuit is regular, it can be It is also suitable for commercialization, 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 (where n is
≧2 integer), has reference mask patterns P ₁ , P ₂ , ... P _o consisting of at least binary information,
When moving the information x ₁ , x ₂ , ... x _o to be compressed from the nth row to the first row in the matrix A consisting of information means arranged in n rows and n columns, (however, i is 1≦i≦n), a _i,j of the matrix A (however, j is i≦j≦
As the information means at the position n), if the reference mask pattern P _i is the first information,
The information to be compressed at the position a _{i+1,j+1 is} a _i-1,j
On the other hand, if the reference mask pattern P _i is the second information, move the information to be compressed at the position a _i+1,j to the position a _i-1,j. Information selection elements are arranged, and a _i,k of the matrix A (where k is 1≦
The information means at the position of k<i) includes the information to be compressed at the position of a _i+1,k , regardless of whether the reference mask pattern P _i is the first or second information. An information compression method characterized by arranging an information transmission element that is moved to a _i-1,k position. 2. The information compression method according to claim 1, wherein the information transmission element is a wiring.