30

Let us assume we are looking for this template:

Stop

The corners of our template are transparent, so the background will vary, like so:

Stop on moon

Stop on everest

Stop on leaves

Assuming we could use the following mask with our template:

Stop Stop mask

It would be very easy to find it.

What I have tried:

I have tried matchTemplate but it doesn't support masks (as far as I know), and using the alpha channel (transparency) in the template does not achieve this, as it compares the alpha channels instead of ignoring those pixels.

I have also looked into "region of interest", which I thought would be the solution, but with it you can only specify a rectangular area. I'm not even sure if it works on the template or not.

I'm sure this is possible to do by writing my own algorithm, but I was hoping this is possible via. standard OpenCV to avoid reinventing the wheel. Not to mention, it would most likely be more optimised than my own.

So, how could I do something like this with OpenCV + Python?

Community
  • 1
  • 1
user1973386
  • 1,095
  • 2
  • 10
  • 18
  • 2
    It would help if you posted stuff that you've tried. Anyhow, a very interesting question. – Morgan Wilde Mar 17 '13 at 09:22
  • Thanks for the comment. I've added the stuff that I have tried, didn't think it was worth mentioning though. – user1973386 Mar 17 '13 at 09:50
  • 1
    Try matching keypoints using SIFT/SURF – Froyo Mar 17 '13 at 13:40
  • @Froyo Thanks for your comment. That would work, but it seems like overkill for something like this, not to mention from the examples that I have tried, keypoint matching was terribly slow. While out of scope of this question, are there OpenCV keypoint matchers that can match-to-many? For instance, being able to find multiple stop signs on the same image via. keypoint matching? – user1973386 Mar 18 '13 at 10:35
  • I have answered to a similar post in : http://stackoverflow.com/questions/35642497/python-opencv-cv2-matchtemplate-with-transparency/36047048#36047048 – Richard Mar 16 '16 at 21:15
  • Find the answer to a similar question there: http://stackoverflow.com/questions/35642497/python-opencv-cv2-matchtemplate-with-transparency/36047048#36047048 – Richard Mar 16 '16 at 21:20
  • Template matching using cv2.matchTemplate() does support masks. See https://docs.opencv.org/4.1.1/df/dfb/group__imgproc__object.html#ga586ebfb0a7fb604b35a23d85391329be. I have used that and it works. You could also just edge extract your image and your template and match the edge image and template. – fmw42 Mar 30 '21 at 20:10

6 Answers6

10

This could be achieved using only matchTemplate function, but a little workaround is needed.

Lets analyse the default metrics(CV_TM_SQDIFF_NORMED). According to matchTemplate documentation the default metrics looks like this

R(x, y) = sum (I(x+x', y+y') - T(x', y'))^2

Where I is image matrix, T is template, R is result matrix. Summation is done over template coordinates x' and y',

So, lets alter this metrics by inserting weight matrix W, which has the same dimensions as T.

Q(x, y) = sum W(x', y')*(I(x+x', y+y') - T(x', y'))^2

In this case, by setting W(x', y') = 0 you can actually make pixel be ignored. So, how to make such metrics? With simple math:

Q(x, y) = sum W(x', y')*(I(x+x', y+y') - T(x', y'))^2
        = sum W(x', y')*(I(x+x', y+y')^2 - 2*I(x+x', y+y')*T(x', y') + T(x', y')^2)
        = sum {W(x', y')*I(x+x', y+y')^2} - sum{W(x', y')*2*I(x+x', y+y')*T(x', y')} + sum{W(x', y')*T(x', y')^2)}

So, we divided Q metrics into tree separate sums. And all those sums could be calculated with matchTemplate function (using CV_TM_CCORR method). Namely

sum {W(x', y')*I(x+x', y+y')^2} = matchTemplate(I^2, W, method=2)
sum{W(x', y')*2*I(x+x', y+y')*T(x', y')} = matchTemplate(I, 2*W*T, method=2)
sum{W(x', y')*T(x', y')^2)} = matchTemplate(T^2, W, method=2) = sum(W*T^2)

The last element is a constant, so, for minimisation it does not have any effect. On the other hand, it still might me useful to see if our template have perfect match (if Q is approaching to zero). Nonetheless, for last element we actually do not need matchTemplate function, since it could be calculated directly.

The final pseudocode looks like this:

result = matchTemplate(I^2, W, method=2) - matchTemplate(I, 2*W*T, method=2) + as.scalar(sum(W*T^2))

Does it really do exactly as defined? Mathematically yes. Practically, there is some small rounding error, because matchTemplate function works on 32-bit floating-point, but I believe it is not a big problem.

Please note, that you can extent analysis and have weighted equivalents for any metrics offered by matchTemplate.

This actually worked for me. I am sorry I don't give actual code. I am working in R, so I don't have the code in Python. But idea is quite straightforward.

I hope this will help.

Kelvin Wang
  • 627
  • 5
  • 21
Vyga
  • 894
  • 8
  • 8
  • 1
    Practically your theory will not work. Why? Because matchTemplate() does not work as the OpenCV documentation says. It does not slide the template over the image and compares them pixel by pixel. If OpenCV would do this it would take 60 seconds to process an image of 500x500 pixel even in C++ code. What OpenCV does to optimize speed is to first calculate DFT (Fourier Transformation) of the image and the template and then compare them in the Fourier space. This makes execution 100 times faster but it makes your theory fail. – Elmue Sep 29 '14 at 13:40
  • @Elmue thanks for reply, but I would like to disagree. Firstly, CV_TM_CCORR – Vyga Oct 02 '14 at 08:49
  • 1
    @Elmue thanks for reply, but I would like to disagree. Yes, OpenCV makes smart calculations and I can noise by rounding errors. Nevertheless, with `CV_TM_CCORR` function we actually can calculate the values I have listed. At the end of the day, the final answer from the smart calculations are as in the formula. I actually did this in R and checked the answer by brute force functions. – Vyga Oct 02 '14 at 08:56
  • 1
    OK, if you really tried your theory in practice I will believe you. But your formula are interesting for someone with diploma in mathematics while normal programmers will feel very left alone with them. The OpenCV documentation is a shame and you add another headache with your formula. OpenCV is a C++ library and some C++ code would be extremely helpful. How do I calculate 2*w*T or sum(..) in C++ ? And what do you mean with as.scalar(sum(W*T^2)). What is 'as' ? You should explain that with some code! – Elmue Oct 04 '14 at 02:42
3

What worked for me the one time I needed this was to fill the "mask" areas with white noise. Then it gets effectively washed out of the correlation when looking for matches. Otherwise I got, as I presume you did, false matches on the masked areas.

KobeJohn
  • 7,390
  • 6
  • 41
  • 62
2

One answer to your question is convolution. Use the template as kernel and filter the image.

The destination Mat will have dense bright areas where your template might be. You'll have to cluster the results (e.g. Mean-shift).

In that way, you'll have a very simplistic implementation of the Generalized Hough Transform or a Template-based convolution matching.

LovaBill
  • 5,107
  • 1
  • 24
  • 32
2

Imagemagick 7.0.3.9 now has a masked compare capability so that you can limit the template matching region. See http://www.imagemagick.org/discourse-server/viewtopic.php?f=4&t=31053

Also, I see that OpenCV 3.0 now has masked template matching. See http://docs.opencv.org/3.0.0/df/dfb/group__imgproc__object.html#ga586ebfb0a7fb604b35a23d85391329be

However, it is only for method == CV_TM_SQDIFF and method == CV_TM_CCORR_NORMED. see python opencv matchTemplate is mask feature implemented?

Community
  • 1
  • 1
fmw42
  • 46,825
  • 10
  • 62
  • 80
1

ImageMagick has logic for finding subimages in other images and it works quite well.

compare -verbose -dissimilarity-threshold 0.1 -subimage-search subimage bigimage

I've used it to find and blur watermarks off some products. Don't ask.

(Sometimes you have to do what you have to do..)

wsdookadr
  • 2,584
  • 1
  • 21
  • 44
1

2021 Update: I've been trying to find a solution for transparency in templates throughout the day, and I think I finally found a way to do it. matchTemplate() has a mask parameter, which apparently works exactly like OP wants it to: ignore certain pixels from a template when searching for it in another image. And since my templates already contain transparency in them, I decided to use my template as both a template and mask parameter. Surprisingly, it worked.

I'm using JavaScript with opencv4nodejs, so the following python code snippet might be completely off, but the theory is there and I'm fairly positive it should work.

# Import OpenCV
import cv2 as cv

# Read both the image and the template
image = cv.imread("image.png", cv.IMREAD_COLOR)
template = cv.imread("template.png", cv.IMREAD_COLOR)

# Match with template as both template and mask parameter
result = cv.matchTemplate(image, template, cv.TM_CCORR_NORMED, None, template)

Here's a gist for JavaScript with opencv4nodejs if you're interested.

Now that I think about it, it seems really stupid and way too good to be true, but I've been getting good matches (0.98+) on most tests. Hope this helps!

Zebiano
  • 373
  • 5
  • 13