Patent US5581635A successfully refreshed from Google Patents.
US5581635A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for fast rotation of run-length encoded images
Assignee: United Parcel Service of America Inc
•
Filing: 1995-07-25
•
Granted: 1996-12-03
•
Expires: 2015-07-25
Abstract
Abstract A method and system including a high speed computer algorithm for rotating images stored in a computer memory, such as those captured by a CCD array. The method and system may be used with an over-the-belt optical character recognition (OCR) reader that captures a pixelized image of the surface of a parcel as it moves along a conveyor. A run-length encoded output image is obtained from a run-length encoded input image, wherein the output image is a rotated version of the input image. A predefined pixel mapping sequence for a rotation angle with a rational tangent is used to map image pixel data. Mapping image pixel data using a predefined pixel mapping sequence allows rotation without floating point computations, and allows the use of a reverse pixel mapping technique to map output runs from an input image in order to avoid the creation of holes or artifacts in the output image. Mapped output runs are scaled to preserve the aspect ratio of the rotated image. The order of processing the elements of the input run-length input table is selected so as to directly create a run-length encoded output table.
Inventors
- 👤 Jie Zhu
- 👤 Michael C. Moed
- 👤 Izrail S. Gorian
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 13:13
CPC Classifications
G; G06; G06T; G06T3/00; G06T3/60; G06T3/606
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
183 words
A method of obtaining output image data representing an output image from input image data representing an input image, the output image and the input image each representing lines of pixels, the output image being a rotated version of the input image, the input image data comprising rows of elements, each element representing at least one pixel of the input image, comprising the steps of: selecting a quadrant of rotation; selecting a rotation angle from a pre-defined set of rotation angles; in response to said rotation angle, retrieving a predefined pixel mapping sequence for mapping pixels of the input image to pixels of the output image; in response to said quadrant of rotation, selecting a row order in which to read the rows of the input image data; in response to said quadrant of rotation, selecting an element order in which to read the elements of each row of the input image data; and mapping the input image data to the output image data in said row order, and within each row in said element order, in accordance with said pixel mapping sequence.
Claim 2
Independent Claim
183 words
A method of obtaining output image data representing an output image from input image data representing an input image, the output image and the input image each representing lines of pixels, the output image being a rotated version of the input image, the input image data comprising rows of elements, each element representing at least one pixel of the input image, comprising the steps of: selecting a quadrant of rotation; selecting a rotation angle from a pre-defined set of rotation angles; in response to said rotation angle, retrieving a predefined pixel mapping sequence for mapping pixels of the input image to pixels of the output image; in response to said quadrant of rotation, selecting a row order in which to read the rows of the input image data; in response to said quadrant of rotation, selecting an element order in which to read the elements of each row of the input image data; and mapping the input image data to the output image data in said row order, and within each row in said element order, in accordance with said pixel mapping sequence.
Claim 3
Dependent Claim
28 words
The method of claim 1, wherein said mapping step comprises reverse pixel mapping, and wherein each element represents individual pixels, or runs of pixels, of the input image.
Claim 4
Dependent Claim
86 words
The method of claim 1, wherein the rows of the input image data correspond to lines of the input image, and wherein the elements of the input image data correspond to pixels of the input image, further comprising the step of, after mapping pixels within each line of the input image, and prior to mapping pixels within a subsequent line of the input image, augmenting a run-length encoded output image comprising one or more output runs so as to incrementally construct the run-length encoded output image.
Claim 5
Dependent Claim
109 words
The method of claim 3, wherein said step of augmenting a run-length encoded output image comprises the steps of: determining whether each pixel mapped to the output image is located adjacent to a previously mapped pixel in the same line of the output image; if a mapped pixel is located adjacent to a previously mapped pixel in the same line of the output image, adding the mapped pixel to an output run comprising the previously mapped pixel; and if a mapped pixel is not located adjacent to a previously mapped pixel in the same line of the output image, defining a new output run starting with the mapped pixel.
Claim 6
Dependent Claim
29 words
The method of claim 4, further comprising the steps of: in response to said rotation angle, retrieving predefined scaling factor; and scaling the output runs by said scaling factor.
Claim 7
Dependent Claim
85 words
The method of claim 1, wherein each row of the input image data corresponds to a line of the input image, and wherein the elements within a row of the input image data define one or more input runs, further comprising the step of, after mapping the pixels defining each input run and prior to mapping the pixels defining a subsequent input run, augmenting a run-length encoded output image comprising one or more output runs so as to incrementally construct the run-length encoded output image.
Claim 8
Dependent Claim
109 words
The method of claim 6, wherein said step of augmenting a run-length encoded output image comprises the steps of: determining whether each pixel mapped to the output image is located adjacent to a previously mapped pixel in the same line of the output image; if a mapped pixel is located adjacent to a previously mapped pixel in the same line of the output image, adding the mapped pixel to an output run comprising the previously mapped pixel; and if a mapped pixel is not located adjacent to a previously mapped pixel in the same line of the output image, defining a new output run starting with the mapped pixel.
Claim 9
Dependent Claim
31 words
The method of claim 7, further comprising the steps of: in response to said angle of rotation, retrieving a predefined scaling factor; and scaling the output runs by said scaling factor.
Claim 10
Dependent Claim
13 words
The method of claim 8, wherein said mapping step comprises reverse pixel mapping.
Claim 11
Independent Claim
231 words
A method of obtaining a run-length encoded output image comprising one or more output runs from a run-length encoded input image comprising one or more input runs, the run-length encoded output image representing an output image comprising lines of pixels, the run-length encoded input image representing an input image comprising lines of pixels, the output image being a rotated version of the input image, the run-length encoded input image comprising rows of elements wherein each row corresponds to a line of the input image, the run-length encoded output image comprising rows of elements wherein each row corresponds to a line of the output image, each element representing at least one pixel of the input image, comprising the steps of: selecting a quadrant of rotation; selecting a rotation angle from a pre-defined set of rotation angles; in response to said rotation angle, retrieving a predefined pixel mapping sequence for mapping pixels of the input image to pixels of the output image; in response to said quadrant of rotation, selecting a row order in which to read the rows of the run-length encoded input image; in response to said quadrant of rotation, selecting an element order in which to read the elements of each row of the run-length encoded input image; and processing the elements of the run-length encoded input image in said row order, and within each row in said element order.
Claim 12
Independent Claim
231 words
A method of obtaining a run-length encoded output image comprising one or more output runs from a run-length encoded input image comprising one or more input runs, the run-length encoded output image representing an output image comprising lines of pixels, the run-length encoded input image representing an input image comprising lines of pixels, the output image being a rotated version of the input image, the run-length encoded input image comprising rows of elements wherein each row corresponds to a line of the input image, the run-length encoded output image comprising rows of elements wherein each row corresponds to a line of the output image, each element representing at least one pixel of the input image, comprising the steps of: selecting a quadrant of rotation; selecting a rotation angle from a pre-defined set of rotation angles; in response to said rotation angle, retrieving a predefined pixel mapping sequence for mapping pixels of the input image to pixels of the output image; in response to said quadrant of rotation, selecting a row order in which to read the rows of the run-length encoded input image; in response to said quadrant of rotation, selecting an element order in which to read the elements of each row of the run-length encoded input image; and processing the elements of the run-length encoded input image in said row order, and within each row in said element order.
Claim 13
Dependent Claim
28 words
The method of claim 11, wherein said processing step comprises reverse pixel mapping, and wherein each element represents individual pixels, or runs of pixels, of the input image.
Claim 14
Dependent Claim
46 words
The method of claim 10, wherein said processing step comprises the steps of: determining the location in the input image of the pixels comprising an input run; and mapping the pixels comprising the input run to the output image in accordance with said pixel mapping sequence.
Claim 15
Dependent Claim
92 words
The method of claim 12, wherein the first pixel of a plurality of consecutive lines of the input image define an edge of the input image, and wherein the step of determining the location in the output image of the pixels comprising the input runs comprises the steps of: in response to said rotation angle, determining pixel locations in the output image corresponding to the edge; and determining the location of input image pixels in the output image in relation to the pixel locations in the output image corresponding to the edge.
Claim 16
Dependent Claim
24 words
The method of claim 13, wherein said step of determining the location of input image pixels in the output image comprises reverse pixel mapping.
Claim 17
Dependent Claim
45 words
The method of claim 14, further comprising the step of, after processing the elements defining each input run and prior to processing the elements defining a subsequent input run, augmenting the run-length encoded output image so as to incrementally construct the run-length encoded output image.
Claim 18
Dependent Claim
108 words
The method of claim 15, wherein said step of augmenting the run-length encoded image comprises the steps of: determining whether each pixel mapped to the output image is located adjacent to a previously mapped pixel in the same line of the output image; if a mapped pixel is located adjacent to a previously mapped pixel in the same line of the output image, adding the mapped pixel to an output run comprising the previously mapped pixel; and if a mapped pixel is not located adjacent to a previously mapped pixel in the same line of the output image, defining a new output run starting with the mapped pixel.
Claim 19
Dependent Claim
38 words
The method of claim 16, wherein said step of determining whether each pixel mapped to the output image is located adjacent to a previously mapped pixel in the same line of the output image comprises reverse pixel mapping.
Claim 20
Dependent Claim
29 words
The method of claim 17, further comprising the steps of: in response to said rotation angle, retrieving predefined scaling factor; and scaling the output runs by said scaling factor.
Claim 21
Independent Claim
240 words
An apparatus for obtaining a run-length encoded output image comprising one or more output runs from a run-length encoded input image comprising one or more input runs, the run-length encoded output image representing an output image comprising lines of pixels, the run-length encoded input image representing an input image comprising lines of pixels, the output image being a rotated version of the input image, the run-length encoded input image comprising rows of elements wherein each row corresponds to a line of the input image, the run-length encoded output image comprising rows of elements wherein each row corresponds to a line of the output image, each element representing at least one pixel of the input image, comprising: means for selecting a quadrant of rotation; means for selecting a rotation angle from a pre-defined set of rotation angles; means for, in response to said rotation angle, retrieving a predefined pixel mapping sequence for mapping pixels of the input image to pixels of the output image; means for, in response to said quadrant of rotation, selecting a row order in which to read the rows of the run-length encoded input image; means for, in response to said quadrant of rotation, selecting an element order in which to read the elements of each row of the run-length encoded input image; and means for processing the elements of the run-length encoded input image in said row order, and within each row in said element order.
Claim 22
Independent Claim
240 words
An apparatus for obtaining a run-length encoded output image comprising one or more output runs from a run-length encoded input image comprising one or more input runs, the run-length encoded output image representing an output image comprising lines of pixels, the run-length encoded input image representing an input image comprising lines of pixels, the output image being a rotated version of the input image, the run-length encoded input image comprising rows of elements wherein each row corresponds to a line of the input image, the run-length encoded output image comprising rows of elements wherein each row corresponds to a line of the output image, each element representing at least one pixel of the input image, comprising: means for selecting a quadrant of rotation; means for selecting a rotation angle from a pre-defined set of rotation angles; means for, in response to said rotation angle, retrieving a predefined pixel mapping sequence for mapping pixels of the input image to pixels of the output image; means for, in response to said quadrant of rotation, selecting a row order in which to read the rows of the run-length encoded input image; means for, in response to said quadrant of rotation, selecting an element order in which to read the elements of each row of the run-length encoded input image; and means for processing the elements of the run-length encoded input image in said row order, and within each row in said element order.
Claim 23
Dependent Claim
31 words
The apparatus of claim 19, wherein said means for processing comprises means for reverse pixel mapping, and wherein each element represents individual pixels, or runs of pixels, of the input image.
Claim 24
Dependent Claim
46 words
The apparatus of claim 19, wherein said means for processing comprises means for: determining the location in the input image of the pixels comprising an input run; and mapping the pixels comprising the input run to the output image in accordance with said pixel mapping sequence.
Claim 25
Dependent Claim
91 words
The apparatus of claim 21, wherein the first pixel of a plurality of consecutive lines of the input image define an edge of the input image, and wherein the means for determining the location in the output image of the pixels comprising the input runs comprises means for: in response to said rotation angle, determining pixel locations in the output image corresponding to the edge; and determining the location of input image pixels in the output image in relation to the pixel locations in the output image corresponding to the edge.
Claim 26
Dependent Claim
45 words
The apparatus of claim 22, further comprising the means for, after processing the elements defining each input run and prior to processing the elements defining a subsequent input run, augmenting the run-length encoded output image so as to incrementally construct the run-length encoded output image.
Claim 27
Dependent Claim
107 words
The apparatus of claim 23, wherein said means for augmenting the run-length encoded image comprises means for: determining whether each pixel mapped to the output image is located adjacent to a previously mapped pixel in the same line of the output image; if a mapped pixel is located adjacent to a previously mapped pixel in the same line of the output image, adding the mapped pixel to an output run comprising the previously mapped pixel; and if a mapped pixel is not located adjacent to a previously mapped pixel in the same line of the output image, defining a new output run starting with the mapped pixel.
Claim 28
Dependent Claim
28 words
The apparatus of claim 24, further comprising means for: in response to said rotation angle, retrieving predefined scaling factor; and scaling the output runs by said scaling factor.
Claim 29
Dependent Claim
241 words
A storage medium comprising a computer program providing a method of obtaining a run-length encoded output image comprising one or more output runs from a run-length encoded input image comprising one or more input runs, the run-length encoded output image representing an output image comprising lines of pixels, the run-length encoded input image representing an input image comprising lines of pixels, the output image being a rotated version of the input image, the run-length encoded input image comprising rows of elements wherein each row corresponds to a line of the input image, the run-length encoded output image comprising rows of elements wherein each row corresponds to a line of the output image, each element representing individual pixels, or runs of pixels, of the input image, comprising the steps of: selecting a quadrant of rotation; selecting a rotation angle from a pre-defined set of rotation angles; in response to said rotation angle, retrieving a predefined pixel mapping sequence for mapping pixels of the input image to pixels of the output image; in response to said quadrant of rotation, selecting a row order in which to read the rows of the run-length encoded input image; in response to said quadrant of rotation, selecting an element order in which to read the elements of each row of the run-length encoded input image; and processing the elements of the run-length encoded input image in said row order, and within each row in said element order.
Claim 30
Dependent Claim
241 words
A storage medium comprising a computer program providing a method of obtaining a run-length encoded output image comprising one or more output runs from a run-length encoded input image comprising one or more input runs, the run-length encoded output image representing an output image comprising lines of pixels, the run-length encoded input image representing an input image comprising lines of pixels, the output image being a rotated version of the input image, the run-length encoded input image comprising rows of elements wherein each row corresponds to a line of the input image, the run-length encoded output image comprising rows of elements wherein each row corresponds to a line of the output image, each element representing individual pixels, or runs of pixels, of the input image, comprising the steps of: selecting a quadrant of rotation; selecting a rotation angle from a pre-defined set of rotation angles; in response to said rotation angle, retrieving a predefined pixel mapping sequence for mapping pixels of the input image to pixels of the output image; in response to said quadrant of rotation, selecting a row order in which to read the rows of the run-length encoded input image; in response to said quadrant of rotation, selecting an element order in which to read the elements of each row of the run-length encoded input image; and processing the elements of the run-length encoded input image in said row order, and within each row in said element order.
Claim 31
Dependent Claim
14 words
The storage medium of claim 26, wherein said processing step comprises reverse pixel mapping.
Claim 32
Dependent Claim
47 words
The storage medium of claim 26, wherein said processing step comprises the steps of: determining the location in the input image of the pixels comprising an input run; and mapping the pixels comprising the input run to the output image in accordance with said pixel mapping sequence.
Claim 33
Dependent Claim
93 words
The storage medium of claim 28, wherein the first pixel of a plurality of consecutive lines of the input image define an edge of the input image, and wherein the step of determining the location in the output image of the pixels comprising the input runs comprises the steps of: in response to said rotation angle, determining pixel locations in the output image corresponding to the edge; and determining the location of input image pixels in the output image in relation to the pixel locations in the output image corresponding to the edge.
Claim 34
Dependent Claim
49 words
The storage medium of claim 29, wherein said method further comprises the step of, after processing the elements defining each input run and prior to processing the elements defining a subsequent input run, augmenting the run-length encoded output image so as to incrementally construct the run-length encoded output image.
Claim 35
Dependent Claim
109 words
The storage medium of claim 30, wherein said step of augmenting the run-length encoded image comprises the steps of: determining whether each pixel mapped to the output image is located adjacent to a previously mapped pixel in the same line of the output image; if a mapped pixel is located adjacent to a previously mapped pixel in the same line of the output image, adding the mapped pixel to an output run comprising the previously mapped pixel; and if a mapped pixel is not located adjacent to a previously mapped pixel in the same line of the output image, defining a new output run starting with the mapped pixel.
Claim 36
Dependent Claim
34 words
The storage medium of claim 31, wherein said method further comprises the steps of: in response to said rotation angle, retrieving a predefined scaling factor; and scaling the output runs by said scaling factor.
References Cited (Backward Citations)
US4554638A
Cited
US4611232A
Cited
US4783834A
Cited
US4985849A
Cited
US4827413A
Cited
US4912559A
Cited
US4792981A
Cited
US4878124A
Cited
JPH0256081A
Cited
US5008951A
Cited
US5124692A
Cited
JPH04296983A
Cited
JPH05313636A
Cited
JPH05324916A
Cited
JPH0630240A
Cited
US5418862A
Cited
US5412197A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-12-03 | 2000-06-03 | 2000-12-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-12-03 | 2004-06-03 | 2004-12-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-12-03 | 2008-06-03 | 2008-12-03 | $7700.00 | Window Closed / Lapsed |