JPH0481231B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Application of the Invention] The present invention relates to an image rotation method and apparatus in digital image processing.

[Background of the invention]

Rotation is one of the basic processes in the field of image processing, such as correcting the tilt of an input document in facsimile, superimposing seal impressions in seal matching (for example, ``positioning of a seal pattern using the correlation of peripheral density with respect to the centroid''). "Matching Method", author Toru Kaneko et al., Institute of Electronics and Communication Engineers, IE81-13, pages 37-42
This is necessary for methods such as pages, etc.

Conventionally, typical methods of rotation include a method using affine transformation and a method using oblique axis transformation. The affine transformation method performs coordinate transformation using the formula X Y = cos θ sin θ - sin θ cos θx y (1). Here (x y)
are the coordinates in the original image, (X Y) are the rotated image (hereinafter,
(referred to as a rotated image), θ is the rotation angle.
Transformation (1) is the definition of rotational transformation in geometry itself, and does not cause distortion in the rotated image, but calculation of transformation (1) takes time. Therefore, this rotation method has the disadvantage that it is difficult to increase the speed. The method using oblique axis transformation approximates the affine transformation (1) of rotation by performing oblique axis transformation twice in the vertical and horizontal directions, and is described in "Image Rotation Method" (Japanese Patent Application Laid-Open No. 55-95145,
(Inventor Hitoshi Miyai) etc. Specifically, from the vertical oblique axis transformation x'y'=1 tanθ0 1x y...(2) and X Y=1 0-tanθ 1x'y'...(3), 1x y=1-tan ² θ tanθ-tanθ 1x y (4) Approximate transformation (1). Oblique axis transformations (2) and (3) are
Faster processing is possible than conversion (1). Therefore, this rotation method is faster than a method using affine transformation. However, as the rotation angle θ increases, the rotated image becomes distorted (for example, when θ=π/4, a square becomes a parallelogram with one vertex angle of π/4).

[Purpose of the invention]

SUMMARY OF THE INVENTION An object of the present invention is to eliminate the drawbacks of the conventional methods as described above, and to provide an image rotation method that is capable of high-speed processing and does not cause distortion in rotated images.

[Summary of the invention]

In order to achieve the above object, the present invention has been made based on the following idea.

Normally, when an image is stored in a memory for various processing, pixels that are continuous in the horizontal or vertical direction on the image are made to correspond to areas having continuous addresses on the memory. Particularly in the case of binary images, pixels that are continuous in the horizontal or vertical direction can usually be read and written as one word. The reason why it is difficult to increase the speed of the conventional affine conversion method is that even if the original image is read out in the order of pixels with consecutive addresses in the memory in the conversion (1), the converted image is generally stored in memory in units of one pixel. This is because the address must be written to a memory area that is not consecutive. On the other hand, the method using the oblique axis transformation can be speeded up by the transformation (2)
This is because in (3), the continuous area of the original image corresponds to the continuous area of the converted image, excluding some image boundaries. Therefore, especially when dealing with a binary image in which one word contains information for multiple pixels, affine transformation can only process one pixel unit and is inefficient, but oblique axis transformation can process one word unit. Yes, it is efficient. In this sense, conversion methods capable of high-speed processing include horizontal or vertical scaling conversion in addition to the above-mentioned oblique axis conversion.

The gist of the present invention is to focus on the fact that affine transformation 1 can be expressed by a combination of the above-mentioned oblique axis transformation and the above-mentioned scaling transformation, and to perform transformation (1) by sequentially performing these transformations. . Since the combined transformation is equivalent to the affine transformation (1), no distortion occurs in the transformed image. Each transformation used for combination can be processed at high speed as described above, and as a result, speeding up of rotation processing can be expected.

[Embodiments of the invention]

Hereinafter, the present invention will be explained in detail with reference to Examples.

For affine transformation (1) that represents rotation, as an example, The decomposition holds true. (However, -π/4θπ/4) Therefore, transformation (1) is vertical (y) direction oblique axis transformation x ₁ y ₁ = 1 tanθ0 1x y (6) Vertical direction reduction transformation x ₂ y ₂ = 1 00 cosθx ₁ y ₁ (7) Horizontal (x) direction expansion conversion This can be realized by sequentially executing four transformations: horizontal oblique axis transformation X Y=1 0-tanθ 1x ₃ y ₃ (9). There are other sets of oblique axis transformation and scaling transformation that are equivalent to transformation (1), but the minimum number of transformations is four as in the above example. The outline of conversions (6) to (9) is shown in FIG.

However, in the digital image targeted by the present invention, the density is defined only on the sampled coordinates, so interpolation is required to actually execute transformations (6) to (9). Here, the nearest neighbor point selection method (for example, "Computer-based Image Rotation Simulation", author Mr. Kageyama, 1981 National Conference of the Institute of Electronics and Communication Engineers, No. 1067) is used as the interpolation method. Conversions (6) to (9) are actually realized by the following steps. In the following explanation,
The unit of coordinates is the interval between the sample points above.

[Step 1] Apply transformation (6) to the integer values m and n, and x _1,n,o ,
Get y _1,n,o . That is, coordinate transformation is performed such that x _1,n,o y _1,n,o = 1 tanθ0 1m n .

Next, x _1,n,o and y _1,n,o are rounded off to integers, and the results are set as m1 and n1, respectively. (Interpolation processing).

Finally, the pixel density of the coordinates (m1 n1) of the converted image is
Let it be the pixel density at the coordinates (m n) of the image to be transformed.

[Step 2] Apply conversion (7) to the integer values m1 and n1,
Obtain x _2,n1,o1 and y _2,n1,o1 . That is, coordinate transformation is performed such that x _2,n1,o1 y _2,n1,o1 =1 00 cosθm1 n1.

Next, x _{2, n1, o1} and y _{2, n1, o1} are rounded off to integers, and the results are set as m2 and n2, respectively.

Finally, the pixel density at the coordinates (m2 n2) of the converted image is
Let it be the pixel density at the coordinates (m1 n1) of the image to be transformed.

[Step 3] Apply conversion (8) to the integer values m2 and n2,
Obtain x _3,n2,o2 and y _3,n2,o2 . i.e. Perform the coordinate transformation.

Next, x _3,n2,o2 and y _3,n2,o2 are rounded off to integers, and the results are set as m3 and n3, respectively.

Finally, the pixel density of the coordinates (m3 n3) of the converted image is
Let it be the density of the pixel at the coordinates (m2 n2) of the image to be transformed.

[Step 4] Apply conversion (9) to the integer values m3, n3, and obtain X _n3,o3 ,
Y get _n3,o3 . That is, coordinate transformation is performed as follows: X _n3,o3 Y _n3,o3 =1 0-tanθ 1m3 n3.

Next, X _n3,o3 and Y _n3,o3 are rounded off to integers, and the results are M and N, respectively.

Finally, the density of the pixel at the coordinates (M N) of the converted image is
Let it be the density of the pixel at the coordinates (m3 n3) of the image to be transformed.

The conversion in the above steps and the correspondence between the pixels of the converted image are shown in FIG. In the figure, 1 to 10 are pixel numbers, and pixels with the same number are corresponding pixels.

In steps 1 and 3 above, a set of pixels that are continuous in the vertical direction on the image to be converted appears as a set of pixels that are continuous in the vertical direction on the converted image. Also, in step 2 and step 4,
A set of pixels that are continuous in the horizontal direction on the converted image appears as is as a set of pixels that are continuous in the horizontal direction on the converted image. Therefore, not only is coordinate calculation simple, but especially when the target is a binary image, processing can be further speeded up by using a device that can read and write N vertically or horizontally continuous pixels as one word. An example of the configuration of an apparatus that satisfies this condition will be described below.

FIG. 3 shows the overall configuration of a device that implements the present invention. In the figure, 101 is a processing section consisting of a microprocessor or a microprogram control processor, 102 is a program memory for storing programs of the processing section 101 and numerical data such as tables;
103 is an image input device, 104 is an image output device,
105 is an image memory for storing image data; 10
6 indicates a bus for data, address and control signals.

Image memory 105 has the following functions.

(B-1) Simultaneously access N pixels that are continuous in the specified access direction (horizontal or vertical) with the specified pixel coordinates as the left end or top end. N here
indicates the data width (word length) of the data bus. 1
The correspondence between bits and pixels within a word is such that each end corresponds to an LSB ( LSB ) .

(B-2) The specified pixel coordinates in the above (B-1) are specified as horizontal and vertical two-dimensional addresses.

The following description will be made assuming that the word length N is 4 for the sake of simplicity. In order to realize the above (B-1), the image memory is composed of four memory modules so that four consecutive pixels in any horizontal or vertical direction are stored in different memory modules. ,
Associate pixels and memory modules. When defining the upper left of the image as the origin, the right horizontal direction as the x axis, and the lower vertical direction as the y axis, the memory module number μ that should store the pixel with coordinates (x, y) is μ = (x + y) 4 ( 10), the correspondence between the pixels and the memory module can be satisfied. Here, is an operation that takes the remainder of division. Also, if the address α in the memory module where a pixel with coordinates (x, y) is to be stored is α=mxy+[×/4] (11), then different pixels are in the same memory module and The correspondence between a pixel and an address within the memory module can be determined without determining the address within the memory module. Here, [ ] is converted into an integer by rounding down the decimal places, and m is a constant specific to the image memory where 4×m is the width of the image memory. FIG. 4a schematically shows the correspondence between pixels and memory module numbers according to equation (10), and FIG. 4b schematically shows the correspondence between pixels and addresses in the memory module according to equation (11). In the figure, 20
1 is a pixel with an x coordinate of 2 and a y coordinate of 3, and is stored at address 6 of the first memory module. however,
Let m be 2.

FIG. 5 shows the configuration of the image memory. In the figure, 30
1 to 303 are specified in function (B-1).
Registers that store pixel coordinates x coordinate, y coordinate, and access direction, respectively; 304 to 307 are 0th, 1st, 2nd, and 3rd memory modules, respectively; 308 to 311 are 0th, 1st, and 2nd memory modules, respectively. , an address generation unit that generates an address in the third memory module, 312 a routing unit that arranges the read data in the bit order described in function (B-1), and 313 the bit order described in function (B-1). This is a routing unit that arranges the data in the order in which it is distributed to predetermined memory modules.

Data reading and writing operations of image memory 105 are as follows. First, the x coordinate (hereinafter abbreviated as x ₀ ), y coordinate (hereinafter abbreviated as y ₀ ), and access direction (right, left, bottom, or top direction, hereinafter abbreviated as t) of the left or top pixel of the set of pixels to be accessed. , buses 106 and 320, 321, 3
22, registers 301 and 30, respectively.
2,303. Address generation unit 308~
311, when t=0 (access direction is right),
Coordinates (x ₀ , y ₀ ), (x ₀ +1, y ₀ ), (x ₀ +2, y ₀ ),
For (x ₀ +3, y ₀ ), when t = 1 (access direction is left), the coordinates (x ₀ , y ₀ ), (x ₀ -1, y ₀ ), (x ₀
-2, y ₀ ), (x ₀ -3, y ₀ ), when t=2 (access direction is down), the coordinates (x ₀ , y ₀ ) (x ₀ ,
y ₀ +1), (x ₀ , y ₀ +2), (x ₀ , y ₀ +3), when t=3 (access direction is up), the coordinates (x ₀ , y ₀ ), (x ₀ , y ₀ −1), (x ₀ , y ₀ −2), (x ₀ ,
y ₀ -3), an address within each memory module is generated using equations (10) and (11). When reading data, a read command is then issued to each memory module 304-307 using a signal 323. signal 32
3, predetermined data is read onto buses 324-327. The routing unit 312 uses the bus 324
Arrange the data of ~327 in the order shown in the correspondence between pixels and bits based on x ₀ and y ₀ ,
Output to bus 106 via bus 328. On the other hand, when writing data, the data to be written is sent from the data bus 106 to the routing section 313 via the bus 328. Next, write command to signal 3
23, the routing section 313 outputs the
Based on x ₀ , y ₀ , the data is arranged in the order shown in the correspondence between pixels and bits, and is sent to buses 329 to 333.
Output to. Finally, write command signal 323 writes data to memory modules 304-307 via buses 329-333, respectively.

Next, a procedure for realizing the rotation of the present invention using the above-described apparatus will be explained. The processing unit 101 executes a program stored in advance in a program memory. FIG. 6 is a schematic flowchart of this program. First, in an image input step, an image is input from the image input device 103. However, images that have been subjected to other processing or
It is also possible to target an image generated by program 1, and this step is omitted in this case. Next, perform transformations (6) to (9) in sequence to rotate the image. Finally, in an image output step, the image is output from the image output device 104. However, it is also possible to perform other processing on the rotated image, and in this case, this step is omitted.

7 to 10 are detailed flowcharts of the steps of conversion (6) to (9), respectively. Since each flowchart has a similar format, it will not be explained individually, but will be explained collectively below. First, the conversion to be processed and the pixel position of the converted image are initialized to the upper left pixel. Next, the access direction of the image memory, that is, the value of t, is set. Next, N pixels (N bits=1 word) are transferred from the current converted image pixel position to the current converted image pixel position in the current access direction. Next, the converted and converted image pixel positions are moved to the next N pixel positions on the same access direction line. After repeating the above for one line, the conversion and conversion target image pixel positions are moved to the beginning of the next line. The above steps are repeated for one image and the processing is completed.

According to this embodiment, although four conversions are required to perform rotation processing on a binary image, processing can be performed in units of N pixels (N is word length). Moreover, the processing of N pixels consists only of incrementing only one of the x and y coordinates, performing the conversion on the converted image, and actually transferring the data. On the other hand, in the conventional method using affine transformation, although the transformation is performed twice, it is necessary to increment both the x and y coordinates of the image to be transformed for each pixel. Therefore, the method according to the present invention has at least N
When N is 4 or more, the speed is high, and by increasing N, the speed can be further increased.
Regarding the image quality of the rotated image, the method of the present invention is equivalent to the method using affine transformation, and is therefore superior to the conventional method using oblique axis transformation.

Although an embodiment using hardware has been described above, the idea of the present invention can also be fully realized by software in a computer system, etc., and can be implemented in an information processing system that involves image and graphic processing.

〔Effect of the invention〕

As described above, according to the present invention, since rotational transformation can be performed by simply updating coordinate data, it is possible to obtain a rotated image of the same quality as the conventional method using affine transformation at a higher speed than before.

Furthermore, it can be realized in a wide variety of ways, from dedicated hardware devices to software, and is expected to be useful in a wide variety of fields.

[Brief explanation of drawings]

FIG. 1 is an explanatory diagram showing the principle of the present invention, FIG. 2 is an explanatory diagram explaining the rules of interpolation, FIG. 3 is an overall configuration diagram of an embodiment of an apparatus for realizing the present invention, and FIG.
5 is an explanatory diagram showing the correspondence between image memory and images in an embodiment of the present invention, FIG. 5 is a configuration diagram of the image memory, FIG. 6 is a schematic flow chart of a rotation program in an embodiment of the present invention, and FIG. Figures 1 through 10 are detailed flowcharts of each step of the rotation program. 101... Processing unit, 105... Image memory, 304
~307...Memory module, 308~311...
Address generation unit, 312, 313... Routing unit,... Vertical oblique axis conversion,... Vertical reduction conversion,...
Horizontal enlargement conversion, ...horizontal oblique axis conversion.

Claims (1)

[Claims] 1. An image rotation processing method in which two-dimensional original image data stored in a memory is processed by an image processing device and converted into an image rotated by an angle θ, wherein the original image is converted into an image rotated by an angle θ. a first oblique axis transformation processing step of converting the intermediate image into an intermediate image tilted at an angle θ in one axis direction;
an enlargement/reduction processing step of reducing the image by cosθ or its approximate magnification and converting it into an intermediate image enlarged by 1/cosθ or its approximate magnification in the direction of the other axis of the orthogonal coordinate system; and a second oblique axis transformation processing step for converting the intermediate image into an image tilted at an angle θ in the direction of the other axis of the orthogonal coordinate system, and the scaling processing step converts the intermediate image into an image tilted at an angle θ in the direction of the other axis of the orthogonal coordinate system. The process is divided into a reduction processing step to obtain an image and an enlargement processing step to obtain an image enlarged in the direction of the other axis. In each readout scanning line along the direction, the image data to be processed is sequentially read out in block units by predetermined pixels, and the image data in blocks is stored in a separate area of the memory according to the rotation angle θ and each scanning line. the address of each write scan line by the number of pixels determined by the position,
Alternatively, an image rotation method characterized in that each image conversion is performed by transferring pixel addresses in each writing scanning line in a shifted form. 2 an image memory for storing image data;
and a data processor that accesses the image data stored in the image memory in units of blocks consisting of a plurality of pixels having consecutive memory addresses, and the image memory is composed of a plurality of memories determined according to the size of the data block. a first register for storing a reference address of a data block to be accessed; and a second register for storing access direction instruction information indicating the relationship between the reference address and the data block.
a plurality of address generation means provided corresponding to the memory module and generating addresses in each memory module to be accessed according to the contents of the first and second registers; and a data array means connected between the data bus and the data bus, and the data processor selects the image to be read and written according to the rotation angle θ of the image and the content of the image processing to be performed. The vertical or horizontal scanning line of the image memory is determined, the reference address of the data block to be accessed is determined within each scanning line, and the reference address and access direction instruction information are transferred to the first and second data blocks of the image memory.
Image data transfer control for writing image data read out in blocks from one image area of the image memory onto the data bus to another image area of the image memory by sequentially applying data to a second register. a first oblique angle converting means for converting the image data into image data having an angle θ in one axis direction of the orthogonal coordinate system by repeating the block transfer operation of the image data by the transfer control means; Axis conversion processing,
Cosθ,
or an image reduction process that reduces the image by its approximate magnification;
The image data is 1/1 in the direction of the other axis of the orthogonal coordinate system.
An image enlargement process that enlarges the image by cosθ or its approximate magnification, and a second oblique axis conversion process that converts the enlarged or reduced image data into image data that is tilted at an angle θ in the direction of the other axis of the orthogonal coordinate system. An image processing apparatus characterized in that the above steps are sequentially executed, and the original image stored in the image memory is converted into an image rotated by an angle θ.