LABEL REUSE METHOD AND SYSTEM FOR CONNECTED COMPONENT LABELING

• US 20090196503A1
• Filed: 02/08/2008
• Published: 08/06/2009
• Est. Priority Date: 02/04/2008
• Status: Active Grant

• Current Assignee: Eyep, Inc.
• Original Assignee: Eyep, Inc.
• Inventors: Sullender, Craig
• Granted Patent: US 8,249,348 B2
• Time in Patent Office: Days
• US Class Current: 382/180
• CPC Class Codes: G06T 1/60 Memory management
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds

Abstract

Embodiments disclosed include methods and systems for reusing labels for connected component labeling including assigning one or more labels to one or more groups of raw data representing one or more regions by designating one or more data structures as containing information about the one or more regions; connecting the one or more labels determined to be related; choosing a root label for the connected one or more labels, the root label determined by locating an earliest data element from the one or more groups of raw data; altering a label list of the one or more labels, the label list altered by flagging the root label to include a region label index; and overwriting one or more region label indexes according to the root label.

Claims

1. A method for connected component labeling, the method comprising:

assigning one or more labels to one or more groups of raw data representing one or more regions by designating one or more data structures as containing information about the one or more regions;

connecting the one or more labels determined to be related;

choosing a root label for the connected one or more labels, the root label determined by locating an earliest data element from the one or more groups of raw data;

altering a label list of the one or more labels, the label list altered by flagging the root label to include a region label index; and

overwriting one or more region label indexes according to the rot label.

2. The method of claim 1 wherein the choosing a root label for the connected one or more labels, the root label determined by locating an earliest data element from the one or more groups of raw data includes:

determining the earliest data element according to a lowest result for ((y*w)+x) wherein y represents a row value, x represents a column value, and w represents a width value.

3. The method of claim 2 wherein the determining the earliest data element according to a first-in-first-out (FIFO) algorithm for raster-organized data arrays.

4. The method of claim 1 wherein the overwriting one or more region label indexes according to the root label includes:

providing a pointer to the root label.

5. The method of claim 1 wherein the altering a label list of the one or more labels, the label list altered by flagging the root label to include a region label index includes:

flagging the root label by setting an unused memory bit when a prior root label no longer points to itself.

6. The method of claim 1 wherein the choosing a root label for the connected one or more labels, the root label determined by locating an earliest data element from the one or more groups of raw data includes:

flagging the root label by setting an unused memory bit when a prior root label no longer points to itself.

7. A method for reusing one or more labels in a connected component labeling system, the method comprising:

determining a location value for each of the one or more labels, each location value identifying a maximum “

y”

extent (“

yMax”

) of an associated label region;

determining which of the one or more labels refer to areas subsumed in a determination of the yMax location value; and

reusing the one or more labels and/or region information memory location values subsumed in the determination of the yMax location value.

8. The method of claim 7 wherein the determining a location value for each of the one or more labels, each location value identifying a maximum “

y”

extent (“

yMax”

) of an associated label region includes;

assigning as the yMax value a y coordinate for each label of the one or more labels located in a memory, the y coordinate assignment based on a row level in the memory.

9. The method of claim 8 wherein the assigning as the yMax value a y coordinate for each label of the one or more labels located in a memory, the y coordinate assignment based on a row level in the memory includes:

determining the y coordinate as a function of the row level in the memory wherein the memory is a data buffer configured to receive label and region information in a receiving row.

10. The method of claim 9 wherein the assigning as the yMax value a y coordinate for each label of the one or more labels located in a memory, the y coordinate assignment based on a row level in the memory includes:

determining the row level according to raster order of rows wherein the rows of are formed by moving data up from a bottom row to a top row.

11. The method of claim 8 wherein the assigning as the yMax value a y coordinate for each label of the one or more labels located in a memory, the y coordinate assignment based on a row level in the memory includes:

receiving label and region information in the memory determining the y coordinate as a function of the row level in the memory wherein the memory is a data buffer configured to receive label and region information in a bottom row.

12. The method of claim 7 further comprising:

comparing two or more yMax values to determine a maximum yMax value; and

assigning the determined yMax value as a root result.

13. The method of claim 8 wherein the reusing the one or more labels and/or region information memory location values subsumed in the determination of the yMax location value includes:

determining that a row of the memory is fully processed and/or about to be overwritten;

for each label in the fully processed and/or about to be overwritten row, comparing each yMax value to a y coordinate for the row;

for each yMax value that matches the y coordinate, designating an associated label as an available label;

for each yMax value that does not match the y coordinate, determining that the yMax value is associated with a series of labels;

comparing each yMax value in the series of labels to the y coordinate; and

for each yMax value in the series of labels that matches the y coordinate, designating an associated label as an available label.

14. The method of claim 7 further comprising:

storing a location of each root in an associated region information location to enable label comparison during subsuming of label data.

15. The method of claim 8 wherein the reusing the one or more labels and/or region information memory location values subsumed in the determination of the yMax location value includes:

determining whether the one or more labels and/or region information memory location values are part of a tree structure; and

locating a root of the tree structure to enable reusing an associated label and/or region information memory location value associated with the root.

16. The method of claim 8 wherein the reusing the one or more labels and/or region information memory location values subsumed in the determination of the yMax location value includes:

enabling each yMax location value to propagate from root value to root value of each region such that each region root contains a yMax location value that is an actual maximum y coordinate.

19. The connected component labeling system of claim 10 further comprising:

a region queue coupled to the label list, the region queue configured to send and receive a plurality of region information locations equal to a number of possible roots; and

a region information module coupled to the label list, the region information module configured to output region information wherein the maximum number of region information locations is equal to the number of possible roots, the number of region information locations being a fraction of the maximum number of region information locations.

17. A computer program product comprising a computer readable medium configured to perform one or more acts for performing connected component labeling, the one or more acts comprising:

one or more instructions for determining a location value for each of the one or more labels, each location value identifying a maximum “

y”

extent (“

yMax”

) of an associated label region;

one or more instructions for determining which of the one or more labels refer to areas subsumed in a determination of the yMax location value; and

one or more instructions for reusing the one or more labels and/or region information memory location values subsumed in the determination of the yMax location value.

18. A connected components labeling system comprising:

a processor;

a memory coupled to the processor, the memory configured to include;

a label buffer configured to be initialized with a sequential count at the beginning of an operation for each array of input data in a raster order, the label buffer configured to hold current labels in use during an operation, the label buffer independent from the height of a connected region;

a label queue coupled to the label buffer, the label queue configured to contain a plurality of locations for holding one or more region labels for the connected components labeling system, the label queue configured to store one or more inactive, closed and/or not currently in use labels and to dispense one or more new labels to the label buffer and receive one or more closed labels no longer required, the one or more inactive labels; and

a label list coupled to the label buffer and the label queue, the label list configured to receive one or more closed labels no longer required by the label buffer.