# Calculating Haar features

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}$$

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...