# Hough Transform 2D Circles Image Filter GetCircles patch.

**URL:** <https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350>\
**Category:** Algorithms\
**Created:** [October 24, 2017, 5:26pm UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350 "2017-10-24T17:26:37Z")\
**Posts on this page:** 20\
**Page:** 2

<div class="post-metadata">

**Author:** ![Niels\_Dekker](https://discourse.itk.org/letter_avatar_proxy/v4/letter/n/9d8465/32.png) [@Niels\_Dekker](https://discourse.itk.org/u/Niels_Dekker)\
**Post date:** [November 12, 2017, 10:58am UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/21 "2017-11-12T10:58:24Z")

</div>

Thanks for your reply, Matt!

So filter-\>GetCircles() only actively searches for circles when the  
’MTime’ of the filter has changed. (Otherwise it just returns the  
previously found circles.)

When an input image of a filter is modified (by image-\>Modified()),  
and filter-\>Update() is called, do you think that in general,  
filter-\>GenerateData() should take care of updating the MTime?

Should HoughTransform2DCirclesImageFilter::GenerateData() be fixed to  
call this-\>Modified()?

> <https://github.com/InsightSoftwareConsortium/ITK/blob/v4.12.2/Modules/Filtering/ImageFeature/include/itkHoughTransform2DCirclesImageFilter.hxx#L82>

---

<div class="post-metadata">

**Author:** ![matt.mccormick](https://discourse.itk.org/user_avatar/discourse.itk.org/matt.mccormick/32/7_2.png) [@matt.mccormick](https://discourse.itk.org/u/matt.mccormick)\
**Post date:** [November 13, 2017, 2:46pm UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/22 "2017-11-13T14:46:34Z")

</div>

> [@Niels\_Dekker](#):
>
> Should HoughTransform2DCirclesImageFilter::GenerateData() be fixed to
> 
> call this-\>Modified()?

Good question.

`->Modified()` does not need to be called in a filter’s `GenerateData()` method because the pipeline system takes care of this.

---

<div class="post-metadata">

**Author:** ![Niels\_Dekker](https://discourse.itk.org/letter_avatar_proxy/v4/letter/n/9d8465/32.png) [@Niels\_Dekker](https://discourse.itk.org/u/Niels_Dekker)\
**Post date:** [November 13, 2017, 3:51pm UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/23 "2017-11-13T15:51:00Z")

</div>

> [@matt.mccormick](#):
>
> -\>Modified() does not need to be called in a filter’s GenerateData() method because the pipeline system takes care of this.

Thanks, Matt. However… with the following code, I expected each filter-\>GetCircles() to do a new search for circles, on each iteration:

```
filter->SetInput(image);

for (int i = 0; i < n; ++i)
{
    image->FillBuffer(n)
    image->Modified();
    filter->Update();
    filter->GetCircles();
}

```

Unfortunately that did not happen, because filter-\>GetCircles() only searches for new circles when this-\>GetMTime() has changed. Otherwise it just returns the previously found circles:

> <https://github.com/Kitware/ITK/blob/28962733bb5ef8653f37b49b4cf09579423e82bc/Modules/Filtering/ImageFeature/include/itkHoughTransform2DCirclesImageFilter.hxx#L188>

Do you think in this case the user code is wrong?

---

<div class="post-metadata">

**Author:** ![matt.mccormick](https://discourse.itk.org/user_avatar/discourse.itk.org/matt.mccormick/32/7_2.png) [@matt.mccormick](https://discourse.itk.org/u/matt.mccormick)\
**Post date:** [November 13, 2017, 3:58pm UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/24 "2017-11-13T15:58:11Z")

</div>

> [@Niels\_Dekker](#):
>
> Unfortunately that did not happen, because filter-\>GetCircles() only searches for new circles when this-\>GetMTime() has changed. Otherwise it just returns the previously found circles:

Perhaps `m_OldModifiedTime` should be updated in `GenerateData()`.

---

<div class="post-metadata">

**Author:** ![blowekamp](https://discourse.itk.org/user_avatar/discourse.itk.org/blowekamp/32/79_2.png) [@blowekamp](https://discourse.itk.org/u/blowekamp)\
**Post date:** [November 13, 2017, 4:00pm UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/25 "2017-11-13T16:00:37Z")

</div>

Proper execution based in on modified times is a tricky thing. It it best handled in the pipeline.

What ever original purpose GetCircles had for doing computation outside of the pipeline line update is no longer there. Perhaps it was related to the former n argument.

I think the computation done in the GetCircle method should be move to be part of the pipeline update. Likely in the AfterThreadedGenerateData.

---

<div class="post-metadata">

**Author:** ![matt.mccormick](https://discourse.itk.org/user_avatar/discourse.itk.org/matt.mccormick/32/7_2.png) [@matt.mccormick](https://discourse.itk.org/u/matt.mccormick)\
**Post date:** [November 13, 2017, 4:22pm UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/26 "2017-11-13T16:22:34Z")

</div>

> [@blowekamp](#):
>
> I think the computation done in the GetCircle method should be move to be part of the pipeline update. Likely in the AfterThreadedGenerateData.

That’s a good idea.

---

<div class="post-metadata">

**Author:** ![dzenanz](https://discourse.itk.org/user_avatar/discourse.itk.org/dzenanz/32/1093_2.png) [@dzenanz](https://discourse.itk.org/u/dzenanz)\
**Post date:** [November 13, 2017, 4:34pm UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/27 "2017-11-13T16:34:17Z")

</div>

Will you do it, @Niels_Dekker?

---

<div class="post-metadata">

**Author:** ![Niels\_Dekker](https://discourse.itk.org/letter_avatar_proxy/v4/letter/n/9d8465/32.png) [@Niels\_Dekker](https://discourse.itk.org/u/Niels_Dekker)\
**Post date:** [November 13, 2017, 4:40pm UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/28 "2017-11-13T16:40:16Z")

</div>

> [@dzenanz](#):
>
> Will you do it, @Niels_Dekker?

If you would like to do it @dzenanz please go ahead! 🙂

Honestly, this particular issue does not have the highest priority to me right now, but it’s good to know that the issue is recognized as a bug.

---

<div class="post-metadata">

**Author:** ![dzenanz](https://discourse.itk.org/user_avatar/discourse.itk.org/dzenanz/32/1093_2.png) [@dzenanz](https://discourse.itk.org/u/dzenanz)\
**Post date:** [November 13, 2017, 5:11pm UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/29 "2017-11-13T17:11:43Z")

</div>

I am not eager to do it, I only wanted to make sure somebody puts it on their to-do list. Because the discussion’s conclusion was that it should be done, without a hint as who should do it 😃

---

<div class="post-metadata">

**Author:** ![Niels\_Dekker](https://discourse.itk.org/letter_avatar_proxy/v4/letter/n/9d8465/32.png) [@Niels\_Dekker](https://discourse.itk.org/u/Niels_Dekker)\
**Post date:** [November 13, 2017, 6:03pm UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/30 "2017-11-13T18:03:26Z")

</div>

OK, I’ll have a look at how to fix the issue by moving code from GetCircles() to AfterThreadedGenerateData, when I have time. But first I would like you to have a look at this new proposed patch of mine: _“ENH: Improved HoughTransform2DCirclesImageFilter accuracy, using Math::Round”_, [http://review.source.kitware.com/#/c/22784](http://review.source.kitware.com/#/c/22784)

---

<div class="post-metadata">

**Author:** ![Niels\_Dekker](https://discourse.itk.org/letter_avatar_proxy/v4/letter/n/9d8465/32.png) [@Niels\_Dekker](https://discourse.itk.org/u/Niels_Dekker)\
**Post date:** [November 21, 2017, 6:14pm UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/31 "2017-11-21T18:14:16Z")

</div>

The documentation says that the filter finds circles, as in the example data:  
 ![](https://discourse.itk.org/uploads/default/original/1X/d36ac2a4640d6ab378f1100d839130c14756ba89.png)

However, the filter can also be used to detect discs (a disc being a region bounded by a circle), assuming that the intensity within the disc is higher than outside the disc. Actually I think it will find a high-intensity-disc _more easily_ than a circle that only has high intensity pixels on the boundary, as the algorithm uses gradient vectors. For a high-intensity disc, the gradient vectors all point away from the disc center. For a high-intensity-circle-boundary, there are gradient vectors pointing away from the circle center, as well as gradient vectors _toward_ the circle center.

Should there be a note added to the documentation that the filter finds discs as well?

By the way, I did already adapt the test code, to directly pass an image of “discs” (generated by ‘CreateCircle’) to the Hough filter, instead of passing images of circle boundaries. I did so by removing the gradient filtering + thresholding preprocessing steps from the test: [http://review.source.kitware.com/#/c/22784/3/Modules/Filtering/ImageFeature/test/itkHoughTransform2DCirclesImageTest.cxx](http://review.source.kitware.com/#/c/22784/3/Modules/Filtering/ImageFeature/test/itkHoughTransform2DCirclesImageTest.cxx) That’s OK, right? It appears to perform just fine (or better) without those preprocessing steps.

---

<div class="post-metadata">

**Author:** ![dzenanz](https://discourse.itk.org/user_avatar/discourse.itk.org/dzenanz/32/1093_2.png) [@dzenanz](https://discourse.itk.org/u/dzenanz)\
**Post date:** [November 21, 2017, 8:48pm UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/32 "2017-11-21T20:48:10Z")

</div>

Expansion and clarification of the documentation is always welcome! The process is same as for code modification (submit to Gerrit etc).

---

<div class="post-metadata">

**Author:** ![Niels\_Dekker](https://discourse.itk.org/letter_avatar_proxy/v4/letter/n/9d8465/32.png) [@Niels\_Dekker](https://discourse.itk.org/u/Niels_Dekker)\
**Post date:** [November 23, 2017, 6:07pm UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/33 "2017-11-23T18:07:11Z")

</div>

OK, here is my proposed expansion of the documentation: “DOC: Mentioned that HoughTransform2DCirclesImageFilter also finds discs”, [http://review.source.kitware.com/#/c/22821/](http://review.source.kitware.com/#/c/22821/)

By the way, the link from the documentation main page of HoughTransform2DCirclesImageFilter to its example documentation page is broken. At [https://itk.org/Doxygen/html/classitk\_1\_1HoughTransform2DCirclesImageFilter.html](https://itk.org/Doxygen/html/classitk_1_1HoughTransform2DCirclesImageFilter.html) (at the section “Wiki Examples”).

If you can fix it, please do 🙂

---

<div class="post-metadata">

**Author:** ![dzenanz](https://discourse.itk.org/user_avatar/discourse.itk.org/dzenanz/32/1093_2.png) [@dzenanz](https://discourse.itk.org/u/dzenanz)\
**Post date:** [November 23, 2017, 6:24pm UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/34 "2017-11-23T18:24:12Z")

</div>

@matt.mccormick has been updating documentation system recently. Matt, can you fix the broken link?

---

<div class="post-metadata">

**Author:** ![matt.mccormick](https://discourse.itk.org/user_avatar/discourse.itk.org/matt.mccormick/32/7_2.png) [@matt.mccormick](https://discourse.itk.org/u/matt.mccormick)\
**Post date:** [December 1, 2017, 2:08pm UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/35 "2017-12-01T14:08:48Z")

</div>

[Here’s a patch](http://review.source.kitware.com/#/c/22843/) to fix the broken documentation link.

---

<div class="post-metadata">

**Author:** ![Niels\_Dekker](https://discourse.itk.org/letter_avatar_proxy/v4/letter/n/9d8465/32.png) [@Niels\_Dekker](https://discourse.itk.org/u/Niels_Dekker)\
**Post date:** [December 10, 2017, 12:20pm UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/36 "2017-12-10T12:20:46Z")

</div>

FYI, I just had a closer look at how the patch I proposed last week, _“PERF: Improved speed of copying and resizing NeighborhoodAllocator”_ [http://review.source.kitware.com/#/c/22862/](http://review.source.kitware.com/#/c/22862/) would affect the performance of ITK’s Hough Transform.

I observed a 10% reduction (approximately) of the duration of _filter-\>Update()_, typically going from 50 to 45 seconds, on the following test program, using VS2017, Release, 64-bit:

```
#include <itkHoughTransform2DCirclesImageFilter.h>
#include <iostream>
#include <ctime>

int main()
{
  typedef unsigned char PixelType;
  const auto image = itk::Image<PixelType>::New();
  enum { sizeX = 4096, sizeY = sizeX };
  image->SetRegions({ sizeX, sizeY });
  image->Allocate();
  image->FillBuffer(1);

  const auto filter =
    itk::HoughTransform2DCirclesImageFilter<PixelType, unsigned char, double>::New();
  filter->SetInput(image);

  const auto time1 = std::time(nullptr);
  filter->Update();
  const auto time2 = std::time(nullptr);

  std::cout << "Duration: " << (time2 - time1) << " seconds" << std::endl;
}

```

HoughTransform2DCirclesImageFilter::GenerateData() indirectly does a lot of Neighborhood allocations, by calling GaussianDerivativeImageFunction::EvaluateAtIndex on each input pixel \> Threshold.

---

<div class="post-metadata">

**Author:** ![dzenanz](https://discourse.itk.org/user_avatar/discourse.itk.org/dzenanz/32/1093_2.png) [@dzenanz](https://discourse.itk.org/u/dzenanz)\
**Post date:** [December 10, 2017, 2:38pm UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/37 "2017-12-10T14:38:36Z")

</div>

As that patch does not make big changes, I am in favor of merging it before release. @matt.mccormick, @blowekamp, @fbudin?

---

<div class="post-metadata">

**Author:** ![matt.mccormick](https://discourse.itk.org/user_avatar/discourse.itk.org/matt.mccormick/32/7_2.png) [@matt.mccormick](https://discourse.itk.org/u/matt.mccormick)\
**Post date:** [December 10, 2017, 5:47pm UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/38 "2017-12-10T17:47:22Z")

</div>

This is a good patch, but we should keep to the feature freeze. Small patches still have unintended consequences. We want a robust release. It will be merged soon, and the next release will come soon enough.

---

<div class="post-metadata">

**Author:** ![Niels\_Dekker](https://discourse.itk.org/letter_avatar_proxy/v4/letter/n/9d8465/32.png) [@Niels\_Dekker](https://discourse.itk.org/u/Niels_Dekker)\
**Post date:** [December 18, 2017, 5:38pm UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/39 "2017-12-18T17:38:31Z")

</div>

GaussianDerivativeImageFunction::EvaluateAtIndex is called many times during an Update() of HoughTransform2DCirclesImageFilter. Can someone please explain this function to me?

Specifically, I see the center of all of its kernels is set to zero (both on line 267 and 277):

[https://github.com/Kitware/ITK/blob/v4.13rc02/Modules/Core/ImageFunction/include/itkGaussianDerivativeImageFunction.hxx#L267](https://github.com/Kitware/ITK/blob/v4.13rc02/Modules/Core/ImageFunction/include/itkGaussianDerivativeImageFunction.hxx#L267)

Do you know why it does so?

_Update (19 December 2017):_ Do you agree that ‘centerval’ is always zero, after the first EvaluateAtIndex call? If so, doesn’t the following patch basically produce the same result as the original code (while being much faster)? “WIP: Removed blurring from GaussianDerivativeImageFunction::EvaluateAtIndex”, [http://review.source.kitware.com/#/c/22926/](http://review.source.kitware.com/#/c/22926/)

---

<div class="post-metadata">

**Author:** ![Niels\_Dekker](https://discourse.itk.org/letter_avatar_proxy/v4/letter/n/9d8465/32.png) [@Niels\_Dekker](https://discourse.itk.org/u/Niels_Dekker)\
**Post date:** [December 23, 2017, 10:09am UTC](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350/40 "2017-12-23T10:09:55Z")

</div>

@dzenanz Thanks for recognizing the GaussianDerivativeImageFunction::EvaluateAtIndex bug, at [http://review.source.kitware.com/#/c/22926/](http://review.source.kitware.com/#/c/22926/) Hope someone can still explain the intention of the function, and how to properly fix it!

There’s another major bug in GaussianDerivativeImageFunction, which directly affects HoughTransform2DCirclesImageFilter. Its protected helper function RecomputeGaussianKernel() may or may not use the image spacing. You see, it has a member m\_UseImageSpacing, which is always true. It _cannot_ be set by the user! That would suggest that the spacing is _always_ used, right? RecomputeGaussianKernel() is called in the default-constructor of GaussianDerivativeImageFunction. But within the default-constructor, the image spacing is not yet known! So then the image spacing is still ignored! GaussianDerivativeImageFunction::SetSigma does call RecomputeGaussianKernel() again, but _only_ when the new sigma is _different_ from the previous one. When HoughTransform2DCirclesImageFilter does set sigma to 1.0 (which is the default), SetSigma usually does not call RecomputeGaussianKernel(), because sigma has not changed.

Note that SetSigma should be called _after_ SetInputImage, because otherwise, RecomputeGaussianKernel() will use the spacing of the previous input image (if any). Note also that SetInputImage does _not_ call RecomputeGaussianKernel().

See [https://github.com/Kitware/ITK/blob/v4.13.0/Modules/Core/ImageFunction/include/itkGaussianDerivativeImageFunction.hxx](https://github.com/Kitware/ITK/blob/v4.13.0/Modules/Core/ImageFunction/include/itkGaussianDerivativeImageFunction.hxx)

[Previous page](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350.md?page=1)

[Next page](https://discourse.itk.org/t/hough-transform-2d-circles-image-filter-getcircles-patch/350.md?page=3)