Seite - 67 - in Proceedings - OAGM & ARW Joint Workshop 2016 on "Computer Vision and Robotics“

The primal-dual algorithm for the solution of (7) will also require knowledge of the operator norm ‖∆‖. An estimate can be found via power iteration [4], which computesλmax, the eigenvalue of ∆ with the greatest modulus if it is well separated from other eigenvalues. Note that this eigenvalue λmax equals‖∆‖due to∆beingsymmetric andpositive semidefinite. The iterationsteps of theprimal-dual algorithmaregiven, in theabstract form,as     wk+1 = (id+σ∂F ∗)−1(wk+σ∆u¯k) uk+1 = (id+τ∂IΩ) −1(uk−τ∆wk+1) u¯k+1 = 2uk+1−uk (9) for suitableparameterτ,σ∈ (0,∞) such that‖∆‖2τσ<1.SinceF∗(u) = 1 2 ‖u‖22 isdifferentiable, a simple computation shows that∂F∗(u) =u, thus z= (id+σ∂F∗)−1(u)⇐⇒ z+σz=u⇐⇒ z= u 1+σ . Further, z= (id+τ∂IΩ) −1(u)⇐⇒ z+τ∂IΩ(z)3u⇐⇒ 0∈∂ (1 2 ‖u−·‖22 +τIΩ(·) ) (z) ⇐⇒ z∈argmin v∈U ‖u−v‖22 +τIΩ(v)⇐⇒ z∈argmin v∈Ω ‖v−u‖22 (10) ⇐⇒ z=PΩ(u), wherePΩ(u) denotes the projection ofu onto Ω, i.e., onto the element in Ω with minimal distance tou. Hence, (10) can be solved by projecting onto the closest feasible point. We can compute this projection for each node individually since only point constraints are considered, i.e., whether or not ‖ui−u0i‖≤ ridoesnotdependontheothernodes’ locations. Theprojectionforeachnode issimply the projectionon theball of radiusri centeredat theoriginal locationu0i, i.e., PΩ(u)i=p(ui,u0i,ri), with p(x,y,r) = { x if‖x−y‖≤ r, r(x−y) ‖x−y‖+y else. (11) Note that Ω, and hence,u0i andri, do not change during the iteration andri is determined according to(3)and(4). Byinserting(10)and(11) into(9), the iterationscanbecomputedbysimplearithmetic operations resulting in Algorithm1. Algorithm1Primal-Dual algorithm for minimisinggraph-Laplacianwithadaptiveconstraints Input: Original point-coordinates u˜0 of mesh, edge informationE,maskingof surfacepointsS. 1: u0← extract surf coo(u˜0), r←get radii(u˜0,E,S),Ω←get Ω(r,u0) .constraints 2: ∆←get ∆(E,S), ‖∆‖←powiter(∆) . inititialisationofLaplacian 3: u←u0, u¯←u0,w←0∈R3×N, τ←‖∆‖−1, σ←‖∆‖−1 4: repeat 5: w← (w+σ∆u¯) (1+σ) . updateof thedualvariable 6: u¯←PΩ(u−τ∆w) .updateof theprimalvariable 7: u←2u¯−u .updateof theextragradient 8: (u,u¯)← (u¯,u) . interchangeofuand u¯ 9: untilmaximalnumber of iterations is reached 10: returnu Output:u+ =u surfacepoint-coordinatesof smoothedmesh. 5 67