埃及信息学杂志：图像特征提取算法的评估及性能比较研究

制作和主办：ElsevierEgyptian Informatics Journal（2013）14，175开罗大学埃及信息学杂志www.elsevier.com/locate/eijwww.sciencedirect.com原创文章图像低层特征提取算法M.M. El-gayar*，H.Soliman，N.梅基埃及曼苏拉大学计算机和信息系统学院信息技术系收稿日期：2012年11月26日;修订日期：2013年6月12日;接受日期：2013年2013年8月2日在线发布摘要特征提取和匹配是许多计算机视觉问题的基础，物体识别或运动结构。目前流行的图像匹配算法的性能评估方法，并依赖于昂贵的描述符检测和匹配。具体地说，该方法评估图像的类型，每个算法在此进行审查，以发挥其最大或最高效率。效率是根据算法发现的匹配数量以及在针对特定图像对测试算法时遇到的I类和II类错误数量来衡量的目前的比较研究评估的性能的算法的基础上获得的结果在不同的标准，如速度，灵敏度，遮挡，和其他。本研究解决了现有比较工具的局限性，并提供了一个通用标准，以预先确定给定评估图像类型的匹配算法的预期效率水平。本工作中使用的算法和相应的图像分为两组：基于特征的和基于纹理的。从这个广泛的分类中，只有三种最广泛使用的算法被评估：颜色直方图，FAST（加速分段测试的特征），SIFT（尺度不变特征变换），PCA-SIFT（主成分分析-SIFT），F-SIFT（快速SIFT）和SURF（加速鲁棒特征）。针对尺度变化、旋转、模糊、光照变化和模糊变换，比较了Fast-SIFT（F-SIFT）特征检测方法的性能。所有的实验都使用重复性测量和正确匹配的数量用于评估测量。SIFT虽然速度较慢，但在大多数情况下都表现出稳定性。F-SIFT是速度最快的一种，性能与SURF、SIFT、PCA-SIFT显示相当它的优点是在旋转和照明变化。©2013制作和主办由Elsevier B.V.代表计算机与信息学院开罗大学。*通讯作者。联系电话：+20 1061936935。电子邮件地址：algyar_1990@yahoo.com（M.M. El-gayar），mans.edu.eg（H.Soliman），nona762005@hotmail.com（N。meky）。开罗大学计算机和信息系负责同行审查。1110-8665© 2013由Elsevier B. V.代表开罗大学计算机与信息学院制作和主办。http://dx.doi.org/10.1016/j.eij.2013.06.003关键词SIFT;PCA-SIFT;F-SIFT;SURF;FAST176M.M. El-gayar等人1. 介绍特征检测和图像匹配是计算机视觉、计算机图形学、摄影测量和所有图像应用中的两个重要课题。它们的应用每天都在各个领域继续增长。从简单的摄影测量任务（如特征识别）到复杂的3D建模软件和图像搜索引擎的开发此外，近几十年来，这一直是一个非常活跃的研究领域，正如围绕这一领域发表的大量工作和文献所表明的那样。十多年前，与2D和3D模型以及物体重建相关的应用主要用于视觉检测和机器人。今天，这些应用现在包括在计算机图形学、虚拟现实、通信等领域使用2D和3D模型。但是，从一对图像中获得高度可靠的匹配结果是一些最流行的匹配方法试图完成的任务。但没有一个被普遍接受。似乎选择适当的方法来完成匹配任务在很大程度上取决于要匹配的图像的类型以及图像及其匹配对在以下参数中的一个或多个中(a)比例：图像视图集合的至少两个元素具有不同的比例。(b)遮挡：是3D世界中空间分离的两个对象可能在投影的2D图像平面中相互干扰的概念。(c)方向：图像视图相对于彼此旋转(d)Af fine Transformation：是否是平面，纹理或边缘对象。(e)模糊：是静止图像或图像序列中快速移动物体（f）照明：照明的变化也是精确特征匹配的典型问题[1，2，3]。比较研究已经发表和可用的图像匹配算法方法的性能评估没有其他方面，如（时间，成本和功耗），但这项研究克服了目前的比较研究的一些限制，结合分析的算法使用不同的场景，以确定在何种情况下，他们将提供最佳的结果。 在[4]中，他们展示了如何计算精细区域检测器的可重复性测量，在[5]中，图像由一组用于索引的尺度不变点2. 相关工作在搜索2D建模文档的过程中，发现了大量解决早期特征检测和后验图像匹配的工作。大多数早期开发的实现似乎在某些有限的图像条件下工作得很好。这些作者的真正挑战是在任何图像下实现真正的不变特征检测，例如（a）一致性，检测到的位置应该对噪声，尺度，方向，杂乱，照明不敏感。(b)准确性，应尽可能接近正确的位置和特征进行检测;（c）速度，应足够快。一些研究集中在算法的应用上，如基于SIFT[6，7]，SIFT的拼接应用[8 - 11]和基于SIFT的交通标志识别[10]。Ke和Sukthankar[12]给出了SIFT和PCA-SIFT的一些比较。PCA非常适合表示关键点补丁，但观察到对配准误差敏感。在[13]中，作者使用了Fast-Hessian检测器，它比Hessian检测器更快更好。第3节将详细介绍这三种方法及其差异。数字图像识别的第一次尝试是基于颜色的算法（颜色直方图或颜色分布特征）。这种做法虽然有效，但有许多局限性。颜色直方图是成功的，快速检测颜色分布特征在任何给定的图像满足基本要求。但它在匹配大量图像时失败，并且不满足以下标准（一致性，准确性）[14]。数字图像识别的第二次尝试仅限于角和边缘的识别。特征检测的开始可以通过Harris和Stephen的工作以及后来被称为Harris Corner Detector的工作来跟踪。Harris成功地在任何给定的图像中检测出鲁棒的特征。但由于它只是检测角点，他的工作缺乏特征点的连通性，这是获得表面和物体等主要级别描述符的主要限制。在Harris角点检测器发表 近 十 年 后 ， 提 出 了 一 种 新 的 角 点 检 测 算 法 FAST（Features from Accelerated Segment Test）。数字图像识别的第三次尝试仅限于从具有杂乱背景的纹理图像中实现可靠的图像匹配。在此之前，重要的是要知道，基于特征的算法已被广泛用作特征点检测器，因为颜色，角和边缘分别对应于具有高信息含量的图像颜色和位置，这意味着它们可以在图像之间匹配。但是基于特征的检测器仅在待匹配的对象具有相同的颜色或可区分的角或边缘时才能准确地执行。然而，当图像受到颜色分布、尺度、照明、旋转或模糊变换的变化时，基于特征的算法的性能不如预期为了克服这些局限性，同时提出了一类新的图像匹配算法.这些算法被称为基于纹理的算法，因为它们能够匹配不同图像之间的特征，尽管存在纹理背景并且缺乏平面和良好定义的边缘。大卫·洛（David Lowe）是这种新颖方法的第一次尝试。Lowe[15]提出了SIFT（尺度不变特征变换），用于从图像中提取不同的不变特征，这些特征可以对图像尺度和旋转保持不变[10，15，16]。然后它被广泛应用于图像拼接，识别，检索等。在Lowe，Ke和Sukthankar使用PCA（主成分分析-SIFT）来归一化梯度块而不是直方图之后[12]。他们表明，基于PCA的局部描述符也是独特的，对图像变形具有鲁棒性。但鲁棒特征提取的方法仍然很慢。Bay等人SURF（加速鲁棒特征），并使用积分图像进行图像卷积和Fast-Hessian检测器[13]。他们的实验证明，它更快，而且效果很好。图像低层特征提取算法的比较研究1773. 图像低层特征提取算法3.1. 基于算法3.1.1. 颜色直方图（颜色检测器）颜色直方图是图像中颜色分布的表示。对于数字图像，颜色直方图表示在图像的颜色空间（所有可能颜色的集合）中的每个固定颜色范围列表中具有颜色的像素数量颜色直方图是一种灵活的结构，可以从各种颜色空间中的图像构建，无论是RGB还是任何维度的任何其他颜色空间[14，17]。直方图分类的主要缺点是表示依赖于所研究对象的颜色，忽略了其形状和纹理。对于具有不同对象内容的两个图像，颜色直方图可能是相同的，这两个图像恰好共享颜色信息。相反，在没有空间或形状信息的情况下，仅基于颜色组织图比较，不同颜色的相似对象可能无法区分。赤白杯与赤白盘，莫辨。换句话说，基于直方图的算法没有通用“杯子”的概念3.1.2. 角点检测器基于SUSAN（最小单值分段同化核）角点标准的FAST（加速分段测试特征）算法[18]。对于特征检测，SUS-AN在要测试的像素（核）上放置一个圆形掩模.掩模的区域是M，并且该掩模中的像素由m表示，并且使用比较函数将每个像素与细胞核进行比较：.I不利用FAST，角点的检测优先于边缘，因为他们声称角点是最直观的特征类型之一，其显示出强烈的二维强度变化，因此与相邻点很好地区分开根据对基于上述标准（一致性，准确性和速度）的现有角点检测器的比较研究，发现大多数检测器满足其中一个标准，但在其他标准中失败[18]。3.2. 纹理算法3.2.1. SIFT检测器SIFT（尺度不变特征变换）由四个主要阶段组成：（a）尺度空间检测，（b）关键点定位，（c）方向分配和（d）关键点描述符。第一阶段使用高斯差分（DOG）函数来识别潜在的兴趣点[15]，这些兴趣点对尺度和方向不变。使用DOG代替高斯以提高计算速度[15，16，19]。D x; y;r v G x; y; kr- G x; y;rω I x; y1/4 Lx;y;kr-Lx;y;r 3其中I是卷积算子，G（x，y，r）是可变尺度高斯，I（x，y）是输入图像D（x，y，r）是具有k倍尺度的高斯微分。在关键点定位步骤中，它们被拒绝低对比度点并消除边缘响应。Hessian矩阵用于计算主曲率并消除主曲率之间的比率大于该比率的关键点。根据关键点周围区域内样本点的梯度方向形成方向直方图，以获得方向分配[15]。实验表明，采用4·4列直方图，每列8个方向面元，效果最好。所以其中t确定半径，并且指数的幂已经根据经验确定。SUSAN的面积由下式给出nMXCM2mM3.2.2. PCA-SIFT检测器PCA-SIFT（Principal Component Analysis-SIFT）是一种标准的SIFT算法，它是为了改进SIFT而出现的一种新算法，用于降维和消除计算量。图1快速SIFT步骤。Cummium-ð1Þ使用的SIFT描述符为4· 4· 8= 128维[7，10]。178M.M. El-gayar等人与Lowe的实现有关的成本[12]，它非常适合表示关键点补丁，并使我们能够将高维样本线性投影到低维特征空间中。换句话说，PCA-SIFT使用PCA而不是平滑加权直方图来归一化梯度补丁[12]。该特征向量明显小于标准SIFT特征向量，并且可以与相同的匹配算法一起使用。PCA-SIFT与SIFT一样，也使用欧几里得距离来确定两个向量是否对应于不同图像中的相同关键点。在PCA-SIFT中，输入向量是通过连接以关键点为中心的41·41块的水平和垂直梯度图创建的，该块具有2· 39· 39= 3042个元素[12]。图2测试中的示例图像根据PCA-SIFT，更少的组件需要更少的存储，并将导致更快的匹配。PCA-SIFT实现了将SIFT的匹配过程加速一个数量级的能力3.2.3. SURF探测器加速鲁棒特征检测器（SURF）的概念，以确保在三个特征检测步骤：检测，描述和匹配的高速。与PCA-SIFT不同，SURF加快了SIFT和SURF算法使用稍微不同的方法来检测特征。SIFT构建了一个图像金字塔，用递增的sigma值的高斯滤波每一层，并取其差值。另一方面，SURF创建了一个在关键点匹配步骤中，最近邻被定义为对于不变描述符向量具有最小欧几里得距离的关键点。Lowe使用了一种更有效的测量方法，该方法通过比较最近邻与第二近邻的距离来获得[15]。3.2.4. F-SIFT检测器F-SIFT（Fast-SIFT）由SIFT的相同的四个主要阶段组成：（a）尺度空间检测，（b）关键点定位，（c）方向分配和（d）关键点描述符和量化为视觉单词的特征向量，并且特征向量明显小于标准SIFT特征向量。每个视觉单词的频率然后被记录在如图1所示的空间平铺的每个平铺的直方图中。图像的最终特征向量是这些直方图的串联4. 实验和结果4.1. 评估测量评估度量是RANSAC（随机样本一致性），用于拒绝不一致的匹配。内点是在输入图像处具有正确匹配的点。我们的目标是同时获得内点和拒绝离群点[5]。如等式（4），算法从不选择全部为内点的m个点的集合的概率为1-p：表1特征检测（描述符）在时间上的比较affine变换问题。 使用图中的A组。 2、总时间是找到所有描述符的时间。快速F-SIFTPCA-siftSIFT冲浪总描述符（im1，img2）8140289346503316001600298241总时间（ms）92464420921530.5201132112611395表2Affine转换时间比较。使用图中的A组。 1，数据表示时间上每种方法的匹配总 数 。快速F-SIFTPCA-siftSIFT冲浪比赛总数8111150175298总时间（ms）99.438.430.552.859图像低层特征提取算法的比较研究179表3特征检测（描述符）比较时间尺度上的变化问题。使用图2的B组，总时间是找到所有描述符的时间。表4时间尺度变化比较。使用图1的B组，数据表示每个方法在时间上的匹配总数。快速F-SIFT PC A -SIFTSIFT冲浪总匹配81 99 20 136298总时间（ms） 14117 15.5 543.46表6旋转改变时间上的比较。使用组在图1的C中，数据表示每个方法在时间上的匹配总数。快速F-SIFTPCA-siftSIFT 冲浪总匹配79 237 200 662298总时间（ms） 15515 17 572.420快速F-SIFTPCA-siftSIFT冲浪总描述符（im1，img2）8178299352 504015601565298298总时间（ms）896658209225 30.529116311651111271-p¼ 11-wmk40其中m是估计模型所需的最少点数，k是所需样本数，w是RANSAC算法从输入数据中选择内点的概率。RANSAC重复地猜测从输入集合中随机抽取的对应模式的集合。我们可以认为内点是正确的匹配数。在以下实验中，匹配均值内点[19]。本文所采用的方法都是基于OPENCV和VL-feat。我们使用标准的图像数据集，其中包括一般的变形，如比例变化，视图变化，照明变化和旋转。如图2所示。所有实验均在1.8GHz、1.0GB RAM的笔记本电脑上进行，操作系统为Windows7.时间评价是一个相对的结果，它只能反映方法时间成本的变化趋势。图像的大小（512*512）和质量、图像类型（JPG）和算法参数（阈值= 1.5）等因素对结果有影响。4.2. 加工时间实验的第一部分展示了af-fine-transformationinvariant的性能。表1显示SURF是最快的，SIFT是最慢的，但它找到了大多数描述符，F-SIFT比SIFT快，比SURF找到更多的描述符。表2显示F-SIFT是最快的一种，SURF是最慢的，但它找到了大多数匹配。4.3. 处理时间第二个实验展示了尺度不变性的性能。表3显示SURF是最快的，SIFT是最慢的，但它找到了大多数描述符，F-SIFT比SIFT快，比SURF找到更多的描述符。表4示出了在匹配和时间上SURF优于F-SIFT4.4. 旋转随加工时间变化第三个实验展示了旋转操作的方法。 如图C所示。 1，图像旋转180度。表5显示，SURF是最快的一个，SIFT是最慢的，但它找到了大多数描述符，F-SIFT比SIFT更快，比SURF找到了更多的描述符表6显示，随着时间的推移，F-SIFT优于SURF，并且匹配几乎相等。4.5. 处理时间第四个实验使用高斯模糊，如图2的D组中的图像。模糊的半径更改为1.5。表7显示SURF是最快的，SIFT是最慢的，但它找到了大多数描述符，F-SIFT比SIFT快，比SURF找到更多的描述符，就像上面的实验一样。表8显示，随着时间的推移，PCA-SIFT最快，F-SIFT优于SURF，并且匹配几乎相等。4.6. 处理时间通过实验验证了这些方法的照明效果如图2的组G所示，从数据1到数据6，图像的亮度变得越来越低。表9显示，SURF是最快的一个，SIFT是最慢的，但它找到了大多数描述符，F-SIFT比SIFT更快，比SURF找到了更多的描述符。表10显示，随着时间和匹配，SURF最快，并且SURF优于F-SIFT。表10显示了照明变化的可重复性。SURF具有最大的重复性，F-SIFT显示出与SURF一样好的性能，这与[12，13]一致。4.7. 讨论表11和图3显示了所有实验的结果。它还表明，没有最好的方法，所有的变形。因此，我们认为，表5关于旋转变化问题的时间上的特征检测（描述符）比较。使用图2的C组，总时间是找到所有描述符的时间。快速F-SIFTPCA-siftSIFT冲浪总描述符（im1，img2）8179299310503915521552298294总时间（ms）53151620320430.529.311251127110109180M.M. El-gayar等人表7关于模糊变化问题的特征检测（描述符）时间比较。使用图2的组D，总时间是找到所有描述符的时间。快速F-SIFTPCA-siftSIFT冲浪总描述符（im1，img2）816299350503215001250298203总时间（ms）51651820322030.527.51127112511197表8时间模糊变化比较。使用组在图1的D中，数据表示每个方法在时间上的匹配总数。表10光照变化时间比较。使用图1的组E，数据表示每个方法在时间上的匹配总数。快速F-SIFTPCA-siftSIFT 冲浪快速F-SIFTPCA-siftSIFT冲浪共25场比赛19720683198共6场比赛22780688296总时间（ms）711815.55394总时间（ms）752112.558440在选择特征检测方法时，请确定最关心的性能是什么。这个实验的结果并不是在所有情况下都是恒定的。算法的变化可以得到一个新的结果，寻找最近的邻居，而不是KNN或使用改进的RANSAC。让 其结果如图1A所示。第三节：(a) SIFT检测到图像上最多的特征点。这是预料之中的，因为大量的纹理 这张照片（视觉欣赏）。另一方面，SIFT的检测率最低，图像5对应于黑线鳕船的第一个视图。这也证实了SIFT在纹理图像上测试时表现最高水平的假设。这也可以通过查看其他图像的结果来检查。(b) SURF也是一种基于纹理的匹配算法，但它似乎在纹理图像与光照变化混淆正因为如此，它没有最好的性能与这对。SURF检测到的特征最多的图像是SIFT检测到的特征较少的图像。这证明SIFTS和SURF是基于纹理的算法，当在平面图像上测试时不能很好地执行。(c) 与SIFT和SURF相反，F-SIFT在由黑线鳕船组成的一对中检测到更多的特征。虽然一般来说，F-SIFT检测到的特征量明显少于SIFT或SURF，但可以理解的是，如果选择了适当的图像集，则这种类型的算法（基于特征的）的最佳性能将得到增强。这是F-SIFT的意外结果，因为大量的但是这大概是因为砖的角和边缘处的低对比度和差的FAST在时间上看起来很好，在其他事情上看起来很糟糕。SIFT的匹配成功归因于其特征表示已被精心设计为对定位错误具有鲁棒性。如所讨论的，已知PCA对配准误差敏感。使用少量的维度在存储空间和匹配速度方面提供了显著的好处[11]。F-SIFT使用KD树来表示和索引描述符，具有SURF一样的良好稳定性。SURF算法在实验中表现出稳定性好、速度快的特点。SURF中使用的“Fast-Hessian”检测器比SIFT中使用的DOG检测器快3倍以上，比Hessian-Laplace检测器5. 结论和今后的工作本文对五种图像变形特征检测方法进行了评价SIFT速度慢，不擅长缩放变化，但它对旋转，照明变化和模糊变换保持不变。快速SIFT比普通SIFT速度快，在各个方面都表现得很好，但SIFT比快速SIFT性能更好。SURF算法具有SIFT算法的快速性和良好的性能，但对旋转和光照变化不稳定。得出的结论是，F-SIFT具有高于SIFT和SURF的最佳整体性能，但它遭受检测非常少的特征，因此匹配。建议通过创建一个提供匹配组件的新实现来改进此算法的属性。有必要通过增加它可以检测的特征量来改进F-SIFT。但应特别注意保持算法的鲁棒性，避免检测到无用的特征。这一领域的未来研究应侧重于测试表9关于照明变化问题的时间上的特征检测（描述符）比较。使用图2的组E，总时间为 找到所有描述符快速F-SIFTPCA-siftSIFT冲浪总描述符（im1，img2）8125299306503015521552298181总时间（ms）54152320419930.5251125112311491图像低层特征提取算法的比较研究181表11所有实验的结论。方法时序转换FAST通用通用SIFT坏的好的缩放共同利益旋转不良最好模糊坏最好照明不良最好PCA-sift好差坏共同共同坏F-SIFT最好的好最好好好好冲浪最好的最好好好好图3性能和时间图作为所有实验的结论。算法在检测场景中的单个对象时的准确性。摄影测量中许多新出现的需求都解决了这个问题，这项工作可能是迈向更深入研究的第一步同时，利用F-SIFT特征提取算法对语义技术进行了改进，消除了人类高层语义感知与图像底层特征之间的语义鸿沟。引用[1] 作者声明：J.局部描述符的性能评估。IEEE Trans Pattern AnalMach Intel2005;27（10）：1615-30.[2] 许Y，李K，李S.光照和摄像机不变立体匹配。计算机视觉模式识别CVPR 2008：1[3] 杨文龙，王文龙，王文龙.用于自动图像标注的整体第五届FTRA多媒体和普适工程国际会议;2011年。[4] [10] Mikolajczyk K，Tuytelaars T，Schmid C，Zisserman A，Matas J，Schaffalitzky F，Kadir T，Gool LV.一个比较的affine区域检测器。IJCV2006;65（1/2）：43-72。[5] 放大图片作者：Mikolajczyk K，Schmid C.基于尺度不变兴趣点的索引。在：第八届国际计算机视觉会议论文集; 2001年，p。 525- 31[6] 杨占龙，郭宝龙。基于SIFT的图像拼接。在：智能信息隐藏和多媒体国际会议，信号处理; 2009年。第1422[7] 萨尔吉安河使用局部描述符的对象识别。国际视觉计算研讨会.内华达州太浩湖; 2007年。p. 709-17[8] 布朗M，劳D。认出了阿汤哥。在：第九届国际计算机视觉会议论文集; 2003年，p。 1218- 27[9] 唐正元，吴一雷，何茂凯，王文宏。干涉条件下图像匹配的筛选描述子。机器学习和控制论国际会议。卷6; 2008年。p.3294-300[10] 许Y，李K，李S.光照和摄像机不变立体匹配。CVPR 2009：1[11] 高峰，魏少华，王学通。基于SIFT特征点的图像匹配算法。18.第18章：你是谁[12] Ke Y，Sukthankar R. PCA-SIFT：局部图像描述符的更独特的表示。在：计算机视觉和模式识别会议论文集; 2004年，p。511- 7[13] 杨伟，王伟，王伟. SURF：加速了强大的功能。2006年第九届欧洲计算机视觉会议[14] 李金霞，陈月红. SIFT特征提取算法在图像配准中的应用。在：第十届国际电子测量仪器会议IEEE; 2011。[15] 洛 湾 从 尺 度 不 变 的 关 键 点 中 提 取 独 特 的 图 像 特 征 。IJCV2004;60（2）：91-110。[16] 王X 。基于局部特征区域颜色直方图的鲁棒图像检索。Springer Netherlands; 2009.[17] Stokman H，Gevers T.图像特征检测中颜色模型的选择与融合。Pattern Anal Mach Intel IEEE TransMarch 2008;29：371-81.[18] 放大图片作者：Rosten E，Porter R，Drummond T.更快更好：角点检测的机器学习方法。IEEE跨模式肛门马赫英特尔2010;32：105-19.[19] 杨文，李文，李文.具有旋转不变快速特征的统一实时跟踪和识别在：IEEE计算机视觉和模式识别会议（CVPR）;2010年6月。