SIFT特征分布式并行提取算法

A Distributed Parallel Algorithm for SIFT Feature Extraction

SIFT(scale invariant feature transform)特征在物体检测和识别、图像配准与融合、纹理识别、场景分类、人脸检测、图像检索、三维重建、数字水印、影像追踪等领域具有广泛应用,但存在计算量大、消耗时间长的缺点.基于消息传递机制,采用数据并行策略,提出了在PC机群或COW(cluster ofworkstation)上提取图像SIFT特征的分布式并行算法(DP-SIFT算法):根据特征空间-高斯尺度金字塔的特点提出了高度宽度受限的数据块划分算法,设计了数据分配和特征调整方法;研究了数据块划分和数据发送方法对通信时间的影响,提出了基于消息传递机制的并行图像处理中数据块划分与数据发送方式协同对通信优化的策略;实验结果表明DP-SIFT算法具有良好的加速性能和较高的处理器利用效率,千兆以太网连接32核的PC机群系统图像规模为1024×768时,加速比和处理器效率分别可以达到20和0.6;图像规模为2048×1536时可达18和0.56.

SIFT（scale invariant feature transform） has been widely applied to object detection and recognition, image registration and fusion, texture recognition, scene classification, human face detection, image retrieval, 3D reconstruction, digital watermarking, and object tracking. However, it is compute-intensive and time-consuming. A distributed parallel algorithm for extracting SIFT features （DP-SIFT algorithm） is proposed using data parallel strategy on PC clusters/COW （cluster of workstation） based on message passing. An algorithm for data blocking with limitation on height and width is designed according to the specific characteristic of feature extraction space. Data distribution and feature adjustment methods are also presented. A strategy of data blocking coordinate with data passing approaches for communication optimization in image parallel processing is proposed after the effect of data blocking methods and data passing approaches on communication time are investigated. Experimental results verify that the DP-SIFT algorithm has remarkable performance on speedup and efficiency. On clusters of PCs with 32 cores linked by gigabit Ethernet, the speedup and efficiency can reach as high as 20 and 0.6 respectively when input image scale is 1 024×768, and 18 and 0.56 when input image scale is 2 048 × 1 536.