4.2.1.1Patch non-local means

A square penalization term is used for the pixel-wise error. As a result the patch error function becomes a weighted squared L2-norm.We write:

In this case we set X = L2(Ωp). For g ≡ 1 the patch non-local means error function reduces to the usual squared L2-norm. The scalar product associated to this Hilbert normed space will be denoted as ⟨⋅, ⋅⟩g and is equal to or ⟨g⋅, ⋅⟩ whenwritten in terms of the usual L2-scalar product. The g-weighted L2-norm will also be denoted as ‖⋅ ‖g.

4.2.1.2Patch non-local medians

The penalization term for the pixel-wise error is taken to be the absolute value | ⋅ |. As a result the patch error function becomes a weighted L1-norm. We write:

In this case we set X = L1(Ωp). For g ≡ 1 the patch non-local means error function reduces to the standard L1-norm.

Furthermore, one can use gradient-based error functions. These error functions are able to find matching patterns even if they differ by additive brightness.

4.2.1.3Patch non-local Poisson

A square penalization term is used for the pixel-wise gradient error. As a result the patch error function becomes

In this case the natural choice for X is W1,2(Ωp). The g-weighted L2-norm of the gradient will also be denoted as ‖⋅ ‖g,∇.

4.2.1.4Patch non-local gradient medians

If we choose X = W1,1(Ωp), the corresponding patch error function is

In principle the above error functions can also be linearly combined or carried to Lp, p ≥ 1.

In the variational framework of exemplar-based inpainting the patch error function is not only used as a criterion for the similarity of patches but also determines the image synthesis. It therefore plays a crucial role which we will further investigate in the subsequent sections.

Since, for a given patch px, we want to compute the best-matching patch py,θ, where the best rotation angle θ is not known a priori, an efficient algorithm should not be based on a pixel-by-pixel comparison but rather employ an expansion in a suitable basis. In this work we restrict the further analysis to the case of error functions derived from the L2-normsince they can be calculated efficiently using the Circular Harmonics basis. For general results with error functions based on the L1-norm the interested reader is referred to [5]. Another approach for the computation of best-matching patches is the PatchMatch correspondence algorithm by [11, 12].

4.2.2.1Definition and basic properties

For a thorough introduction of the Circular Harmonics, we consider the Laplace eigenvalue problem on a disk of radius r with Dirichlet boundary conditions

From (2.4) we obtain a sequence of eigenfunctions (ψi)i∈ℕ with eigenvalues λi which, when normalized, form an orthonormal basis for L2(Br(0)).

The system of eigenfunctions to the above problem can be identified with the compactly supported Circular Harmonics functions on Br(0), which,whenwritten in polar coordinates (ρ, θ), read as

where Jm denotes the Bessel-functions of first kind and order m, (jm,n)n∈ℕ denotes the (increasing) sequence of the positive roots of Jm, see [54] for details, and cm,n the normalization constant. Furthermore, the eigenvalues associated to em,n,r are well known, and explicitly given by

A crucial observation is that the Laplace operator commutes with the rotations Rα. As a consequence the em,n,r are simultaneously eigenfunctions of both operators. In particular, for (m, n) ∈ ℤ×ℕwe have

This property (referred to as self-steerability in [6]) will be of utmost importance for the detection of the mutual rotation when comparing the image pattern on two given patches.

As we can see in Figure 4 the Circular Harmonics possess a certain structure with respect to radial and angular frequencies. With increasing m the term eimθ in (2.5) causes increasing oscillatory behavior in θ, whereas with increasing n the radial frequency increases. Also, the Fourier transform of a compactly supported Circular Harmonic function ℱem,n,r ∈ L1 has a fast decay in its radial direction (ℱem,n,r(ρ, θ) ∼ ρ−5/2) and has its predominant frequencies at radial distance jm,n/r [29, 57], see also Figure 5. We will now discuss why these properties are important once the Circular Harmonics are sampled and applied to discrete signals.

4.2.2.2Sampling of circular harmonics

For our purpose, the application to digital images, the Circular Harmonics will not be used in the continuous setting, but in the discrete one. An important and classical result in the theory of digital-to-analog signal conversion, which guarantees an errorfree passage from continuous to discrete signals, is Shannon’s sampling theorem. It gives a relation of the sampling rate necessary to obtain the full information of a signal f after discrete sampling to its band-width, that is the localization of its Fouriertransform ℱ(f). We recall that the one-dimensional Fourier-transform of a signal f is given by

If the Fourier-transform of f is such that F (f)(ω) = 0 for all |ω| ≥ B, B > 0, then the sampling theorem states that f is completely determined by giving its ordinates at a series of points spaced one from the other [51]. Functions, whose Fourier-transform fulfills the above condition, are also called bandlimited functions. The theorem easily extends to higher dimensions, simply by tensor product. As a corollary of the sampling theorem, the scalar product of bandlimited functions f, g, is preserved under sampling, that is , see [31, Theorem 3.4].

If functions are not suitably bandlimited, that is the sampling process violates the above bound established by [51], signals, which were different before the sampling, become indistinguishable (or aliases of one another) when sampled. In signal processing this ambiguity is referred to as aliasing. For a more thorough introduction to aliasing we refer to [46].

In Section 4.2.2.1 we have seen that the Circular Harmonics are not bandlimited, but their Fourier-transforms have a fast decay in radial direction. Choosing suitable norms to measure the tails of the Fourier-transforms we can estimate the aliasing error, the distortion of a signal under sampling, details in [29, Sections 2, 3], and [31, Thm. 3.4]. As a consequence for any desired precision ε > 0 and any radius r there exists a sampling rate τ > 0, that is a sampling grid τℤ2, and a frequency set Φr,ε containing frequency pairs (m, n) such that the corresponding em,n,r have an aliasing error which can be controlled by ε. Here, on purpose and for the sake of a more concise presentation, we do not wish to discuss the details of the sampling theory applied to Circular Harmonics, but limit ourselves to just stating the fundamental facts. We will denote these sampled functions with “⋅s” for “sampled” whenever it is important to stress the difference to their corresponding analog versions. Analogously denotes the sampled disk

For an adequate choice of ε > 0 (and thus of sampling rate τ > 0 small enough so that is affected by small aliasing errors) we have that

and thus forms a near-orthonormal system, which implies that thesampled functions remain linearly independent. If we choose (note: this is not possible for arbitrary ε) the system Φr,ε is a frame for (see, e.g., [30] for the definition of a frame and some of their properties). Examples for admissible frequency sets of Circular Harmonics functions can be seen in Figures 4 and 6.

4.2.2.3Self-steerability of sampled circular harmonics

Again as a consequence of [31, Theorem 3.4], the self-steerability can be carried over to the case of discrete compactly supported Circular Harmonics in an approximate way: For any rotation operator Rα and suitably bandlimited function f we have that

holds for all (m, n) ∈ Φr,ε. As announced before, this property will be used to detect mutual angles when checking for similarities in the patterns of two patches.

Since image data, in gray levels or the separated color RGB channels, can be interpreted as a function with real values, we shall only be using the positive moments.Indeed, for real signals we have

and thus no additional information is obtained from the moments m < 0. Furthermore, the moments for m = 0 are rotation-invariant and thus redundant for detection of mutual angles. To calculate mutual angles it hence suffices to include pairs of (m, n) in Φr,ε which have m > 0.

We are now ready to discuss algorithms that detect mutual angles for matching patterns.

4.2.3.1Idealized matching coefficient

An ideal matching coefficient comparing two patches should fulfill the following properties: It should detect the mutual rotation angle between the patches independently of the original mutual rotation. Hence, we do not want to restrict to any discrete set of angles. Additionally, it should provide a measure of how similar the patterns of the two patches are to each other. Of course, robustness to noise is also a requirement, since we have to deal with the aliasing errors which are due to the discretization of the Circular Harmonics, and noise can also be assumed a priori on the image. Of course, an efficient calculation is desired. It’s plenty to ask, but we shall show now that all of these wishes are indeed realizable.

A possible definition for a matching coefficient comparing two functions px ∈ L2(Br(0)), py ∈ L2(Br(0)) considering a rotation angle θ is given by

It fulfills the following properties which show the independence of the rotations of the patches at the start:

where the second property is due to (2.9). Furthermore, the matching coefficient is independent of multiplicative brightness, that is for λ ∈ ℝ, λ > 0, M(λpx , py , θ) = M (px , py , θ).Moreover, since both p x and py are non-negative functions, we have that 0 ≤ M(px , py , θ) ≤ 1 (by Cauchy–Schwarz inequality and ‖Rθpx‖2 = ‖px‖2), where M(px , py , θ) = 1 if and only if λRθpx = py for some λ > 0.

We have mentioned after (2.10) that we can exclude the moments m ≤ 0 from the detection of the best-matching angle. In fact, the contribution of moments for m < 0 are precisely the same as the ones for m > 0 when considering M (px , py , θ) and thus yield no further information. Excluding the moments with m = 0 makes the matching coefficient independent of constant additive brightness, and even of additive radially symmetric functions ϕ, that is ϕ(r, θ) = ϕ(r), since they are only spanned by the (e0,n,r)n∈ℕ.

As a consequence px and py must not be in ?Φ to obtain information about their mutual angles. The information obtained from their orthogonal projection to ?Φ yields as much information as including the corresponding moments m < 0 and the moments m = 0.

Therefore, let us assume without loss of generality that px , py ∈ ?Φ for px , py real valued signals. From (2.9) we deduce that

where denotes the (discrete) CH-moment of the corresponding Circular Harmonics function em,n,r and Re[c] the real part of a complex number c. In view of this equation

For a practical computation of the best-matching coefficient, when one wants to find the angle which maximizes it, one needs a relatively fine angle resolution and to apply a maximization search over (2.13). In the subsequent section we will investigate an even more efficient way to detect mutual angles.

4.2.3.2Matching coefficient via circular sum

Let and be defined as above. Furthermore, let

and likewise

Again, we want to find θ ∈ [0, 2π] such that the scalar product ⟨Rθpx , py⟩ℓ2 is maximal. For real valued patches, the scalar product can be rewritten as the sum ofthe scalar products Thus, for every m we would like to find the rotation angle θ = θ(m) such that the real part of the scalar product is maximized. We have the following result:

Assume that

then a rotation angle of −α applied on is the one which maximizes the real part of over θ ∈ [0, 2π], since

and for all θ ∈ [0, 2π].

In this way, the scalar products for different m > 0 each suggest a possible good rotation angle. Iteratively considering all contributions of different m’s (suitably weighted with their respective norms) we expect to compute a successive approximation and correction of the best-matching rotation angle θ. Let us formalize this idea and introduce the circular sum operation to rigorously define the procedure.

Let us first consider the operator ⊕k:

For an integer m > 0 we define the circular sum operation on υ1, . . . , υm ∈ ℂ {0} by:

For m ∈ ℕ {0} and a sequence υ1 = ρ1eiα, . . . , υm = ρmeimα, with ρk > 0 for all k = 1, . . . , m and α ∈ [0, 2π], the circular sum detects α in the following way:

This motivates the following definition [32]:

We note that due to the (almost) orthonormality in (2.8). The factor which multiplies the scalar product leads to a suitable weighting of the different proposed angles and thus to a more robust angle detection,since for small values of one might not want to trust the detected angle as much as the one of more prominent terms, cf. [32].

Motivated by (2.17) the mutual angle is then given by θ = arg(M(px , py)). The circular sum and the process of rotating back by the angle calculated so far guarantee that the calculated matching coefficient |M(px , py)| and rotation angle arg(M(px , py)) are independent of the mutual rotation as follows:

Furthermore, we have that 0 ≤ |M(px , py)| ≤ 1 (by Cauchy–Schwarz inequality) and|M(px , py)| ≈ 1 if and only if there exists λ > 0 such that for all k = 1, . . . , m. The circular sum has additionally an intrinsic auto-correction property: The error on the angle αk at some k step of the circular sum is compensated by the next term k + 1. To illustrate this, we consider the following example, where υk = eikα, k = 1, . . . , m − 2, m, and υm−1 = ei((m−1)α)+δα. Then

If 0 < δα ≪ 1 and m large enough, a small-angle approximation yields

and in any case one obtains

for some λ ∈ [0, 1]. Thus, the correction term e−iλδα always has the opposite phase sign to the error eiδα done in the step before. This property ensures a certain stability to noise and robustness of the procedure, since especially for larger k when the aliasing errors become larger the auto-correction property ensures a rigid result. The detected angles of small k’s tend to be very accurate due to the particular circular oscillation behavior of the Circular Harmonics (see (2.5)).

We will now use the quantities here introduced by means of the Circular Harmonics to measure the error between two patches in error functions which are interesting for the inpainting task.