Insight Journal (ISSN 2327-770X) - Finding regional extrema

Finding regional extrema - methods and performance

Department of Medicine, Monash University, Australia. Unite de Biologie du Developpement et de la Reproduction, Institut National de la Recherche Agronomique, France.

Please use this identifier to cite or link to this publication: http://hdl.handle.net/1926/153

Published in The Insight Journal - 2005 August - December.

Submitted by Richard Beare on 11-14-2006.

Finding regional extrema of images is an important step in a number of
morphological algorithms, such as some versions of the watershed
transformfootnote{This work started because we were trying to compare
different watershed algorithms}. Regional extrema may also be
important cues of other tasks, such as splitting objects based on
distance transform information. This report provides an overview of
the methods available in ITK and compares the performance with a new
filter.

Data

2 Files (2Mb)

Finding_regional_extrema_-_methods_and_performance.pdf (230Kb) [view paper]
regionalExtrema.tar.gz (2Mb)

Code

Automatic Testing Results by Insight-Journal Dashboard on Wed Feb 22 23:34:10 2006 for revision #5

expertise: 5 sensitivity: 5

This project passed all of its tests.
Click here for more details.

Go here to access the main testing dashboard.

Automatic Testing Results by Insight-Journal Dashboard on Thu Jan 26 16:50:51 2006 for revision #3

expertise: 5 sensitivity: 4.5

Automatic Testing Results by Insight-Journal Dashboard on Tue Jan 3 21:32:11 2006 for revision #2

expertise: 5 sensitivity: 5

Automatic Testing Results by Insight-Journal Dashboard on Fri Dec 23 13:15:26 2005 for revision #1

expertise: 5 sensitivity: 5

Reviews

A comprehensive, well presented paper. by Dan Mueller on 01-09-2006 for revision #3

expertise: 4 sensitivity: 4.5

Summary:
The authors discuss how to extract regional minima/maxima regions from binary/greyscale images. Two approaches are presented and compared: 1. the current ITK approach using the HConvexImageFilter and HConcaveImageFilter, and 2. a new approach using a simple flooding-based algorithm (referred to by the authors as ValuedRegionalExtremaImageFilter).

Hypothesis:
The hypothesis is that the ValuedRegionalExtremaImageFilter approach is computational faster than the HConvexImageFilter/HConcaveImageFilter approach. Test results indicate that the proposed approach (ValuedRegionalExtremaImageFilter) is faster.

Evidence:
Each approach has been implemented in ITK and execution times reported in the paper.

Open Science:
Full open source for the filters, examples and tests, as well as input images, are provided.

Reproducibility:
I was able to download, compile, and run the work. However, I had some minor problems compiling the code because I was using an older version of ITK (InsightToolkit-2.2.0). Compiling with InsightToolkit-2.4.1 was successful. I was also unable to run the tests because they rely on the DART Image Compare program. (Does anyone know how I can obtain the Image Compare program for testing Insight Journal articles? The IJ WIKI mentions that DART tests use Image Compare, but it does not explain how to obtain it for desktop testing/reproducibility.)

Use of Open Source Software:
Uses ITK.

Open Source Contributions:
The source code was relatively easy to get going (besides the minor unrelated issues listed above).

Code Quality:
The code quality is fairly easy to read. However, I would like to see more comments within ValuedRegionalExtremaImageFilter::GenerateData() more fully explaining the algorithm - I find it hard to read what is being done and why.

Final Thoughts:
Thanks for this addition to ITK. The speed increases for finding regional maxima/minima will help enhance various segmentation tasks. A comprehensive, well presented paper.

Comment by Dan Mueller: Additional comments, and flood filling

I like the addition comments you have added so far - I found it much easier to work out how the algorithm works.

Now that I better understand what is happening, have you considered using the itk::FloodFilledFunctionConditionalIterator? This iterator is templated over a comparison function and allows you to walk over a neighbourhood image region which conforms to the comparison function. The only drawback is this iterator is currently *not* implemented with a ShapedNeighborhoodIterator and therefore you can not set the FullyConnected property... From what I understand however, it does what you are doing in the last phase of your algorithm... Just a thought.

Comment by Richard Beare: Draft of additional comments

Hi Dan,
I've started extending the comments in ValuedRegionalExtremaImageFilter::GenerateData() - see below. Is there any particular part where you think more detail is helpful?

ValuedRegionalExtremaImageFilter
::GenerateData()
{
// Allocate the output
this->AllocateOutputs();

// 2 phases
ProgressReporter progress(this, 0, this->GetOutput()->GetRequestedRegion().GetNumberOfPixels()*2);

// copy input to output - isn't there a better way?
typedef ImageRegionConstIterator InputIterator;
typedef ImageRegionIterator OutputIterator;

InputIterator inIt( this->GetInput(),
this->GetOutput()->GetRequestedRegion() );
OutputIterator outIt( this->GetOutput(),
this->GetOutput()->GetRequestedRegion() );
inIt = inIt.Begin();
outIt = outIt.Begin();

InputImagePixelType firstValue = inIt.Get();
this->m_Flat = true;

while ( !outIt.IsAtEnd() )
{
InputImagePixelType currentValue = inIt.Get();
outIt.Set( static_cast( currentValue ) );
if( currentValue != firstValue )
{ this->m_Flat = false; }
++inIt;
++outIt;
progress.CompletedPixel();
}

// if the image is flat, there is no need to do the work:
// the image will be unchanged
if( !this->m_Flat )
{
// Now for the real work!
// More iterators - use shaped ones so that we can set connectivity
// Note : all comments refer to finding regional minima, because
// it is briefer and clearer than trying to describe both regional
// maxima and minima processes at the same time
ISizeType kernelRadius;
kernelRadius.Fill(1);
NOutputIterator outNIt(kernelRadius,
this->GetOutput(),
this->GetOutput()->GetRequestedRegion() );
setConnectivity( &outNIt, m_FullyConnected );

CNInputIterator inNIt(kernelRadius,
this->GetInput(),
this->GetOutput()->GetRequestedRegion() );
setConnectivity( &inNIt, m_FullyConnected );

ConstantBoundaryCondition iBC;
iBC.SetConstant(m_MarkerValue);
inNIt.OverrideBoundaryCondition(&iBC);

ConstantBoundaryCondition oBC;
oBC.SetConstant(m_MarkerValue);
outNIt.OverrideBoundaryCondition(&oBC);

TFunction1 compareIn;
TFunction2 compareOut;

outIt = outIt.Begin();

// set up the stack and neighbor list
IndexStack IS;
typename NOutputIterator::IndexListType IndexList;
IndexList = outNIt.GetActiveIndexList();

while ( !outIt.IsAtEnd() )
{
OutputImagePixelType V = outIt.Get();
// if the output pixel value = the marker value then we have
// already visited this pixel and don't need to do so again
if (compareOut(V, m_MarkerValue))
{
// reposition the input iterator
inNIt += outIt.GetIndex() - inNIt.GetIndex();

InputImagePixelType Cent = static_cast(V);

// check each neighbor of the input pixel
typename CNInputIterator::ConstIterator sIt;
for (sIt = inNIt.Begin(); !sIt.IsAtEnd(); ++sIt)
{
InputImagePixelType Adjacent = sIt.Get();
if (compareIn(Adjacent, Cent))
{
// The centre pixel cannot be part of a regional minima
// because one of its neighbors is smaller.
// Set all pixels in the output image that are connected to
// the centre pixel and have the same value to
// m_MarkerValue
// This is the flood filling step. It is a simple, stack
// based, procedure. The original value (V) of the pixel is
// recorded and the pixel index in the output image
// is set to the marker value. The stack is initialized
// with the pixel index. The flooding procedure pops the
// stack, sets that index to the marker value and places the
// indexes of all neighbors with value V on the stack. The
// process terminates when the stack is empty.
outNIt += outIt.GetIndex() - outNIt.GetIndex();
//setConnectedPixels(outNIt, V, IS, IndexList);

OutputImagePixelType NVal;
//IndexStack IS;
OutIndexType idx;
// Initialize the stack
IS.push(outNIt.GetIndex());
outNIt.SetCenterPixel(m_MarkerValue);

typename NOutputIterator::IndexListType::const_iterator LIt;

while (!IS.empty())
{
// Pop the stack
idx = IS.top();
IS.pop();
// position the iterator
outNIt += idx - outNIt.GetIndex();
// check neighbors
for (LIt = IndexList.begin(); LIt != IndexList.end(); ++LIt)
{
NVal = outNIt.GetPixel(*LIt);
if (NVal == V)
{
// still in a flat zone
IS.push(outNIt.GetIndex(*LIt));
// set the output as the marker value
outNIt.SetPixel(*LIt, m_MarkerValue);
}
}
}
// end flooding
}
}
}
++outIt;
progress.CompletedPixel();
}
}

}

Comment by Gaetan Lehmann: ImageCompare

Hi Dan,

You can get ImageCompare at http://insight-journal.org/documentation/CMake/ImageCompare.tgz

Thanks for your review.

Gaetan

Add a new review

Quick Comments

Comment by Altheqa Stone

واجهات حجر هاشمىحجر هاشمىواجهات حجر هاشمى هيصمحجر هاشمى هيصماسعار حجر هاشمىاسعار حجر هاشمى هيصمتركيب حجر هاشمىتركيب حجر هاشمى هيصمواجهات فلل حجر هاشمى هيصمانواع الحجر الهاشمىأشكال الحجر الهاشمىسعر متر الحجر الهاشمىواجهات حجر هاشمياسعار الحجر الهاشمى فى مصر.واجهات حجر هاشمى مصرواجهات حجر هاشمى2020.واجهات منازل حجر هاشمىواجهات عمارات حجر هاشمىاشكال واجهات حجر هاشمىاحدث واجهات حجر هاشمىديكورات حجر هاشمى سعر متر الحجر الهاشمي في مصر 2020 اسعار تركيب الحجر الهاشمي اسعار الحجر الهاشمى بمصر اسعار توريد وتركيب الحجر الهاشمى

اسعار الحجر الهاشمى بمصر اسعار الحجر الهاشمى فرز اول وتانى
https://www.altheqa-eg.com/stone-prices/
الحجر الهاشمي الاختيار الأفضل لواجهات المنازل والفلل أفضل صنعة تركيب وأقل سعرًا
https://www.dekorishn-altheqa.com/decoration/
أنواع الحجر الهاشمي بمصر مميزات وعيوب كل نوع وما الأفضل لك
https://www.altheqa-eg.com/stone-types/
تعرف على أسعار الحجر الهاشمي في مصر بأشكاله المختلفة
https://www.altheqa-stone.com/hashmi-stone-prices/
حجر هاشمي هيصم بأقل تكاليف انتقال فرز أول للديكورات الخارجية والداخلية
https://www.decoration-altheqa.com/stone-facades/
حجر هاشمي فرز أول لواجهات الفلل والقصور والعمائر
https://www.altheqa-stone.com/stone-2020/
حجر هاشمى هيصم لواجهات المنازل والعمائر فى مصر 2020
https://www.dekorishn-altheqa.com/modern-stone-2/
تركيب الحجر الفرعوني لواجهات المنازل والفلل 2020
https://www.dekorishn-altheqa.com/stone-houses/
واجهات الحجر الفرعوني في مصر تركيبها بأقل الأسعار
https://www.altheqa-stone.com/altheqa-stone/
أفضل شركة لتركيب الحجر البازلت في مصر بأسعار مناسبة واستخدامات متعددة
https://www.altheqa-eg.com/black-basalt/
أنواع الحجر البازلت أسعار تركيب الحجر البازلت في مصر 2020
https://www.decoration-altheqa.com/basalt-altheqa/
هل الحجر الهاشمى يتوقف استخدامه فى الواجهات فحسب؟
https://www.altheqa-eg.com/stone-work/
سعر متر الحجر الهاشمى خامة مصنع فرز اول
https://www.dekorishn-altheqa.com/stone-meter-price/
شركة الثقه للمقاولات
https://www.altheqa-eg.com
أهم الشركات لوظيفة تركيب حجر هاشمى هيصم
https://www.altheqa-eg.com/%d8%a3%d9%87%d9%85-%d8%a7%d9%84%d8%b4%d8%b1%d9%83%d8%a7%d8%aa-%d9%84%d9%88%d8%b8%d9%8a%d9%81%d8%a9-%d8%aa%d8%b1%d9%83%d9%8a%d8%a8-%d8%ad%d8%ac%d8%b1-%d9%87%d8%a7%d8%b4%d9%85%d9%89-%d9%87%d9%8a%d8%b5/
حجر هاشمى هيصم هو الافضل دائما لماذا؟
https://www.altheqa-eg.com/%d8%ad%d8%ac%d8%b1-%d9%87%d8%a7%d8%b4%d9%85%d9%89-%d9%87%d9%8a%d8%b5%d9%85-%d9%87%d9%88-%d8%a7%d9%84%d8%a7%d9%81%d8%b6%d9%84-%d8%af%d8%a7%d8%a6%d9%85%d8%a7-%d9%84%d9%85%d8%a7%d8%b0%d8%a7%d8%9f/
تركيب حجر هاشمى هيصم خطوة بخطوة
https://www.altheqa-eg.com/%d8%aa%d8%b1%d9%83%d9%8a%d8%a8-%d8%ad%d8%ac%d8%b1-%d9%87%d8%a7%d8%b4%d9%85%d9%89-%d9%87%d9%8a%d8%b5%d9%85-%d8%ae%d8%b7%d9%88%d8%a9-%d8%a8%d8%ae%d8%b7%d9%88%d8%a9/
واجهات جذابه من الحجر الهاشمى
https://www.altheqa-eg.com/%d9%88%d8%a7%d8%ac%d9%87%d8%a7%d8%aa-%d8%ac%d8%b0%d8%a7%d8%a8%d9%87-%d9%85%d9%86-%d8%a7%d9%84%d8%ad%d8%ac%d8%b1-%d8%a7%d9%84%d9%87%d8%a7%d8%b4%d9%85%d9%89/
شركة الثقه للمقاولات
https://www.altheqa-stone.com/
معرض صور حجر هاشمى
https://www.altheqa-stone.com/stone-decorations/
تعرف على اسعار الحجر الهاشمى
https://www.altheqa-stone.com/%d8%aa%d8%b9%d8%b1%d9%81-%d8%b9%d9%84%d9%89-%d8%a7%d8%b3%d8%b9%d8%a7%d8%b1-%d8%ad%d8%ac%d8%b1-%d9%87%d8%a7%d8%b4%d9%85%d9%89-%d9%87%d9%8a%d8%b5%d9%85/
تصدير حجر هاشمى
https://www.altheqa-stone.com/export/
سعر حجر هاشمى وطريقه تركيبه
https://www.altheqa-stone.com/%d8%b3%d8%b9%d8%b1-%d8%ad%d8%ac%d8%b1-%d9%87%d8%a7%d8%b4%d9%85%d9%89-%d9%87%d9%8a%d8%b5%d9%85-%d9%88%d8%b7%d8%b1%d9%8a%d9%82%d9%87-%d8%aa%d8%b1%d9%83%d9%8a%d8%a8%d8%a9/
لمعرفه اسعار الحجر الهاشمى فى مصر
https://www.altheqa-stone.com/%d8%a7%d8%b3%d8%b9%d8%a7%d8%b1-%d8%ad%d8%ac%d8%b1-%d9%87%d8%a7%d8%b4%d9%85%d9%89/
اسعار حجر هاشمى
https://www.dekorishn-altheqa.com/%D8%A7%D8%B3%D8%B9%D8%A7%D8%B1-%D8%AD%D8%AC%D8%B1-%D9%87%D8%A7%D8%B4%D9%85%D9%89/
واجهات فلل حجر هاشمى
https://www.dekorishn-altheqa.com/%D9%88%D8%A7%D8%AC%D9%87%D8%A7%D8%AA-%D9%81%D9%84%D9%84-%D8%AD%D8%AC%D8%B1-%D9%87%D8%A7%D8%B4%D9%85%D9%8A/
اشكال واجهات عمارات حجر هاشمى هيصم
https://www.dekorishn-altheqa.com/modern-homes/
كتالوج صور واجهات بيوت مصرية ريفية
https://www.dekorishn-altheqa.com/happy-home/
اشكال واجهات منازل | اشكال واجهات عمارات
https://www.dekorishn-altheqa.com/home-decor/
اسعار البازلت فى مصر
https://www.dekorishn-altheqa.com/%D8%A7%D8%B3%D8%B9%D8%A7%D8%B1-%D8%A7%D9%84%D8%A8%D8%A7%D8%B2%D9%84%D8%AA-%D9%81%D9%89-%D9%85%D8%B5%D8%B1/
واجهات منازل وفلل بتصيمات حجر هاشمى فخمة
https://www.altheqa-eg.com/modern-homes/
اشكال وصور واجهات منازل وبيوت بالحجر الهاشمى بطريقة حديثة
https://www.dekorishn-altheqa.com/stone-altheqa/

كيف يمكنك تحديد سعر متر الحجر الهاشمى فى واجهات الفلل والمنازل
https://www.decoration-altheqa.com/%d9%83%d9%8a%d9%81-%d9%8a%d9%85%d9%83%d9%86%d9%83-%d8%aa%d8%ad%d8%af%d9%8a%d8%af-%d8%b3%d8%b9%d8%b1-%d9%85%d8%aa%d8%b1-%d8%a7%d9%84%d8%ad%d8%ac%d8%b1-%d8%a7%d9%84%d9%87%d8%a7%d8%b4%d9%85%d9%89-%d9%81/

Comment by Altheqa Stone

Resources


Download All

Statistics more


Global rating:
Review rating:	[review]
Code rating:
Views:	2555
Downloads:	4996
Paper Quality:
2 comments

Information more


Paper Id:	65
Keywords:	regional minima, flooding, performance, mathematical morphology
Toolkits:	ITK (moved into the sandbox), CMake
Revision:
Export citation:
Status:	Open for public review

Share

Linked Publications more


GeoInterp: Contour Interpolation with Geodesic Snakes Geodesic Snakes by Saboo R., Julian R., Stephen P.
N4ITK: Nick's N3 ITK Implementation For MRI Bias Field Correction by Tustison N., Gee J.
Computing Bone Morphometric Feature Maps from 3-Dimensional Images by Vimort J., McCormick M., Paniagua B.
Exporting Contours to DICOM-RT Structure Set by Gorthi S., Bach Cuadra M., Thiran J.
Applying Image Mining to Support Gestational Age Determination by Araujo A., Bellon O., Silva L., Vieira E., Cat M.
A Skull-Stripping Filter for ITK by Bauer S., Fejes T., Reyes M.
ITK in Biomedical Research and Commercial Applications by McCormick M., Aylward S., Johnson H., Lowekamp B.
Scalable Simple Linear Iterative Clustering (SSLIC) Using a Generic and Parallel Approach by Lowekamp B., Chen D., Yaniv Z., Yoo T.
Anisotropic Fast Marching in ITK by Mirebeau J.
An Open Source, Fast Ultrasound B-Mode Implementation for Commodity Hardware by McCormick M.

View license

Loading license...

Send a message to the author