View source for Scale-invariant feature operator

{{Short description|Algorithm to detect local features in images}}
{{orphan|date=January 2019}}
{{Feature detection (computer vision) navbox}}
In the fields of [[computer vision]] and [[image analysis]], the '''scale-invariant feature operator''' (or '''SFOP''') is an algorithm to [[Feature detection (computer vision)|detect local features]] in images. The algorithm was published by Förstner et al. in 2009.<ref name=foerstner2009 />

==Algorithm==
The scale-invariant feature operator (SFOP) is based on two theoretical concepts: 
*'''spiral model'''<ref name="biguen1990"/>
*'''feature operator'''<ref name="foerstner1994"/>

Desired properties of keypoint detectors:
* '''Invariance and repeatability''' for object recognition
* '''Accuracy''' to support camera calibration
* '''Interpretability''': Especially '''corners and circles''', should be part of the detected keypoints (see figure).
* As few '''control parameters''' as possible with clear semantics
* '''Complementarity''' to known detectors

'''scale-invariant corner/circle detector.'''

==Theory==
===Maximize the weight===
Maximize the weight <math>w</math>= 1/variance of a point <math>p</math>

 <math>w(\mathbf{p},\alpha,\tau,\sigma)=\left(N(\sigma)-2\right)\frac{\lambda_{min}(M(\mathbf{p},\alpha,\tau,\sigma))}{\Omega(\mathbf{p},\alpha,\tau,\sigma)}   </math>  

comprising:

'''1. the image model<ref name="biguen1990"/>'''
<gallery widths="250px" heights="250px" perrow="3" caption="Distance d of an edge from a reference point p in a spiral feature">
  File:ipb_FigModelJunction.png
  File:ipb_FigModelCircular.png
  File:ipb_FigModelSpiral.png
</gallery>

<math>
\begin{align}
\Omega(\mathbf{p},\alpha,\tau,\sigma)& =\sum_{n=1}^{N(\sigma)}[(\mathbf{q}_n-\mathbf{p})^T \mathbf{R}_{\alpha}\mathbf{\nabla}_T g(\mathbf{q}_n)]^2G_{\sigma}(\mathbf{q}_n-\mathbf{p}) \\
& =N(\sigma)\mathbf{tr}\left\{R_{\alpha}\mathbf{\nabla}_{\tau}\mathbf{\nabla}_{\tau}^TR_{\alpha}^T*\mathbf{p}\mathbf{p}^TG_{\sigma}(\mathbf{p})\right\} 
\end{align}
</math>

'''2. the smaller eigenvalue of the structure tensor'''
<math> 
\underbrace{M(\mathbf{p},\alpha,\tau,\sigma)}_{\text{structure tensor}}=\underbrace{G_{\sigma}(\mathbf{p})}_{\text{weighted summation}}*\underbrace{(R_{\sigma}\nabla_{\tau}\nabla_{\tau}^TR_{\sigma}^T)}_{\text{squared rotated gradients}}
</math>

===Reduce the search space===
Reduce the 5-dimensional search space by
*linking the differentiation scale <math>\tau</math> to the integration scale

:<math>\tau=\sigma/3</math>
*solving for the optimal <math>\hat \alpha</math> using the model
:<math>\Omega(\alpha) = a - b \cos(2 \alpha - 2 \alpha_0)</math>
*and determining the parameters from three angles, e. g.
:<math> \Omega(0^\circ), \Omega(60^\circ), \Omega(120^\circ)\quad \rightarrow \quad a, b, \alpha_0 \quad \rightarrow \quad \hat\alpha</math>
*pre-selection possible:
:<math> \alpha =  0^\circ \, \rightarrow \, \mbox{junctions}, \quad \alpha = 90^\circ \, \rightarrow \, \mbox{circular features}</math>

===Filter potential keypoints===

*non-maxima suppression over scale, space and angle

*thresholding the isotropy <math>\lambda_{2(M)}</math>:<br/>eigenvalues characterize the shape of the keypoint, smallest eigenvalue has to be larger than threshold <math>T_{\lambda}</math> <br/> derived from noise variance <math>V(n)</math> and significance level <math>S</math>:

:<math>T_\lambda(V(n), \tau, \sigma, S) = \frac{N(\sigma)}{16 \pi \tau^4} V(n) \chi^2_{2,S}</math>

==Algorithm==
[[File:ipb_algorithm.png|none|x400px|Algorithm]]

==Results==
===Interpretability of SFOP keypoints===
<gallery widths="160px" heights="160px" perrow="4" caption="Results of different detectors on a Siemens star ">
  File:ipb_siemens_fos.png|Sfop: junctions red, circular features cyan
  File:ipb_siemens_ebr.png|Edge-based Regions
  File:ipb_siemens_ibr.png|Intensity-based Regions
  File:ipb_siemens_mser.png|[[Maximally_stable_extremal_regions|MSER]]
  File:ipb_siemens_haraff.png|[[Harris_affine_region_detector|Harris affine]]
  File:ipb_siemens_hesaff.png|[[Hessian_affine_region_detector|Hessian affine]]
  File:ipb_siemens_sift.png|[[Scale-invariant_feature_transform#Scale-invariant_feature_detection|Lowe]]
</gallery>

==See also==

*[[Corner detection]]
*[[Feature detection (computer vision)]]

== References ==
<references>
<ref name="biguen1990">{{cite journal
 | author = Bigün, J.
 | title = A Structure Feature for Some Image Processing Applications Based on Spiral Functions
 | journal = Computer Vision, Graphics, and Image Processing
 | volume = 51
 | number = 2
 | pages = 166–194
 | year = 1990
 }}</ref>
<ref name="foerstner2009">{{cite book
 | doi=10.1109/ICCV.2009.5459458
| chapter=Detecting interpretable and accurate scale-invariant keypoints
| title=2009 IEEE 12th International Conference on Computer Vision
| pages=2256–2263
| year=2009
| last1=Forstner
| first1=Wolfgang
| last2=Dickscheid
| first2=Timo
| last3=Schindler
| first3=Falko
| isbn=978-1-4244-4420-5
| citeseerx=10.1.1.667.2530
}}</ref>
<ref name="foerstner1994">{{cite conference
 | author = Förstner, Wolfgang
 | title = A Framework for Low Level Feature Extraktion
 | book-title = European Conference on Computer Vision
 | volume = 3
 | pages = 383–394
 | location = Stockholm, Sweden
 | year = 1994
}}</ref> 
</references>

==External links==
* [http://www.ipb.uni-bonn.de/sfop/ Project website at University of Bonn]

[[Category:Applications of computer vision]]
[[Category:Learning in computer vision]]