java 匹配线路 优先级如何实现 线路匹配算法

admin2024-06-05  8

1. 匹配算法

以第4节第二个结果为例:

Model中的直线段:          

M={A,B,C,D}                             

待匹配图像中提取的直线段集合Data:

D={0,,1,2,3,4,5,6,7,8,9,10,11,12}

将二者两两线段间所以可能的匹配方式放入集合S:

S={(A,0)(A,1)...(A,12)(B,0)(B,1)...(B,12)...(D,12)}

利用幂集的概念,将两幅图像之间所有可能的匹配图放入幂集C中。

C={

     {(A,0)},{(A,0)(A,1)}...{(A,0)(A,1)(A,12)(B,0)(B,1)...(B,12)...(D,12)}

     }

C的元素有h=2exp(4*13)个,也就是说在多对多(many-to-many)的情况下,有h中匹配的可能性。现在有两种寻找最优匹配的方法:全局最优和局部最优

1. 1局部最优匹配算法(邻域法)


用海明距离(Hamming-distance-one)表示邻域,0表示为匹配,1表示匹配(图中黑点)。在C中选取某一个匹配图作为初始状态。


如下图中的Map={ (A,0), (A,3), (A,7), (B,2), (B,8), (C,3), (C,4), (C,7), (C,8), (C,9), (C,10), (C,11), (C,12), (D,0), (D,1), (D,3), (D,4), (D,10) }


Hamming-distance-one表示的匹配图可以表示为[1001000100000  0010000010000  0001100111111  1101100000100]


其邻域表示与初始状态仅仅差一位的匹配图。


采取最速下降法(Steppest-Descent),将初始状态所有邻域的Err计算,找到Err下降最快的一个邻域作为下一迭代的初始Map。终止至初始状态的Err小于其所有邻域的Err。


如下图:




java 匹配线路 优先级如何实现 线路匹配算法,java 匹配线路 优先级如何实现 线路匹配算法_java 匹配线路 优先级如何实现,第1张


这种方法收敛于局部最优,但是强烈的依赖于初始状态的选择,论文中随机选取4个初始状态达到四个局部最优,选取Err最小的为结果。


1. 2全局最优匹配算法


h=m exp(d),其中m为model数量,d为data数量。


全局最优算法计算量巨大,以上文为例,需要进行4exp(13)=67108864次计算。但是可以根据data直线夹角的限制来减少计算的次数。


2.利用“垂直距离的平方最小”求FitErr

垂直距离平方的意思是Data中的直线,经过F变换后(旋转、平移和尺度),转到与Model同一个坐标系下。Data中的点(文中用到的是两端点)到相对应的Model中线段距离的平方。其中变换方程F的定义如下。

java 匹配线路 优先级如何实现 线路匹配算法,java 匹配线路 优先级如何实现 线路匹配算法_Data_02,第2张

为方便矩阵运算,Data中的第i条线段的第j个点Dij(j=1或j2)的坐标表示如下:

java 匹配线路 优先级如何实现 线路匹配算法,java 匹配线路 优先级如何实现 线路匹配算法_邻域_03,第3张

若用Ni来表示Model中第i条直线的法向量。Mij表示这条线段上的第j点(随意的一点)到原点的向量。Rho等于N·M表示原点到Model中这条线的距离(有正负号)。

Vij表示在可能匹配结果C中,第i条Data中的直线的第j个点到Ni相关Model直线的距离,其中j=1或j=2。即表示直线的两个端点到对应Model的距离。表示如下:

java 匹配线路 优先级如何实现 线路匹配算法,java 匹配线路 优先级如何实现 线路匹配算法_邻域_04,第4张

所谓“平方距离”最小,文章有两种表示方式Ep和EI:(Ei验证过)

java 匹配线路 优先级如何实现 线路匹配算法,java 匹配线路 优先级如何实现 线路匹配算法_初始状态_05,第5张

文章通过求倒数和偏导数的方式求极值,得到Ep的最小值,从而得到三个变量Phi、T和S。通过求Ei的最小值得到的是FitErr。FitErr有个利用Sigma归一化的过程,Sigma的定义为“超过Sigma个像素距离后认为FitErr很大。”Sigma的选取比较重要。

java 匹配线路 优先级如何实现 线路匹配算法,java 匹配线路 优先级如何实现 线路匹配算法_Data_06,第6张

3.计算OmissionErr

OmissionErr表示的是Data中的线段经过上一步计算的Phi、T和S变换后得到的直线,与Model直线未重合的程度p。因此,若在当前变换条件下无Data与Model重合,此时重合的概率为0,p=1.0,Omission最大,若完全重合,重合概率为1.0,p=0,OmissionErr最小。其中a=0.75,Lm是Model的总长,lm是当前model长。

重合的计算利用转换完成的的Data与Model两切向量点积计算。因为Model对于Data是一对多,因此Data中匹配到同一Model的直线重合程度要取交集。

java 匹配线路 优先级如何实现 线路匹配算法,java 匹配线路 优先级如何实现 线路匹配算法_Data_07,第7张

java 匹配线路 优先级如何实现 线路匹配算法,java 匹配线路 优先级如何实现 线路匹配算法_邻域_08,第8张

java 匹配线路 优先级如何实现 线路匹配算法,java 匹配线路 优先级如何实现 线路匹配算法_Data_09,第9张

根据输入匹配图Err的最小来判断最佳的匹配。

其中Err由三个部分组成,分别是FitErr,OmissionErr和SacaleErr。

4.计算SacleErr

为防止尺度变换过大从而使得上述两者Err很小而匹配效果不佳,加入ScaleErr。若进行全局搜索最佳匹配,可简单的使Scale在一定范围内,如[0.5,2]之间接受,否则不接受。若进行局部最优匹配,简单的阈值操作很有可能在迭代中间状态时因为某一状态的所有“邻域”都不满足scale的范围,从而收敛错误,因此需要加上ScaleErr。其中r=2。

java 匹配线路 优先级如何实现 线路匹配算法,java 匹配线路 优先级如何实现 线路匹配算法_邻域_10,第10张

5.效果示意图


示例一:四图分别为Data原图、原图提取Data线段,Model线段,匹配结果。



java 匹配线路 优先级如何实现 线路匹配算法,java 匹配线路 优先级如何实现 线路匹配算法_java 匹配线路 优先级如何实现_11,第11张


.

java 匹配线路 优先级如何实现 线路匹配算法,java 匹配线路 优先级如何实现 线路匹配算法_邻域_12,第12张

示例二:三图分别为Model、Data,匹配结果。

java 匹配线路 优先级如何实现 线路匹配算法,java 匹配线路 优先级如何实现 线路匹配算法_初始状态_13,第13张

----------------------------------------------------参考文献--------------------------------------------

Beveridge J R, Riseman E M. How easy is matching 2D line models using local search?[J]. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 1997, 19(6): 564-579.   

Beveridge J R. Local search algorithms for geometric object recognition: Optimal correspondence and pose[J]. 1993.(博士论文)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!