<p>Digital topology, crucial for image analysis, tackles identifying connected components and holes in digital images using homology groups (Betti numbers). These invariants are essential in machine learning and biomedical image analysis, requiring accurate and efficient computation. This study introduces a novel algorithm for computing homology groups and Euler characteristics of 2D digital images. Using digital simplicial complexes and 8-adjacency, the method achieves computational efficiency, with a time complexity of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$O(k^{2.1})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>k</mi> <mrow> <mn>2.1</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, surpassing traditional persistent homology methods (<InlineEquation ID="IEq2"> <EquationSource Format="TEX">$O(n^3)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>3</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>). A significant contribution is the proof that higher-dimensional homology groups (<InlineEquation ID="IEq3"> <EquationSource Format="TEX">$H_n^8(X) = 0$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msubsup> <mi>H</mi> <mi>n</mi> <mn>8</mn> </msubsup> <mrow> <mo stretchy="false">(</mo> <mi>X</mi> <mo stretchy="false">)</mo> </mrow> <mo>=</mo> <mn>0</mn> </mrow> </math></EquationSource> </InlineEquation> for <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$n \ge 2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mo>≥</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>) vanish in 2D digital images, ensuring consistency with classical topology. Extensive evaluations confirmed the algorithm’s scalability with pixel density, accurately computing Betti numbers (<InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\beta _0$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>β</mi> <mn>0</mn> </msub> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\beta _1$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>β</mi> <mn>1</mn> </msub> </math></EquationSource> </InlineEquation>) and Euler characteristics, validated independently. The open-source tool (<Emphasis FontCategory="NonProportional">“DHGComp”</Emphasis>) supports applications in machine learning, biomedical image analysis, and computer vision, advancing digital topology methodologies.</p>

Efficient computation of homology groups, betti numbers, and euler characteristics for 2D digital images

期刊论文
发表日期：

2025年4月10日

查看全文

Ahmet Öztel,
Bayram Akgül,
İsmet Karaca,
Özgür Ege

摘要

Digital topology, crucial for image analysis, tackles identifying connected components and holes in digital images using homology groups (Betti numbers). These invariants are essential in machine learning and biomedical image analysis, requiring accurate and efficient computation. This study introduces a novel algorithm for computing homology groups and Euler characteristics of 2D digital images. Using digital simplicial complexes and 8-adjacency, the method achieves computational efficiency, with a time complexity of $O(k^{2.1})$ $O (k^{2.1})$ , surpassing traditional persistent homology methods ( $O(n^3)$ $O (n^{3})$ ). A significant contribution is the proof that higher-dimensional homology groups ( $H_n^8(X) = 0$ $H_{n}^{8} (X) = 0$ for $n \ge 2$ $n \geq 2$ ) vanish in 2D digital images, ensuring consistency with classical topology. Extensive evaluations confirmed the algorithm’s scalability with pixel density, accurately computing Betti numbers ( $\beta _0$ $β_{0}$ , $\beta _1$ $β_{1}$ ) and Euler characteristics, validated independently. The open-source tool (“DHGComp”) supports applications in machine learning, biomedical image analysis, and computer vision, advancing digital topology methodologies.