US4876733A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for performing morphic transformations on image data in a general purpose computer
Assignee: International Business Machines Corp
•
Filing: 1989-03-07
•
Granted: 1989-10-24
•
Expires: 2009-03-07
Abstract
Abstract A method for carrying out morphic transformations with minimal memory accesses by using a two step convolving sequence to form an intermediate image. The components of the intermediate image are used in a recursive process to provide the desired final convolution. The word resulting from this convolution is then used to access a morphic transformation table in a second memory access for table hookup. The two step convolution requires a total of only two memory reads and two memory writes.
Inventors
- 👤 Mark A. Lavin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 21:05
CPC Classifications
G; G06; G06T; G06T5/00; G06T5/20
Claims Analysis
Total Claims: 8
Claim 1
Independent Claim
342 words
A method for use in a general purpose computer, for transforming an input image into an output image using a morphic transformation on image data comprised of pixels, said general purpose computer having a memory, said method comprising the steps of: storing original pixels of said input image in said memory, said original pixels being addressed by at least first and second indexes; mapping each of said original pixels in memory into an image of transformed pixels wherein each transformed pixel contains data representing an original pixel and neighboring pixels in a predefined neighborhood wherein, said mapping comprises; accumulating said original pixels accessed according to said first index to provide first accumulated values and storing said first accumulated values in said memory; shifting said first accumulated value stored in said memory by two and replacing said first accumulated value stored in said memory with said value shifted by two to provide a first replaced accumulated value; ORing said value of said original pixel with said first replaced accumulated value to provide a first ORred accumulated value and replacing said first accumulated value with said first ORred accumulated value in said memory; accumulating said original pixels accessed according to said second index to provide second accumulated values and storing said second accumulated values in said memory; shifting said second accumulated values a second predetermined number of bits to provide a shifted second accumulated value; and ORing said first ORred accumulated value in said memory to said second accumulated value to provide a second added accumulated value and replacing said value in said memory with said second added accumulated value; searching a lookup table using said second added accumulated value as an index and storing a value pointed to in said lookup table by said index in an output array in said memory; and repeating said steps of mapping and searching for each of said original pixels; and providing an output image having pixels corresponding to values in said output array, thereby requiring only four accesses to said memory to determine said morphic transformation.
Claim 2
Independent Claim
342 words
A method for use in a general purpose computer, for transforming an input image into an output image using a morphic transformation on image data comprised of pixels, said general purpose computer having a memory, said method comprising the steps of: storing original pixels of said input image in said memory, said original pixels being addressed by at least first and second indexes; mapping each of said original pixels in memory into an image of transformed pixels wherein each transformed pixel contains data representing an original pixel and neighboring pixels in a predefined neighborhood wherein, said mapping comprises; accumulating said original pixels accessed according to said first index to provide first accumulated values and storing said first accumulated values in said memory; shifting said first accumulated value stored in said memory by two and replacing said first accumulated value stored in said memory with said value shifted by two to provide a first replaced accumulated value; ORing said value of said original pixel with said first replaced accumulated value to provide a first ORred accumulated value and replacing said first accumulated value with said first ORred accumulated value in said memory; accumulating said original pixels accessed according to said second index to provide second accumulated values and storing said second accumulated values in said memory; shifting said second accumulated values a second predetermined number of bits to provide a shifted second accumulated value; and ORing said first ORred accumulated value in said memory to said second accumulated value to provide a second added accumulated value and replacing said value in said memory with said second added accumulated value; searching a lookup table using said second added accumulated value as an index and storing a value pointed to in said lookup table by said index in an output array in said memory; and repeating said steps of mapping and searching for each of said original pixels; and providing an output image having pixels corresponding to values in said output array, thereby requiring only four accesses to said memory to determine said morphic transformation.
Claim 3
Dependent Claim
60 words
The method according to claim 1 wherein said said original pels are addressed by first and second indices and said transformation is performed on an h by w neighborhood of said two dimensional array of data, h being aligned with said first index and w being aligned with said second index, wherein said first predetermined number is equal to 2h.
Claim 4
Dependent Claim
27 words
The method according to claim 2 further comprising the step of retaining only 2 h -1 least significant bits of said values stored in said temporary memory.
Claim 5
Dependent Claim
32 words
The method according to claim 3 further comprising the step of retaining only 2 hw -1 least significant bits of said second added accumulated value prior to its use as an index.
Claim 6
Dependent Claim
33 words
The method according to claim 4 wherein the step of retaining only said 2 h -1 least significant bits comprises ANDing said value in temporary memory multiplied by two, with 2 h -1.
Claim 7
Dependent Claim
36 words
The method according to claim 5 wherein the step of retaining only said 2 hw -1 least significant bits of said second added accumulated value comprises ANDing said second added accumulated value with 2 hw -1.
Claim 8
Dependent Claim
19 words
The method according to claim 6 wherein said neighborhood is the Moore neighborhood and h and w equal 3.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-10-23 | 1993-04-24 | 1993-10-24 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-10-23 | 1997-04-24 | 1997-10-24 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-10-23 | 2001-04-24 | 2001-10-24 | $7700.00 | Window Closed / Lapsed |