Hardware-amenable connected components labeling

Patent metadata

Field	Value
Publication number	US-9508003-B2
Application number	US-201414253696-A
Country	US
Kind code	B2
Filing date	Apr 15, 2014
Priority date	Apr 15, 2013
Publication date	Nov 29, 2016
Grant date	Nov 29, 2016

Abstract

The subject disclosure is directed towards performing connected components in hardware, such as an FPGA, which is facilitated by a linked list structure that does not grow. During a connected components graph labeling process, when a merge is encountered, the data structure comprising labels and associated equivalency data swaps the equivalency data of the two vertices whose different labels produced the merge condition.

First claim

What is claimed is:

1. A method comprising:
performing collected components processing, wherein performing collected components processing includes:
maintaining a relabeling data structure comprising labels;
labeling vertices of a graph based upon labeling rules;
detecting a merge condition when a first set of one or more pixels has two intersecting arcs connecting the first set of one or more pixels to two neighbor pixels labeled with conflicting labels;
accessing the relabeling data structure based upon the merge condition; and
propagating a label from one of the two neighbor pixels to the first one or more pixels through associating an inherited label with the first one or more pixels in which the inherited label is inherited from one of the two neighbor pixels when a disparity threshold comparison with the one of the two neighbor pixels is met.

2. The method of claim 1 wherein the graph represents pixels of an image, and wherein the method further comprises traversing the graph in raster order to reach a selected pixel.

3. The method of claim 1 wherein accessing the relabeling data structure based upon the merge condition comprises swapping equivalency data associated with one labeled pixel with equivalency data associated with another labeled pixel.

4. The method of claim 3 wherein swapping the equivalency data comprises generating a closed loop.

5. The method of claim 1 wherein accessing the relabeling data structure based upon the merge condition comprises modifying at least one relabel data entry.

6. A system comprising:
a label management component; and
a label assignment component for communication with the label management component, the label assignment component configured to:
evaluate disparity data between a first pixel and two neighbor pixels;
based upon the disparity data, associate a label with the first pixel, wherein associating a label with the first pixel comprises associating an inherited label with the first pixel in which the inherited label is inherited from one neighbor pixel when a disparity threshold comparison with the one neighbor pixel is met; and
communicate the associated label of the first pixel to the label management component.

7. The system of claim 6 , wherein associating a label with the first pixel comprises generating and associating a new label with the first pixel when a disparity threshold comparison with either of the neighbor pixels is not met.

8. The system of claim 6 , wherein associating a label with the first pixel additionally comprises associating an inherited label with the first pixel when a disparity threshold comparison with another neighbor pixel is not met.

9. The system of claim 6 , wherein associating a label with the first pixel comprises associating an inherited label with the first pixel in which the inherited label is inherited from one neighbor pixel when a disparity threshold comparison with both neighbor pixels is met and both neighbor pixels have the same label.

10. The system of claim 6 , wherein associating a label with the first data element comprises associating an inherited label with the first pixel in which the inherited label is inherited from one neighbor pixel when a disparity threshold comparison with both neighbor pixels is met and both neighbor pixels do not have the same label, and to perform a merge operation to associate both neighbor pixels with a common label.

11. The system of claim 6 , wherein the label management component computes in raster-scan order.

12. The system of claim 6 , wherein the label management component buffers one row of both disparity and label information.

13. The system of claim 12 , further comprising a memory area having a queue that includes a disparity cache and a label cache, the queue having N stages to hold an entire width of an image and storing values for locations side by side.

14. One or more computer-storage memories comprising computer-executable components, the components comprising:
a label management component; and
a label assignment component that when executed by at least one processor causes the at least one processor to:
communicate with the label management component to obtain label data associated with pixels;
enable stream processing through buffering a row of the data elements, said stream processing providing access to disparity data between a first pixel and two neighbor pixels;
evaluate the disparity data between the first pixels and the two neighbor pixels; and
based upon the disparity data, communicate with the label management component to associate a label with the first pixel, wherein associating a label with the first pixel comprises associating an inherited label with the first pixel in which the inherited label is inherited from one neighbor pixel when a disparity threshold comparison with the two neighbor pixels is met.

15. The one or more computer-storage memories of claim 14 , wherein associating a label with the first pixel comprises generating and associating a new label with the first pixel when the disparity threshold comparison with either of the neighbor pixels is not met.

16. The one or more computer-storage memories of claim 14 , wherein associating a label with the first pixel comprises associating the inherited label with the first pixel in which the inherited label is inherited from one neighbor pixel when the disparity threshold comparison with another neighbor pixel is not met.

17. The one or more computer-storage memories of claim 14 , wherein associating a label with the first pixel comprises associating the inherited label with the first pixel when the disparity threshold comparison with both neighbor pixels is met and both neighbor pixels have the same label.

18. The one or more computer-storage memories of claim 14 , wherein associating a label with the first pixel comprises associating the inherited label with the first pixel in which the inherited label is inherited from one neighbor pixel when the disparity threshold comparison with both neighbor pixels is met and both neighbor pixels do not have the same label, and to perform a merge operation to associate both neighbor pixels with a common label.

19. The one or more computer-storage memories of claim 14 , wherein the label management component, when executed by at least one processor, causes the at least one processor to:
determine whether a current label points to itself;
upon determining that the current label points to itself, determine whether a destination label has been visited;
upon determining that the destination label points to itself, travel to the initial label; and
upon determining that the destination label does not point to itself, analyze the destination address.

20. The one or more computer-storage memories of claim 14 , wherein the label management component, when executed by at least one processor, causes the at least one processor to buffer one row of both disparity and label information.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Eguro Kenneth Hiroshi
• Smith George E
• Swilley Shawn Michael

Classifications

• G06F2218/12

  Classification; Matching · CPC title

• H04N25/611

  Correction of chromatic aberration · CPC title

• H04N23/11

  for generating image signals from visible and infrared light wavelengths · CPC title

• H04N23/56

  provided with illuminating means · CPC title

• G02B27/44

  Grating systems; Zone plate systems (G02B27/46 takes precedence) · CPC title