2
$\begingroup$

Consider an array $X$ with shape $H \times W$. Let $Y$ be the other array of the same shape and $Z$ is an array of shape $h \times w$.

We want to construct an array $R$ of shape $(H-h + 1, W-w+ 1)$ by the following rule:

$$\displaystyle R[k, l] = \sum_{i, j} (X[i,j] - Y[i,j])^2 +$$ $$ \sum_{i=0}^{h-1}\sum_{j=0}^{w-1}[(X[k + i, l + j] - Z[i, j])^2 - (X[k + i, l + j] - Y[k + i, l + j])^2]$$

So it's better to represent it via the image: we erase some subarray of size $h \times w$ in $X - Y$, change it by $X_{h, w} - Z$ and compute the sum of squares.

Using dynamic programming we can solve it pretty fast, but it's still a time-consuming process. I think that it's possible to calculate such an array using fast Fourier convolutions. But we need to determine convolution arrays to do that.

Any hints?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.