http://iet.metastore.ingenta.com
1887

Elasticity-based matching by minimising the symmetric difference of shapes

Elasticity-based matching by minimising the symmetric difference of shapes

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Computer Vision — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

The authors consider the problem of matching two shapes assuming these shapes are related by an elastic deformation. Using linearised elasticity theory and the finite-element method, they seek an elastic deformation that is caused by simple external boundary forces and accounts for the difference between the two shapes. The main contribution is in proposing a cost function and an optimisation procedure to minimise the symmetric difference between the deformed and the target shapes as an alternative to point matches that guide the matching in other techniques. The authors show how to approximate the non-linear optimisation problem by a sequence of convex problems. They demonstrate the utility of the proposed method in experiments and compare it to an iterative closest point like matching algorithm.

References

    1. 1)
      • 1. Simon, K., Sheorey, S., Jacobs, D., et al: ‘A linear elastic force optimization model for shape matching’, J. Math. Imaging Vis., 2014, 51, (2), pp. 260278.
    2. 2)
      • 2. Simon, K., Sheorey, S., Jacobs, D., et al: ‘A hyperelastic two-scale optimization model for shape matching’, SIAM J. Sci. Comput., 2016, 39, (1), pp. B165B189.
    3. 3)
      • 3. Sederberg, T.W., Greenwood, E.: ‘A physically based approach to 2-D shape blending’, ACM SIGGRAPH Comput. Graph., 1992, 26, (2), pp. 2534.
    4. 4)
      • 4. Vatti, B.R.: ‘A generic solution to polygon clipping’, Commun. ACM, 1992, 35, (7), pp. 5663.
    5. 5)
      • 5. Gelfand, N, Mitra, N.J., Guibas, L.J., et al: ‘Robust global registration’. Symp. on Geometry Processing, 2005, pp. 197206.
    6. 6)
      • 6. Rusinkiewicz, S., Levoy, M.: ‘Efficient variants of the ICP algorithm’. Proc. of the 3rd Int. Conf. on 3-D Digital Imaging and Modeling, 2001.
    7. 7)
      • 7. Beg, M.F., Miller, M.I., Trouvé, A., et al: ‘Computing large deformation metric mappings via geodesic flows of diffeomorphisms’, Int. J. Comput. Vis., 2005, 61, (2), pp. 139157.
    8. 8)
      • 8. Christensen, G.E., Rabbitt, R.D., Miller, M.I.: ‘Deformable templates using large deformation kinematics’, IEEE Trans. Image Process., 1996, 5, (10), pp. 14351447.
    9. 9)
      • 9. Amit, Y.: ‘A nonlinear variational problem for image matching’, SIAM J. Sci. Comput., 1994, 15, (1), pp. 207224.
    10. 10)
      • 10. Bajcsy, R., Broit, C.: ‘Matching of deformed images’. Proc. Int. Conf. Pattern Recognition, 1982, pp. 351353.
    11. 11)
      • 11. Ferrant, M., Warfield, S.K., Guttmann, C.R.G., et al: ‘3D image matching using a finite element based elastic deformation model’. Proc. of MICCAI 1999, LNCS 1679, 1999, pp. 202209.
    12. 12)
      • 12. Holden, M.: ‘A review of geometric transformations for nonrigid body registration’, IEEE Trans. Med. Imaging, 2008, 27, (1), pp. 111128.
    13. 13)
      • 13. Nealen, A., Müller, M., Keiser, R., et al: ‘Physically based deformable models in computer graphics’, Comput. Graph. Forum, 2006, 25, (4), pp. 809836.
    14. 14)
      • 14. Terzopoulos, D., Platt, J., Barr, A., et al: ‘Elastically deformable models’, ACM Siggraph Comput. Graphics, 1987, 21, (4), pp. 205214.
    15. 15)
      • 15. Mio, W., Srivastava, A., Joshi, S.: ‘On shape of plane elastic curves’, Int. J. Comput. Vis., 2007, 73, (3), pp. 307324.
    16. 16)
      • 16. Younes, L.: ‘Computable elastic distances between shapes’, SIAM J. Appl. Math, 1998, 58, (2), pp. 565586.
    17. 17)
      • 17. Younes, L.: ‘Optimal matching between shapes via elastic deformations’, Image Vis. Comput., 1999, 17, pp. 381389.
    18. 18)
      • 18. Younes, L.: ‘Spaces and manifolds of shapes in computer vision: an overview’, Image Vis. Comput., 2012, 30, pp. 389397.
    19. 19)
      • 19. Besl, P.J., McKay, N.D.: ‘A method for registration of 3-D shapes’, IEEE Trans. Pattern Anal. Mach. Intell., 1992, 14, (2), pp. 239256.
    20. 20)
      • 20. Allen, B., Curless, B., Popović, Z.: ‘The space of human body shapes: reconstruction and parameterization from range scans’, ACM Trans. Graph., 2003, 22, (3), pp. 587594.
    21. 21)
      • 21. Brown, B.J., Rusinkiewicz, S.: ‘Global non-rigid alignment of 3-D scans’, ACM Trans. Graph., 2007, 26, (3), 21.
    22. 22)
      • 22. Kovalsky, S.Z., Aigerman, N., Basri, R., et al: ‘Controlling singular values with semidefinite programming’, ACM Trans. Graph., 2014, 33, (4), 68-1.
    23. 23)
      • 23. Dubuisson, M.-P., Jain, A.K.: ‘A modified hausdorff distance for object matching’. Int. Conf. on Pattern Recognition, 1994, Vol. 1, pp. 566568.
    24. 24)
      • 24. Alt, H., Fuchs, U., Rote, G., et al: ‘Matching convex shapes with respect to the symmetric difference’, Algorithmica 21, 1998, 21, (1), pp. 89103.
    25. 25)
      • 25. Sethian, J.A.: ‘Level Set methods and fast marching methods: evolving interfaces in computational geometry, fluid mechanics, computer vision, and materials science’ (Cambridge University Press, Cambridge, UK, 1999), Vol. 3.
    26. 26)
      • 26. Chan, T.F., Vese, L.: ‘Active contours without edges’, IEEE Trans. Image Process., 2001, 10, (2), pp. 266277.
    27. 27)
      • 27. Chan, T.F., Vese, L.: ‘A level set algorithm for minimizing the Mumford–Shah functional in image processing’. IEEE Workshop on Variational and Level Set Methods in Computer Vision, 2001, pp. 161168.
    28. 28)
      • 28. Overgaard, N.C., Solem, J.E.: ‘Separating rigid motion for continuous shape evolution’. Int. Conf. on Pattern Recognition, 2006.
    29. 29)
      • 29. Ambrosio, L., Tortorelli, V.M.: ‘Approximation of functional depending on jumps by elliptic functional via Γat-convergence’, Commun. on Pure and Appl. Math., 1990, 43, (8), pp. 9991036.
    30. 30)
      • 30. Berkels, B., Linkmann, G., Rumpf, M.: ‘An SL(2)-invariant shape median’, J. Math. Imaging Vision, 2010, 37, (2), pp. 8597.
    31. 31)
      • 31. Rumpf, M., Wirth, B.: ‘A nonlinear elastic shape averaging approach’, SIAM J. Imaging Sci., 2009, 2, (3), pp. 800833.
    32. 32)
      • 32. Mumford, D., Shah, J.: ‘Optimal approximations by piecewise smooth functions and associated variational problems’, Commun. Pure And Appl. Math., 1989, 42, (5), pp. 577685.
    33. 33)
      • 33. Bronstein, A.M., Bronstein, M.M., Mahmoudi, M., et al: ‘A Gromov–Hausdorff framework with diffusion geometry for topologically-robust non-rigid shape matching’, Int. J. Comput. Vis., 2010, 89, (2–3), pp. 266286.
    34. 34)
      • 34. Huttenlocher, D., Klanderman, G., Rucklidge, W.: ‘Comparing images using the hausdorff distance’, IEEE Trans. Pattern Anal. Mach. Intell., 1993, 15, pp. 850863.
    35. 35)
      • 35. Memoli, F.: ‘On the use of Gromov–Hausdorff distances for shape comparison’, Eurographics Symposium on Point-Based Graphics (The Eurographics Association, 2007) doi: 10.2312/SPBG/SPBG07/081-090.
    36. 36)
      • 36. Memoli, F.: ‘Gromov–Hausdorff distances in Euclidean spaces’. IEEE Computer Society Conf. on Computer Vision and Pattern Recognition Workshops, CVPRW ‘08, 2008, pp. 18.
    37. 37)
      • 37. Memoli, F.: ‘Gromov–Wasserstein distances and the metric approach to object matching’, Found. Comput. Math., 2011, 11, (4), pp. 417487.
    38. 38)
      • 38. Bronstein, A.M., Bronstein, M.M., Bruckstein, A.M., et al: ‘Analysis of two-dimensional non-rigid shapes’, Int. J. Comput. Vis., 2008, 78, (1), pp. 6788.
    39. 39)
      • 39. Bronstein, A.M., Bronstein, M.M., Kimmel, R.: ‘Generalized multidimensional scaling: a framework for isometry-invariant partial surface matching’, Proc. Natl. Acad. Sci., 2006, 103, (5), pp. 11681172.
    40. 40)
      • 40. Memoli, F.: ‘The Gromov–Wasserstein distance: a brief overview’, Axioms, 2014, 3, (3), pp. 335341.
    41. 41)
      • 41. Fedorov, A., Billet, E., Prastawa, M., et al: ‘Evaluation of brain MRI alignment with the robust hausdorff distance measures’. Int. Symp. on Visual Computing, 2008, pp. 594603.
    42. 42)
      • 42. Shapiro, M.D., Blaschko, M.B.: ‘On hausdorff distance measures’ (Computer Vision Laboratory University of Massachusetts, Amherst, MA, 1003, 2004).
    43. 43)
      • 43. Myronenko, A., Song, X.: ‘Point set registration: coherent point drift’, IEEE Trans. Pattern Anal. Mach. Intell., 2010, 32, (12), pp. 22622275.
    44. 44)
      • 44. Bro-Nielsen, M.: ‘Finite elements modeling in surgery simulation’, Proc. IEEE, 1998, 86, (3), pp. 490503.
    45. 45)
      • 45. Ciarlet, P.G.: ‘Mathematical elasticity. Volume I: Three-Dimensional Theory’, Series ‘Studies in Mathematics and its Applications’, (North-Holland, Amsterdam, 1988).
    46. 46)
      • 46. Dhondt, G.: ‘The finite element method for three-dimensional thermomechanical Applications’ (John Wiley & Sons, Chicester, UK, 2004).
    47. 47)
      • 47. Sadd, M.H.: ‘Elasticity. Theory, applications, and numerics’ (Elsevier Butterworth-Heinemann, Oxford, UK, 2005).
    48. 48)
      • 48. Braess, D.: ‘Finite elements. Theory, fast solvers, and applications in solid mechanics’ (Cambridge University Press, Cambridge, UK, 2001).
    49. 49)
      • 49. Sutherland, I.E., Hodgman, G.W.: ‘Reentrant polygon clipping’, ACM Commun, 1974, 17, (1), pp. 3242.
    50. 50)
      • 50. Greiner, G., Hormann, K.: ‘Efficient clipping of arbitrary polygons’, ACM Trans. on Graph. (TOG), 1998, 17, (2), pp. 7183.
    51. 51)
      • 51. Kimmel, R.: ‘Numerical geometry of images: theory, algorithms, and applications’ (Springer Verlag, Berlin, Germany, 2003).
    52. 52)
      • 52. Murta, A., Howard, T.: ‘The general polygon CLipping library GPC’, http://www.cs.man.ac.uk/toby/gpc/.
    53. 53)
      • 53. Andersen, E.D., Andersen, K.D.: ‘The mosek interior point optimizer for linear programming: an implementation of the homogeneous algorithm’ (Kluwer Academic Publishers, Dordrecht, Netherlands, 1999), pp. 197232.
    54. 54)
      • 54. Löfberg, J.:YALMIP: A toolbox for modeling and optimization in MATLAB’. Proc. of the CACSD Conf., 2004, http://users.isy.liu.se/johanl/yalmip.
    55. 55)
      • 55. Sebastian, T.B., Klein, P.N., Kimia, B.B.: ‘Recognition of shapes by editing shock graphs’. Int. Conf. on Computer Vision, 2001, pp. 755762.
    56. 56)
      • 56. Latecki, L.J., Lakämper, R., Eckhardt, U.: ‘Shape descriptors for non-rigid shapes with a single closed contour’. IEEE Conf. on Computer Vision and Pattern Recognition (CVPR), 2000, vol. 1, pp. 424429.
    57. 57)
      • 57. Bronstein, A.M., Bronstein, M.M., Kimmel, R.: ‘Numerical geometry of non-rigid shapes’ (Springer, Heidelberg, Germany, 2008).
    58. 58)
      • 58. Blank, M., Gorelick, L., Shechtman, E., et al: ‘Actions as space-time shape’. Int. Conf. on Computer Vision, 2005, pp. 13951402.
    59. 59)
      • 59. Lipman, Y.: ‘Bounded distortion mapping spaces for triangular meshes’, ACM Trans. Graph., 2012, 31, (4) 108.
    60. 60)
      • 60. Alexa, M., Cohen-Or, D., Levin, D.: ‘As-rigid-as-possible shape interpolation’, Proc. of the 27th Annual Conf. on Computer Graphics and Interactive Techniques, 2000, pp. 157164.
    61. 61)
      • 61. Levi, Z., Gotsman, C.: ‘Smooth rotation enhanced as-rigid-As-possible mesh animation’. IEEE Transactions on Visualization and Computer Graphics, 2015.
    62. 62)
      • 62. Sorkine, O., Alexa, M.: ‘As-rigid-as-possible surface modeling’. Symp. on Geometry Processing, 2007, Vol. 4.
    63. 63)
      • 63. Peckar, W., Schnörr, C., Rohr, K., et al: ‘Parameter-Free elastic deformation approach for 2D and 3D registration using prescribed displacements’, J. Math. Imaging Vis., 1999, 10, (2), pp. 143162.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cvi.2017.0277
Loading

Related content

content/journals/10.1049/iet-cvi.2017.0277
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address