System for fast 90-degree rotation of bi-level images

Claim 2

In a 32-bit operating system, a method of rotating by 90° a block of bi-level image data having 8 rows by 8 columns of pixel data bits, comprising the computer implemented steps of: generating an intermediate matrix having 8 rows by 8 columns of pixel data bits from the pixel data bits of the block, wherein the block is divided into four row pairs and the intermediate matrix is divided into four nibble column pairs, each said row pair corresponding to one of the nibble column pairs, each row of each row pair being divided into two halves, one of said halves of one row of each row pair being rotated 90° and translated to form a top half of one nibble column of the corresponding nibble column pair, the other one of said halves of said one row also being rotated 90° and translated to form a top half of the other nibble column of the corresponding nibble column pair, one of said halves of the other row of each row pair being rotated 90° and translated to form a bottom half of said one nibble column, the other one of said halves of said other row being rotated 90° and translated to form a bottom half of the other nibble column of the corresponding nibble column pair; saving the rows of the intermediate matrix sequentially into first and second 32-bit processor registers; copying the first 32-bit register into a third 32-bit processor register and the second 32-bit register into a fourth 32-bit processor register; shifting each of the first and second registers by one bit in opposite directions; and overlaying alternate bits from the fourth register onto the first register and from the third register onto the second register.

Claim 3

The method, according to claim 1, wherein the step of generating an intermediate matrix comprises generating an intermediate matrix wherein successive row pairs from top to bottom in the block correspond to successive nibble column pairs from right to left in the intermediate matrix, and wherein said one row of each row pair is the top row of each said row pair.

Claim 4

The method according to claim 2, wherein the step of shifting each of the first and second registers by one bit in opposite directions comprises shifting the first register by one bit left and shifting the second register by one bit right.

Claim 5

The method according to claim 3, wherein the step of overlaying alternate bits further comprises the steps of zeroing out all odd bits of the first and fourth registers and all even bits of the second and third register, and logical ORing the first register with the fourth register and the register with the third register.

Claim 6

The method according to claim 1, wherein the step of generating an intermediate matrix comprises generating an intermediate matrix wherein successive row pairs from top to bottom in the block correspond to successive nibble column pairs from left to right in the intermediate matrix, and wherein said one row of each row pair is the bottom row of each said row pair.

Claim 7

The method, according to claim 5, wherein the step of shifting each of the first and second register by one bit in opposite directions comprises shifting the first register by one bit right and shifting the second register by one bit left.

Claim 8

The method according to claim 6, wherein the step of overlaying alternate bits further comprises the steps of zeroing out all even bits of the first and fourth registers and all odd bits of the second and third registers, and logical ORing the first register with the fourth register and the second register with the third register.

Claim 9

The method, according to claim 1, wherein the step of generating an intermediate matrix comprises: obtaining a first set of 4-byte values from at least one lookup table for each odd-numbered row from the block and dynamically overlaying said first set of 4-byte values in the first 32-bit register; and obtaining a second set of 4-byte values from said at least one lookup table for each even-numbered row from the block and dynamically overlaying said second set of 4-byte values in the second 32-bit register.

Claim 10

In a 32-bit operating system, a method of rotating a bi-level image by 90°, comprising the computer implemented steps of: a) selecting an unrotated 8 by 8 pixel matrix from the image data; b) generating an intermediate matrix having 8 rows by 8 columns of pixel data bits from the pixel data bits of the block, wherein the block is divided into four row pairs and the intermediate matrix is divided into four nibble column pairs, each said row pair corresponding to one of the nibble column pairs, each row of each row pair being divided into two halves, one of said halves of one row of each row pair being rotated 90° and translated to form a top half of one nibble column of the corresponding nibble column pair, the other one of said halves of said one row also being rotated 90° and translated to form a top half of the other nibble column of the corresponding nibble column pair, one of said halves of the other row of each row pair being rotated 90° and translated to form a bottom half of said one nibble column, the other one of said halves of said other row being rotated 90° and translated to form a bottom half of the other nibble column of the corresponding nibble column pair; c) saving the rows of the intermediate matrix sequentially into first and second 32-bit processor registers; d) copying the first 32-bit register into a third 32-bit processor register and the second 32-bit register into a fourth 32-bit processor register; e) shifting each of the first and second registers by one bit in opposite directions; and f) overlaying alternate bits from the fourth register onto the first register and from the third register onto the second register; and g) repeating steps a) through f) until the image has been rotated.

Claim 11

In a 32-bit operating system, a method of rotating a bi-level image by 90°, comprising the computer implemented steps of: a) selecting an unrotated 8 by 8 pixel matrix from the image data; b) generating an intermediate matrix having 8 rows by 8 columns of pixel data bits from the pixel data bits of the block, wherein the block is divided into four row pairs and the intermediate matrix is divided into four nibble column pairs, each said row pair corresponding to one of the nibble column pairs, each row of each row pair being divided into two halves, one of said halves of one row of each row pair being rotated 90° and translated to form a top half of one nibble column of the corresponding nibble column pair, the other one of said halves of said one row also being rotated 90° and translated to form a top half of the other nibble column of the corresponding nibble column pair, one of said halves of the other row of each row pair being rotated 90° and translated to form a bottom half of said one nibble column, the other one of said halves of said other row being rotated 90° and translated to form a bottom half of the other nibble column of the corresponding nibble column pair; c) saving the rows of the intermediate matrix sequentially into first and second 32-bit processor registers; d) copying the first 32-bit register into a third 32-bit processor register and the second 32-bit register into a fourth 32-bit processor register; e) shifting each of the first and second registers by one bit in opposite directions; and f) overlaying alternate bits from the fourth register onto the first register and from the third register onto the second register; and g) repeating steps a) through f) until the image has been rotated.

Claim 12

A 32-bit system for operating a block of bi-level image data having 8 rows by 8 columns of pixel data bits, comprising: means for generating an intermediate matrix having 8 rows by 8 columns of pixel data bits from the pixel data bits of the block, wherein the block is divided into four row pairs and the intermediate matrix is divided into four nibble column pairs, each said row pair corresponding to one of the nibble column pairs, each row of each row pair being divided into two halves, one of said halves of one row of each row pair being rotated 90° and translated to form a top half of one nibble column of the corresponding nibble column pair, the other one of said halves of said one row also being rotated 90° and translated to form a top half of the other nibble column of the corresponding nibble column pair, one of said halves of the other row of each row pair being rotated 90° and translated to form a bottom half of said one nibble column, the other one of said halves of said other row being rotated 90° and translated to form a bottom half of the other nibble column of the corresponding nibble column pair; at least first, second, third, and fourth 32-bit processor registers, the first and third registers for saving, in duplicate, the first four rows of the intermediate matrix and the second and fourth registers for saving, in duplicate, the remaining four rows of the intermediate matrix; means for shifting each of the first and second registers by one bit in opposite directions; and means for overlaying alternate bits from the fourth register onto the first register and from the third register onto the second register.

Claim 13

A 32-bit system for operating a block of bi-level image data having 8 rows by 8 columns of pixel data bits, comprising: means for generating an intermediate matrix having 8 rows by 8 columns of pixel data bits from the pixel data bits of the block, wherein the block is divided into four row pairs and the intermediate matrix is divided into four nibble column pairs, each said row pair corresponding to one of the nibble column pairs, each row of each row pair being divided into two halves, one of said halves of one row of each row pair being rotated 90° and translated to form a top half of one nibble column of the corresponding nibble column pair, the other one of said halves of said one row also being rotated 90° and translated to form a top half of the other nibble column of the corresponding nibble column pair, one of said halves of the other row of each row pair being rotated 90° and translated to form a bottom half of said one nibble column, the other one of said halves of said other row being rotated 90° and translated to form a bottom half of the other nibble column of the corresponding nibble column pair; at least first, second, third, and fourth 32-bit processor registers, the first and third registers for saving, in duplicate, the first four rows of the intermediate matrix and the second and fourth registers for saving, in duplicate, the remaining four rows of the intermediate matrix; means for shifting each of the first and second registers by one bit in opposite directions; and means for overlaying alternate bits from the fourth register onto the first register and from the third register onto the second register.

Claim 14

A system, according to claim 10, wherein the means for generating an intermediate matrix comprises at least one lookup table.

Claim 15

A system, according to claim 11, wherein said at least one lookup table comprises multiple look tables, each lookup table being adapted for generating a 4-byte value for at least one row from the block.

Claim 16

A system, according to claim 10, wherein the means for generating an intermediate matrix comprises: four lookup tables, each lookup table being adapted for generating 4-byte values for at least two rows from the block; and means for dynamically overlaying 4-byte values from alternate rows from the block into one of said registers.