JP2695266B2 - Arbitrary image rotation method and device - Google Patents

Description

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an image data rotation method and apparatus for rotating image data such as characters and figures at an arbitrary angle.

2. Description of the Related Art Conventionally, many techniques have been disclosed for rotating an image by 90 degrees, but the following method is used for rotating an arbitrary angle.

One pixel of the source image (original image) in X and Y coordinates
Expressed as S _X and S _Y , the rotation angle is a, and the corresponding X and Y coordinates of the rotated destination image (target image) are
If D _X , D _Y , D _X , D _Y is calculated by the formula of D _X = S _X COSa-S _Y SINa D _Y = S _Y SINa + S _Y COSa, and is calculated in bit unit at the corresponding position of the destination image. Writing was done sequentially.

However, according to the above method, it is necessary to perform four multiplications and two additions per pixel, and sequentially write in bit units at corresponding positions in the destination image.
Therefore, when the size of the rotating image becomes large, the amount of calculation increases in proportion to the square of the size, and there is a problem that the calculation time becomes long.

The present invention has been made in view of the above-mentioned problems, and the original image is divided into blocks each having a size of a predetermined pixel without processing an arbitrary angle of the image for each corner pixel, and the block is divided into row units. It is an object of the present invention to provide a method and apparatus for rotating an image at an arbitrary angle, which enables high-speed processing by performing the processing described in 1.

Means for Solving the Problems In order to achieve the above object, the original image is divided into blocks each having a size of a predetermined pixel, and for this block,
Operations such as shift, reduction, enlargement, rotation by 90 degrees, and rotation may be performed on a row-by-row basis of the matrix forming the block. The arbitrary angle rotation method of the image of the present invention is based on the reference point on the reference coordinate axis. When an image is rotated by an arbitrary angle θ to create a target image, the original image is formed as a set of reference blocks made of N × N pixels and a square having one side parallel to the axis rotated −θ with respect to the reference coordinate axis. One of the vertices of each of the reference blocks is a rotation vertex, and each of the reference blocks is rotated by θ about the rotation vertex to create a rotation block. The rotation vertex of this rotation block is about θ of the reference point. The amount of movement in the direction of the reference coordinate axis that occurs when rotating is ΔY,
It is characterized in that the moving amount in the direction perpendicular to the reference coordinate axis is ΔX, the rotary block is moved in parallel in the direction of the reference coordinate axis by ΔY, and the rotary block is moved in parallel by ΔX in the direction perpendicular to the reference coordinate axis to obtain a target image. It is a thing. Further, when the rotation block is created from the reference block, the axis passing through the rotation vertex and parallel to the reference coordinate axis is defined as the Y axis, and the axis orthogonal to the Y axis is defined as the X axis to configure the reference block. With the x-axis and y-axis coordinates of the element as (x, y), the x-coordinate of the element is shifted in the x-axis direction to become xy * tan θ, and further X
Multiply cosθ in the axial direction to obtain xcosθ-y * sinθ, then multiply the y coordinate by 1 / cosθ in the Y-axis direction to y / cosθ and move to (xcosθ-y * sinθ, y / cosθ) coordinates The reference block is formed in the shape of a parallelogram in which one of the reference blocks has a length equal to the X-axis and Y-axis directions of the rotary block, and the other has a protrusion in the Y-axis direction from the rotary block, and the other has a concave shape. The read row bit sequence and the corresponding row bit sequence of the recessed triangular portion are read out so that the protruding triangular portion overlaps the recessed triangular portion. Is taken as a matrix consisting of N rows × N columns that matches the shape of the rotation block, the transposed matrix of this N rows × N columns matrix is obtained, and each row of this transposed matrix protrudes into the triangular shape. The bits of the part are at the right end of the line For rows lined up toward each other, it is preferable to perform a left rotation by the number of protruding bits in the row to obtain a rotated image, calculate a transpose matrix of this rotated image, and use this transposed matrix as the rotation block. . When obtaining the transposed matrix, the target matrix is set to N rows × N columns, and the number M of conversion modes of this matrix is M = [log ₂ N] (where [] is the integer when the internal numerical value is an integer. An integer
When the number after the decimal point is included, it is obtained by rounding up.), The N lines are numbered 0 to N-1, and the conversion mode L
(= 1 to M) for each, the A number rows and B number ^{line, A = k * 2 L ~k} * 2 L +2 L-1 -1 B = A + 2 L-1 k = O~ (N / 2 L ) -1 to obtain the row bit sequence of row A and row B as A
(J), expressed in B (j), A '( j), B' (j) the A '(j) = A ( j) j = k * 2 L ~k * 2 L +2 L-1 -1 A '(j) = B ( j-2 L-1) j = k * 2 L +2 L-1 ~k * 2 L +2 L -1 B' (j) = B (j) j = k * 2 L +2 ^{L-1 to} k * 2 ^L +2 ^L- 1 B '(j) = A (j + 2 ^L-1 ) j = k * 2 ^{L to} k * 2 ^L +2 ^L-1 -1 k = O to (N / 2 ^L ) −1, A (j) is A ′ (j) and B (j) is B ′.
It is preferable that the matrix of N rows × N columns is obtained by converting into (j) and changing L from 1 to M, and this matrix is used as the transposed matrix. Further, when the rotation block is created from the reference block, the axis passing through the rotation vertex and parallel to the reference coordinate axis is defined as the Y axis, and the axis orthogonal to the Y axis is defined as the X axis to configure the reference block. Element X
The x-coordinate of the element is x-
It is shifted in the X-axis direction so that y * tanθ, and then multiplied by cosθ in the X-axis direction to obtain xcosθ−y * sioθ, and then the y coordinate is multiplied by 1 / cosθ in the Y-axis direction to yield y / cosθ as (xcosθ− (y * sin θ, y / cos θ) coordinates so that the reference block has the same length as the X-axis and Y-axis directions of the rotating block and protrudes downward from the rotating block in the Y-axis in a triangular shape, and the upper portion is concave. When a parallelogram is formed, and this triangle is formed by row bits arranged in parallel with the X axis and formed by n rows, each row of the parallelogram formed by n + N rows is numbered 0 to n + N-1. When a mask matrix having n + 1 rows × N columns and having the triangularly recessed range as 0 and the other as 1 is created and the 0th row is obtained, first, the 0th row to the nth row are calculated.
The 0'th row to the n'th row depending on the logical product of the row and the mask matrix.
A row is created, the 1'th row is masked in the 0'th row where the bit is not 0, the masked portion is set to 0 bit, and the masked row and the 0'th row are ORed to obtain the first row. A 0'-corrected row is created, the 2'-th row is masked for the portion of the 0'-corrected row whose bit is not 0, and this masked portion is set to 0 bit. The masked row and the 0'-corrected row are ORed First 1 '
Make a modified line, mask the 3'-th line of the 1'-corrected line where the bit is not 0, and make this masked part 0 bit,
The masked line and the 1'-corrected line are logically ORed to form the 2'-corrected line. In the same manner, the n'-th line is changed to the (n-
2) 'Mask the part where the bit of the modified line is not 0 to make this masked part 0 bit, and take the logical sum of this masked line and the (n-2)' modified line ) ′
If a corrected row is created, this (n-1) '-corrected row is the 0th row, and similarly, N-1 rows are obtained in the same manner to obtain a matrix of N rows x N columns, and this matrix is the rotation block. Good.
Further, the image arbitrary-angle rotation device of the present invention generates a reference block that represents an original image as a set of reference blocks composed of squares of N × N pixels each side of which is parallel to the axis rotated by −θ with respect to the reference coordinate axis. Means for rotating the reference block by θ to create a rotation block, one of the vertices of the reference block, which is the center of rotation, is defined as a rotation vertex, and an axis passing through the rotation vertex and parallel to the reference coordinate axis is defined as a Y-axis. The axis that is orthogonal to this and that passes through the apex is the X axis, the coordinates of the X axis and the Y axis of the elements forming the reference block are x and y, and the x coordinate of the element is xy * tan θ. X to shift in the direction
Axial direction shifting means, X-axis direction reducing means for multiplying the output of the X-axis direction shifting means by cos θ in the X-axis direction, and y coordinate of 1
/ cos θ times the Y-axis direction enlarging means, each column of the matrix forming a parallelogram having two sides parallel to the Y-axis direction formed by the output of the X-axis direction reducing means and the Y-axis direction enlarging means In the Y-axis direction to create a rotation block, and the rotation vertex of the rotation block is rotated by θ around a reference point on the reference coordinate axis that is the rotation center for rotating the original image. And a moving means for moving the rotary block by calculating a moving amount in the reference coordinate axis direction and a moving amount in a direction perpendicular to the reference coordinate axis. Further, the rotating block creating means reads out a triangular portion protruding from the rotating block of the parallelogram for each row bit row parallel to the X axis, and the protruding triangular portion corresponds to the rotating block. Matrix generation for generating a matrix matching the shape of the rotating block by taking the logical sum of the row bit sequence read so as to overlap the more depressed triangular portion and the corresponding row bit sequence of the depressed triangular portion Means and
Rotating means for performing a row rotation for each row of the matrix, and a transposed matrix creating means for creating a transposed matrix of the matrix, the output of the matrix generating means is input to the transposed matrix creating means to output a transposed matrix, This row is rotated by the rotation means for each row, and for the rows in which the bits of the portion protruding in the triangular shape are arranged from the left end of the row toward the right end, the left rotation is performed by the number of protruding bits arranged in the row. It is preferable that the matrix is input to the transposed matrix creating unit to output a transposed matrix, and this matrix is used as the value of the rotation block. Further, the transposed matrix creating means includes an image data storing means for storing image data and a conversion mode number M of N rows × N columns of image data.
M = [log ₂ N] (where [] is the integer when the internal numerical value is an integer,
Conversion mode calculation means for outputting a conversion mode L (= 1 to M) obtained by rounding up when there are numerical values below the decimal point, and the above N rows are numbered 1 to N-1 Depending on L, the A-th row and the B-th row from the N-th row are A = k * 2 ^{L to} k * 2 ^L + 2 ^L-1 -1 B = A + 2 ^L-1 k = O to (N / 2 ^L )- The row bit sequence A of row A and row B is calculated by 1
(J) and B (j) are selected, and A (j) and B (j) are input to input A '(j) and B' (j).
The A '(j) = A ( j) j = k * 2 L ~k * 2 L +2 L-1 -1 A' (j) = B (j-2 L-1) j = k * 2 L +2 ^{L-1 ~k * 2 L +2} L -1 B '(j) = B (j) j = k * 2 L +2 L-1 ~k * 2 L +2 L -1 B' (j) = A (j + 2 ^{L1) j = k * 2 L} ~k * 2 is calculated by ^{L +2 L1 -1 k = O~ (} N / 2 L) -1, wherein the image data a (j), B a (j), respectively Convert it to A '(j), B' (j), and change this operation to L
And image conversion means for obtaining a matrix of N rows × N columns by changing from 1 to M. Further, as the rotation block creating means, the parallelogram is a parallelogram that is triangular in shape and protrudes downward from the rotation block in the Y-axis direction and is recessed in the upper side. The triangle is a bit array n rows parallel to the X-axis. When formed, each row of the parallelogram formed by n + N rows is numbered 0 to n + N-1, and the range formed by n + 1 rows × N columns is set to 0 and the other one is set to 0. The logical multiplication of the mask matrix and the n + 1th row × Nth column from the kth row to the k + nth row is performed from the k'th row to the (k + th) row.
n) 'row creating masking means, and the (k + 1)' th row is masked at the portion where the bit of the (k-1) 'th corrected row is not 0 to make this masked portion 0 bit, and the masked row Correction line creating means for taking a logical sum of the (k-1) 'th correction line to form a k'th correction line, and for obtaining the kth line, the masking means performs the k'th row to the (k + n) th row. ) ′
A row is obtained, and the (k + n-1) 'th corrected row is sequentially obtained from the k'th corrected row by the corrected row creating means.
1) ′ The corrected row may be the k-th row, and rows 0 to N−1 may be obtained to obtain a matrix of N rows × N columns, and this matrix may be used as a rotation block.

Operation First, the basic idea of the present invention will be described with reference to FIG.

It is assumed that the original image 100 is rotated about the reference point 102 on the reference coordinate axis 101 by an arbitrary angle θ to obtain a target image 103 indicated by a broken line.

First, the original image 100 is represented as a set of reference blocks 104. The reference block 104 is a square block made up of N × N pixels, and one side of the square corresponds to the reference coordinate axis 101.
It is parallel to the axis when rotated by θ.

Then rotate each reference block 104 one of its vertices
As 06, the rotation block 105 is created by making a θ rotation around this.

Next, the amount of movement ΔY in the direction of the reference coordinate axis 101 and the amount of movement Δx in the direction orthogonal to the reference coordinate axis 101, which occur when the rotation vertex 106 of the rotation block 105 on the original image 100 is rotated by θ around the reference point 102, are calculated. The rotary block 105 is moved in parallel by ΔY in the direction of the reference coordinate axis 101 and by ΔX in the direction perpendicular to the reference coordinate axis 101.

In this way, the rotation vertex 106 becomes a point on the target image 103.
Move to 107. In this way, as a result of moving all the reference blocks 104 on the original image 100, the target image 103 shown by the broken line is formed, so that the original image 100 is rotated by the arbitrary angle θ.
Can rotate. Next, a method of rotating the reference block 104 to create the rotation block 105 will be described with reference to FIGS. 2 to 7.

Keep Figure 2, all points of the square of the reference block 104, moving a point on the straight line O ₁ -K1 is one side of the square parallel to the X axis (shift) linearly O ₁ -K2 to top To move to.

The rotation angle is θ, the coordinate x of any point in the reference block 104,
y, where the coordinates after movement are X, Y, X, Y = x−y * TAN θ, y When the above conversion is performed, the reference block 104 becomes the parallelogram A shown in FIG.

Next, in FIG. 3, each point in the parallelogram A is compressed in the X-axis direction so that one side m1 of the parallelogram A overlaps with one side m2 of the rotary block 105. As a result, the coordinates X, Y of each point are X, Y = (x−y * TANθ) COSθ, y = x * COSθ−y * SIN
When the conversion above θ, y is executed, the parallelogram A is transformed into the parallelogram B shown in FIG.

Next, in FIG. 4, the parallelogram B is enlarged in the Y-axis direction so that the point P of the parallelogram B overlaps the point Q. As a result, the coordinates X, Y of each point are transformed into the parallelogram C shown in FIG. 5 when the above conversion is performed, X, Y = x * COS [theta] -y * SIN [theta], y / COS [theta].

In FIG. 5, when all the points in the parallelogram C are moved (shifted) in the Y-axis direction so that the points b and c overlap with the points c and g, the rotation is completed at the position of the rotation block 105.

The coordinates X and Y of each point are: X = x * COSθ−y * SINθ Y = y * / COSθ + (x * COSθ−y * SINθ) * TANθ =
x * SINθ + y * COSθ, which agrees with the equation described in the section of the related art.

By the way, in the normal memory structure, the bit sequence in the X-axis direction, that is, the row direction can be read or written together in word units, but the bit sequence in the Y-axis direction, that is, the column direction must be 1 bit at a time. Cannot read or write. If a special memory structure is adopted, it is possible to perform processing in units of a plurality of bits in the column direction, but if this is done, the circuit configuration becomes large and complicated. Considering the characteristics of such a memory, since the shift and enlargement / reduction processing can be performed up to the creation of the parallelogram C shown in FIG. 5, bit processing can be performed in a row unit in a normal memory. Is shifted in parallel to the Y-axis and matched with the rotation block 105 is a 1-bit process, and rapid processing cannot be performed. Therefore, the present invention implements the method of shifting the parallelogram C in parallel with the Y-axis by using two methods as follows, using an ordinary memory.

 First, one method will be described with reference to FIG.

In FIG. 6, step 1 is the same as the state shown in FIG. The triangle abc of the parallelogram C is moved to the upper triangle part. The movement is performed row by row, and when row 0 is moved to row 0'and row 2 is moved to row 2 ', triangle abc moves to the upper part and becomes a square matrix as shown in step 2. Next, step 3 is the transposed matrix of the matrix of step 2. Step 3
In, the triangular portion moves to the position shown. Next, a left rotate shift is performed so that all the triangles abc are on the right side, and step 4 is obtained. When the transposed matrix of the matrix in step 4 is taken, the state shown in step 5 is obtained. At this time, the position of b in the triangular portion has moved to the position of c in step 1 as shown in the figure.

That is, all the figures become figures that are translated in the Y-axis direction, and the rotation block 105 is obtained.

 Another method will be described with reference to FIG.

This method represents a process for converting a matrix of parallelogram C into a square matrix, and shows a method of converting k rows from Axxx to ABCD rows.

In step 1, the mask 1 determined by the size of the triangular portion is multiplied from k rows to the row determined by the size of the mask 1 to obtain the rightmost matrix. In step 2, the mask 2 is covered on the (k + 1) 'th row to obtain the rightmost row. In step 3, the k'row and the row obtained in step 2 are ORed to obtain the rightmost row. In step 4, the mask 3 is overlaid on the (k + 2) 'row to obtain the rightmost row, and in step 5, the logical sum of this row and the row obtained in step 3 is obtained to obtain the rightmost row. In step 6, the mask 4 is placed on the (k + 3) ′ row to obtain the rightmost row, and in step 7, this row and the row obtained in step 5 are ORed,
Get the desired row ABCD. By performing such processing for each row, the same result as when the parallelogram C is translated in the Y axis is obtained, and the rotation block 105 is obtained.

Embodiment An embodiment of the present invention will be described below with reference to FIGS. 1 to 16.

FIG. 8 is a block diagram showing the configuration of the embodiment of the present invention.

The reference block generation means 1 causes the original image 100 to be −θ with respect to the reference coordinate axis 101 as described in FIG. 1 (where θ is the rotation angle when the original image 100 is rotated by θ to create the target image 103). ) This is a means for generating the reference block 104 which is the component so that the reference block 104 is configured as a set of N × N pixels each side of which is parallel to the rotated axis. The X-axis direction shifting means 2 sets one of the vertices of the reference block 104 as the rotation vertex 106 as described with reference to FIG.
An axis passing through 106 and parallel to the reference coordinate axis 101 is defined as a Y-axis, an axis orthogonal to the Y-axis is defined as an axis passing through the rotation vertex 106, and the X-axis and Y-axis coordinates of the elements forming the reference block 104 are defined as x and y. And the second
As described in the figure, the straight line O which is one side of the reference block 104
₁ on the Y-axis by moving in parallel a point on the X axis -K1 linear O ₁ -K
This is a means for moving all the points in the reference block 104 so as to move to 2, and creating the parallelogram A shown in FIG. At this time, the points x and y in the reference block 104 are represented by X and Y, and X, Y = x * TAN θ, y.

The X-axis direction reduction means 3 is means for reducing the parallelogram A shown in FIG. 3 in the X-axis direction so as to become a parallelogram B shown in FIG.

As a result, the coordinates X, Y after reduction are X, Y = x * COSθ−y * SINθ, y.

A concrete example of the reduction in the X-axis direction is shown in FIG. In FIG. 9, if the source data is the row data before reduction and the reduction ratio is 2/3, as shown in the data after the reduction processing, 3 bits of 9 bits of the source data are thinned out to 6 bits. It becomes line data.

The Y-axis direction enlarging means 4 is means for enlarging the parallelogram B shown in FIG. 4 in the Y-axis direction to form a parallelogram C shown in FIG. As a result, the coordinates X, Y after expansion are X, Y = x * COSθ-y * SINθ, y / COSθ.

FIG. 10 shows a specific example of enlargement processing in the Y-axis direction. In Fig. 10, the source data shows each line before enlargement, and if the enlargement ratio is 1.5 times, 0 lines and 2 lines are provided in 4 lines of the source data.
Lines are added to form 6 lines of data as shown in the data after the enlargement processing.

The rotation block creating means 5 is means for creating each rotation block 105 shown in FIG. 1 by shifting each column of the matrix forming the parallelogram C shown in FIG. 5 in the Y-axis direction, and details will be described later. .

As shown in FIG. 1, the moving means 6 includes a rotating block 105.
Of the rotation vertex 106 of the original image 100 about the reference point 102, which is the center of rotation of the original image 100, in the reference coordinate axis 101 direction ΔY, in the direction orthogonal to the reference coordinate axis 101 ΔX
Is calculated and the rotation block 105 is moved, whereby the original image 100 is rotated by θ to become the target image 103. Next, details of the rotation block generation means 5 will be described. The present invention discloses two method technologies for the rotation block generation means 5. First, the first method will be described with reference to FIGS. 11 to 13.

FIG. 11 is a block diagram showing the configuration of the rotation block generation means 5, and the matrix generation means 51 is a triangular portion a protruding from the rotation block 105 of the parallelogram C as shown in FIG.
It is a means for reading out bc for each row bit sequence parallel to the X-axis and writing this read row bit sequence in the recessed triangular portion so as to overlap the triangular portion efg recessed from the rotation block 105. FIGS. 12 (a) and 12 (b) show this specific example, which will be described.

The figure (a) is a matrix showing the parallelogram C. The underlined bits are the bits that make up the protruding triangle.

 The following operation is performed on the matrix shown in FIG.

8th line data with underline added (
72 73 64 65 56 57 ) is read. Next, the data 0th row (00 01) at the place where this row data is to be written is read, and the logical sum of these two row data is taken and written in the 0th row.

Next, read the 9th row data ( 74 75 6667 ),
The data of the first line (10 11 02
03) is read and the logical sum of these two row data is taken and written in the first row.

Read the 10th row data ( 76 77 ) and write this row data to the 2nd row data (20 21 12 13 04 05
) Is read out and the logical sum of these two row data is taken and written in the second row.

 By the above processing, the matrix shown in FIG.

Next, when the transposed matrix of the figure (b) is created by the transposed matrix creating means 52, it becomes as shown in the figure (c). The creation of the transposed matrix will be described later with reference to FIG. Next, for the row having the underlined bits in FIG. 3C, the rotation means 53 performs the left rotation until all the underlined bits move to the right side. As a result, the diagram (d) is obtained.
This process is performed in the following procedure. In the figure (c), the data ( 72 02 12 22 32 42 52 62) in the second row is read. Left rotate by 1 bit, which is the number of underlined bits, and the result (02 12 22 32 42 52 62 72 )
To the original second line.

Read the data of the 3rd row ( 73 03 13 23 33 34 43 53 63) and rotate 1 bit to the left, and the result (03 13 23
33 43 53 63 73 ) on the original third line.

 The same applies to the 4th to 6th rows.

The data of the 7th row ( 57 67 77 07 17 27 37 47) is read out, and the number of underlined bits is 3-bit left rotate, and the result (07 17 27 37 47 57 67 77 ) is written to the 7th row.

Next, when the transposed matrix is made into the transposed matrix again by the transposed matrix creation means 52, the transposed matrix shown in FIG. The matrix shown in FIG. 6E is a matrix obtained by shifting the structure of FIG. 7A in the Y-axis direction for each column, and represents the rotation block 105. Next 13
A method of creating a transposed matrix will be described with reference to the drawings.

The image data storage means 521 stores image data. The conversion mode calculation means 522 stores N rows in the image data storage means 521.
When N columns of image data are stored, the number M of conversion modes is calculated by the following formula.

M = [log ₂ N] However, [] represents an integer when the internal numerical value is an integer, and a rounded up integer when the numerical value below the decimal point is included. After obtaining the number M of conversion modes, the value of the conversion mode L is changed from 1 to M.
Output up to.

The row selection means 523 changes the row number of N rows × N columns from 0 to N according to the value of the conversion mode L output from the conversion mode calculation means 522.
Assuming that the number is −1, the Ath row and the Bth row are determined from the Nth row by the following equation.

^{A = k * 2 L ~k *} 2 L +2 L-1 -1 B = A + 2 L-1 k = O~ (N / 2 L) -1 bit sequence of the A number of rows and B Ban row A (j ), B (j)
(Where j = 0 to N-1) is selected.

The image conversion means 524 inputs these A (j) and B (j),
A '(j) and B' (j) are calculated by the following formula.

A '(j) = A ( j) j = k * 2 L ~k * 2 L +2 L-1 -1 A' (j) = B (j-2 L-1) j = k * 2 L +2 L ^{-1 to} k * 2 ^L +2 ^L -1 B '(j) = B (j) j = k * 2 ^L +2 ^{L-1 to} k * 2 ^L +2 ^L -1 B' (j) = A (j + 2 ^{L -1) j = k * 2 L} ~k * 2 L +2 L-1 -1 k = O~ (N / 2 L) -1 Then, the image data a (j), B (j ) , respectively a '
(J), B '(j). This operation is conversion mode L
By changing from 1 to M, a matrix of N rows × N columns can be obtained. This matrix is the transposed matrix.

Many techniques have been published for obtaining the transposed matrix, and thus these methods may be used. Next, the second method of the rotation block generating means 5 will be described with reference to FIGS. 14 to 16.

FIG. 14 is a block diagram of the rotation block generating means 5. In the mask means 54, a portion abc in which the parallelogram C shown in FIG.
When the rotation block 105 is formed of N rows and N columns in a row bit arrangement parallel to the axis, each row of the parallelogram C formed of n + N rows is numbered 0 to n + N-1. Then
Create a mask matrix consisting of n + 1 rows x N columns, where the triangle abc part is 0 and the others are 1, and from the k rows of the parallelogram C to k +
The k'th row through the logical product of n + 1 rows × N columns up to n rows
Create the (k + n) 'th row. This will be described with reference to the specific example of FIG. In step 1 of FIG. 15, the leftmost matrix represents the parallelogram C of FIG. Rotating block
Reference numeral 105 is a matrix of 8 rows × 8 columns, and the triangular part abc is a matrix of 3 rows × 8 columns. Therefore, the mask matrix has 4 rows × 8 columns as shown in the mask 1 at the center. And this mask 1
Is applied to the 3rd to 7th rows of the parallelogram C in step 1, and a matrix of 4 rows × 8 columns is obtained in which 0 corresponds to the triangular portion as shown at the right end. .
The corrected row creating means 55 sets the (k + 1) 'th row obtained by the masking means 54 to the (k-1)' th corrected row (this is the kth'th row).
(Equal to row) masks the portion where the bit is not 0, sets this masked portion to 0 bit, and takes the logical sum of this masked row and the (k-1) 'th corrected row to the k'th corrected row Is calculated, and using this, the (k + n-1) '-corrected row is sequentially obtained, and this (k + n-1)'-corrected row is defined as k row, and 0
From the row to the (N-1) th row, a matrix of N rows x N columns is obtained.
This matrix becomes the rotation block 105.

Next, this will be specifically described with reference to FIGS. 15 and 16.

In step 2 of FIG. 15, the mask 2 is set to the (3-
1) 'is a corrected row, that is, a mask in which the non-zero bit in the 3'th row of the rightmost matrix of step 1 is 0 and the others are 1, and the result of masking this to the 4'th row is the matrix shown at the rightmost. Becomes In step 3, the logical sum of the (3-1) '-corrected row and the row obtained in step 2 is obtained, and the obtained row is the 3'-corrected row. In step 4, 3 '
The 5'th row is masked by the mask 3 in which the bit of the corrected row is not 0 and the other is 1, and the row thus obtained is ORed with the 3'corrected row in step 5 to obtain the 4 ' You will get the modified row. Then, in step 6, the 6'th row is masked by the mask 4 in which the portion of the 4'-corrected row whose bit is not 0 is 0 and the others are 1, and the row thus obtained is changed to the 4'-corrected row in step 7. If the logical sum is taken, the 5'corrected line is obtained.
This 5'-corrected row is the third row shown in step 1. By performing such an operation from 0 to N−1 rows of step 1, the matrix of 8 rows × 8 columns shown in step 8 is obtained,
This matrix is the rotation block 105.

The rotation block generation means 5 uses the second method when the number of bits rotated at one time is small or the rotation angle θ is small as a criterion for determining whether to use the first method or the second method. Method is faster, otherwise the first
This method can be executed faster.

EFFECTS OF THE INVENTION As is apparent from the above description, the present invention divides an original image into blocks of a predetermined size, and shifts, reduces, enlarges, replaces lines, rotates 90 degrees, rotates, etc., in units of lines for each block. By performing the above operation, it is possible to rapidly rotate the image at an arbitrary angle using a memory having a normal structure.

[Brief description of the drawings]

FIG. 1 is a diagram showing the principle of the present invention, FIG. 2 is an explanatory diagram of X-axis direction shifting means, and FIG. 3 is an explanatory diagram of X-axis direction reducing means.
FIG. 4 is an explanatory view of Y-axis direction enlarging means, FIG. 5 is a view showing a result of processing by means shown in FIGS. 2 to 4, and FIG. 6 is a square obtained by shifting a parallelogram in the Y-axis direction. Showing the first method, FIG. 7 shows the second method of shifting the parallelogram in the Y-axis direction to form a square, and FIG. 8 is a block diagram showing the configuration of the embodiment of the present invention. FIG. 9 is a diagram showing a concrete example of reduction in the X-axis direction by the X-axis direction reduction means, and FIG. 10 is Y
The figure which shows the specific example of the expansion of the Y-axis direction by the axial expansion means, FIG. 11 is a block diagram which shows the 1st apparatus of a rotation block preparation means, FIG. 12 shows the operation example of the apparatus shown in FIG. FIG. 13 is a block diagram showing the details of the transposed matrix creating means of FIG. 11, FIG. 14 is a block diagram showing a second device of the rotating block creating means, and FIGS. 15 and 16 are FIG. FIG. 6 is a diagram showing an operation example of the apparatus shown in FIG. 1 ... Reference block generating means, 2 ... X axis direction shifting means, 3 ... X axis direction reducing means, 4 ... Y axis direction expanding means, 5 ... Rotation block creating means, 51 ... Matrix creating means, 52 ... Transposed matrix creating means, 521 ... Image data storing means, 522 ... Conversion mode calculating means, 523 ... Row selecting means, 524 ... Image converting means, 553 ... Rotating means, 54
…… Mask means, 55 …… Corrected line creation means, 6 …… Movement means.

Claims (8)

(57) [Claims] 1. A memory for storing an original image, a calculating means for calculating a position of the original image corresponding to a rotated target image, and a writing means for writing the target image obtained by the calculating means in the memory. And having one vertex of the original image as a reference point, an axis perpendicular to the reference point as a reference coordinate axis, and N × N pixels each side of which is parallel to the axis obtained by rotating the original image by −θ with respect to the reference coordinate axis. Is represented as an aggregate of reference blocks each having a square shape, one of the vertices of each of the reference blocks is a rotation vertex, and the reference block is rotated by θ about the rotation vertex to create a rotation block, and the rotation of the rotation block is performed. The rotation block is rotated in the reference coordinate axis direction and the reference coordinates by the amount of movement in the reference coordinate axis direction and the direction perpendicular to the reference coordinate axis, which occurs when the apex is rotated about the reference point by θ. Any angle spinning method for the image, characterized in that to obtain a rotated image any angle θ by which to translate each perpendicular direction. 2. When creating the rotation block in which the reference block is rotated by θ, an axis passing through the rotation vertex and parallel to the reference coordinate axis is defined as a Y axis, and an axis orthogonal to the Y axis and passing through the rotation vertex is X. The x-axis and y-axis coordinates of the element that constitutes the reference block as an axis are (x, y) and the x of the element is
Coordinates are shifted in the X-axis direction so that they are xy * tanθ, and then multiplied by cosθ in the X-axis direction to obtain xcosθ-y * sinθ, and then y-coordinates are multiplied by Y / cosθ in the Y-axis direction to y / cosθ. By moving to the (xcos θ−y * sin θ, y / cos θ) coordinate, the reference block is moved to the X-axis, Y
A row of bits that has the same length as the axial direction and has a triangular shape in the Y-axis direction that forms a parallelogram with one protruding from the rotating block and the other indented and parallel to the X-axis in the protruding portion Shape of the rotating block by taking the logical sum of the read row bit sequence and the corresponding row bit sequence of the depressed triangular portion so that the protruding triangular portion overlaps the depressed triangular portion. A matrix consisting of N rows × N columns matching
The transposed matrix of the matrix of columns is obtained, and for each row of the transposed matrix, the bits of the part protruding in the triangular shape are arranged from the left end of the row toward the right end, and for the rows, the left rotation is equal to the number of protruding bits. To obtain the rotated image, calculate the transposed matrix of this rotated image,
The arbitrary-angle rotation method for an image according to claim 1, wherein the transposed matrix is used as the rotation block. 3. When obtaining the transposed matrix, the target matrix is N rows × N columns, and the number M of conversion modes of this matrix is M = [log ₂ N] (where [] is an integer whose integer is an integer. When that integer,
When the number after the decimal point is included, it is obtained by rounding up.), The N rows are numbered 0 to N-1, and the conversion mode L
For every (= 1 to M), the A-th row and the B-th row are A = k * 2 ^{L to} K * 2 ^L + 2 ^L-1 -1 B = A + 2 ^L-1 k = 0 to (N / 2 ^L ) -1 to obtain the row bit sequence of row A and row B as A
(J), expressed in B (j), A '( j), B' (j) the A '(j) = A ( j) j = k * 2 L ~K * 2 L +2 L-1 -1 A '(j) = B (j-2 ^L-1 ) j = k * 2 ^L + 2 ^{L-1 to} K * 2 ^L + 2 ^L- 1 B' (j) = B (j) j = k * 2 ^L +2 ^{L-1 to} K * 2 ^L +2 ^L -1 B '(j) = A (j + 2 ^L-1 ) j = k * 2 ^{L to} K * 2 ^L +2 ^L-1 -1 k = 0 to (N / 2 ^L ) −1, A (j) is A ′ (j) and B (j) is B ′.
3. An arbitrary angle of an image according to claim 2, wherein a matrix of N rows × N columns is obtained by converting into (j) and changing L from 1 to M, and this matrix is used as the transposed matrix. Rotation method. 4. When creating the rotation block from the reference block, an axis passing through the rotation vertex and parallel to the reference coordinate axis is defined as a Y axis, and an axis orthogonal to the Y axis is defined as an X axis and the reference is defined as the reference axis. The X axis of the elements that make up the block,
With the coordinate of the Y axis as (x, y), the x coordinate of the element is shifted in the X axis direction so as to be xy * tanθ, and further multiplied by cosθ in the X axis direction to obtain xcosθ−y * sinθ. By multiplying the y-coordinate by 1 / cosθ in the Y-axis direction and moving it to (xcosθ-y * sinθ, y / cosθ) coordinates as y / cosθ, the reference block is set to the X-axis and Y-axis lengths of the rotary block. When the triangle is formed in the same shape and protrudes downward from the rotation block in the Y-axis downward, and indents the upper side in a parallelogram, and when this triangle is formed by row bits arranged in parallel to the X-axis and formed by n rows, it is formed by n + N rows. Each of the rows of the parallelogram is numbered as 0 to n + N−1, and a mask matrix having n + 1 rows × N columns as the triangular depression range is set to 0 and the other is set to 1, and the 0th row is created. First, the 0'th row is obtained by the logical product of the 0th row to the nth row and the mask matrix.
The n'th row is created, and the n'th row is masked at the non-zero bit of the (n-2) '-corrected row to make the masked portion 0 bit, and the masked row and the (n- 2) 'The corrected line is ORed to make the (n-1)' corrected line,
The (n-1) 'th corrected row is set to the 0th row, and similarly, up to N-1 rows are obtained in the same manner to obtain a matrix of N rows x N columns, and this matrix is used as the rotation block. The method for rotating an arbitrary angle of an image according to claim 1. 5. A memory for storing an original image, a calculating means for calculating a position of the original image corresponding to the rotated target image, and a writing means for writing the target image obtained by the calculating means in the memory. And one vertex of the original image as a reference point, an axis perpendicular to this reference point as a reference coordinate axis, and a square of N × N pixels with one side parallel to the axis rotated −θ with respect to the reference image coordinate axis. A reference block generating means represented as an aggregate of reference blocks, and when one of the vertices of the reference block, which is the center of rotation, is used as a rotation vertex when the reference block is rotated by θ to create a rotation block,
An axis passing through this rotation vertex and parallel to the reference coordinate axis is defined as a Y-axis, an axis orthogonal to this and passing through the vertex is defined as an X-axis, and coordinates of X-axis and Y-axis of elements constituting the reference block are defined as x and y. , X-axis direction shift means for shifting the x-coordinate of the element in the X-axis direction to be xy * tan θ, X-axis direction reduction means for multiplying the output of the X-axis direction shift means by cos θ in the X-axis direction, y Y-axis direction enlarging means for multiplying the coordinates by 1 / cos θ, and a matrix forming a parallelogram having two sides parallel to the Y-axis direction formed by the outputs of the x-axis direction reducing means and the Y-axis direction enlarging means. A rotation block creating means for creating a rotation block by shifting each column in the Y-axis direction, and the rotation vertex of the rotation block is centered on a reference point on the reference coordinate axis which is a rotation center for rotating the original image. As the θ coordinate of the reference coordinate axis direction Momentum and calculates the amount of movement perpendicular to the reference coordinate axes, any angle spinning device of an image, characterized in that a moving means for moving the rotating block. 6. The rotating block creating means reads out a triangular portion protruding from the rotating block of the parallelogram for each row bit array parallel to the X axis, and the protruding triangular portion is depressed. So that the row bit sequence read out and the corresponding row bit sequence of the recessed triangular portion are ORed to create a matrix matching the shape of the rotation block, and each row of the matrix About Rotate Means to Rotate Rows About
And a transposed matrix creating means for creating a transposed matrix of a matrix,
The output of the matrix generation means is input to the transposed matrix generation means to output a transposed matrix, and the bits of the portion of the matrix protruding in the triangular shape for each row by the rotation means are arranged from the left end to the right end of the row. With respect to the rows that are lined up, the left rotation is performed by the number of the protruding bits, and the matrix thus created is input to the transposed matrix creating means to output the transposed matrix, and this matrix is used as the value of the rotation block. The apparatus for rotating an arbitrary angle of an image according to claim 5, wherein: 7. The transposed matrix creating means sets an image data storage means for storing image data and a conversion mode number M of N rows × N columns of image data as M = [log ² N] (where [] is internal If the numerical value of is an integer,
When a numerical value below the decimal point is included, it is obtained by rounding up the integer) and the conversion mode calculation means for outputting the conversion mode L (= 1 to M) and the N rows are 1 to N-1.
Numbered Mounting the A number rows and B number row than said N rows in accordance with the conversion mode ^{L, A = k * 2 L} ~K * 2 L +2 L-1 -1 B = A + 2 L-1 k = 0~ (N / 2 ^L) -1 by calculating the row bit sequence a of the a-th row and B-number row
(J), a row selection means for selecting B (j), and A
(J) and B (j) are input, and A ′ (j) and B ′ (j) are A ′ (j) = A (j) j = k * 2 ^{L to} K * 2 ^L +2 ^L-1 − 1 A '(j) = B (j-2 ^L-1 ) j = k * 2 ^L + 2 ^{L-1 to} K * 2 ^L + 2 ^L- 1 B' (j) = B (j) j = k * 2 ^L + 2 ^{L-1 to} K * 2 ^L + 2 ^L- 1 B '(j) = A (j + 2 ^L-1 ) j = k * 2 ^{L to} K * 2 ^L + 2 ^L-1 -1 k = 0 to (N / 2 ^L ) -1 to calculate A (j) of the image data into A '
(J) is an image conversion means for converting B (j) into B '(j), and changing this operation from L to 1 to M to obtain a matrix of N rows x N columns. The arbitrary angle rotation device for an image according to claim 6, wherein. 8. The rotating block forming means is a parallelogram in which the parallelogram is triangular from the rotating block and protrudes downward from the Y-axis in a downward direction of the Y-axis, and the upper side is indented, and the triangle is a bit array parallel to the X-axis. When formed by n rows, n
Each row of the parallelogram formed by + N rows is represented by 0 to n + N
-1 and a mask matrix having n + 1 rows × N columns, which is 0 in the range indented in the triangular shape and 1 in the other, and a logical product of n + 1 rows × N columns from k rows to k + n rows k '
A mask means for creating a row to the (k + n) 'th row;
The +1) 'th row is masked for the portion where the bit of the (k-1)' th corrected row is not 0, and this masked portion is set to 0 bit, and the masked row and the (k-1) 'th corrected row are ORed. And a correction row creating means for creating a k'th correction row, and when determining the kth row, the mask means determines the k'th row to the (k + n) 'row, and the correction row creating means determines the first row. From the K'corrected line, the (k + n-1) 'th corrected line is sequentially obtained,
This (k + n-1) 'modified row is the k-th row, and N is calculated from the 0th row.
6. The apparatus for rotating an arbitrary angle of an image according to claim 5, wherein a matrix of N rows × N columns is obtained by obtaining up to −1 row, and this matrix is used as a rotation block.