# Template Matching in SimpleITK

**URL:** <https://discourse.itk.org/t/template-matching-in-simpleitk/5735>\
**Category:** Algorithms\
**Tags:** itk, simpleitk, registration\
**Created:** [February 21, 2023, 1:21pm UTC](https://discourse.itk.org/t/template-matching-in-simpleitk/5735 "2023-02-21T13:21:34Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![elapins](https://discourse.itk.org/letter_avatar_proxy/v4/letter/e/96bed5/32.png) [@elapins](https://discourse.itk.org/u/elapins)\
**Post date:** [February 21, 2023, 1:21pm UTC](https://discourse.itk.org/t/template-matching-in-simpleitk/5735/1 "2023-02-21T13:21:34Z")

</div>

I have used template matching in previous code, and was wondering if template matching is available in SimpleITK? Or if there are specific functions that will achieve the same outcome?

Thank you!

---

<div class="post-metadata">

**Author:** ![zivy](https://discourse.itk.org/user_avatar/discourse.itk.org/zivy/32/1726_2.png) [@zivy](https://discourse.itk.org/u/zivy)\
**Post date:** [February 21, 2023, 1:46pm UTC](https://discourse.itk.org/t/template-matching-in-simpleitk/5735/2 "2023-02-21T13:46:31Z")

</div>

Hello @elapins,

The equivalent of template matching in ITK/SimpleITK would be the Exhaustive optimizer, see [this notebook](https://github.com/InsightSoftwareConsortium/SimpleITK-Notebooks/blob/master/Python/63_Registration_Initialization.ipynb) for a discussion in the context of initialization. A slightly different use case is shown in [this notebook](https://github.com/InsightSoftwareConsortium/SimpleITK-Notebooks/blob/master/Python/69_x-ray-panorama.ipynb).

---

<div class="post-metadata">

**Author:** ![elapins](https://discourse.itk.org/letter_avatar_proxy/v4/letter/e/96bed5/32.png) [@elapins](https://discourse.itk.org/u/elapins)\
**Post date:** [February 21, 2023, 2:44pm UTC](https://discourse.itk.org/t/template-matching-in-simpleitk/5735/3 "2023-02-21T14:44:38Z")

</div>

I have tried adding this type of exhaustive optimizer, and had some confusion about the step size/grid search. No matter what step sizes I use, does this search actually search the full image? I noticed that when I increased the grid size, the results varied and would be further away from the initialization points.

As well, is it possible to write a general template matching algorithm that will work for any image? Or will the inputs always vary dependent on the images being used?

---

<div class="post-metadata">

**Author:** ![zivy](https://discourse.itk.org/user_avatar/discourse.itk.org/zivy/32/1726_2.png) [@zivy](https://discourse.itk.org/u/zivy)\
**Post date:** [February 21, 2023, 6:42pm UTC](https://discourse.itk.org/t/template-matching-in-simpleitk/5735/4 "2023-02-21T18:42:46Z")

</div>

Hello @elapins,

The way the exhaustive optimizer works is by defining a grid in the transformation’s parameter space and using those parameter settings as the “registration result”. The metric is evaluated for each of these potential transformations and the one with the lowest value is returned as the result.

You need to have a clear understanding of your transformation’s parameter space and what are the appropriate bounds in which you are searching.

For example, a 2D rigid transformation parameterized as a translation and rotation angle, so we have a 3D parameter space. You need to identify the relevant search space. For example tx \in [-100, 10], ty \in [50, 700], \theta \in [0, \pi/4]. Then you need to decide on the grid. For example, sample tx every 0.5mm, sample ty every 5mm and sample \theta every \pi/8 radians.

You then feed this grid into the optimizer and get the parameters that provide the lowest metric value.

---

<div class="post-metadata">

**Author:** ![elapins](https://discourse.itk.org/letter_avatar_proxy/v4/letter/e/96bed5/32.png) [@elapins](https://discourse.itk.org/u/elapins)\
**Post date:** [February 23, 2023, 4:26pm UTC](https://discourse.itk.org/t/template-matching-in-simpleitk/5735/5 "2023-02-23T16:26:42Z")

</div>

For the example you just provided, what would the grid and step inputs be then? I am confused about how to get the correct bounds and steps inputted.

THank you!!!

---

<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:** [February 24, 2023, 2:21pm UTC](https://discourse.itk.org/t/template-matching-in-simpleitk/5735/6 "2023-02-24T14:21:10Z")

</div>

The [FFTNormalizedCorrelationImageFilter](https://simpleitk.org/doxygen/latest/html/classitk_1_1simple_1_1FFTNormalizedCorrelationImageFilter.html) performs template matching to find a global optimal solution when translation is the solvable parameter.

The maximum of the the cor-filter needs to be found and a transform constructed. Here is some pseudo code:

```auto
    print("FFT Correlation...")
    out = sitk.FFTNormalizedCorrelationImageFilter(image, template)

    print("Detecting peak...")
    out = sitk.SmoothingRecursiveGaussian(out)
    print("\tConnected components and maxima...")
    cc = sitk.ConnectedComponent(sitk.RegionalMaxima(out, fullyConnected=True))
    print("\tLabel statistics...")
    stats = sitk.LabelStatisticsImageFilter()
    stats.Execute(out, cc)
    labels = sorted(stats.GetLabels(), key=lambda l: stats.GetMean(l))

    peak_pt = out.TransformContinuousIndexToPhysicalPoint(stats.GetBoundingBox(labels[-1])[::2])
    peak_value = stats.GetMean(labels[-1])

    center_pt = out.TransformContinuousIndexToPhysicalPoint([p / 2.0 for p in out.GetSize()])

    translation = [c - p for c, p in zip(center_pt, peak_pt)]
    translation += [0] * image.GetDimension() - len(translation))

    print("FFT peak correlation of {0} at translation of {1}".format(peak_value, translation))

```

---

<div class="post-metadata">

**Author:** ![elapins](https://discourse.itk.org/letter_avatar_proxy/v4/letter/e/96bed5/32.png) [@elapins](https://discourse.itk.org/u/elapins)\
**Post date:** [March 8, 2023, 4:24pm UTC](https://discourse.itk.org/t/template-matching-in-simpleitk/5735/7 "2023-03-08T16:24:56Z")

</div>

hi @blowekamp ,

Thank you so much for your help! I am just confused about the following lines of code in your pseudo code:

> translation = [c - p for c, p in zip(center\_pt, peak\_pt)]  
> translation += [0] \* image.GetDimension() - len(translation))

I keep getting an error with the second line _“unsupported operand type(s) for -: ‘list’ and ‘int’”_

Could you explain to me what these two lines are exactly doing? I am trying to re-write this in c++ as well, so any guidance on this section would be great.

Thank you!

---

<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:** [March 8, 2023, 4:29pm UTC](https://discourse.itk.org/t/template-matching-in-simpleitk/5735/8 "2023-03-08T16:29:06Z")

</div>

> [@elapins](#):
>
> translation += [0] \* image.GetDimension() - len(translation))

I believe this line is suppose to pad translation with zeros so that it’s the length of the image’s dimensions.

---

<div class="post-metadata">

**Author:** ![elapins](https://discourse.itk.org/letter_avatar_proxy/v4/letter/e/96bed5/32.png) [@elapins](https://discourse.itk.org/u/elapins)\
**Post date:** [March 8, 2023, 4:32pm UTC](https://discourse.itk.org/t/template-matching-in-simpleitk/5735/9 "2023-03-08T16:32:29Z")

</div>

what is the [0] supposed to be indexing?

---

<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:** [March 8, 2023, 4:33pm UTC](https://discourse.itk.org/t/template-matching-in-simpleitk/5735/10 "2023-03-08T16:33:36Z")

</div>

The above was just “pseudo” code. I think it was suppose to be constructing a list of just one element with the zero value.

---

<div class="post-metadata">

**Author:** ![elapins](https://discourse.itk.org/letter_avatar_proxy/v4/letter/e/96bed5/32.png) [@elapins](https://discourse.itk.org/u/elapins)\
**Post date:** [March 8, 2023, 4:35pm UTC](https://discourse.itk.org/t/template-matching-in-simpleitk/5735/11 "2023-03-08T16:35:45Z")

</div>

ok thanks! Is the translation output with respect to the center of the image? or top left corner