SIFT算法复杂度比较高，多次卷积计算量比较大，并且由于产生的特征点很多，生成特征向量的时间也就比较长；至于后期的匹配和识别过程，也需要一定的时间，比如基于kd-tree的BBF算法，虽说搜索速度比逐一比较加快了几个数量级，但数据库一大，输入特征点比较多的话，还是挺耗时的。而hash hough即需要空间上资源(每个feature需要对应16个bin)，也需要一定的计算量，如求解基于最小二乘的仿射变换。因此要做到实时真是太难了。目前看到的最快速度大概也就是10帧左右吧，那已是commercial product了，并且David Lowe本人亲自参与开发，自是不可比拟的了。
SIFT算法过程也比较复杂，目前网上有一些参考代码，质量参差不齐，倒是不错的参考，完全自己写，还是比较难的，目前还没这样的算法素养。kd-tree比较成熟了，拿来用就是了，倒是generalized hash hough有点费神，Lowe的paper写得挺含糊，也并没有找到可参考的代码，只能自己边想边写了。hough变换的原理很简单，只想不明白hash与hough是如何结合的，看了一大堆hough变换的应用资料，再结合hash原理，用了三天才将代码写出，其中用到了STL中的hashmap(STL还是挺方便的，后来自己用C写了个hashtable实现hash hough，效果就有点差，可能是hash函数不够hash，数据结构安排也不合理)，效果还是挺好的，挺开心的，也挺佩服Lowe提出的算法和框架，确实很有效。
下面是一些截图，已经将SIFT-Based目标识别做成模块，集成到Demo中了：
第四张图为landmark，前三张为在线识别视频截图，左边主窗口为识别图像，左边小窗口为视频图像，中下数据窗口为识别结果，右边竖条为landmark image database。
7 条评论:
这篇文章不错，楼主能详细介绍一个generalized hough transform吗？我看了好久没看懂， 网上资料好像也很少.
In fact, many papers on generalized Hough transform are available, and probably you can get some ideas about this algorithm.
However, it seems to me that hash hough as mentioned in Lowe's paper, is different from GHT, more like a kind of variant to traditional hough transform, where the difference lies in whether the bins are set fixed according to the possible ranges of votes, or can change dynamicly according to one special vote. My implementation adopts the latter approach, in which the bins are allocated for speical votes, thus saving a lot of space, compared with traditional hough transform.
我也是不明白Hash Hough Transform的做法，不知道这两个方面是怎么结合的，楼主能详细的解释一下吗？谢谢
通常Hough变换需要预先指定参数空间，通常这会很要求分配很大的参数空间，但其实只用到了其中很小的一部分。
Hash和Hough的结合，正是为了解决这一问题，以节省空间复杂度。一个办法是对参数进行重映射(Hash)，然后插入动态数据结构中，以实现按需分配。
Hash的好处在于，对于相同的key，会映射到同一hash value，也就是所谓的碰撞，在这里，正符合投票的概念。
这是我的理解。其实也不一定非要用hash hough去实现，RANSAC也不错，这两者的时间、空间复杂度，是有一个折衷的。
你好，请问楼主有ransac的c代码吗？本人现在做项目，急需一份代码做测试，多谢了。
我邮箱：llj2007_bj@163.com
不胜感激！
你好，我现在刚开始看SIFT算法，能给个联系方式吗，如果有问题想多多请教！
您好，我想请假个问题：lowe04年的论文里，在用hash hough去除错配后，又有一个章节Solution for affine parameters，请问目的是什么，介绍的较简单，能详细解释一下吗？谢谢！
发表评论