Count Matches to a Kernel

Question

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.

Answer 1

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:

• Fast Template Matching
• Fast Template Matching With Polynomials
• FasT-Match: Fast Affine Template Matching - The Computer Vision ...
• Very Fast Template Matching