A Measure of Directional Convexity Inspired by Binary Tomography

• Autorzy: Balázs P. , Ozsvár Z. , Tasi T. S. , Nyúl L. G.

Identyfikatory

DOI

10.3233/FI-2015-1269

• Języki publikacji: EN

Abstrakty

EN

Inspired by binary tomography, we present a measure of directional convexity of binary images combining various properties of the configuration of 0s and 1s in the binary image. The measure can be supported by proper theory, is easy to compute, and as shown in our experiments, behaves intuitively. The measure can be useful in numerous applications of digital image processing and pattern recognition, and especially in binary tomography. We show in detail an application of this latter one, by providing a novel reconstruction algorithm for almost hv-convex binary images. We also present experimental results and mention some of the possible generalizations of the measure.

Słowa kluczowe

EN

digital geometry; convexity measure; hv-convexity; binary tomography; reconstruction from projections

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 141, nr 2/3
• Strony: 151--167
• Opis fizyczny: Bibliogr. 28 poz., rys., tab., wykr.

Twórcy

autor

Balázs P.

• University of Szeged, Institute of Informatics Árpád tér 2., H-6720 Szeged, Hungary

autor

Ozsvár Z.

• University of Szeged, Institute of Informatics Árpád tér 2., H-6720 Szeged, Hungary

autor

Tasi T. S.

• University of Szeged, Institute of Informatics Árpád tér 2., H-6720 Szeged, Hungary

autor

Nyúl L. G.

• University of Szeged, Institute of Informatics Árpád tér 2., H-6720 Szeged, Hungary

Bibliografia

• [1] Balázs, P.: Discrete tomographic reconstruction of binary images with disjoint components using shape information. Int. Journal of Shape Modeling 14:2 (2008) 189–207.
• [2] Balázs, P.: A framework for generating some discrete sets with disjoint components by using uniform distributions. Theoret. Comput. Sci. 406 (2008) 15–23.
• [3] Balázs, P.: A benchmark set for the reconstruction of hv-convex discrete sets from horizontal and vertical projections. Discrete Appl. Math. 157 (2009) 3447–3456.
• [4] Barcucci, E., Del Lungo, A., Nivat, M., Pinzani, R.: Medians of polyominoes: a property for the reconstruction. Int. J. Imag. Syst. Tech. 9 (1998) 69–77.
• [5] Batenburg, K.J.: An evolutionary algorithm for discrete tomography, Disc. Appl. Math. 151 (2005) 36–54.
• [6] Billionnet, A., Jarray, F. Tlig, G., Zagrouba, E.: Reconstructing convex matrices by integer programming approaches. J. Math. Model. Algor. 12 (2013) 329–343.
• [7] Boxter, L.: Computing deviations from convexity in polygons. Pattern Recogn. Lett. 14 (1993) 163–167.
• [8] Bresenham, J.E.: Algorithm for computer control of a digital plotter, IBM Systems Journal 4 (1965) 25–30.
• [9] Brunetti, S., Del Lungo, A., Del Ristoro, F., Kuba, A., Nivat, M.: Reconstruction of 4- and 8-connected convex discrete sets from row and column projections. Linear Algebra Appl. 339 (2001) 37–57.
• [10] Calamoneri, T., Fusco, E.G., Shende, A.M., Shende, S.M.: Proxy assignments for filling gaps in wireless ad-hoc lattice computers. Lecture Notes in Comput. Sci. 4474 (2007) 208–221.
• [11] Chrobak,M., Dürr, C.: Reconstructing hv-convex polyominoes fromorthogonal projections. Inform. Process. Lett. 69(6) (1999) 283–289.
• [12] Dahl, G., Flatberg, T.: Optimization and reconstruction of hv-convex (0,1)-matrices. Discrete Appl. Math. 151 (2005) 93–105.
• [13] Deville, Y., Barette, O., Van Hentenryck, P.: Constraint satisfaction over connected row-convex constraints. Artificial Intelligence 109(1-2) (1999) 243–271.
• [14] Herman, G.T., Kuba, A. (eds.) Advances in Discrete Tomography and its Applications. Birkh¨auser, Boston (2007)
• [15] Jarray, F., Tlig, G.: A simulated annealing for reconstructing hv-convex binary matrices. Electronic Notes in Discrete Math. 36 (2010) 447–454.
• [16] Kuba, A.: Reconstruction of two-directionally connected binary patterns from their two orthogonal projections. Computer Vision, Graphics, and Image Proc. 27 (1984) 249–265.
• [17] Latecki, L.J., Lakamper, R.: Convexity rule for shape decomposition based on discrete contour evolution. Comput. Vis. Image Und. 73(3) (1999) 441–454.
• [18] Nelson, M.R.: The Data Compression Book, M&T Books, Redwood City, CA (1991)
• [19] Ozsvár, Z., Balázs, P.: An empirical study of reconstructing hv-convex binary matrices from horizontal and vertical projections. Acta Cybern. 21(1) (2013) 149–163.
• [20] Rahtu, E., Salo, M., Heikkila J.: A new convexity measure based on a probabilistic interpretation of images. IEEE T. Pattern Anal. 28(9) (2006) 1501–1512.
• [21] Rosin, P.L., Zunic, J.: Probabilistic convexity measure. IET Image Process. 1(2) (2007) 182–188.
• [22] Ryser, H.J.: Combinatorial properties of matrices of zeros and ones. Canad. J. Math. 9 (1957) 371–377.
• [23] Sonka, M., Hlavac, V., Boyle, R.: Image Processing, Analysis, and Machine Vision 3rd ed. Thomson Learning, Toronto (2008)
• [24] Stern, H.: Polygonal entropy: a convexity measure. Pattern Recogn. Lett. 10 (1998) 229–235.
• [25] Tasi, T.S., Nyúl, L.G., Balázs, P.: Directional convexity measure for binary tomography. Lecture Notes in Comput. Sci. 8259 (2013) 9–16.
• [26] van Beek, P., Dechter R.: On the minimality and global consistency of row convex networks. J. ACM 42(3) (1995) 543–561.
• [27] Woeginger, G.J.: The reconstruction of polyominoes from their orthogonal projections. Inform. Process. Lett. 77 (2001) 225–229.
• [28] Zunic, J., Rosin, P.L.: A new convexity measure for polygons. IEEE T. Pattern Anal. 26(7) (2004) 923–934