function. Denoising has numerous applications in communications, control, machine learning, and many other fields of engineering and science. A common way to solve the problem utilizes the total variation (TV) regularization. Many efficient numerical algorithms have been developed for solving the TV regularization problem. Condat described a fast direct algorithm to compute the processed 1D signal. In this paper, we propose a variant of the Condat's algorithm based on the direct 1D TV regularization problem. The usage of the Condat's method with the taut string approach leads to a clear geometric description of the extremal One of the most known techniques for denosing of noisy signals and images was proposed by Rudin, Osher, and Fatemi [1].
22 is called a fidelity term and Consider the following variational problem: ( ) = ∥ − 0 ∥22+
( ), 0 = + .
∗ = arg min ∈ ( ) ( ). ∇ ( ) = { 1, > 0 −1, < 0 [−1; 1], = 0 2.1. Computation of the subgradient
Consider subgradient ∇ ( ): ∇ ( ) = ∑ =1 ∇ ( − 0)
+ λ ∑ =−11 ∇| +1 − |.
2 ∑ =1 ∇ ( − 0) 2 = ( 1 − 10, 2 − 02, … , 1 −1 − 0 −1, − 0 ).
In a similar manner with Eq. (6) the subgradients ∇| +1 − |, = 1, … , − 1, can be written as (1) (7) (8) Image Processing, Geoinformation Technology and Information Security / A. Makovetskii, S. Voronin, V. Kober
(−1,1,0,0,0, … ,0,0), 2 > 1 ∇| 2 − 1| = { (1, −1,0,0,0, … ,0,0), 2 < 1 ,
{( 1, − 1, 0,0,0, … ,0,0)| 1 ∈ [−1; 1]}, 2 = 1 ∇| 3 − 2| = { (0, −1,1,0,0, … ,0,0), 3 > 2 (0,1, −1,0,0, … ,0,0), 3 < 2 , {(0, 2, − 2, 0,0, … ,0,0)| 2 ∈ [−1; 1]}, 3 = 2 ∇| −1 − −2| = { ∇| − −1| = {
… (0,0,0,0,0, … , −1,1,0), −1 > −2 (0,0,0,0,0, … ,1, −1,0), −1 < −2 , {(0,0,0,0,0, … , −2, − −2, 0)| −2 ∈ [−1; 1]}, −1 = −2 (0,0,0,0,0, … 0, −1,1), > −1 (0,0,0,0,0, … 0,1, −1), < −1 , {(0,0,0,0,0, … ,0, −1, − −1)| −1 ∈ [−1; 1]}, = −1 ∑ =−11 ∇| +1 − | = {( 1, 2 − 1, 3 − 2, 4 − 3,…, −1 − −2,− −1 ) | = −1, +1 > , = 1, +1 < , ∈ [−1; 1], +1 = , = 1, …, − 1}.
From expressions (8) and (13) we get the following parameterization of the subradient: {
( ∇ ( ))1 = ( 1 − 10) + λ 1 ( ∇ ( ))2 = ( 2 − 02) + λ 2 − λ 1 ( ∇ ( ))3 = ( 3 −… 03) + λ 3 − λ 2 . ( ∇ ( )) −1 = ( −1 − 0−1) + λ −1 − λ −2
( ∇ ( )) = ( − 0) + λ −1 Consider the sequence of the cumulative sums: Consider such variables 1, … , and 01, … , 0 , that
∗1 = 10 − λ 1 ∗2 + ∗1 = 02 + 10 − 2 ∗3 + ∗2 + ∗1 = …03 + 02 + 10 − 3 .
∗ −1 + ⋯ + ∗1 = 0−1 + ⋯ + 10 − −1 { ∗ + ⋯ + ∗1 = 0 + ⋯ + 10
1 = ∗1, 01 = 10 2 = ∗2 + ∗1, 02 = 02 + 10
… −1 = ∗ −1 + ⋯ + ∗1, 0 −1 = 0−1 + ⋯ + 10 { = ∗ + ⋯ + ∗1, 0 = 0 + ⋯ + 10 . (9) (10) (11) (12) (13) (14) (15) (16) (17) (18)
Image Processing, Geoinformation Technology and Information Security / A. Makovetskii, S. Voronin, V. Kober So the solution to the problem in Eq. (3) is reduced to the solution of the problem: 1 = 01 − λ 1 2 = 02 − 2 3 = 03 − 3 ,
… −1 = 0 −1 − −1 { = 0 with given discrete function 0 and unknown discrete functions and satisfying to the conditions in Eq. (15).
Consider additional variables 0 = 00 = 0. Note that then for any = 1, … , − 1 the condition +1 > is equivalent to the condition +1 − 2 + −1 > 0, the condition +1 < is equivalent to the condition +1 − 2 + −1 < 0, the condition +1 = is equivalent to the condition +1 − 2 + −1 = 0.
Then the set of equations in Eq. (19) can be rewritten taking into account additional variables: 0 = 00 = 0 1 = 01 − λ 1 2 = 02 − 2 3 = 03 − 3 ,
… −1 = 0 −1 − −1 { = 0 where 2.2. Construction the ,,tube’’
The values 00, 01, … , 0 of the discrete function 0 defines a piecewise linear curve, which is an axial line of the tube. The values 00, 01 + λ, … , 0 −1 + λ, 0 form the upper piecewise linear border of the tube, the values 00, 01 − λ, … , 0 −1 − λ, 0 form the bottom piecewise linear border of the tube. Figure 1 shows an example of a tube.
0
0 U0
U02 2 2.3. Description of the extremal function
Since δi, i = 1, … , n − 1, take values in the segment [−1; 1], a piecewise linear curve defined by the values U1, … , Un of a discrete function U (i.e. solution to the problem in Eq. (20)) entirely belongs to the tube.
If the second discrete derivative equals zero, +1 − 2 + −1 = 0 then the piecewise linear curve defined by the values U1, … , Un of a discrete function U in the neighborhood of the point is a straight line.
If the second discrete derivative is positive, +1 − 2 + −1 > 0 then from Eq. (21) we see that = −1 and Eq. (20) shows us that = 0 + λ, i.e. belongs to the upper border of the tube.
If the second discrete derivative is negative, +1 − 2 + −1 < 0 then from Eq. (21) we see that = 1 and Eq. (20) shows us that = 0 − λ, i.e. belongs to the lower border of the tube.
It means that a piecewise linear curve defined by the values U0, … , Un of a discrete function U exactly coincides with so called ,,taut string” connecting the endpoints of the tube. Image Processing, Geoinformation Technology and Information Security / A. Makovetskii, S. Voronin, V. Kober
U02
Taut string in the tube.
In this paper, we propose a variant of the Condat’s method based on the direct 1D TV regularization problem. The usage of the Condat’smethod with the taut string method leads to a clear geometric description of the extremal function.
The work was supported by Russian Science Foundation grant №15-19-10010.
0
0
U0
1