Method and apparatus for rotating an image

• US 5,412,768 A
• Filed: 04/13/1994
• Issued: 05/02/1995
• Est. Priority Date: 01/22/1990
• Status: Expired due to Fees

• Current Assignee: Matsushita Graphic Communication Systems, Inc. (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Graphic Communication Systems, Inc. (Panasonic Holdings Corporation)
• Inventors: Ozaki, Yutaka
• Primary Examiner(s): Nguyen, Phu K.
• Application Number:
  US08/227,088
• Time in Patent Office: 384 Days
• Field of Search: 395/133, 395/137, 395/138, 395/155, 395/161, 395/162, 395/164, 382/44, 382/46, 345/121, 345/126
• US Class Current: 345/585
• CPC Class Codes: G06T 3/602 by block rotation, e.g. by recursive reversal or rotation

Abstract

In a method and an an apparatus for rotating a source image about a reference point on a reference coordinate axis through an arbitrary angle θ to obtain a destination image, the source image is represented by a group of reference blocks. Each of the reference blocks has N×N pixels and is composed of a square having a side parallel to an axis which is rotated relative to the reference coordinate axis by an angle of ×θ. One of vertexes of each of the reference blocks is defined as a rotation center vertex. Each of the reference blocks is rotated about the rotation center vertex by an angle of θ to obtain a rotation block. Calculations are made on shift quantities ΔY and ΔX of the rotation center vertex of each of the rotation blocks. The shift quantities ΔY and ΔX result from a rotation of the rotation center vertex about the reference point through an angle of θ. The shift quantity ΔY is defined as extending along the reference coordinate axis, and the shift quantity ΔX is defined as extending perpendicular to the reference coordinate axis. The rotation block is translated in a direction of the reference coordinate axis by the shift quantity ΔY, and is translated in a direction perpendicular to the reference coordinate axis by the shift quantity ΔX to obtain the destination image.

Claims

1. A method of rotating a reproduced video image by an apparatus including a central processing unit (cpu), a main memory, an image storing memory for storing image data in rows, a plurality of input latches, a plurality of output latches, a data conversion circuit, an exchange circuit, a row order change circuit and a selection circuit with said plurality of input latches connected to said cpu, said main memory and said image storing memory, said data conversion circuit connected between a predetermined number of input latches and output latches, said exchange circuit and said row order change circuit connected between an input latch and an output latch, and said selection circuit connected to said predetermined number of output latches connected to said data conversion circuit, comprising the steps of:

calculating a conversion mode number M with respect to image data of N rows×

N columns by referring to an equation expressed as;

M=[log₂ N] where N is a power of 2 and when a numeral within a bracket "[ ]" is equal to an integer, the bracket denotes the integer; and

when a numeral within the bracket contains a fraction, the bracket denotes an integer which is obtained by counting the fraction as one, said step of calculating a conversion including a step of reading out the N rows of image data from the image storing memory;

numbering the N rows by 0˜

N-1 and transferring the rows to the plurality of input latches;

calculating rows having numbers A and B for each of conversion modes L (=1˜

M) by referring to equations expressed as;

space="preserve" listing-type="equation">A=k*2.sup.L ˜

k*2.sup.L +2.sup.L-1 -1

space="preserve" listing-type="equation">B=A+2.sup.L-1

space="preserve" listing-type="equation">k=0˜

(N/2.sup.L)-1

where a character "*" denotes an operator of product;

representing row bit arrangements of the rows having the numbers A and B by A(j) and B(j) respectively;

converting the row bit arrangements A(j) and B(j) into bit arrangements A'"'"'(j) and B'"'"'(j) with said data conversion circuit by referring to equations expressed as;

##EQU7## latching the row data obtained by the step of converting in said plurality of output latches;

writing the latched row data into said image storing memory via said selection circuit;

varying L from 1 to M and thereby deriving conversion image data of N rows×

N columns;

representing bit arrangements of rows of the conversion image data by E(j); and

converting the bit arrangements of the rows of the conversion image data by referring to equations expressed as;

space="preserve" listing-type="equation">F(j)=E(N-j-1), j=0˜

N-1

where F(j) denotes rows composing 90-degree clockwise-rotated image data of N rows×

N columns.

2. A method of rotating a reproduced video image by an apparatus including a central processing unit (cpu), a main memory, an image storing memory for storing image data in rows, a plurality of input latches, a plurality of output latches, a data conversion circuit, an exchange circuit, a row order change circuit and a selection circuit with said plurality of input latches connected to said cpu, said main memory and said image storing memory, said data conversion circuit connected between a predetermined number of input latches and output latches, said exchange circuit and said row order change circuit connected between an input latch and an output latch, and said selection circuit connected to said predetermined number of output latches connected to said data conversion circuit, comprising the steps of:

calculating a conversion mode number M with respect to image data of N rows×

N columns by referring to an equation expressed as;

M=[log₂ N] where when a numeral within a bracket "[ ]" is equal to an integer, the bracket denotes the integer; and

when a numeral within the bracket contains a fraction, the bracket denotes an integer which is obtained by counting the fraction as one, said step of calculating a conversion including a step of reading out the N rows of image data from the image storing memory;

numbering the N rows by 0˜

N-1 and transferring the rows to the plurality of input latches;

calculating rows having numbers A and B for each of conversion modes L (=1˜

M) by referring to equations expressed as;

space="preserve" listing-type="equation">A=k*2.sup.L ˜

k*2.sup.L +2.sup.L-1 -1

space="preserve" listing-type="equation">B=A+2.sup.L-1

space="preserve" listing-type="equation">k=0˜

(N/2.sup.L)-1

where a character "*" denotes an operator of product;

representing row bit arrangements of the rows having the number A and B by A(j) and B(j) respectively;

converting the row bit arrangements A(j) and B(j) into bit arrangements A'"'"'(j) and B'"'"'(j) by referring to equations expressed as;

##EQU8## latching the row data obtained by the step of converting in said plurality of output latches;

writing the latched row data into said image storing memory via said selection circuit;

varying L from 1 to M and thereby deriving conversion image data of N rows×

N columns;

representing an "i" row of the conversion image data by E(i,j); and

changing the rows of the conversion image data by referring to equations expressed as;

space="preserve" listing-type="equation">E'"'"'(i,j)=E(N-i-1,j), i=0˜

N-1

where E'"'"'(i,j) denotes rows composing 90-degree counterclockwise-rotated image data of N rows×

N columns.

3. An apparatus for rotating a reproduced video image through 90 degrees, comprising:

a central processing unit (CPU);

a main memory;

an image storing memory;

a plurality of input latches;

a plurality of output latches;

a data conversion circuit;

an exchange circuit;

a row order change circuit; and

a selection circuit, said plurality of input latches connected to said CPU, said main memory and said image storing memory, said data conversion circuit connected between a predetermined number of input latches and output latches, said exchange circuit and said row order change circuit connected between an input latch and an output latch, and said selection circuit connected to said predetermined number of output latches connected to said data conversion circuit;

wherein

said CPU includes means for calculating a conversion mode number M with respect to image data of N rows×

N columns by referring to an equation expressed as;

M=[log₂ N] where when a numeral within a bracket "[ ]" is equal to an integer, the bracket denotes the integer; and

when a numeral within the bracket contains a fraction, the bracket denotes an integer which is obtained by counting the fraction as one,

means for numbering the N rows by 0˜

N-1, and

means for calculating rows having numbers A and B for each of conversion modes L (=1˜

M) by referring to equations expressed as;

space="preserve" listing-type="equation">A=k*2.sup.L ˜

k*2.sup.L +2.sup.L-1 -1

space="preserve" listing-type="equation">B=A+2.sup.L-1

space="preserve" listing-type="equation">k=0˜

(N/2.sup.L)-1

where a character "*" denotes an operator of product;

said data conversion circuit includes means for representing row bit arrangements of the rows having the numbers A and B by A(j) and B(j) respectively;

means for converting the row bit arrangements A(j) and B(j) into bit arrangements A'"'"'(j) and B'"'"'(j) by referring to equations expressed as;

##EQU9## said CPU varying L from 1 to M and thereby deriving conversion image data of N rows×

N columns;

said exchange circuit includes means for representing bit arrangements of rows of the conversion image data by E(j), and

means for converting the bit arrangements of the rows of the conversion image data by referring to equations expressed as;

space="preserve" listing-type="equation">F(j)=E(N-j-1), j=0˜

N-1

where F(j) denotes rows composing 90-degree clockwise-rotated image data of N rows×

N columns; and

said row order change circuit includes means for representing an "i" row of the conversion image data by E(i,j), and

means for changing the rows of the conversion image data by referring to equations expressed as;

space="preserve" listing-type="equation">E'"'"'(i,j)=E(N-i-1,j), i=0˜

N-1

where E'"'"'(i,j) denotes rows composing 90-degree counterclockwise-rotated image data of N rows×

N columns.

4. A method of rotating a reproduced video image by an apparatus including a central processing unit (cpu), a main memory, an image storing memory, a plurality of input latches, a plurality of output latches, a data conversion circuit, an exchange circuit, a row order change circuit and a selection circuit with said plurality of input latches connected to said cpu, said main memory and said image storing memory, said data conversion circuit connected between a predetermined number of input latches and output latches, said exchange circuit and said row order change circuit connected between an input latch and an output latch, and said selection circuit connected to said predetermined number of output latches connected to said data conversion circuit, comprising the steps of:

representing the source image by a group of reference blocks, wherein each of the reference blocks has N×

N pixels and is composed of a square having a side parallel to an axis which is rotated relative to the reference coordinate axis by an angle of -θ

;

defining one of vertexes of each of the reference blocks as a rotation center vertex;

rotating each of the reference blocks about the rotation center vertex by an angle of θ

to obtain a rotation block;

calculating shift quantities Δ

Y and Δ

X of the rotation center vertex of each of the rotation blocks, wherein the shift quantities Δ

Y and Δ

X result from a rotation of the rotation center vertex about the reference point through an angle of θ

, and wherein the shift quantity Δ

Y is defined as extending along the reference coordinate axis and the shift quantity Δ

X is defined as extending perpendicular to the reference coordinate axis; and

translating the rotation block in a direction of the reference coordinate axis by the shift quantity Δ

Y and translating the rotation block in a direction perpendicular to the reference coordinate axis by the shift quantity Δ

X o obtain the destination image.

5. The method of claim 4 further comprising the steps of:

setting a Y axis equal to an axis which passes through the rotation center vertex and which extends parallel to the reference coordinate axis;

setting an X axis equal to an axis which passes through the rotation center vertex and which extends perpendicular to the Y axis;

representing an X axis coordinate and a Y axis coordinate of each of elements composing the reference block by (x,y);

shifting the element in a direction of the X axis so that the x coordinate of the element will be equal to a value given as;

space="preserve" listing-type="equation">x-y* tan θ

where a character "*" denotes an operator of product;

multiplying the x coordinate of the element by cos θ

so that the x coordinate will be equal to a value given as;

space="preserve" listing-type="equation">x* cos θ

-y* sin θ

multiplying the y coordinate of the element by 1/cos θ

so that the y coordinate will be equal to a value given as;

space="preserve" listing-type="equation">y/cos θ

whereby the element having the coordinate (x,y) is shifted to the coordinate (x* cos θ

-y* sin θ

, y/cos θ

);

transforming the reference block into a parallelogram by the shift of the elements, wherein the parallelogram is equal to the rotation block in lengths of directions of the X axis and the Y axis, and wherein the parallelogram has a first triangular part and a second triangular part extending outward and inward of the rotation block respectively;

reading out each of row bit arrangements parallel to the X axis with respect to the first triangular part;

executing an OR operation between the readout row bit arrangements and corresponding row bit arrangements of the second triangular part so that the first triangular part will match to the second triangular part to obtain a matrix of N rows×

N columns which has a shape corresponding to a shape of the rotation block;

deriving a first transposed matrix with respect to the matrix of N rows×

N columns;

with respect to each of rows of the first transposed matrix where bits of the first triangular part are arranged from a left-hand end toward a right-hand end of the row, executing a left rotation of the row by a number of the bits of the first triangular part to obtain a rotation image;

deriving a second transposed matrix with respect to the rotation image; and

using the second transposed matrix as the rotation block.

6. The method of claim 5 wherein each of the first and second transposed matrix deriving steps comprises:

calculating a conversion mode number M with respect to the matrix of N rows×

N columns by referring to an equation expressed as;

M=[log₂ N] where when a numeral within a bracket "[ ]" is equal to an integer, the bracket denotes the integer; and

when a numeral within the bracket contains a fraction, the bracket denotes an integer which is obtained by counting the fraction as one;

numbering the N rows by 0˜

N-1;

calculating rows having numbers A and B for each of conversion modes L (=1˜

M) by referring to equations expressed as;

space="preserve" listing-type="equation">A=k*2.sup.L ˜

k*2.sup.L +2.sup.L-1 -1

space="preserve" listing-type="equation">B=A+2.sup.L-1

space="preserve" listing-type="equation">k=0˜

(N/2.sup.L)-1

where a character "*" denotes an operator of product;

representing row bit arrangements of the rows having the numbers A and B by A(j) and B(j) respectively;

converting the row bit arrangements A(j) and B(j) into bit arrangements A'"'"'(j) and B'"'"'(j) by referring to equations expressed as;

##EQU10## varying L from 1 to M and thereby deriving a matrix of N rows×

N columns which is used as the transposed matrix.

7. The method of claim 4 further comprising the steps of:

setting a Y axis equal to an axis which passes through the rotation center vertex and which extends parallel to the reference coordinate axis;

setting an X axis equal to an axis which passes through the rotation center vertex and which extends perpendicular to the Y axis;

representing an X axis coordinate and a Y axis coordinate of each of elements composing the reference block by (x,y);

shifting the element in a direction of the X axis so that the x coordinate of the element will be equal to a value given as;

space="preserve" listing-type="equation">x-y* tan θ

where a character "*" denotes an operator of product;

multiplying the x coordinate of the element by cos θ

so that the x coordinate will be equal to a value given as;

space="preserve" listing-type="equation">x* cos θ

-y* sin θ

multiplying the y coordinate of the element by 1/cos θ

so that the y coordinate will be equal to a value given as;

space="preserve" listing-type="equation">y/cos θ

whereby the element having the coordinate (x,y) is shifted to the coordinate (x* cos θ

-y* sin θ

, y/cos θ

);

transforming the reference block into a parallelogram by the shift of the elements, wherein the parallelogram are equal to the rotation block in lengths of directions of the X axis and the Y axis, wherein the parallelogram has a first triangular part and a second triangular part extending outward and inward of the rotation block respectively, and wherein the first triangular part is composed of an n number of row bit arrangements parallel to the X axis;

numbering rows of the parallelogram of n+N rows by 0˜

n+n-1;

generating a mask matrix divided into a first region and a second region, wherein the first region corresponds to the second triangular part and is "0", and wherein the second region is "1";

executing an AND operation between the "0" row˜

the "n" row and the mask matrix to generate a "0'"'"'" row˜

an "n'"'"'" row;

masking a part of the "1'"'"'" row which corresponds to a part of the "0'"'"'" row where bits differ from "0", and setting the masked part equal to "0";

executing an OR operation between the masked row and the "0'"'"'" row to generate a revised "0'"'"'" row;

masking a part of the "2'"'"'" row which corresponds to a part of the revised "0'"'"'" row where bits differ from "0", and setting the masked part equal to "0";

executing an OR operation between the masked row and the revised "0'"'"'" row to generate a revised "1'"'"'" row;

masking a part of the "3'"'"'" row which corresponds to a part of the revised "1'"'"'" row where bits differ from "0", and setting the masked part equal to "0";

executing an OR operation between the masked row and the revised "1'"'"'" row to generate a revised "2'"'"'" row;

similarly masking a part of the "n'"'"'" row which corresponds to a part of the revised "(n-2)'"'"'" row where bits differ from "0", and setting the masked part equal to "0";

similarly executing an OR operation between the masked row and the revised "(n-2)'"'"'" row to generate a revised "(n-1)'"'"'" row;

setting the revised "(n-1)'"'"'" row as a "0" row; and

deriving subsequent rows up to an N-1 row by similar steps to obtain a matrix of N rows×

N columns which is used as the rotation block.

8. An apparatus for rotating a source video image about a reference point on a reference coordinate axis through an arbitrary angle θ

to obtain a destination video image, comprising;

means for representing the source image by a group of reference blocks, wherein each of the reference blocks has N×

N pixels and is composed of a square having a side parallel to an axis which is rotated relative to the reference coordinate axis by an angle of -θ

;

means for defining one of vertexes of each of the reference blocks as a rotation center vertex;

means for rotating each of the reference blocks about the rotation center vertex by an angle of θ

to obtain a rotation block;

means for calculating shift quantities Δ

Y and Δ

X of the rotation center vertex of each of the rotation blocks, wherein the shift quantities Δ

Y and Δ

X result from a rotation of the rotation center vertex about the reference point through an angle of θ

, and wherein the shift quantity Δ

Y is defined as extending along the reference coordinate axis and the shift quantity Δ

X is defined as extending perpendicular to the reference coordinate axis; and

means for translating the rotation block in a direction of the reference coordinate axis by the shift quantity Δ

Y and translating the rotation block in a direction perpendicular to the reference coordinate axis by the shift quantity Δ

X to obtain the destination image.

9. The apparatus of claim 8 further comprising:

means for setting a Y axis equal to an axis which passes through the rotation center vertex and which extends parallel to the reference coordinate axis;

means for setting an X axis equal to an axis which passes through the rotation center vertex and which extends perpendicular to the Y axis;

means for representing an X axis coordinate and a Y axis coordinate of each of elements composing the reference block by (x,y);

means for shifting the element in a direction of the X axis so that the x coordinate of the element will be equal to a value given as;

space="preserve" listing-type="equation">x-y* tan θ

where a character "*" denotes an operator of product;

means for multiplying the x coordinate of the element by cos θ

so that the x coordinate will be equal to a value given as;

space="preserve" listing-type="equation">x* cos θ

-y* sin θ

means for multiplying the y coordinate of the element by 1/cos θ

so that the y coordinate will be equal to a value given as;

space="preserve" listing-type="equation">y/cos θ

whereby the element having the coordinate (x,y) is shifted to the coordinate (x* cos θ

-y* sin θ

, y/cos θ

);

means for transforming the reference block into a parallelogram by the shift of the elements, wherein the parallelogram are equal to the rotation block in lengths of directions of the X axis and the Y axis, and wherein the parallelogram has a first triangular part and a second triangular part extending outward and inward of the rotation block respectively;

means for reading out each of row bit arrangements parallel to the X axis with respect to the first triangular part;

means for executing an OR operation between the readout row bit arrangements and corresponding row bit arrangements of the second triangular part so that the first triangular part will match to the second triangular part to obtain a matrix of N rows×

N columns which has a shape corresponding to a shape of the rotation block;

means for deriving a first transposed matrix with respect to the matrix of N rows×

N columns;

with respect to each of rows of the first transposed matrix where bits of the first triangular part are arranged from a left-hand end toward a right-hand end of the row, means for executing a left rotation of the row by a number of the bits of the first triangular part to obtain a rotation image;

means for deriving a second transposed matrix with respect to the rotation image; and

means for using the second transposed matrix as the rotation block.

10. The apparatus of claim 9 wherein each of the first and second transposed matrix deriving means comprises:

means for calculating a conversion mode number M with respect to the matrix of N rows×

N columns by referring to an equation expressed as;

M=[log₂ N] where when a numeral within a bracket "[ ]" is equal to an integer, the bracket denotes the integer; and

when a numeral within the bracket contains a fraction, the bracket denotes an integer which is obtained by counting the fraction as one;

means for numbering the N rows by 0˜

N-1;

means for calculating rows having numbers A and B for each of conversion modes L (=1˜

M) by referring to equations expressed as;

space="preserve" listing-type="equation">A=k*2.sup.L ˜

k*2.sup.L +2.sup.L-1 -1

space="preserve" listing-type="equation">B=A+2.sup.L-1

space="preserve" listing-type="equation">k=0˜

(N/2.sup.L)-1

where a character "*" denotes an operator of product;

means for representing row bit arrangements of the rows having the numbers A and B by A(j) and B(j) respectively;

means for converting the row bit arrangements A(j) and B(j) into bit arrangements A'"'"'(j) and B'"'"'(j) by referring to equations expressed as;

##EQU11## means for varying L from 1 to M and thereby deriving a matrix of N rows×

N columns which is used as the transposed matrix.

11. The apparatus of claim 8 further comprising:

means for setting a Y axis equal to an axis which passes through the rotation center vertex and which extends parallel to the reference coordinate axis;

means for setting an X axis equal to an axis which passes through the rotation center vertex and which extends perpendicular to the Y axis;

means for representing an X axis coordinate and a Y axis coordinate of each of elements composing the reference block by (x,y);

means for shifting the element in a direction of the X axis so that the x coordinate of the element will be equal to a value given as;

space="preserve" listing-type="equation">x-y* tan θ

where a character "*" denotes an operator of product;

means for multiplying the x coordinate of the element by cos θ

so that the x coordinate will be equal to a value given as;

space="preserve" listing-type="equation">x* cos θ

-y* sin θ

means for multiplying the y coordinate of the element by 1/cos θ

so that the y coordinate will be equal to a value given as;

space="preserve" listing-type="equation">y/cos θ

whereby the element having the coordinate (x,y) is shifted to the coordinate (x* cos θ

-y* sin θ

, y/cos θ

);

means for transforming the reference block into a parallelogram by the shift of the elements, wherein the parallelogram are equal to the rotation block in lengths of directions of the X axis and the Y axis, wherein the parallelogram has a first triangular part and a second triangular part extending outward and inward of the rotation block respectively, and wherein the first triangular part is composed of an n number of row bit arrangements parallel to the X axis;

means for numbering rows of the parallelogram of n+N rows by 0˜

n+n-1;

means for generating a mask matrix divided into a first region and a second region, wherein the first region corresponds to the second triangular part and is "0", and wherein the second region is "1";

means for executing an AND operation between the "0" row ˜

the "n" row and the mask matrix to generate a "0" row ˜

an "n'"'"'" row;

means for masking a part of the "1'"'"'" row which corresponds to a part of the "0'"'"'" row where bits differ from "0", and setting the masked part equal to "0";

means for executing an OR operation between the masked row and the "0'"'"'" row to generate a revised "0'"'"'" row;

means for masking a part of the "2'"'"'" row which corresponds to a part of the revised "0'"'"'" row where bits differ from "0", and setting the masked part equal to "0";

means for executing an OR operation between the masked row and the revised "0'"'"'" row to generate a revised "1'"'"'" row;

means for masking a part of the "3'"'"'" row which corresponds to a part of the revised "1'"'"'" row where bits differ from "0", and setting the masked part equal to "0";

means for executing an OR operation between the masked row and the revised "1'"'"'" row to generate a revised "2'"'"'" row;

means for similarly masking a part of the "n'"'"'" row which corresponds to a part of the revised "(n-2)'"'"'" row where bits differ from "0", and setting the masked part equal to "0";

means for similarly executing an OR operation between the masked row and the revised "(n-2)'"'"'" row to generate a revised "(n-1)'"'"'" row;

means for setting the revised "(n-1)'"'"'" row as a "0" row; and

means for deriving subsequent rows up to an N-1 row by similar steps to obtain a matrix of N rows×

N columns which is used as the rotation block.