微信服务号

微信订阅号

2025年3月24日 11:58 星期一
首页 > 过刊浏览>2016年第27卷第10期 >2462-2472. DOI:10.13328/j.cnki.jos.005090
PDF HTML阅读 XML下载 导出引用 引用提醒
层次结构K-d树的立体图像快速匹配方法
作者:
基金项目:

国家自然科学基金（61373107）


Fast and Hierarchical K-d Tree Based Stereo Image Matching Method
Author:
Fund Project:

National Natural Science Foundation of China (61373107)

  • 摘要
    • | |
  • 访问统计
    • |
  • 参考文献 [42]
    • |
  • 相似文献 [20]
    • | | |
  • 文章评论
    摘要:

    特征匹配是计算机视觉和图形图像处理领域中很多研究方向的基础，也是当前的研究热点.SIFT（scaleinvariant feature transformation）特征因其具有尺度、旋转不变性，对一定范围的仿射及视角变换具有鲁棒性等优点，自Lowe提出后，10多年来一直受到众多研究人员的关注.匹配的快速性和准确性是很多应用对特征匹配的要求，如三维重建中立体图像对（stereo pairwise image，简称SPI）的匹配.针对这一问题，以SIFT特征为基础，提出用于SPI匹配的方向大约一致（approximately consistent in orientation，简称ACIO）约束关系，其描述了SPI的匹配特征向量间的空间位置关系，有效地避免了误匹配的发生，提高了匹配的精度；通过对标准K-d树（standard K-d tree，简称SKD-tree）结构的分析，提出了层次结构K-d树（hierarchical K-d tree，简称HKD-tree），将SPI特征集根据ACIO约束关系划分成层次结构并建立映射，该方法缩小了搜索空间，从而达到加速匹配的目的.在ACIO和HKD-tree的基础上，提出了高效、快速的匹配算法.实验结果表明，所提方法比SKD-tree方法和最新的级联哈希方法（cascade hash，简称CasHash）在精度上略占优势，但在匹配速度上比SKD-tree快一个数量级以上，同时也数倍于CasHash.

    Abstract:

    Feature Matching has long been the basis and a central topic in the field of computer vision and image processing. SIFT (scale-invariant feature transformation, by David G. Lowe), due to its advantages of invariance to image scale and rotation, and robustness to a substantial range of affine distortion and change in viewpoint, has been attracting the attention of many domestic and foreign researchers over a decade. Rapidity and accuracy are very crucial for stereo pairwise image matching in applications such as 3D reconstruction. First, in order to accelerate the speed and promote the accuracy of matching, this paper proposes a novel method based on SIFT called approximately consistent in orientation (ACIO), which depicts the spatial location relationship of two matched vectors between stereo pairwise images (SPI), and therefore improves the accuracy of matching efficiently by avoiding the wrong correspondences. Secondly, this paper analyzes the structure of standard K-d tree (SKD-tree) and proposes a new one with hierarchical structure, named HKD-tree, which partitions the feature sets of SPI into stripes in terms of ACIO constraint and builds map between them. By reducing the search space, the matching speed increases greatly. Thirdly this work presents an efficient and fast matching algorithm based on ACIO and HKD-tree. Extensive trials based on a benchmark data set show that the proposed approach outperforms the state-of-the-art methods in matching speed with slight promotion in accuracy. Particulary, it is one order of magnitude faster than SKD-tree and also several times against the recent CasHash method.

    参考文献
    [1] Cheng J,Leng C,Wu JX,Cui HN,Lu HQ.Fast and accurate image matching with cascade hashing for 3d reconstruction.In:Proc.of the 2014 IEEE Conf.on Computer Vision and Pattern Recognition.Washington:IEEE,2014.1-8.[doi:10.1109/CVPR.2014.8]
    [2] Dalal N,Triggs B.Histograms of oriented gradients for human detection.In:Proc.of the 2005 IEEE Conf.on Computer Vision and Pattern Recognition.Washington:IEEE,2005.886-893.[doi:10.1109/CVPR.2005.177]
    [3] Lowe DG.Object recognition from local scale-invariant features.In:Proc.of the 7th IEEE Int'l Conf.on Computer Vision.Washington:IEEE,1999,2:1150-1157.[doi:10.1109/ICCV.1999.790410]
    [4] Lowe DG.Distinctive image features from scale-invariant keypoints.Int'l Journal of Computer Vision,2004,60(2):91-110.[doi:10.1023/B:VISI.0000029664.99615.94]
    [5] Snavely N,Seitz SM,Szeliski R.Photo tourism:Exploring photo collections in 3D.ACM Trans.on Graphics (TOG),2006,25(3):835-846.[doi:10.1145/1141911.1141964]
    [6] Philbin J,Chum O,Isard M,Sivic J,Zisserman A.Object retrieval with large vocabularies and fast spatial matching.In:Proc.of the 2007 IEEE Conf on Computer Vision and Pattern Recognition.Washington:IEEE,2007.1-8.[doi:10.1109/CVPR.2007.383172]
    [7] Mikolajczyk K,Leibe B,Schiele B.Multiple object class detection with a generative model.In:Proc.of the 2006 IEEE Computer Society Conf.on Computer Vision and Pattern Recognition.Washington:IEEE,2006,1:26-36.[doi:10.1109/CVPR.2006.202]
    [8] Ferrari V,Tuytelaars T,Van Gool L.Simultaneous object recognition and segmentation by image exploration.In:Pajdla T,ed.Proc.of the Computer Vision-ECCV 2004.Heidelberg:Springer-Verlag,2004.40-54.[doi:10.1007/978-3-540-24670-1_4]
    [9] Arth C,Leistner C,Bischof H.Robust local features and their application in self-calibration and object recognition on embedded systems.In:Proc.of the 2007 IEEE Conf.on Computer Vision and Pattern Recognition.Washington:IEEE,2007.1-8.[doi:10.1109/CVPR.2007.383419]
    [10] Li FF,Perona P.A Bayesian hierarchical model for learning natural scene categories.In:Proc.of the 2005 IEEE Conf.on Computer Vision and Pattern Recognition.Washington:IEEE,2005.524-531.[doi:10.1109/CVPR.2005.16]
    [11] Lazebnik S,Schmid C,Ponce J.Beyond bags of features:Spatial pyramid matching for recognizing natural scene categories.In:Proc.of the 2006 IEEE Computer Society Conf.on Computer Vision and Pattern Recognition.Washington:IEEE,2006,2:2169-2178.[doi:10.1109/CVPR.2006.68]
    [12] Bay H,Tuytelaars T,Van Gool L.Surf:Speeded up robust features.In:Leonardis A,ed.Proc.of the Computer vision-ECCV 2006.Heidelberg:Springer-Verlag,2006.404-417.[doi:10.1007/11744023_32]
    [13] Toews M,Wells W.SIFT-Rank:Ordinal description for invariant feature correspondence.In:Proc.of the 2009 IEEE Conf on Computer Vision and Pattern Recognition.Washington:IEEE,2009.172-177.[doi:10.1109/CVPR.2009.5206849]
    [14] Calonder M,Lepetit V,Strecha C,Fua P.Brief:Binary robust independent elementary features.In:Daniilidis K,ed.Proc.of the Computer Vision-ECCV 2010.Heidelberg:Springer-Verlag,2010.778-792.[doi:10.1007/978-3-642-15561-1_56]
    [15] Rublee E,Rabaud V,Konolige K,Bradski G.ORB:An efficient alternative to SIFT or SURF.In:Proc.of the 2011 IEEE Int'l Conf.on Computer Vision.Washington:IEEE,2011.2564-2571.[doi:10.1109/ICCV.2011.6126544]
    [16] Li B,Liu L,Wei ZQ.A strong robust real-time image matching algorithm.Ruan Jian Xue Bao/Journal of Software,2014,25(7):1583-1592(in Chinese with English abstract).http://www.jos.org.cn/1000-9825/4450.htm.[doi:10.13328/j.cnki.jos.004450]
    [17] Pele O,Werman M.A linear time histogram metric for improved shift matching.In:Forsyth D,ed.Proc.of the Computer Vision-ECCV 2008.Heidelberg:Springer-Verlag,2008.495-508.[doi:10.1007/978-3-540-88690-7_37]
    [18] Ling HB,Okada K.Diffusion distance for histogram comparison.In:Proc.of the 2006 IEEE Computer Society Conf.on Computer Vision and Pattern Recognition.Washington:IEEE,2006,1:246-253.[doi:10.1109/CVPR.2006.99]
    [19] Werman M,Peleg S,Melter R,Kong TY.Bipartite graph matching for points on a line or a circle.Journal of Algorithms,1986,7(2):277-284.[doi:10.1016/0196-6774(86)90009-X]
    [20] Ke Y,Sukthankar Y.PCA-SIFT:A more distinctive representation for local image descriptors.In:Proc.of the 2004 IEEE Computer Society Conf.on Computer Vision and Pattern Recognition.Washington:IEEE,2004,2:Ⅱ-506-Ⅱ-513.[doi:10.1109/CVPR.2004.1315206]
    [21] Mikolajczyk K,Schmid C.A performance evaluation of local descriptors.IEEE Trans.on Pattern Analysis and Machine Intelligence,2005,27(10):1615-1630.[doi:10.1109/TPAMI.2005.188]
    [22] Gilinsky A,Zelnik-Manor L.SIFTpack:A compact representation for efficient SIFT matching.In:Proc.of the 2013 IEEE Int'l Conf.on Computer Vision.Washington:IEEE,2013.777-784.[doi:10.1109/ICCV.2013.101]
    [23] Strecha C,Bronstein AM,Bronstein MM,Fua P.LDAHash:Improved matching with smaller descriptors.IEEE Trans.on Pattern Analysis and Machine Intelligence,2012,34(1):66-78.[doi:10.1109/TPAMI.2011.103]
    [24] Liu C,Yuen J,Torralba A,Sivic J,Freeman WT.Sift flow:Dense correspondence across different scenes.In:Forsyth D,Torr P,Zisserman A,eds.Proc.of the Computer Vision-ECCV 2008.Heidelberg:Springer-Verlag,2008.28-42.[doi:10.1007/978-3-540-88690-7_3]
    [25] Ghamdi MA,Zhang L,Gotoh Y.Spatio-Temporal SIFT and its application to human action classification.In:Fusiello A,ed.Proc.of the Computer Vision-ECCV 2012,Workshops and Demonstrations.Heidelberg:Springer-Verlag,2012.301-310.[doi:10.1007/978-3-642-33863-2_30]
    [26] Lopes APB,Oliveira RS,de Almeida JM,de Arnaldo AA.Spatio-Temporal frames in a bag-of-visual-features approach for human actions recognition.In:Proc.of the 2009 XXⅡ Brazilian Symp.on Computer Graphics and Image Processing.Washington:IEEE,2009.315-321.[doi:10.1109/SIBGRAPI.2009.17]
    [27] Kanade T,Okutomi M.A stereo matching algorithm with an adaptive window:Theory and experiment.IEEE Trans.on Pattern Analysis and Machine Intelligence,1994,16(9):920-932.[doi:10.1109/34.310690]
    [28] Veksler O.Stereo matching by compact windows via minimum ratio cycle.In:Proc.of the 8th IEEE Int'l Conf.on Computer Vision,2001.Washington:IEEE,2001,1:540-547.[doi:10.1109/ICCV.2001.937563]
    [29] Veksler O.Fast variable window for stereo correspondence using integral images.In:Proc.of 2003 IEEE Computer Society Conf.on Computer Vision and Pattern Recognition.Washington:IEEE,2003,1:I-556-I-561.[doi:10.1109/CVPR.2003.1211403]
    [30] Wang K.Adaptive stereo matching algorithm based on edge detection.In:Proc.of the 2004 Int'l Conf.on Image Processing.Washington:IEEE,2004,2:1345-1348.[doi:10.1109/ICIP.2004.1419748]
    [31] Yoon KJ,Kweon IS.Adaptive support-weight approach for correspondence search.IEEE Trans.on Pattern Analysis and Machine Intelligence,2006,28(4):650-656.[doi:10.1109/TPAMI.2006.70]
    [32] Banks J,Bennamoun M,Corke P.Non-Parametric techniques for fast and robust stereo matching.In:Proc.of the IEEE Region 10 Annual Conf.on Speech and Image Technologies for Computing and Telecommunications.Washington:IEEE,1997,1:365-368.[doi:10.1109/TENCON.1997.647332]
    [33] Zabih R,Woodfill J.Non-Parametric local transforms for computing visual correspondence.In:Eklundh JO,ed.Proc.of the Computer Vision-ECCV'94.Heidelberg:Springer-Verlag,1994,2:151-158.[doi:10.1007/BFb0028345]
    [34] Cai J.Integration of optical flow and dynamic programming for stereo matching.IET Image Processing,2012,6(3):205-212.[doi:10.1049/iet-ipr.2010.0070]
    [35] Nguyen M,Chan YH,Delmas P,Gimel'farb G.Symmetric dynamic programming stereo using block matching guidance.In:Proc.of the 28th Int'l Conf.of Image and Vision Computing New Zealand (IVCNZ).Washington:IEEE,2013.88-93.[doi:10.1109/IVCNZ.2013.6726997]
    [36] Taniai T,Matsushita Y,Naemura T.Graph cut based continuous stereo matching using locally shared labels.In:Proc.of the 2014 IEEE Conf.on Computer Vision and Pattern Recognition.Washington:IEEE,2014.1613-1620.[doi:10.1109/CVPR.2014.209]
    [37] Zhang H,Cheng FY,Yuan D,Li YC,Sun MG.Stereo matching with global edge constraint and graph cuts.In:Proc.of the 21st Int'l Conf.on Pattern Recognition (ICPR).Washington:IEEE,2012.372-375.
    [38] Sun J,Zheng NN,Shum HY.Stereo matching using belief propagation.IEEE Trans.on Pattern Analysis and Machine Intelligence,2003,25(7):787-800.[doi:10.1109/TPAMI.2003.1206509]
    [39] Ahmadzadeh A,Madani H,Jafari K,Jazi FS,Daneshpajouh S,Gorgin S.Fast and adaptive BP-based multi-core implementation for stereo matching.In:Proc.of the 11th IEEE/ACM Int'l Conf.on Formal Methods and Models for Codesign (MEMOCODE).Washington:IEEE,2013.135-138.
    [40] Scharstein D,Szeliski R.A taxonomy and evaluation of dense two-frame stereo correspondence algorithms.Int'l Journal of Computer Vision,2002,47(1/3):7-42.[doi:10.1023/A:1014573219977]
    [41] Heiko H,Scharstein D.Evaluation of cost functions for stereo matching.In:Proc.of the 2007 IEEE Conf.on Computer Vision and Pattern Recognition.IEEE,2007.1-8.[doi:10.1109/CVPR.2007.383248]
    [16] 李兵,刘磊,魏志强.一种具有强实时性、强鲁棒性的图像匹配算法.软件学报,2014,25(7):1583-1592.http://www.jos.org.cn/1000-9825/4450.htm.[doi:10.13328/j.cnki.jos.004450]
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

张贵安,袁志勇,童倩倩,廖祥云.层次结构K-d树的立体图像快速匹配方法.软件学报,2016,27(10):2462-2472

复制
分享
文章指标
  • 点击次数:4418
  • 下载次数: 6378
  • HTML阅读次数: 3171
  • 引用次数: 0
历史
  • 收稿日期:2016-02-02
  • 最后修改日期:2016-03-25
  • 在线发布日期: 2016-08-11
文章二维码
友情链接:中国科学院软件研究所中国计算机学会中国科学院国家自然科学基金委员会CCF数字图书馆Int'l J of Softw Info计算机系统应用
您是第19727752位访问者
版权所有：中国科学院软件研究所 京ICP备05046678号-3
地址：北京市海淀区中关村南四街4号,邮政编码：100190
电话：010-62562563 传真：010-62562533 Email：jos@iscas.ac.cn
技术支持：北京勤云科技发展有限公司

京公网安备 11040202500063号