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

Abstract

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(k2.1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(k<^>{2.1})$$\end{document}, surpassing traditional persistent homology methods (O(n3)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n<^>3)$$\end{document}). A significant contribution is the proof that higher-dimensional homology groups (Hn8(X)=0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$H_n<^>8(X) = 0$$\end{document} for n >= 2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n \ge 2$$\end{document}) 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\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta _0$$\end{document}, beta 1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\beta _1$$\end{document}) 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.