注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

王小二的博客

勤俭以修身,淡泊以明志

 
 
 

日志

 
 

min-hash用来做partial duplicate image discovery  

2012-07-09 19:56:10|  分类: 专业相关 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 from: http://blog.csdn.net/kipykspy/article/details/5988100


min-hash中h(I)返回的值是,二值化bag of words向量为1的位置所对应的最小值。
如:
bit map of bag of words:                     1 ....
hash()                           : 0.1  0.3  0.2  0.5  0.15 0.6 ....
则h() = 0.3(第二列对应的)


1次min-hash(即使用一个hash函数,h(I)的结果是一个数),且sketch = 1时(做一次N个min-hash,结果是一个向量(min-hash次数等于1时为一个数)):
h相同,若I1 I2的元素相同,则h(I1), h(I2)亦相同。
其中,I1 I2为二值化的bag of words。由于h是随机函数,则每个等于1的元素处,所对应的h()取最小值的概率是等可能的。
注意到h(I)后,所得到的向量每个元素都不相等(哈希特性)。则h(I)相等 可推出 在两幅图像的二值化的bag of words向量的某个相同的位置上,都为1。
所以

 

    P(h(I1)==h(I2))

= 在两幅图像的二值化的bag of words向量的相同位置上都为1(的数量)/ 在两幅图像的二值化的bag of words向量的任意位置上任意一个向量的元素为1(的数量)

= sim(I1,I2)

 

 

所以当N(min_hash) = k , sketch = n时:
P(h(I1)==h(I2)) = 1 - (1 - sim(I1,I2)^k )^n
此时,
                                     sim(I1,I2) > theta
P(h(I1)==h(I2))近似为:
                                     otherwise

min-hash取min,取max,甚或是取第N大或小的效果都是一样的。

min-hash之所以不直接用(向量中的)位置信息而取k*n(N(min_hash) = k , sketch = n)个random(hash)函数是因为位置信息是单调递增的。

  评论这张
 
阅读(239)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017