How to Solve the Image Dehazing Problem Using ADMM?

Question

I want to solve the image dehazing problem using ADMM.

I want to use the proximal algorithm to optimize each element.

I refer to this treatise: Efficient image dehazing with boundary constraint and contextual regularization.

From the above paper, we solve the following optimal solution problem in order to erase the haze added to the image.

$$\min\frac{1}{2}\Vert{x-g}\Vert_2^2+\Vert w\circ (D x)\Vert_1 \tag 1$$

Where, $x$ is reconstructed haze map, $g$ is detected haze map, $D$ is the differential operator ($3☓3 $ kirsch and Laplacian operator for preserving image edges and corners) , $\circ$ is the element-wise multiplication operator, and $w$ is the weighting function which is related to the squared difference between the two neighboring pixels.

Equation (1) can be stably solved using the intermediate variable $r$ as follows:

$$r=(w\circ (Dx^{(k)}) )\tag2$$

Then, the augmented Lagrangian of equations (1):

$$L(x^{(k)},r,y)=\frac{1}{2}\Vert{x^{(k)}-g}\Vert_2^2+\Vert{r}\Vert_1-y(r-w\circ (Dx^{(k)}) )+\frac{ρ}{2}\Vert{r-w\circ (Dx^{(k)}) }\Vert_2^2 \tag3$$

Where y is the Lagrange multiplier of the constraint $r$ in the row and column directions.

To solve with ADMM, equation (3) is applied to the sub-problems, (the other two variables are omitted.) This question is about how to solve this equation.

[x-update]

$$x^{(k+1)}=\mbox{argmin}\frac{1}{2}\Vert{x^{(k)}-g}\Vert_2^2-y(r-w\circ (Dx^{(k)}) )+\frac{ρ}{2}\Vert{r-w\circ (Dx^{(k)}) }\Vert_2^2 \tag4$$

[What I want you to tell me]

①To calculate the gradient of Eq. (4), when Eq. (4) is differentiated and set to 0，I don't know how to handle $w$ and $D$ operator. Will they be transposed???

② Should I solve this equation directly using MATLB etc.?

[I edited it.]

Vectors => small letters.

Matrices => capital letters.

$D$ is matrix form convolution operator.(if $g$ is $n×n$,then $D$ is $n^{2}× n^{2}$.)

Answer 1

The function is given by:

$$ f \left( \boldsymbol{x} \right) = \frac{1}{2} {\left\| \boldsymbol{x} - \boldsymbol{g} \right\|}_{2}^{2} - { \boldsymbol{y} }^{T} \left( \boldsymbol{r} - \boldsymbol{w} \odot \left( D \boldsymbol{x} \right) \right) + \frac{\rho}{2} {\left\| \boldsymbol{r} - \boldsymbol{w} \odot \left( D \boldsymbol{x} \right) \right\|}_{2}^{2} $$

Where $ \odot $ is the Hadamard Product.

Remark: Pay attention that I used $ \boldsymbol{y} $ as a vector (You missed the transpose there).

The gradient is given by:

$$ \frac{\partial f \left( \boldsymbol{x} \right) }{\partial \boldsymbol{x}} = \boldsymbol{x} - \boldsymbol{g} + {D}^{T} \left( \boldsymbol{y} \odot \boldsymbol{w} \right) - \rho {D}^{T} \left( \left( \boldsymbol{r} - \boldsymbol{w} \odot \left( D \boldsymbol{x} \right) \right) \odot \boldsymbol{w} \right) $$

This is a linear function of $ \boldsymbol{x} $ henec you'll be able to extract a closed form of $ \boldsymbol{x} $.

Solving it directly or by iterative solver depends on the dimension of $ \boldsymbol{x} $.