Normalized Cut Meets MRF
We propose a new segmentation or clustering model that combines Markov Random Field (MRF) and Normalized Cut (NC) objectives. Both NC and MRF models are widely used in machine learning and computer vision, but they were not combined before due to signific
- PDF / 4,452,230 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 107 Downloads / 261 Views
2
Computer Science, University of Western Ontario, London, Canada {mtang73,yuri}@csd.uwo.ca, [email protected] Ecole de Technologie Sup´erieure, University of Quebec, Montreal, Canada [email protected]
Abstract. We propose a new segmentation or clustering model that combines Markov Random Field (MRF) and Normalized Cut (NC) objectives. Both NC and MRF models are widely used in machine learning and computer vision, but they were not combined before due to significant differences in the corresponding optimization, e.g. spectral relaxation and combinatorial max-flow techniques. On the one hand, we show that many common applications for multi-label MRF segmentation energies can benefit from a high-order NC term, e.g. enforcing balanced clustering of arbitrary high-dimensional image features combining color, texture, location, depth, motion, etc. On the other hand, standard NC applications benefit from an inclusion of common pairwise or higherorder MRF constraints, e.g. edge alignment, bin-consistency, label cost, etc. To address NC+MRF energy, we propose two efficient multi-label combinatorial optimization techniques, spectral cut and kernel cut, using new unary bounds for different NC formulations.
1
Introduction
Let Ω be a collection of pixels/voxels or any other data points p that may also be referred to as graph nodes. A segmentation can be equivalently represented either as a labeling S := (Sp |p ∈ Ω) including integer node labels 1 ≤ Sp ≤ K or as a partitioning {S k } of set Ω into K segments S k := {p ∈ Ω|Sp = k}. Our general energy formulation combining Normalized Cut clustering and MRF regularization potentials is E(S) = −
assoc(S k , S k ) k
assoc(Ω, S k )
+ γ
Ec (Sc )
(1)
c∈F
where the first term is the standard NC energy [1] with association Apq ≡ S i AS j for 1 ≤ i, j ≤ K assoc(S i , S j ) :=
(2)
p∈S i ,q∈S j
based on affinity matrix or kernel A := [Apq ] with Apq := A(fp , fq ) defined by some similarity function A(·, ·) for node features fp . The equivalent matrix expression in (2) represents segments S k as indicator vectors such that Spk = 1 c Springer International Publishing AG 2016 B. Leibe et al. (Eds.): ECCV 2016, Part II, LNCS 9906, pp. 748–765, 2016. DOI: 10.1007/978-3-319-46475-6 46
Normalized Cut Meets MRF
749
iff Sp = k and symbol means a transpose. The second term in (1) is a general formulation of arbitrary MRF potentials [2–4]. Constant γ sets a relative weight of this term. Symbol c represent a factor or subset of nodes c ⊂ Ω and Sc := (Sp |p ∈ c) is a restriction of labeling S to c. Energy terms or potentials Ec (Sc ) for a given set of factors F represent various forms of second or higher-order constraints. For example, common pair-wise factors represent smoothness and contrast/edge alignment [2,5]. Popular higher-order factors are superpixel/bin consistency [3,6], label cost [4], and many others. Section 2.2 details several standard MRF potentials used in this paper’s example. 1.1
Motivation and Related Work
Due to significant differences in applicable
Data Loading...
