FREAK reconstruction as an inverse problem

4 min read

In a previous post, I have briefly introduced our FREAK descriptor, which belongs to the more general family of the LBPs. In this post, I will state mathematically the problem of the reconstruction of an image patch given its descriptor, i.e. answering the question:

Can you guess which image part created this particular description vector ?

As far as we have seen, there is only one recent article [WJP11] addressing the same question. In this work, Weinzaepfel and his co-authors first learn the relationship between SIFT descriptors and image patches in a database. It’s like considering that the SIFT descriptor is the key used to sort a dictionary of image parts. The core of the inversion process is a lookup operation in this database given an observed descriptor.

Our approach

We chose a somewhat more brutal approach, by considering instead the case where no external information is available. Since it is an ill-posed problem1, embracing the reconstruction task then naturally calls for a regularized inverse problem approach.

Ingredients of the regularized inverse problem

This approach is quite common among image processing tasks, hence I will directly give its formulation (see the paper for the details).

Regularization function

We chose as regularizer the Total Variation, i.e. the norm of the gradient (and not its squared norm as in Tikhonov). It seemed to be a good fit because :

  1. it promotes sharp, piecewise-flat results, which is a good model for small image patches (typically 32x32 pixels);
  2. it is expressed in the image domain (a.k.a. analysis) , not in a coefficient space (a.k.a. synthesis, e.g. wavelet domain), like the LBP that we want to invert.

Data term

We chose the $\ell_1$-norm for the data term. This norm is known to be robust to salt-and-pepper noise, hence it will show some robustness to misestimations of the pixel-wise error, which is good in our case (recall that in the limit we only have access to the sign of the difference between pixels, and not its value).

Furthermore, although it’s not differentiable, the proximal mapping of its Fenchel-Legendre conjugate is easy to compute.

Primal-dual solver

The regularization term and the data term are completed by a set indicator function to guide the minimization process, and finally we have an initial equation which is convex, but non-differentiable, because of the $\ell_1$-norm in the data term and in the Total Variation:

$$\hat{x} = \underset{x}{\operatorname{argmin}}~\underbrace{ \lambda | A_{\mathcal L}x - g|_1 }_{ \text{data term} }+\underbrace{ | p |_\text{TV} + \delta_{\mathcal S}(x) }_{\text{regularization} },$$

where $x$ and $g$ are respectively the unknown and the observation, $A$ is the LBP, and $\mathcal{S}$ is a set of acceptable solutions.

After a bit of cooking2, this problem boils down to :

$$\underset{x}{\operatorname{argmin}}~F(Kx) + G(x), $$

with $K = \left(\begin{array}{c} A_{\mathcal L} \\\ \nabla \end{array}\right)$ and $Kx = (y, z)^T = (A_\mathcal{L}x, \nabla x)^T$.

$G$ is the remaining part of the initial constraints, i.e. the indicator function of $\mathcal{S}$.

This formula is interesting because we have 2 independent constraints inside $F$ :

$$F(Kx) = F_1(y) + F_2(z) = \lambda | y - g |_1 + | z |_1. $$

Furthermore, the different members of the final expression may not be differentiable, but it is convex and we know how to compute efficiently their proximal mapping (or equivalently, the proximal mapping of their Fenchel-Legendre conjugate). Hence, we can apply the primal-dual solver presented in [CP10] to solve it.

Where to go next ?

Upcoming post

In the next post of the series, I’ll explain how we modeled the LBPs to create a linear operator $A_\mathcal{L}$, before moving on to the implementation.

If you don’t want to miss the next posts, please subscribe to the blog ! You can also follow me on Twitter.

References for further reading

  1. The description is given by a projection, hence we’re losing information. ^
  2. See the paper for more hints, or come at the ICPR conference to have a chat! ^
research lbp en

Related