# How to Solve the Image Dehazing Problem Using ADMM?

I want to solve the image dehazing problem using ADMM.

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

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

• I think you need to get the notation straight. For instance, it seems that $W$ is a vector, not a function. If you use small letter for vectors and capital letters for matrices I will solve it.
– Royi
Jun 21, 2021 at 5:29
• Thank you for your reply. Is it mean that vector : $W$ -> $w$? Jun 21, 2021 at 22:56
• It means that in order to solve it we need the dimensions of each element.
– Royi
Jun 22, 2021 at 3:32
• I am dealing with n☓n images. (n=512) So, $g, x, y, r, w$ is vector : $n^{2}$, and $D$ is convolution operator matrices : $n^{2}×n^{2}$. Jun 22, 2021 at 8:15
• If $D$ is a convolution operator in the form of a matrix the operation on ${x}^{k}$ should be a matrix multiplication and not convolution. So you can remove this.
– Royi
Jun 22, 2021 at 17:06

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

$$\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}$$.
• Thank you for your answer! I almost understood. There is only one thing I don't understand. I don't understand why $w$ in the last term is at the end. Jun 25, 2021 at 4:20