Feature detection and matching

1. Points and Patches(Feature detectors, Feature descriptors, Feature matching, Feature tracking, Application:performance driven animation). 2. Edges(Edge detection, Edge linking, Application: Edge editing and enhancement) 3. Lines(Successive approximation, Hough transform, Vanishing points, Application: Retangle detection).  

Introduction

一系列的的feature detectors和descriptor可以用来分析，描述和匹配images。这包括point-like interest operators，region like interest operators，edges operators，straight lines。Feature detection和matching是一个计算机视觉应用上的essential component。对于有的image pair，我们想align两幅图像，使他们无缝的stich into一个composite mosaic。 对于第另外一些image pair，我们想要建立a set of correspondence，这样3dmodel可以被构建，或者in-between view可以产生。 在这两种case下，不同的feature被detect和match，从而实现alignment或者产生一组correspondence。第一种feature是图像上的特定的location（第一种是keypoint feature)，比如mountain peaks，building corners，doorways，或者shaped patches of snow。这种localized feature通常被称为keypoint feature或者interest points，通常用point location附近的patches来描述。另外一种重要的特征是edges(第二种是edges features)，比如a profile of mountain。这种feature可以基于orientation和local appearance来匹配，这也是一个object boundaries和occlusion events的indicators。Edge可以分为longer curves和straight line segments，这可以直接matched或者analyzed来发现vanishing points。这一章我们重在描述一些practical approaches，来检测这些features并讨论如果在不同的images间建立feature correspondences。Keypoint feature在一系列的application中使用，Edges和Line提供的信息适用于描述object boundaries和man-made objects。

PCA-SIFT

Inspired by SIFT, Ke提出了一个更简单的方式来计算descriptor。它通过39*39的patch，计算x和y方向上的derivative，但是通过Principal Component Analysis（PCA），使得产生的Vector由3042维减少到36维。另外一个popular的SIFT的variant是SURF，它使用box filter来近似SIFT中使用的derivative和integral。

Feature Matching

一旦我们已经从两个或多个图像中extract features和descriptor，下一步就是在这些图像间establish初步的feature matches。（Once...）In this section，我们divide这个问题into两个separate component。（divide into... split into）。第一步是选择matching strategy，这决定了哪些correspondence会被pass到下一个阶段进行后续处理。第二步是devise有效的data structures和algorithm，来进行matching。（devise设计相处发明，design）。

Matching Strategy and error rates

Matching Strategy 很大程度上取决于 context。如果我们给定的两幅图像由很大程度的overlap，那么一副图像上的most features很可能与另外一个图像上的most feature 匹配。除了少部分由于occlude或者appearance改变太多，而不能匹配。 相反，如果我们想要recognize在cluttered scene中有多少known objects，大多数的feature不能匹配。除此之外，大量的potentially matching object需要检索出来，而这需要更有效地strategies。To begin with，我们假设feature descriptor已经可以直接使用Euclidean distancel(vector magnitude)来进行ranking potential matches。通常的流程需要把transform feature vector到new scaled basis。这就是whitening，在eigenface-based face recognition中经常用到。

给定一个Euclidean distance metric，最简单的matching strategy就是设定threshold。（set a threshold) 返回所有的不超过threshold的matches。设置太高的threshold，会产生很多的false positive，即 incorrect matches being returned。设置太低的threshold，会产生很多的false negatives，即correct matches被missed。

我们可以count正确匹配，错误匹配，来quantify匹配算法的性能（quantify the performance）。理想的，这些threshold可以自适应于feature space的不同区域。如果有足够的training data，it is sometimes possible 对不同的feature学习到不同的threshold。

Efficient Matching

一旦我们已经决定了matching strategy，我们任然需要在potential candidate中有效地寻找陪准点。发现corresponding feature point的最简单办法是对比该幅图像的feature和另外图像的所有feature。但是，这种方法 is quadratic in the number of extracted feature。（in the number of ....) 这在大多数application都不practical。

一个更好的方法是devise一个indexing structure，例如一个multi-dimensional search tree或者hash table，来快速search for与给定的feature接近的feature。