JPH0731727B2 - Image 90 degree rotation method - Google Patents

Description

Description: FIELD OF THE INVENTION The present invention relates to an image 90 ° rotation method for a binary image packed in word organization memory.

[Prior art]

As a method for obtaining a transposed image of an N × N binary image which is conventionally packed and stored in a memory N word consisting of 1 word N bits, the original image is constructed to produce transposed 1 word N pixels. Focusing on a certain bit position of a word to be extracted, one bit is extracted from each word, and N words are repeated. N
An example of the case of = 8 is shown in FIG. 90 of the image in FIG.
In order to rotate by .degree., One word is read out from the image of FIG. 10A one by one, and the pixel of the a-th bit is taken out bit by bit, and one word of the a-th row of FIG. Therefore, it is necessary to read the memory N ² times and write N times in order to obtain the image of FIG.

[Problems to be solved by the invention]

The conventional method has a problem in that since the memory is read N × N times and written N times, N × N + N accesses are required and the processing time is delayed.

[Means for Solving the Problems] According to the first invention, in an image 90-degree rotation method in an information processing apparatus having a memory capable of accessing word units composed of N = 2n bits, N × N of 2 is used. When the value image is stored in N words, if the n-j + 1 bit in the binary representation of the bit position of the N-bit word is 1, give 1 to the same bit position of the N-bit data M. And an operation of outputting N-bit mask data M by
(I + 1) >> Data A and B of two addresses obtained by j
Is read, and the data obtained by logically ORing the data obtained by shifting B∩ 2n ^- j bits to the left and A ∩ and the data obtained by shifting A ∩ M to the right by 2n ^- j bits and the B ∩M are obtained. Data is stored in (i + 1) >> j and i >> j, respectively (however, the bar above the symbol is a logical NOT, ∩ is a logical product, and ≫ in i >> j is i to the right by j bits). This is a symbol indicating a rotation shift (n-bit rotation).) The mask data M output operation is repeated n times with j = 1, ..., N, and the mask data M output operation is repeated for each time. Store operation i = 0,2,4,
… By repeating N / 2 times as N-2, 9 to the right
An image 90 degree rotation method is obtained which is characterized by obtaining an N × N binary image rotated 0 degrees.

According to the second aspect of the present invention, in a method of rotating an image 90 in an information processing apparatus having a memory capable of accessing a word unit composed of N = 2n bits, N × N binary images are stored in N words. At this time, if the (n−j + 1) th bit in the binary representation of the bit position of the N-bit word is 1, the N-bit mask data M which is obtained by giving 1 to the same bit position of the N-bit data M is output. Operation, i >> j,
(I + 1) >> Data A and B of two addresses obtained by j
Is read, and the data obtained by logically ORing the data obtained by shifting A∩ 2n ^- j bits to the left and B ∩ and the data obtained by shifting B ∩ M to the right by 2n ^- j bits and the A ∩M are obtained. Data is stored in i >> j and (i + 1) >> j, respectively (however, the bar above the symbol is logical negation, ∩ is logical product, >> in i >> j is i to the right by j bits). This is a symbol indicating a rotation shift (n-bit rotation).) The mask data M output operation is repeated n times with j = 1, ..., N, and the mask data M output operation is repeated for each time. Store operation i = 0,2,4,
…, N-2 is repeated N / 2 times, and leftward 9
An image 90 degree rotation method is obtained which is characterized by obtaining an N × N binary image rotated 0 degrees.

[Examples] The present invention will be described with reference to the drawings. Figure 1 is the first
FIG. 3 is a block diagram showing an embodiment of the present invention. In this example, n = 4, that is, N = 16, for simplification of description.

A 16 × 16 binary image is stored in the memory as 16 words, and each word consists of data for 16 horizontal pixels of the image. The partial replacement of the corresponding words in this case is divided into four stages. In the first stage, a pair of words, that is, 8 pairs stored in 8 pairs of address 0 and address 8, address 1 and address 9, ..., Address 7 and address F, as shown in FIG. Partial replacement as shown in FIG. A in Fig. 1 (b),
B indicates paired data.

For partial replacement, j = 1 in the first stage, and the bit position of the mask consisting of 16 bits (the rightmost bit is 0th
When expressed in binary (as a bit), a mask M = (111111) in which 1 is given to a bit position where the n-j + 1th bit is 1.
1100000000). Similarly, the mask data in the second stage is M = (1111000011110000), the mask data in the third stage is M = (1100110011001100), and the mask data in the fourth stage is M = (1010101010).
101010). The paired addresses are i >> j, (i +
1) >> j (where i >> j indicates that i is rotated shifted right by j bits (n-bit rotation))
Then, when j = 1,2,3,4 and i = 0,2,4, ... 14, the address of the word forming a pair in the first stage is obtained.

The word address paired in each stage is shown in FIG.
It is shown in (c), (e) and (g). Partial replacement of corresponding words is shown in FIGS. 1 (b), (d), (f) and (h).

Explaining the first stage, for the data A and B read at the address of the word to be paired, the lower 8 bits of B are set to the upper 8 bits of B, the upper 8 bits of B are set to the upper 8 bits of A, and A The operation of replacing the upper 8 bits of A with the lower 8 bits of A and the lower 8 bits of A with the lower 8 bits of B is performed on the eight pair words. Similarly, in the second, third and fourth stages, the partial replacement is made in small increments as shown in FIG. 1 (d),
Partial replacement is performed as shown in (f) and (h).

The operations for partial replacement shown in FIGS. 1 (b), (d), (f), and (h) are performed by using the mask data M and FIG. 1 (a),
For paired data A and B shown in (c), (e), and (g), B∩ is left-shifted by 2n ^- j bits and data is logically ORed with A∩, and A∩M. 2n ^- j bits are right-shifted and B∩M is ORed.

The (X, Y) coordinates of each pixel are 2 bits of 4 bits (x _{0 to} x ₃ , y _{0 to} y ₃ ).
In terms of the coordinates (x ₃ x ₂ x ₁ x ₀ , y ₃ y ₂ y ₁ y ₀ ), the partial replacement operation is (x ₃ x ₂ x ₁ x ₀ , y ₃ y ₂ at the first stage. y ₁ y
₀₎ pixel coordinate position _{(y 3 x 2 x 1 x} 0, 3 y 2 y 1 y 0 ) to the coordinate position, in the second stage _{(y 3 x 2 x 1 x} 0, 3 y 2 y 1 y 0 ) The pixel at the coordinate position is moved to the (y ₃ y ₂ x ₁ x ₀ , _{3 2} y ₁ y ₀ ) coordinate position, and the (y ₃ y ₂ x ₁ x ₀ , _{3 2} y ₁ y ₀ ) coordinate position is set on the third stage. pixel to the _{(y 3 y 2 y 1 x} 0, 3 2 1 y 0) coordinates, in the fourth stage the pixel coordinate position _{(y 3 y 2 y 1 x} 0, 3 2 1 y 0) ( It corresponds to moving to the y ₃ y ₂ y ₁ y ₀ , _{3 2 1 0} ) coordinate position, and thereby a 90-degree rotated image is obtained.

FIG. 3 is a diagram showing how a particular pixel moves by the operation of FIG.
The pixels at the (0011,0010) coordinate position in the second, third, and fourth stages are (0011,1010), (0011,1110), (0011,1100),
It is shown that it moves in the order of (0010,1100).

Further, in the case of a 90-degree rotated image of an image larger than 16 × 16, for example, when transposing a 64 × 64 image, as shown in FIG. The method of the present invention is applied to a partial image, and then the partial image is replaced with the partial image at the target position, which can be easily applied to the 90-degree rotated image processing of a larger image.

FIG. 2 is a block diagram showing an embodiment of the second invention. In this example, n = 4, that is, N = 16, for simplification of description.

A 16 × 16 binary image is stored in the memory as 16 words, each word consisting of data for one horizontal pixel of the image. The partial replacement of the corresponding words in this case is divided into four stages. In the first stage, words to be paired, that is, as shown in FIG. 7A, stored in eight pairs of address 0 and address 8, address 1 and address 9, ..., Address 7 and address F 8 Partial replacement as shown in FIG. 2B is performed on the paired data. A in FIG. 2 (b),
B indicates paired data.

For partial replacement, j = 1 in the first stage, and the bit position of the mask consisting of 16 bits (the rightmost bit is 0th
When expressed in binary (as a bit), a mask M = (111111) in which 1 is given to a bit position where the n-j + 1th bit is 1.
1100000000). Similarly, the mask data in the second stage is M = (1111000011110000), the mask data in the third stage is M = (1100110011001100), and the mask data in the fourth stage is M = (1010101010).
101010). The address to be paired is i >> j, (i
+1) >> j (where i >> j indicates that i is rotated and shifted right by j bits (n-bit rotation)), j = 1,2,3,4, i = 0,2, When 4, ... 14, the address of the word forming the pair in the first stage of FIG. 1 is obtained.

The word address paired in each stage is shown in FIG.
It is shown in (c), (e) and (g). The partial replacement of corresponding words is shown in FIGS. 2 (b), (d), (f) and (h).

Explaining the first stage, for the data A and B read at the address of the word to be paired, the lower 8 bits of B are set to the lower 8 bits of A, the lower 8 bits of A are set to the upper 8 bits of A, and A The operation of replacing the upper 8 bits of B with the upper 8 bits of B and the upper 8 bits of B with the lower 8 bits of B is performed on the eight pair words. Similarly, in the second, third, and fourth stages, partial replacement is performed in small increments, and the steps are shown in FIGS. 2 (b), (d), (f),
Partial replacement is performed as shown in (h).

The operations for partial replacement shown in FIGS. 2 (b), (d), (f), and (h) are performed with the mask data M and FIGS. 2 (a), (c),
For the paired data A and B shown in (e) and (g), A∩
2n ^- j bits left-shifted data and B ∩ are ORed, and B ∩ M is 2n ^- j bits right-shifted data and A ∩ M is ORed. Corresponding to.

The (X, Y) coordinates of each pixel are 2 bits of 4 bits (x _{0 to} x ₃ , y _{0 to} y ₃ ).
In terms of the coordinates expressed in binary (x ₃ x ₂ x ₁ x ₀ , y ₃ y ₂ y ₁ y ₀ ), the partial replacement operation is (x ₃ x ₂ x ₁ x ₀ , y ₃ y in the first stage. ₂ y
₁ y ₀₎ of the pixel at the coordinate position (to _{3 x 2 x 1 x 0,} x 3 y 2 y 1 y 0) coordinates, in the second stage _{(3 x 2 x 1 x 0} , x 3 y 2 y 1 The pixel at the y ₀ ) coordinate position to the ( _{3 2} x ₁ x ₀ , x ₃ x ₂ y ₁ y ₀ ) coordinate position
The pixel at the ( _{3 2} x ₁ x ₀ , x ₃ x ₂ y ₁ y ₀ ) coordinate position is moved to the ( _{3 2 1} x ₀ , x ₃ x ₂ x ₁ y ₀ ) coordinate position on the stage, and ( ₃ This corresponds to moving the pixel at the coordinate position of _{2 1} x ₀ , x ₃ x ₂ x ₁ y ₀ ) to the ( _{3 2 1 0} , x ₃ x ₂ x ₁ x ₀ ) coordinate position. A rotated image is obtained.

FIG. 5 is a diagram showing how a specific pixel moves by the operation of FIG.
In the second, third and fourth stages, the pixel at the (0011,0010) coordinate position is (1011,0010), (1111,0010), (1101,0010),
It is shown that it moves in the order of (1101,0011).

In the example of N = 16, the memory access is 16 because the memory is read and written 16 times in each stage in the process of 4 stages.
It becomes x2x4. Generally, when N = 2n, the memory is accessed 2N times in each stage in the processing of n stages, so that the total is 2Nlog ₂ N times.

〔The invention's effect〕

According to the present invention, a 90 ° rotated image of an N × N binary image can be processed with 2NlogN memory accesses.
The memory access time can be reduced by N + 1 / 2logN times.

[Brief description of drawings]

FIG. 1 is a block diagram showing the principle of the first invention, FIG. 2 is a block diagram showing the principle of the second invention, and FIG.
FIG. 4 is a diagram showing how a specific pixel moves when the method shown in FIG. 4 is used, FIG. 4 is a diagram showing a second embodiment of the present invention, and FIG. 5 is a diagram showing the method shown in FIG. FIG. 6 is a block diagram of a conventional example showing a state in which a specific pixel moves when used. A, B ... Paired data.

Claims (2)

[Claims] 1. A method of rotating an image by 90 degrees in an information processing apparatus having a memory capable of accessing a word unit composed of N = 2n bits, where N × N binary images are stored in N words. N in the binary representation of the bit position of the word of bits
-If the j + 1th bit is 1, an operation of outputting N-bit mask data M by giving 1 to the same bit position of N-bit data M, i >> j, (i + 1)
>> Read the data A and B at the two addresses obtained at j, and shift the B ∩ by 2n ^- j bits to the left and the logical OR of the data and A ∩, and shift the A ∩ M to the 2n ^- j bits to the right. Data and the data obtained by ORing B∩M,
Each has an operation of storing in (i + 1) >> j and i >> j (however, the bar above the symbol is a logical NOT, ∩ is a logical product,
i >> j is a symbol indicating that i is rotated shifted right by j bits (n-bit rotation). ) The mask data M output operation is repeated n times with j = 1, ..., N, and the data storage operation is performed i = 0, 2, 4, ..., N for each mask data M output operation.
Image 90 characterized by obtaining N × N binary image rotated 90 degrees to the right by repeating N / 2 times as -2
Degree rotation method. 2. A method of rotating an image by 90 degrees in an information processing apparatus having a memory capable of accessing a word unit composed of N = 2n bits, where N × N binary images are stored in N words. N in the binary representation of the bit position of the word of bits
-If the j + 1th bit is 1, an operation of outputting N-bit mask data M by giving 1 to the same bit position of N-bit data M, i >> j, (i + 1)
>> Read the data A and B at the two addresses obtained in j and shift the A∩ by 2n ^- j bits to the left and the logical OR of B∩ and B∩M by the 2n ^- j bits to the right. Data and the data obtained by the logical sum of A∩M,
Each has an operation of storing in i >> j and (i + 1) >> j, (however, the bar above the symbol is a logical NOT, ∩ is a logical product,
i >> j is a symbol indicating that i is rotated shifted right by j bits (n-bit rotation). ) The mask data M output operation is repeated n times with j = 1, ..., N, and the data storage operation is performed i = 0, 2, 4, ..., N for each mask data M output operation.
Image 90 characterized by obtaining N × N binary image rotated 90 degrees to the left by repeatedly operating N / 2 times as -2
Degree rotation method.