Three-dimensional system and method for connection component labeling

• US 8,340,421 B2
• Filed: 03/30/2008
• Issued: 12/25/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): Tran, Phuoc
• Application Number:
  US12/058,706
• Publication Number:
  US 20090196508A1
• Time in Patent Office: 1,731 Days
• Field of Search: 382/173, 382/180, 382/203
• US Class Current: 382/173
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices

Abstract

Embodiments disclosed include methods and systems for three dimensional connected component labeling, including determining a location value for each of one or more labels, each location value identifying a maximum “y” extent and a maximum “z” extent of an associated label region; storing each of the one or more labels that refer to areas subsumed in a determination of the maximum y extent in the maximum “z” extent as a yzMax location value; buffering in a frame buffer the one or more of labels; and providing access via a three-dimensional kernel to one or more values in a current line buffer and/or a current array and/or a previous array.

Claims

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

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

y”

extent and a maximum “

z”

extent of an associated label region;

b. storing each of the one or more labels that refer to areas subsumed in a determination of the maximum y extent in the maximum “

z”

extent as a yzMax location value;

c. buffering in a frame buffer the one or more of labels; and

providing access via a three-dimensional kernel to one or more values in a current line buffer and/or a current array and/or a previous array.

2. The method of claim 1 further comprising:

propagating each yzMax location value to propagate from root label to root label of each region such that each region root contains a yzMax value that is a function of (y, z) coordinates.

3. The method of claim 1 wherein the one or more location values are received from one or more raster-organized data arrays wherein the data is image data arranged to display an image.

4. The method of claim 1 wherein one or more region features are stored in a memory structure accessible by the line buffer to enable random access by the one or more labels according to the location values.

5. The method of claim 1 wherein the location values are stored in the memory structure to enable ordering the location values based on one or more of size and/or shape and/or time dimensions.

6. A computer program product comprising a non-transitory computer readable medium configured to perform one or more acts for performing three dimensional labeling of one or more labels the one or more acts comprising:

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

y”

extent and a maximum “

z”

extent of an associated label region;

b. one or more instructions for storing each of the one or more labels that refer to areas subsumed in a determination of the maximum y extent and maximum z extent as a yzMax location value;

c. one or more instructions for buffering in a frame buffer the one or more of labels; and

d. one or more instructions for providing access via a three-dimensional kernel to one or more values in a current line buffer and/or a current array and/or a previous array.

7. The computer program product of claim 6 further comprising:

one or more instructions for propagating each yzMax location value to propagate from root value to root value of each region such that each region root contains a yzMax value that is a function of (y, z) coordinates.

8. The computer program product of claim 6 wherein the one or more instructions for determining a location value for each of one or more labels, each location value identifying a maximum “

y”

extent and a maximum “

z”

extent of an associated label region includes receiving the location value from one or more raster-organized data arrays wherein the data is image data arranged to display an image.

9. The computer program product of claim 6 wherein the one or more instructions for providing access via a three-dimensional kernel to a position in a current line buffer and/or a current array and a previous array include:

one or more instructions for storing one or more region features in a memory structure accessible by the line buffer to enable random access by the one or more labels according to the location values.

10. The computer program product of claim 6 wherein the one or more instructions for determining a location value for each of one or more labels, each location value identifying a maximum “

y”

extent and a maximum “

z”

extent of an associated label region include;

one or more instructions for the location values are stored in the memory structure to enable ordering the location values based on one or more of size and/or shape and/or time dimensions.

11. A method for a three dimensional kernel for performing connected component labeling, the method comprising:

accessing one or more values located in corresponding locations in a first two-dimensional array and a second two-dimensional array;

performing kernel operations on one or more successive array locations in each of the first and second two-dimensional arrays; and

comparing the one or more accessed values to determine one or more relationships for three-dimensional connected component labeling.

12. The method of claim 11 wherein the performing kernel operations includes designating no more than four locations arranged in three perpendicular directions about a center location to create the three dimension kernel;

and moving the three-dimensional kernel over data in a single two-dimensional representation of the first and second two dimensional arrays.

13. The method of claim 11 wherein the performing kernel operations includes designating no more than four locations arranged in three perpendicular directions about a center location to create the three dimension kernel to create a minimum kernel capable of three dimensional connected component labeling using a single frame buffer and single line buffer.

14. The method of claim 13 wherein the three-dimensional kernel enables extending a third dimension indefinitely, wherein said extension of the third dimension is independent of requiring additional resources.

15. The method of claim 14 wherein the resources include one or more of processing, memory, power, and/or clocking requirements.

16. A computer program product comprising a non-transitory computer readable medium configured to perform one or more acts for a three dimensional kernel for three dimensional connected component labeling, the one or more acts comprising:

a. one or more instructions for accessing one or more values located in corresponding locations in a first two-dimensional array and a second two-dimensional array;

b. one or more instructions for performing kernel operations on one or more successive array locations in each of the first and second two-dimensional arrays; and

c. one or more instructions for comparing the one or more accessed values to determine one or more relationships for three-dimensional connected component labeling.

17. The computer program product of claim 16 wherein the one or more instructions for performing kernel operations includes one or more instructions for designating no more than four locations arranged in three perpendicular directions about a center location to create the three dimension kernel;

and one or instructions for moving the three-dimensional kernel over data in a single two-dimensional representation of the first and second two-dimensional arrays.

18. The computer program product of claim 16 wherein the one or more instructions for performing kernel operations includes one or more instructions for designating no more than four locations arranged in three perpendicular directions about a center location to create the three dimension kernel to create a minimum kernel capable of three dimensional connected component labeling using a single frame buffer and single line buffer.

19. The computer program product of claim 18 wherein the three-dimensional kernel enables one or more instructions for extending a third dimension indefinitely, wherein said extension of the third dimension is independent of requiring additional resources.

20. The computer program product of claim 19 wherein the resources include one or more of processing, memory, power, and/or clocking requirements.