简介

一个Object可以通过occluding contour，从background中分离出来。一方面，pixel位于object上，另一方面，pixel在background上。发现occluding contour是一个很重要的挑战，因为object的outline是由occluding contour形成的。我们期待，occluding contour拥有图像亮度的sharp changes。除此之外，还有其他重要的原因可导致图像亮度的sharp changes。除了sharp changes in occluding contour，还包括sharp changes in albedo (反照率），sharp Changes in surface orientation, 或者sharp changes in illumination。每一个都可以提供定义object的information。Occluding Contour承载着 shape information，sharp changes in albedo承载着 texture information，illumination changes告诉你where the sun is。所有的这些意味着image intensity的sharp changes值得关注与推敲。

Sharp changes in brightness会产生large image gradients。首先我们描述了提取image gradient的common method，一种重要的gradient的用处是发现edge或者edge point，其亮度改变极其剧烈。对于edge，图像gradient很大，但是方向基本保持一致。但是在corners，图像梯度矢量在方向上swing sharply（swing是摇摆的意思）。除了edge，corner 也很重要，因为他们很容易 match from image to image. 在corner，我们可以看到strong image gradient的变化，这种cue会产生corner detector。如果我们描述一个neighborhood around a corner, 我们可以match description across images。Such matching is an important basic subroutine in computer vision。其应用包括：estimate能产生图像重叠的homography（因此形成mosaic)；估计fundamental matrix；从multiple view重建3D points。我们必须在neighborhood中发现一个natural size。这个neighborhood中，寻找一个能最佳描述local gray level的blob。一旦我们拥有了这个neighborhood，有两种natural construction来present邻域的orientation field。（SIFT和HOG是两种自然的construction）。The resulting feature yield well-behaved matchers。

Computing the image gradient

derivative estimate可以用finite difference来表达。Image noise可能会导致pixel并不look like他的neighbor pixel，以至于simple finite difference倾向于give response to噪声（give response to受噪声影响）。As a result，对x和y方向taking one finite difference 给出了一个noisy gradient estimate。Deal with这个问题的方法是smooth the image，然后differentiate it。最常见的noise model是additive stationary Gaussian noise model，而每个pixel会添加一个符合Gaussian probability distribution的噪声值。这个distribution总是拥有zero mean，standard deviation是一个该模型的参数。这个model倾向于描述camera的thermal noise。Contour of an object可能会产生具有较大梯度的 a long chain of points。另外一个example，一个corner通常包含many tens of pixels。如果noise在每个像素上都是independent并且additive，由noise产生的large derivative只是local event. 在differentiate之前，smooth image会在单个像素的尺度上suppress noise（suppress noise 经典用法，抑制噪声）。但是，由multiple pixel尺度上的noise产生的gradient变化则很难smooth out。

Derivative of Gaussian Filters

Smooth image 然后 differentiate等同于convolve with derivative of smoothing kernel。（Smoothing an image and then differentiating it is the same as convolving it with the derivative of a smoothing kernel）首先，differentiation是linear并且shift invariant。公式推导证明我们只需要convolve with the derivative of the Gaussian，而不是convolv with the Gaussian and then differentiate。Derivative filters looks like the effects they intended to detect。x derivative filter看起来像vertical light bolb，而紧邻着vertical dark blob。Standard deviation通常被称为scale of the smoothing。Scale拥有一个substantial effect on the response of a derivative filter。如果filter scale小于constant background上的bar，这个filter会在bar的两边有所相应。我们可以resolve the rising edge and falling edge of the bar。如果filter width更宽，bar可以smooth into background, the bar并没有产生或者很少产生response。

Gradient-based edge dector

Image gradient主要有两种重要的representation。第一是计算 edges，edges在亮度上有fast changes。这些通常被看作magnitude of gradient是extremal的点(梯度幅度的极值点就是edge)。 第二个是使用gradient orientation，这largely independent of illumination intensity。Sharp changes in image intensity通常位于image上的curves，这就是edges，而这些curve就是由edge point组成的（edge point是一个term, are made up of）。很多effect可以产生edge，尽管并不guarantee产生这些effect。举个例子，object可能与background有同样的intensity，这种情况下occluding contour可能不会产生edge。这意味着interpreting edge point会很困难。尽管这样，他们worth finding。在大多数的寻找edge的方法，都是先计算gradient magnitude。沿着a thick trail(足迹、小径)，gradient 呈现较大的 magnitude。但是 occluding contour实际上是curve，因此我们必须从一系列的distinctive points(区别性的点，edge point就是distinctive point)来obtain a curve。Gradient magnitude可以被认为是 a chain of low hills。Making local maxima会标记isolated points，或者叫小山顶。一个更好的criteria是沿着maximal magnitude进行slice。这会得到类似皇冠明珠的a chain of points。Each point可以用来predict下一个点的 location. 下一个点的位置会roughly at right angle。Forming these chain被称作nonmaximum suppression（非极大值抑制算法）。在一个finer resolution上identify the location of these chain会相对更加直接。很多个chain接近于合理的representation of object boundaries。事实上，这是因为我们已经标记gradient magnitude的maxima，而没有考虑how large这些maxima。更常见的是apply a threshold test来确保maxima比一些lower bound要大。相反，这会导致broken edge curves。The usual trick来解决这个问题是使用hysteresis。我们设定两个threshold，开始edge chain的时候refer to the larger threshold，follow以后的点的时候refer to the smaller threshold。这种trick会给出improve效果的dedge output。Most current edgefinders follow these lines。

Orientation

当light更加的brighter或者darker，image会更加的brigher或者darker。这可以represent as图像的scaling。The magnitude of the gradient会随着image而尺度变化。 这会对edge detector提出新的挑战，因为当image gradient远高或者低于threshold时候，edge points可能会appear或者disappear。一个解决的方法是represent图像梯度的orientation，这不会受到scalling的影响。 The gradient orientation依靠smoothing scale at which gradient was computed。Orientation field can be quite characteristic of particular textures。我们会使用这个重要的property来解决以下的more complex feature。这就是发现角点和构建临窗(finding corners and building neighborhood)。

Finding Corners and Building Neighborhoods

值得matching的points往往是corners，因为corners可以被localized，我们可以知道where a corner is。因此产生了一个叫做interest point的general term，interest point经常用来描述corner。放置一个小的window在一个constant value的patch上 (patch翻译成中文是片段的意思)。如果你在任意方向上translate the window，the image in the window不会有change significantly。这意味着你不能从gray level得出window location的reliable estimate。Similarly，如果你translate window up and down (translate是移动的意思），the image in the window并没有改变，所以你不能estimate location along the edge。（这就是著名的aperture problem，孔径问题)。如果包含corner，任何的movement of the window都会改变the image in the window。（这也意味着patch of image around corner不是self-similar)。因此你可以估计the location of the corner。但是corner并不是唯一的拥有这个property的local image structure。有很多种方式可以representing一个interesting corner附近的neighborhood。方法根据what might happen to the neighborhood来进行变化。我们假设neighborhood只被translated, rotated, and scaled，without loss of generality我们假设patches是circular。我们必须estimate the radius of the circule。

Finding Corners

一种发现corner的方式是发现edges，然后walk the edge寻找corner.这种方法会work poorly，因为edge detector通常会fail at corners。在sharp corner或者unfortunately oriented corners, 很难进行梯度估计。因为smoothing region cover the corner。在corner，我们期待两个重要的effects。首先必须有large gradient。第二在small neighborhood，the gradient orientation必须swing sharply。我们可以通过looking at variation in orientation来identify corners。H matrix给出一个behavior of orientation in a window的好的idea。如果是一个constant gray level的window，这个matrix的两个eigenvalue都非常小，因为matrix中的所有term都很小。在edge window（存在edge的image window），we expect看到一个large eigenvalue associated with gradient at the edge，以及一个由于few gradient in other direction所导致的small eigenvalue。但是在corner window（存在corner的image window），两个eigenvalue都比较大。The local maxima 通过一个threshold来进行测试，这个测试是否product of the eigenvalue比square of the average要大。 Large和local maximal value可以imply that the eigenvalue都比较大。Harris corner detector 可以测试是否product of the eigenvalue大于the square of average。Locally maximal value表明不同方向的eigenvalue都更大。这便是我们期待的，这个detector不受translation和rotation的影响（Window的移动和旋转都不影响检测出corner）。

Using scale and orientation to build a neighborhood

把一个corner变成image neighborhood，我们必须estimate the radius of the circular patch。当图像更大的时候，radius estimate应该正比关系变得更大。举个例子，一个2倍的scaled 图像，我们的方法应该得到两倍大小的the estimate of patch radius。我们可以以一个固定appearance的blob来定位corner。然后选择scale，从而绘制最佳的fitting blob。一个有效的方式是使用Laplacian of Gaussian filter.在Laplacian变换之前smooth image是非常自然地。注意Laplacian是线性operator, 这意味着我们可以把Laplacian变换看作convolve with kernel。Smooth an image然后应用Laplacian变换等同于convolve the image与smooth kernel的Laplacian变换。想象在patch的中心，应用smoothed Laplacian operator。我们已经establish，在一个特定的点，我们通过选择local maximum，得到一个covariant scale estimate。Corner detector倾向于产生neighborhood。Laplacian of Gaussian方法产生中心估计不是十分准确的neighborhood，但是scale estimate将更好。这将对large change of scale的matching problem非常有用。As we have seen，orientation histogram是一个image patches的自然表达。但是，我们不能在image coordinate上表达orientation。因为the patch我们matching的已经被旋转了。我们需要reference orientation，使得所有的angle可以可以被量测。一个自然的reference orientation是最common的orientation in the patch。我们计算gradient orientation的histogram，发现the largest peak。这个peak就是reference orientation for the patch。如果在same magnitude上有两个peaks，我们make multiple copies of the patch。

Describing Neighborhoods With SIFT And HoG Features

我们知道center, radius, 和 a set of image patch的方向。方向应该提供一个good representation。不同的texture倾向于有不同的orientation field。这pattern of orientation在不同的parts of the patch可能有巨大的不同。我们的representation应该会对small errors in center, radius, orientation of patch，因为不太可能准确的estimate。你应该think of these neighborhood由pattern elements组成。在这个case中，pattern elements会是orientation，但是其他种类的pattern elements也要求符合下列的trick。这就是如果element在neighborhood内move around（因为不太可能发现right center），只要大多数elements在right place上， neighborhood拥有right properties。我们必须build  feature， 让他能够不受rearrangement的影响，不论是否正好present在正确的位置上。最明显的方法是用histogram来represent neighborhood。但是这也会confuse too many pattern with one another。举个例子，所有的vertical strips的neighborhood都会mixed up。最自然的方法是take histogram locally, within subpatches of the neighborhood。这会yield一个重要的feature construction: SIFT.

SIFT Features

我们可以计算一个不受translation，rotation, scale等影响的representation。对于每个patch，我们通过translate the center to origin来rectify the patch，通过rotateorientation direction使其沿着x-axis，通过scale the neighborhood让其radius为1。我们rectified的patch的任何representation，都会invariant to translation，rotation，and scale。尽管我们不需要rectify in practice，相反，我们在each step 计算description时进行rectification。A SIFT descriptor(Scale Invariant Feature Transform) is constructed out of image gradients, and uses both magnitude and orientation. 这个descriptor通过归一化来抑制光照亮度引起的改变。 这种descriptor是一组image gradient的histogram组成。这些histogram揭露了图像梯度的general spatial trend但是suppress detail。举个例子，如果我们estimate the center, scale, or orientation of the patch有任何轻微的错误，the rectified patch就会shift slightly。As a result，simply recording the gradient 在每个点 会导致representation在不同的instance下不停的变换。A histogram of gradient反而会对这些改变非常robust。我们histogram local average of image gradient（histogram可以作为动词）。标准的SIFT descriptor通过divide the rectified patch into a nXn grid来获得。我们然后subdivide 每个grid element（网格单元） into mXm subgrid of subcell(subcell的subgrid)。在每个subcell的中心，我们计算gradient estimate。The gradient estimate 通过在cell中心的 weighted average of gradient来获得。这意味着gradient make contribution to more than one subcell，以至于small error in the location of the center会导致samll change in the descriptor。我们使用这些graident estimate来产生histogram。 每个grid element都拥有q-cell orientation histogram。

HOG Feature

HOG Feature(For Histogram of Gradient Orientations) 是一个重要的variant of SIFT feature。再一次，我们histogram gradient orientation in cells，但是adjust the process to try and identify high-contrast edges。我们可以通过count gradient orientation with weights 来 recover contrast information。这意味着，不是normalize gradient contribution over the whole neighborhood，我们normalize with respect to nearby gradient only。Normalization 可能 occur on a grid of cells that is different from the orientation subgrid。A single gradient location可能会贡献于许多不同的histogram，normalized in somewhat different way，这意味着我们会相对不太可能miss boundaries that have low contrast。