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?


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.