Skip to main content
SpringerLink
Log in

Morphological Decomposition and Compression of Binary Images via a Minimum Set Cover Algorithm

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

Abstract

In this paper, by a novel morphological decomposition method, we propose an efficient compression approach. Our presented decomposition arises from solving a minimum set cover problem (MSCP) obtained from the image skeleton data. We first use the skeleton pixels to create a collection of blocks which cover the foreground. The given blocks are both overlapped and too many. Hence, in order to find the minimum number of the blocks that cover the foreground, we form an MCSP. To solve this problem, we present a new algorithm of which accuracy is better than those of the known methods in the literatures. Also, its error analysis is studied to obtain an error bound. In the sequel, we present a fast algorithm which include an extra parameter by which the relation between the accuracy and CPU time can be controlled. Finally, several examples are given to confirm the efficiency of our approach.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. The database exists in two versions original (the leaves with petioles, high resolution) and simplified (the leaves without petioles, downsampled by a factor 2). Table 3 refers to the original version.

References

  1. Quddus, A., Fahmy, M.M.: Binary text image compression using overlapping rectangular partitioning. Pattern Recognit. Lett. 20, 81–88 (1999)

    Article  MATH  Google Scholar 

  2. Zakaria, M.F., Vroomen, L.J., Zsombor-Murray, P., van Kessel, J.M.: Fast algorithm for the computation of moment invariants. Pattern Recognit. 20(6), 639–643 (1987)

    Article  Google Scholar 

  3. Dai, M., Baylou, P., Najim, M.: An efficient algorithm for computation of shape moments from run-length codes or chain codes. Pattern Recognit. 25(10), 1119–1128 (1992)

    Article  Google Scholar 

  4. Flusser, J.: Refined moment calculation using image block representation. IEEE Trans. Image Process. 9(11), 1977–1978 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  5. Li, B.C.: A new computation of geometric moments. Pattern Recognit. 26(1), 109–113 (1993)

    Article  Google Scholar 

  6. Spiliotis, I.M., Mertzios, B.G.: Real-time computation of two-dimensional moments on binary images using image block representation. IEEE Trans. Image Process. 7(11), 1515–1609 (1998)

    Article  Google Scholar 

  7. Kawaguchi, E., Endo, T.: On a method of binary-picture representation and its application to data compression. IEEE Trans. Pattern Anal. 2(1), 27–35 (1980)

    Article  MATH  Google Scholar 

  8. Sossa-Azuela, J.H., Yáñez-Márquez, C., Dáz de León S, J.L.: Computing geometric moments using morphological erosions. Pattern Recognit. 34(2), 271–276 (2001)

    Article  MATH  Google Scholar 

  9. Suk, T., Flusser, J.: Refined morphological methods of moment computation. In: 20th International Conference on Pattern Recognition ICPR10, IEEE Computer Society, vol. 30, pp. 966–970 (2010)

  10. Eppstein, D.: aph-theoretic solutions to computational geometry problems. In: 35th International Workshop on Graph-Theoretic Concepts in Computer Science WG09. Lecture Notes in Computer Science, vol. 5911, pp. 1–16. Springer (2009)

  11. Ferrari, L., Sankar, P.V., Sklansky, J.: Minimal rectangular partitions of digitized blobs. Comput. Vision Graph. Image Process. 28(1), 58–71 (1980)

    Article  MATH  Google Scholar 

  12. Goldberg, A.V., Rao, S.: Beyond the flow decomposition barrier. J. ACM 45(5), 783–797 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  13. Imai, H., Asano, T.: Efficient algorithms for geometric graph search problems. SIAM J. Comput. 15(2), 478–494 (1986)

    Article  MathSciNet  MATH  Google Scholar 

  14. Lipski Jr., W., Lodi, E., Luccio, F., Mugnai, C., Pagli, L.: On two-dimensional data organization II, Fundamenta Informaticae. Ann. Soc. Math. Pol. 4(2), 254–260 (1979)

    MATH  Google Scholar 

  15. Keil, J.M.: Polygon decomposition. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 491–518. Elsevier, New York (2000)

    Chapter  Google Scholar 

  16. Ohtsuki, T.: Minimum dissection of rectilinear regions. Proc. IEEE Int. Conf. Circuits Syst. ISCAS 82, 1210–1213 (1982)

    Google Scholar 

  17. Suk, T., Höschl IV, C., Flusser, J.: Rectangular decomposition of binary images. In: ACIVS, 14th International Conference, Czech Republic (2012 September). https://doi.org/10.1007/978-3-642-33140-4_19

  18. Suk, T., Höschl IV, C., Flusser, J.: Decomposition of binary images: a survey and comparison. Pattern Recognit. 45, 4279–4291 (2012)

    Article  Google Scholar 

  19. Arcelli, C., Di Baja, G.S.: Ridge points in euclidean distance maps. Pattern Recognit. Lett 1, 237–243 (1992)

    Article  Google Scholar 

  20. Hesselink, W.H., Roerdink, J.B.T.M.: Euclidean skeletons of digital image and volume data in linear time by the integer medial axis transform. IEEE Trans. Pattern. Anal. 30(12), 2204–2217 (2008)

    Article  Google Scholar 

  21. Jalba, A.C., Sobiecki, A., Telea, A.C.: An unified multiscale framework for planar, surface, and curve skeletonization. IEEE Trans. Pattern. Anal. 38(1), 30–45 (2016)

    Article  Google Scholar 

  22. Marie, R., Labbani-Igbida, O., Mouaddib, E.M.: The delta medial axis: a fast and robust algorithm for filtered skeleton extraction. Pattern Recognit. 56, 26–39 (2016)

    Article  Google Scholar 

  23. Presti, L.L., Cascia, M.L.: 3D skeleton-based human action classification: a survey. Pattern Recognit. 53, 130–147 (2016)

    Article  Google Scholar 

  24. Wu, Q.J., Bourland, J.D.: Three-dimensional skeletonization for computer-assisted treatment planning in radiosurgery. Comput. Med. Imaging Gr. 24(4), 243–251 (2000)

    Article  Google Scholar 

  25. Borgefors, G.: Distance transformations in digital images. Comput. Vision Graph. 34, 344–371 (1986)

    Article  Google Scholar 

  26. Hirata, T.: A unified linear-time algorithm for computing distance maps. Inform. Process. Lett. 58, 129–133 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  27. Maurer Jr., C.R., Qi, R., Raghavan, V.: A linear time algorithm for computing the euclidean distance transform in arbitrary dimensions. IEEE Trans. Pattern. Anal. 25(2), 265–270 (2003)

    Article  Google Scholar 

  28. Hesselink, W.H.: A linear-time algorithm for euclidean feature transform sets. Inform. Process. Lett. 102, 181–186 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  29. Maurer Jr., C.R., Raghavan, V., Qi, R.: A Linear time algorithm for computing the euclidean distance transform in arbitrary dimensions. Inf. Process. Med. Imaging 58, 358–364 (2001)

    Article  MATH  Google Scholar 

  30. Meijster, A., Roerdink, J.B.T.M., Hesselink, W.H.: A general algorithm for computing distance transforms in linear time. In: Goutsias, J., Vincent, L., Bloomberg, D.S. (eds.) Mathematical Morphology and Its Applications to Image and Signal Processing, pp. 331–340. Kluwer Academic, Dordrecht (2000)

    Google Scholar 

  31. Strzodka, R., Telea, A.: Generalized distance transforms and skeletons in graphics hardware. In: Proceedings of the Joint EUROGRAPHICS and IEEE TCVG Symposium on Visualization, pp. 221–230 (2004)

  32. Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. The MIT Press, Cambridge (1991)

    MATH  Google Scholar 

  33. Karp, R.M.: Reducibility among combinatorial problems. In: Miller, Raymond E., Thatcher, James W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)

    Chapter  Google Scholar 

  34. Desai, R., Yang, Q., Wu, Z., Meng, W., Yu, C.: Identifying redundant search engines in a very large scale metasearch engine context. In: ACM WIDM ’06, 8th ACM International Workshop on Web Information and Data Management, November 10, pp. 51–58. Arlington, Virginia, USA (2006)

  35. Yang, Q., MacPeek, J., Nofsinger, A.: Efficient and effective practical algorithms for the set-covering problem. In: Conference on Scientific Computing (CSC08), The 2008 World Congress in Computer Science, Computer Engineering and Applied Computing (WORLDCOMP08), Las Vegas, July 14–17 (2008)

  36. Yang, Q., Nofsinger, A., McPeek, J., Phinney, J., Knuesel, R.: A complete solution to the set covering problem. In: Proceedings of the International Conference on Scientific Computing (CSC), Las Vegas, NV, USA, 27–30 July, pp. 36–41 (2015)

  37. Department of Image Processing: Tree leaf database. http://zoi.utia.cas.cz/tree_leaves

Download references

Acknowledgements

We thank the anonymous reviewers for their careful reading of our manuscript and their many insightful comments and suggestions.

Author information

Authors and Affiliations

  1. Mathematics Department, Vali-e-Asr University of Rafsanjan, Rafsanjan, Iran

    Davod Farazmanesh & Ali Tavakoli

  2. Mathematics Department, University of Mazandaran, Babolsar, Iran

    Ali Tavakoli

Authors
  1. Davod Farazmanesh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ali Tavakoli
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ali Tavakoli.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Farazmanesh, D., Tavakoli, A. Morphological Decomposition and Compression of Binary Images via a Minimum Set Cover Algorithm. J Math Imaging Vis 61, 71–83 (2019). https://doi.org/10.1007/s10851-018-0825-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10851-018-0825-x

Keywords

Mathematics Subject Classification

Search

Navigation