4 M.Tang, D.Marin, I.B.Ayed, Y.Boykov
assuming that they are easier to optimize. An auxiliary function a
t
(S) at iteration t is
an upper bound for E(S) touching the original energy at the current solution S
t
a
t
(S) ≥ E(S), E(S
t
) = a
t
(S
t
).
To decrease E(S) one can minimize the auxiliary function a
t
giving the next solution
S
t+1
= arg min
S
a
t
(S).
This iterative process guarantees the original energy decrease: E(S
t+1
) ≤ a
t
(S
t+1
) ≤
a
t
(S
t
) = E(S
t
). Note that the bound does not have to be optimized globally. As long
as a
t
(S
t+1
) ≤ a
t
(S
t
), the original energy is guaranteed to decrease E(S
t+1
) ≤ E(S
t
).
2.1 Unary bounds for Normalized Cut
Below we derive two bounds for (1) and propose move-making algorithms such as ex-
pansion and swap [2] to optimize such multi-label auxiliary functions for our NC+MRF
energy. To the best of our knowledge, this is the first use of move-making algorithms in
the context of bound optimization. The existing high-order bound-optimization graph
cut techniques apply to binary segmentation [17,18]. The computation aspects of eval-
uating our bounds for large-scale problems are discussed in Sec.2.1.1.
Our first bound, called kernel bound, is an exact auxiliary function for the high-
order energy (1). It is expressed as a function of the pairwise affinities or kernels. Our
second bound, called spectral bound, can be viewed as an auxiliary function for the
K-means discretization step in standard spectral relaxation methods [1,19]. Unlike our
kernel bound, this approximate bound requires eigen vector computations.
The next lemma helps to derive our kernel bound for energy (1) in Proposition 1.
Lemma 1 (concavity) Equivalently rewrite the first (NC) term in (1) as
−
k
assoc(S
k
, S
k
)
assoc(Ω, S
k
)
≡
k
e(S
k
) for e(X) := −
X
′
AX
d
′
X
(3)
using the matrix notation in (2) with affinity matrix A := [A
pq
] and vector d := A 1
of node degrees d
p
=
q
A
pq
. Function e : R
|Ω|
→ R in (3) is concave over region
d
′
X > 0 assuming that affinity matrix A is positive semi-definite.
Proof. It follows from negative definiteness of the Hessian ∇∇e, see [20, Lemma 1].
The first-order Taylor expansion T
t
(X) := e(X
t
) + ∇e(X
t
)
′
(X − X
t
) at a current
solution X
t
is an obvious bound for the concave function e(X) in (3). Its gradient
∇e(X
t
) = d
X
t
′
AX
t
(d
′
X
t
)
2
− AX
t
2
d
′
X
t
implies bound T
t
(X) ≡ ∇e(X
t
)
′
X and Prop.1.
Proposition 1 (kernel bound) For positive semi-definite affinity matrix A and any cur-
rent solution S
t
the following is an auxiliary function for NC+MRF energy (1)
a
t
(S) =
k
∇e(S
k
t
)
′
S
k
+ γ
c∈F
E
c
(S
c
). (4)
剩余16页未读，继续阅读
weixin_42175448
- 粉丝: 0
- 资源: 1
我的内容管理
展开
最新资源
- zlib-1.2.12压缩包解析与技术要点
- 微信小程序滑动选项卡源码模版发布
- Unity虚拟人物唇同步插件Oculus Lipsync介绍
- Nginx 1.18.0版本WinSW自动安装与管理指南
- Java Swing和JDBC实现的ATM系统源码解析
- 掌握Spark Streaming与Maven集成的分布式大数据处理
- 深入学习推荐系统：教程、案例与项目实践
- Web开发者必备的取色工具软件介绍
- C语言实现李春葆数据结构实验程序
- 超市管理系统开发：asp+SQL Server 2005实战
- Redis伪集群搭建教程与实践
- 掌握网络活动细节：Wireshark v3.6.3网络嗅探工具详解
- 全面掌握美赛：建模、分析与编程实现教程
- Java图书馆系统完整项目源码及SQL文件解析
- PCtoLCD2002软件：高效图片和字符取模转换
- Java开发的体育赛事在线购票系统源码分析
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
