Algorithms

The image-smoothing algorithms in Julia.

L0 Smooth

L0 Smooth (paper) is an image-smoothing algorthim through minimizing the L0 norm of image's gradient.

ImageSmooth.L0Smooth — Type

L0Smooth <: AbstractImageSmoothAlgorithm
L0Smooth(; λ=2e-2, κ=2.0, βmax=1e5)

smooth(img, f::L0Smooth)
smooth!(out, img, f::L0Smooth)

Smoothing img via L0 gradient minimization to approximate prominent structure in a sparsity-control manner.

Output

Return Array{Gray{N0f8}} for Gray input or Array{RGB{N0f8}} for RGB input.

Details

Using the strategy of minimizing the L0 norm of image's gradient.

This algorithm works particularly effective for sharpening major edges by increasing the steepness of amplitude transition while eliminating low-amplitude structures to some extent. See [1] for more details.

Options

The function argument is described in detail below.

λ::Float64

The argument 𝜆 is a weight directly controlling the significance of the L0 gradient norm term, which must be greater than zero.

A larger 𝜆 makes the smoothed image have very few edges.

Default: 2e-2

βmax::Float64

The argument βmax is the upper bound of 𝛽 in [1], which must be greater than 1e4.

In this algorithm, two auxiliary variables ℎ and 𝑣 are used to approximate the solution. A large enough 𝛽 ensures that the alternating optimization strategy based on introducing auxiliary variables is available.

Default: 1e5

κ::Float64

The argument 𝜅 is the iteraiton rate, which must be larger than 1.0.

This algorithm using an alternating optimization strategy to get the solution. In each iteration, the argument 𝛽 controls the similarity between gradient pair (𝛥₁𝑆ₚ, 𝛥₂𝑆ₚ) (denoted by $(\partial_x S_p, \partial_y S_p)$ in [1]) and auxiliary pair (ℎₚ, 𝑣ₚ). The argument 𝜅 is used to update 𝛽 as 𝛽 ⟵ 𝜅𝛽.

Default: 2.0

Examples

You can use the default arguments for L0Smooth, and then use smooth to apply the AbstractImageSmoothAlgorithm.

using TestImages
using ImageSmooth

img = testimage("cameraman")

fₛ = L0Smooth() # using default arguements
imgₛ = smooth(img, fₛ)

Manually setting the arguements is also available:

fₛ = L0Smooth(λ=0.0015, κ=1.05, βmax=2e5) # manually set the arguments
imgₛ = smooth(img, fₛ)

See also smooth! for in-place operation.

References

[1] Xu, L., Lu, C., Xu, Y., & Jia, J. (2011, December). Image smoothing via L 0 gradient minimization. In Proceedings of the 2011 SIGGRAPH Asia conference (pp. 1-12). DOI:10.1145/2024156.2024208

source

Using in the REPL

julia> using ImageSmooth
julia> L0Smooth()L0Smooth(0.02, 2.0, 100000.0)

Details of L0 Smoothing

For 2D image, the input image is denoted by $I$ and the computed result is denoted by $S$. The gradient $\nabla S_p=(\partial_x S_p,\partial_y S_p)^T$ for each pixel $p$ is calculated as forward difference along the $x$ and $y$ directions.

So, the L0 gradient term of this algorithm is denoted as follow:

\[C(S)=\#\left\{p\big| |\partial_x S_p|+|\partial_y S_p|\ne 0 \right\}. \]

And $S$ is estimated by solving:

\[\mathop{\text{min}}\limits_{S} \left\{ \mathop{\sum}\limits_{p}(S_p-I_p)^2 + \lambda \cdot C(S) \right\}. \]

However, it's hard to solve this equation. So the strategy is using an alternating optimization, especially, introducing auxiliary variables $h_p$ and $v_p$ , corresponding to $\partial_x S_p$ and $\partial_y S_p$ respectively, to approximate the solution of the primal equation.

Thus, the objective function of this algorithm becomes:

\[\mathop{\text{min}}\limits_{S,h,v}\left\{\mathop{\sum}\limits_{p}(S_p-I_p)^2 + \lambda C(h,v) + \beta \left((\partial_x S_p-h_p)^2 + (\partial_y S_p-v_p)^2 \right)\right\}, \]

where $C(h,v)=\#\left\{p\big| |h_p|+|v_p|\ne 0 \right\}$, and $\beta$ is an automatically adapting parameter.

The new objective function can be splitted into two subproblems. Both of them can get the solution so that the altered problem is solvable.

Subproblem 1: computing $S$

The subproblem for $S$ is to minimize:

\[\left\{\mathop{\sum}\limits_{p}(S_p-I_p)^2 + \beta \left((\partial_x S_p-h_p)^2 + (\partial_y S_p-v_p)^2 \right)\right\}, \]

and the solution is:

\[S = \mathscr{F}^{-1}\left(\frac{\mathscr{F}(I) + \beta \left(\mathscr{F}(\partial_{x})^*\mathscr{F}(h) + \mathscr{F}(\partial_y)^*\mathscr{F}(v)\right)}{\mathscr{F}(1) + \beta \left(\mathscr{F}(\partial_{x})^*\mathscr{F}(\partial_{x}) + \mathscr{F}(\partial_y)^*\mathscr{F}(\partial_y)\right)}\right).\]

Subproblem 2: computing $(h,v)$

The objective function for $(h,v)$ is:

\[\mathop{\text{min}}\limits_{h,v}\left\{\mathop{\sum}\limits_{p} (\partial_x S_p-h_p)^2 + (\partial_y S_p-v_p)^2 + \frac{\lambda}{\beta} C(h,v)\right\}. \]

It can be spatially decomposed because each element $h_p$ and $v_p$ of pixel $p$ can be estimated individually. Thus, the equation is decommposed to:

\[\mathop{\sum}\limits_{p} \mathop{\text{min}}\limits_{h_p,v_p}\left\{(h_p - \partial_x S_p)^2 + (v_p - \partial_y S_p)^2 + \frac{\lambda}{\beta} H(|h_p| + |v_p|)\right\}, \]

where

\[H(|h_p| + |v_p|) = \begin{cases} 1 \qquad & |h_p| + |v_p| \ne 0 \\ 0 \qquad & |h_p| + |v_p| = 0 \end{cases}\]

and the solution for each pixel $p$ is:

\[(h_p, v_p) = \begin{cases} (0, 0) \qquad & (\partial_x S_p)^2 + (\partial_y S_p)^2 \le \frac{\lambda}{\beta} \\ (\partial_x S_p, \partial_y S_p) \qquad & otherwise \end{cases}\]

Demonstration

In the following examples, L0 Smooth algorithm is used to smoothing both Gray image and RGB image.

using ImageSmooth

# L0 Smooth for Gray images
img_gray = testimage("cameraman")

# Using L0 Smooth algorithm
fₛ = L0Smooth() # using default arguements

# Apply the algorithm to the image
imgₛ = smooth(img_gray, fₛ)

mosaicview(img_gray, imgₛ; nrow=1)

# L0 Smooth for RGB images
img_rgb = testimage("lena_color_512")

fₛ = L0Smooth(λ=4e-2, κ=2.0, βmax=1e5) # manually setting arguements

imgₛ = smooth(img_rgb, fₛ)

mosaicview(img_rgb, imgₛ; nrow=1)