Feature detection (computer vision): Difference between revisions

Content deleted Content added
Cydebot (talk | contribs)
m Robot - Speedily moving category Feature detection to Category:Feature detection (computer vision) per CFDS.
Add R tags
 
(44 intermediate revisions by 37 users not shown)
Line 1:
#REDIRECT [[Feature (computer vision)#Detectors]]
{{multiple issues|
{{Rcatshell|
{{no footnotes|date=April 2013}}
{{R to section}}
{{essay|date=April 2013}}
{{R with history}}}}
}}
 
{{FeatureDetectionCompVisNavbox}}
 
In [[computer vision]] and [[image processing]] the concept of '''feature detection''' refers to methods that aim at computing abstractions of image information and making local decisions at every image point whether there is an [[image feature]] of a given type at that point or not. The resulting features will be subsets of the image ___domain, often in the form of isolated points, continuous curves or connected regions.
 
== Definition of a feature ==
 
There is no universal or exact definition of what constitutes a feature, and the exact definition often depends on the problem or the type of application. Given that, a feature is defined as an "interesting" part of an [[Digital image|image]], and features are used as a starting point for many computer vision algorithms. Since features are used as the starting point and main primitives for subsequent algorithms, the overall algorithm will often only be as good as its feature detector. Consequently, the desirable property for a feature detector is ''repeatability'': whether or not the same feature will be detected in two or more different images of the same scene.
 
Feature detection is a low-level [[image processing]] operation. That is, it is usually performed as the first operation on an image, and examines every [[pixel]] to see if there is a feature present at that pixel. If this is part of a larger algorithm, then the algorithm will typically only examine the image in the region of the features. As a built-in pre-requisite to feature detection, the input image is usually smoothed by a [[Gaussian blur|Gaussian]] kernel in a [[scale space|scale-space representation]] and one or several feature images are computed, often expressed in terms of local [[derivative]] operations.
 
Occasionally, when feature detection is [[computationally expensive]] and there are time constraints, a higher level algorithm may be used to guide the feature detection stage, so that only certain parts of the image are searched for features.
 
Many computer vision algorithms use feature detection as the initial step, so as a result, a very large number of feature detectors have been developed. These vary widely in the kinds of feature detected, the computational complexity and the repeatability. At an overview level, these feature detectors can (with some overlap) be divided into the following groups:
 
== Types of image features ==
 
=== Edges ===
 
Edges are points where there is a boundary (or an edge) between two image regions. In general, an edge can be of almost arbitrary shape, and may include junctions. In practice, edges are usually defined as sets of points in the image which have a strong [[gradient]] magnitude. Furthermore, some common algorithms will then chain high gradient points together to form a more complete description of an edge. These algorithms usually place some constraints on the properties of an edge, such as shape, smoothness, and gradient value.
 
Locally, edges have a one-dimensional structure.
 
=== Corners / interest points ===
 
The terms corners and interest points are used somewhat interchangeably and refer to point-like features in an image, which have a local two dimensional structure. The name "Corner" arose since early algorithms first performed edge detection, and then analysed the edges to find rapid changes in direction (corners). These algorithms were then developed so that explicit edge detection was no longer required, for instance by looking for high levels of [[curvature]] in the image gradient. It was then noticed that the so-called corners were also being detected on parts of the image which were not corners in the traditional sense (for instance a small bright spot on a dark background may be detected). These points are frequently known as interest points, but the term "corner" is used by tradition.
 
=== Blobs / regions of interest or interest points ===
 
Blobs provide a complementary description of image structures in terms of regions, as opposed to corners that are more point-like. Nevertheless, blob descriptors often contain a preferred point (a local maximum of an operator response or a center of gravity) which means that many blob detectors may also be regarded as interest point operators. Blob detectors can detect areas in an image which are too smooth to be detected by a corner detector.
 
Consider shrinking an image and then performing corner detection. The detector will respond to points which are sharp in the shrunk image, but may be smooth in the original image. It is at this point that the difference between a corner detector and a blob detector becomes somewhat vague. To a large extent, this distinction can be remedied by including an appropriate notion of scale. Nevertheless, due to their response properties to different types of image structures at different scales, the LoG and DoH [[blob detection|blob detectors]] are also mentioned in the article on [[corner detection]].
 
=== Ridges ===
 
For elongated objects, the notion of ''ridges'' is a natural tool. A ridge descriptor computed from a grey-level image can be seen as a generalization of a medial axis. From a practical viewpoint, a ridge can be thought of as a one-dimensional curve that represents an axis of symmetry, and in addition has an attribute of local ridge width associated with each ridge point. Unfortunately, however, it is algorithmically harder to extract ridge features from general classes of grey-level images than edge-, corner- or blob features. Nevertheless, ridge descriptors are frequently used for road extraction in aerial images and for extracting blood vessels in medical images—see [[ridge detection]].
 
== Feature detectors ==
 
{| class="wikitable"
|+ Common feature detectors and their classification:
!Feature detector!![[Edge detection|Edge]]!![[Corner detection|Corner]]!![[Blob detection|Blob]]
|-
| [[Canny edge detector|Canny]]
| X
|
|
|-
|-
| [[Sobel operator|Sobel]]
| X
|
|
|-
|-
|[[Corner detection#The Harris & Stephens / Plessey corner detection algorithm|Harris & Stephens / Plessey]]
| X
| X
|
|-
|[[Corner detection#The SUSAN corner detector|SUSAN]]
| X
| X
|
|-
|[[Corner detection#The Shi and Tomasi corner detection algorithm|Shi & Tomasi]]
|
| X
|
|-
|[[Corner detection#The level curve curvature approach|Level curve curvature]]
|
| X
|
|-
|[[Features from accelerated segment test|FAST]]
|
| X
| X
|-
|[[Blob detection#The Laplacian of Gaussian|Laplacian of Gaussian]]
|
| X
| X
|-
| [[Difference of Gaussians]]
|
| X
| X
|-
|[[Blob detection#The determinant of the Hessian|Determinant of Hessian]]
|
| X
| X
|-
| [[MSER]]
|
|
| X
|-
| [[Principal Curvature-Based Region Detector|PCBR]]
|
|
| X
|-
| [[Blob detection#Grey-level blobs, grey-level blob trees and scale-space blobs|Grey-level blobs]]
|
|
|X
|}
 
== Feature extraction ==
 
Once features have been detected, a local image patch around the feature can be extracted. This extraction may involve quite considerable amounts of image processing. The result is known as a feature descriptor or feature vector. Among the approaches that are used to feature description, one can mention [[N-jet]]s and local histograms (see [[scale-invariant feature transform]] for one example of a local histogram descriptor). In addition to such attribute information, the feature detection step by itself may also provide complementary attributes, such as the edge orientation and gradient magnitude in edge detection and the polarity and the strength of the blob in blob detection.
 
== See also ==
* [[Feature learning]]
* [[Vectorization (image tracing)]]
 
== References ==
 
*{{cite journal
| author=T. Lindeberg
| title=Scale-space
| journal=Encyclopedia of Computer Science and Engineering ([[Benjamin Wah]], ed), John Wiley and Sons
| volume = IV
| pages = 2495–2504
| year = 2008/2009
| doi=10.1002/9780470050118.ecse609
| url = http://www.nada.kth.se/~tony/abstracts/Lin08-EncCompSci.html
}} (summary and review of a number of feature detectors formulated based on a scale-space operations)
*{{Cite journal|last=Canny|first=J.|author-link=John Canny|title=A Computational Approach To Edge Detection|journal=IEEE Trans. Pattern Analysis and Machine Intelligence|volume=8|pages=679–714|year=1986|doi=10.1109/TPAMI.1986.4767851|issue=6}}. ([[Canny edge detector|Canny edge detection]])
* {{cite conference
| author=C. Harris and M. Stephens
| title=A combined corner and edge detector
| booktitle=Proceedings of the 4th Alvey Vision Conference
| pages=pages 147–151
| year=1988
| url=http://www.csse.uwa.edu.au/~pk/research/matlabfns/Spatial/Docs/Harris/A_Combined_Corner_and_Edge_Detector.pdf
|format=PDF}}(Harris/Plessey corner detection)
*{{cite journal
| author=S. M. Smith and J. M. Brady
| title=SUSAN - a new approach to low level image processing
| url=http://citeseer.ist.psu.edu/smith95susan.html
| journal=International Journal of Computer Vision
| volume=23
| pages=45–78
|date=May 1997
| doi=10.1023/A:1007963824710
| issue=1
}}(The SUSAN corner detector)
* {{cite conference
| author=J. Shi and C. Tomasi
| title=Good Features to Track,
| publisher=Springer
|date=June 1994
| booktitle=9th IEEE Conference on Computer Vision and Pattern Recognition
| url=http://citeseer.ist.psu.edu/shi94good.html
}}(The Shi and Tomasi corner detector)
*{{cite conference
| author=E. Rosten and T. Drummond
| title=Machine learning for high-speed corner detection
| booktitle=European Conference on Computer Vision
| publisher=Springer
| pages=430–443
| year=2006
| id = {{citeseerx|10.1.1.60.3991}}
| doi=10.1007/11744023_34
}}(The FAST corner detector)
* {{cite journal
| author=T. Lindeberg
| title=Feature detection with automatic scale selection
| journal=International Journal of Computer Vision
| year=1998
| volume=30
| issue=2
| pages=pp 77–116
| url=http://www.nada.kth.se/cvap/abstracts/cvap198.html
| format=abstract
| doi=10.1023/A:1008045108935
}}(Laplacian and determinant of Hessian blob detection as well as automatic scale selection)
* {{cite journal
| author=D. Lowe
| title=Distinctive Image Features from Scale-Invariant Keypoints
| journal=International Journal of Computer Vision
| year=2004
| url=http://citeseer.ist.psu.edu/654168.html
| doi=10.1023/B:VISI.0000029664.99615.94
| volume=60
| pages=91
| issue=2
}}(DOG blob detection with automatic scale selection)
*{{cite conference
| author=J. Matas, O. Chum, M. Urban and T. Pajdla
| title=Robust wide baseline stereo from maximally stable extremum regions
| booktitle=British Machine Vision Conference
| year=2002
| pages=384–393
| url=http://cmp.felk.cvut.cz/~matas/papers/matas-bmvc02.pdf
|format=PDF}}(The MSER blob detector)
* {{cite journal
| author=T. Lindeberg
| title=Detecting Salient Blob-Like Image Structures and Their Scales with a Scale-Space Primal Sketch: A Method for Focus-of-Attention
| journal=International Journal of Computer Vision
| year=1993
| volume=11
| issue=3
| pages=pp 283–318
| url=http://www.nada.kth.se/~tony/abstracts/Lin92-IJCV.html
| doi=10.1007/BF01469346
| format=abstract
}}(Grey-level blob detection and scale-space blobs)
*R. Haralick, "Ridges and Valleys on Digital Images," Computer Vision, Graphics, and Image Processing vol. 22, no. 10, pp. 28–38, Apr. 1983. (Ridge detection using facet model)
*J. L. Crowley and A. C. Parker, "A Representation for Shape Based on Peaks and Ridges in the Difference of Low Pass Transform", IEEE Transactions on PAMI, PAMI 6 (2), pp 156–170, March 1984. (Ridge detection based on DOGs)
*D. Eberly, R. Gardner, B. Morse, S. Pizer, C. Scharlach, Ridges for image analysis, Journal of Mathematical Imaging and Vision, v.4 n.4, p. 353-373, Dec. 1994. (Fixed scale ridge detection)
* {{cite journal
| author=T. Lindeberg
| title=Edge detection and ridge detection with automatic scale selection
| journal=International Journal of Computer Vision
| year=1998
| volume=30
| issue=2
| pages=pp 117–154
| url=http://www.nada.kth.se/cvap/abstracts/cvap191.html
| doi=10.1023/A:1008097225773
| format=abstract
}}(Ridge detection with automatic scale selection)
 
[[Category:Feature detection (computer vision)|*]]