US5598181A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for rotating a digital image ninety degrees using a small auxiliary buffer
Assignee: Xerox Corp
•
Filing: 1994-09-26
•
Granted: 1997-01-28
•
Expires: 2014-09-26
Abstract
Abstract A method for rotating an image clockwise or counter clockwise by ninety degrees in place in an image buffer with a small auxiliary buffer is disclosed. The image, defined by a rectangular pattern of H lines with each line having W pixels, is segmented into square blocks of N pixels per row and N lines per column. The image is stored in an image buffer, and each square block of pixels in the image buffer is rotated by ninety degrees. A starting memory location in the image buffer is selected from a set of starting memory locations, and a memory word at the selected starting memory location is copied into a memory word of a temporary storage buffer. A replacement memory location in the image buffer is determined for the memory word in the temporary storage buffer, which is swapped with a memory word at the replacement memory location. A sequence of replacement memory locations is defined by repeating the preceding operation until the selected starting memory location in the image buffer is determined to be a replacement memory location in the image buffer for the memory word in the temporary storage buffer. The sequence of replacement memory locations is terminated by replacing the memory word at the selected starting memory location with the memory word in the temporary storage buffer.
Inventors
- 👤 Dorian Kermisch
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 15:43
CPC Classifications
G; G06; G06T; G06T3/00; G06T3/60; G06T3/602; G09; G09G; G09G5/00; G09G5/36; G09G5/39; G09G5/393
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
273 words
A method for rotating an image in place while entirely resident in a memory, the image being defined by a rectangular pattern of H lines with each line having W pixels, comprising the steps of: segmenting the image into square blocks of N pixels per row and N lines per column, said segmenting step storing each line of W pixels defining the image in an array of memory words of an image buffer so that the image is entirely resident in the image buffer; individually rotating, in place, each N×N square block of pixels in the image buffer segmented by said segmenting step through a selected angle; and subsequent to said segmenting and said rotating steps, performing the steps of: selecting a memory word of the image buffer as a starting memory location; copying the memory word at the starting memory location into a memory word of a temporary storage buffer; determining a replacement memory location s n+1 in the image buffer of the memory word in the temporary storage buffer originally stored at memory location s n in the image buffer; swapping the memory word in the temporary storage buffer with a memory word at the replacement memory location s n+1 in the image buffer; repeating said steps of determining and swapping until the starting memory location in the image buffer is equivalent to the replacement memory location s n+1 in the image buffer for the memory word stored in the temporary storage buffer; and replacing the memory word at the starting memory location in the image buffer with the memory word in the temporary storage buffer, to terminate said repeating step.
Claim 2
Independent Claim
273 words
A method for rotating an image in place while entirely resident in a memory, the image being defined by a rectangular pattern of H lines with each line having W pixels, comprising the steps of: segmenting the image into square blocks of N pixels per row and N lines per column, said segmenting step storing each line of W pixels defining the image in an array of memory words of an image buffer so that the image is entirely resident in the image buffer; individually rotating, in place, each N×N square block of pixels in the image buffer segmented by said segmenting step through a selected angle; and subsequent to said segmenting and said rotating steps, performing the steps of: selecting a memory word of the image buffer as a starting memory location; copying the memory word at the starting memory location into a memory word of a temporary storage buffer; determining a replacement memory location s n+1 in the image buffer of the memory word in the temporary storage buffer originally stored at memory location s n in the image buffer; swapping the memory word in the temporary storage buffer with a memory word at the replacement memory location s n+1 in the image buffer; repeating said steps of determining and swapping until the starting memory location in the image buffer is equivalent to the replacement memory location s n+1 in the image buffer for the memory word stored in the temporary storage buffer; and replacing the memory word at the starting memory location in the image buffer with the memory word in the temporary storage buffer, to terminate said repeating step.
Claim 3
Dependent Claim
32 words
The method of claim 1, further comprising the step of substituting the starting memory location with a subsequent starting memory location and repeating said steps of copying, determining, swapping, repeating and replacing.
Claim 4
Dependent Claim
34 words
The method of claim 2, further comprising the step of performing said substituting step, until each location of every memory word in the image buffer is defined in a sequence of replacement memory locations.
Claim 5
Dependent Claim
31 words
The method of claim 3, further comprising the step of recording each starting memory location identified by said selecting step and said substituting step to form a set of starting locations.
Claim 6
Dependent Claim
50 words
The method of claim 4, further comprising the step of rotating a subsequent image, being defined by a rectangular pattern of H lines with each line having W pixels, by performing said steps of copying, determining, swapping, repeating and substituting for each starting location in the set of starting locations.
Claim 7
Dependent Claim
39 words
The method of claim 4, further comprising the steps of: determining a plurality of sets of starting memory locations for different image buffer configurations; and storing the plurality of sets of starting memory locations in a look up table.
Claim 8
Dependent Claim
32 words
The method of claim 1, wherein said segmenting step comprises the step of storing each row of pixels of each square block in a sequence of memory words of the image buffer.
Claim 9
Dependent Claim
35 words
The method of claim 7, wherein said segmenting step comprises the step of copying the sequence of memory words at a starting memory location into a sequence of memory words of the temporary storage buffer.
Claim 10
Dependent Claim
32 words
The method of claim 1, wherein said segmenting step stores an image defined by a rectangular pattern of K lines with each line having W pixels, where K is less than H.
Claim 11
Dependent Claim
122 words
The method of claim 1, wherein said rotating step comprises the steps of: representing each square block of N×N pixels segmented by said segmenting step as a two dimensional array A(x,y) of N pixels per row and N pixels per column, each two dimensional array A(x,y) having an x and y component enumerated from zero to N-1; selecting a set of N starting pixels from the two dimensional array A(x,y); and replacing each starting pixel in the set of N starting pixels in accordance with the following sequence of replacement operations: replace pixel A(x,y) with pixel A(y, N-1-x); replace pixel A(y, N-1-x) with pixel A(N-1-y, N-1-x); replace pixel A(N-1-y, N-1-x) with pixel A(N-1-x, y); and replace pixel A(N-1-x, y) with pixel A(x,y).
Claim 12
Dependent Claim
19 words
The method of claim 1, wherein said rotating step rotates the image through the selected angle of ninety degrees.
Claim 13
Independent Claim
299 words
An apparatus for rotating an image in place while entirely resident in a memory, the image being defined by a rectangular pattern of H lines with each line having W pixels, comprising: an image buffer being defined by an array of memory words; means for segmenting the image into square blocks of N pixels per row and N lines per column, said segmenting means storing each line of W pixels of the image in the array of memory words of said image buffer; means for individually rotating, in place, each N×N square block of pixels in said image buffer segmented by said segmenting means through a selected angle; means for selecting a memory word of the image buffer as a starting memory location; an auxiliary storage buffer having at least one memory word; means for copying the memory word at the starting memory location into a memory word of said auxiliary storage buffer originally stored at memory location s n in said image buffer; a processor for determining a replacement memory location s n+1 in said image buffer of the memory word stored in said auxiliary storage buffer; means for swapping the memory word in said auxiliary storage buffer with a memory word at the replacement memory location s n+1 in said image buffer; means for defining a sequence of replacement memory locations with said processor and said swapping means that terminates in response to the starting memory location in said image buffer being determined to be a replacement memory location s n+1 in said image buffer for the memory word in said auxiliary storage buffer; and means for replacing the memory word at the starting memory location in said image buffer with the memory word in said auxiliary storage buffer to terminate the sequence of replacement memory locations.
Claim 14
Independent Claim
299 words
An apparatus for rotating an image in place while entirely resident in a memory, the image being defined by a rectangular pattern of H lines with each line having W pixels, comprising: an image buffer being defined by an array of memory words; means for segmenting the image into square blocks of N pixels per row and N lines per column, said segmenting means storing each line of W pixels of the image in the array of memory words of said image buffer; means for individually rotating, in place, each N×N square block of pixels in said image buffer segmented by said segmenting means through a selected angle; means for selecting a memory word of the image buffer as a starting memory location; an auxiliary storage buffer having at least one memory word; means for copying the memory word at the starting memory location into a memory word of said auxiliary storage buffer originally stored at memory location s n in said image buffer; a processor for determining a replacement memory location s n+1 in said image buffer of the memory word stored in said auxiliary storage buffer; means for swapping the memory word in said auxiliary storage buffer with a memory word at the replacement memory location s n+1 in said image buffer; means for defining a sequence of replacement memory locations with said processor and said swapping means that terminates in response to the starting memory location in said image buffer being determined to be a replacement memory location s n+1 in said image buffer for the memory word in said auxiliary storage buffer; and means for replacing the memory word at the starting memory location in said image buffer with the memory word in said auxiliary storage buffer to terminate the sequence of replacement memory locations.
Claim 15
Dependent Claim
12 words
The apparatus of claim 12, wherein the selected angle is ninety degrees.
References Cited (Backward Citations)
US4929085A
Cited
US4894646A
Cited
US4916746A
Cited
US5034733A
Cited
US5133025A
Cited
US4995089A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-01-28 | 2000-07-29 | 2001-01-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-01-28 | 2004-07-29 | 2005-01-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-01-28 | 2008-07-29 | 2009-01-28 | $7700.00 | Window Closed / Lapsed |