GCT变换及几何图形形状相似性判定

目的 人类的视觉能力可以轻易地判定两个几何图形形状的相似性,但是,这对于计算机来说仍是一个开问题。在计算机视觉应用中,不仅需要对图形形状进行分类和相似性判定,还需要对图形形状的相似性度量给出与人类的视觉判断一致的结果,这是目前图形形状表示和分类算法没有较好解决的问题。方法 通过GCT变换,将图形形状从实数空间的坐标表示变换到复数空间的复数特征向量表示,进而将判定两个几何形状的相似性问题转化为判定它们的复数空间特征向量的相似性问题。GCT变换不仅可以判定图形形状的相似性,它还是可逆的,它可以近似重建原图形形状。结果 GCT变换具有位移、尺度和旋转不变性,它不仅可以判定几何图形形状的相似性,给出与人类视觉判断一致的相似性结果,而且在两个几何图形形状相似的情况下,还能计算出它们的角度旋转和尺度缩放。结论 对于封闭的几何形状,如果几何形状的中心点位于几何形状的内部且过中心点的任一直线与该几何形状有且只有两个交点,理论证明和实验验证,GCT变换可以高效准确地判定这类几何图形形状的相似性,并给出与人类视觉判定一致的结果。     

非均匀有理B样条曲线优化匹配组合

目的 为了解决从曲线库(轮廓线集合)中筛选出与期望曲线相匹配的相似曲线段问题,研究基于Kabsch算法的NURBS(非均匀有理B样条)曲线优化匹配组合方法。方法 首先提出一种基于Kabsch算法的曲线相似性判断方法,针对两条NURBS曲线上相同个数点阵,经最优旋转和平移变换得到其最小均方根偏差,进而依据基于最小均方根偏差和相似度指标判断曲线相似性;在此基础上,提出一种类似二分查找法的曲线优化匹配组合方法,对于给定相似度和最小搜索步长,通过曲线分割和相似性判断得到期望曲线分割段数最少的相似组合曲线。结果 给定一条期望的3D曲线,在相似度为0.025和最小搜索步长为0.05情况下,采用所提方法从包含4条3D曲线的曲线库中依次筛选出10段基元构建相似组合曲线。结论 提出了一种新的NURBS曲线优化匹配组合方法,实验结果表明,对不同期望曲线能高效稳定构建相对应的相似组合曲线,适用于类似碎片拼接重构问题。     

结合轮廓与形状特征的仿射形状匹配

目的 针对仿射变换下形状匹配中存在的描述子对形状的描述能力不足,以及描述子计算耗时大的问题,改进基于所有图像点投影的方法,提出一种利用轮廓计算投影面积的仿射形状匹配算法。方法 该算法分为粗匹配和精匹配两个阶段。粗匹配阶段以CSS角点作为备选特征点,首先统计轮廓投影面积分布作为特征点描述子;然后利用动态规划蚁群算法匹配两幅图片公共特征点序列,并将匹配好的特征点序列记为对应的新特征点;最后采用该新特征点划分目标曲线,得到对应的轮廓曲线;这一阶段的目的是对形状的筛选以及寻找一致的轮廓特征点,同时完成轮廓曲线的划分。精匹配阶段,采用小波仿射不变描述子,对粗匹配阶段匹配代价最小的5%的目标进行对应曲线匹配,得到精匹配阶段的匹配代价,从而实现对仿射目标的识别;精匹配弥补了描述子对轮廓细节描述不足的问题。结果 算法的平均检索速度比传统基于形状投影分布描述子提高44.3%,在MPEG-7图像库上的检索效果为98.65%,在MPEG-7仿射图像库上的查准率与查全率综合评价指标比传统的基于形状投影分布描述子高3.1%,比形状上下文高25%。结论 本文算法匹配效果好,效率高,抗噪性强,解决了仿射描述子计算速度慢、描述能力不足的问题,能有效地应用于仿射形状匹配与检索领域。     

角点距离矩阵和同心圆划分的曲线描述与匹配

曲线匹配对于物体识别、目标跟踪、碎片拼接等有着重要的意义。针对曲线匹配的效率与鲁棒性问题,提出了一种基于角点距离矩阵和同心圆划分的曲线描述与匹配算法。该算法分为粗略匹配和精确匹配两个阶段。粗略匹配阶段首先采用角点距离矩阵来描述曲线;然后通过子矩阵的方法来匹配曲线。精确匹配阶段首先采用同心圆划分的方法描述曲线;然后通过两条曲线同心圆描述集的差异度度量函数来度量他们的相似性。算法不仅具有平移、旋转、缩放不变性,而且具有较强的鲁棒性,可用于遮挡物体的匹配以及基于轮廓的图形拼接。实验结果表明了该算法的有效性和可行性。     

基于局部模型匹配的几何活动轮廓跟踪

目的 在复杂背景下,传统轮廓跟踪方法只考虑了目标的整体特征或显著性特征,没有充分利用目标的局部特征信息,尤其是目标发生遮挡时,容易发生跟踪漂移,甚至丢失目标.针对上述问题,提出一种基于局部模型匹配的几何活动轮廓(LM-GAC)跟踪算法.方法 首先,利用超像素技术将图像中的颜色特征相似的像素点归为一类,形成由一些像素点组成的超像素,从而把目标分割成若干个超像素块,再结合EMD(earth mover's distance)相似性度量构建局部特征模型.然后,进行局部模型匹配,引入噪声模型来估算局部模型参数θ,这样可以增强特征模型的自适应性,提高局部模型匹配的准确性.最后,结合粒子滤波的水平集分割方法提取目标轮廓,实现目标轮廓精确跟踪.结果 本文算法与多种目标轮廓跟踪算法进行对比,在部分遮挡、目标形变、光照变化、复杂背景等条件的基准图像序列均具有较高的跟踪成功率,平均成功率为79.6%.结论 实验结果表明,根据不同的图像序列,可以自适应地实时改变噪声模型参数和粒子的权重,使得本文算法具有较高的准确性和鲁棒性.特别是在复杂的背景下,算法能较准确地进行目标轮廓跟踪.     

特征点聚类高精度视差图像拼接

目的 针对不同视点下具有视差的待拼接图像中,特征点筛选存在漏检率高和配准精度低的问题,提出了一种基于特征点平面相似性聚类的图像拼接算法。方法 根据相同平面特征点符合同一变换的特点,计算特征点间的相似性度量,利用凝聚层次聚类把特征点划分为不同平面,筛选误匹配点。将图像划分为相等大小的网格,利用特征点与网格平面信息计算每个特征点的权重,通过带权重线性变换计算网格的局部单应变换矩阵。最后利用多频率融合方法融合配准图像。结果 在20个不同场景图像数据上进行特征点筛选比较实验,随机抽样一致性（random sample consensus, RANSAC）算法的平均误筛选个数为30,平均误匹配个数为8,而本文方法的平均误筛选个数为3,平均误匹配个数为2。对20个不同场景的多视角图像,本文方法与AutoStitch（automatic stitching）、APAP（as projective as possible）和AANAP（adaptive as-natural-as-possible）等3种算法进行了图像拼接比较实验,本文算法相比性能第2的算法,峰值信噪比（peak signal to noise ratio,PSNR）平均提高了8.7%,结构相似性（structural similarity,SSIM）平均提高了9.6%。结论 由本文提出的基于特征点平面相似性聚类的图像拼接算法处理后的图像保留了更多的特征点,因此提高了配准精度,能够取得更好的拼接效果。     

空时形状预测与高效编码

目的 形状是视觉对象的关键特征,形状编码是对象基图像和视频处理中的关键技术,但现有无损形状编码方法压缩效率普遍不高.为此,提出一种基于链码表示和空时预测的高效无损形状编码新算法.方法 首先逐帧提取视觉对象的形状轮廓并转化为链码表示;然后基于对象轮廓的帧间活动性将形状视频序列分成帧内预测编码帧和帧间预测编码帧,并基于轮廓链码的空域相关性和时域相关性对二者分别进行空域和时域补偿与预测;最后基于链码的方向约束特性对预测后的位移矢量和预测残差进行高效编码压缩.结果 为了检验所提算法的性能,基于MPEG-4标准形状测试序列进行了编码实验测试.与现有主要方法相比本文算法能提高压缩效率6%到71.6%不等.结论 本文算法可广泛应用于对象基编码、基于内容的图像检索、图像分析与理解等领域.     

形状的圆内距离变换

目的 形状的描述、匹配、相似性判定和检索是计算机视觉和图像识别的基本问题,也是一个开问题。在目前公开的方法中,除了只能应用于简单形状的几何复变换和基于边界的傅里叶描述子外,其他的方法均不能由构建的形状特征描述符重建原形状,因此不能保证所建立的形状特征能客观地描述原形状。本文提出了形状的圆内距离变换,该方法所建立的描述符可用于形状匹配、相似性度量和形状检索。该方法是可逆的,也就是可以从形状描述符重建原形状。方法 形状的圆内距离变换通过在形状的最小外接圆内旋转和切分形状,求出形状相邻切分点之间的距离,并由此构建形状的特征矩阵。对于任意相似的形状,从理论上证明了形状的圆内距离变换具有缩放、旋转和位移不变性。结果 对发生了形变、扭曲和仿射变换的形状,采用圆内距离变换方法进行了形状的相似性度量、检索和重建实验,结果表明,形状的圆内距离变换可以准确地描述形状、度量形状的相似性、检索形状并重建原形状。在形状的相似性度量上,形状的圆内距离变换能给出与人类视觉一致的结果,并且当两个形状相似时,还能计算出它们的尺度缩放和角度旋转。通过与经典的方法,包括形状上下文方法、傅里叶描述子方法、拉东柱状图方法,针对典型的MPEG-7形状库进行对比实验,发现形状的圆内距离变换在形状检索的综合得分上相比这些经典方法提高了近20%。结论 形状的圆内距离变换在形状的描述、相似性判定和检索上是有效和可逆的,具有广泛的可适用性且优于本文比较的其他经典方法。     

一类完备正交函数系下的轮廓曲线匹配算法

轮廓曲线包含了图像中大量的关键信息,主要用于探讨基于轮廓曲线的图像匹配问题.在假定图像间具有相似关系的前提下,借助于一种完备正交函数系V系统,提出一种新的曲线匹配算法.首先由V描述子评估曲线间的相似度,以此确定匹配曲线段,然后求得曲线间的变换参数,最后进行了图像拼接测试.该算法着眼于轮廓线的整体特征且不需要提取曲线的局部特征,避免了特征选取这一难点.大量的模拟及真实图像实验结果表明,从图像中提取的2条曲线间即使不严格满足相似变换关系,依然可取得比较满意的结果,从而验证了文中算法的可行性.     

基于图像特征的植物形态相似度算法

目的 研究不同植物形态之间的相似度是有效区分植物种类或科属的一个重要依据。目前的植物形态相似度计算方法,大多只考虑了植物拓扑结构或者外围轮廓等几何形状方面的相似性,而未涉及叶片颜色、冠层叶片的稠密状态及株型的松散状态等因素。因此,基于植物图像的形状特征和颜色特征,本文提出一种基于图像特征的植物形态相似度计算方法。方法 首先,获取图像的轮廓特征和区域特征。轮廓特征用植物枝条的松散程度表示,具体包括植物的高宽比、轮廓四边形和第1个1级侧枝的高度;区域特征用叶片稠密度表示,计算叶片所占整个包围矩形面积的比例。其次,获取图像的颜色特征,使用基于HSV和YUV颜色空间的颜色直方图,统计图像的颜色分布。最后,利用信息熵分析数据的离散程度,据此确定各部分对应的权重大小,加权得到总体的相似度值。结果 实验在人工采集的数据集上进行,得出松散度、稠密度和颜色对应的权重分别为0.62、0.17和0.21。在此基础上得到的相似度计算结果符合实际,可以有效度量植物之间的相似程度。同时,将提出的算法应用于图像检索,并与常见的5种方法进行比较。实验得出该算法查准率都在0.747 7以上。在同一查准率水平下,相比于其他方法,查全率也都处于较高水平。尤其在相似度阈值大于0.8时,查准率可以达到0.910 8以上。另外,该方法对植物图像缩放不敏感,同类植物的相似度依然接近于1。结论 本文提出的植物形态相似度算法,结合了形状特征和颜色特征,计算结果符合人的视觉感受。与其他方法相比,可以更有效区分植物种类或科属。算法主要适用于背景单一的单株植物图像,可为研究植物形态的相似性提供技术参考。     

基于曲率匹配的细胞几何形状特征提取方法

细胞轮廓的几何形状是细胞学涂片判读的重要参考,对研究宫颈病变的计算机辅助诊断具有重要意义。针对现有基于形状模板匹配的几何形状识别方法鲁棒性较差的问题,提出了基于曲率匹配的几何形状特征提取方法,通过比较模板轮廓和待识别轮廓的曲率,计算曲率曲线之间的相似度,进而得到细胞轮廓的形状特征,并采用依次旋转轮廓选取最佳匹配的方法来解决轮廓方向不一致的问题,采用以面积等效圆的半径比作为放大比率进行轮廓缩放的方法来解决轮廓大小不一致的问题。通过相关实验证明了该方法所提取的几何形状特征具有尺度不变性和旋转不变性,并与改进Hausdorff距离进行了实验对比,结果表明提取的形状特征能更加准确地识别出细胞轮廓的几何形状。     

基于特征点和最小面积的曲线描述和匹配

为了对关键特征点相同而子曲线曲率不同的曲线进行识别,提出一种新的平面曲线的描述和匹配方法。基于关键特征点进行粗匹配,根据精度要求设定最小面积阈值在子曲线上重新采样点,定义了一种新的采样点的识别向量,并根据子曲线上采样点的识别向量构造了新的识别向量矩阵,最后根据识别向量矩阵的差异度度量子曲线的相似性。通过对所有子曲线的识别实现对整条曲线的识别。该识别方法逐层筛选、由粗到精,避免了冗余操作。实验表明该方法高效、可行。     

Curve Matching,Time Warping,and Light Fields: New Algorithms for Computing Similarity between Curves

The problem of curve matching appears in many application domains, like time series analysis, shape matching, speech recognition, and signature verification, among others. Curve matching has been studied extensively by computational geometers, and many measures of similarity have been examined, among them being the Fréchet distance (sometimes referred in folklore as the “dog-man” distance). A measure that is very closely related to the Fréchet distance but has never been studied in a geometric context is the Dynamic Time Warping measure (DTW), first used in the context of speech recognition. This measure is ubiquitous across different domains, a surprising fact because notions of similarity usually vary significantly depending on the application. However, this measure suffers from some drawbacks, most importantly the fact that it is defined between sequences of points rather than curves. Thus, the way in which a curve is sampled to yield such a sequence can dramatically affect the quality of the result. Some attempts have been made to generalize the DTW to continuous domains, but the resulting algorithms have exponential complexity. In this paper we propose similarity measures that attempt to capture the “spirit” of dynamic time warping while being defined over continuous domains, and present efficient algorithms for computing them. Our formulation leads to a very interesting connection with finding short paths in a combinatorial manifold defined on the input chains, and in a deeper sense relates to the way light travels in a medium of variable refractivity. Alon Efrat earned his Bachelor in Applied Mathematics from the Technion, Israel’s Institute of Technology in 1991, earned his Master in Computer Science from the Technion in 1993, and his Ph.D. in Computer Science from Tel-Aviv University in 1998. During the years 1998–2000 he was a Post Doctorate Research Assistant at the Computer Science Department at Stanford University, and at IBM Almaden Research Center. Since 2000, he is an assistant Professor at the Computer Science Department at the University of Arizona. His main research areas are Computational Geometry, and its applications. Quanfu Fan is a Ph.D. student in the department of Computer Science at the University of Arizona. His research interests include object recognition and image understanding, information retrieval, and geometric algorithms.     

基于粒子群算法的三维CAD模型相似性计算

为了更加准确地度量两个模型之间的形状差异,提出了一种基于粒子群的模型相似性计算方法。利用面的组成边数来构造面相似度矩阵,通过粒子群算法对该矩阵进行搜索,得到了两个模型之间的最优面匹配序列。根据这个最优面匹配序列,从面相似度矩阵中提取对应的面相似性值。通过累积面之间的相似性来计算模型之间的整体相似性。以此为基础来度量模型之间的差异。实验结果表明：该方法能够准确地度量两个模型之间的相似程度。     

基于直线和二次曲线的多回路平面曲线分割

提出了一种多回路平面曲线的分割算法。算法以直线段和二次曲线段作为拟合的基本单元，通过边缘跟踪把多回路的平面曲线分割成曲线段或单回路的封闭曲线，然后在曲线曲率不连续处继续分割。针对一次分割时可能会产生的迷向问题，提出了基于对偶原理的线段合并技术。该算法的结果能简单有效地描述场景中的物体，使高级视觉任务更简单。实验结果表明算法能取得较好的效果。     

基于高光谱非线性向量空间的光谱曲线特征差异性分析

地物光谱特征分析是对地物进行分类和匹配的基础,目前高光谱遥感技术应用在精细物种识别中主要采用波谱分析的方法。重点探索非线性空间里的相似性测度方法,由于光谱曲线表征复杂光谱成像的非线性过程,论文从空间目标的整体形状描述非空集合之间的差异,采用Fr′echet距离、Hausdorff距离、Euclidian距离分别定义光谱特征曲线的距离,设计算法测量光谱向量之间的非线性相似程度。结果表明,采用Fr′echet距离、Hausdorff距离、Euclidian距离度量光谱相似度的精度依次减弱,但依据Fr′echet距离的算法时间复杂度略高。基于Fréchet距离的方法充分考虑了曲线上点的位置信息及整体曲线的走势问题,其在精度、抗噪能力等方面均有提升,从而为分析光谱特征提供了可能的新途径。     

一种基于拱高半径复变函数的面实体匹配算法

针对面实体匹配问题进行了研究。面实体的边界线在某点的拱高正是对边界线在该点的弯曲程度和凸凹性的反映,该点的中心距离又可以对面实体形状的整体进行描述,通过边界线上某点的中心距离和拱高组成复数,并对其进行快速傅里叶变换可以获取傅里叶形状描述子,作为对面实体形状相似度的度量。将面实体的空间位置、形状、大小等相似度通过加权综合,获得了一种综合空间相似度度量模型,利用此模型对面实体进行匹配。实验结果表明,算法能够有效地进行面实体的匹配。     

基于NRLCTI码和匹配子曲线的平面曲线识别

为了更简单、有效地进行平面曲线的识别,首次给出了一种新的NRLCTI码的定义,并设计了一种新的算法用来匹配目标和模型轮廓曲线上的每段子曲线,同时还提出了一种从单幅图形和图像来识别平面曲线的方法。该识别方法首先利用NRLCTI码初步匹配了目标和模型轮廓曲线上的关键特征点,从而解决了用穷尽搜索法寻求特征点所对应的高费率和低效率的问题;然后在NRLCTI码匹配的前提下,再通过匹配目标和模型轮廓曲线上的每小段,从而解决了用多边形或圆锥曲线来近似曲线的不准确性问题。实验结果表明,该算法简单、有效。