Label reuse method and connected component labeling

• US 8,577,143 B2
• Filed: 07/18/2012
• Issued: 11/05/2013
• Est. Priority Date: 02/04/2008
• Status: Expired due to Fees

• Current Assignee: Eyep, Inc.
• Original Assignee: Eyep, Inc.
• Inventors: Sullender, Craig
• Primary Examiner(s): Fitzpatrick, Atiba O
• Application Number:
  US13/552,597
• Publication Number:
  US 20120284482A1
• Time in Patent Office: 475 Days
• Field of Search: 382173-180, 348143-153
• 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 reusing one or more labels in a connected component labeling system, the method comprising:

a. 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 by 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; and

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; and

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

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

c. reusing the one or more labels subsumed in the determination of the yMax location value.

2. The method for reusing one or more labels in a connected component labeling system of claim 1 further comprising:

a. 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

b. 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.

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

a. 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 by 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;

by 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;

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

c. reusing the one or more labels subsumed in the determination of the yMax location value.

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

a. 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 by 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;

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

c. reusing the one or more labels subsumed in the determination of the yMax location value;

d. wherein the reusing of the one or more labels subsumed in the determination of the yMax location value includes;

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

ii. 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;

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

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

v. 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.

5. The method for reusing one or more labels in a connected component labeling system of claim 4 wherein the reusing of the one or more labels subsumed in the determination of the yMax location value includes:

a. determining whether the one or more labels are part of a tree structure; and

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

6. The method for reusing one or more labels in a connected component labeling system of claim 5 wherein the reusing of the one or more labels subsumed in the determination of the yMax location value includes:

a. 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.

7. The method for reusing one or more labels in a connected component labeling system of claim 4, further comprising:

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

assigning the determined yMax value as a root result.