INCREMENTAL CONTOUR-EXTRACTION SCHEME FOR BINARY IMAGE SEGMENTS

• US 20130259382A1
• Filed: 03/29/2012
• Published: 10/03/2013
• Est. Priority Date: 03/29/2012
• Status: Active Grant

• Current Assignee: Analog Devices, Inc.
• Original Assignee: Analog Devices, Inc.
• Inventors: MATH, ROOPA S.
• Granted Patent: US 9,275,467 B2
• Time in Patent Office: Days
• US Class Current: 382/195
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/181 involving edge growing; involving edge linking

Abstract

Contours of objects appearing in a digital image are extracted in a plurality of one-directional passes across the digital image. Each pass loads rows or columns of the image into a local memory, in the order they appear in the image, and analyzes them for the presence of portions of the full contour. The portions are then combined to create the full contour.

Claims

1. A method for extracting contours in a digital image, the method comprising:

performing a plurality of one-directional passes across the digital image, each pass comprising;

i. loading rows or columns of the digital image from an external memory to a local memory,

ii. identifying pixels in each row or column that correspond to a new contour of an object in the digital image or to a continuation of an already-found contour of the object, and

iii. adding the identified pixels to a list of contour pixels corresponding to the object for the current pass; and

combining the list of contour pixels from each pass into a full contour of the object.

2. The method of claim 1, wherein the plurality of one-directional passes consists of two, three, or four one-directional passes.

3. The method of claim 1, wherein the plurality of one-directional passes comprises a top-to-bottom pass, a bottom-to-top pass, a left-to-right pass, and a right-to-left pass.

4. The method of claim 1, wherein combining the list of contour pixels from each path comprises searching for an endpoint of a first contour portion in a second, adjacent contour portion and connecting the first and second contour portions at the endpoint.

5. The method of claim 1, wherein the digital image is a binary digital image.

6. The method of claim 1, wherein identifying pixels in each row or column that correspond to the new contour comprises identifying an object at a position in a current row or column, wherein the position was unoccupied by the object at a corresponding position in a previous row or column.

7. The method of claim 6, wherein identifying the object at the position in the current row or column comprises identifying a binary “

1”

digit and wherein the corresponding position in the previous row or column held a binary “

0”

digit.

8. The method of claim 1, wherein identifying pixels that correspond to a continuation of an already-found contour comprises (i) finding a beginning pixel or an end pixel of the already-found contour in a previous row or column and (ii) searching for a neighboring contour pixel in a current row or column.

9. A system for extracting contours in a digital image, the system comprising:

a local memory for storing data corresponding to the image; and

a processor comprising;

i. a memory management unit for loading a portion of the image from an external memory to the local memory, and

ii. an execution unit for executing instructions to (i) perform a plurality of one-directional passes across the digital image by analyzing the portion of the image, each pass identifying a portion of a contour of an object in the digital image and (ii) combine the portions of the contour into a full contour of the object.

10. The system of claim 9, wherein the portions of the image loaded from the external memory comprise rows or columns of the image.

11. The system of claim 9, wherein the processor is a digital-signal processor.

12. The system of claim 9, further comprising a high-speed interface that connects the local memory to the processor and a low-speed interface that connects the external memory to the processor.

13. The system of claim 9, wherein a size of the local memory is less than the size of the image.

14. The system of claim 9, wherein the instructions to combine the portions of the contour comprise instructions to search for an endpoint of a first contour portion in a second, adjacent contour portion and to connect the first and second contour portions at the endpoint.

15. The system of claim 9, wherein the plurality of one-directional passes consists of two, three, or four one-directional passes.

16. The system of claim 9, wherein the plurality of one-directional passes comprises a top-to-bottom pass, a bottom-to-top pass, a left-to-right pass, and a right-to-left pass.