[Insight-users] Fast binary morphology dilation

[Miller, James V (Research)]

Jerome,

The complexity of "padding" the input is with respect to supporting
streaming.
Let's say I have an image which 100x100 pixels.  I could process the entire
image at once.  But suppose I only want to operate on the middle 50x50
pixels, so that my output image is only 50x50 pixels.  I want the
"boundary pixels" of this 50x50 region to be correct, in that they are 
exactly the same values as I would have gotten if I had filtered the 
entire 100x100 pixel image and then cropped out the middle 50x50 piece.

The question is how hard is it to support this in this algorithm.  If I was 
doing a convolution with a 5x5 kernel, I would simply "pad" the input
requested region by 2 pixels on each side (+-x, +-y).  Then when I went to
calculate the 
output pixels on the boundary of the 50x50 region, I know the input pixels
that are outside the output 50x50 region are valid input pixels (if the
subregion 
under consideration was closer to the boundary of the input's
LargestPossibleRegion, I would know the input pixels that are outside the 
output 50x50 region either valid input pixels OR are prescribed boundary
condition pixels).

For the sake of Minkowski addition, let's say my structuring element has 
radius [0, 5] and has a single "on" pixel at offset [0, 5].  The result of 
the dilation should shift my image vertically by 5 pixels.  So to generate 
the pixels in the output requested region, I would need to know input pixel
values that are 5 pixels outside the output requested region.  Therefore, 
my GenerateInputRequestedRegion() method will need to pad the output 
requested region by maximum of the radius of my structuring element and
the radius neighborhood connectivity.

The trick I see for the surface tracking in this context is being able to 
distinguish between the border of the image and the border of an object.
You track surfaces off the edge of the image. (I think this can be handled
by checking the "status" of the SetPixel calls in the surface tracking
stage.

Jim



-----Original Message-----
From: jerome schmid [mailto:jerome.schmid at ircad.u-strasbg.fr]
Sent: Tuesday, September 14, 2004 12:18 PM
To: Miller, James V (Research)
Cc: insight-users at itk.org
Subject: RE: [Insight-users] Fast binary morphology dilation


James,

Good idea of checking dimensions at compilation, I never try it in itk.

With respect to the GenerateInputRequestedRegion, I still don't understand
your viewpoint.

In your previous e-mail you speak about " pixel that "on" and on the border
of the image (defined by the LargestPossibleRegion)" saying that these kinds
of pixels will be always tagged as border pixels. Actually if you consider
your image as finite, the boundary pixels are border pixels and they should
be considered as it, isn'it?. Or maybe I don't understand your comment...

In a first version, I padded the input requested region like you with the
max. However I realise or think, that we need the input requested region to
be padded only by the neighborhood of connectivity radius, because for the
boundary pixels of the output requested region, we have to determine if they
are inner pixel or border pixels ( in sense of surface or contour pixels ).
Consequently we have to look in a connectivity neighborhood if any
background pixel is present.

So why padding the input requested region with the max, if we will only
access input pixels in a region = output request region + pad for
neighborhood test ( i.e m_radius region )?

You wrote about me: "you are padding the 1 so that any surface connectivity
can be tracked." Yes...this is the purpose of the border tracking
procedure...

Maybe you are speaking about an issue that I can't figure out. Sorry...!

Jerome



-----Message d'origine-----
De : Miller, James V (Research) [mailto:millerjv at crd.ge.com]
Envoye : mardi 14 septembre 2004 17:38
A : 'jerome schmid'; Miller, James V (Research)
Cc : insight-users at itk.org
Objet : RE: [Insight-users] Fast binary morphology dilation


Jerome,

For the multiple objects, I am thinking of copying the input labels to the
output as I previously mentioned.  However, I think if I replace the pixels
that have DilateValue with the BackgroundValue, then your cross without the
center pixel may work properly.

For the check on the dimensions, I am going to try to use the
ConceptChecking
macros to ensure the proper dimensions instead of putting that code in
GenerateInputRequestedRegion. This will force the code not to compile as
opposed to generating a runtime error.

With respect to the GenerateInputRequestedRegion, you are padding the 1 so
that
any surface connectivity can be tracked. Shouldn't also have to pad by the
radius of the structuring element.  In particular,

padBy = max(m_Radius, m_Kernel.GetRadius())

using the max check will allow structuring elements that are for instance
3x3x0, i.e. a 2D kernel in a 3D volume.

Jim


-----Original Message-----
From: jerome schmid [mailto:jerome.schmid at ircad.u-strasbg.fr]
Sent: Tuesday, September 14, 2004 4:39 AM
To: Miller, James V (Research)
Cc: insight-users at itk.org
Subject: RE: [Insight-users] Fast binary morphology dilation


James,

Thanks for the interest for the filter proposed together we should improve
it.

First of all you are right for the GenerateInputRequestedRegion() function,
we must pad the input requested region. My first version did it but I cannot
remember why I remove this function...There is also a test which must be
done, for instance in this same function:

		// Test dimensions of input, output images and structuring
elements
		if( !(	TInputImage::ImageDimension ==
TOutputImage::ImageDimension && \
				TKernel::NeighborhoodDimension ==
TInputImage::ImageDimension ) )
		{
			// build an exception
			DataObjectError e(__FILE__, __LINE__);

			OStringStream msg;
			msg << static_cast<const char
*>(this->GetNameOfClass())
				<< "::GenerateInputRequestedRegion()";
			e.SetLocation(msg.str().c_str());
			e.SetDescription("The dimensions of input, output
and structuring element
must be the same.");
			throw e;
		}

This test is necessary if user plays to give a SE in 2D whereas the input
image are in 3D , etc...In fact as we manage
index internally it can be dangerous. Honestly I do not think users use an
input image in 3D with a output in 2D with a SE in 1D for instance!

I add your version with the modification attached to this mail.( I hadn't
attach the .h, the modifications are of course in the
generateInputRequestedRegion and in the GenerateData one at the beginnning
when we define the tmpRequestedRegion ). It is zipped because my previous
mail was refused, > 40 kb...

Secondly, if you want to manage your objects stuff ( some objects labeled
with #i ) I think the final loop you put is ok. I understand better your
"most appropriate background value" now however you are agree with me that
when center pixel was not on, some problems appeared previously.

Last point it is true that threading this filter can be difficult, that is
why I started with the normal version...

Regards,

Jerome

-----Message d'origine-----
De : Miller, James V (Research) [mailto:millerjv at crd.ge.com]
Envoye : lundi 13 septembre 2004 22:30
A : 'jerome schmid'
Objet : RE: [Insight-users] Fast binary morphology dilation


Jerome,

I have a few other questions on this new filter.

I am a bit confused by the "second stage" code.  I think this filter needs
a GenerateInputRequestedRegion().  The superclass' version will only request
an input requested region that matches the output requested region.  At a
minimum, the input requested region would need to be padded by one.  And I
think
it should really be padded by the m_Kernel.GetRadius().

That being said, I do not see how a pixel that "on" and on the border of the

image (defined by the LargestPossibleRegion) will ever be marked as a border
pixel.  Since the boundary condition for the oNeighIt is the background tag,

any neighboring pixel that is outside the border of the image will return
the background tag.   So the code

      // Test current pixel: it is a border pixel or an inner pixel?
      bool bIsOnContour = false;

      for (i = 0; i < neighborhoodSize; ++i)
        {
        // If at least one neighbour pixel is off the center pixel
        // belongs to contour
        if( oNeighbIt.GetPixel(i) == backgroundTag )
          {
          bIsOnContour = true;
          break;
          }
        }

will say bIsOnContour is true for a pixel that is on and one of its
neighbors is
off AND bIsOnContour is true for a pixel that is on and on the boundary of
the
image (wrt LargestPossibleRegion).

(On a side note, it is not going to be trivial to thread this filter.  The
"third stage" code is not thread safe. Multiple threads could try to write
to
the same pixel at the same time. For instance, pixels near the boundary
between
threads.)

I've attached my modified versions of your filter.

Jim