Region-growing algorithm
View Patent ↗A technique for automatically generating a virtual model of a branched structure using as an input a plurality of images taken of the branched structure. The technique employs an algorithm that avoids inaccuracies associated with sub-optimal threshold settings by “patching” holes or leaks created due to the inherent inconsistencies with imaging technology. By “patching” the holes, the algorithm may continue to run using a more sensitive threshold value than was previously possible.
1. A method for creating a virtual model of an anatomical structure from a three-dimensional image volume, comprising:
providing a three-dimensional image volume created from a plurality of two-dimensional images;
setting a threshold value, above which is indicative that an imaged voxel is not representing tissue;
selecting a seed point voxel in said three-dimensional image volume as a starting point;
performing a plurality of iterations, each iteration comprising:
segmenting voxels, immediately adjacent said seed point in all desired directions, that meet or exceed said threshold value;
determining a number of voxels segmented in this iteration;
if said number of voxels is greater than zero, determining whether said number is large enough to indicate leakage;
removing leaked voxels and storing them as leaked objects for post-processing
identifying segmented voxels as seed points for next iteration if no leakage is indicated;
detecting when said number of voxels segmented equals zero;
performing secondary iterations on leaked objects, if any, until said number of voxels segmented equals zero, said secondary iterations comprising:
selecting voxels in a first iteration detecting leakage for a given leaked object as seed points;
reducing said threshold value;
segmenting voxels, immediately adjacent said seed points in all desired directions, that meet or exceed said threshold value;
determining a number of voxels segmented in this iteration;
if said number of voxels is greater than zero, determining whether said number is large enough to indicate leakage;
removing leaked voxels and storing them as leaked objects for post-processing
identifying segmented voxels as seed points for next iteration if no leakage is indicated.
2. The method of claim 1 wherein selecting a seed point voxel in said three-dimensional image volume as a starting point comprises selecting a seed point voxel having a high threshold.
3. The method of claim 2 wherein selecting a seed point voxel having a high threshold comprises selecting a seed point voxel having a threshold indicative of air.
4. A computer readable medium storing instructions that when read by a computer perform a method for creating a virtual model of an anatomical structure from a three-dimensional image volume, comprising:
using as a threshold, an image voxel density indicative of a fluid;
segmenting only voxels meeting said threshold, thereby creating a virtual model of interior cavities and/or lumens of said anatomical structure, wherein the segmenting is performed as a series of iterations using a segmented voxel as a seed point and analyzing unsegmented voxels adjacent said seed point in a desired direction; and
repeating said iterations using newly segmented voxels from an iteration as seed points for a next iteration until no unsegmented voxels adjacent said seed points in said desired direction remain.
5. The method of claim 4 further comprising:
separating from said segmenting step, voxels meeting said threshold but forming objects, identified as leaked objects, that fail to meet criteria based on comporting to known anatomical structure.
6. The method of claim 5 further comprising:
resegmenting said leaked objects using a reduced threshold;
separating from said resegmenting step, voxels meeting said reduced threshold but forming objects, identified as leaked objects, that fail to meet criteria based on comporting to known anatomical structure;
adding resegmented voxels, not separated, to said virtual model.
7. The method of claim 6 comprising:
performing said resegmenting step as a series of iterations using a set of first-segmented voxels identified as part of a leaked object as seed points and analyzing unsegmented voxels adjacent said seed points in a desired direction;
repeating said iterations using newly segmented voxels from an iteration as seed points for a next iteration until no unsegmented voxels adjacent said seed points in said desired direction remain.