Segmented face approximation with adaptive region growing based on low-degree polynomial fitting | Signal, Image and Video Processing
Skip to main content
Springer Nature Link
Log in

Segmented face approximation with adaptive region growing based on low-degree polynomial fitting

  • Original Paper
  • Published:
Signal, Image and Video Processing Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

Nowadays, an objective in visual communication is to send and store images of faces at a low bit rate, such that the faces are still recognizable and that the compression does not prevent remote face analysis. We present a novel segmented face approximation algorithm. Greyscale face images are segmented into meaningful surface segments with an adaptive region growing algorithm based on low-degree polynomial fitting. The algorithm uses a new adaptive thresholding technique with the \(L_\infty \) fitting cost as a segmentation criterion. The polynomial degree and the fitting error are automatically adapted during the region growing process. The main novelty is that the algorithm detects outliers and edges, distinguishes between strong and smooth intensity transitions, and finds surface segments that are bent in a certain way, such as flat, planar, convex, concave or saddle patches. As a result, the surface segments correspond to facial features, and the contours separating the surface segments coincide with real image face edges. Moreover, the curvature-based surface shape information facilitates many tasks in automated face analysis, demonstrated in this paper by face verification performed on the polynomial representation. The polynomial representation provides good approximation of facial features, while preserving all the necessary details of the face in the reconstructed image. When compared with different compression methods, we achieve higher compression ratios and better recognizable faces at low bit rates. This is confirmed by correct identification percentages obtained by face recognition algorithms on the compressed data.

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
¥17,985 /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 (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18

Similar content being viewed by others

Notes

  1. Remember that during region growing, only the fitting cost was computed.

Abbreviations

\(p\) :

Pixel

\(S\) :

Segment

\(d\) :

Polynomial degree

\(r(S)\) :

Minimal fitting cost over \(S\)

\(\tilde{r}(S)\) :

Estimated fitting cost over \(S\)

\(D\) :

Elemental subset

\(M\) :

Number of elemental subsets

\(\tilde{r}(S_i; p_i)\) :

Estimated fitting cost of adding \(p_i\) to \(S_i\)

\(p_k\) :

New pixel

\(X_k\) :

Local behaviour measure of fitting costs

\(R_k\) :

Local neighbourhood of \(p_k\)

\(T_X\) :

Threshold on \(X_k\)

\(Y_k\) :

Global behaviour measure of fitting costs

\(T_Y\) :

Threshold on \(Y_k\)

References

  1. Adams, R., Bischof, L.: Seeded region growing. IEEE Trans. Pattern Anal. Mach. Intell. 16(6), 641–647 (1994)

    Article  Google Scholar 

  2. Aharon, M., Elad, M., Bruckstein, A.: The k-svd: an algorithm for designing of overcomplete dictionaries for sparse representation. IEEE Trans. Signal. Process. 54, 4311–4322 (2006)

    Article  Google Scholar 

  3. Alani, D., Averbuch, A.: Dekel S Image coding with geometric wavelets. IEEE Trans. Image Process. 16(1), 69–77 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  4. Aravind, I., Chaitanya, C., Guruprasad, M., Partha, S., Sudhaker, S.: Implementation of image segmentation and reconstruction using genetic algorithms. In: IEEE International Conference on Industrial Technology, pp. 970–975 (2002)

  5. Bartlett, M., Donato, G., Movellan, J., Hager, J., Ekman, P., Sejnowski, T.: Image representations for facial expression coding. Adv. Neural Inf. Process. Syst. 12, 886–892 (2000)

    Google Scholar 

  6. Biswas, S.: Segmentation based compression for gray-level images. Pattern Recogn. 36(7), 1501–1517 (2003)

    Article  Google Scholar 

  7. Bosworth, J., Acton, S.: Segmentation-based image coding by morphological local monotonicity. In: Conference on Signals, Systems and Computers, pp. 65–69 (2000)

  8. Bryt, O., Elad, M.: Compression of facial images using the K-SVD algorithm. J. Vis. Commun. Image R 19, 270–282 (2008)

    Article  Google Scholar 

  9. Candès, E.J., Donoho, D.L.: Curvelets: a surprisingly effective nonadaptive representation for objects with edges. In: Curves and Surfaces, pp. 1–10 (1999)

  10. Canny, J.: A computational approach to edge detection. IEEE Trans. Pattern Anal. Mach. Intell. 8, 679–698 (1986)

    Article  Google Scholar 

  11. Christopoulos, C., Philips, W., Skodras, A., Cornelis, J.: Segmented image coding: techniques and experimental results. Signal Process. Image Commun. 11, 63–80 (1997)

    Article  Google Scholar 

  12. Comaniciu, D., Meer, P.: Mean shift: a robust approach toward feature space analysis. IEEE Trans. Pattern Anal. Mach. Intell. 24(5), 603–619 (2002)

    Article  Google Scholar 

  13. Couprie, C., Grady, L., Najman, L., Talbot, H.: Power watershed: a unifying graph-based optimization framework. IEEE Trans. Pattern Anal. Mach. Intell. 33(7), 1384–1397 (2011)

    Article  Google Scholar 

  14. Deboeverie, F., Teelen, K., Veelaert, P., Philips, W.: Adaptive constructive polynomial fitting. In: Proceedings of Advanced Concepts for Intelligent Vision Systems, pp. 173–184 (2010)

  15. Deboeverie, F., Veelaert, P., Philips, W.: Face analysis using curve edge maps. In: Proceedings of International Conference on Image Analysis and Processing, pp. 109–118 (2011)

  16. Do, M.N., Vetterli, M.: Contourlets. In: Stoeckler, J., Welland, G.V. (eds.) Beyond Wavelets. Academic, San Diego (2003)

    Google Scholar 

  17. Donoho, D.L.: Wedgelets: nearly minimax estimation of edges. Ann. Stat. 27(3), 859–897 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  18. Donoho, D.L., Huo, X.: Beamlets and multiscale image analysis. Technical report, Department of Statistics, Stanford University, Stanford, CA (2001)

  19. Eden, M., Kocher, M.: On the performance of a contour coding algorithm in the context of image coding part 1: contour segment coding. Signal Process. 8, 381–386 (1985)

    Article  Google Scholar 

  20. Elad, M., Goldenberg, R., Kimmel, R.: Low bit-rate compression of facial images. IEEE Trans. Image Process. 16(9), 2379–2383 (2007)

    Article  MathSciNet  Google Scholar 

  21. Gerek, O.N., Çinar, H.: Segmentation based coding of human face images for retrieval. Signal Process. 84, 1041–1047 (2004)

    Article  MATH  Google Scholar 

  22. Gersho, A., Gray, R.: Vector Quantization and Signal Compression. Kluwer Academic Publishers, Dordrecht (1995)

    Google Scholar 

  23. Gilge, M., Engelhardt, T., Mehlan, R.: Coding of arbitrarily shaped image segments based on a generalized orthogonal transform. Signal Process. Image Commun. 1(2), 153–180 (1989)

    Article  Google Scholar 

  24. Hu, J., Wang, R., Wang, Y.: Compression of personal identification pictures using vector quantization with facial feature correction. Opt. Eng. 35, 198–203 (1996)

    Article  Google Scholar 

  25. Jackway, P.: Gradient watersheds in morphological scalespace. IEEE Trans. Image Process. 15(6), 913–921 (1996)

    Article  Google Scholar 

  26. Kanga, C.C., Wanga, W.J., Kangb, C.H.: Image segmentation with complicated background by using seeded region growing. Int. J. Electron. Commun. (2012). doi:10.1016/j.aeue.2012.01.011

  27. Kassim, A.A., Lee, W.S., Zonoobi, D.: Hierarchical segmentation-based image coding using hybrid quad-binary trees. IEEE Trans. Image Process. 6, 1284–1291 (2009)

    Article  MathSciNet  Google Scholar 

  28. Kunt, M., Ikonomopoulos, A., Kocher, M.: Second generation image coding. Proc. IEEE 73(4), 549–574 (1985)

    Article  Google Scholar 

  29. Kunt, M., Benard, M., Leonardi, R.: Recent results in high-compression image coding. IEEE Trans. Circ. Syst. 34(11), 1306–1336 (1987)

    Article  Google Scholar 

  30. Lambert, J.: Photometria Sive de Mensura de Gratibus Luminis. Colorum et Umbrae. Eberhard Klett, Augsberg (1760)

    Google Scholar 

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

    Article  Google Scholar 

  32. Li, H., Roivainen, P., Forchheimer, R.: 3-d motion estimation in model-based facial image coding. IEEE Trans. Pattern Anal. Mach. Intell. 15(6), 545–555 (1993)

    Article  Google Scholar 

  33. Lyons, M., Akamatsu, S.: Coding facial expressions with Gabor wavelets. In: Proceedings of Third IEEE International Conference on Automatic Face and Gesture Recognition, pp. 200–205 (1998)

  34. Martinez, A., Benavente, R.: The ar face database. Technical report. CVC Technical, Report # 24 (1998)

  35. Maxwell, B.A., Shafer, S.A.: Segmentation and interpretation of multicolored objects with highlights. Comput. Vis. Image Underst. 77, 1–24 (2000)

    Article  Google Scholar 

  36. Moghaddam, B., Pentland, A.: An automatic system for model-based coding of faces. In: IEEE Data Compression Conference, pp. 362–370 (1995)

  37. Muñoz, X., Freixenet, J., Cufí, X., Martí, J.: Strategies for image segmentation combining region and boundary information. Pattern Recogn. Lett. 24(1–3), 375–392 (2003)

    Article  Google Scholar 

  38. Pappas, T.N.: An adaptive clustering algorithm for image segmentation. IEEE Trans. Signal Process. 40(4), 901–914 (1992)

    Article  Google Scholar 

  39. Pennec, E.L., Mallat, S.: Sparse geometric image representations ith bandelets. IEEE Trans. Image Process. 14(4), 423–438 (2005)

    Google Scholar 

  40. Philips, W.: Fast coding of arbitrarily shaped image segments using weakly separable bases. Opt Eng Special Sect. Vis. Commun. Image Process. 35, 177–186 (1996)

    Google Scholar 

  41. Pohle, R., Toennies, K.D.: Proceedings of spie medical imaging. In: Segmentation of medical images using adaptive region growing, pp. 1337–1347 (2001)

  42. Psychological image collection at stirling (pics) (n.d.). http://www.pics.stir.ac.uk

  43. Qin, A.K., Clausi, D.A.: Multivariate image segmentation using semantic region growing with adaptive edge penalty. IEEE Trans. Image Process. 19(8), 2157–2170 (2010)

    Article  MathSciNet  Google Scholar 

  44. Radha, H., Vetterli, M., Leonardi, R.: Image compression using binary space partitioning trees. IEEE Trans. Image Process. 5(12), 1610–1624 (1996)

    Article  Google Scholar 

  45. Reid, M.M., Millar, R.J., Black, N.D.: Second-generation image coding: an overview. ACM Comput. Surv. 29(1), 3–29 (1997)

    Article  Google Scholar 

  46. Ruppertsberg, A.I., Vetter, T., Bülthoff, H.H.: A face specific similarity measure for image coding and synthesis. Investig. Ophthalmol. Vis. Sci. 39(4), 173 (1998)

    Google Scholar 

  47. Sakalli, M., Yan, H.: Feature-based compression of human face images. Opt. Eng. 37, 1520–1529 (1998)

    Article  Google Scholar 

  48. Salembier, P., Brigger, P., Casas, J., Pardas, M.: Morphological operators for image and video compression. IEEE Trans. Image Process. 5(6), 881–898 (1996)

    Article  Google Scholar 

  49. Samet, H.: The quadtree and related hierarchical data structures. ACM Comput. Surv. 16(2), 187–260 (1984)

    Article  MathSciNet  Google Scholar 

  50. Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22(8), 888–905 (2000)

    Article  Google Scholar 

  51. Shukla, R., Dragotti, P.L., Do, M.N., Vetterli, M.: Rate-distortion optimized tree-structured compression algorithms for piecewise polynomial images. IEEE Trans. Image Process. 14(3), 343–359 (2005)

    Article  MathSciNet  Google Scholar 

  52. Sikora, T.: Trends and perspectives in image and video coding. Proc. IEEE 93(1), 6–17 (2005)

    Article  MathSciNet  Google Scholar 

  53. Sim, K., Hartley, R.: Removing outliers using the \(l_\infty \) norm. In: Proceedings of Computer Vision and, Pattern Recognition, pp. 485–494 (2006)

  54. Somasundarama, K., Palaniappan, N.: Adaptive low bit rate facial feature enhanced residual image coding method using spiht for compressing personal id images. Int. J. Electron. Commun. 65, 589–594 (2011)

    Article  Google Scholar 

  55. Sullivan, G.J., Baker, R.L.: Efficient quadtree coding of images and video. IEEE Trans. Image Process. 3(3), 327–331 (1994)

    Article  Google Scholar 

  56. Taubman, D., Marcellin, M.: JPEG2000: Image Compression Fundamentals, Standards and Practice. Kluwer, Norwell (2002)

    Book  Google Scholar 

  57. Tou, J.T., Gonzalez, R.C.: Pattern Recognition Principles. Addison-Wesley, Reading (1974)

    MATH  Google Scholar 

  58. Turk, M., Pentland, A.: Eigenfaces for recognition. J. Cognit. Neurosci. 3(1), 71–86 (1991)

    Article  Google Scholar 

  59. Veelaert, P.: Constructive fitting and extraction of geometric primitives. CVGIP Graph. Models Image Process. 59(4), 233–251 (1997)

    Article  Google Scholar 

  60. Veelaert, P.: Separability and tight enclosure of point sets, digital geometry algorithms. Theor. Found. Appl. Comput. Imag. 2, 215–243 (2012)

    MathSciNet  Google Scholar 

  61. Veelaert, P., Teelen, K.: Fast polynomial segmentation of digitized curves. In: Proceedings of Discrete Geometry for Computer Imagery, pp. 482–493 (2006)

  62. Vila-Forcén, J.E., Voloshynovskiy, S., Koval, O., Pun, T.: Facial image compression based on structured codebooks in overcomplete domain. EURASIP J. Appl. Signal Process. 2006, 1–11, Art ID 69042 (2006)

  63. Viola, P., Jones, M.: Rapid object detection using a boosted cascade of simple features. In: Proceedings of Computer Vision and, Pattern Recognition, pp. 511–518 (2001)

  64. Wagemans, J., Doorn, A.J.V., Koenderink, J.: The shading cue in context. i-Perception 1(3), 159–178 (2010)

    Article  Google Scholar 

  65. Willett, R., Nowak, R.: Platelets: a multiscale approach for recovering edges and surfaces in photon-limited medical imaging. IEEE Trans. Med. Imag. 22(3), 332–350 (2003)

    Article  Google Scholar 

  66. Yemez, Y., Sankur, B., Anarim, E.: An object-oriented video codec based on region growing motion segmentation. In: Proceedings of International Conference on Image Processing, pp. 444–447 (1997)

  67. Yoo, H.W., Junga, S.H., Janga, D.S., Nab, Y.K.: Extraction of major object features using VQ clustering for content-based image retrieval. Pattern Recogn. 35, 1115–1126 (2002)

    Article  MATH  Google Scholar 

Download references

Acknowledgments

The work was financially supported by iMinds and IWT through the Project ‘iCoCoon’ and by FWO through the Project G.0.398.11.N.10 ‘Multi-camera human behavior monitoring and unusual event detection’.

Author information

Authors and Affiliations

  1. Department of Telecommunications and Information Processing, Image Processing and Interpretation, UGent/iMinds, St-Pietersnieuwstraat 41, 9000, Ghent, Belgium

    Francis Deboeverie, Peter Veelaert & Wilfried Philips

Authors
  1. Francis Deboeverie
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Peter Veelaert
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Wilfried Philips
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Francis Deboeverie.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Deboeverie, F., Veelaert, P. & Philips, W. Segmented face approximation with adaptive region growing based on low-degree polynomial fitting. SIViP 9, 347–363 (2015). https://doi.org/10.1007/s11760-013-0441-6

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11760-013-0441-6

Keywords

Search

Navigation