Eliminating Switching Components in Binary Matrices by 0-1 Flips and Column Permutations

• Autorzy: Hantos N. , Balázs P.

Identyfikatory

DOI

10.3233/FI-2015-1268

• Języki publikacji: EN

Abstrakty

EN

Analysis of patterns in binary matrices plays a vital role in numerous applications of computer science. One of the most essential patterns of such matrices are the so called switching components, where the number and location of the components gives valuable information about the binary matrix. One way to measure the effect of switching components in a binary matrix is counting the number of 0-s which have to be replaced with 1-s in order to eliminate the switching components. However, finding the minimal number of 0-1 flips is generally an NP-complete problem. We present two novel-type heuristics for the above problem and show via experiments that they outperform the formerly proposed ones, both in optimality and in running time. We also show how to use those heuristics for determining the so-called nestedness level of a matrix, and how to use the flips for binary image compression.

Słowa kluczowe

EN

binary matrix; image reconstruction; switching component; uniqueness; 0-1 flip; nestedness; data compression

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

Twórcy

autor

Hantos N.

• Department of Algorithms And Their Applications, Faculty of Informatics Eötvös Loránd University Pázmány Péter sétány 1/C, H-1117, Budapest, Hungary

autor

Balázs P.

• Department of Image Processing and Computer Graphics University of Szeged Árpád tér 2. H-6720, Szeged, Hungary

Bibliografia

• [1] M.R. Berthold, C. Borgelt, F. Höppner, F. Klawonn, Guide to Intelligent Data Analysis, Springer, 2010.
• [2] S.K. Chang, The reconstruction of binary patterns from their projections, Comm. ACM 14 (1971) 21-25.
• [3] R.C. Gonzalez, R.E. Woods, Digital Image Processing (3rd Edition), Prentice Hall, 2008.
• [4] N. Hantos, P. Balázs, Fast heuristics for eliminating switching components in binary matrices by 0-1 flips, Proceedings of the Iberoamerican Congress on Pattern Recognition CIARP 2014, Lecture Notes in Computer Science 8827 (2014) 62–69.
• [5] G.T. Herman, A. Kuba (Eds.), Advances in Discrete Tomography and its Applications, Birkh¨auser, Boston, 2007.
• [6] H. Mannila, E. Terzi, Nestedness and segmented nestedness, KDD ’07 Proceedings of the 13th ACM SIGKDD international conference on knowledge discovery and data mining (2007) 480–489.
• [7] T.M. Mitchell, Machine Learning, McGraw Hill, 1997.
• [8] H.J. Ryser, Combinatorial properties of matrices of zeros and ones, Canad. J. Math. 9 (1957) 371–377.
• [9] J. Serra, Image Analysis and Mathematical Morphology, Academic Press, New York, 1982.
• [10] X. Wu, V. Kumar (Eds.), The Top Ten Algorithms in Data Mining, Chapman & Hall/CRC, 2007