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