基于GPU加速的快速图像相似区域查找

摘要/Abstract

摘要： 图像相似区域查找是很多图形图像应用中的关键问题,也是计算瓶颈。传统加速方法如ANN(Approximate Nearest Neighbor)处理较大图像区域时速度较慢,而且在非度量空间下不支持精确查找。提出基于GPU加速的图像相似区域并行查找的通用计算框架,该框架可以扩展,以支持任意距离函数。特别针对在图像处理中应用广泛的欧氏距离(度量空间)和Chamfer距离(非度量空间)分别提出了基于CUDA的高效相似区域查找算法,比较完备地给出了相似性计算在不同度量空间下的实现。进一步,在设计具体的CUDA加速算法中,结合不同距离计算的特点对并行计算过程进行优化。该方法采用穷举的查找策略,在欧氏距离和Chamfer距离下都能实现精确查找,且大大提高了计算效率。实验结果表明,加速算法在准确查找的基础上执行速度比传统加速方法提升了一至二个数量级,且应用于纹理合成的实例表明,算法可以快速合成高质量的纹理。

关键词: 度量空间,图像相似区域,GPU,Chamfer距离,纹理合成中图法分类号TP391文献标识码A

Abstract: Many image processing or computer graphic applications involve similar patches search in images,which is a very computational-expensive operation．Traditional acceleration methods such as ANN (Approximate Nearest Neighbor) do not support exact search in non-metric space,and the searching time becomes longer for high-dimensional space.In this paper the general GPU-based framework to compute the similar patches was proposed which can be extended to incorporate any distance functions．Specifically,both Euclidean distance and non-metric Chamfer distance are adopted to compute the similarity between two patches．We proposed the GPU-based algorithm for fast search of similar patches in images under these two distances．Besides,the distances computation is optimized to achieve more efficient CUDA implementation．This algorithm supports exact search since exhaustive search strategy is adopted．The distances between patches are computed in parallel on GPU to greatly improve the computational efficiency．Experimental results show that our method has one or two orders of magnitude speedup compared with traditional acceleration methods and the results of applications in texture synthesis show that our method is capable to synthesize high-quality textures with fast speed.

Key words: Metric space,Similar patches,GPU,Chamfer distance,Texture synthesis

汤颖,肖廷哲,范菁. 基于GPU加速的快速图像相似区域查找[J]. 计算机科学, 2014, 41(2): 290-296. https://doi.org/

TANG Ying,XIAO Ting-zhe and FAN Jing. GPU-based Fast Search of Similar Patches in Images[J]. Computer Science, 2014, 41(2): 290-296. https://doi.org/

参考文献

[1] Efros A A,Leung T K．Texture synthesis by non-parametricsampling[C]∥Proceedings of the Seventh IEEE International Conference on Computer Vision．Greece,1999:1033-1038
[2] Hertzmann A,Jacobs C E,Oliver N,et al．Image analogies[C]∥Proceedings of the 28th annual conference on Computer graphics and interactive techniques．New York,NY,USA:ACM,2001:327-340
[3] Wang H,Wexler Y,Ofek E,et al．Factoring repeated contentwithin and among images[J]．ACM Trans．Graphics(SIGGRAPH),2008,27:3
[4] Barrow H G,Tenenbaum J M,Bolles R C,et al．Parametric correspondence and Chamfer matching:two new techniques for ima-ge matching[C]∥Proceedings of the 5th International Joint Conference on Artificial Intelligence-Volume 2．San Francisco,CA,USA:Morgan Kaufmann Publishers Inc.,1977:659-663
[5] Borgefors G．Hierarchical Chamfer matching:a parametric edge matching algorithm[J]．IEEE Transactions on Pattern Analysis and Machine Intelligence,1988,10(6):849-865
[6] Bonneel N,Van De Panne M,Lefebvre S,et al．Proxy-GuidedTexture Synthesis for Rendering Natural Scenes[C]∥Vision Modeling and Visualization Workshop (VMV 2010)．Siegen,Allemagne:Eurographics Association,2010:87-95
[7] Kumar N,Zhang L,Nayar S．What Is a Good Nearest Neighbors Algorithm for Finding Similar Patches in Images?[J]．ComputerVision-ECCV 2008,5303:364-378
[8] Samet H．多维与度量数据结构基础[M]．周立柱,王宏,邓俊辉,等译．北京:清华大学出版社,2011:461-698
[9] Athitsos V,Sclaroff S．Database Indexing Methods for 3D Hand Pose Estimation[C]∥Gesture-Based Communication in Human-Computer Interaction:5th International Gesture Workshop,GW 2003,Genova,Italy,April 15-17,2003,Selected Revised Papers．Springer,2004,2915:288
[10] Wei L Y,Levoy M．Fast texture synthesis using tree-structured vector quantization[C]∥Proceedings of the 27th annual conference on Computer graphics and interactive techniques．New York,NY,USA:ACM Press/Addison-Wesley Publishing Co.,2000:479-488
[11] Lefebvre S,Hoppe H．Parallel controllable texture synthesis[J]．ACM Transactions on Graphics,2005,24(3):777-786
[12] Lefebvre S,Hoppe H．Appearance-space texture synthesis[J]．ACM Transactions on Graphics,2006,25(3):541-548
[13] Ashikhmin M．Synthesizing natural textures[C]∥Proceedings of the 2001symposium on Interactive 3D graphics．New York,NY,USA:ACM,2001:217-226
[14] Lowe D G．Distinctive Image Features from Scale-Invariant Keypoints[J]．International Journal of Computer Vision,2004,60(2):91-110
[15] Sivic J,Zisserman A．Video Google:a text retrieval approach to object matching in videos[C]∥Proceedings of the Ninth IEEE International Conference on Computer Vision．2003:1470-1477
[16] Nister D,Stewenius H．Scalable Recognition with a Vocabulary Tree[C]∥Proceedings of IEEE Computer Society Conference on Computer Vision and Pattern Recognition．2006,2:2161-2168
[17] Shechtman E,Irani M．Matching Local Self-Similarities acrossImages and Videos[C]∥Proceedings of IEEE Conference on Computer Vision and Pattern Recognition．2007:1-8
[18] Buades A,Coll B,Morel J-M．A non-local algorithm for imagedenoising[C]∥Proceedings of IEEE Computer Society Confe-rence on Computer Vision and Pattern Recognition．2005,2:60-65
[19] Freeman W T,Jones T R,Pasztor E C．Example-based super-resolution[J]．IEEE Computer Graphics and Applications,2002,22(2):56-65
[20] Barnes C,Shechtman E,Finkelstein A,et al．PatchMatch:a randomized correspondence algorithm for structural image editing[J]．ACM Transactions on Graphics-TOG,2009,28(3):24
[21] Tang Y,Shi X,Xiao T,et al．An improved image analogy method based on adaptive CUDA-accelerated neighborhood matching framework[J]．The Visual Computer,2012,28(6):743-753
[22] Tong X,Zhang J,Liu L,et al．Synthesis of bidirectional texture functions on arbitrary surfaces[J]．ACM Transactions on Graphics,2002,21(3):665-672
[23] Mount D M,Arya S．ANN:Approximate Nearest Neighbor Library[EB/OL]．http://www.cs.umd.edu/~mount/ANN/,2012-08-29
[24] Muja M,Lowe D G．Fast approximate nearest neighbors with automatic algorithm configuration[C]∥Proceedings of International Conference on Computer Vision Theory and Applications (VISSAPP’09)．Portugal:INSTICC Press,2009:331-340
[25] Athitsos V,Hadjieleftheriou M,Kollios G,et al．Query-sensitive embeddings[C]∥Proceedings of the 2005ACM SIGMOD international conference on Management of data．New York,NY,USA:ACM,2005:706-717
[26] Athitsos V,Potamias M,Papapetrou P,et al．Nearest Neighbor Retrieval Using Distance-Based Hashing[C]∥Proceedings of IEEE 24th International Conference on Data Engineering．2008:327-336
[27] Basic Linear Algebra Subprograms[EB/OL]．Wikipedia,the free encyclopedia.http://en.wikipedia.org/wiki/Basic_Linear_Algebra_Subprograms,2012-09-11
[28] Monteiro E,Maule M,Sampaio F,et al．Real-time block mat-ching motion estimation onto GPGPU[C]∥ 201219th IEEE International Conference on Image Processing (ICIP)．IEEE,2012:1693-1696
[29] Massanes F,Cadennes M,Brankov J G．Compute-unified device architecture implementation of a block-matching algorithm for multiple graphical processing unit cards[J]．Journal of electronic imaging,2011,20(3)

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed