Techniques for connected component labeling

• US 9,042,652 B2
• Filed: 11/01/2012
• Issued: 05/26/2015
• Est. Priority Date: 11/01/2012
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Gupta, Niraj, Agam, Oren, Eitan, Benny, Hagog, Mostafa
• Primary Examiner(s): Hung, Yubin
• Application Number:
  US13/666,913
• Publication Number:
  US 20140119657A1
• Time in Patent Office: 936 Days
• Field of Search: 382/164, 382/173, 382/180
• US Class Current: 382/180
• CPC Class Codes: G06T 2200/28 involving image processing hardware
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices

Abstract

An apparatus may include a memory, a processor circuit, and a connected component labeling module. The connected component labeling module may be operative of the processor circuit to determine one or more connected components during reading of an image comprising a multiplicity of pixels from the memory, assign a label to a plurality of pixels of the multiplicity of pixels, generate one or more label connections for a respective one or more labels, each label connection linking a higher label to a lowest label for the same connected component, and write to the memory for each label of the one or more labels a lowest label as defined by the label connection for the each label after a label is assigned to each pixel.

Claims

1. An apparatus, comprising:

a memory;

a processor circuit coupled to the memory; and

a connected component labeling module operative of the processor circuit to;

determine one or more connected components during reading of an image comprising a multiplicity of pixels from the memory;

assign a label to a plurality of pixels of the multiplicity of pixels;

generate one or more label connections for a respective one or more labels, each label connection linking a higher label to a lowest label for the same connected component;

write to the memory for each label of the one or more labels a lowest label as defined by the label connection for the each label after a label is assigned to each pixel;

read the label connections from a running buffer when a maximum number of updated labels supported by the running buffer is reached;

mark a label position corresponding to labels updated; and

determine a lowest label available for currently stored labels in the running buffer.

2. The apparatus of claim 1, the connected component labeling module operative on the processor circuit to generate one or more bounding boxes for the respective one or more labels after updating the label connection.

3. The apparatus of claim 2, comprising:

a label connection buffer operative to store the one or more label connections; and

a bounding box buffer operative to store the one or more bounding boxes.

4. The apparatus of claim 3, the label connection buffer comprising:

a running buffer to store one or more label connections for respective one or more labels currently in use; and

a cache to cache label connections not stored in the running buffer.

5. The apparatus of claim 3, the bounding box buffer comprising:

another running buffer to store one or more bounding boxes for a respective one or more labels currently in use, the apparatus; and

a cache to cache bounding boxes not stored in the other running buffer.

6. The apparatus of claim 1, the connected component labeling module operative on the processor circuit to determine a position of an edge of a contour of the one or more labels.

7. The apparatus of claim 1, the connected component labeling module operative on the processor circuit to:

read the one or more label connections after a label is assigned to each pixel;

save to the memory only a lowest label for each label according to the label connection for that label; and

delete from the memory any label that is higher than the lowest label for the each label.

8. The apparatus of claim 1, comprising a content addressable memory to implement the running buffer, the running buffer operative to temporarily store the one or more label connections and respective one or more updated labels.

9. The apparatus of claim 1, comprising a digital display operative to present the image.

10. At least one non-transitory computer-readable storage medium comprising a plurality of instructions that, when executed, cause a system to:

determine one or more connected components during reading of an image comprising a multiplicity of pixels from the memory;

assign a label to a plurality of pixels of the multiplicity of pixels;

generate one or more label connections for a respective one or more labels, each label connection linking a higher label to a lowest label for the same connected component;

write to the memory for each label of the one or more labels a lowest label as defined by the label connection for the each label after a label is assigned to each pixel;

read the label connections from a running buffer when a maximum number of updated labels supported by the running buffer is reached;

mark a label position corresponding to labels updated; and

determine a lowest label available for currently stored labels in the running buffer.

11. The at least one non-transitory computer-readable storage medium of claim 10 comprising instructions that, when executed, cause a system to generate one or more bounding boxes for the respective one or more labels after updating the label connection.

12. The at least one non-transitory computer-readable storage medium of claim 10 comprising instructions that, when executed, cause a system to store the one or more label connections and the one or more bounding boxes.

13. The at least one non-transitory computer-readable storage medium of claim 10 comprising instructions that, when executed, cause a system to:

store in the running buffer one or more label connections for respective one or more labels currently in use; and

cache label connections not stored in the running buffer.

14. The at least one non-transitory computer-readable storage medium of claim 10 comprising instructions that, when executed, cause a system to:

store in another running buffer one or more bounding boxes for respective one or more labels currently in use; and

cache bounding boxes not stored in the other running buffer.

15. The at least one non-transitory computer-readable storage medium of claim 10 comprising instructions that, when executed, cause a system to determine a position of an edge of a contour of the one or more labels.

16. The at least one non-transitory computer-readable storage medium of claim 10 comprising instructions that, when executed, cause a system to:

read the one or more label connections after a label is assigned to each pixel;

save to the memory only a lowest label for each label according to the label connection for that label; and

delete from the memory any label that is higher than the lowest label for the each label.

17. The at least one non-transitory computer-readable storage medium of claim 10 comprising instructions that, when executed, cause a system to temporarily store the one or more label connections and respective one or more updated labels in the running buffer, the running buffer, the running buffer being implemented by a content addressable memory.

18. A computer-implemented method, comprising:

determining one or more connected components during reading of an image comprising a multiplicity of pixels from memory;

assigning a label to a plurality of pixels of the multiplicity of pixels;

generating one or more label connections for a respective one or more labels, each label connection linking a higher label to a lowest label for the same connected component;

writing to the memory for each label of the one or more labels a lowest label as defined by the label connection for the each label after a label is assigned to each pixel;

reading the label connections from a running buffer when a maximum number of updated labels supported by the running buffer is reached;

marking a label position corresponding to labels updated; and

determining a lowest label available for currently stored labels in the running buffer.

19. The computer implemented method of claim 18 comprising generating one or more bounding boxes for the respective one or more labels after updating the label connection.

20. The computer implemented method of claim 18, comprising:

storing one or more label connections in a first buffer; and

storing the one or more bounding boxes in a second buffer.

21. The computer implemented method of claim 18 comprising:

storing one or more label connections for respective one or more labels currently in use in the running buffer; and

caching label connections not stored in the running buffer.

22. The computer implemented method of claim 18 comprising:

storing one or more bounding boxes for respective one or more labels currently in use in another running buffer; and

caching label connections not stored in the other running buffer.

23. The computer implemented method of claim 18 comprising determining a position of an edge of a contour of the one or more labels.

24. The computer implemented method of claim 18 comprising:

reading the one or more label connections after a label is assigned to each pixel;

saving to the memory only a lowest label for each label according to the label connection for that label; and

deleting from the memory any label that is higher than the lowest label for the each label.