Interpolation Optimization Problem

I will try to give the motivation behind this problem and later the math formality.

Given a grayscale image (1 Channel - M by N Matrix).

Someone marks some pixels as anchors.

Now, you need to interpolate the other pixels (Which are not anchors) by minimizing a given cost function s.t. the end result is an image which has the original image values at the anchors and interpolated values else were s.t. it minimizes the cost function.

Given an $M$ by $N$ matrix (A 1 channel image for that matter) $ I $.

Subset of the elements (Pixels) in the matrix are marked as reference and their location is a group marked as $ S $.

The optimization cost function is given by:

$$ \sum_{\mathbf{r}} \left( E(\mathbf{r}) - \sum_{\mathbf{s} \in N(\mathbf{r})} {w}_{\mathbf{rs}} E(\mathbf{s}) \right)^2, \text{ s.t. } \forall p \in S \; E(\mathbf{p}) = I(\mathbf{p})\,, $$

where a bold letter $ \mathbf{p}, \mathbf{r}, \mathbf{s} $ means an element (Pixel) location.

The group $ N(r) $ is the neighborhood of $ \mathbf{r} $, which is size $ k $ namely, a $ k $ by $ k $ rectangle where $ \mathbf{r} $ is in the middle.

The weights $ {w}_{\mathbf{rs}} $ are defined as following:

$$ {w}_{\mathbf{rs}} \propto \exp\left(-\frac{(I(\mathbf{r}) - I(\mathbf{s}))^2}{2\sigma^2_r} \right )\ \ \text{ s.t. } \sum_{\mathbf{s} \in N(\mathbf{r})} w_{\mathbf{rs}} = 1\,. $$

Namely, the weights are normalized to 1 within the neighborhood. The variance is calculated on the matrix $ I $ in the neighborhood (You can assume it is given).

So the problem is to find a matrix $ E $ which is equal to $ I $ on all reference points and interpolates other places by bringing the cost function to minimum.

It looks like a weighted least squares per neighborhood (The inner brackets).

I couldn't formalize it (For the whole matrix) a way that can be easily calculated and solved in e.g. MATLAB.
Is there a way to formalize it as classic Weighted LS problem?

Or any other form which using the classic tools will bring s

Using few tricks the equation can be transformed into classic Quadratic Programming problem:

$ E = \arg \max_{E} \sum_{\mathbf{r}} \left( E(\mathbf{r}) - \sum_{\mathbf{s} \in N(\mathbf{r})} {w}_{\mathbf{rs}} E(\mathbf{s}) \right)^2 $

Defining $ \mathbf{e} = vec \left ( E \right ) $, Namely vectorizing the matrix, and defining a matrix $ A $ defined the proper usage of the weights $ {w}_{\mathbf{rs}} $, Namely put them in the correct entry at each row per pixel the above could be rewritten as:

$$ \mathbf{e} = \arg \max_{\mathbf{e}} {\left ( \mathbf{e} - A\mathbf{e} \right ) }^{T} \left ( \mathbf{e} - A\mathbf{e} \right ) = \arg \max_{\mathbf{e}} {\left( \left ( I - A \right ) \mathbf{e} \right )}^{T} \left( \left ( I - A \right ) \mathbf{e} \right ) $$

Defining $ B = I - A $ yields:

$$ \mathbf{e} = \arg \max_{\mathbf{e}} {\left( \left ( I - A \right ) \mathbf{e} \right )}^{T} \left( \left ( I - A \right ) \mathbf{e} \right ) = \arg \max_{\mathbf{e}} {\mathbf{e}}^{T} {B}^{T} B \mathbf{e} $$

Defining $ L = {B}^{T} B $ , namely $ L , is a Symmetric Positive Definite Matrix yields:

$$ \mathbf{e} = \arg \max_{\mathbf{e}} {\mathbf{e}}^{T} L \mathbf{e} $$

Adding the equality constraints using $ C \mathbf{e} = \mathbf{t} $ where $ \mathbf{t} $ is vectorization of all "Reference Pixels"

All in all this yields a Classic Quadratic Programming problem given by:

$$ \mathbf{e} = \arg \max_{\mathbf{e}} {\mathbf{e}}^{T} L \mathbf{e}, \; s.t. \; C \mathbf{e} = \mathbf{t} $$

Few notes:

• The matrix $ L $ is Symmetric and Positive Definite matrix and usually sparse (Assuming "Small Neighborhood").

• The matrix $ L $ wast built by the Matrix $ I - A $ which each row of it was normalized to be zero (Each row of $ A $ is normalized to 1 ).

Now two things are needed:

• Optimized fast algorithm to solve this problem utilizing its properties.

• Assuming the image is large, are the methods to solve this problem by blocks to avoid memory limits?

StackExchange Computer Science Q#23794, answer score: 5