[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Full Multiresolution Active Shape Models

  • Published:
Journal of Mathematical Imaging and Vision Aims and scope Submit manuscript

Abstract

The incorporation of a multiresolution image approach is one of the most popular variants of Active Shape Models (ASMs), providing a more robust algorithm and minimizing its initialization dependency. Using the wavelet transform, the present paper extends the multiresolution analysis to the shape space, developing a novel multiresolution shape framework, capable of being incorporated into most of ASM variants. The tests performed with two different types of images, face images (AR database) and chest radiographs (JSRT database), demonstrate how this new generation of algorithms significantly reduce the computational cost, more than halving it, while maintaining the same levels of accuracy.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Algorithm 1
Algorithm 2
Fig. 7
Fig. 8

Similar content being viewed by others

Notes

  1. All the algorithms were performed on a 3.3 GHz Intel® Xeon® W5590 with 12 GB of RAM. All implementations were in Matlab® R2010a 64-bits.

  2. The absolute running times correspond to implementations performed in Matlab® R2010a 64-bits prioritizing the clarity of the code over the execution speed. Thus, they must be interpreted with caution, and not as an absolute reference.

References

  1. Al-Shaher, A.A., Hancock, E.R.: Learning mixtures of point distribution models with the em algorithm. Pattern Recognit. 36(12), 2805–2818 (2003)

    Article  MATH  Google Scholar 

  2. Allen, P.D., Graham, J., Farnell, D.J.J., Harrison, E.J., Jacobs, R., Nicopolou-Karayianni, K., Lindh, C., van der Stelt, P.F., Horner, K., Devlin, H.: Detecting reduced bone mineral density from dental radiographs using statistical shape models. IEEE Trans. Inf. Technol. Biomed. 11(6), 601–610 (2007)

    Article  Google Scholar 

  3. van Assen, H.C., Danilouchkine, M.G., Frangi, A.F., Ordás, S., Westenberg, J.J.M., Reiber, J.H.C., Lelieveldt, B.P.F.: Spasm: a 3D-ASM for segmentation of sparse and arbitrarily oriented cardiac MRI data. Med. Image Anal. 10(2), 286–303 (2003)

    Article  Google Scholar 

  4. van den Berg, J.C. (ed.): Wavelets in Physics. Cambridge University Press, Cambridge (1999)

    Google Scholar 

  5. Böhm, W.: Cubic B-Spline curves and surfaces in computer aided geometric design. Computing 19(1), 29–34 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  6. Burt, P.: The Pyramid as a structure for efficient computation. In: Multi-Resolution Image Processing and Analysis. Springer, Berlin (1984)

    Google Scholar 

  7. Cerrolaza, J., Villanueva, A., Cabeza, R.: Shape constraint strategies: novel approaches and comparative robustness. In: Proc. British Machine Vision Conf. (BMVC’11) (2011)

    Google Scholar 

  8. Cheung, K.W., Yeung, D.Y., Chin, R.T.: On deformable models for visual pattern recognition. Pattern Recognit. 35(7), 1507–1526 (2002)

    Article  MATH  Google Scholar 

  9. Chuang, G.C.H., Kuo, C.C.J.: Wavelet descriptor of planar curves: theory and applications. IEEE Trans. Image Process. 5(1), 56–70 (1996)

    Article  Google Scholar 

  10. Cootes, T.F., Taylor, C.J., Lanitis, A.: In: Active Shape Models: Evaluation of a Multi-resolution Method for Improving Image Search, pp. 327–336 (1994)

    Google Scholar 

  11. Cootes, T.F., Taylor, C.J.: Active shape models: A review of recent work. In: Current Issues in Statistical Shape Analysis, pp. 108–114. Leeds University Press, Leeds (1995)

    Google Scholar 

  12. Cootes, T.F., Taylor, C.J.: Statistical models of appearance for computer vision. Tech. rep., Department of Imaging Science and Biomedical Engineering, University of Manchester (2004). Available from http://www.isbe.man.ac.uk/~bim/Models/appmodels.pdf

  13. Cootes, T.F., Taylor, C.J., Cooper, D.H., Graham, J.: Active shape models—their training and application. Comput. Vis. Image Underst. 61(1), 38–59 (1995)

    Article  Google Scholar 

  14. Daubechies, I.: Ten Lectures on Wavelets. Society for Industrial and Applied Mathematics, Philadelphia (1992)

    Book  MATH  Google Scholar 

  15. Davatzikos, C., Tao, X., Shen, D.: Hierarchical active shape models, using the wavelet transform. IEEE Trans. Med. Imaging 22(3), 414–423 (2003)

    Article  Google Scholar 

  16. Davies, R.H., Twining, C.J., Cootes, T.F., Taylor, C.J.: Building 3-D statistical shape models by direct optimization. IEEE Trans. Med. Imaging 29(4), 961–981 (2010)

    Article  Google Scholar 

  17. Deubler, J., Olivo, J.C.: A wavelet-based multiresolution method to automatically register images. J. Math. Imaging Vis. 7, 199–209 (1997)

    Article  Google Scholar 

  18. Duta, N., Sonka, M.: Segmentation and interpretation of MR brain images: an improved active shape model. IEEE Trans. Med. Imaging 17(6), 1049–1062 (1998)

    Article  Google Scholar 

  19. Farin, G.E., Hansford, D.: The Essential of CAGD. AK Peters, Wellesley (2000)

    Google Scholar 

  20. Feng, J., Ip, H.H.: A multi-resolution statistical deformable model (misto) for soft-tissue organ reconstruction. Pattern Recognit. 42(7), 1543–1558 (2009)

    Article  Google Scholar 

  21. Finkelstein, A., Salesin, D.H.: Multiresolution curves. In: SIGGRAPH, pp. 261–268. ACM, New York (1994)

    Google Scholar 

  22. Frangi, A.F., Rueckert, D., Schnabel, J.A., Niessen, W.J.: Automatic construction of multiple-object three-dimensional statistical shape models: application to cardiac modeling. IEEE Trans. Med. Imaging 21(9), 1151–1166 (2002)

    Article  Google Scholar 

  23. Garrido, A., Blanca, N.P.D.L.: Physically-based active shape models: initialization and optimization. Pattern Recognit. 31(8), 1003–1017 (1998)

    Article  Google Scholar 

  24. van Ginneken, B., Frangi, A.F., Staal, J.J., ter Haar Romeny, B.M., Viergever, M.A.: Active shape model segmentation with optimal features. IEEE Trans. Med. Imaging 21(8), 924–933 (2002)

    Article  Google Scholar 

  25. van Ginneken, B., Stegmann, M.B., Loog, M.: Segmentation of anatomical structures in chest radiographs using supervised methods: a comparative study on a public database. Med. Image Anal. 10(1), 19–40 (2006)

    Article  Google Scholar 

  26. Gortler, S.J., Cohen, M.F.: Hierarchical and variational geometric modeling with wavelets. Tech. rep., Department of Computer Science Princeton University (1995). Available from http://www.cs.harvard.edu/~sjg/papers/TR-95-25.ps

  27. Goswami, J.C., Chan, A.K.: Fundamentals of Wavelets: Theory, Algorithms, and Applications. Wiley-Interscience, New York (1999)

    MATH  Google Scholar 

  28. Hamarneh, G., Gustavsson, T.: Deformable spatio-temporal shape models: extending active shape models to 2D+time. Image Vis. Comput. 22(6), 461–470 (2004). doi:10.1016/j.imavis.2003.11.009

    Article  Google Scholar 

  29. Hoogendoorn, C., Sukno, F.M., Ordás, S., Frangi, A.F.: Bilinear models for spatio-temporal point distribution analysis. Int. J. Comput. Vis. 85, 237–252 (2009)

    Article  Google Scholar 

  30. Lanitis, A., Taylor, C.J., Cootes, T.F.: Automatic interpretation and coding of face images using flexible models. IEEE Trans. Pattern Anal. Mach. Intell. 19(7), 743–756 (1997)

    Article  Google Scholar 

  31. Leduc, J.P.: A group-theoretic construction with spatiotemporal wavelets for the analysis of rotational motion. J. Math. Imaging Vis. 17, 207–236 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  32. Lee, S.W., Kang, J., Shin, J., Paik, J.: Hierarchical active shape model with motion prediction for real-time tracking of non-rigid objects. IET Comput. Vis. 1(1), 17–24 (2007)

    Article  MathSciNet  Google Scholar 

  33. Li, H., Chutatape, O.: Boundary detection of optic disk by a modified asm method. Pattern Recognit. 36(9), 2093–2104 (2003). Kernel and Subspace Methods for Computer Vision

    Article  MATH  Google Scholar 

  34. Lina, J.M.: Image processing with complex Daubechies wavelets. J. Math. Imaging Vis. 7, 211–223 (1997)

    Article  MathSciNet  Google Scholar 

  35. Ling, H., Zhou, S., Zheng, Y., Georgescu, B., Suehling, M., Comaniciu, D.: Hierarchical, learning-based automatic liver segmentation. In: IEEE Conference on Computer Vision and Pattern Recognition, 2008. CVPR 2008, pp. 1–8 (2008). doi:10.1109/CVPR.2008.4587393

    Google Scholar 

  36. Liu, C., Shum, H.Y., Zhang, C.: Hierarchical shape modeling for automatic face localization. In: ECCV’02: Proc. 7th European Conf. Comp. Vis. II, pp. 687–703. Springer, London (2002)

    Google Scholar 

  37. Lohakan, M., Nantivatana, P., Narkbuakaew, W., Pintavirooj, C., Sangworasil, M.: Multiresolution image alignment based on discrete wavelet transform. In: IEEE Reg. 10 TENCON (2005), pp. 1–4 (2005)

    Chapter  Google Scholar 

  38. Lounsbery, M., DeRose, T., Warren, J.: Multiresolution surfaces of arbitrary topological type. Tech. rep., Department of Computer Science and Engineering, University of Washington (1994)

  39. Lounsbery, M., DeRose, T.D., Warren, J.: Multiresolution analysis for surfaces of arbitrary topological type. ACM Trans. Graph. 16(1), 34–73 (1997)

    Article  Google Scholar 

  40. Lounsbery, M., DeRose, T.D., Warren, J.: Multiresolution analysis for surfaces of arbitrary topological type. ACM Trans. Graph. 16, 34–73 (1997)

    Article  Google Scholar 

  41. Mallat, S.G.: A theory for multiresolution signal decomposition: the wavelet representation. IEEE Trans. Pattern Anal. Mach. Intell. 11(7), 674–693 (1989)

    Article  MATH  Google Scholar 

  42. Mallat, S.G.: A theory for multiresolution signal decomposition: the wavelet representation. IEEE Trans. Pattern Anal. Mach. Intell. 11(7), 674–693 (1989). doi:10.1109/34.192463

    Article  MATH  Google Scholar 

  43. Martinez, A., Benavente, R.: The ar face database. Tech. rep., Computer Vision Center, Universitat Autònoma de Barcelona (1998). Available from http://www.cat.uab.cat/Publications/1998/MB98/CVCReport24.pdf

  44. Mokhtarian, F., Mackworth, A.K.: A theory of multiscale, curvature-based shape representation for planar curves. IEEE Trans. Pattern Anal. Mach. Intell. 14(8), 789–805 (1992)

    Article  Google Scholar 

  45. Olsen, L., Samavati, F.F., Bartels, R.H.: Multiresolution for curves and surfaces based on constraining wavelets. Comput. Graph. 31(3), 449–462 (2007)

    Article  Google Scholar 

  46. Samavati, F.F.: Local filters of b-spline wavelets. In: Proc. of Int. Workshop Biometric Tech. (2004), pp. 105–110 (2004)

    Google Scholar 

  47. Shiraishi, J., Katsuragawa, S., Ikezoe, J., Matsumoto, T., Kobayashi, T., Komatsu, K., Matsui, M., Fujita, H., Kodera, Y., Doi, K.: Development of a digital image database for chest radiographs with and without a lung nodule: receiver operating characteristic analysis of radiologists’ detection of pulmonary nodules. Am. J. Roentgenol. 174, 71–74 (2000)

    Google Scholar 

  48. Singh, S.P.: Approximation Theory, Wavelets and Applications. Springer, Berlin (2009)

    Google Scholar 

  49. Stegmann, M.B., Fisker, R., Ersbøll, B.K.: On properties of active shape models. Tech. rep., Informatics and Mathematical Modelling, Technical University of Denmark, DTU, Richard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby (2000). Available from http://www2.imm.dtu.dk/pubdb/views/edocdownload.php/125/pdf/imm125.pdf

  50. Stollnitz, E.J., Derose, T.D., Salesin, D.H.: Wavelets for Computer Graphics: Theory and Applications. Morgan Kaufmann, San Francisco (1996)

    Google Scholar 

  51. Sukno, F.M., Frangi, A.F.: Reliability estimation for statistical shape models. IEEE Trans. Image Process. 17(12), 2442–2455 (2008)

    Article  MathSciNet  Google Scholar 

  52. Sukno, F.M., Ordas, S., Butakoff, C., Cruz, S., Frangi, A.F.: Active shape models with invariant optimal features: application to facial analysis. IEEE Trans. Pattern Anal. Mach. Intell. 29(7), 1105–1117 (2007). doi:10.1109/TPAMI.2007.1041

    Article  Google Scholar 

  53. Taylor, C.J., Cooper, D.H., Graham, J.: Training models of shape from sets of examples. In: Proc. British Machine Vision Conf., pp. 9–18. Springer, London (1992)

    Google Scholar 

  54. Zavadsky, V.: Image approximation by rectangular wavelet transform. J. Math. Imaging Vis. 27, 129–138 (2007)

    Article  MathSciNet  Google Scholar 

  55. Zhang, H.M., Wang, Z., Han, L., Li, D.: Locating the starting point of closed contour based on half-axes-angle. In: Proc. Int. Conf. Machine Learning and Cyber (2004), pp. 3899–3903 (2004)

    Google Scholar 

Download references

Acknowledgements

The work described in this study was supported by the Spanish Ministry of Science and Innovation with an FPU grant (AP2007-03931). This work was also partially supported by the Spanish Ministry of Science and Innovation (Ref. TIN2009-14536-C02-01), Plan E and FEDER.

Author information

Authors and Affiliations

  1. Department of Electrical and Electronic Engineering, Public University of Navarra, Pamplona, Spain

    Juan J. Cerrolaza, Arantxa Villanueva & Rafael Cabeza

  2. Research Group for Computational Imaging and Simulation Technologies in Biomedicine, Universitat Pompeu Fabra, Barcelona, Spain

    Constantine Butakoff & Alejandro F. Frangi

  3. Centre for Image Processing & Analysis, Dublin City University, Dublin 9, Ireland

    Federico M. Sukno

  4. Molecular & Cellular Therapeutics, Royal College of Surgeons in Ireland, Dublin 2, Ireland

    Federico M. Sukno

Authors
  1. Juan J. Cerrolaza
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Arantxa Villanueva
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Federico M. Sukno
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Constantine Butakoff
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Alejandro F. Frangi
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Rafael Cabeza
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Juan J. Cerrolaza.

Appendix: Starting Point Dependency in Closed Contours

Appendix: Starting Point Dependency in Closed Contours

Invariance, uniqueness and stability are desirable properties of shape descriptors [44]. Chuang and Kuox [9] successfully derived these properties when using wavelets as shape descriptors, under the assumption of a well defined starting point for the curves. While this condition is easily satisfied in the case of open contours, there exists an inherent uncertainty when dealing with closed ones. In the absence of a prior registration, the problem of starting point of the contour must be handled ad hoc, since different starting points of the same shape will result in different wavelet coefficients. Lohakan et al. [37] solve this problem by defining the point of maximum curvature as starting point, while Zhang et al. [55] propose a starting point location strategy based on half-axes-angles, i.e., the least counterclockwise angles formed by the line segments connecting the centroid to the nearest and farthest point of the contour. However, the PDM requires that the landmarks are placed in the same order and in the same places along the object’s contour, ensuring thus a point correspondence, and eliminating the need for a consistent localization of the starting point in every shape. Nevertheless, there still exists an uncertainty about whether or not the chosen starting point, and thus the corresponding coarser versions of the shape, significantly affects the final segmentation accuracy.

Suppose (14) is the vector expression of a contour. If the contour is closed, this notation remains valid assuming an implicit periodicity of its control points [19]

$$ \bigl(x_{K_{0}+i}^{0}, x_{K_{0}+i}^{0}\bigr) = \bigl(x_{i}^{0}, x_{i}^{0}\bigr), \quad i=1,\ldots,k $$
(28)

for a uniform k-th degree B-spline closed curve. This periodicity condition, depending on whether the contour is closed or open, is also reflected in the set of filtering matrices. In the case of open contours, and following the block notation proposed by Samavati [46], the form of these matrices for a B-spline wavelet decomposition can be expressed as

$$ \mathbf{M}^{j} = \begin{pmatrix} \mathbf{M}_{s}^{j}\\ \mathbf{M}_{r}^{j}\\ \mathbf{M}_{e}^{j} \end{pmatrix} $$
(29)

where M j can be A j, B j, F j or G j. \(\mathbf{M}_{s}^{j}\) and \(\mathbf{M}_{e}^{j}\) represent special submatrices for the start and end of the curve, required to guarantee the end-point interpolation, while \(\mathbf{M}_{r}^{j}\) corresponds to the regular portion of the curve. In the case of closed contours, this block notation is simplified thanks to the implicit periodicity, \(\mathbf{M}^{j}=\mathbf{M}_{r}^{j}\). Focusing our attention on the analysis filter A j, the elements of each row of its regular structure, \(\mathbf{A}_{r}^{j}\), are obtained by shifting right by two positions of the elements of the previous row. An immediate consequence of this particular structure is the invariance of the wavelet coefficients to the displacements of the starting point that are a multiple of two. Suppose \(\mathbf{x}_{t}^{j-1}\) represents the vector form of the closed contour x j−1 whose starting point has been shifted t positions to the right. With this notation

$$ \mathbf{A}^{j}\mathbf{x}_{t}^{j-1} = \mathbf{A}^{j}\mathbf{x}_{t+2n}^{j-1}, \quad n\in\mathbb{Z} $$
(30)

That is, given a closed contour at the j-th level of resolution, there are 2L possible coarser versions at the level j+L-th, with L∈ℕ (see Fig. 9). This raises an interesting issue when incorporating a multiresolution shape approach to the segmentation algorithm, since a new degree-of-freedom has been added to the algorithm and thus, it should be properly optimized.

Fig. 9
figure 11

Starting point dependency in closed contours. (a) Contour of a right lung in highest resolution (level 0); (b), (c) and (d) show the possible contours obtained in levels 1, 2 and 3, respectively, when shifting the starting point

Full size image

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cerrolaza, J.J., Villanueva, A., Sukno, F.M. et al. Full Multiresolution Active Shape Models. J Math Imaging Vis 44, 463–479 (2012). https://doi.org/10.1007/s10851-012-0338-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-012-0338-y

Keywords

Search

Navigation