稀疏与冗余在图像处理中的关键应用与模式识别

需积分: 50 182 浏览量更新于2024-07-19 2 收藏 21.34MB PDF 举报

"稀疏和冗余在图像处理中的应用是一个关键主题，尤其是在计算机图形学和视觉处理领域。本文档深入探讨了这两个概念在图像分析中的重要作用。首先，我们回顾了早期统计学中的简约概念，包括其在减少复杂性中的基础作用，以及在波形分析中如何体现。现代的简约概念主要集中在l1范数及其变体上，这些技术被用于寻找数据的稀疏表示，即用少量参数描述大量数据的特性。在信号处理中，尤其是图像去噪、压缩和超分辨率等任务中，通过构建稀疏模型，可以从观测数据（通常包含噪声）中恢复原始图像。这种稀疏表示法允许通过重构算法从有限的测量数据重建出高分辨率或清晰的图像。此外，SAR成像和缺失图像重构也是这类应用的重要部分，它们依赖于从稀疏向量中恢复丢失的信息。另一方面，基于分类的应用则聚焦于模式识别，如盲源分离、音乐表示与分类、人脸识别和文本检测。这些场景下，目标是提取对象的关键特征并构造稀疏向量，确保类间有较强的区分性。通过计算稀疏向量与标准值的距离或者向量间的相似度，可以有效地进行模式识别和分类。在图像处理的实践中，发现自然图像的结构是一个核心步骤。预处理技术如平滑和标准化有助于提高后续分析的精度。主成分分析（PCA）作为一种常用的降维方法，通过对图像数据进行线性变换，找出最能解释数据变异的主要方向。而聚类或矢量量化（如K-means）则用于数据分组，揭示图像中的潜在结构。字典学习作为稀疏表示的基石，它涉及到学习一个最优的基（或字典），该基可以最小化数据的重构误差，同时使得数据在该基下的表示尽可能地稀疏。压缩感知和稀疏恢复理论则提供了理论支持，证明了即使在测量数据有限的情况下，也可以通过优化算法找到精确的稀疏解。稀疏性和冗余在图像处理中是至关重要的，它们不仅用于提高数据处理的效率和效果，还推动了图像理解和识别领域的进步。理解并有效利用这些概念和技术对于现代计算机视觉研究和实际应用至关重要。"

1.2. Wavelets in signal processing 13

A natural idea has inspired the recent concept of group sparsity

that will be presented in the next section; it consists in exploiting the

wavelet structure to improve thresholding estimators. Speciﬁcally, it is

possible to use neighborhood relations between wavelet basis elements

to deﬁne groups of coeﬃcients that form a partition G of {1, . . . , p}, and

use a group-thresholding operator [Hall et al., 1999, Cai, 1999] deﬁned

for every group g in G as

[g] ,

(



1 −

kβ[g]k



β[g] if kβ[g]k

≥ λ,

0 otherwise,

(1.7)

where β[g] is the vector of size |g| recording the entries of β whose

indices are in g. By using such an estimator, groups of neighbor coeﬃ-

cients are set to zero together when their joint ℓ

-norm falls below the

threshold λ. Interestingly, even though the next interpretation does not

appear in early work about group-thresholding [Hall et al., 1999, Cai,

1999], it is possible to view α

with β = D

⊤

x as the solution of the

following penalized problem

min

α∈R

kx − Dαk

+ λ

g∈G

kα[g]k

, (1.8)

where the closed-form solution (1.7) holds because D is orthogonal [see

Bach et al., 2012a]. Such a formulation will be studied in the next sec-

tion for general matrices.

Finally, other ideas for exploiting both structure and wavelet par-

simony have been proposed. One is a coding scheme called “zero-tree”

wavelet coding [Shapiro, 1993], which uses the tree structure of wavelets

to force all descendants of zero coeﬃcients to be zero as well. Equiv-

alently, a coeﬃcient can be non-zero only if its parent in the tree i s

non-zero, as illustrated in Figure 1.2. This idea has been revisited later

in a more general context by Zhao et al. [2009]. Other complex models

have been used as well for modeling interactions between coeﬃcients:

we can mention the application of hidden Markov models (HMM) to

wavelets by Crouse et al. [1998] and the Gaussian scale mixture model

of Portilla et al. [2003].

14 A Short Introduction to Parsimony

1.3 Modern parsimony: the ℓ

-norm and other variants

The era of “modern” parsimony corresponds probably to the use

of convex optimization techniques for solving feature selection or

sparse decomposition problems. Even though the ℓ

-norm was in-

troduced for that purpose in geophysics [Claerbout and Muir, 1973,

Taylor et al., 1979], it was popularized in statistics with the Lasso es-

timator of Tibshirani [1996] and independently in signal processing

with the basis pursuit formulation of Chen et al. [1999]. Given obser-

vations x in R

and a matrix of predictors D in R

n×p

, the Lasso consists

of learning a linear model x ≈ Dα by solving the following quadratic

program:

min

α∈R

kx − Dαk

s.t. kαk

≤ µ. (1.9)

As detailed in the sequel, the ℓ

-norm encourages the solution α to be

sparse and the parameter µ is used to control the trade-oﬀ between

data ﬁtting and the sparsity of α. In practice, reducing the value of µ

leads indeed to sparser solution in general, i.e., with more zeroes, even

though there is no formal relation between the sparsity of α and its ℓ

norm for general matrices D.

The basis pursuit denoising formulation of Chen et al. [1999] is rel-

atively similar but the ℓ

-norm is used as a penalty instead of a con-

straint. It can be written as

min

α∈R

kx − Dαk

+ λkαk

, (1.10)

which is essentially equivalent to (1.9) from a convex optimization per-

spective, and in fact (1.10) is also often called “Lasso” in the literature.

Given some data x, matrix D, and parameter µ > 0, we indeed know

from Lagrange multiplier theory [see, e.g., Borwein and Lewis, 2006,

Boyd and Vandenberghe, 2004] that for all solution α

⋆

of (1.9), there

exists a parameter λ ≥ 0 such that α

⋆

is also a solution of (1.10). We

note, however, that there is no direct mapping between λ and µ, and

thus the choice of formulation (1.9) or (1.10) should be made accord-

ing to how easy it is to select the parameters λ or µ. For instance, one

may prefer (1.9) when a priori information about the ℓ

-norm of the

solution is available. In Figure 1.4, we illustrate the eﬀect of changing

16 A Short Introduction to Parsimony

which is related to (1.10) in the sense that the set of solutions of (1.10)

converges to the solutions of (1.12) when λ converges to 0

, whenever

the linear system x = Dα is feasible. These four formulations (1.9-1.12)

have gained a large success beyond the statistics and signal processing

communities. More generally, the ℓ

-norm has been used as a regular-

ization function beyond the least-square context, leading to problems

of the form

min

α∈R

f(α) + λkαk

, (1.13)

where f : R

→ R is a loss function. In the rest of this section, we will

present several variants of the ℓ

-norm, but before that, we will try to

understand why such a penalty is appropriate for sparse estimation.

Why does the ℓ

-norm induce sparsity? Even though we have

claimed that there is no rigorous relation between the sparsity of α

and its ℓ

-norm in general, intuition about the sparsity-inducing eﬀect

of the ℓ

-norm may be obtained from several viewpoints.

Analytical point of view. In the previous section about wavelets,

we have seen that when D is orthogonal, the ℓ

-decomposition prob-

lem (1.10) admits an analytic closed form solution (1.5) obtained by

soft-thresholding. As a result, whenever the magnitude of the inner

product d

⊤

x is smaller than λ for an index i, the corresponding vari-

able α

⋆

[i] is equal to zero. Thus, the number of zeroes of the solution α

⋆

monotonically increases with λ.

For non-orthogonal matrices D, such a monotonic relation does not

formally hold anymore; in practice, the sparsity-inducing property of

the ℓ

-penalty remains eﬀective, as illustrated in Figure 1.4. Some in-

tuition about this fact can be gained by studying optimality conditions

for the general ℓ

-regularized problem (1.13) where f is a diﬀerentiable

function. The following lemma details these conditions.

Lemma 1.1 (Optimality conditions for ℓ

-regularized problems).

A vector α

⋆

in R

is a solution of (1.13) if and only if

∀i = 1, . . . , p

(

−∇f(α

⋆

)[i] = λ sign(α

⋆

[i]) if α

⋆

[i] 6= 0,

|∇f(α

⋆

)[i]| ≤ λ otherwise.

(1.14)

1.3. Modern parsimony: the ℓ

-norm and other variants 17

Proof. A proof using the classical concept of subdiﬀerential from con-

vex optimization can be found in [see,e.g., Bach et al., 2012a]. Here,

we provide instead an elementary proof using the simpler concept of

directional derivative for nonsmooth functions, deﬁned as, when the

limit exists,

∇g(α, κ) , lim

t→0

g(α + tκ) − g(α)

for a function g : R

→ R at a point α in R

and a direction κ

in R

. For convex functions g, directional derivatives always exist and

a classical optimality condition for α

⋆

to be a minimum of g is to

have ∇g(α

⋆

, κ) non-negative for all directions κ [Borwein and Lewis,

2006]. Intuitively, this means that one cannot ﬁnd any direction κ such

that an inﬁnitesimal move along κ from α

⋆

decreases the value of the

objective. When g is diﬀerentiable, the condition is equivalent to the

classical optimality condition ∇g(α

⋆

) = 0.

We can now apply the directional derivative condition to the func-

tion g : α 7→ f(α) + λkαk

, which is equivalent to

∀κ ∈ R

, ∇f(α

⋆

)

⊤

κ + λ

i=1

(

sign(α

⋆

[i])κ[i] if α

⋆

[i] 6= 0,

|κ[i]| otherwise

)

≥ 0.

(1.15)

It is then easy to show that (1.15) holds for all κ if and only the

inequality holds for the speciﬁc values κ = e

and κ = −e

for all i,

where e

is the vector in R

with zeroes everywhere except for the i-th

entry that is equal to one. This immediately provides an equivalence

between (1.15) and (1.14).

Lemma 1.1 is interesting from a computational point of view (see

Section 5.2), but it also tells us that when λ ≥ k∇f(0)k

∞

, the condi-

tions (1.14) are satisﬁed for α

⋆

= 0, the sparsest solution possible.

Physical point of view. In image processing or computer vision,

the word “energy” often denotes the objective function of a minimiza-

tion problem; it is indeed common in physics to have complex systems

that stabilize at a conﬁguration of minimum potential energy. The neg-

ative of the energy’s gradient represents a force, a terminology we will

剩余201页未读，继续阅读

qq_24599599

粉丝: 1

稀疏与冗余在图像处理中的关键应用与模式识别

图像稀疏表示模型及其在图像处理反问题中的应用

稀疏与冗余表示——理论及其在信号与图像处理中的应用（英文原版）

稀疏和冗余-在信号和图像处理方面从理论到实际应用

稀疏和冗余-在信号和图像处理方面从理论

稀疏冗余表示 在信号和图像处理方面从理论到实际应用（中文）

稀疏与冗余表示在图像信号处理中的应用

稀疏与冗余表示：理论与信号图像处理应用

稀疏与冗余表示：理论到信号与图像处理应用

稀疏与冗余表示：从理论到信号与图像处理应用

稀疏与冗余表示：信号与图像处理的应用理论

最新资源

稀疏冗余表示在信号和图像处理方面从理论到实际应用（中文）