4
$\begingroup$

So, I have this problem where I want to apply a kernel to an image and count the number of matches that happened.

So for example, if I have the kernel: $$\begin{bmatrix} 1 & 2 & 1\\ 1 & 2 & 1\\ 1 & 2 & 1\\ \end{bmatrix}$$ And the image: $$\begin{bmatrix} 1 & 1 & 2 & 1 & 2\\ 1 & 1 & 2 & 1 & 2\\ 1 & 1 & 2 & 1 & 2\\ \end{bmatrix}$$ The result should be (ignoring the borders): $$\begin{bmatrix} 3 & 9 & 0\\ \end{bmatrix}$$ Explanation: when the kernel is in the first position (2,2), the 3 left ones match to the kernel, in the middle position (3,2) all 9 elements match and in the right (4,2) there is no match.

I ended up doing two convolutions (or correlations), one to count the numner of ones and one to count the number of twos.

For example: First convolution (to count where value is 1): $$\begin{bmatrix} 1 & 0 & 1\\ 1 & 0 & 1\\ 1 & 0 & 1\\ \end{bmatrix}$$ $$\begin{bmatrix} 1 & 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 1 & 0\\ 1 & 1 & 0 & 1 & 0\\ \end{bmatrix}$$ Result: $$\begin{bmatrix} 3 & 6 & 0 \end{bmatrix}$$ Second convolution (to count where value is 2): $$\begin{bmatrix} 0 & 1 & 0\\ 0 & 1 & 0\\ 0 & 1 & 0\\ \end{bmatrix}$$ $$\begin{bmatrix} 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 0 & 1\\ \end{bmatrix}$$ Result: $$\begin{bmatrix} 0 & 3 & 0 \end{bmatrix}$$

At the end I add up the results to get the expected result. The problem is that if my image has 256 values, I have to do that 256 times and it becomes 256x slower than a convolution. Still, this ends up being faster than doing for loops and checking all kernel positions. This is partly due to the fourier transform that makes convolution faster.

My question is if it is possible to apply this operation faster? Maybe by just modifying the convolution a little bit?

EDIT: My kernel has maximum size 64x64 and my image has size around 300x300. If I use the standard kernel convolution (Direct Convolution), then it will try to match the kernel for every position of the image. To match the kernel it takes 64x64 comparisons, and it will do that for every position in the image (300x300), so this will take 300x300x64x64 comparisons (total 368.640.000 operations).

If I compute first the fourier transform of the images (FFT Convolution), then I can do the multiplication directly and it will cost only (300x300 operations). There is a cost to compute the fourier of the images in the first place, so at the end it will take around 300x300xlog(300)xlog(300) operations (this takes a total of around 500.000 operations).

OpenCV has a convolution method (filter2D) and a template matching method (matchTemplate) that are very fast, and I believe they use fourier plus some other optimizations.

The function matchTemplate in OpenCv has different methods to compute the match https://www.docs.opencv.org/2.4/doc/tutorials/imgproc/histograms/template_matching/template_matching.html, but none of them work for what I need.

What I need is a function to count the matches, and I want to know if it is possible to that similar to other template matching methods in opencv (that I assume use the FFT Convolution).

An approximate result should be fine, so if the output for the first example is, lets say, [3.28, 9.45, 0.32], it shouldn't be a problem.

$\endgroup$
  • 1
    $\begingroup$ Could you please details your calculations regarding the cost of convolution, FFT, or template matching? $\endgroup$ – Laurent Duval Jul 24 '18 at 21:15
  • $\begingroup$ I edited the question with more info $\endgroup$ – klaus Jul 25 '18 at 4:58
  • $\begingroup$ In OpenCV docs.opencv.org/2.4/doc/tutorials/imgproc/histograms/… I see a lot of different similarity metrics, yet little Fourier $\endgroup$ – Laurent Duval Jul 25 '18 at 7:11
  • $\begingroup$ I couldn't find anything in the documentation, but in some stack overflow posts. For example, in one of the comments !here there is this comment: "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 ..." $\endgroup$ – klaus Jul 25 '18 at 15:51
  • 1
    $\begingroup$ ”it will take around 300x300xlog(300)xlog(300) operations” Not really, a lot more. The FFT is O(n log n), but it doesn’t do n log n operations, there is a scaling factor there too. And the scaling factor is quite large (depending on implementation, and on how well you can decompose n into small primes). Timing the computation is the only way you can say whether direct implementation is going to be too slow. Did you implement it and try it? You’ve got small images, I don’t think it’ll be slow at all! $\endgroup$ – Cris Luengo Jul 28 '18 at 15:32
5
+50
$\begingroup$

Besides what is discussed below (see for instance the above Cris Luengo's comment): for reasonably-sized images, and modern computing techniques, I can see no reason in practice why the basic template match counting could be slow, and why one should look for faster, imprecise and incomplete alternatives.

[UPDATE 20180730] You are trying to compare matches in a pair of matrices. Ontologically, the comparison operation is not a linear operation. Hence, no convolution operation, naturally linear, seems be the easiest approach. Neither the FFT or Fourier stuff in general, as they are quite related to linearity.

IMHO, you ought to look at the concept of Template Matching, and avoid the notion of kernel, which is a debated notion.

Instead, a simple counting approach could do the job. For instance in Matlab:

%% The OP kernel and image
% dataKernel = [1 2 1;1 2 1;1 2 1;];
% dataImage = [1 1 2 1 2;1 1 2 1 2;1 1 2 1 2;];

%% A random kernel and image
dataKernel = floor(256*rand(64,64));
dataImage = floor(256*rand(300,300));

%% Compute sizes
[nRowKernel,nColKernel] = size(dataKernel);
[nRowImage,nColImage] = size(dataImage);

[nRowCrop] = nRowImage - nRowKernel+1;
[nColCrop] = nColImage - nColKernel+1;

lMatch = zeros(nRowCrop,nColCrop);
dataImageCrop = zeros(size(dataKernel));

tic;
for iRowCrop = 1:nRowCrop;
    for iColCrop = 1:nColCrop;
        dataImageCrop = dataImage(iRowCrop:iRowCrop+nRowKernel-1,iColCrop:iColCrop+nColKernel-1); % Crop a portion of the image
        lMatch(iRowCrop,iColCrop) = length(find(dataImageCrop - dataKernel == 0));
    end
end

Here, I just used an ad-hoc displacement for the crop, but than could be automated easily. No product, just differences. If your data are limited size integer, there might be more options for speed. But even in Matlab, this is relatively fast.

FFT-based cosine similarity for fast template matching seems to better explain what is alluded too in OpenCV performance on template matching (provided by the OP). If the image is of size $I_x \times I_y$, and the template is $T_x \times T_y$, with $T_x < I_x$ and $T_y < I_y$, you can expect a number of operations of:

  • $O(I_xI_y T_x T_y)$ with the standard comparison,
  • $O(I_xI_y\log I_x \log I_y)$ with a Fourier method.

From afar, Fourier might seem to be beneficial whenever $\log I_x \log I_y < T_x T_y$. But:

  • this is only an asymptotic result the constant behind the $O(\cdot)$ can make a huge difference
  • then you have to find maxima, which add to the overall cost
  • the hardware implementation (pipeline, CPU/GPU) can made a lot of difference in practice, compared to number of operations
  • indeed, the first one only require adds/subtracts and absolute values on integers, the second complex operations on floats; thus, there might be huge variations between implementations
  • a difference of pixels, like the sum of absolute difference (SAD) does not translate easily in Fourier because it is orthogonal
  • implementing fast correlations, the FFT might be able to provide you with a "best match", but it is not local, so I cannot imagine right now how this can directly give you a count by patch location.

So far, to me:

  • if you only want a best match, then you can do Fourier on the whole image;
  • if you really want (even approximate) counts at all template locations, I do not see an easy and useful Fourier implementation for that so far.

However, you can speed the matching up, with several tricks, like using the symmetry of the template (if any), the integral image, multiscale pyramid-like matching, etc. A few additional pointers:

$\endgroup$
  • $\begingroup$ Isn't that the same as doing for loops, checking all kernel positions and counting the matches? If so, this takes O(MNmn) and is too slow compared to the fourier version (stackoverflow.com/questions/16164749/…) $\endgroup$ – klaus Jul 24 '18 at 16:40
  • $\begingroup$ Thanks for the insights, they have been helpful. So, even if I want approximate counts at all locations, you think the best approach would still be to do the standard comparison? Actually I only need the point with the most matches, so I am thinking of using a fast template matching using SQDIFF to find candidate points and then use the standard comparison to find which one gives me the most matches. $\endgroup$ – klaus Jul 30 '18 at 3:44
  • $\begingroup$ I wouldn't say this is the best. Indeed, it depends somehow on your actual goals. From "all counts" to "only one point with most matches", there is a distance, and there are probably many tricks that can be used, using pyramids, integral images and so on. Yet I think there are many optimized librairies $\endgroup$ – Laurent Duval Jul 30 '18 at 6:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.