论文部分内容阅读
距离变换是计算图像中每个点到最近的特征点的距离,将原本无意义的孤立的特征点表示为特征点与背景点的距离关系。距离变换对图像作出了更为丰富的表达,后续方法可以根据需要在这个结果基础上进行处理。距离变换是一种重要的基础工具,在计算机视觉,计算机图形学,形状分析,模式识别和计算几何等方面都有着重要的应用。然而,由于距离变换的计算的非常复杂,往往成为整个分析方法性能的瓶颈。随着人们对这一问题认识的深入,不断有新的方法提出,距离变换算法的效率不断提高。尽管目前的欧几里德距离变换方法已经达到了线性时间复杂度(与图像中的像素数成线性),但是系数项仍旧较大。本文通过对距离变换算法的研究,提高算法效率,能够提高相关领域此类问题计算性能,对多个科学分支的研究带来帮助,同时,距离变换的研究仅限于到最近邻特征点的距离,但在实际应用中,k近邻概念有着更为广泛的意义,放之距离变换也是如此。 首先,本文提出了一种高效的二维二值图像的距离变换算法。二维二值图像的距离变换是研究最多和最为透彻的,也是后续各种变体的基础。所提出方法采用了直接计算中垂线与行或者列的交叉点的算法,实现了更为高效的实现。与之前提出的最为先进的算法相比,所提出的方法是目前效率最高的算法。 其次,本文提出了一种高效的高维二值图像的距离变换算法。在前述高效二维距离变换算法的基础上,这里给出一个统一的计算多维度二值图像的算法。通过与之前最为先进的多维距离变换算法比较,这里所提出的方法具有较大的速度优势。 第三,本文提出来一种二维二值图像的高阶距离变换算法。如果把基于最近邻的基础的距离变换视为一阶距离变换,那么k阶距离变换就是计算每个点到其k近邻特征点的距离的算法。在所提出的二维二值图像距离变换算法中所用到的中垂线交叉点计算方法基础上,给出一个基于独立扫描的高阶距离变换算法。 最后,本文提出了一种通用的距离变换算法GEDT(Generalized Exact Eu-clidean Distance Transform)。该方法能够计算任意维度的二值图像的任意阶次的距离变换,算法的计算复杂度为O(dNk2)(N为图像中的像素点数目,k是阶数,d是图像的维度)。 本文对距离变换算法进行了的全面改进,扩展了距离变换的定义,完善了距离变换的概念。这一系列改进将对相关领域的研究提供有力的支持。本文还给出了二维距离变换在手指静脉身份识别中的应用和k阶距离变换在Hausdorff距离计算中的应用。这些应用表明,高效距离变换算法能够有效地提高相关研究的方法的效率。