This invention is in the field of digital image handling and, more particularly, is an improved circuit for the rotation of a digital image by a multiple of 90 degrees.
It is frequently necessary to rotate a digital image by multiples of 90 degrees, or to create the mirror images of these rotations. A method and circuit for producing these rotations at high speed without the necessity of special hardware is described in commonly owned patent applications Ser. No. 07/453,738 entitled "Method to Rotate a Bitmap Image 90 Degrees", and Ser. No. 07/721,797, "Parallel Rotation Algorithm" which are incorporated herein by reference.
To use a numerical example, the method can be explained as the addition of the rotation of the bits within each 4 by 4 bit block and the rotation of the blocks of the whole image. To rotate bits within a block, the first 4 bit word is loaded into the first line of a 4 by 4 bit buffer. The next word is circularly rotated upward one bit and loaded into the second line of the buffer. The third word is circularly shifted two bits and loaded into the third line of the buffer and the fourth line is circularly shifted three bits and loaded into the fourth line of the buffer. At this point a vertical line in the original image is still a vertical line in the buffer, but a horizontal line in the original is now a diagonal line in the buffer.
Since the buffer is implemented from 4 by 1 bit devices, any bit in each device is addressable independently of the other devices, and a bit in one word in the buffer can be loaded into, or read from, any bit of the four words of memory. Therefore, if the bits in the buffer are addressed along diagonal lines parallel to the diagonal line in the buffer and read out as single 4-bit words, the diagonal line in the buffer will become a vertical line at the output. Continuing with addressing the bits along diagonal lines, the vertical line in the buffer will become a diagonal line at the output. The output four words are then shifted to line up the diagonal bits into a horizontal line. Since this line started as a vertical line, it can be seen that the 4 by 4 bit block has now been completely rotated 90 degrees. To rotate the blocks within the image, a simple addressing algorithm provides that each block of the original image is read into the correct block of the page buffer.
Of course, the algorithm can be scaled up to larger sizes. However, in these larger sizes, the number of address lines becomes excessive. For example, in a sixteen line by sixteen bit buffer implemented from 16 by 1 bit RAM devices, sixty-four address lines would be required.
USPTO Backgrounds
USPTO Backgrounds