Report

B-SPLINE SNAKE: A FLEXIBLE TOOL FOR PARAMETRIC CONTOUR DETECTION P. Brigger, J. Hoeg, and M. Unser Presented by Yu-Tseh Chi OUTLINES Snake revisited B-Spline curve B-Snake B-Spline Snake Cubic B-Spline snake = Snake Implicit smoothness constraints Results and Discussion Conclusion By Yu-Tseh Chi SNAKE An energy minimizing parametric curve guided by external and internal forces. s* min{Eint ( s ) Eext ( s )} s Internal energy enforce the continuity constraint. α |s’|2 + β |s’’|2 By Yu-Tseh Chi SNAKE External energy (data term) attracts the curve to the image features such as edges and corners. By Yu-Tseh Chi DISADVANTAGE OF SNAKE Slow convergence due to large number of coefficients Difficulty in determining weights associated with smoothness constraints Eint = α |s’|2 + β |s’’|2 Description of the curve by a finite set of disconnected points. High-order derivatives on the discrete curve may not be accurate in noisy environments. By Yu-Tseh Chi OUTLINES Snake revisited B-Spline curve B-Snake B-Spline Snake Cubic B-Spline snake = Snake Implicit smoothness constraints Results and Discussion Conclusion By Yu-Tseh Chi B-SPLINE CURVE A piece-wise polynomial defined by N 1 S (u ) Ci id (u ) i 0 C1 C2 Ci : control points d i : basis function of degree d C4 C0 C3 C5 By Yu-Tseh Chi BASIS FUNCTION u ui ui d 1 u d 1 d 1 (u ) βi (u) βi 1 (u) ui d ui ui d 1 ui 1 d i 1 if ui u ui { (u ) 0 i 0 otherwise ui are called knot values Number of knot values = Number of ctrl pts + degree +1 C1 C2 C4 C0 C3 By Yu-Tseh Chi C5 BASIS FUNCTION Different ratios between knot intervals define different curve For a degree 3 B-Spline curve with 5 control points: u1=[0 1 2 3 4 5 6 7 8] and u2=[0 2 4 6 8 10 12 14 16] define the same curve. By Yu-Tseh Chi BASIS FUNCTION u ui ui d 1 u d 1 d 1 (u ) βi (u) βi 1 (u) ui d ui ui d 1 ui 1 d i 1 if ui u ui { (u ) 0 i 0 otherwise C1 C2 C4 C0 C3 C5 By Yu-Tseh Chi B-SPLINE CURVE N 1 S (u ) Ci id (u ) i 0 C0 C1 C2 C3 C4 C5 Important properties Defined by only few parameters Cd-1 continuity A degree 3 B-Spline curve is C2 continuous Duplicate knot values decrease continuity by 1 By Yu-Tseh Chi C1 C2 C4 C0 C3 C5 B-SPLINE CURVE N 1 S (u ) Ci id (u ) i 0 C0 C1 C2 C3 C4 Important properties Defined by only few parameters Cd-1 continuity A degree 3 B-Spline curve is C2 continuous Duplicate knot values decrease continuity by 1 By Yu-Tseh Chi C5 B-SPLINE CURVE N 1 S (u ) Ci id (u ) i 0 C0 C1 C2 C3 C4 Important properties Defined by only few parameters Cd-1 continuity Locality By Yu-Tseh Chi C5 CLOSED CURVE For a degree d B-Spline curve, add d duplicate control points in the end. Add knot values according. C2 C8 C1 C7 C3 C4 C5 By Yu-Tseh Chi C0 C6 OUTLINES Snake revisited B-Spline curve B-Snake B-Spline Snake Cubic B-Spline snake = Snake Implicit smoothness constraints Results and Discussion Conclusion By Yu-Tseh Chi DISADVANTAGE OF SNAKE Slow convergence due to large number of coefficients Difficulty in determining weights associated with smoothness constraints Eint = α |s’|2 + β |s’’|2 Description of the curve by a finite set of disconnected points. High-order derivatives on the discrete curve may not be accurate in noisy environments. By Yu-Tseh Chi B-SNAKE Proposed by Medioni et. al. Curve is replaced by its B-Spline approximation N 1 S (u ) Ci id (u ) i 0 Advantages of this formulation Local Control Continuity Less points to apply optimization By Yu-Tseh Chi ENERGY FUNCTION OF B-SNAKE N 1 E (u ) { (Ci ( id (u ))') (Ci ( id (u ))") F ( S (u ))} i 0 d ( i )' is the derivative of the basis function d d d 1 d 1 i i 1 = ui d ui ui d 1 ui F(S(u)) is the data term as defined in the orginal Snake. By Yu-Tseh Chi ALGORITHM Calculate the ctrl points based on some points sampled from the user-defined curve. Update the ctrl points Cik+1= Cik + η*∂E/ ∂ Cik By Yu-Tseh Chi DISADVANTAGE OF B-SNAKE Does not take advantage of the implicit smoothness constraint of B-Spline curve. Still have the regularization term explicitly N 1 E (u ) { (Ci ( id (u ))') (Ci ( id (u ))") F ( S (u ))} i 0 By Yu-Tseh Chi OUTLINES Snake revisited B-Spline curve B-Snake B-Spline Snake Cubic B-Spline snake = Snake Implicit smoothness constraints Results and Discussion Conclusion By Yu-Tseh Chi B-SPLINE SNAKE Proposed by Unser et. al. Same formulation as B-Snake Using S (u) C (u) to outline contour in an image. N 1 i 0 By Yu-Tseh Chi i d i CONTRIBUTIONS Optimal solution for Snake (a curvatureconstrained E ) is a cubic spline. Specify initial contour by node points of a Bspline curve instead of control points. Enforce smoothness constraint implicitly. Improve speed and robutsness by using a multi-resolution scheme. By Yu-Tseh Chi SNAKE = CUBIC SPLINE S * (u ) arg min V (k , s(k )) ( s" (u )) du s k Similar formulation to the one of Snake S* is the optimal solution V is the data term. S(k) some points on the curve S(u) 2nd term is the smoothness constraint. By Yu-Tseh Chi 2 SNAKE = CUBIC SPLINE S * (u ) arg min V (k , S (k )) ( S " (u )) du s 2 k Define Sint(u) is the cubic spline interpolation of the Snake S(u) and Sint(ui)=S(ui) Above equation can be rewritten as S * (u ) arg min V (k , Sint (k )) s k S " (u )du By Yu-Tseh Chi SNAKE = CUBIC SPLINE S * (u ) arg min V (k , Sint (k )) ( S " (u )) du s 2 k Using first integral equation, 2nd term can be rewritten as S " (u ) du Sint " (u ) du 2 2 " ( S " (u ) Sint (u ))2 du By Yu-Tseh Chi SNAKE = CUBIC SPLINE S * (u ) arg min V (k , Sint (k )) ( Sint " (u ))2 du s k " ( S " (u ) Sint (u ))2 du S* is the optimal solution s.t. the energy function is minimized. The energy function can be minimized if and only if the 3rd term is minimized. S * (u) S * (u) " By Yu-Tseh Chi " int SNAKE = CUBIC SPLINE S * (u) S * (u) " " int By intergrading twice, S(u) – Sint(u) = au+b Because of the interpolation condition S(ui) = Sint(ui) , a = 0 and b=0 S(u) = Sint(u) By Yu-Tseh Chi SNAKE = CUBIC SPLINE Another way to prove it S * (u ) arg min V (k , S (k )) ( S " (u )) 2 du s k Take the Euler-Lagrange of the 2nd term. ( 4) (u ) 0 S(u) is a cubic spline. S All Splines can be represented by a B-Spline. The optimal solution for Snake is a cubic BSpline By Yu-Tseh Chi CONTRIBUTIONS Optimal solution for Snake (a curvatureconstrained E ) is a cubic spline. Specify initial contour by node points of a Bspline curve instead of control points. Enforce smoothness constraint implicitly. Improve speed and robutsness by using a multi-resolution scheme. By Yu-Tseh Chi NODES POINTS Provide more intuitive user interaction. Specify a B-spline curve from user defined node points. By Yu-Tseh Chi NODE POINTS Node points are points on the B-Spline S(u) where u = ui ( are knot values of the B-Spline) To calculate ctrl points based on given node points, we use S (u ) C (u ) N 1 i 0 S (u0 ) 0 S (u ) 0 1 ... . ... . S (un ) ... N = B*C -1 C=B *N By Yu-Tseh Chi 1 0 2 1 .. . . ... 0 C0 ... 0 C1 ... Points . Node u =ui when . ... . ... Cn i 3 i Control points CONTRIBUTIONS Optimal solution for Snake (a curvatureconstrained E ) is a cubic spline. Specify initial contour by node points of a Bspline curve instead of control points. Impose smoothness constraint implicitly. Improve speed and robutsness by using a multi-resolution scheme. By Yu-Tseh Chi IMPLICIT SMOOTHNESS CONSTRAINT S * (u ) arg min V (k , S (k )) ( S " (u )) du s k 2 2nd term is the smoothness constraint. Ignore 2nd term, by introducing smoothness factor h. By Yu-Tseh Chi IMPLICIT SMOOTHNESS CONSTRAINT Original parameterization S (u ) C (u ) with u =[0 1 2 3 …. N+3] We sample points S(ui) on the curve to do the optimization. N 1 i 0 By Yu-Tseh Chi i d i IMPLICIT SMOOTHNESS CONSTRAINT New parameterization S (u ) C (u ) with u =[0 1h 2h …. (N+3)h] Sample points on S(u) where u is a integer h decides how dense we want to sample from the curve N 1 i 0 h=1 By Yu-Tseh Chi i d i h=2 h=4 h=8 IMPLICIT SMOOTHNESS CONSTRAINT S * (u ) arg min V ( k , S ( k )) s k ( S " (u )) 2 du h acts as the regularization factor in Snake. By Yu-Tseh Chi IMPLICIT SMOOTHNESS CONSTRAINT S * (u ) arg min V ( k , S ( k )) s k ( S " (u )) 2 du h acts as the regularization factor in Snake. By Yu-Tseh Chi CONTRIBUTIONS Optimal solution for Snake (a curvatureconstrained E ) is a cubic spline. Specify initial contour by node points of a Bspline curve instead of control points. Impose smoothness constraint implicitly. Improve speed and robutsness by using a multi-resolution scheme. By Yu-Tseh Chi MULTI-RESOLUTION SCHEME Used in many Research topic. Image pyramid scheme. To increase speed and prevent local minimum. By Yu-Tseh Chi ENERGY FORMULATION Energy function g(S(i)) is the external potential function . Smoothed gradient of the input image. Φ is a smoothing kernel (Guassian) By Yu-Tseh Chi OPTIMIZATION N 1 S (u ) Ci i3 (u ) i 0 By Yu-Tseh Chi Use steepest descent algorithm to obtain new control points. k 1 i C By Yu-Tseh Chi C ( ) Ci k i OUTLINES Snake revisited B-Spline curve B-Snake B-Spline Snake Cubic B-Spline snake = Snake Implicit smoothness constraints Results and Discussion Conclusion By Yu-Tseh Chi RESULTS By Yu-Tseh Chi RESULTS By Yu-Tseh Chi RESULTS By Yu-Tseh Chi RESULTS By Yu-Tseh Chi OUTLINES Snake revisited B-Spline curve B-Snake B-Spline Snake Cubic B-Spline snake = Snake Implicit smoothness constraints Results and Discussion Conclusion By Yu-Tseh Chi CONCLUSIONS Snake = cubic B-spline Improvement of optimization speed by introducing # of free parameters of Snake curve. Intuitive user-interaction. By Yu-Tseh Chi THANK YOU! QUESTIONS? Have a nice summer break! By Yu-Tseh Chi