图像欧拉数计算的快速化研究

The Euler number is one of the most important topological property in an image. It is very robust because it does not change when the image is stretched, flexed, rotated or irregular deformed. The Euler number has been used in fields of image understanding, pattern recognition and computer vision widely. In many real-time image processing systems, it is necessary to extract basic shape features of objects in images as faster as possible in order to get more time for complicated object recognition processing. In our project, we aim to obtain more efficient Euler number computing algorithms for 2D and 3D images. Firstly, we analyze the factors which will influence the efficiency of Euler number computing algorithms and improve the efficiency of bit-quad-based algorithms as much as possible by use of state transition and multi-row scanning methods. Then, we will propose a novel Euler number computing algorithm by use of the Euler formula in graph theory to reduce the number of bit-quad patterns to be counted in current Euler number computing algorithms for 2D images. Lastly, we will extend our proposed methods for improving the computation of the Euler number of a 2D image to compute the Euler number of a 3D image and propose a more efficient Euler number computing algorithm for 3D images based on the unique characteristics of 3D images. By the achievements of our project, the efficiency of Euler number computing for 2D and 3D images will be improved greatly. Our research will provide a stronger technical support for real-time image processing systems and make some academic contributions to image pattern recognition and computer vision.

图像欧拉数是图像的重要拓扑特征之一，因其在图像发生拉伸、收缩、旋转及不规则弹性形变时保持不变，有很强的鲁棒性，故被广泛应用于图像理解与模式识别、计算机视觉等领域。在实时图像处理系统中，图像特征提取越快，就能有越多的时间对目标进行更全面的识别处理。本项目将开展图像欧拉数计算的快速化研究。首先将深入分析现有二维图像欧拉数算法中影响计算效率的因素，利用状态转换和多行扫描的方法尽量减少对像素的重复检查，达到提高计算效率的目的；然后应用图论中的欧拉公式减少现有二维图像欧拉数算法中需要统计的四方块模式，提出基于图论的新算法并加以优化；最后，将提高二维图像欧拉数算法效率的方法扩展应用到三维图像欧拉数计算中，并针对三维图像独有的特点提出提高效率的新方法。旨在实现二维和三维图像欧拉数的快速计算。本项目的研究成果将为实时图像处理系统提供更为有力的技术支持，为图像模式识别和计算机视觉的学术发展作出相应的贡献。

图像欧拉数是图像的重要拓扑特征之一，因其在图像发生拉伸、收缩、旋转及不规则弹性形变时保持不变，有很强的鲁棒性，故被广泛应用于图像理解与模式识别、计算机视觉等领域。本项目针对图像欧拉数的快速计算进行研究。本项目提出了状态转换和多行扫描的有效策略，分别从水平和垂直两个方向减少图像欧拉数计算过程中像素的重复检查。理论上说，一次扫描的行数越多，处理一个四方块需要检查的像素平均数量就越少；与此同时，一次扫描的行数越多，处理过程需要考虑的状态数也随之增多，算法也就越复杂，实现起来效率就会随之降低，本项目探究了一次扫描的最大行数与算法复杂度之间的平衡性，通过实验验证了一次扫描的最佳行数，得到了高效的基于四方块统计的二维图像欧拉数算法。本项目提出了基于图论的8-邻接图像欧拉数算法并加以优化。针对直接统计与给定图像对应图形中的结点、边和基本面数量效率较低的实际情况，将统计图形中的结点、边和基本面数量的过程转换为处理图像中的四方块，分析每一种四方块对图像欧拉数的增量，找出对图像欧拉数真正有影响的四方块类型，同时利用状态转换和多行扫描方法减少对像素的重复检查，得到高效的基于图论的8-邻接二维图像欧拉数算法。本项目将提高二维图像欧拉数算法效率的有效策略扩展应用到三维图像欧拉数计算中，针对现有三维图像欧拉数算法的特点，通过改变处理图像中三维立方体模式时的像素扫描顺序及合并部分三维立方体模式，减少现有算法中处理一个三维立方体模式所需要检查的像素数量，提出提高三维图像欧拉数计算效率的新方法。在本项目的资助下，项目组发表论文13篇，授权发明专利3件、软件著作权4件，培养硕士研究生3名。本项目的研究成果将为实时图像处理系统提供更为有力的技术支持，为图像模式识别和计算机视觉的学术发展作出相应的贡献。