4.6.2.1Total Variational Model

The total variational model is a basic and typical image repair model. The total variational algorithm is a non-isotropic diffusion algorithm that can be used to denoise while preserving edge continuity and sharpness.

Defining the cost function of diffusion as follows:

$R\left[f\right]={\displaystyle \underset{F}{\iint }|\nabla f\left(x,y\right)|}\text{d}x\text{d}y\left(4.109\right)$

where ∇f is the gradient of f. Consider the case of Gaussian noise, in order to remove noise, eq. (4.109) is also subject to the following constraints

$\frac{1}{\Vert F-D\Vert }{\displaystyle \underset{F-D}{\iint }|f-g{|}^2\text{d}x\text{d}y={\sigma }^2}\left(4.110\right)$

where ||F –D|| is the area of the region F –D, and σ is the noise mean square error. The objective of eq. (4.109) is to repair the region and to keep its boundary as smooth as possible, while the function of eq. (4.110) is to make the repairing process robust to noise.

With the help of Lagrangian factor λ, eq. (4.109) and eq. (4.110) can be combined to convert the constrained problem into the unconstrained problem

$E\left[f\right]={\displaystyle \underset{F}{\iint }|\nabla f\left(x,y\right)|\text{d}x\text{d}y}+\frac{\lambda }{2}{\displaystyle \underset{F-D}{\iint }|f-g{|}^2}\text{d}x\text{d}y\left(4.111\right)$

If the extended Lagrangian factor λD is introduced,

${\lambda }_D\left(r\right)=\{\begin{array}{cc}0& r\in D\\ \lambda & r\in \left(F-D\right)\end{array}\left(4.112\right)$

The functional (4.111) becomes

$J\left[f\right]={\displaystyle \underset{F}{\iint }|\nabla f\left(x,y\right)|\text{d}x\text{d}y}+\frac{{\lambda }_D}{2}{\displaystyle \underset{F}{\iint }|f-g{|}^2}\text{d}x\text{d}y\left(4.113\right)$

According to the variational principle, the corresponding energy gradient descent equation is obtained

$\frac{\partial f}{\partial t}=\nabla \cdot \left[\frac{\nabla f}{|\nabla f|}\right]+{\lambda }_D\left(f-g\right)\left(4.114\right)$

In eq. (4.114), ∇ • represents the divergence.

Equation (4.114) is a nonlinear reaction-diffusion equation with a diffusion coefficient of 1/|∇f|. Within the region D to be repaired, λD is zero, so eq. (4.114) degenerates into a pure diffusion equation; while around the region D to be repaired, the second term of eq. (4.114) makes the solution of the equation tending to the original image. The original image can be finally obtained by solving the partial differential equation eq. (4.114).

Example 4.6 Image inpainting

A set of images in Figure 4.14 gives an example of image inpainting for removing overlay text. The first three images, from left to right, are the original image, superimposed text image (to be repaired image), and the results of inpainting. The rightmost image is the difference image (equalized by histogram equalization for display) between the original image and the inpainting result image, where the PSNR between the two images is about 20 dB.

4.6.2.2Hybrid Models

In the total variational model described above, diffusion is only performed in the orthogonal direction of the gradient (i. e., the edge direction), not in the gradient direction. This feature of the total variational model preserves the edge when the diffusion is near the contour of the region; however, in the smooth position within the region, the edge direction will be more random, and the total variation model may produce false contours due to noise influence.

Consider that the gradient term in the cost function is substituted by the gradient square term in the total variational model

$R\left[f\right]={\displaystyle \underset{F}{\iint }|\nabla f\left(x,y\right){|}^2\text{d}x\text{d}y}\left(4.115\right)$

and in addition, eq. (4.110) is also used for transforming the problem into an unconstrained problem. Then, by using the extended Lagrangian factor of eq. (4.112), a functional can be obtained

$J\left[f\right]={\displaystyle \underset{F}{\iint }|\nabla f\left(x,y\right){|}^2\text{d}x\text{d}y}+\frac{{\lambda }_D}{2}{\displaystyle \underset{F}{\iint }|f-g{|}^2\text{d}x\text{d}y}\left(4.116\right)$

This results in a harmonic model. Harmonic model is an isotropic diffusion, in which the edge direction and gradient direction are not be distinguished, so it can reduce the impact of noise generated by false contours, but it may lead to a certain fuzziness for the edge.

A hybrid model of weighted sums of two models takes the gradient term in the cost function as

$R_h\left[f\right]={\displaystyle \underset{F}{\iint }h|\nabla f\left(x,y\right)|+\frac{\left(1-h\right)}{2}}|\nabla f\left(x,y\right){|}^2\text{d}x\text{d}y\left(4.117\right)$

where, h $\in$ [0, 1] is the weighting parameter. The functional of the hybrid model is

$J_h\left[f\right]={\displaystyle \underset{F}{\iint }h|\nabla f\left(x,y\right)|+\frac{\left(1-h\right)}{2}}|\nabla f\left(x,y\right){|}^2\text{d}x\text{d}y+\frac{{\lambda }_D}{2}{\displaystyle \underset{F}{\iint }|f-g{|}^2\text{d}x\text{d}y}\left(4.118\right)$

Comparing eq. (4.109) with eq. (4.118) shows that when h = 1, eq. (4.118) is the total variational model.

Another hybrid model combining the two models is the p-harmonic model, where the gradient term in the cost function is

$R_p\left[f\right]={\displaystyle \underset{F}{\iint }|\nabla f\left(x,y\right){|}^p}\text{d}x\text{d}y\left(4.119\right)$

where, p [1, 2] is the control parameter. The functional of the p-harmonic model is

$J_p\left[f\right]={\displaystyle \underset{F}{\iint }|\nabla f{\left(x,y\right)}^p|\text{d}x\text{d}y}+\frac{{\lambda }_D}{2}{\displaystyle \underset{F}{\iint }|f-g{|}^2}\text{d}x\text{d}y\left(4.120\right)$

Comparing eq. (4.113) with eq. (4.120) shows that when p = 1, eq. (4.120) is the total variational model. Comparing eq. (4.116) with eq. (4.120) shows that when p = 2, eq. (4.120) is the p-harmonic model. Thus, selecting 1 < p < 2 could achieve a better balance between the two models.

4.6.3.1Calculating the Priority of the Image Block

For larger target regions, the process of filling the image block is conducted from the outside to inside. A priority value is calculated for each image block on the filling front, and the filling order for the image blocks is then determined based on the priority value. Considering the need to keep the structure information, this value is relatively large for image blocks that are located on consecutive edges and surrounded by high confidence pixels. In other words, a region with a stronger continuous edge (human is more sensitive to edge information) has the priority to fill, and a region whose more information are known (which is more likely to be more correct) has also the priority to fill.

The priority value of the image block P(p) centered on the boundary point p can be calculated as follows:

$P\left(p\right)=\mathrm{C}\left(p\right)\cdot D\left(p\right)\left(4.121\right)$

In eq. (4.121), the first term C(p) is also called the confidence term, which indicates the proportion of the perfect pixels in the current image block; the second term, D(p) is also called the data item, which is the inner product of the iso-illuminance line at point p(line of equal gray value) and the unit normal vectors. The more numbers the perfect pixels in the current image block, the bigger the first term C(p). The more consistent the normal direction of the current image block with the direction of the iso-illuminance line, the bigger the value of the second term D(p), which makes the algorithm to have higher priority to fill the image blocks along the direction of the iso-illuminance line, so that the repaired image can keep the structure information of the target region well. Initially, C(p) = 0 and D(p) = 1.

4.6.3.2Propagating Texture and Structure Information

When the priority values are calculated for all image blocks on all the fronts, the image block with the highest priority can be determined and then it can be filled with the image block data selected from the source region. In selecting the image blocks from the source region, the sum of squared differences of the filled pixels in the two image blocks should be minimized. In this way, the result obtained from such a filling could propagate both the texture and the structure information from the source region to the target region.

4.6.3.3Updating the Confidence Value

When an image block is filled with new pixel values, the already existing confidence value is updated with the confidence value of the image block where the new pixel is located. This simple update rule helps to measure the relative confidence between image blocks on the frontline.

A schematic for describing the above steps is given in Figure 4.15. Figure 4.15(a) gives an original image, where T represents the target region, both S(S1 and S2) represent source regions, and both B(B1 and B2) represent the boundaries between the target region and two source regions, respectively. Figure 4.15(b) shows the image block Rp to be filled, which is currently centered on p on B. Figure 4.15(c) shows two candidate image blocks found from the source regions, which can be used for filling. One of the two blocks, Ru, is at the junction of two regions that can be used for filling (similar with the block to be filled), while the other, Rv, is in the first region that can be used for filling (has a larger gap with the block to be filled). Figure 4.15(d) gives the result of the partial filling by using the nearest candidate block (here Ru, but some combinations of multiple candidate image blocks are also possible) to Rp. The above-described filling process can be performed sequentially for all the image blocks in T, and the target region can be finally filled with the contents from source region.

In the filling process, the image blocks can be sequentially selected following the order of peeling onion skin, that is, from outside to inside, ring-by-circle order. If the boundary point of the target region is the center of the image block, the pixels of the image region in the source region are known, and the pixels in the target region are unknown and need to be filled. For this reason, it is also considered to assign weights to the image blocks to be repaired. The more numbers of known pixels are included, the greater the corresponding weights are, and the larger the number of known pixels, the higher the repair order.

Example 4.7 Image completion

A set of images in Figure 4.16 gives an example of removing the (unwanted) object from the image. From left to right are given the original image, the image marking the scope of the object to be removed (image needing to repair) and the image of repair results. Here the object scale is relatively large than text strokes, but the visual effect of repair is relatively satisfactory.