Region-growing algorithm

• US 8,842,898 B2
• Filed: 04/22/2013
• Issued: 09/23/2014
• Est. Priority Date: 02/01/2010
• Status: Active Grant

• Current Assignee: Covidien LP (Medtronic Plc)
• Original Assignee: Covidien LP (Medtronic Plc)
• Inventors: Averbuch, Dorain, Kreinin, Yuri
• Primary Examiner(s): AZARIAN, SEYED H
• Application Number:
  US13/867,217
• Publication Number:
  US 20130236076A1
• Time in Patent Office: 519 Days
• Field of Search: 382/100, 382/103, 382106-107, 382128-134, 382154-155, 382/168, 382172-173, 382/181, 382/199, 382/224, 382/232, 382/254, 382/276, 382/305, 382/312, 378/4, 378/21, 600/425, 600/415, 600/432
• US Class Current: 382/131
• CPC Class Codes: G06T 2207/10081 Computed x-ray tomography [CT]
• CPC Class Codes: G06T 2207/20156 Automatic seed setting
• CPC Class Codes: G06T 2207/30061 Lung
• CPC Class Codes: G06T 7/0012 Biomedical image inspection
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/136 involving thresholding
• CPC Class Codes: G06T 7/187 involving region growing; involving region merging; involving connected component labelling
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds

Abstract

A region growing algorithm for controlling leakage is presented including a processor configured to select a starting point for segmentation of data, initiate a propagation process by designating adjacent voxels around the starting point, determine whether any new voxels are segmented, count and analyze the segmented new voxels to determine leakage levels, and identify and record segmented new voxels from a previous iteration when the leakage levels exceed a predetermined threshold. The processor is further configured to perform labeling of the segmented new voxels of the previous iteration, select the segmented new voxels from the previous iteration when the leakage levels fall below the predetermined threshold, and create a voxel list based on acceptable segmented voxels found in the previous iteration.

Claims

1. A region growing algorithm for controlling leakage comprising a processor configured to:

select a starting point for segmentation of data;

initiate a propagation process by designating adjacent voxels around the starting point;

determine whether any new voxels are segmented;

count and analyze the segmented new voxels to determine leakage levels;

identify and record segmented new voxels from a previous iteration when the leakage levels exceed a predetermined threshold;

perform labeling of the segmented new voxels of the previous iteration;

select the segmented new voxels from the previous iteration when the leakage levels fall below the predetermined threshold; and

create a voxel list based on acceptable segmented voxels found in the previous iteration.

2. The region growing algorithm of claim 1, wherein the starting point is a point in a trachea.

3. The region growing algorithm of claim 2, wherein the starting point is a single voxel inside the trachea that meets a high threshold value.

4. The region growing algorithm of claim 3, wherein the single voxel is surrounded by 26 adjacent voxels, 17 voxels extending in a direction of growth.

5. The region growing algorithm of claim 1, wherein the data is computed tomography (CT) scan data.

6. The region growing algorithm of claim 1, wherein voxels in a distal direction of the starting point are segmented.

7. The region growing algorithm of claim 1, wherein the voxel list is used to create a virtual model of an anatomical structure.

8. A region growing algorithm for creating a virtual model of an anatomical structure, the region growing algorithm comprising a processor configured to:

provide a three-dimensional image volume created from a plurality of two-dimensional images;

set a threshold value, above which is indicative that an imaged voxel is not representing tissue;

select a seed point voxel in the three-dimensional image volume as a starting point;

perform a plurality of first iterations;

detect when a number of voxels segmented equals zero; and

perform a plurality of second iterations on leaked objects, if any, until the number of voxels segmented equals zero.

9. The region growing algorithm of claim 8, wherein each of the plurality of first iterations includes segmenting voxels, located adjacent the seed point in a plurality of directions, that meet or exceed the threshold value.

10. The region growing algorithm of claim 9, wherein each of the plurality of first iterations further includes determining a number of voxels segmented in this iteration and if the number of voxels is greater than zero, determining whether the number is large enough to indicate leakage.

11. The region growing algorithm of claim 10, wherein each of the plurality of first iterations further includes removing leaked voxels and storing the leaked voxels as leaked objects for post-processing.

12. The region growing algorithm of claim 11, wherein each of the plurality of first iterations further includes identifying segmented voxels as seed points for a next iteration if no leakage is indicated.

13. The region growing algorithm of claim 8, wherein each of the plurality of second iterations include selecting voxels in a first iteration detecting leakage for a given leaked object as seed points.

14. The region growing algorithm of claim 13, wherein the plurality of second iterations further include reducing the threshold value.

15. The region growing algorithm of claim 14, wherein the plurality of second iterations further include segmenting voxels, located adjacent the seed points in a plurality of directions, that meet or exceed the threshold value.

16. The region growing algorithm of claim 15, wherein the plurality of second iterations further include determining a number of voxels segmented in this iteration and if the number of voxels is greater than zero, determining whether the number is large enough to indicate leakage.

17. The region growing algorithm of claim 16, wherein the plurality of second iterations further include removing leaked voxels and storing the leaked voxels as leaked objects for post-processing.

18. The region growing algorithm of claim 17, wherein the plurality of second iterations further include identifying segmented voxels as seed points for a next iteration if no leakage is indicated.

19. A region growing algorithm for creating a virtual model of an anatomical structure from a three-dimensional image volume, the region growing algorithm comprising a processor configured to:

use, as a threshold, an image voxel density indicative of a fluid;

segment voxels meeting the threshold;

create a virtual model of interior cavities or lumens of the anatomical structure;

perform a series of iterations using a segmented voxel as a seed point;

analyze non-segmented voxels adjacent the seed point in a plurality of directions;

repeat the iterations using newly segmented voxels from an iteration as seed points for a next iteration until no non-segmented voxels adjacent the seed points in the plurality of directions remain; and

separate voxels meeting the threshold but forming leaked objects that fail to satisfy one or more criteria based on comporting to a known anatomical structure.

20. The region growing algorithm of claim 19, wherein the processor further re-segments the leaked objects using a reduced threshold and separates voxels meeting the reduced threshold but forming the leaked objects.