1
$\begingroup$

I am confused on how to solve this problem, does anyone have any ideas?

https://www.merl.com/publications/docs/TR2004-043.pdf

For a Haar filter $H \in \mathbb{R}^{3 \times 5}$ defined as below:

What is the equation to calculate the Haar features using integral image II?

In this problem an input images is $I \in \mathbb{R}^{m \times n}$ and integral image is denoted by $II\in \mathbb{R}^{m \times n}$

$H = \begin{bmatrix} 0 & -1 & -1 & 1 & 0\\ 0 & -1 & -1 & 1 &0\\ 0 & -1 & -1 & 1&0\\ \end{bmatrix}$

$\endgroup$
2
$\begingroup$

As mentioned the Haar filters use a lookup table with the say $A_{i,j} = \sum_{k=0}^{i} \sum_{l=1}^{j} I_{k,l}$

Now consider a the convolution with a filter $H \in \mathbb{R}^{m \times n}$, such that $H_{i,j}=1$, the convolution will can be calculated as $$\begin{eqnarray}Y_{i,j} &=& \sum_{k=1}^{m} \sum_{l=1}^{n} H_{k,l} I_{i-k+1, j-k+1} \\ &=& \sum_{k=1}^{m} \sum_{l=1}^{n} I_{i-k+1, j-k+1} \\ &=& \sum_{k=i-m+1}^{i} \sum_{l=j-n+1}^{j} I_{k, l} \\ &=& \sum_{k=i-m+1}^{i} \left( \sum_{l=0}^{j} I_{k, l} - \sum_{l=0}^{j-n} I_{k, l}\right) \\ &=& \sum_{k=0}^{i} \left( \sum_{l=0}^{j} I_{k, l} - \sum_{l=0}^{j-n} I_{k, l}\right) - \sum_{k=0}^{i-m+1} \left( \sum_{l=0}^{j} I_{k, l} - \sum_{l=0}^{j-n} I_{k, l}\right)\\ &=& \left(A_{i,j} - A_{i,j-n}\right) - \left( A_{i-m,j} - A_{i-m, j-n}\right)\\ \end{eqnarray} $$

Of course you can generalize this for $H_{i,j} = c$ for constant $c$ (by multiplying the resulting image), and you can use the shifting properties of the convolution if the filter is padded.

Now looking to your $H$, it can be decomposed in two rectangular regions constant regions. It can be decomposed as

$$H_1 + H_2 = \begin{bmatrix} 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 \\0 & 0 & 0 & 1 & 0\end{bmatrix} + (-1) \begin{bmatrix} 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \end{bmatrix}$$

To convolve with a the non-zero submatrix of $H_1$, a matrix in $\mathbb{R}^{3 \times 1}$ you will use $A_{i,j} + A_{i-3, j-1} - A_{i, j-1} - A_{i-3,j}$

To convolve with the non-zero submatrix of $H_2$, a matrix in $\mathbb{R}^{3 \times 2}$ you will use $A_{i,j} + A_{i-3, j-2} - A_{i, j-2} - A_{i-3,j}$

Of course you can have other conventions for the indices...

$\endgroup$

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.