Hough Transform 2D Circles Image Filter GetCircles patch.

Algorithms
1

I’m currently trying out itk::HoughTransform2DCirclesImageFilter::GetCircles(n), and while I get quite promising results, there still appears room for improvement of the code.

Here’s my first patch for this function:
"PERF: Break out of loop as soon as requested number of circles is found"
http://review.source.kitware.com/#/c/22744/

Please have a look! What do you think?

Link to HoughTransform2DCirclesImageFilter::GetCircles(n):

2

These performance improvement contributions are appreciated! The patch looks good. Thank you @Niels_Dekker :clap:

3

Thank you Matt! Actually I see two more possible performance improvements in the very same function!

  1. At the beginning it makes a copy of GetOutput(0) to outputImage. Looks like an expensive operation that should not be necessary, as outputImage is only used as an input to DiscreteGaussianImageFilter. I think it might as well pass the result of GetOutput(0) directly to the filter, right?

  2. It uses MinimumMaximumImageCalculator to find the maximum pixel value of postProcessImage, but then it iterates another time over the pixel data to find the actual index of that pixel. I think it should use MinimumMaximumImageCalculator::GetIndexOfMaximum(), right?

Hope you can help me to get these two PERF issues fixed as well :slight_smile:

4

1 . The output image is copied because the the GetCircles method may be called multiple times and we don’t want to modify the output image. I would look into changing the loop to use ImageAlgorithm::Copy. It should be much faster.

  1. The GetIndexOfMaximum seems reasonable.

  2. You may want to look into the SmoothingRecursiveGaussianImageFilter over the Discrete.

5

Good catch. Yes, that looks right. One side effect we have to watch out for is unintended / unnecessary pipeline updates. Adding the PipelineMonitorImageFilter before the filter will hep to verify that unintended behavior does not occur.

Sounds good.

Thanks for contributing these improvements! :sunny:

6

Ahh! Using Image::Graft is a way to isolate an internal pipeline in a filter from the external execution. You can look at the CompositeFilterExample for reference. I believe you could replace the copy with something like:

outputImage->Graft(this->GetOutput(0));

The outputImage will still be a new image, but it will reference the same data as GetOutput(0).

7

Thank you very much for getting my first GetCircles patch http://review.source.kitware.com/#/c/22744/ (breaking out of loop as soon as requested number of circles is found) onto the master branch!

@matt.mccormick, @blowekamp, I just submitted my second patch, which avoids expensive copying of the image data from HoughTransform2DCirclesImageFilter::GetOutput(0): http://review.source.kitware.com/#/c/22747/

I still think it should be OK to directly use the data from GetOutput(0) as input to the DiscreteGaussianImageFilter, especially because the input parameter is a pointer-to-const, and the instance of DiscreteGaussianImageFilter is only a locally used object. When the function has returned, the DiscreteGaussianImageFilter and its output are gone. Right?

Do you still think that something like Image::Graft or PipelineMonitorImageFilter should be added in this specific case? I’m asking also because the unit tests now just appear to run successfully. Can you show me a test that would fail on my patch at http://review.source.kitware.com/#/c/22747/ ?

8

Unfortunately, the pipelining is not const correct and modification may still occur.

Yes.

This also brings up another possible area for performance optimization – if the DiscreteGaussianImageFilter can be re-used, its output will not get allocated and deallocated repeatedly.

Unnecessary pipeline updates for this filter are likely not covered by the tests and will need manual attention.

9

@matt.mccormick Thank you for your informative replies :slight_smile:

Is itk::DiscreteGaussianImageFilter known to modify its input? If so, wouldn’t that be a bug of DiscreteGaussianImageFilter?

10

You may want to look at the ITK Softwareguide information about how the pipeline is executed. In should when update is called on a filter the update is processed all the way up the connected filters to ensure everything in the pipeline is up to date. For this case we don’t want that to happen. We want to run the DiscreteGaussian on just the “output” disconnected from the filter that generated it.

To test this cases would require complicated construction of pipelines, updates, and then modification of components of the pipeline. We generally rely on best practices for this type of thing.

Hope that helps.

11

As it appears less trivial than I expected to avoid the extra copying of GetOutput(0) (my patch http://review.source.kitware.com/#/c/22747/), I just posted a patch of GetCircles(n) on a different PERF issue (which does not include my proposed fix to avoid the copying). Please have a look and tell me what you think:

http://review.source.kitware.com/#/c/22748
It avoids redundant iterative searches for the maximum in the Hough Transform output image, by calling MinimumMaximumImageCalculator::GetIndexOfMaximum(), instead of GetMaximum().

12

@blowekamp You wrote at http://review.source.kitware.com/#/c/22748/1

What happens if the image is empty?

When an empty image is passed as input to HoughTransform2DCirclesImageFilter, GetCircles() throws an exception. It already did so long before I started patching the function. Example:

const auto emptyImage = itk::Image<int>::New();
const auto filter = itk::HoughTransform2DCirclesImageFilter<int, int>::New();
filter->SetInput(emptyImage);
filter->Update();
filter->GetCircles(); // throws itk::InvalidRequestedRegionError.

This behavior may not be very elegant, but it doesn’t matter much to me, because it doesn’t seem to make much sense to pass an empty image to the filter. Moreover, this behavior has been like that for a very long time. I could even reproduce it on ITK 4.6.0.

or [what happens if] more circle are requested than exist?

For a non-empty input image, even when you ask for more circles than exist, you just get the number of circles you’re requesting! Again, GetCircles() already did behave like that long before I started patching. For example:

const auto image = itk::Image<int>::New();
const auto filter = itk::HoughTransform2DCirclesImageFilter<int, int>::New();

image->SetRegions({ 1, 1 });
image->Allocate(true);

filter->SetInput(image);
filter->SetNumberOfCircles(42);
filter->Update();
const auto numberOfFoundCircles = filter->GetCircles().size();

Here ‘numberOfFoundCircles’ is 42, just like the requested number of circles. I don’t think that’s very nice, but it’s the way it’s always been. At least I can reproduce it with ITK 4.6.0. None of my proposed PERF patches change this behavior.

13

Thank you all for having accepted my patch to avoid redundant iterative searches for maxima, in GetCircles(n), https://itk.org/gitweb?p=ITK.git;a=commit;h=f74a599e140e2ae4c28716ed48853299b4abb8ba

I just submitted another patch to avoid unnecessary memory allocation and copying of pixel data from GetOutput(0), in GetCircles(n). It uses the Graft method suggested here by @blowekamp Please review: http://review.source.kitware.com/#/c/22760/

It could replace my original patch for that particular issue (which hasn’t been accepted so far), which directly passes a pointer from GetOutput(0) to the gaussianFilter: http://review.source.kitware.com/#/c/22746/ (I still think either of the two patches just work fine.)

2 Likes
14

Thanks for contributing @Niels_Dekker!

2 Likes
15

Thank you all for having accepted my patch to avoid unnecessary allocation and copying of pixel data in GetCircles(n), https://itk.org/gitweb?p=ITK.git;a=commit;h=d207d2598ae47f296943a899e6de2d8806bb2f69

I just submitted a patch to remove the apparently obsolete parameter (unsigned int n) from the function. Please review: http://review.source.kitware.com/#/c/22766/

Could it be that this parameter (n) was originally meant to allow the user to specify the number of requested circles? Currently, it doesn’t seem to be useful anymore.

1 Like
16

Thanks for the contributions, @Niels_Dekker ! :sunny: :sparkles:

I added a review to the new patch.

17

Thank you all for having accepted my patch to remove the obsolete parameter (n) from GetCircles(), https://itk.org/gitweb?p=ITK.git;a=commit;h=63a51c8d493785fb44cb424b0ca4a08c4e96a21f

I just submitted a patch to ensure that the function returns an empty list of circles, when a user has explicitly called filter->SetNumberOfCircles(0). Please review:
http://review.source.kitware.com/#/c/22772/

FYI With previous ITK releases (<= ITK v4.12.2), filter->GetCircles() would typically return one or more (!) circles, when filter->SetNumberOfCircles(0) was called. Which seems very counter-intuitive to me.

18

@dzenanz Thanks for having reviewed and merged my latest proposed GetCircles() patch, “BUG: HoughTransform GetCircles() should avoid circles with accumulator <= 0” , https://itk.org/gitweb?p=ITK.git;a=commit;h=28962733

I would like to mention that I think the bug fix is in accordance with the original intent of the function, as it originally tested on a variable called ‘found’, to check whether it should still continue searching for circles. However, it appeared that ‘found’ was always true, when it was tested:

Anyway, ‘found’ is removed already:
https://itk.org/gitweb?p=ITK.git;a=commit;h=bc34f7e57433a5e8bc44b315f3f0596f032c026b

19

My latest commit https://itk.org/gitweb?p=ITK.git;a=blobdiff;f=Modules/Filtering/ImageFeature/test/itkHoughTransform2DCirclesImageTest.cxx;h=dca39bdb63a6eec8094c845e1f90a43de09a4027;hp=709ba8efc4a56d1bd352f7779fcc6a233d824d24;hb=28962733;hpb=014b1245feb3dd10d1c5a5fdd56d8f69ddaeb850 does the following, in itkHoughTransform2DCirclesImageTest.cxx

filter->SetInput(image);

for (PixelType pixelValue = 0; pixelValue <= 2; ++pixelValue)
{
  image->FillBuffer(pixelValue);
  image->Modified();
  filter->Update();

  if (!filter->GetCircles().empty())
    // ....            
}

It appeared that doing image->Modified() was necessary to trigger a filter->GenerateData() on each iteration of the for-loop. Right? But then, shouldn’t the image already be marked as modified by image->FillBuffer(pixelValue)?

Update: While doing image->Modified() appears necessary to trigger filter->GenerateData() on each iteration of the for-loop, filter->GetCircles() only actively searches for circles on the first iteration. Is that a bug in the filter? Or should the test also do filter->Modified(), on each iteration?

20

Thanks for the continued contributions, @Niels_Dekker :slight_smile:

quote=“Niels_Dekker, post:19, topic:350”]
It appeared that doing image->Modified() was necessary to trigger a filter->GenerateData() on each iteration of the for-loop. Right? But then, shouldn’t the image already be marked as modified by image->FillBuffer(pixelValue)?
[/quote]

Yes, looking into the implementation of FillBuffer(), it does not call ->Modified() internally. This may be historical, or it may be for performance reasons (we do not check to see if the image is not already filled with the value, so ->Modified() would not be correct).

Without looking into the details, it could be a bug, or it could be a deliberate performance choice.