您的位置: 首页  >  文章  >  基于图像形状的一种比较漂亮的分类算法

基于图像形状的一种比较漂亮的分类算法

分类: 文章 • 2024-01-27 11:52:46

原文：http://blog.csdn.net/lishuhuakai/article/details/53573241

 

基于图像形状的一种比较漂亮的分类算法

我首先讲一下我所遭遇到的情况吧:

有n类似于下图的图片:

基于图像形状的一种比较漂亮的分类算法

我这里有一个需求就是,将这些图片分类,分类的效果至少也应该是这样的:

基于图像形状的一种比较漂亮的分类算法

将一些形状非常类似的图片分在一起.


我大致查阅了一下挺多的分类算法,这些算法大致分为了两类:

一类是通过对分类器进行训练,比如说要识别猫,那就要喂给分类器非常多的猫的图片,得到一些参数之后才能够比较精确地对图片进行识别.当然,这一大类的方法对于我们所拥有的数据来说,并不适合,我们并没有用于训练的图片.

另外一种方法不用训练,思想和机器学习里面的聚类差不太多,主要通过比较图片的一些特征,计算出与相似度类似的一个度量,来对图片进行分类.


好吧,我们大致只能使用聚类之类的东西来分类了.


究竟怎么来分呢?

说实话,我尝试了一些比较有名的聚类算法,效果都不怎么理想,然后我看到了Hausdorff Distance,这是一种在图像处理中轨迹识别什么的经常用到的距离度量,我只是抱着试一试的心态尝试了一下Hausdorff Distance加上k均值聚类,结果效果出乎我的意料,效果拔群.上面的效果你也看到了,至少在眼睛上看起来,非常不错.


关于Hausdorff Distance,推荐你看这里:

http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/98/normand/main.html

有中文翻译版的:

http://blog.sina.com.cn/s/blog_4062094e0102vkpf.html


k均值聚类应该不用我来讲了,差不多都烂了.


我这里给出Hausdorff Distance的Python代码实现吧:

[python] view plain copy
 print?
  1.   
[python] view plain copy
 print?
  1. """ 
  2.     目标: 
  3.     ~~~~~~~~~ 
  4.     实现 Hausdorff 距离.该距离的定义如下: 
  5.     A = {a1, a2, ..., an}, B = {b1, b2, ..., bm} 
  6.     两者的 Hausdorff 距离为: 
  7.     H(A, B) = max{h(A, B), h(B, A)}, 
  8.     其中 
  9.     h(A, B)的定义如下,无法用数学公式来展现,我这里用语言来描述一下得了. 
  10.     对于A中的每一个点a,首先在B中找到一个距离a最近的点b,得到a,b它们之间的距离dist(a, b),这里的dist定义如下: 
  11.     dist(a, b) = sqrt((xa - xb)^2, (ya - yb)^2),就是欧氏距离啦. 
  12.     通过计算得到n个这样的距离,找出其中最大的一个,作为h(A, B),h(B, A)同理. 
  13. """  
  14. from math import sqrt  
  15.   
  16. def euclidean_metric(pa, pb):  
  17.     ''''' 
  18.     计算两个点的欧式距离. 
  19.     关于输入的pa以及pb,它们应该是一个list或者tuple,长度应该相等. 
  20.     '''  
  21.     return sqrt((pa[0] - pb[0])**2 + (pa[1] - pb[1])**2)  
  22.   
  23. def one_way_hausdorff_distance(sa, sb):  
  24.     '''''计算单向hausdorff距离'''  
  25.     distance = 0.0  
  26.     for pa in sa: # 对于a集合中的每一个点,要求出这个点到  
  27.         shortest = 9999999  
  28.         for pb in sb:  
  29.             dis = euclidean_metric(pa, pb)  
  30.             if dis < shortest:  
  31.                 shortest = dis  
  32.         if shortest > distance:  
  33.             distance = shortest  
  34.     return distance  
  35.   
  36. def hausdorff_distance(sa, sb):  
  37.     ''''' 
  38.     计算两个集合中的点的 hausdorff 距离. 
  39.     关于输入的sa以及sb,两者应该是点的list或者tuple,而点的定义参照euclidean_metric. 
  40.     '''  
  41.     dis_a = one_way_hausdorff_distance(sa, sb)  
  42.     dis_b = one_way_hausdorff_distance(sb, sa)  
  43.     return dis_a if dis_a > dis_b else dis_b  
  44.   
  45.   
  46. if __name__ == '__main__':  
  47.     assert(euclidean_metric((1, 1), (1, 6)) == 5)  
  48.     A = [(0, 0), (1, 0), (2, 0), (3, 0), (4, 0)]  
  49.     B = [(0, 3), (1, 3), (2, 3), (3, 3), (3, 2), (4, 2)]  
  50.     C = [(4, 2), (4, 1), (4, 0)]  
  51.     D = [(0, 2), (1, 2), (2, 2), (2, 3), (2, 4)]  
  52.     one_way_hausdorff_distance(A, B)  

另外还有一种度量公式,那就是Fréchet distance.

这是最近才找到的一种距离,将这种距离运用于分类,效果其实比上面的还要好.

它的python实现代码如下:

[python] view plain copy
 print?
  1. """ 
  2.     Fréchet distance 
  3. """  
  4. import math  
  5. import numpy as np  
  6.   
  7. # Euclidean distance.  
  8. def euc_dist(pt1,pt2):  
  9.     return math.sqrt((pt2[0]-pt1[0])**2+(pt2[1]-pt1[1])**2)  
  10.   
  11. def _c(ca,i,j,P,Q):  
  12.     if ca[i,j] > -1:  
  13.         return ca[i,j]  
  14.     elif i == 0 and j == 0:  
  15.         ca[i,j] = euc_dist(P[0],Q[0])  
  16.     elif i > 0 and j == 0:  
  17.         ca[i,j] = max(_c(ca,i-1,0,P,Q),euc_dist(P[i],Q[0]))  
  18.     elif i == 0 and j > 0:  
  19.         ca[i,j] = max(_c(ca,0,j-1,P,Q),euc_dist(P[0],Q[j]))  
  20.     elif i > 0 and j > 0:  
  21.         ca[i,j] = max(min(_c(ca,i-1,j,P,Q),_c(ca,i-1,j-1,P,Q),_c(ca,i,j-1,P,Q)),euc_dist(P[i],Q[j]))  
  22.     else:  
  23.         ca[i,j] = float("inf")  
  24.     return ca[i,j]  
  25.   
  26. """ Computes the discrete frechet distance between two polygonal lines 
  27. Algorithm: http://www.kr.tuwien.ac.at/staff/eiter/et-archive/cdtr9464.pdf 
  28. P and Q are arrays of 2-element arrays (points) 
  29. """  
  30. def frechet_distance(P,Q):  
  31.     ca = np.ones((len(P),len(Q)))  
  32.     ca = np.multiply(ca,-1)  
  33.     return _c(ca,len(P)-1,len(Q)-1,P,Q)  
函数的调用方法和上面Hausdorff Distance的代码一致.

相关推荐