Finding the Optimal Bit-Quad Patterns for Computing the Euler Number of 2D Binary Images Using Simulated Annealing

Wilfrido Gómez-Flores; Humberto Sossa; Fernando Arce

doi:10.1007/978-3-030-77004-4_23

Finding the Optimal Bit-Quad Patterns for Computing the Euler Number of 2D Binary Images Using Simulated Annealing

Wilfrido Gómez-Flores, Humberto Sossa, Fernando Arce

Centro de Investigación en Computación (CIC)

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

This paper presents an automatic method for obtaining formulas to calculate the Euler number in 2D binary images. This problem is addressed as a combinatorial optimization problem, where specific bit-quad patterns are optimally combined. An algorithm based on simulated annealing is devised to find optimal expressions to compute the Euler number, considering 4- and 8-connectivity. The proposed approach found the complete family of expressions using three bit-quad patterns that correctly estimate the Euler number. Besides, another 58 new expressions are found that use more than three bit-quads. Hence, the proposed method can obtain automatically explainable formulas of the Euler number, and it can be potentially extended to other image representations.

Original language	English
Title of host publication	Pattern Recognition - 13th Mexican Conference, MCPR 2021, Proceedings
Editors	Edgar Roman-Rangel, Ángel Fernando Kuri-Morales, José Francisco Martínez-Trinidad, Jesús Ariel Carrasco-Ochoa, José Arturo Olvera-López
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	240-250
Number of pages	11
ISBN (Print)	9783030770037
DOIs	https://doi.org/10.1007/978-3-030-77004-4_23
State	Published - 2021
Event	13th Mexican Conference on Pattern Recognition, MCPR 2021 - Virtual, Online Duration: 23 Jun 2021 → 26 Jun 2021

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12725 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	13th Mexican Conference on Pattern Recognition, MCPR 2021
City	Virtual, Online
Period	23/06/21 → 26/06/21

Keywords

Bit-quad patterns
Combinatorial optimization
Euler number
Explainability
Simulated annealing

Access to Document

10.1007/978-3-030-77004-4_23

Cite this

Gómez-Flores, W., Sossa, H., & Arce, F. (2021). Finding the Optimal Bit-Quad Patterns for Computing the Euler Number of 2D Binary Images Using Simulated Annealing. In E. Roman-Rangel, Á. F. Kuri-Morales, J. F. Martínez-Trinidad, J. A. Carrasco-Ochoa, & J. A. Olvera-López (Eds.), Pattern Recognition - 13th Mexican Conference, MCPR 2021, Proceedings (pp. 240-250). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12725 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-77004-4_23

Gómez-Flores, Wilfrido ; Sossa, Humberto ; Arce, Fernando. / Finding the Optimal Bit-Quad Patterns for Computing the Euler Number of 2D Binary Images Using Simulated Annealing. Pattern Recognition - 13th Mexican Conference, MCPR 2021, Proceedings. editor / Edgar Roman-Rangel ; Ángel Fernando Kuri-Morales ; José Francisco Martínez-Trinidad ; Jesús Ariel Carrasco-Ochoa ; José Arturo Olvera-López. Springer Science and Business Media Deutschland GmbH, 2021. pp. 240-250 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{80a3602943414831b1f91382ccdd03c0,

title = "Finding the Optimal Bit-Quad Patterns for Computing the Euler Number of 2D Binary Images Using Simulated Annealing",

abstract = "This paper presents an automatic method for obtaining formulas to calculate the Euler number in 2D binary images. This problem is addressed as a combinatorial optimization problem, where specific bit-quad patterns are optimally combined. An algorithm based on simulated annealing is devised to find optimal expressions to compute the Euler number, considering 4- and 8-connectivity. The proposed approach found the complete family of expressions using three bit-quad patterns that correctly estimate the Euler number. Besides, another 58 new expressions are found that use more than three bit-quads. Hence, the proposed method can obtain automatically explainable formulas of the Euler number, and it can be potentially extended to other image representations.",

keywords = "Bit-quad patterns, Combinatorial optimization, Euler number, Explainability, Simulated annealing",

author = "Wilfrido G{\'o}mez-Flores and Humberto Sossa and Fernando Arce",

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 13th Mexican Conference on Pattern Recognition, MCPR 2021 ; Conference date: 23-06-2021 Through 26-06-2021",

year = "2021",

doi = "10.1007/978-3-030-77004-4_23",

language = "Ingl{\'e}s",

isbn = "9783030770037",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "240--250",

editor = "Edgar Roman-Rangel and Kuri-Morales, {{\'A}ngel Fernando} and { Mart{\'i}nez-Trinidad}, {Jos{\'e} Francisco} and Carrasco-Ochoa, {Jes{\'u}s Ariel} and { Olvera-L{\'o}pez}, {Jos{\'e} Arturo}",

booktitle = "Pattern Recognition - 13th Mexican Conference, MCPR 2021, Proceedings",

address = "Alemania",

}

Gómez-Flores, W, Sossa, H & Arce, F 2021, Finding the Optimal Bit-Quad Patterns for Computing the Euler Number of 2D Binary Images Using Simulated Annealing. in E Roman-Rangel, ÁF Kuri-Morales, JF Martínez-Trinidad, JA Carrasco-Ochoa & JA Olvera-López (eds), Pattern Recognition - 13th Mexican Conference, MCPR 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12725 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 240-250, 13th Mexican Conference on Pattern Recognition, MCPR 2021, Virtual, Online, 23/06/21. https://doi.org/10.1007/978-3-030-77004-4_23

Finding the Optimal Bit-Quad Patterns for Computing the Euler Number of 2D Binary Images Using Simulated Annealing. / Gómez-Flores, Wilfrido; Sossa, Humberto; Arce, Fernando.
Pattern Recognition - 13th Mexican Conference, MCPR 2021, Proceedings. ed. / Edgar Roman-Rangel; Ángel Fernando Kuri-Morales; José Francisco Martínez-Trinidad; Jesús Ariel Carrasco-Ochoa; José Arturo Olvera-López. Springer Science and Business Media Deutschland GmbH, 2021. p. 240-250 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12725 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Finding the Optimal Bit-Quad Patterns for Computing the Euler Number of 2D Binary Images Using Simulated Annealing

AU - Gómez-Flores, Wilfrido

AU - Sossa, Humberto

AU - Arce, Fernando

PY - 2021

Y1 - 2021

N2 - This paper presents an automatic method for obtaining formulas to calculate the Euler number in 2D binary images. This problem is addressed as a combinatorial optimization problem, where specific bit-quad patterns are optimally combined. An algorithm based on simulated annealing is devised to find optimal expressions to compute the Euler number, considering 4- and 8-connectivity. The proposed approach found the complete family of expressions using three bit-quad patterns that correctly estimate the Euler number. Besides, another 58 new expressions are found that use more than three bit-quads. Hence, the proposed method can obtain automatically explainable formulas of the Euler number, and it can be potentially extended to other image representations.

AB - This paper presents an automatic method for obtaining formulas to calculate the Euler number in 2D binary images. This problem is addressed as a combinatorial optimization problem, where specific bit-quad patterns are optimally combined. An algorithm based on simulated annealing is devised to find optimal expressions to compute the Euler number, considering 4- and 8-connectivity. The proposed approach found the complete family of expressions using three bit-quad patterns that correctly estimate the Euler number. Besides, another 58 new expressions are found that use more than three bit-quads. Hence, the proposed method can obtain automatically explainable formulas of the Euler number, and it can be potentially extended to other image representations.

KW - Bit-quad patterns

KW - Combinatorial optimization

KW - Euler number

KW - Explainability

KW - Simulated annealing

UR - http://www.scopus.com/inward/record.url?scp=85111370180&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-77004-4_23

DO - 10.1007/978-3-030-77004-4_23

M3 - Contribución a la conferencia

AN - SCOPUS:85111370180

SN - 9783030770037

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 240

EP - 250

BT - Pattern Recognition - 13th Mexican Conference, MCPR 2021, Proceedings

A2 - Roman-Rangel, Edgar

A2 - Kuri-Morales, Ángel Fernando

A2 - Martínez-Trinidad, José Francisco

A2 - Carrasco-Ochoa, Jesús Ariel

A2 - Olvera-López, José Arturo

PB - Springer Science and Business Media Deutschland GmbH

T2 - 13th Mexican Conference on Pattern Recognition, MCPR 2021

Y2 - 23 June 2021 through 26 June 2021

ER -

Gómez-Flores W, Sossa H, Arce F. Finding the Optimal Bit-Quad Patterns for Computing the Euler Number of 2D Binary Images Using Simulated Annealing. In Roman-Rangel E, Kuri-Morales ÁF, Martínez-Trinidad JF, Carrasco-Ochoa JA, Olvera-López JA, editors, Pattern Recognition - 13th Mexican Conference, MCPR 2021, Proceedings. Springer Science and Business Media Deutschland GmbH. 2021. p. 240-250. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-77004-4_23

Finding the Optimal Bit-Quad Patterns for Computing the Euler Number of 2D Binary Images Using Simulated Annealing

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this