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 ?

### Related work

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 problem^{1}, 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 :

- it promotes
**sharp, piecewise-flat**results, which is a good model for small image patches (typically 32x32 pixels); - 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 cooking^{2}, 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

- The FREAK home page
- [DAV12] Reconstructing FREAKs: Beyond Bits: Reconstructing Images from Local Binary Descriptors
- [WJP11] Weinzaepfel, P., Jegou, H., & Pérez, P. (2011). Reconstructing an image from its local descriptors (pp. 337–344). Presented at the 2011 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). preprint
- [CP10] Chambolle, A., & Pock, T. (2010). A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging. Journal of Mathematical Imaging and Vision, 40(1), 120–145. preprint

- The description is given by a projection, hence we’re losing information.
^{^} - See the paper for more hints, or come at the ICPR conference to have a chat!
^{^}