A new run-based algorithm for Euler number computing

详细信息    查看全文

• 作者：Bin Yao ; Lifeng He ; Shiying kang ; Xiao Zhao…
• 关键词：Euler number ; Topological feature ; Pattern recognition ; Image processing
• 刊名：Pattern Analysis and Applications
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：20
• 期：1
• 页码：49-58
• 全文大小：
• 刊物类别：Computer Science
• 刊物主题：Pattern Recognition;
• 出版者：Springer London
• ISSN：1433-755X
• 卷排序：20

文摘

The Euler number of a binary image is an important topological feature for many image processing, image analysis, pattern recognition, and computer vision applications. This paper proposes a new run-based Euler number computation algorithm. The conventional run-based algorithm processes rows of the given image one-by-one from top to bottom in a single phase. For each row, it finds the runs in the row and records the start and end locations of each run to compute neighbor runs. In contrast, our algorithm calculates the Euler number of an image in two phases. In the first phase, we process odd rows alternately to find runs and only record its end location. In the second phase, we process each of the remaining even rows to find runs and calculate neighboring runs between the current row and the rows immediately above and below using the recorded run data. Using this method, the number of accesses required to compute the Euler number decreases in almost all cases. Analysis of the time complexity and experimental results demonstrate that our algorithm outperforms conventional Euler number computation algorithms.