[ITK-users] optimizing iterations over relative small connected components (flood-fill)

[Grothausmann, Roman Dr.]

Dear mailing list members,


I'm looking for a highly efficient method to "pick" single watershed segmented 
regions in my extension to ITKSnap 
(https://github.com/pyushkevich/itksnap/pull/1). If my understanding is correct, 
such a region is guaranteed to be a single connected component (CC). The dynamic 
level adjustment in the extension can lead to very small CCs compared to the 
overall image which is processed. Currently I've a project where the ratio of 
the amount of voxels in a CC relative to the total voxels in the image is about 
1/1000000 or even smaller.

The current implementation 
(https://github.com/romangrothausmann/itksnap/blob/master%2BgdWS/GUI/Model/JoinModel.cxx#L123) 
uses an ImageRegionIterator 
(https://github.com/romangrothausmann/itksnap/blob/master%2BgdWS/Logic/ImageWrapper/ImageWrapper.h#L119) 
which is considerably slow as it iterates over the whole image not making use of 
the click position as a seed. I suspect this could be optimized with either a 
RandomAccessIterator initialized at the seed and then running recursively on the 
neighbouring voxels. However, I also stumbled over the 
FloodFilledImageFunctionConditionalIterator and the 
ShapedFloodFilledFunctionConditionalConstIterator in conjunction with a 
BinaryThresholdImageFunction (as in this example: 
http://itk.org/Wiki/ITK/Examples/WishList/Iterators/FloodFilledImageFunctionConditionalIterator)
Which approach is better?
Are there even better ones?
Is there a way to construct reasonable conditions to run these iterators in a 
filter in ThreadedGenerateData, i.e. a way to estimate in advance the small 
region of the CC to be processed partially by multiple threads?

Thanks for any help or hints.
Roman

PS: In the example it says: "The iterator only visits 4-connected neighbors. The 
code in FloodFilledFunctionConditionalConstIterator.txx should be replaced."
Would that be what was done in the contribution contributing 
ShapedFloodFilledFunctionConditionalConstIterator?


-- 
Dr. Roman Grothausmann

Tomographie und Digitale Bildverarbeitung
Tomography and Digital Image Analysis

Institut für Funktionelle und Angewandte Anatomie, OE 4120
Medizinische Hochschule Hannover
Carl-Neuberg-Str. 1
D-30625 Hannover

Tel. +49 511 532-2900