Connected component labeling system and method

• US 8,280,167 B2
• Filed: 02/04/2008
• Issued: 10/02/2012
• 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): Bayat, Ali
• Application Number:
  US12/025,738
• Publication Number:
  US 20090196502A1
• Time in Patent Office: 1,702 Days
• Field of Search: 382/164, 382/171, 382/173, 382/175, 382/176, 382/177, 382/178, 382/179, 382/180, 382/204, 382/305, 707/790, 707/812
• 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 for connected component labeling including labeling groups of raw data as one or more regions, the labeling including designating one or more data structures as containing information about the one or more regions; designating one or more of the regions as one or more subregions to expose a spatial distribution of one or more region features; and arranging at least one memory array with a 1:1 correspondence to a data array associated with the raw data to enable one or more data structures to include feature labels of the one or more subregions, the 1:1 correspondence enabling acquisition of the one or more region features with a controllable precision.

Claims

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

labeling groups of raw data as one or more regions, the labeling including designating one or more data structures as containing information about the one or more regions;

designating one or more of the regions as one or more subregions to expose a spatial distribution of one or more features;

arranging at least one memory array organized to include at least one line buffer with a 1;

1 correspondence to the raw data, the arranging to enable one or more data structures to include at least one feature label of the one or more subregions with a controllable precision; and

recording in the one or more data structures one or more shapes and/or sizes of regions of previously segmented data.

2. The method of claim 1 wherein the one or more features are stored in the one or more data structures, the one or more data structures configured to minimize memory requirements for actions anticipatory to connected component labeling.

3. The method of claim 2 wherein the one or more actions anticipatory to connected component labeling include segmentation.

4. The method of claim 1 wherein the labeling groups of raw data as one or more regions includes incorporating at least one segmentation rule for determining which data elements of the raw data are related to enable labeling during segmentation and/or relabeling without regard to any prior processing.

5. The method of claim 1 wherein the labeling groups of raw data as one or more regions includes operating on text data, the labeling including designating the at least one feature by operating on one or more related segments sharing one or more textual qualities.

6. The method of claim 1 wherein the labeling groups of raw data as one or more regions includes arranging the raw data in raster order.

7. The method of claim 6 wherein the raster order includes providing rows of width w stacked from top to bottom with a height of h rows.

8. The method of claim 6 wherein the raster order includes providing image data capable of being referenced by pixel location at x width and y height as p(x, y).

9. The method of claim 1 wherein the providing a memory array with a 1:

1 correspondence to a data array includes enabling linear addressing in the memory array.

10. The method of claim 9 wherein the linear addressing enables spatial conversion and/or memory address offset functions.

11. The method of claim 9 wherein the linear addressing enables combining of the at least one feature independent of requiring additional memory space in the memory array and independent of memory array space required during a prior region designation.

12. The method of claim 9 wherein the linear addressing includes providing one or more region metrics via an indexing scheme using an original data label providing a raw data index, a data label index, a region label index and a region information index.

13. The method of claim 12 wherein the assigning the one or more region labels as a function of label demand includes:

storing the one or more region labels in a memory array including at least four types of memory locations, the four types of memory locations for one or more of raw data, data labels, region labels, and region information.

14. The computer program product of claim 13 wherein the independence of the one or more region information indexes and the one or more region labels further enables root finding operations performed on a line-by-line basis in the memory array.