Coupling From the Past- Nonconstructive

  • 格式:pdf
  • 大小:302.18 KB
  • 文档页数:11

Towards exact MPM-decision for Labelling Problems
5/11
Equivalent Transformation: “cast” measurement qv onto an incident edge, only once for each node v ∈ V equivalent Gibbs specification: given as set of |E| different matrices, ∀ e ∈ E[G]. A(e) Observation: partition functions for |E|-line and |E|-cycle computable in linear time! (apart from matrix operations) Z f , m-line Z f , m-cycle =
(k,k )∈K 2 e∈E[G]
A(e) A(e)
(k,k)∈K 2 e∈E[G]
=
• • •
e∈E[G]
A(e) the usual matrix product A the sum over all entries of matrix A A the trace of matrix A
(k,k )∈K 2 (k,k)∈K 2
Recapitulation
2/11
MPM-estimator based on node marginal: ∀ vi ∈ V : ˆ ˆ f ∗(vi) = argmax PG f (vi) = k, y
k∈K
Homogeneous Markov Chains {Xt}t≥0 {Zt}t≥1 ∼ uniform[0, 1] and {Xt}t≥0 ∼ Gibbsian[f ∈ K V ] random transition rule: tr : K V × [0, 1] → K V stochastic transition matrix: P = pij = P tr(i, Zt+1) = j | i, j ∈ K V recurrence equation Xt+1 = tr(Xt, Zt+1) as HMC ergodicity and stationarity componentwise HMC - Gibbs Sampler Goodness of an Estimator: Systematic Errors - stationary chain and correlations between samples Random Error
Stereo Model for Surface Patches
9/11
Surface Patch Model ⇔ “Colored Surface” labellings f ∈ (Z × S)V local potentials: guv ( f (u) = (Zu , Su), f (v) = (Zv , Sv ) ) = exp − exp − α/σ
2
Stereo Model for Surface Patches
8/11
Segmentation Model all possible segmentations or colorings h ∈ S V with label set S = {s1, . . . , sk } local potentials ∀ (u, v) ∈ E : with α > α > 1 guv ( h(u), h(v) ) = α α if h(u) = h(v), otherwise
S1
S2
S2
S3
S3
References
[1] Wilfrid S. Kendall and Elke Th¨nnes. Perfect Simulation in Stochastic Geometry. o Pattern Recognition, 32(9):1569–1586, September 1999. [2] James Gary Propp and David Bruce Wilson. Exact Sampling with coupled Markov Chains and Applications to statistical Mechanics. Random Structures and Algorithms, 9(1-2):223–252, 1996. [3] L. Robert and R Deriche. Dense Depth Map Reconstruction: A Minimization and Regularization Approach which Preserves Discontinuities. In Bernard Buxton, editor, Proceedings of the 4th European Conference on Computer Vision, Cambridge, UK, 1996. [4] Dimitrij Schlesinger. PhD thesis, Fakult¨t Informatik, TU Dresden, Germany, 2003. a [1, 2, 4, 3]
⇒ start only two samplers in fmin, fmax w.r.t. K V , ∀ f ∈ KV : fmin f
⇒ running time is function of length of these two trajectories until coalescence appears ⇒ function of “contraction ability” of transition rule ⇒ function of Gibbs specification
i.e. t ∈ {t∗, t∗ + 1, . . . , −1} reusing old random pairs of former rounds. 4. Check for coalescence at time 0, that is check if X0(fm) occupy the same state ∀ m. If so, this common value X0 is returned, otherwise let t∗ ← (t∗ − 1) and go to step 2. ⇒ with probability 1 the CFTP algorithm stops ie. returns a value. ⇒ this value is realisation of r.v. distributed acc. to stationary distribution of HMC.
Towards exact MPM-decision for Labelling Problems
T. Wierschin
1/11
Outline: Computing the MPM estimator • Exact Markov Chain Monte Carlo Simulation with CFTP • Exact Computation for certain Base Graphs Application: Stereo Models for Labelling Problems • Near-Baseline Stereo Rig and Labellings • Surface Patch Model Nhomakorabea11/11
Coupling From the Past - Nonconstructive
3/11
Exact Sampling through Monitoring Stationarity [2] 1. Set starting value for the time to go back, t∗ ← −1. 2. Generate new random pair M t∗+1 = (U t∗ , vt∗ ). 3. Start a chain in each labelling fm | m = 1, · · · , |K V | at time t∗ and run the chains Xt+1(fm) = tr Xt(fm), M t+1 to time 0
Coupling From the Past - Constructive
4/11
Monotone CFTP endow labelling space K V with an appropriate partial order say (K V , ) transition function tr is monotone, iff it respects this partial order on K V : ∀M : tr fi, M tr fj , M ⇔ fi : fmax fj .
⇒ obtaining all marginals in quadratic time.
Stereo Model for Surfaces
6/11
Surface Model [3] two cameras as pinhole models near-baseline-stereo - completely calibrated with projections {P1, P2} bijection via surface xj yj = Pj ◦ Pi−1 xi yi
Stereo Model for Surfaces
7/11
Surface Model and Labellings [4] equivalence between correspondence of pixel pair (pi , pj ) and computing depth Zi for each pixel pi in image i: label set Z = (pj , Zr1), (pj , Zr2), . . . , (pj , Zrd) , d some r 2 1 d neighborhood labellings t ∈ Z V local potentials (regularization ansatz): ∀ (u, v) ∈ E : σ controlling positive scalar guv t(u) − t(v) ( t(u), t(v) ) = exp − σ