Incremental contour-extraction scheme for binary image segments

• US 9,275,467 B2
• Filed: 03/29/2012
• Issued: 03/01/2016
• Est. Priority Date: 03/29/2012
• Status: Active Grant

• Current Assignee: Analog Devices, Inc.
• Original Assignee: Analog Devices, Inc.
• Inventors: Math, Roopa S.
• Primary Examiner(s): Mehta, Bhavesh
• Assistant Examiner(s): Mistry, Oneal R
• Application Number:
  US13/433,429
• Publication Number:
  US 20130259382A1
• Time in Patent Office: 1,433 Days
• Field of Search: None
• US Class Current: 1/1
• 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 first one-directional pass across the digital image, the 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 contour of an object in the digital image, and

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

iv. combining the list of contour pixels from the pass into the contour of the object; and

performing a second pass, comprising analyzing the contour pixels to classify the contour as a full closed-path contour comprising identifying an edge pixel for a first contour portion, identifying an edge pixel for a second contour portion, traversing the contour from the edge pixel of the second contour portion until finding a pixel having coordinates the same as the edge pixel for the first contour portion, identifying an overlapping portion of the first and second contour portions, and discarding the overlapping portion.

2. The method of claim 1, further comprising performing a second, third, or fourth one-directional pass, and combining contour pixels identified in the passes with the contour pixels identified in the first pass.

3. The method of claim 2, wherein combining the list of contour pixels from each pass 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.

4. The method of claim 1, further comprising performing a plurality of one-directional passes comprising a top-to-bottom pass, a bottom-to-top pass, a left-to-right pass, and a right-to-left pass.

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 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 in each row or column that correspond to the contour of the object comprises (i) finding a beginning pixel or an end pixel of an already-found contour in a previous row or column and (ii) searching for a neighboring contour pixel in a current row or column.

9. The method of claim 1, wherein:

traversing the contour comprises;

i. identifying the overlapping portion of the first and second contour portions, comprising accessing a first pixel of the first contour; and

ii. searching the second contour in the one direction from a second pixel of the second contour until a pixel is found having the same coordinates as the first pixel of the first contour to identify a first overlapping portion of the contours;

iii. discarding the overlapping portion;

iv. accessing a first pixel of the second contour;

v. searching the first contour in the one direction from a second pixel of the first contour until a pixel is found having the same coordinates as the first pixel of the second contour to identify a second overlapping portion of the contours; and

vi. combining two or more non-discarded portions of the first and second contours to create the full contour of the object.

10. The method of claim 1, wherein the first one-directional pass is a row-by-row or column-by-column pass.

11. 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 first one-directional pass across the digital image by analyzing the portion of the image, the pass identifying a portion of a contour of an object in the digital image, (ii) combine the portions of the contour into a complete contour of the object; and

(iv) analyze the contour to classify the contour as a full closed-path contour comprising identifying an edge pixel for a first contour portion, identifying an edge pixel for a second contour portion, and in a second pass traversing the contour from the edge pixel of the second contour portion until finding a pixel having coordinates the same as the edge pixel for the first contour portion, and identifying an overlapping portion of the first and second contour portions, and discarding the overlapping portions.

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

13. The system of claim 11, 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.

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

15. The system of claim 11, 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.

16. The system of claim 11, wherein the execution unit is further configured for executing instructions for performing one two, or three additional passes.

17. The system of claim 16, wherein the passes comprise a top-to-bottom pass, a bottom-to-top pass, a left-to-right pass, and a right-to-left pass.

18. The system of claim 11, wherein the execution unit is further configured for executing instructions for performing at least one additional one-directional pass across the digital image if the contour is not classified as a full closed-path contour, and merging contour pixels identified in the at least one additional pass with the contour pixels identified in the first pass.

19. The system of claim 11, wherein:

traversing the contour comprises;

i. identifying the overlapping portion of the first and second contour portions, comprising accessing a first pixel of the first contour; and

ii. searching the second contour in the one direction from a second pixel of the second contour until a pixel is found having the same coordinates as the first pixel of the first contour to identify a first overlapping portion of the contours;

iii. discarding the overlapping portion;

iv. accessing a first pixel of the second contour;

v. searching the first contour in the one direction from a second pixel of the first contour until a pixel is found having the same coordinates as the first pixel of the second contour to identify a second overlapping portion of the contours; and

vi. combining two or more non-discarded portions of the first and second contours to create the full contour of the object.

20. The system of claim 11, wherein the first one-directional pass is a row-by-row or column-by-column pass.

21. One or more non-transitory computer-readable storage mediums having stored thereon executable instructions operable to instruct a processor for:

performing a first one-directional pass across the digital image, the 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 contour of an object in the digital image, and

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

iv. combining the list of contour pixels from the pass into the contour of the object; and

performing a second pass, comprising analyzing the contour pixels to classify the contour as a full closed-path contour comprising identifying an edge pixel for a first contour portion, identifying an edge pixel for a second contour portion, traversing the contour from the edge pixel of the second contour portion until finding a pixel having coordinates the same as the edge pixel for the first contour portion, and identifying an overlapping portion of the first and second contour portions, and discarding the overlapping portion.

22. The one or more non-transitory computer-readable storage mediums of claim 21, wherein the instructions are further operable to instruct a processor for:

performing a second one-directional across the digital image to find a second contour, the pass comprising;

traversing the contour comprising;

i. identifying the overlapping portion of the first and second contour portions, comprising accessing a first pixel of the first contour; and

ii. searching the second contour in the one direction from a second pixel of the second contour until a pixel is found having the same coordinates as the first pixel of the first contour to identify a first overlapping portion of the contours;

iii. discarding the overlapping portion;

iv. accessing a first pixel of the second contour;

v. searching the first contour in the one direction from a second pixel of the first contour until a pixel is found having the same coordinates as the first pixel of the second contour to identify a second overlapping portion of the contours; and

vi. combining two or more non-discarded portions of the first and second contours to create the full contour of the object.