Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon free Elasticity-based matching by minimising the symmetric difference of shapes

  • Author(s): Konrad Simon 1  and  Ronen Basri 2
    • View affiliations
  • Source: Volume 12, Issue 4, June 2018, p. 412 – 423
    DOI:  10.1049/iet-cvi.2017.0277 , Print ISSN 1751-9632, Online ISSN 1751-9640
© The Institution of Engineering and Technology
Received 26/06/2017, Accepted 10/12/2017, Revised 30/11/2017, Published 14/12/2017

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.

Inspec keywords: shape recognition; minimisation; elasticity; convex programming; finite element analysis; image matching; elastic deformation

Other keywords: nonlinear optimisation problem; external boundary forces; optimisation procedure; cost function; elastic deformation; elasticity-based matching; shape symmetric difference minimisation; convex problem sequence; finite element method; linearised elasticity theory

Subjects: Optimisation techniques; Optimisation techniques; Image recognition; Finite element analysis; Computer vision and image processing techniques; Finite element analysis

References

    1. 1)
      • 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. 67–88.
    2. 2)
      • 34. Huttenlocher, D., Klanderman, G., Rucklidge, W.: ‘Comparing images using the hausdorff distance’, IEEE Trans. Pattern Anal. Mach. Intell., 1993, 15, pp. 850–863.
    3. 3)
      • 51. Kimmel, R.: ‘Numerical geometry of images: theory, algorithms, and applications’ (Springer Verlag, Berlin, Germany, 2003).
    4. 4)
      • 52. Murta, A., Howard, T.: ‘The general polygon CLipping library GPC’, http://www.cs.man.ac.uk/toby/gpc/.
    5. 5)
      • 49. Sutherland, I.E., Hodgman, G.W.: ‘Reentrant polygon clipping’, ACM Commun, 1974, 17, (1), pp. 32–42.
    6. 6)
      • 37. Memoli, F.: ‘Gromov–Wasserstein distances and the metric approach to object matching’, Found. Comput. Math., 2011, 11, (4), pp. 417–487.
    7. 7)
      • 58. Blank, M., Gorelick, L., Shechtman, E., et al: ‘Actions as space-time shape’. Int. Conf. on Computer Vision, 2005, pp. 1395–1402.
    8. 8)
      • 57. Bronstein, A.M., Bronstein, M.M., Kimmel, R.: ‘Numerical geometry of non-rigid shapes’ (Springer, Heidelberg, Germany, 2008).
    9. 9)
      • 50. Greiner, G., Hormann, K.: ‘Efficient clipping of arbitrary polygons’, ACM Trans. on Graph. (TOG), 1998, 17, (2), pp. 71–83.
    10. 10)
      • 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. 143–162.
    11. 11)
      • 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. 161–168.
    12. 12)
      • 43. Myronenko, A., Song, X.: ‘Point set registration: coherent point drift’, IEEE Trans. Pattern Anal. Mach. Intell., 2010, 32, (12), pp. 2262–2275.
    13. 13)
      • 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. 999–1036.
    14. 14)
      • 30. Berkels, B., Linkmann, G., Rumpf, M.: ‘An SL(2)-invariant shape median’, J. Math. Imaging Vision, 2010, 37, (2), pp. 85–97.
    15. 15)
      • 17. Younes, L.: ‘Optimal matching between shapes via elastic deformations’, Image Vis. Comput., 1999, 17, pp. 381–389.
    16. 16)
      • 22. Kovalsky, S.Z., Aigerman, N., Basri, R., et al: ‘Controlling singular values with semidefinite programming’, ACM Trans. Graph., 2014, 33, (4), 68-1.
    17. 17)
      • 55. Sebastian, T.B., Klein, P.N., Kimia, B.B.: ‘Recognition of shapes by editing shock graphs’. Int. Conf. on Computer Vision, 2001, pp. 755–762.
    18. 18)
      • 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. 587–594.
    19. 19)
      • 61. Levi, Z., Gotsman, C.: ‘Smooth rotation enhanced as-rigid-As-possible mesh animation’. IEEE Transactions on Visualization and Computer Graphics, 2015.
    20. 20)
      • 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.
    21. 21)
      • 44. Bro-Nielsen, M.: ‘Finite elements modeling in surgery simulation’, Proc. IEEE, 1998, 86, (3), pp. 490–503.
    22. 22)
      • 46. Dhondt, G.: ‘The finite element method for three-dimensional thermomechanical Applications’ (John Wiley & Sons, Chicester, UK, 2004).
    23. 23)
      • 32. Mumford, D., Shah, J.: ‘Optimal approximations by piecewise smooth functions and associated variational problems’, Commun. Pure And Appl. Math., 1989, 42, (5), pp. 577–685.
    24. 24)
      • 5. Gelfand, N, Mitra, N.J., Guibas, L.J., et al: ‘Robust global registration’. Symp. on Geometry Processing, 2005, pp. 197–206.
    25. 25)
      • 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.
    26. 26)
      • 24. Alt, H., Fuchs, U., Rote, G., et al: ‘Matching convex shapes with respect to the symmetric difference’, Algorithmica 21, 1998, 21, (1), pp. 89–103.
    27. 27)
      • 15. Mio, W., Srivastava, A., Joshi, S.: ‘On shape of plane elastic curves’, Int. J. Comput. Vis., 2007, 73, (3), pp. 307–324.
    28. 28)
      • 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.
    29. 29)
      • 10. Bajcsy, R., Broit, C.: ‘Matching of deformed images’. Proc. Int. Conf. Pattern Recognition, 1982, pp. 351–353.
    30. 30)
      • 12. Holden, M.: ‘A review of geometric transformations for nonrigid body registration’, IEEE Trans. Med. Imaging, 2008, 27, (1), pp. 111–128.
    31. 31)
      • 62. Sorkine, O., Alexa, M.: ‘As-rigid-as-possible surface modeling’. Symp. on Geometry Processing, 2007, Vol. 4.
    32. 32)
      • 3. Sederberg, T.W., Greenwood, E.: ‘A physically based approach to 2-D shape blending’, ACM SIGGRAPH Comput. Graph., 1992, 26, (2), pp. 25–34.
    33. 33)
      • 47. Sadd, M.H.: ‘Elasticity. Theory, applications, and numerics’ (Elsevier Butterworth-Heinemann, Oxford, UK, 2005).
    34. 34)
      • 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. 1168–1172.
    35. 35)
      • 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.
    36. 36)
      • 8. Christensen, G.E., Rabbitt, R.D., Miller, M.I.: ‘Deformable templates using large deformation kinematics’, IEEE Trans. Image Process., 1996, 5, (10), pp. 1435–1447.
    37. 37)
      • 21. Brown, B.J., Rusinkiewicz, S.: ‘Global non-rigid alignment of 3-D scans’, ACM Trans. Graph., 2007, 26, (3), 21.
    38. 38)
      • 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. 239–256.
    39. 39)
      • 59. Lipman, Y.: ‘Bounded distortion mapping spaces for triangular meshes’, ACM Trans. Graph., 2012, 31, (4) 108.
    40. 40)
      • 14. Terzopoulos, D., Platt, J., Barr, A., et al: ‘Elastically deformable models’, ACM Siggraph Comput. Graphics, 1987, 21, (4), pp. 205–214.
    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. 594–603.
    42. 42)
      • 45. Ciarlet, P.G.: ‘Mathematical elasticity. Volume I: Three-Dimensional Theory’, Series ‘Studies in Mathematics and its Applications’, (North-Holland, Amsterdam, 1988).
    43. 43)
      • 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. 202–209.
    44. 44)
      • 13. Nealen, A., Müller, M., Keiser, R., et al: ‘Physically based deformable models in computer graphics’, Comput. Graph. Forum, 2006, 25, (4), pp. 809–836.
    45. 45)
      • 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. 139–157.
    46. 46)
      • 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. 197–232.
    47. 47)
      • 36. Memoli, F.: ‘Gromov–Hausdorff distances in Euclidean spaces’. IEEE Computer Society Conf. on Computer Vision and Pattern Recognition Workshops, CVPRW ‘08, 2008, pp. 1–8.
    48. 48)
      • 42. Shapiro, M.D., Blaschko, M.B.: ‘On hausdorff distance measures’ (Computer Vision Laboratory University of Massachusetts, Amherst, MA, 1003, 2004).
    49. 49)
      • 23. Dubuisson, M.-P., Jain, A.K.: ‘A modified hausdorff distance for object matching’. Int. Conf. on Pattern Recognition, 1994, Vol. 1, pp. 566–568.
    50. 50)
      • 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. 266–286.
    51. 51)
      • 4. Vatti, B.R.: ‘A generic solution to polygon clipping’, Commun. ACM, 1992, 35, (7), pp. 56–63.
    52. 52)
      • 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. B165–B189.
    53. 53)
      • 48. Braess, D.: ‘Finite elements. Theory, fast solvers, and applications in solid mechanics’ (Cambridge University Press, Cambridge, UK, 2001).
    54. 54)
      • 26. Chan, T.F., Vese, L.: ‘Active contours without edges’, IEEE Trans. Image Process., 2001, 10, (2), pp. 266–277.
    55. 55)
      • 28. Overgaard, N.C., Solem, J.E.: ‘Separating rigid motion for continuous shape evolution’. Int. Conf. on Pattern Recognition, 2006.
    56. 56)
      • 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. 260–278.
    57. 57)
      • 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. 424–429.
    58. 58)
      • 31. Rumpf, M., Wirth, B.: ‘A nonlinear elastic shape averaging approach’, SIAM J. Imaging Sci., 2009, 2, (3), pp. 800–833.
    59. 59)
      • 9. Amit, Y.: ‘A nonlinear variational problem for image matching’, SIAM J. Sci. Comput., 1994, 15, (1), pp. 207–224.
    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. 157–164.
    61. 61)
      • 18. Younes, L.: ‘Spaces and manifolds of shapes in computer vision: an overview’, Image Vis. Comput., 2012, 30, pp. 389–397.
    62. 62)
      • 40. Memoli, F.: ‘The Gromov–Wasserstein distance: a brief overview’, Axioms, 2014, 3, (3), pp. 335–341.
    63. 63)
      • 16. Younes, L.: ‘Computable elastic distances between shapes’, SIAM J. Appl. Math, 1998, 58, (2), pp. 565–586.
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
Print this page
This is a required field
Please enter a valid email address