<NME> covdet.c <BEF> /** @file covdet.c ** @brief Covariant feature detectors - Definition ** @author Karel Lenc ** @author Andrea Vedaldi ** @author Michal Perdoch **/ /* Copyright (C) 2013-14 Andrea Vedaldi. Copyright (C) 2012 Karel Lenc, Andrea Vedaldi and Michal Perdoch. All rights reserved. This file is part of the VLFeat library and is made available under the terms of the BSD license (see the COPYING file). */ /** <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @page covdet Covariant feature detectors @author Karel Lenc @author Andrea Vedaldi @author Michal Perdoch @tableofcontents <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @ref covdet.h implements a number of covariant feature detectors, based on three cornerness measures (determinant of the Hessian, trace of the Hessian (aka Difference of Gaussians, and Harris). It supprots affine adaptation, orientation estimation, as well as Laplacian scale detection. - @subpage covdet-fundamentals - @subpage covdet-principles - @subpage covdet-differential - @subpage covdet-corner-types <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @section covdet-starting Getting started <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> The ::VlCovDet object implements a number of covariant feature detectors: Difference of Gaussian, Harris, determinant of Hessian. Variant of the basic detectors support scale selection by maximizing the Laplacian measure as well as affine normalization. @code // create a detector object VlCovDet * covdet = vl_covdet_new(method) ; // set various parameters (optional) vl_covdet_set_first_octave(covdet, -1) ; // start by doubling the image resolution vl_covdet_set_octave_resolution(covdet, octaveResolution) ; vl_covdet_set_peak_threshold(covdet, peakThreshold) ; vl_covdet_set_edge_threshold(covdet, edgeThreshold) ; // process the image and run the detector vl_covdet_put_image(covdet, image, numRows, numCols) ; vl_covdet_detect(covdet) ; // drop features on the margin (optional) vl_covdet_drop_features_outside (covdet, boundaryMargin) ; // compute the affine shape of the features (optional) vl_covdet_extract_affine_shape(covdet) ; // compute the orientation of the features (optional) vl_covdet_extract_orientations(covdet) ; // get feature frames back vl_size numFeatures = vl_covdet_get_num_features(covdet) ; VlCovDetFeature const * feature = vl_covdet_get_features(covdet) ; // get normalized feature appearance patches (optional) vl_size w = 2*patchResolution + 1 ; for (i = 0 ; i < numFeatures ; ++i) { float * patch = malloc(w*w*sizeof(*desc)) ; vl_covdet_extract_patch_for_frame(covdet, patch, patchResolution, patchRelativeExtent, patchRelativeSmoothing, feature[i].frame) ; // do something with patch } @endcode This example code: - Calls ::vl_covdet_new constructs a new detector object. @ref covdet.h supports a variety of different detectors (see ::VlCovDetMethod). - Optionally calls various functions to set the detector parameters if needed (e.g. ::vl_covdet_set_peak_threshold). - Calls ::vl_covdet_put_image to start processing a new image. It causes the detector to compute the scale space representation of the image, but does not compute the features yet. - Calls ::vl_covdet_detect runs the detector. At this point features are ready to be extracted. However, one or all of the following steps may be executed in order to process the features further. - Optionally calls ::vl_covdet_drop_features_outside to drop features outside the image boundary. - Optionally calls ::vl_covdet_extract_affine_shape to compute the affine shape of features using affine adaptation. - Optionally calls ::vl_covdet_extract_orientations to compute the dominant orientation of features looking for the dominant gradient orientation in patches. - Optionally calls ::vl_covdet_extract_patch_for_frame to extract a normalized feature patch, for example to compute an invariant feature descriptor. <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @page covdet-fundamentals Covariant detectors fundamentals @tableofcontents <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> This page describes the fundamental concepts required to understand a covariant feature detector, the geometry of covariant features, and the process of feature normalization. <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @section covdet-covariance Covariant detection <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> The purpose of a *covariant detector* is to extract from an image a set of local features in a manner which is consistent with spatial transformations of the image itself. For instance, a covariant detector that extracts interest points $\bx_1,\dots,\bx_n$ from image $\ell$ extracts the translated points $\bx_1+T,\dots,\bx_n+T$ from the translated image $\ell'(\bx) = \ell(\bx-T)$. More in general, consider a image $\ell$ and a transformed version $\ell' = \ell \circ w^{-1}$ of it, as in the following figure: @image html covdet.png "Covariant detection of local features." The transformation or <em>warp</em> $w : \real^2 \mapsto \real^2$ is a deformation of the image domain which may capture a change of camera viewpoint or similar imaging factor. Examples of warps typically considered are translations, scaling, rotations, and general affine transformations; however, in $w$ could be another type of continuous and invertible transformation. Given an image $\ell$, a **detector** selects features $R_1,\dots,R_n$ (one such features is shown in the example as a green circle). The detector is said to be **covariant** with the warps $w$ if it extracts the transformed features $w[R_1],\dots, w[R_n]$ from the transformed image $w[\ell]$. Intuitively, this means that the &ldquo;same features&rdquo; are extracted in both cases up to the transformation $w$. This property is described more formally in @ref covdet-principles. Covariance is a key property of local feature detectors as it allows extracting corresponding features from two or more images, making it possible to match them in a meaningful way. The @ref covdet.h module in VLFeat implements an array of feature detection algorithm that have are covariant to different classes of transformations. <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @section covdet-frame Feature geometry and feature frames <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> As we have seen, local features are subject to image transformations, and they apply a fundamental role in matching and normalizing images. To operates effectively with local features is therefore necessary to understand their geometry. The geometry of a local feature is captured by a <b>feature frame</b> $R$. In VLFeat, depending on the specific detector, the frame can be either a point, a disc, an ellipse, an oriented disc, or an oriented ellipse. A frame captures both the extent of the local features, useful to know which portions of two images are put in correspondence, as well their shape. The latter can be used to associate to diagnose the transformation that affects a feature and remove it through the process of **normalization**. More precisely, in covariant detection feature frames are constructed to be compatible with a certain class of transformations. For example, circles are compatible with similarity transformations as they are closed under them. Likewise, ellipses are compatible with affine transformations. Beyond this closure property, the key idea here is that all feature occurrences can be seen as transformed versions of a base or <b>canonical</b> feature. For example, all discs $R$ can be obtained by applying a similarity transformation to the unit disc $\bar R$ centered at the origin. $\bar R$ is an example of canonical frame as any other disc can be written as $R = w[\bar R]$ for a suitable similarity $w$. @image html frame-canonical.png "The idea of canonical frame and normalization" The equation $R = w[\bar R_0]$ matching the canonical and detected feature frames establishes a constraint on the warp $w$, very similar to the way two reference frames in geometry establish a transformation between spaces. The transformation $w$ can be thought as a the **pose** of the detected feature, a generalization of its location. In the case of discs and similarity transformations, the equation $R = w[\bar R_0]$ fixes $w$ up to a residual rotation. This can be addressed by considering oriented discs instead. An **oriented disc** is a disc with a radius highlighted to represent the feature orientation. While discs are appropriate for similarity transformations, they are not closed under general affine transformations. In this case, one should consider the more general class of (oriented) ellipses. The following image illustrates the five types of feature frames used in VLFeat: @image html frame-types.png "Types of local feature frames: points, discs, oriented discs, ellipses, oriented ellipses." Note that these frames are described respectively by 2, 3, 4, 5 and 6 parameters. The most general type are the oriented ellipses, which can be used to represent all the other frame types as well. <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @section covdet-frame-transformation Transforming feature frames <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> Consider a warp $w$ mapping image $\ell$ into image $\ell'$ as in the figure below. A feature $R$ in the first image co-variantly transform into a feature $R'=w[R]$ in the second image: @image html covdet-normalization.png "Normalization removes the effect of an image deformation." The poses $u,u'$ of $R=u[R_0]$ and $R' = u'[R_0]$ are then related by the simple expression: \[ u' = w \circ u. \] <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @section covdet-frame-normalization Normalizing feature frames <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> In the example above, the poses $u$ and $u'$ relate the two occurrences $R$ and $R'$ of the feature to its canonical version $R_0$. If the pose $u$ of the feature in image $\ell$ is known, the canonical feature appearance can be computed by un-warping it: \[ \ell_0 = u^{-1}[\ell] = \ell \circ u. \] This process is known as **normalization** and is the key in the computation of invariant feature descriptors as well as in the construction of most co-variant detectors. <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @page covdet-principles Principles of covariant detection @tableofcontents <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> The goals of a co-variant detector were discussed in @ref covdet-fundamentals. This page introduces a few general principles that are at the basis of most covariant detection algorithms. Consider an input image $\ell$ and a two dimensional continuous and invertible warp $w$. The *warped image* $w[\ell]$ is defined to be \[ w[\ell] = \ell \circ w^{-1}, \] or, equivalently, \[ w[\ell](x,y) = \ell(w^{-1}(x,y)), \qquad \forall (x,y)\in\real^2. \] Note that, while $w$ pushes pixels forward, from the original to the transformed image domain, defining the transformed image $\ell'$ requires inverting the warp and composing $\ell$ with $w^{-1}$. The goal a covariant detector is to extract the same local features irregardless of image transformations. The detector is said to be <b>covariant</b> or <b>equivariant</b> with a class of warps $w\in\mathcal{W}$ if, when the feature $R$ is detected in image $\ell$, then the transformed feature $w[R]$ is detected in the transformed image $w[\ell]$. The net effect is that a covariant feature detector appears to &ldquo;track&rdquo; image transformations; however, it is important to note that a detector *is not a tracker* because it processes images individually rather than jointly as part of a sequence. An intuitive way to construct a covariant feature detector is to extract features in correspondence of images structures that are easily identifiable even after a transformation. Example of specific structures include dots, corners, and blobs. These will be generically indicated as **corners** in the followup. A covariant detector faces two challenges. First, corners have, in practice, an infinite variety of individual appearances and the detector must be able to capture them to be of general applicability. Second, the way corners are identified and detected must remain stable under transformations of the image. These two problems are addressed in @ref covdet-cornerness-localmax and @ref covdet-cornerness-normalization respectively. <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @section covdet-cornerness Detection using a cornerness measure <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> One way to decide whether an image region $R$ contains a corner is to compare the local appearance to a model or template of the corner; the result of this comparisons produces a *cornerness score* at that location. This page describe general theoretical properties of the cornerness and the detection process. Concrete examples of cornerness are given in @ref covdet-corner-types. A **cornerness measure** associate a score to all possible feature locations in an image $\ell$. As described in @ref covdet-frame, the location or, more in general, pose $u$ of a feature $R$ is the warp $w$ that maps the canonical feature frame $R_0$ to $R$: \[ R = u[R_0]. \] The goal of a cornerness measure is to associate a score $F(u;\ell)$ to all possible feature poses $u$ and use this score to extract a finite number of co-variant features from any image. <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @subsection covdet-cornerness-localmax Local maxima of a cornerness measure <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> Given the cornerness of each candidate feature, the detector must extract a finite number of them. However, the cornerness of features with nearly identical pose must be similar (otherwise the cornerness measure would be unstable). As such, simply thresholding $F(w;\ell)$ would detect an infinite number of nearly identical features rather than a finite number. The solution is to detect features in correspondence of the local maxima of the score measure: \[ \{w_1,\dots,w_n\} = \operatorname{localmax}_{w\in\mathcal{W}} F(w;\ell). \] This also means that features are never detected in isolation, but by comparing neighborhoods of them. <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @subsection covdet-cornerness-normalization Covariant detection by normalization <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> The next difficulty is to guarantee that detection is co-variant with image transformations. Hence, if $u$ is the pose of a feature extracted from image $\ell$, then the feature of pose $u' = w[u]$ must be detected in the transformed image $\ell' = w[\ell]$. Since features are extracted in correspondence of the local maxima of the cornerness score, a sufficient condition is that corresponding features attain the same score in the two images. \[ \forall u\in\mathcal{W}: \quad F(u;\ell) = F(w[u];w[\ell]), \qquad\text{or}\qquad F(u;\ell) = F(w \circ u ;\ell \circ w^{-1}). \] One simple way to satisfy this equation is to compute a cornerness score *after normalizing the image* by the inverse of the candidate feature pose warp $u$, as follows: \[ F(u;\ell) = F(1;u^{-1}[\ell]) = F(1;\ell \circ u) = \mathcal{F}(\ell \circ u). \] where $1 = u^{-1} \circ u$ is the identity transformation and $\mathcal{F}$ is an arbitrary functional. Intuitively, co-variant detection is obtained by looking if the appearance of the feature resembles a corner only *after normalization*. Formally: \[ F(w \circ u ;\ell \circ w^{-1}) = \mathcal{F}(1; \ell \circ w^{-1} \circ w \circ u) = \mathcal{F}(1; \ell\circ u) = F(w;\ell). \] Concrete examples of the functional $\mathcal{F}$ are given in @ref covdet-corner-types. <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @subsection covdet-locality Locality of the detected features <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> In the definition above, the cornenress functional $\mathcal{F}$ is an arbitrary functional of the entire normalized image $u^{-1}[\ell]$. In practice, one is always interested in detecting **local features** (at the very least because the image extent is finite). This is easily obtained by considering a cornerness $\mathcal{F}$ which only looks in a small region of the normalized image, usually corresponding to the extent of the canonical feature $R_0$ (e.g. a unit disc centered at the origin). In this case the extent of the local feature in the original image is simply given by $R = u[R_0]$. <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @section covdet-partial Partial and iterated normalization <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> Practical detectors implement variants of the ideas above. Very often, for instance, detection is an iterative process, in which successive parameters of the pose of a feature are determined. For instance, it is typical to first detect the location and scale of a feature using a rotation-invariant cornerness score $\mathcal{F}$. Once these two parameters are known, the rotation can be determined using a different score, sensitive to the orientation of the local image structures. Certain detectors (such as Harris-Laplace and Hessian-Laplace) use even more sophisticated schemes, in which different scores are used to jointly (rather than in succession) different parameters of the pose of a feature, such as its translation and scale. While a formal treatment of these cases is possible as well, we point to the original papers. <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @page covdet-differential Differential and integral image operations @tableofcontents <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> Dealing with covariant interest point detector requires working a good deal with derivatives, convolutions, and transformations of images. The notation and fundamental properties of interest here are discussed next. <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @section covdet-derivatives Derivative operations: gradients <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> For the derivatives, we borrow the notation of @cite{kinghorn96integrals}. Let $f: \mathbb{R}^m \rightarrow \mathbb{R}^n, \bx \mapsto f(\bx)$ be a vector function. The derivative of the function with respect to $\bx$ is given by its *Jacobian matrix* denoted by the symbol: \[ \frac{\partial f}{\partial \bx^\top} = \begin{bmatrix} \frac{\partial f_1}{x_1} & \frac{\partial f_1}{x_2} & \dots \\ \frac{\partial f_2}{x_1} & \frac{\partial f_2}{x_2} & \dots \\ \vdots & \vdots & \ddots \\ \end{bmatrix}. \] When the function $ f $ is scalar ($n=1$), the Jacobian is the same as the gradient of the function (or, in fact, its transpose). More precisely, the <b>gradient</b> $\nabla f $ of $ f $ denotes the column vector of partial derivatives: \[ \nabla f = \frac{\partial f}{\partial \bx} = \begin{bmatrix} \frac{\partial f}{\partial x_1} \\ \frac{\partial f}{\partial x_2} \\ \vdots \end{bmatrix}. \] The second derivative $H_f $ of a scalar function $ f $, or <b>Hessian</b>, is denoted as \[ H_f = \frac{\partial f}{\partial \bx \partial \bx^\top} = \frac{\partial \nabla f}{\partial \bx^\top} = \begin{bmatrix} \frac{\partial f}{\partial x_1 \partial x_1} & \frac{\partial f}{\partial x_1 \partial x_2} & \dots \\ \frac{\partial f}{\partial x_2 \partial x_1} & \frac{\partial f}{\partial x_2 \partial x_2} & \dots \\ \vdots & \vdots & \ddots \\ \end{bmatrix}. \] The determinant of the Hessian is also known as <b>Laplacian</b> and denoted as \[ \Delta f = \operatorname{det} H_f = \frac{\partial f}{\partial x_1^2} + \frac{\partial f}{\partial x_2^2} + \dots \] <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @subsection covdet-derivative-transformations Derivative and image warps <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> In the following, we will often been interested in domain warpings $u: \mathbb{R}^m \rightarrow \mathbb{R}^n, \bx \mapsto u(\bx)$ of a function $f(\bar\bx) $ and its effect on the derivatives of the function. The key transformation is the chain rule: \[ \frac{\partial f \circ u}{\partial \bx^\top} = \left(\frac{\partial f}{\partial \bar\bx^\top} \circ u\right) \frac{\partial u}{\partial \bx^\top} \] In particular, for an affine transformation $u = (A,T) : \bx \mapsto A\bx + T$, one obtains the transformation rules: \[ \begin{align*} \frac{\partial f \circ (A,T)}{\partial \bx^\top} &= \left(\frac{\partial f}{\partial \bar\bx^\top} \circ (A,T)\right)A, \\ \nabla (f \circ (A,T)) &= A^\top (\nabla f) \circ (A,T), \\ H_{f \circ(A,T)} &= A^\top (H_f \circ (A,T)) A, \\ \Delta (f \circ(A,T)) &= \det(A)^2\, (\Delta f) \circ (A,T). \end{align*} \] <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @section covdet-smoothing Integral operations: smoothing <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> In practice, given an image $\ell$ expressed in digital format, good derivative approximations can be computed only if the bandwidth of the image is limited and, in particular, compatible with the sampling density. Since it is unreasonable to expect real images to be band-limited, the bandwidth is artificially constrained by suitably smoothing the image prior to computing its derivatives. This is also interpreted as a form of regularization or as a way of focusing on the image content at a particular scale. Formally, we will focus on Gaussian smoothing kernels. For the 2D case $\bx\in\real^2$, the Gaussian kernel of covariance $\Sigma$ is given by \[ g_{\Sigma}(\bx) = \frac{1}{2\pi \sqrt{\det\Sigma}} \exp\left( - \frac{1}{2} \bx^\top \Sigma^{-1} \bx \right). \] The symbol $g_{\sigma^2}$ will be used to denote a Gaussian kernel with isotropic standard deviation $\sigma$, i.e. $\Sigma = \sigma^2 I$. Given an image $\ell$, the symbol $\ell_\Sigma$ will be used to denote the image smoothed by the Gaussian kernel of parameter $\Sigma$: \[ \ell_\Sigma(\bx) = (g_\Sigma * \ell)(\bx) = \int_{\real^m} g_\Sigma(\bx - \by) \ell(\by)\,d\by. \] <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @subsection covdet-smoothing-transformations Smoothing and image warps <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> One advantage of Gaussian kernels is that they are (up to renormalization) closed under a linear warp: \[ |A|\, g_\Sigma \circ A = g_{A^{-1} \Sigma A^{-\top}} \] This also means that smoothing a warped image is the same as warping the result of smoothing the original image by a suitably adjusted Gaussian kernel: \[ g_{\Sigma} * (\ell \circ (A,T)) = (g_{A\Sigma A^\top} * \ell) \circ (A,T). \] <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @page covdet-corner-types Cornerness measures @tableofcontents <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> The goal of a cornerness measure (@ref covdet-cornerness) is to associate to an image patch a score proportional to how strongly the patch contain a certain strucuture, for example a corner or a blob. This page reviews the most important cornerness measures as implemented in VLFeat: - @ref covdet-harris - @ref covdet-laplacian - @ref covdet-hessian This page makes use of notation introduced in @ref covdet-differential. <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @section covdet-harris Harris corners <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> This section introduces the fist of the cornerness measure $\mathcal{F}[\ell]$. Recall (@ref covdet-cornerness) that the goal of this functional is to respond strongly to images $\ell$ of corner-like structure. Rather than explicitly encoding the appearance of corners, the idea of the Harris measure is to label as corner *any* image patch whose appearance is sufficiently distinctive to allow accurate localization. In particular, consider an image patch $\ell(\bx), \bx\in\Omega$, where $\Omega$ is a smooth circular window of radius approximately $\sigma_i$; at necessary condition for the patch to allow accurate localization is that even a small translation $\ell(\bx+\delta)$ causes the appearance to vary significantly (if not the origin and location $\delta$ would not be distinguishable from the image alone). This variation is measured by the sum of squared differences \[ E(\delta) = \int g_{\sigma_i^2}(\bx) (\ell_{\sigma_d^2}(\bx+\delta) - \ell_{\sigma_d^2}(\bx))^2 \,d\bx \] Note that images are compared at scale $\sigma_d$, known as *differentiation scale* for reasons that will be clear in a moment, and that the squared differences are summed over a window softly defined by $\sigma_i$, also known as *integration scale*. This function can be approximated as $E(\delta)\approx \delta^\top M[\ell;\sigma_i^2,\sigma_d^2] \delta$ where \[ M[\ell;\sigma_i^2,\sigma_d^2] = \int g_{\sigma_i^2}(\bx) (\nabla \ell_{\sigma_d^2}(\bx)) (\nabla \ell_{\sigma_d^2}(\bx))^\top \, d\bx. \] is the so called **structure tensor**. A corner is identified when the sum of squared differences $E(\delta)$ is large for displacements $\delta$ in all directions. This condition is obtained when both the eignenvalues $\lambda_1,\lambda_2$ of the structure tensor $M$ are large. The **Harris cornerness measure** captures this fact: \[ \operatorname{Harris}[\ell;\sigma_i^2,\sigma_d^2] = \det M - \kappa \operatorname{trace}^2 M = \lambda_1\lambda_2 - \kappa (\lambda_1+\lambda_2)^2 \] <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @subsection covdet-harris-warped Harris in the warped domain <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> The cornerness measure of a feature a location $u$ (recall that locations $u$ are in general defined as image warps) should be computed after normalizing the image (by applying to it the warp $u^{-1}$). This section shows that, for affine warps, the Harris cornerness measure can be computed directly in the Gaussian affine scale space of the image. In particular, for similarities, it can be computed in the standard Gaussian scale space. To this end, let $u=(A,T)$ be an affine warp identifying a feature location in image $\ell(\bx)$. Let $\bar\ell(\bar\bx) = \ell(A\bar\bx+T)$ be the normalized image and rewrite the structure tensor of the normalized image as follows: \[ M[\bar\ell; \bar\Sigma_i, \bar\Sigma_d] = M[\bar\ell; \bar\Sigma_i, \bar\Sigma_d](\mathbf{0}) = \left[ g_{\bar\Sigma_i} * (\nabla\bar\ell_{\bar\Sigma_d}) (\nabla\bar\ell_{\bar\Sigma_d})^\top \right](\mathbf{0}) \] This notation emphasizes that the structure tensor is obtained by taking derivatives and convolutions of the image. Using the fact that $\nabla g_{\bar\Sigma_d} * \bar\ell = A^\top (\nabla g_{A\bar\Sigma A^\top} * \ell) \circ (A,T)$ and that $g_{\bar\Sigma} * \bar \ell = (g_{A\bar\Sigma A^\top} * \ell) \circ (A,T)$, we get the equivalent expression: \[ M[\bar\ell; \bar\Sigma_i, \bar\Sigma_d](\mathbf{0}) = A^\top \left[ g_{A\bar\Sigma_i A^\top} * (\nabla\ell_{A\bar\Sigma_dA^\top})(\nabla\ell_{A\bar\Sigma_d A^\top})^\top \right](A\mathbf{0}+T) A. \] In other words, the structure tensor of the normalized image can be computed as: \[ M[\bar\ell; \bar\Sigma_i, \bar\Sigma_d](\mathbf{0}) = A^\top M[\ell; \Sigma_i, \Sigma_d](T) A, \quad \Sigma_{i} = A\bar\Sigma_{i}A^\top, \quad \Sigma_{d} = A\bar\Sigma_{d}A^\top. \] This equation allows to compute the structure tensor for feature at all locations directly in the original image. In particular, features at all translations $T$ can be evaluated efficiently by computing convolutions and derivatives of the image $\ell_{A\bar\Sigma_dA^\top}$. A case of particular instance is when $\bar\Sigma_i= \bar\sigma_i^2 I$ and $\bar\Sigma_d = \bar\sigma_d^2$ are both isotropic covariance matrices and the affine transformation is a similarity $A=sR$. Using the fact that $\det\left( s^2 R^\top M R \right)= s^4 \det M$ and $\operatorname{tr}\left(s^2 R^\top M R\right) = s^2 \operatorname{tr} M$, one obtains the relation \[ \operatorname{Harris}[\bar \ell;\bar\sigma_i^2,\bar\sigma_d^2] = s^4 \operatorname{Harris}[\ell;s^2\bar\sigma_i^2,s^2\bar\sigma_d^2](T). \] This equation indicates that, for similarity transformations, not only the structure tensor, but directly the Harris cornerness measure can be computed on the original image and then be transferred back to the normalized domain. Note, however, that this requires rescaling the measure by the factor $s^4$. Another important consequence of this relation is that the Harris measure is invariant to pure image rotations. It cannot, therefore, be used to associate an orientation to the detected features. <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @section covdet-hessian Hessian blobs <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> The *(determinant of the) Hessian* cornerness measure is given determinant of the Hessian of the image: \[ \operatorname{DetHess}[\ell;\sigma_d^2] = \det H_{g_{\sigma_d^2} * \ell}(\mathbf{0}) \] This number is large and positive if the image is locally curved (peaked), roughly corresponding to blob-like structures in the image. In particular, a large score requires the product of the eigenvalues of the Hessian to be large, which requires both of them to have the same sign and are large in absolute value. <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @subsection covdet-hessian-warped Hessian in the warped domain <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> Similarly to the Harris measure, it is possible to work with the Hessian measure on the original unnormalized image. As before, let $\bar\ell(\bar\bx) = \ell(A\bar\bx+T)$ be the normalized image and rewrite the Hessian of the normalized image as follows: \[ H_{g_{\bar\Sigma_d} * \bar\ell}(\mathbf{0}) = A^\top \left(H_{g_{\Sigma_d} * \ell}(T)\right) A. \] Then \[ \operatorname{DetHess}[\bar\ell;\bar\Sigma_d] = (\det A)^2 \operatorname{DetHess}[\ell;A\bar\Sigma_d A^\top](T). \] In particular, for isotropic covariance matrices and similarity transformations $A=sR$: \[ \operatorname{DetHess}[\bar\ell;\bar\sigma_d^2] = s^4 \operatorname{DetHess}[\ell;s^2\bar\sigma_d^2](T) \] <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @section covdet-laplacian Laplacian and Difference of Gaussians blobs <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> The **Laplacian of Gaussian (LoG)** or **trace of the Hessian** cornerness measure is given by the trace of the Hessian of the image: \[ \operatorname{Lap}[\ell;\sigma_d^2] = \operatorname{tr} H_{g_{\sigma_d}^2 * \ell} \] <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @subsection covdet-laplacian-warped Laplacian in the warped domain <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> Similarly to the Hessian measure, the Laplacian cornenress can often be efficiently computed for features at all locations in the original unnormalized image domain. In particular, if the derivative covariance matrix $\Sigma_d$ is isotropic and one considers as warpings similarity transformations $A=sR$, where $R$ is a rotatin and $s$ a rescaling, one has \[ \operatorname{Lap}[\bar\ell;\bar\sigma_d^2] = s^2 \operatorname{Lap}[\ell;s^2\bar\sigma_d^2](T) \] Note that, comparing to the Harris and determinant of Hessian measures, the scaling for the Laplacian is $s^2$ rather than $s^4$. <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @subsection covdet-laplacian-matched Laplacian as a matched filter <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> The Laplacian is given by the trace of the Hessian operator. Differently from the determinant of the Hessian, this is a linear operation. This means that computing the Laplacian cornerness measure can be seen as applying a linear filtering operator to the image. This filter can then be interpreted as a *template* of a corner being matched to the image. Hence, the Laplacian cornerness measure can be interpreted as matching this corner template at all possible image locations. To see this formally, compute the Laplacian score in the input image domain: \[ \operatorname{Lap}[\bar\ell;\bar\sigma_d^2] = s^2 \operatorname{Lap}[\ell;s^2\bar\sigma_d^2](T) = s^2 (\Delta g_{s^2\bar\sigma_d^2} * \ell)(T) \] The Laplacian fitler is obtained by moving the Laplacian operator from the image to the Gaussian smoothing kernel: \[ s^2 (\Delta g_{s^2\bar\sigma_d^2} * \ell) = (s^2 \Delta g_{s^2\bar\sigma_d^2}) * \ell \] Note that the filter is rescaled by the $s^2$; sometimes, this factor is incorporated in the Laplacian operator, yielding the so-called normalized Laplacian. The Laplacian of Gaussian is also called *top-hat function* and has the expression: \[ \Delta g_{\sigma^2}(x,y) = \frac{x^2+y^2 - 2 \sigma^2}{\sigma^4} g_{\sigma^2}(x,y). \] This filter, which acts as corner template, resembles a blob (a dark disk surrounded by a bright ring). <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @subsection covdet-laplacian-dog Difference of Gaussians <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> The **Difference of Gaussian** (DoG) cornerness measure can be interpreted as an approximation of the Laplacian that is easy to obtain once a scalespace of the input image has been computed. As noted above, the Laplacian cornerness of the normalized feature can be computed directly from the input image by convolving the image by the normalized Laplacian of Gaussian filter $s^2 \Delta g_{s^2\bar\sigma_d^2}$. Like the other derivative operators, this filter is simpe to discriteize. However, it is often approximated by computing the the *Difference of Gaussians* (DoG) approximation instead. This approximation is obtained from the easily-proved identity: \[ \frac{\partial}{\partial \sigma} g_{\sigma^2} = \sigma \Delta g_{\sigma^2}. \] This indicates that computing the normalized Laplacian of a Gaussian filter is, in the limit, the same as taking the difference between Gaussian filters of slightly increasing standard deviation $\sigma$ and $\kappa\sigma$, where $\kappa \approx 1$: \[ \sigma^2 \Delta g_{\sigma^2} \approx \sigma \frac{g_{(\kappa\sigma)^2} - g_{\sigma^2}}{\kappa\sigma - \sigma} = \frac{1}{\kappa - 1} (g_{(\kappa\sigma)^2} - g_{\sigma^2}). \] One nice propery of this expression is that the factor $\sigma$ cancels out in the right-hand side. Usually, scales $\sigma$ and $\kappa\sigma$ are pre-computed in the image scale-space and successive scales are sampled with uniform geometric spacing, meaning that the factor $\kappa$ is the same for all scales. Then, up to a overall scaling factor, the LoG cornerness measure can be obtained by taking the difference of successive scale space images $\ell_{(\kappa\sigma)^2}$ and $\ell_{\sigma^2}$. <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @page covdet-affine-adaptation Affine adaptation <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> @page covdet-dominant-orientation Dominant orientation <!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ --> **/ #include "covdet.h" #include <string.h> /** @brief Reallocate buffer ** @param buffer ** @param bufferSize ** @param targetSize ** @return error code **/ static int _vl_resize_buffer (void ** buffer, vl_size * bufferSize, vl_size targetSize) { void * newBuffer ; if (*buffer == NULL) { *buffer = vl_malloc(targetSize) ; if (*buffer) { *bufferSize = targetSize ; return VL_ERR_OK ; } else { *bufferSize = 0 ; return VL_ERR_ALLOC ; } } newBuffer = vl_realloc(*buffer, targetSize) ; if (newBuffer) { *buffer = newBuffer ; *bufferSize = targetSize ; return VL_ERR_OK ; } else { return VL_ERR_ALLOC ; } } /** @brief Enlarge buffer ** @param buffer ** @param bufferSize ** @param targetSize ** @return error code **/ static int _vl_enlarge_buffer (void ** buffer, vl_size * bufferSize, vl_size targetSize) { if (*bufferSize >= targetSize) return VL_ERR_OK ; return _vl_resize_buffer(buffer,bufferSize,targetSize) ; } /* ---------------------------------------------------------------- */ /* Finding local extrema */ /* ---------------------------------------------------------------- */ /* Todo: make this generally available in the library */ typedef struct _VlCovDetExtremum2 { vl_index xi ; vl_index yi ; float x ; float y ; float peakScore ; float edgeScore ; } VlCovDetExtremum2 ; typedef struct _VlCovDetExtremum3 { vl_index xi ; vl_index yi ; vl_index zi ; float x ; float y ; float z ; float peakScore ; float edgeScore ; } VlCovDetExtremum3 ; VL_EXPORT vl_size vl_find_local_extrema_3 (vl_index ** extrema, vl_size * bufferSize, float const * map, vl_size width, vl_size height, vl_size depth, double threshold) ; VL_EXPORT vl_size vl_find_local_extrema_2 (vl_index ** extrema, vl_size * bufferSize, float const * map, vl_size width, vl_size height, double threshold) ; VL_EXPORT vl_bool vl_refine_local_extreum_3 (VlCovDetExtremum3 * refined, float const * map, vl_size width, vl_size height, vl_size depth, vl_index x, vl_index y, vl_index z) ; VL_EXPORT vl_bool vl_refine_local_extreum_2 (VlCovDetExtremum2 * refined, float const * map, vl_size width, vl_size height, vl_index x, vl_index y) ; /** @internal ** @brief Find the extrema of a 3D function ** @param extrema buffer containing the extrema found (in/out). ** @param bufferSize size of the @a extrema buffer in bytes (in/out). ** @param map a 3D array representing the map. ** @param width of the map. ** @param height of the map. ** @param depth of the map. ** @param threshold minumum extremum value. ** @return number of extrema found. ** @see @ref ::vl_refine_local_extreum_2. **/ vl_size vl_find_local_extrema_3 (vl_index ** extrema, vl_size * bufferSize, float const * map, vl_size width, vl_size height, vl_size depth, double threshold) { vl_index x, y, z ; vl_size const xo = 1 ; vl_size const yo = width ; vl_size const zo = width * height ; float const *pt = map + xo + yo + zo ; vl_size numExtrema = 0 ; vl_size requiredSize = 0 ; #define CHECK_NEIGHBORS_3(v,CMP,SGN) (\ v CMP ## = SGN threshold && \ v CMP *(pt + xo) && \ v CMP *(pt - xo) && \ v CMP *(pt + zo) && \ v CMP *(pt - zo) && \ v CMP *(pt + yo) && \ v CMP *(pt - yo) && \ \ v CMP *(pt + yo + xo) && \ v CMP *(pt + yo - xo) && \ v CMP *(pt - yo + xo) && \ v CMP *(pt - yo - xo) && \ \ v CMP *(pt + xo + zo) && \ v CMP *(pt - xo + zo) && \ v CMP *(pt + yo + zo) && \ v CMP *(pt - yo + zo) && \ v CMP *(pt + yo + xo + zo) && \ v CMP *(pt + yo - xo + zo) && \ v CMP *(pt - yo + xo + zo) && \ v CMP *(pt - yo - xo + zo) && \ \ v CMP *(pt + xo - zo) && \ v CMP *(pt - xo - zo) && \ v CMP *(pt + yo - zo) && \ v CMP *(pt - yo - zo) && \ v CMP *(pt + yo + xo - zo) && \ v CMP *(pt + yo - xo - zo) && \ v CMP *(pt - yo + xo - zo) && \ v CMP *(pt - yo - xo - zo) ) for (z = 1 ; z < (signed)depth - 1 ; ++z) { for (y = 1 ; y < (signed)height - 1 ; ++y) { for (x = 1 ; x < (signed)width - 1 ; ++x) { float value = *pt ; if (CHECK_NEIGHBORS_3(value,>,+) || CHECK_NEIGHBORS_3(value,<,-)) { numExtrema ++ ; requiredSize += sizeof(vl_index) * 3 ; if (*bufferSize < requiredSize) { int err = _vl_resize_buffer((void**)extrema, bufferSize, requiredSize + 2000 * 3 * sizeof(vl_index)) ; if (err != VL_ERR_OK) abort() ; } (*extrema) [3 * (numExtrema - 1) + 0] = x ; (*extrema) [3 * (numExtrema - 1) + 1] = y ; (*extrema) [3 * (numExtrema - 1) + 2] = z ; } pt += xo ; } pt += 2*xo ; } pt += 2*yo ; } return numExtrema ; } /** @internal ** @brief Find extrema in a 2D function ** @param extrema buffer containing the found extrema (in/out). ** @param bufferSize size of the @a extrema buffer in bytes (in/out). ** @param map a 3D array representing the map. ** @param width of the map. ** @param height of the map. ** @param threshold minumum extremum value. ** @return number of extrema found. ** ** An extremum contains 2 ::vl_index values; they are arranged ** sequentially. ** ** The function can reuse an already allocated buffer if ** @a extrema and @a bufferSize are initialized on input. ** It may have to @a realloc the memory if the buffer is too small. **/ vl_size vl_find_local_extrema_2 (vl_index ** extrema, vl_size * bufferSize, float const* map, vl_size width, vl_size height, double threshold) { vl_index x, y ; vl_size const xo = 1 ; vl_size const yo = width ; float const *pt = map + xo + yo ; vl_size numExtrema = 0 ; vl_size requiredSize = 0 ; #define CHECK_NEIGHBORS_2(v,CMP,SGN) (\ v CMP ## = SGN threshold && \ v CMP *(pt + xo) && \ v CMP *(pt - xo) && \ v CMP *(pt + yo) && \ v CMP *(pt - yo) && \ \ v CMP *(pt + yo + xo) && \ v CMP *(pt + yo - xo) && \ v CMP *(pt - yo + xo) && \ v CMP *(pt - yo - xo) ) for (y = 1 ; y < (signed)height - 1 ; ++y) { for (x = 1 ; x < (signed)width - 1 ; ++x) { float value = *pt ; if (CHECK_NEIGHBORS_2(value,>,+) || CHECK_NEIGHBORS_2(value,<,-)) { numExtrema ++ ; requiredSize += sizeof(vl_index) * 2 ; if (*bufferSize < requiredSize) { int err = _vl_resize_buffer((void**)extrema, bufferSize, requiredSize + 2000 * 2 * sizeof(vl_index)) ; if (err != VL_ERR_OK) abort() ; } (*extrema) [2 * (numExtrema - 1) + 0] = x ; (*extrema) [2 * (numExtrema - 1) + 1] = y ; } pt += xo ; } pt += 2*xo ; } return numExtrema ; } /** @internal ** @brief Refine the location of a local extremum of a 3D map ** @param refined refined extremum (out). ** @param map a 3D array representing the map. ** @param width of the map. ** @param height of the map. ** @param depth of the map. ** @param x initial x position. ** @param y initial y position. ** @param z initial z position. ** @return a flat indicating whether the extrema refinement was stable. **/ VL_EXPORT vl_bool vl_refine_local_extreum_3 (VlCovDetExtremum3 * refined, float const * map, vl_size width, vl_size height, vl_size depth, vl_index x, vl_index y, vl_index z) { vl_size const xo = 1 ; vl_size const yo = width ; vl_size const zo = width * height ; double Dx=0,Dy=0,Dz=0,Dxx=0,Dyy=0,Dzz=0,Dxy=0,Dxz=0,Dyz=0 ; double A [3*3], b [3] ; #define at(dx,dy,dz) (*(pt + (dx)*xo + (dy)*yo + (dz)*zo)) #define Aat(i,j) (A[(i)+(j)*3]) float const * pt ; vl_index dx = 0 ; vl_index dy = 0 ; /*vl_index dz = 0 ;*/ vl_index iter ; int err ; assert (map) ; assert (1 <= x && x <= (signed)width - 2) ; assert (1 <= y && y <= (signed)height - 2) ; assert (1 <= z && z <= (signed)depth - 2) ; for (iter = 0 ; iter < 5 ; ++iter) { x += dx ; y += dy ; pt = map + x*xo + y*yo + z*zo ; /* compute the gradient */ Dx = 0.5 * (at(+1,0,0) - at(-1,0,0)) ; Dy = 0.5 * (at(0,+1,0) - at(0,-1,0)); Dz = 0.5 * (at(0,0,+1) - at(0,0,-1)) ; /* compute the Hessian */ Dxx = (at(+1,0,0) + at(-1,0,0) - 2.0 * at(0,0,0)) ; Dyy = (at(0,+1,0) + at(0,-1,0) - 2.0 * at(0,0,0)) ; Dzz = (at(0,0,+1) + at(0,0,-1) - 2.0 * at(0,0,0)) ; Dxy = 0.25 * (at(+1,+1,0) + at(-1,-1,0) - at(-1,+1,0) - at(+1,-1,0)) ; Dxz = 0.25 * (at(+1,0,+1) + at(-1,0,-1) - at(-1,0,+1) - at(+1,0,-1)) ; Dyz = 0.25 * (at(0,+1,+1) + at(0,-1,-1) - at(0,-1,+1) - at(0,+1,-1)) ; /* solve linear system */ Aat(0,0) = Dxx ; Aat(1,1) = Dyy ; Aat(2,2) = Dzz ; Aat(0,1) = Aat(1,0) = Dxy ; Aat(0,2) = Aat(2,0) = Dxz ; Aat(1,2) = Aat(2,1) = Dyz ; b[0] = - Dx ; b[1] = - Dy ; b[2] = - Dz ; err = vl_solve_linear_system_3(b, A, b) ; if (err != VL_ERR_OK) { b[0] = 0 ; b[1] = 0 ; b[2] = 0 ; break ; } /* Keep going if there is sufficient translation */ dx = (b[0] > 0.6 && x < (signed)width - 2 ? 1 : 0) + (b[0] < -0.6 && x > 1 ? -1 : 0) ; dy = (b[1] > 0.6 && y < (signed)height - 2 ? 1 : 0) + (b[1] < -0.6 && y > 1 ? -1 : 0) ; if (dx == 0 && dy == 0) break ; } /* check threshold and other conditions */ { double peakScore = at(0,0,0) + 0.5 * (Dx * b[0] + Dy * b[1] + Dz * b[2]) ; double alpha = (Dxx+Dyy)*(Dxx+Dyy) / (Dxx*Dyy - Dxy*Dxy) ; double edgeScore ; if (alpha < 0) { /* not an extremum */ edgeScore = VL_INFINITY_D ; } else { edgeScore = (0.5*alpha - 1) + sqrt(VL_MAX(0.25*alpha - 1,0)*alpha) ; } refined->xi = x ; refined->yi = y ; refined->zi = z ; refined->x = x + b[0] ; refined->y = y + b[1] ; refined->z = z + b[2] ; refined->peakScore = peakScore ; refined->edgeScore = edgeScore ; return err == VL_ERR_OK && vl_abs_d(b[0]) < 1.5 && vl_abs_d(b[1]) < 1.5 && vl_abs_d(b[2]) < 1.5 && 0 <= refined->x && refined->x <= (signed)width - 1 && 0 <= refined->y && refined->y <= (signed)height - 1 && 0 <= refined->z && refined->z <= (signed)depth - 1 ; } #undef Aat #undef at } /** @internal ** @brief Refine the location of a local extremum of a 2D map ** @param refined refined extremum (out). ** @param map a 2D array representing the map. ** @param width of the map. ** @param height of the map. ** @param x initial x position. ** @param y initial y position. ** @return a flat indicating whether the extrema refinement was stable. **/ VL_EXPORT vl_bool vl_refine_local_extreum_2 (VlCovDetExtremum2 * refined, float const * map, vl_size width, vl_size height, vl_index x, vl_index y) { vl_size const xo = 1 ; vl_size const yo = width ; double Dx=0,Dy=0,Dxx=0,Dyy=0,Dxy=0; double A [2*2], b [2] ; #define at(dx,dy) (*(pt + (dx)*xo + (dy)*yo )) #define Aat(i,j) (A[(i)+(j)*2]) float const * pt ; vl_index dx = 0 ; vl_index dy = 0 ; vl_index iter ; int err ; assert (map) ; assert (1 <= x && x <= (signed)width - 2) ; assert (1 <= y && y <= (signed)height - 2) ; for (iter = 0 ; iter < 5 ; ++iter) { x += dx ; y += dy ; pt = map + x*xo + y*yo ; /* compute the gradient */ Dx = 0.5 * (at(+1,0) - at(-1,0)) ; Dy = 0.5 * (at(0,+1) - at(0,-1)); /* compute the Hessian */ Dxx = (at(+1,0) + at(-1,0) - 2.0 * at(0,0)) ; Dyy = (at(0,+1) + at(0,-1) - 2.0 * at(0,0)) ; Dxy = 0.25 * (at(+1,+1) + at(-1,-1) - at(-1,+1) - at(+1,-1)) ; /* solve linear system */ Aat(0,0) = Dxx ; Aat(1,1) = Dyy ; Aat(0,1) = Aat(1,0) = Dxy ; b[0] = - Dx ; b[1] = - Dy ; err = vl_solve_linear_system_2(b, A, b) ; if (err != VL_ERR_OK) { b[0] = 0 ; b[1] = 0 ; break ; } /* Keep going if there is sufficient translation */ dx = (b[0] > 0.6 && x < (signed)width - 2 ? 1 : 0) + (b[0] < -0.6 && x > 1 ? -1 : 0) ; dy = (b[1] > 0.6 && y < (signed)height - 2 ? 1 : 0) + (b[1] < -0.6 && y > 1 ? -1 : 0) ; if (dx == 0 && dy == 0) break ; } /* check threshold and other conditions */ { double peakScore = at(0,0) + 0.5 * (Dx * b[0] + Dy * b[1]) ; double alpha = (Dxx+Dyy)*(Dxx+Dyy) / (Dxx*Dyy - Dxy*Dxy) ; double edgeScore ; if (alpha < 0) { /* not an extremum */ edgeScore = VL_INFINITY_D ; } else { edgeScore = (0.5*alpha - 1) + sqrt(VL_MAX(0.25*alpha - 1,0)*alpha) ; } refined->xi = x ; refined->yi = y ; refined->x = x + b[0] ; refined->y = y + b[1] ; refined->peakScore = peakScore ; refined->edgeScore = edgeScore ; return err == VL_ERR_OK && vl_abs_d(b[0]) < 1.5 && vl_abs_d(b[1]) < 1.5 && 0 <= refined->x && refined->x <= (signed)width - 1 && 0 <= refined->y && refined->y <= (signed)height - 1 ; } #undef Aat #undef at } /* ---------------------------------------------------------------- */ /* Covarant detector */ /* ---------------------------------------------------------------- */ #define VL_COVDET_MAX_NUM_ORIENTATIONS 4 #define VL_COVDET_MAX_NUM_LAPLACIAN_SCALES 4 #define VL_COVDET_AA_PATCH_RESOLUTION 20 #define VL_COVDET_AA_MAX_NUM_ITERATIONS 15 #define VL_COVDET_OR_NUM_ORIENTATION_HISTOGAM_BINS 36 #define VL_COVDET_AA_RELATIVE_INTEGRATION_SIGMA 3 #define VL_COVDET_AA_RELATIVE_DERIVATIVE_SIGMA 1 #define VL_COVDET_AA_MAX_ANISOTROPY 5 #define VL_COVDET_AA_CONVERGENCE_THRESHOLD 1.001 #define VL_COVDET_AA_ACCURATE_SMOOTHING VL_FALSE #define VL_COVDET_AA_PATCH_EXTENT (3*VL_COVDET_AA_RELATIVE_INTEGRATION_SIGMA) #define VL_COVDET_OR_ADDITIONAL_PEAKS_RELATIVE_SIZE 0.8 #define VL_COVDET_LAP_NUM_LEVELS 10 #define VL_COVDET_LAP_PATCH_RESOLUTION 16 #define VL_COVDET_LAP_DEF_PEAK_THRESHOLD 0.01 #define VL_COVDET_DOG_DEF_PEAK_THRESHOLD VL_COVDET_LAP_DEF_PEAK_THRESHOLD #define VL_COVDET_DOG_DEF_EDGE_THRESHOLD 10.0 #define VL_COVDET_HARRIS_DEF_PEAK_THRESHOLD 0.000002 #define VL_COVDET_HARRIS_DEF_EDGE_THRESHOLD 10.0 #define VL_COVDET_HESSIAN_DEF_PEAK_THRESHOLD 0.003 #define VL_COVDET_HESSIAN_DEF_EDGE_THRESHOLD 10.0 #define VL_COVDET_GSS_BASE_SCALE 1.6 /** @brief Covariant feature detector */ struct _VlCovDet { VlScaleSpace *gss ; /**< Gaussian scale space. */ VlScaleSpace *css ; /**< Cornerness scale space. */ VlCovDetMethod method ; /**< feature extraction method. */ double peakThreshold ; /**< peak threshold. */ double edgeThreshold ; /**< edge threshold. */ double lapPeakThreshold; /**< peak threshold for Laplacian scale selection. */ vl_size octaveResolution ; /**< resolution of each octave. */ vl_index numOctaves ; /**< number of octaves */ vl_index firstOctave ; /**< index of the first octave. */ double baseScale ; /**< the base scale of the gss. */ vl_size maxNumOrientations ; /**< max number of detected orientations. */ double nonExtremaSuppression ; vl_size numNonExtremaSuppressed ; VlCovDetFeature *features ; vl_size numFeatures ; vl_size numFeatureBufferSize ; float * patch ; vl_size patchBufferSize ; vl_bool transposed ; VlCovDetFeatureOrientation orientations [VL_COVDET_MAX_NUM_ORIENTATIONS] ; VlCovDetFeatureLaplacianScale scales [VL_COVDET_MAX_NUM_LAPLACIAN_SCALES] ; vl_bool aaAccurateSmoothing ; float aaPatch [(2*VL_COVDET_AA_PATCH_RESOLUTION+1)*(2*VL_COVDET_AA_PATCH_RESOLUTION+1)] ; float aaPatchX [(2*VL_COVDET_AA_PATCH_RESOLUTION+1)*(2*VL_COVDET_AA_PATCH_RESOLUTION+1)] ; float aaPatchY [(2*VL_COVDET_AA_PATCH_RESOLUTION+1)*(2*VL_COVDET_AA_PATCH_RESOLUTION+1)] ; float aaMask [(2*VL_COVDET_AA_PATCH_RESOLUTION+1)*(2*VL_COVDET_AA_PATCH_RESOLUTION+1)] ; float lapPatch [(2*VL_COVDET_LAP_PATCH_RESOLUTION+1)*(2*VL_COVDET_LAP_PATCH_RESOLUTION+1)] ; float laplacians [(2*VL_COVDET_LAP_PATCH_RESOLUTION+1)*(2*VL_COVDET_LAP_PATCH_RESOLUTION+1)*VL_COVDET_LAP_NUM_LEVELS] ; vl_size numFeaturesWithNumScales [VL_COVDET_MAX_NUM_LAPLACIAN_SCALES + 1] ; vl_bool allowPaddedWarping ; } ; VlEnumerator vlCovdetMethods [VL_COVDET_METHOD_NUM] = { {"DoG" , (vl_index)VL_COVDET_METHOD_DOG }, {"Hessian", (vl_index)VL_COVDET_METHOD_HESSIAN }, {"HessianLaplace", (vl_index)VL_COVDET_METHOD_HESSIAN_LAPLACE }, {"HarrisLaplace", (vl_index)VL_COVDET_METHOD_HARRIS_LAPLACE }, {"MultiscaleHessian", (vl_index)VL_COVDET_METHOD_MULTISCALE_HESSIAN}, {"MultiscaleHarris", (vl_index)VL_COVDET_METHOD_MULTISCALE_HARRIS }, {0, 0 } } ; /** @brief Create a new object instance ** @param method method for covariant feature detection. ** @return new covariant detector. **/ VlCovDet * vl_covdet_new (VlCovDetMethod method) { VlCovDet * self = vl_calloc(sizeof(VlCovDet),1) ; self->method = method ; self->octaveResolution = 3 ; self->numOctaves = -1 ; self->firstOctave = -1 ; self->baseScale = VL_COVDET_GSS_BASE_SCALE ; self->maxNumOrientations = VL_COVDET_MAX_NUM_ORIENTATIONS ; switch (self->method) { case VL_COVDET_METHOD_DOG : self->peakThreshold = VL_COVDET_DOG_DEF_PEAK_THRESHOLD ; self->edgeThreshold = VL_COVDET_DOG_DEF_EDGE_THRESHOLD ; self->lapPeakThreshold = 0 ; /* not used */ break ; case VL_COVDET_METHOD_HARRIS_LAPLACE: case VL_COVDET_METHOD_MULTISCALE_HARRIS: self->peakThreshold = VL_COVDET_HARRIS_DEF_PEAK_THRESHOLD ; self->edgeThreshold = VL_COVDET_HARRIS_DEF_EDGE_THRESHOLD ; self->lapPeakThreshold = VL_COVDET_LAP_DEF_PEAK_THRESHOLD ; break ; case VL_COVDET_METHOD_HESSIAN : case VL_COVDET_METHOD_HESSIAN_LAPLACE: case VL_COVDET_METHOD_MULTISCALE_HESSIAN: self->peakThreshold = VL_COVDET_HESSIAN_DEF_PEAK_THRESHOLD ; self->edgeThreshold = VL_COVDET_HESSIAN_DEF_EDGE_THRESHOLD ; self->lapPeakThreshold = VL_COVDET_LAP_DEF_PEAK_THRESHOLD ; break; default: assert(0) ; } self->nonExtremaSuppression = 0.5 ; self->features = NULL ; self->numFeatures = 0 ; self->numFeatureBufferSize = 0 ; self->patch = NULL ; self->patchBufferSize = 0 ; self->transposed = VL_FALSE ; self->aaAccurateSmoothing = VL_COVDET_AA_ACCURATE_SMOOTHING ; self->allowPaddedWarping = VL_TRUE ; { vl_index const w = VL_COVDET_AA_PATCH_RESOLUTION ; vl_index i,j ; double step = (2.0 * VL_COVDET_AA_PATCH_EXTENT) / (2*w+1) ; double sigma = VL_COVDET_AA_RELATIVE_INTEGRATION_SIGMA ; for (j = -w ; j <= w ; ++j) { for (i = -w ; i <= w ; ++i) { double dx = i*step/sigma ; double dy = j*step/sigma ; self->aaMask[(i+w) + (2*w+1)*(j+w)] = exp(-0.5*(dx*dx+dy*dy)) ; } } } { /* Covers one octave of Laplacian filters, from sigma=1 to sigma=2. The spatial sampling step is 0.5. */ vl_index s ; for (s = 0 ; s < VL_COVDET_LAP_NUM_LEVELS ; ++s) { double sigmaLap = pow(2.0, -0.5 + (double)s / (VL_COVDET_LAP_NUM_LEVELS - 1)) ; double const sigmaImage = 1.0 / sqrt(2.0) ; double const step = 0.5 * sigmaImage ; double const sigmaDelta = sqrt(sigmaLap*sigmaLap - sigmaImage*sigmaImage) ; vl_size const w = VL_COVDET_LAP_PATCH_RESOLUTION ; vl_size const num = 2 * w + 1 ; float * pt = self->laplacians + s * (num * num) ; memset(pt, 0, num * num * sizeof(float)) ; #define at(x,y) pt[(x+w)+(y+w)*(2*w+1)] at(0,0) = - 4.0 ; at(-1,0) = 1.0 ; at(+1,0) = 1.0 ; at(0,1) = 1.0 ; at(0,-1) = 1.0 ; #undef at vl_imsmooth_f(pt, num, pt, num, num, num, sigmaDelta / step, sigmaDelta / step) ; #if 0 { char name [200] ; snprintf(name, 200, "/tmp/%f-lap.pgm", sigmaDelta) ; vl_pgm_write_f(name, pt, num, num) ; } #endif } } return self ; } /** @brief Reset object ** @param self object. ** ** This function removes any buffered features and frees other ** internal buffers. **/ void vl_covdet_reset (VlCovDet * self) { if (self->features) { vl_free(self->features) ; self->features = NULL ; } if (self->css) { vl_scalespace_delete(self->css) ; self->css = NULL ; } if (self->gss) { vl_scalespace_delete(self->gss) ; self->gss = NULL ; } } /** @brief Delete object instance ** @param self object. **/ void vl_covdet_delete (VlCovDet * self) { vl_covdet_reset(self) ; if (self->patch) vl_free (self->patch) ; vl_free(self) ; } /** @brief Append a feature to the internal buffer. ** @param self object. ** @param feature a pointer to the feature to append. ** @return status. ** ** The feature is copied. The function may fail with @c status ** equal to ::VL_ERR_ALLOC if there is insufficient memory. **/ int vl_covdet_append_feature (VlCovDet * self, VlCovDetFeature const * feature) { vl_size requiredSize ; assert(self) ; assert(feature) ; self->numFeatures ++ ; requiredSize = self->numFeatures * sizeof(VlCovDetFeature) ; if (requiredSize > self->numFeatureBufferSize) { int err = _vl_resize_buffer((void**)&self->features, &self->numFeatureBufferSize, (self->numFeatures + 1000) * sizeof(VlCovDetFeature)) ; if (err) { self->numFeatures -- ; return err ; } } self->features[self->numFeatures - 1] = *feature ; return VL_ERR_OK ; } /* ---------------------------------------------------------------- */ /* Process a new image */ /* ---------------------------------------------------------------- */ /** @brief Detect features in an image ** @param self object. ** @param image image to process. ** @param width image width. ** @param height image height. ** @return status. ** ** @a width and @a height must be at least one pixel. The function ** fails by returing ::VL_ERR_ALLOC if the memory is insufficient. **/ int vl_covdet_put_image (VlCovDet * self, float const * image, vl_size width, vl_size height) { vl_size const minOctaveSize = 16 ; vl_index lastOctave ; vl_index octaveFirstSubdivision ; vl_index octaveLastSubdivision ; VlScaleSpaceGeometry geom = vl_scalespace_get_default_geometry(width,height) ; assert (self) ; assert (image) ; assert (width >= 1) ; assert (height >= 1) ; /* (minOctaveSize - 1) 2^lastOctave <= min(width,height) - 1 */ lastOctave = vl_floor_d(vl_log2_d(VL_MIN((double)width-1,(double)height-1) / (minOctaveSize - 1))) ; if (self->numOctaves > 0) { lastOctave = VL_MIN((vl_index)self->numOctaves - self->firstOctave - 1, lastOctave); } if (self->method == VL_COVDET_METHOD_DOG) { octaveFirstSubdivision = -1 ; octaveLastSubdivision = self->octaveResolution + 1 ; } else if (self->method == VL_COVDET_METHOD_HESSIAN) { octaveFirstSubdivision = -1 ; octaveLastSubdivision = self->octaveResolution ; } else { octaveFirstSubdivision = 0 ; octaveLastSubdivision = self->octaveResolution - 1 ; } geom.width = width ; geom.height = height ; geom.firstOctave = self->firstOctave ; geom.lastOctave = lastOctave ; geom.octaveResolution = self->octaveResolution ; geom.baseScale = self->baseScale * pow(2.0, 1.0 / self->octaveResolution) ; geom.octaveFirstSubdivision = octaveFirstSubdivision ; geom.octaveLastSubdivision = octaveLastSubdivision ; if (self->gss == NULL || ! vl_scalespacegeometry_is_equal (geom, vl_scalespace_get_geometry(self->gss))) { if (self->gss) vl_scalespace_delete(self->gss) ; self->gss = vl_scalespace_new_with_geometry(geom) ; if (self->gss == NULL) return VL_ERR_ALLOC ; } vl_scalespace_put_image(self->gss, image) ; return VL_ERR_OK ; } /* ---------------------------------------------------------------- */ /* Cornerness measures */ /* ---------------------------------------------------------------- */ /** @brief Scaled derminant of the Hessian filter ** @param hessian output image. ** @param image input image. ** @param width image width. ** @param height image height. ** @param step image sampling step (pixel size). ** @param sigma Gaussian smoothing of
{'commit': "diff --git a/vl/covdet.c b/vl/covdet.c\nindex 571e4f2..31c581c 100644\n--- a/vl/covdet.c\n+++ b/vl/covdet.c\n@@ -352,12 +352,12 @@ comparing neighborhoods of them.\n \n The next difficulty is to guarantee that detection is co-variant with\n image transformations. Hence, if $u$ is the pose of a feature\n-extracted from image $\\ell$, then the feature of pose $u' = w[u]$ must\n-be detected in the transformed image $\\ell' = w[\\ell]$.\n+extracted from image $\\ell$, then the transformed pose $u' = w[u]$\n+must be detected in the transformed image $\\ell' = w[\\ell]$.\n \n Since features are extracted in correspondence of the local maxima of\n the cornerness score, a sufficient condition is that corresponding\n-features attain the same score in the two images.\n+features attain the same score in the two images:\n \n \\[\n \\forall u\\in\\mathcal{W}: \\quad F(u;\\ell) = F(w[u];w[\\ell]),\n@@ -370,7 +370,7 @@ score *after normalizing the image* by the inverse of the candidate\n feature pose warp $u$, as follows:\n \n \\[\n-  F(u;\\ell) = F(1;u^{-1}[\\ell]) = F(1;\\ell \\circ u) = \\mathcal{F}(\\ell \\circ u).\n+  F(u;\\ell) = F(1;u^{-1}[\\ell]) = F(1;\\ell \\circ u) = \\mathcal{F}(\\ell \\circ u),\n \\]\n \n where $1 = u^{-1} \\circ u$ is the identity transformation and\n@@ -378,15 +378,20 @@ $\\mathcal{F}$ is an arbitrary functional. Intuitively, co-variant\n detection is obtained by looking if the appearance of the feature\n resembles a corner only *after normalization*. Formally:\n \n-\\[\n+@f{align*}\n+F(w[u];w[\\ell])\n+&=\n F(w \\circ u ;\\ell \\circ w^{-1})\n-=\n-\\mathcal{F}(1; \\ell \\circ w^{-1} \\circ w \\circ u)\n-=\n-\\mathcal{F}(1; \\ell\\circ u)\n-=\n-F(w;\\ell).\n-\\]\n+\\\\\n+&=\n+F(1; \\ell \\circ w^{-1} \\circ w \\circ u)\n+\\\\\n+&=\n+\\mathcal{F}(\\ell\\circ u)\n+\\\\\n+&=\n+F(u;\\ell).\n+@f}\n \n Concrete examples of the functional $\\mathcal{F}$ are given in @ref\n covdet-corner-types.\n", 'commit_subject': 'covdet.c: improves doc', 'repo_name': 'vlfeat/vlfeat', 'committer': {'name': 'Andrea Vedaldi', 'email': '412674b6eaeb392cf6309bc8344c997e51457723@gmail.com', 'time_sec': '1409931677', 'tz_offset': '60', 'date': {'seconds': '1409931677'}}, 'commit_tree': '2d2d20ff9308d2c26a5fb80cd605bcda6f6bc80d', 'commit_message': 'covdet.c: improves doc\n', 'language_name': 'Python', 'license': 'bsd-2-clause', 'hunks': "@@ -352,12 +352,12 @@ comparing neighborhoods of them.\n \n The next difficulty is to guarantee that detection is co-variant with\n image transformations. Hence, if $u$ is the pose of a feature\n-extracted from image $\\ell$, then the feature of pose $u' = w[u]$ must\n-be detected in the transformed image $\\ell' = w[\\ell]$.\n+extracted from image $\\ell$, then the transformed pose $u' = w[u]$\n+must be detected in the transformed image $\\ell' = w[\\ell]$.\n \n Since features are extracted in correspondence of the local maxima of\n the cornerness score, a sufficient condition is that corresponding\n-features attain the same score in the two images.\n+features attain the same score in the two images:\n \n \\[\n \\forall u\\in\\mathcal{W}: \\quad F(u;\\ell) = F(w[u];w[\\ell]),\n@@ -370,7 +370,7 @@ score *after normalizing the image* by the inverse of the candidate\n feature pose warp $u$, as follows:\n \n \\[\n-  F(u;\\ell) = F(1;u^{-1}[\\ell]) = F(1;\\ell \\circ u) = \\mathcal{F}(\\ell \\circ u).\n+  F(u;\\ell) = F(1;u^{-1}[\\ell]) = F(1;\\ell \\circ u) = \\mathcal{F}(\\ell \\circ u),\n \\]\n \n where $1 = u^{-1} \\circ u$ is the identity transformation and\n@@ -378,15 +378,20 @@ $\\mathcal{F}$ is an arbitrary functional. Intuitively, co-variant\n detection is obtained by looking if the appearance of the feature\n resembles a corner only *after normalization*. Formally:\n \n-\\[\n+@f{align*}\n+F(w[u];w[\\ell])\n+&=\n F(w \\circ u ;\\ell \\circ w^{-1})\n-=\n-\\mathcal{F}(1; \\ell \\circ w^{-1} \\circ w \\circ u)\n-=\n-\\mathcal{F}(1; \\ell\\circ u)\n-=\n-F(w;\\ell).\n-\\]\n+\\\\\n+&=\n+F(1; \\ell \\circ w^{-1} \\circ w \\circ u)\n+\\\\\n+&=\n+\\mathcal{F}(\\ell\\circ u)\n+\\\\\n+&=\n+F(u;\\ell).\n+@f}\n \n Concrete examples of the functional $\\mathcal{F}$ are given in @ref\n covdet-corner-types.\n", 'addition_count': 17, 'deletion_count': 12, 'src_file': 'a/vl/covdet.c', 'tgt_file': 'b/vl/covdet.c', 'file_extension': '.c', 'before_file': '/** @file covdet.c\n ** @brief Covariant feature detectors - Definition\n ** @author Karel Lenc\n ** @author Andrea Vedaldi\n ** @author Michal Perdoch\n **/\n\n/*\nCopyright (C) 2013-14 Andrea Vedaldi.\nCopyright (C) 2012 Karel Lenc, Andrea Vedaldi and Michal Perdoch.\nAll rights reserved.\n\nThis file is part of the VLFeat library and is made available under\nthe terms of the BSD license (see the COPYING file).\n*/\n\n/**\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@page covdet Covariant feature detectors\n@author Karel Lenc\n@author Andrea Vedaldi\n@author Michal Perdoch\n@tableofcontents\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n\n@ref covdet.h implements a number of covariant feature detectors, based\non three cornerness measures (determinant of the Hessian, trace of the Hessian\n(aka Difference of Gaussians, and Harris). It supprots affine adaptation,\norientation estimation, as well as Laplacian scale detection.\n\n- @subpage covdet-fundamentals\n- @subpage covdet-principles\n- @subpage covdet-differential\n- @subpage covdet-corner-types\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@section covdet-starting Getting started\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n\nThe ::VlCovDet object implements a number of covariant feature\ndetectors: Difference of Gaussian, Harris, determinant of Hessian.\nVariant of the basic detectors support scale selection by maximizing\nthe Laplacian measure as well as affine normalization.\n\n@code\n// create a detector object\nVlCovDet * covdet = vl_covdet_new(method) ;\n\n// set various parameters (optional)\nvl_covdet_set_first_octave(covdet, -1) ; // start by doubling the image resolution\nvl_covdet_set_octave_resolution(covdet, octaveResolution) ;\nvl_covdet_set_peak_threshold(covdet, peakThreshold) ;\nvl_covdet_set_edge_threshold(covdet, edgeThreshold) ;\n\n// process the image and run the detector\nvl_covdet_put_image(covdet, image, numRows, numCols) ;\nvl_covdet_detect(covdet) ;\n\n// drop features on the margin (optional)\nvl_covdet_drop_features_outside (covdet, boundaryMargin) ;\n\n// compute the affine shape of the features (optional)\nvl_covdet_extract_affine_shape(covdet) ;\n\n// compute the orientation of the features (optional)\nvl_covdet_extract_orientations(covdet) ;\n\n// get feature frames back\nvl_size numFeatures = vl_covdet_get_num_features(covdet) ;\nVlCovDetFeature const * feature = vl_covdet_get_features(covdet) ;\n\n// get normalized feature appearance patches (optional)\nvl_size w = 2*patchResolution + 1 ;\nfor (i = 0 ; i < numFeatures ; ++i) {\n  float * patch = malloc(w*w*sizeof(*desc)) ;\n  vl_covdet_extract_patch_for_frame(covdet,\n                                    patch,\n                                    patchResolution,\n                                    patchRelativeExtent,\n                                    patchRelativeSmoothing,\n                                    feature[i].frame) ;\n  // do something with patch\n}\n@endcode\n\nThis example code:\n\n- Calls ::vl_covdet_new constructs a new detector object. @ref\n  covdet.h supports a variety of different detectors (see\n  ::VlCovDetMethod).\n- Optionally calls various functions to set the detector parameters if\n  needed (e.g. ::vl_covdet_set_peak_threshold).\n- Calls ::vl_covdet_put_image to start processing a new image. It\n  causes the detector to compute the scale space representation of the\n  image, but does not compute the features yet.\n- Calls ::vl_covdet_detect runs the detector. At this point features are\n  ready to be extracted. However, one or all of the following steps\n  may be executed in order to process the features further.\n- Optionally calls ::vl_covdet_drop_features_outside to drop features\n  outside the image boundary.\n- Optionally calls ::vl_covdet_extract_affine_shape to compute the\n  affine shape of features using affine adaptation.\n- Optionally calls ::vl_covdet_extract_orientations to compute the\n  dominant orientation of features looking for the dominant gradient\n  orientation in patches.\n- Optionally calls ::vl_covdet_extract_patch_for_frame to extract a\n  normalized feature patch, for example to compute an invariant\n  feature descriptor.\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->\n@page covdet-fundamentals Covariant detectors fundamentals\n@tableofcontents\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->\n\nThis page describes the fundamental concepts required to understand a\ncovariant feature detector, the geometry of covariant features, and\nthe process of feature normalization.\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->\n@section covdet-covariance Covariant detection\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->\n\nThe purpose of a *covariant detector* is to extract from an image a\nset of local features in a manner which is consistent with spatial\ntransformations of the image itself. For instance, a covariant\ndetector that extracts interest points $\\bx_1,\\dots,\\bx_n$ from image\n$\\ell$ extracts the translated points $\\bx_1+T,\\dots,\\bx_n+T$ from the\ntranslated image $\\ell\'(\\bx) = \\ell(\\bx-T)$.\n\nMore in general, consider a image $\\ell$ and a transformed version\n$\\ell\' = \\ell \\circ w^{-1}$ of it, as in the following figure:\n\n@image html covdet.png "Covariant detection of local features."\n\nThe transformation or <em>warp</em> $w : \\real^2 \\mapsto \\real^2$ is a\ndeformation of the image domain which may capture a change of camera\nviewpoint or similar imaging factor. Examples of warps typically\nconsidered are translations, scaling, rotations, and general affine\ntransformations; however, in $w$ could be another type of continuous\nand invertible transformation.\n\nGiven an image $\\ell$, a **detector** selects features $R_1,\\dots,R_n$\n(one such features is shown in the example as a green circle). The\ndetector is said to be **covariant** with the warps $w$ if it extracts\nthe transformed features $w[R_1],\\dots, w[R_n]$ from the transformed\nimage $w[\\ell]$. Intuitively, this means that the &ldquo;same\nfeatures&rdquo; are extracted in both cases up to the transformation\n$w$. This property is described more formally in @ref\ncovdet-principles.\n\nCovariance is a key property of local feature detectors as it allows\nextracting corresponding features from two or more images, making it\npossible to match them in a meaningful way.\n\nThe @ref covdet.h module in VLFeat implements an array of feature\ndetection algorithm that have are covariant to different classes of\ntransformations.\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->\n@section covdet-frame Feature geometry and feature frames\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->\n\nAs we have seen, local features are subject to image transformations,\nand they apply a fundamental role in matching and normalizing\nimages. To operates effectively with local features is therefore\nnecessary to understand their geometry.\n\nThe geometry of a local feature is captured by a <b>feature frame</b>\n$R$. In VLFeat, depending on the specific detector, the frame can be\neither a point, a disc, an ellipse, an oriented disc, or an oriented\nellipse.\n\nA frame captures both the extent of the local features, useful to know\nwhich portions of two images are put in correspondence, as well their\nshape.  The latter can be used to associate to diagnose the\ntransformation that affects a feature and remove it through the\nprocess of **normalization**.\n\nMore precisely, in covariant detection feature frames are constructed\nto be compatible with a certain class of transformations. For example,\ncircles are compatible with similarity transformations as they are\nclosed under them. Likewise, ellipses are compatible with affine\ntransformations.\n\nBeyond this closure property, the key idea here is that all feature\noccurrences can be seen as transformed versions of a base or\n<b>canonical</b> feature. For example, all discs $R$ can be obtained\nby applying a similarity transformation to the unit disc $\\bar R$\ncentered at the origin. $\\bar R$ is an example of canonical frame\nas any other disc can be written as $R = w[\\bar R]$ for a suitable\nsimilarity $w$.\n\n@image html frame-canonical.png "The idea of canonical frame and normalization"\n\nThe equation $R = w[\\bar R_0]$ matching the canonical and detected\nfeature frames establishes a constraint on the warp $w$, very similar\nto the way two reference frames in geometry establish a transformation\nbetween spaces. The transformation $w$ can be thought as a the\n**pose** of the detected feature, a generalization of its location.\n\nIn the case of discs and similarity transformations, the equation $R =\nw[\\bar R_0]$ fixes $w$ up to a residual rotation. This can be\naddressed by considering oriented discs instead. An **oriented disc**\nis a disc with a radius highlighted to represent the feature\norientation.\n\nWhile discs are appropriate for similarity transformations, they are\nnot closed under general affine transformations. In this case, one\nshould consider the more general class of (oriented) ellipses. The\nfollowing image illustrates the five types of feature frames used in\nVLFeat:\n\n@image html frame-types.png "Types of local feature frames: points, discs, oriented discs, ellipses, oriented ellipses."\n\nNote that these frames are described respectively by 2, 3, 4, 5 and 6\nparameters. The most general type are the oriented ellipses, which can\nbe used to represent all the other frame types as well.\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->\n@section covdet-frame-transformation Transforming feature frames\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->\n\nConsider a warp $w$ mapping image $\\ell$ into image $\\ell\'$ as in the\nfigure below. A feature $R$ in the first image co-variantly transform\ninto a feature $R\'=w[R]$ in the second image:\n\n@image html covdet-normalization.png "Normalization removes the effect of an image deformation."\n\nThe poses $u,u\'$ of $R=u[R_0]$ and $R\' = u\'[R_0]$ are then related by\nthe simple expression:\n\n\\[\n  u\' = w \\circ u.\n\\]\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->\n@section covdet-frame-normalization Normalizing feature frames\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->\n\nIn the example above, the poses $u$ and $u\'$ relate the two\noccurrences $R$ and $R\'$ of the feature to its canonical version\n$R_0$. If the pose $u$ of the feature in image $\\ell$ is known, the\ncanonical feature appearance can be computed by un-warping it:\n\n\\[\n \\ell_0 = u^{-1}[\\ell] = \\ell \\circ u.\n\\]\n\nThis process is known as **normalization** and is the key in the\ncomputation of invariant feature descriptors as well as in the\nconstruction of most co-variant detectors.\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->\n@page covdet-principles Principles of covariant detection\n@tableofcontents\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->\n\nThe goals of a co-variant detector were discussed in @ref\ncovdet-fundamentals. This page introduces a few general principles\nthat are at the basis of most covariant detection algorithms. Consider\nan input image $\\ell$ and a two dimensional continuous and invertible\nwarp $w$. The *warped image* $w[\\ell]$ is defined to be\n\n\\[\n w[\\ell] = \\ell \\circ w^{-1},\n\\]\n\nor, equivalently,\n\n\\[\n w[\\ell](x,y) =  \\ell(w^{-1}(x,y)), \\qquad \\forall (x,y)\\in\\real^2.\n\\]\n\nNote that, while $w$ pushes pixels forward, from the original to the\ntransformed image domain, defining the transformed image $\\ell\'$\nrequires inverting the warp and composing $\\ell$ with $w^{-1}$.\n\nThe goal a covariant detector is to extract the same local features\nirregardless of image transformations. The detector is said to be\n<b>covariant</b> or <b>equivariant</b> with a class of warps\n$w\\in\\mathcal{W}$ if, when the feature $R$ is detected in image\n$\\ell$, then the transformed feature $w[R]$ is detected in the\ntransformed image $w[\\ell]$.\n\nThe net effect is that a covariant feature detector appears to\n&ldquo;track&rdquo; image transformations; however, it is important to\nnote that a detector *is not a tracker* because it processes images\nindividually rather than jointly as part of a sequence.\n\nAn intuitive way to construct a covariant feature detector is to\nextract features in correspondence of images structures that are\neasily identifiable even after a transformation. Example of specific\nstructures include dots, corners, and blobs. These will be generically\nindicated as **corners** in the followup.\n\nA covariant detector faces two challenges. First, corners have, in\npractice, an infinite variety of individual appearances and the\ndetector must be able to capture them to be of general applicability.\nSecond, the way corners are identified and detected must remain stable\nunder transformations of the image. These two problems are addressed\nin @ref covdet-cornerness-localmax and @ref\ncovdet-cornerness-normalization respectively.\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@section covdet-cornerness Detection using a cornerness measure\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n\nOne way to decide whether an image region $R$ contains a corner is to\ncompare the local appearance to a model or template of the corner; the\nresult of this comparisons produces a *cornerness score* at that\nlocation. This page describe general theoretical properties of the\ncornerness and the detection process. Concrete examples of cornerness\nare given in @ref covdet-corner-types.\n\nA **cornerness measure** associate a score to all possible feature\nlocations in an image $\\ell$. As described in @ref covdet-frame, the\nlocation or, more in general, pose $u$ of a feature $R$ is the warp\n$w$ that maps the canonical feature frame $R_0$ to $R$:\n\n\\[\n    R = u[R_0].\n\\]\n\nThe goal of a cornerness measure is to associate a score $F(u;\\ell)$\nto all possible feature poses $u$ and use this score to extract a\nfinite number of co-variant features from any image.\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@subsection covdet-cornerness-localmax Local maxima of a cornerness measure\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n\nGiven the cornerness of each candidate feature, the detector must\nextract a finite number of them. However, the cornerness of features\nwith nearly identical pose must be similar (otherwise the cornerness\nmeasure would be unstable). As such, simply thresholding $F(w;\\ell)$\nwould detect an infinite number of nearly identical features rather\nthan a finite number.\n\nThe solution is to detect features in correspondence of the local\nmaxima of the score measure:\n\n\\[\n \\{w_1,\\dots,w_n\\} = \\operatorname{localmax}_{w\\in\\mathcal{W}} F(w;\\ell).\n\\]\n\nThis also means that features are never detected in isolation, but by\ncomparing neighborhoods of them.\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@subsection covdet-cornerness-normalization Covariant detection by normalization\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n\nThe next difficulty is to guarantee that detection is co-variant with\nimage transformations. Hence, if $u$ is the pose of a feature\nextracted from image $\\ell$, then the feature of pose $u\' = w[u]$ must\nbe detected in the transformed image $\\ell\' = w[\\ell]$.\n\nSince features are extracted in correspondence of the local maxima of\nthe cornerness score, a sufficient condition is that corresponding\nfeatures attain the same score in the two images.\n\n\\[\n\\forall u\\in\\mathcal{W}: \\quad F(u;\\ell) = F(w[u];w[\\ell]),\n\\qquad\\text{or}\\qquad\nF(u;\\ell) = F(w \\circ u ;\\ell \\circ w^{-1}).\n\\]\n\nOne simple way to satisfy this equation is to compute a cornerness\nscore *after normalizing the image* by the inverse of the candidate\nfeature pose warp $u$, as follows:\n\n\\[\n  F(u;\\ell) = F(1;u^{-1}[\\ell]) = F(1;\\ell \\circ u) = \\mathcal{F}(\\ell \\circ u).\n\\]\n\nwhere $1 = u^{-1} \\circ u$ is the identity transformation and\n$\\mathcal{F}$ is an arbitrary functional. Intuitively, co-variant\ndetection is obtained by looking if the appearance of the feature\nresembles a corner only *after normalization*. Formally:\n\n\\[\nF(w \\circ u ;\\ell \\circ w^{-1})\n=\n\\mathcal{F}(1; \\ell \\circ w^{-1} \\circ w \\circ u)\n=\n\\mathcal{F}(1; \\ell\\circ u)\n=\nF(w;\\ell).\n\\]\n\nConcrete examples of the functional $\\mathcal{F}$ are given in @ref\ncovdet-corner-types.\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@subsection covdet-locality Locality of the detected features\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n\nIn the definition above, the cornenress functional $\\mathcal{F}$ is an\narbitrary functional of the entire normalized image $u^{-1}[\\ell]$.\nIn practice, one is always interested in detecting **local features**\n(at the very least because the image extent is finite).\n\nThis is easily obtained by considering a cornerness $\\mathcal{F}$\nwhich only looks in a small region of the normalized image, usually\ncorresponding to the extent of the canonical feature $R_0$ (e.g. a\nunit disc centered at the origin).\n\nIn this case the extent of the local feature in the original image is\nsimply given by $R = u[R_0]$.\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@section covdet-partial Partial and iterated normalization\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n\nPractical detectors implement variants of the ideas above. Very often,\nfor instance, detection is an iterative process, in which successive\nparameters of the pose of a feature are determined. For instance, it\nis typical to first detect the location and scale of a feature using a\nrotation-invariant cornerness score $\\mathcal{F}$. Once these two\nparameters are known, the rotation can be determined using a different\nscore, sensitive to the orientation of the local image structures.\n\nCertain detectors (such as Harris-Laplace and Hessian-Laplace) use\neven more sophisticated schemes, in which different scores are used to\njointly (rather than in succession) different parameters of the pose\nof a feature, such as its translation and scale. While a formal\ntreatment of these cases is possible as well, we point to the original\npapers.\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@page covdet-differential Differential and integral image operations\n@tableofcontents\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n\nDealing with covariant interest point detector requires working a good\ndeal with derivatives, convolutions, and transformations of images.\nThe notation and fundamental properties of interest here are discussed\nnext.\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@section covdet-derivatives Derivative operations: gradients\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n\nFor the derivatives, we borrow the notation of\n@cite{kinghorn96integrals}. Let $f: \\mathbb{R}^m \\rightarrow\n\\mathbb{R}^n, \\bx \\mapsto f(\\bx)$ be a vector function. The derivative\nof the function with respect to $\\bx$ is given by its *Jacobian\nmatrix* denoted by the symbol:\n\n\\[\n\\frac{\\partial f}{\\partial \\bx^\\top}\n=\n\\begin{bmatrix}\n  \\frac{\\partial f_1}{x_1} & \\frac{\\partial f_1}{x_2} & \\dots \\\\\n  \\frac{\\partial f_2}{x_1} & \\frac{\\partial f_2}{x_2} & \\dots \\\\\n  \\vdots & \\vdots & \\ddots \\\\\n\\end{bmatrix}.\n\\]\n\nWhen the function $ f $ is scalar ($n=1$), the Jacobian is the same as\nthe gradient of the function (or, in fact, its transpose). More\nprecisely, the <b>gradient</b> $\\nabla f $ of $ f $ denotes the column\nvector of partial derivatives:\n\n\\[\n\\nabla f\n = \\frac{\\partial f}{\\partial \\bx}\n =\n \\begin{bmatrix}\n  \\frac{\\partial f}{\\partial x_1} \\\\\n  \\frac{\\partial f}{\\partial x_2} \\\\\n  \\vdots\n\\end{bmatrix}.\n\\]\n\nThe second derivative $H_f $ of a scalar function $ f $, or\n<b>Hessian</b>, is denoted as\n\n\\[\nH_f\n= \\frac{\\partial f}{\\partial \\bx \\partial \\bx^\\top}\n= \\frac{\\partial \\nabla f}{\\partial \\bx^\\top}\n=\n\\begin{bmatrix}\n  \\frac{\\partial f}{\\partial x_1 \\partial x_1} & \\frac{\\partial f}{\\partial x_1 \\partial x_2} & \\dots \\\\\n  \\frac{\\partial f}{\\partial x_2 \\partial x_1} & \\frac{\\partial f}{\\partial x_2 \\partial x_2} & \\dots \\\\\n  \\vdots & \\vdots & \\ddots \\\\\n\\end{bmatrix}.\n\\]\n\nThe determinant of the Hessian is also known as <b>Laplacian</b> and denoted as\n\n\\[\n \\Delta f = \\operatorname{det} H_f =\n\\frac{\\partial f}{\\partial x_1^2} +\n\\frac{\\partial f}{\\partial x_2^2} +\n\\dots\n\\]\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@subsection covdet-derivative-transformations Derivative and image warps\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n\nIn the following, we will often been interested in domain warpings $u:\n\\mathbb{R}^m \\rightarrow \\mathbb{R}^n, \\bx \\mapsto u(\\bx)$ of a\nfunction $f(\\bar\\bx) $ and its effect on the derivatives of the\nfunction. The key transformation is the chain rule:\n\n\\[\n\\frac{\\partial f \\circ u}{\\partial \\bx^\\top}\n=\n\\left(\\frac{\\partial f}{\\partial \\bar\\bx^\\top} \\circ u\\right)\n\\frac{\\partial u}{\\partial \\bx^\\top}\n\\]\n\nIn particular, for an affine transformation $u = (A,T) : \\bx \\mapsto\nA\\bx + T$, one obtains the transformation rules:\n\n\\[\n\\begin{align*}\n\\frac{\\partial f \\circ (A,T)}{\\partial \\bx^\\top}\n&=\n\\left(\\frac{\\partial f}{\\partial \\bar\\bx^\\top} \\circ (A,T)\\right)A,\n\\\\\n\\nabla (f \\circ (A,T))\n&= A^\\top (\\nabla f) \\circ (A,T),\n\\\\\nH_{f \\circ(A,T)}\n&= A^\\top (H_f \\circ (A,T)) A,\n\\\\\n\\Delta (f \\circ(A,T))\n&= \\det(A)^2\\, (\\Delta f) \\circ (A,T).\n\\end{align*}\n\\]\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@section covdet-smoothing Integral operations: smoothing\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n\nIn practice, given an image $\\ell$ expressed in digital format, good\nderivative approximations can be computed only if the bandwidth of the\nimage is limited and, in particular, compatible with the sampling\ndensity. Since it is unreasonable to expect real images to be\nband-limited, the bandwidth is artificially constrained by suitably\nsmoothing the image prior to computing its derivatives. This is also\ninterpreted as a form of regularization or as a way of focusing on the\nimage content at a particular scale.\n\nFormally, we will focus on Gaussian smoothing kernels. For the 2D case\n$\\bx\\in\\real^2$, the Gaussian kernel of covariance $\\Sigma$ is given\nby\n\n\\[\ng_{\\Sigma}(\\bx) = \\frac{1}{2\\pi \\sqrt{\\det\\Sigma}}\n  \\exp\\left(\n  - \\frac{1}{2} \\bx^\\top \\Sigma^{-1} \\bx\n  \\right).\n\\]\n\nThe symbol $g_{\\sigma^2}$ will be used to denote a Gaussian kernel\nwith isotropic standard deviation $\\sigma$, i.e. $\\Sigma = \\sigma^2\nI$. Given an image $\\ell$, the symbol $\\ell_\\Sigma$ will be used to\ndenote the image smoothed by the Gaussian kernel of parameter\n$\\Sigma$:\n\n\\[\n\\ell_\\Sigma(\\bx) = (g_\\Sigma * \\ell)(\\bx)\n=\n\\int_{\\real^m}\ng_\\Sigma(\\bx - \\by) \\ell(\\by)\\,d\\by.\n\\]\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@subsection covdet-smoothing-transformations Smoothing and image warps\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n\nOne advantage of Gaussian kernels is that they are (up to\nrenormalization) closed under a linear warp:\n\n\\[\n |A|\\, g_\\Sigma \\circ A = g_{A^{-1} \\Sigma A^{-\\top}}\n\\]\n\nThis also means that smoothing a warped image is the same as warping\nthe result of smoothing the original image by a suitably adjusted\nGaussian kernel:\n\n\\[\ng_{\\Sigma} * (\\ell \\circ (A,T))\n=\n(g_{A\\Sigma A^\\top} * \\ell) \\circ (A,T).\n\\]\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@page covdet-corner-types Cornerness measures\n@tableofcontents\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n\nThe goal of a cornerness measure (@ref covdet-cornerness) is to\nassociate to an image patch a score proportional to how strongly the\npatch contain a certain strucuture, for example a corner or a\nblob. This page reviews the most important cornerness measures as\nimplemented in VLFeat:\n\n- @ref covdet-harris\n- @ref covdet-laplacian\n- @ref covdet-hessian\n\nThis page makes use of notation introduced in @ref\ncovdet-differential.\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@section covdet-harris Harris corners\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n\nThis section introduces the fist of the cornerness measure\n$\\mathcal{F}[\\ell]$. Recall (@ref covdet-cornerness) that the goal of\nthis functional is to respond strongly to images $\\ell$ of corner-like\nstructure.\n\nRather than explicitly encoding the appearance of corners, the idea of\nthe Harris measure is to label as corner *any* image patch whose\nappearance is sufficiently distinctive to allow accurate\nlocalization. In particular, consider an image patch $\\ell(\\bx),\n\\bx\\in\\Omega$, where $\\Omega$ is a smooth circular window of radius\napproximately $\\sigma_i$; at necessary condition for the patch to\nallow accurate localization is that even a small translation\n$\\ell(\\bx+\\delta)$ causes the appearance to vary significantly (if not\nthe origin and location $\\delta$ would not be distinguishable from the\nimage alone). This variation is measured by the sum of squared\ndifferences\n\n\\[\nE(\\delta) = \\int g_{\\sigma_i^2}(\\bx)\n(\\ell_{\\sigma_d^2}(\\bx+\\delta) -\n \\ell_{\\sigma_d^2}(\\bx))^2 \\,d\\bx\n\\]\n\nNote that images are compared at scale $\\sigma_d$, known as\n *differentiation scale* for reasons that will be clear in a moment,\nand that the squared differences are summed over a window softly\ndefined by $\\sigma_i$, also known as *integration scale*. This\nfunction can be approximated as $E(\\delta)\\approx \\delta^\\top\nM[\\ell;\\sigma_i^2,\\sigma_d^2] \\delta$ where\n\n\\[\n  M[\\ell;\\sigma_i^2,\\sigma_d^2]\n= \\int  g_{\\sigma_i^2}(\\bx)\n (\\nabla \\ell_{\\sigma_d^2}(\\bx))\n (\\nabla \\ell_{\\sigma_d^2}(\\bx))^\\top \\, d\\bx.\n\\]\n\nis the so called **structure tensor**.\n\nA corner is identified when the sum of squared differences $E(\\delta)$\nis large for displacements $\\delta$ in all directions. This condition\nis obtained when both the eignenvalues $\\lambda_1,\\lambda_2$ of the\nstructure tensor $M$ are large. The **Harris cornerness measure**\ncaptures this fact:\n\n\\[\n \\operatorname{Harris}[\\ell;\\sigma_i^2,\\sigma_d^2] =\n \\det M - \\kappa \\operatorname{trace}^2 M =\n \\lambda_1\\lambda_2 - \\kappa (\\lambda_1+\\lambda_2)^2\n\\]\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@subsection covdet-harris-warped Harris in the warped domain\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n\nThe cornerness measure of a feature a location $u$ (recall that\nlocations $u$ are in general defined as image warps) should be\ncomputed after normalizing the image (by applying to it the warp\n$u^{-1}$). This section shows that, for affine warps, the Harris\ncornerness measure can be computed directly in the Gaussian affine\nscale space of the image. In particular, for similarities, it can be\ncomputed in the standard Gaussian scale space.\n\nTo this end, let $u=(A,T)$ be an affine warp identifying a feature\nlocation in image $\\ell(\\bx)$. Let $\\bar\\ell(\\bar\\bx) =\n\\ell(A\\bar\\bx+T)$ be the normalized image and rewrite the structure\ntensor of the normalized image as follows:\n\n\\[\n M[\\bar\\ell; \\bar\\Sigma_i, \\bar\\Sigma_d]\n=\n M[\\bar\\ell; \\bar\\Sigma_i, \\bar\\Sigma_d](\\mathbf{0})\n=\n\\left[\ng_{\\bar\\Sigma_i} *\n(\\nabla\\bar\\ell_{\\bar\\Sigma_d})\n(\\nabla\\bar\\ell_{\\bar\\Sigma_d})^\\top\n\\right](\\mathbf{0})\n\\]\n\nThis notation emphasizes that the structure tensor is obtained by\ntaking derivatives and convolutions of the image. Using the fact that\n$\\nabla g_{\\bar\\Sigma_d} * \\bar\\ell = A^\\top (\\nabla g_{A\\bar\\Sigma\nA^\\top} * \\ell) \\circ (A,T)$ and that $g_{\\bar\\Sigma} * \\bar \\ell =\n(g_{A\\bar\\Sigma A^\\top} * \\ell) \\circ (A,T)$, we get the equivalent\nexpression:\n\n\\[\n M[\\bar\\ell; \\bar\\Sigma_i, \\bar\\Sigma_d](\\mathbf{0})\n =\nA^\\top\n\\left[\ng_{A\\bar\\Sigma_i A^\\top} *\n(\\nabla\\ell_{A\\bar\\Sigma_dA^\\top})(\\nabla\\ell_{A\\bar\\Sigma_d A^\\top})^\\top\n\\right](A\\mathbf{0}+T)\nA.\n\\]\n\nIn other words, the structure tensor of the normalized image can be\ncomputed as:\n\n\\[\nM[\\bar\\ell; \\bar\\Sigma_i, \\bar\\Sigma_d](\\mathbf{0})\n=\nA^\\top M[\\ell; \\Sigma_i, \\Sigma_d](T) A,\n\\quad\n\\Sigma_{i} = A\\bar\\Sigma_{i}A^\\top,\n\\quad\n\\Sigma_{d} = A\\bar\\Sigma_{d}A^\\top.\n\\]\n\nThis equation allows to compute the structure tensor for feature at\nall locations directly in the original image. In particular, features\nat all translations $T$ can be evaluated efficiently by computing\nconvolutions and derivatives of the image\n$\\ell_{A\\bar\\Sigma_dA^\\top}$.\n\nA case of particular instance is when $\\bar\\Sigma_i= \\bar\\sigma_i^2 I$\nand $\\bar\\Sigma_d = \\bar\\sigma_d^2$ are both isotropic covariance\nmatrices and the affine transformation is a similarity $A=sR$.  Using\nthe fact that $\\det\\left( s^2 R^\\top M R \\right)= s^4 \\det M$ and\n$\\operatorname{tr}\\left(s^2 R^\\top M R\\right) = s^2 \\operatorname{tr}\nM$, one obtains the relation\n\n\\[\n \\operatorname{Harris}[\\bar \\ell;\\bar\\sigma_i^2,\\bar\\sigma_d^2] =\n s^4 \\operatorname{Harris}[\\ell;s^2\\bar\\sigma_i^2,s^2\\bar\\sigma_d^2](T).\n\\]\n\nThis equation indicates that, for similarity transformations, not only\nthe structure tensor, but directly the Harris cornerness measure can\nbe computed on the original image and then be transferred back to the\nnormalized domain. Note, however, that this requires rescaling the\nmeasure by the factor $s^4$.\n\nAnother important consequence of this relation is that the Harris\nmeasure is invariant to pure image rotations. It cannot, therefore, be\nused to associate an orientation to the detected features.\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@section covdet-hessian Hessian blobs\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n\nThe *(determinant of the) Hessian* cornerness measure is given\ndeterminant of the Hessian of the image:\n\n\\[\n \\operatorname{DetHess}[\\ell;\\sigma_d^2]\n =\n \\det H_{g_{\\sigma_d^2} * \\ell}(\\mathbf{0})\n\\]\n\nThis number is large and positive if the image is locally curved\n(peaked), roughly corresponding to blob-like structures in the image.\nIn particular, a large score requires the product of the eigenvalues\nof the Hessian to be large, which requires both of them to have the\nsame sign and are large in absolute value.\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@subsection covdet-hessian-warped Hessian in the warped domain\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n\nSimilarly to the Harris measure, it is possible to work with the\nHessian measure on the original unnormalized image. As before, let\n$\\bar\\ell(\\bar\\bx) = \\ell(A\\bar\\bx+T)$ be the normalized image and\nrewrite the Hessian of the normalized image as follows:\n\n\\[\nH_{g_{\\bar\\Sigma_d} * \\bar\\ell}(\\mathbf{0}) = A^\\top \\left(H_{g_{\\Sigma_d} * \\ell}(T)\\right) A.\n\\]\n\nThen\n\n\\[\n \\operatorname{DetHess}[\\bar\\ell;\\bar\\Sigma_d]\n =\n (\\det A)^2 \\operatorname{DetHess}[\\ell;A\\bar\\Sigma_d A^\\top](T).\n\\]\n\nIn particular, for isotropic covariance matrices and similarity\ntransformations $A=sR$:\n\n\\[\n \\operatorname{DetHess}[\\bar\\ell;\\bar\\sigma_d^2]\n =\n s^4 \\operatorname{DetHess}[\\ell;s^2\\bar\\sigma_d^2](T)\n\\]\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@section covdet-laplacian Laplacian and Difference of Gaussians blobs\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n\nThe **Laplacian of Gaussian (LoG)** or **trace of the Hessian**\ncornerness measure is given by the trace of the Hessian of the image:\n\n\\[\n \\operatorname{Lap}[\\ell;\\sigma_d^2]\n =\n \\operatorname{tr} H_{g_{\\sigma_d}^2 * \\ell}\n\\]\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->\n@subsection covdet-laplacian-warped Laplacian in the warped domain\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->\n\nSimilarly to the Hessian measure, the Laplacian cornenress can often\nbe efficiently computed for features at all locations in the original\nunnormalized image domain. In particular, if the derivative covariance\nmatrix $\\Sigma_d$ is isotropic and one considers as warpings\nsimilarity transformations $A=sR$, where $R$ is a rotatin and $s$ a\nrescaling, one has\n\n\\[\n \\operatorname{Lap}[\\bar\\ell;\\bar\\sigma_d^2]\n =\n s^2 \\operatorname{Lap}[\\ell;s^2\\bar\\sigma_d^2](T)\n\\]\n\nNote that, comparing to the Harris and determinant of Hessian\nmeasures, the scaling for the Laplacian is $s^2$ rather than $s^4$.\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->\n@subsection covdet-laplacian-matched Laplacian as a matched filter\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->\n\nThe Laplacian is given by the trace of the Hessian\noperator. Differently from the determinant of the Hessian, this is a\nlinear operation. This means that computing the Laplacian cornerness\nmeasure can be seen as applying a linear filtering operator to the\nimage. This filter can then be interpreted as a *template* of a corner\nbeing matched to the image. Hence, the Laplacian cornerness measure\ncan be interpreted as matching this corner template at all possible\nimage locations.\n\nTo see this formally, compute the Laplacian score in the input image domain:\n\n\\[\n \\operatorname{Lap}[\\bar\\ell;\\bar\\sigma_d^2]\n =\n s^2 \\operatorname{Lap}[\\ell;s^2\\bar\\sigma_d^2](T)\n =\n s^2 (\\Delta g_{s^2\\bar\\sigma_d^2} * \\ell)(T)\n\\]\n\nThe Laplacian fitler is obtained by moving the Laplacian operator from\nthe image to the Gaussian smoothing kernel:\n\n\\[\n s^2 (\\Delta g_{s^2\\bar\\sigma_d^2} * \\ell)\n=\n (s^2 \\Delta g_{s^2\\bar\\sigma_d^2}) * \\ell\n\\]\n\nNote that the filter is rescaled by the $s^2$; sometimes, this factor\nis incorporated in the Laplacian operator, yielding the so-called\nnormalized Laplacian.\n\nThe Laplacian of Gaussian is also called *top-hat function* and has\nthe expression:\n\n\\[\n\\Delta g_{\\sigma^2}(x,y)\n=\n\\frac{x^2+y^2 - 2 \\sigma^2}{\\sigma^4} g_{\\sigma^2}(x,y).\n\\]\n\nThis filter, which acts as corner template, resembles a blob (a dark\ndisk surrounded by a bright ring).\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->\n@subsection covdet-laplacian-dog Difference of Gaussians\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -->\n\nThe **Difference of Gaussian** (DoG) cornerness measure can be\ninterpreted as an approximation of the Laplacian that is easy to\nobtain once a scalespace of the input image has been computed.\n\nAs noted above, the Laplacian cornerness of the normalized feature can\nbe computed directly from the input image by convolving the image by\nthe normalized Laplacian of Gaussian filter $s^2 \\Delta\ng_{s^2\\bar\\sigma_d^2}$.\n\nLike the other derivative operators, this filter is simpe to\ndiscriteize. However, it is often approximated by computing the the\n*Difference of Gaussians* (DoG) approximation instead. This\napproximation is obtained from the easily-proved identity:\n\n\\[\n  \\frac{\\partial}{\\partial \\sigma} g_{\\sigma^2} =\n  \\sigma \\Delta g_{\\sigma^2}.\n\\]\n\nThis indicates that computing the normalized Laplacian of a Gaussian\nfilter is, in the limit, the same as taking the difference between\nGaussian filters of slightly increasing standard deviation $\\sigma$\nand $\\kappa\\sigma$, where $\\kappa \\approx 1$:\n\n\\[\n\\sigma^2 \\Delta g_{\\sigma^2}\n\\approx\n\\sigma \\frac{g_{(\\kappa\\sigma)^2} - g_{\\sigma^2}}{\\kappa\\sigma - \\sigma}\n=\n\\frac{1}{\\kappa - 1}\n(g_{(\\kappa\\sigma)^2} - g_{\\sigma^2}).\n\\]\n\nOne nice propery of this expression is that the factor $\\sigma$\ncancels out in the right-hand side. Usually, scales $\\sigma$ and\n$\\kappa\\sigma$ are pre-computed in the image scale-space and\nsuccessive scales are sampled with uniform geometric spacing, meaning\nthat the factor $\\kappa$ is the same for all scales. Then, up to a\noverall scaling factor, the LoG cornerness measure can be obtained by\ntaking the difference of successive scale space images\n$\\ell_{(\\kappa\\sigma)^2}$ and $\\ell_{\\sigma^2}$.\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@page covdet-affine-adaptation Affine adaptation\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n@page covdet-dominant-orientation Dominant orientation\n<!-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~  -->\n**/\n\n#include "covdet.h"\n#include <string.h>\n\n/** @brief Reallocate buffer\n ** @param buffer\n ** @param bufferSize\n ** @param targetSize\n ** @return error code\n **/\n\nstatic int\n_vl_resize_buffer (void ** buffer, vl_size * bufferSize, vl_size targetSize) {\n  void * newBuffer ;\n  if (*buffer == NULL) {\n    *buffer = vl_malloc(targetSize) ;\n    if (*buffer) {\n      *bufferSize = targetSize ;\n      return VL_ERR_OK ;\n    } else {\n      *bufferSize = 0 ;\n      return VL_ERR_ALLOC ;\n    }\n  }\n  newBuffer = vl_realloc(*buffer, targetSize) ;\n  if (newBuffer) {\n    *buffer = newBuffer ;\n    *bufferSize = targetSize ;\n    return VL_ERR_OK ;\n  } else {\n    return VL_ERR_ALLOC ;\n  }\n}\n\n/** @brief Enlarge buffer\n ** @param buffer\n ** @param bufferSize\n ** @param targetSize\n ** @return error code\n **/\n\nstatic int\n_vl_enlarge_buffer (void ** buffer, vl_size * bufferSize, vl_size targetSize) {\n  if (*bufferSize >= targetSize) return VL_ERR_OK ;\n  return _vl_resize_buffer(buffer,bufferSize,targetSize) ;\n}\n\n/* ---------------------------------------------------------------- */\n/*                                            Finding local extrema */\n/* ---------------------------------------------------------------- */\n\n/* Todo: make this generally available in the library */\n\ntypedef struct _VlCovDetExtremum2\n{\n  vl_index xi ;\n  vl_index yi ;\n  float x ;\n  float y ;\n  float peakScore ;\n  float edgeScore ;\n} VlCovDetExtremum2 ;\n\ntypedef struct _VlCovDetExtremum3\n{\n  vl_index xi ;\n  vl_index yi ;\n  vl_index zi ;\n  float x ;\n  float y ;\n  float z ;\n  float peakScore ;\n  float edgeScore ;\n} VlCovDetExtremum3 ;\n\nVL_EXPORT vl_size\nvl_find_local_extrema_3 (vl_index ** extrema, vl_size * bufferSize,\n                         float const * map,\n                         vl_size width, vl_size height, vl_size depth,\n                         double threshold) ;\n\nVL_EXPORT vl_size\nvl_find_local_extrema_2 (vl_index ** extrema, vl_size * bufferSize,\n                         float const * map,\n                         vl_size width, vl_size height,\n                         double threshold) ;\n\nVL_EXPORT vl_bool\nvl_refine_local_extreum_3 (VlCovDetExtremum3 * refined,\n                           float const * map,\n                           vl_size width, vl_size height, vl_size depth,\n                           vl_index x, vl_index y, vl_index z) ;\n\nVL_EXPORT vl_bool\nvl_refine_local_extreum_2 (VlCovDetExtremum2 * refined,\n                           float const * map,\n                           vl_size width, vl_size height,\n                           vl_index x, vl_index y) ;\n\n/** @internal\n ** @brief Find the extrema of a 3D function\n ** @param extrema buffer containing the extrema found (in/out).\n ** @param bufferSize size of the @a extrema buffer in bytes (in/out).\n ** @param map a 3D array representing the map.\n ** @param width of the map.\n ** @param height of the map.\n ** @param depth of the map.\n ** @param threshold minumum extremum value.\n ** @return number of extrema found.\n ** @see @ref ::vl_refine_local_extreum_2.\n **/\n\nvl_size\nvl_find_local_extrema_3 (vl_index ** extrema, vl_size * bufferSize,\n                         float const * map,\n                         vl_size width, vl_size height, vl_size depth,\n                         double threshold)\n{\n  vl_index x, y, z ;\n  vl_size const xo = 1 ;\n  vl_size const yo = width ;\n  vl_size const zo = width * height ;\n  float const *pt = map + xo + yo + zo ;\n\n  vl_size numExtrema = 0 ;\n  vl_size requiredSize = 0 ;\n\n#define CHECK_NEIGHBORS_3(v,CMP,SGN)     (\\\nv CMP ## = SGN threshold &&               \\\nv CMP *(pt + xo) &&                       \\\nv CMP *(pt - xo) &&                       \\\nv CMP *(pt + zo) &&                       \\\nv CMP *(pt - zo) &&                       \\\nv CMP *(pt + yo) &&                       \\\nv CMP *(pt - yo) &&                       \\\n\\\nv CMP *(pt + yo + xo) &&                  \\\nv CMP *(pt + yo - xo) &&                  \\\nv CMP *(pt - yo + xo) &&                  \\\nv CMP *(pt - yo - xo) &&                  \\\n\\\nv CMP *(pt + xo      + zo) &&             \\\nv CMP *(pt - xo      + zo) &&             \\\nv CMP *(pt + yo      + zo) &&             \\\nv CMP *(pt - yo      + zo) &&             \\\nv CMP *(pt + yo + xo + zo) &&             \\\nv CMP *(pt + yo - xo + zo) &&             \\\nv CMP *(pt - yo + xo + zo) &&             \\\nv CMP *(pt - yo - xo + zo) &&             \\\n\\\nv CMP *(pt + xo      - zo) &&             \\\nv CMP *(pt - xo      - zo) &&             \\\nv CMP *(pt + yo      - zo) &&             \\\nv CMP *(pt - yo      - zo) &&             \\\nv CMP *(pt + yo + xo - zo) &&             \\\nv CMP *(pt + yo - xo - zo) &&             \\\nv CMP *(pt - yo + xo - zo) &&             \\\nv CMP *(pt - yo - xo - zo) )\n\n  for (z = 1 ; z < (signed)depth - 1 ; ++z) {\n    for (y = 1 ; y < (signed)height - 1 ; ++y) {\n      for (x = 1 ; x < (signed)width - 1 ; ++x) {\n        float value = *pt ;\n        if (CHECK_NEIGHBORS_3(value,>,+) || CHECK_NEIGHBORS_3(value,<,-)) {\n          numExtrema ++ ;\n          requiredSize += sizeof(vl_index) * 3 ;\n          if (*bufferSize < requiredSize) {\n            int err = _vl_resize_buffer((void**)extrema, bufferSize,\n                                        requiredSize + 2000 * 3 * sizeof(vl_index)) ;\n            if (err != VL_ERR_OK) abort() ;\n          }\n          (*extrema) [3 * (numExtrema - 1) + 0] = x ;\n          (*extrema) [3 * (numExtrema - 1) + 1] = y ;\n          (*extrema) [3 * (numExtrema - 1) + 2] = z ;\n        }\n        pt += xo ;\n      }\n      pt += 2*xo ;\n    }\n    pt += 2*yo ;\n  }\n  return numExtrema ;\n}\n\n/** @internal\n ** @brief Find extrema in a 2D function\n ** @param extrema buffer containing the found extrema (in/out).\n ** @param bufferSize size of the @a extrema buffer in bytes (in/out).\n ** @param map a 3D array representing the map.\n ** @param width of the map.\n ** @param height of the map.\n ** @param threshold minumum extremum value.\n ** @return number of extrema found.\n **\n ** An extremum contains 2 ::vl_index values; they are arranged\n ** sequentially.\n **\n ** The function can reuse an already allocated buffer if\n ** @a extrema and @a bufferSize are initialized on input.\n ** It may have to @a realloc the memory if the buffer is too small.\n **/\n\nvl_size\nvl_find_local_extrema_2 (vl_index ** extrema, vl_size * bufferSize,\n                         float const* map,\n                         vl_size width, vl_size height,\n                         double threshold)\n{\n  vl_index x, y ;\n  vl_size const xo = 1 ;\n  vl_size const yo = width ;\n  float const *pt = map + xo + yo ;\n\n  vl_size numExtrema = 0 ;\n  vl_size requiredSize = 0 ;\n#define CHECK_NEIGHBORS_2(v,CMP,SGN)     (\\\nv CMP ## = SGN threshold &&               \\\nv CMP *(pt + xo) &&                       \\\nv CMP *(pt - xo) &&                       \\\nv CMP *(pt + yo) &&                       \\\nv CMP *(pt - yo) &&                       \\\n\\\nv CMP *(pt + yo + xo) &&                  \\\nv CMP *(pt + yo - xo) &&                  \\\nv CMP *(pt - yo + xo) &&                  \\\nv CMP *(pt - yo - xo) )\n\n  for (y = 1 ; y < (signed)height - 1 ; ++y) {\n    for (x = 1 ; x < (signed)width - 1 ; ++x) {\n      float value = *pt ;\n      if (CHECK_NEIGHBORS_2(value,>,+) || CHECK_NEIGHBORS_2(value,<,-)) {\n        numExtrema ++ ;\n        requiredSize += sizeof(vl_index) * 2 ;\n        if (*bufferSize < requiredSize) {\n          int err = _vl_resize_buffer((void**)extrema, bufferSize,\n                                      requiredSize + 2000 * 2 * sizeof(vl_index)) ;\n          if (err != VL_ERR_OK) abort() ;\n        }\n        (*extrema) [2 * (numExtrema - 1) + 0] = x ;\n        (*extrema) [2 * (numExtrema - 1) + 1] = y ;\n      }\n      pt += xo ;\n    }\n    pt += 2*xo ;\n  }\n  return numExtrema ;\n}\n\n/** @internal\n ** @brief Refine the location of a local extremum of a 3D map\n ** @param refined refined extremum (out).\n ** @param map a 3D array representing the map.\n ** @param width of the map.\n ** @param height of the map.\n ** @param depth of the map.\n ** @param x initial x position.\n ** @param y initial y position.\n ** @param z initial z position.\n ** @return a flat indicating whether the extrema refinement was stable.\n **/\n\nVL_EXPORT vl_bool\nvl_refine_local_extreum_3 (VlCovDetExtremum3 * refined,\n                           float const * map,\n                           vl_size width, vl_size height, vl_size depth,\n                           vl_index x, vl_index y, vl_index z)\n{\n  vl_size const xo = 1 ;\n  vl_size const yo = width ;\n  vl_size const zo = width * height ;\n\n  double Dx=0,Dy=0,Dz=0,Dxx=0,Dyy=0,Dzz=0,Dxy=0,Dxz=0,Dyz=0 ;\n  double A [3*3], b [3] ;\n\n#define at(dx,dy,dz) (*(pt + (dx)*xo + (dy)*yo + (dz)*zo))\n#define Aat(i,j) (A[(i)+(j)*3])\n\n  float const * pt ;\n  vl_index dx = 0 ;\n  vl_index dy = 0 ;\n  /*vl_index dz = 0 ;*/\n  vl_index iter ;\n  int err ;\n\n  assert (map) ;\n  assert (1 <= x && x <= (signed)width - 2) ;\n  assert (1 <= y && y <= (signed)height - 2) ;\n  assert (1 <= z && z <= (signed)depth - 2) ;\n\n  for (iter = 0 ; iter < 5 ; ++iter) {\n    x += dx ;\n    y += dy ;\n    pt = map + x*xo + y*yo + z*zo ;\n\n    /* compute the gradient */\n    Dx = 0.5 * (at(+1,0,0) - at(-1,0,0)) ;\n    Dy = 0.5 * (at(0,+1,0) - at(0,-1,0));\n    Dz = 0.5 * (at(0,0,+1) - at(0,0,-1)) ;\n\n    /* compute the Hessian */\n    Dxx = (at(+1,0,0) + at(-1,0,0) - 2.0 * at(0,0,0)) ;\n    Dyy = (at(0,+1,0) + at(0,-1,0) - 2.0 * at(0,0,0)) ;\n    Dzz = (at(0,0,+1) + at(0,0,-1) - 2.0 * at(0,0,0)) ;\n\n    Dxy = 0.25 * (at(+1,+1,0) + at(-1,-1,0) - at(-1,+1,0) - at(+1,-1,0)) ;\n    Dxz = 0.25 * (at(+1,0,+1) + at(-1,0,-1) - at(-1,0,+1) - at(+1,0,-1)) ;\n    Dyz = 0.25 * (at(0,+1,+1) + at(0,-1,-1) - at(0,-1,+1) - at(0,+1,-1)) ;\n\n    /* solve linear system */\n    Aat(0,0) = Dxx ;\n    Aat(1,1) = Dyy ;\n    Aat(2,2) = Dzz ;\n    Aat(0,1) = Aat(1,0) = Dxy ;\n    Aat(0,2) = Aat(2,0) = Dxz ;\n    Aat(1,2) = Aat(2,1) = Dyz ;\n\n    b[0] = - Dx ;\n    b[1] = - Dy ;\n    b[2] = - Dz ;\n\n    err = vl_solve_linear_system_3(b, A, b) ;\n\n    if (err != VL_ERR_OK) {\n      b[0] = 0 ;\n      b[1] = 0 ;\n      b[2] = 0 ;\n      break ;\n    }\n\n    /* Keep going if there is sufficient translation */\n\n    dx = (b[0] > 0.6 && x < (signed)width - 2 ?  1 : 0)\n    + (b[0] < -0.6 && x > 1 ? -1 : 0) ;\n\n    dy = (b[1] > 0.6 && y < (signed)height - 2 ?  1 : 0)\n    + (b[1] < -0.6 && y > 1 ? -1 : 0) ;\n\n    if (dx == 0 && dy == 0) break ;\n  }\n\n  /* check threshold and other conditions */\n  {\n    double peakScore = at(0,0,0)\n    + 0.5 * (Dx * b[0] + Dy * b[1] + Dz * b[2]) ;\n    double alpha = (Dxx+Dyy)*(Dxx+Dyy) / (Dxx*Dyy - Dxy*Dxy) ;\n    double edgeScore ;\n\n    if (alpha < 0) {\n      /* not an extremum */\n      edgeScore = VL_INFINITY_D ;\n    } else {\n      edgeScore = (0.5*alpha - 1) + sqrt(VL_MAX(0.25*alpha - 1,0)*alpha) ;\n    }\n\n    refined->xi = x ;\n    refined->yi = y ;\n    refined->zi = z ;\n    refined->x = x + b[0] ;\n    refined->y = y + b[1] ;\n    refined->z = z + b[2] ;\n    refined->peakScore = peakScore ;\n    refined->edgeScore = edgeScore ;\n\n    return\n    err == VL_ERR_OK &&\n    vl_abs_d(b[0]) < 1.5 &&\n    vl_abs_d(b[1]) < 1.5 &&\n    vl_abs_d(b[2]) < 1.5 &&\n    0 <= refined->x && refined->x <= (signed)width - 1 &&\n    0 <= refined->y && refined->y <= (signed)height - 1 &&\n    0 <= refined->z && refined->z <= (signed)depth - 1 ;\n  }\n#undef Aat\n#undef at\n}\n\n/** @internal\n ** @brief Refine the location of a local extremum of a 2D map\n ** @param refined refined extremum (out).\n ** @param map a 2D array representing the map.\n ** @param width of the map.\n ** @param height of the map.\n ** @param x initial x position.\n ** @param y initial y position.\n ** @return a flat indicating whether the extrema refinement was stable.\n **/\n\nVL_EXPORT vl_bool\nvl_refine_local_extreum_2 (VlCovDetExtremum2 * refined,\n                           float const * map,\n                           vl_size width, vl_size height,\n                           vl_index x, vl_index y)\n{\n  vl_size const xo = 1 ;\n  vl_size const yo = width ;\n\n  double Dx=0,Dy=0,Dxx=0,Dyy=0,Dxy=0;\n  double A [2*2], b [2] ;\n\n#define at(dx,dy) (*(pt + (dx)*xo + (dy)*yo ))\n#define Aat(i,j) (A[(i)+(j)*2])\n\n  float const * pt ;\n  vl_index dx = 0 ;\n  vl_index dy = 0 ;\n  vl_index iter ;\n  int err ;\n\n  assert (map) ;\n  assert (1 <= x && x <= (signed)width - 2) ;\n  assert (1 <= y && y <= (signed)height - 2) ;\n\n  for (iter = 0 ; iter < 5 ; ++iter) {\n    x += dx ;\n    y += dy ;\n    pt = map + x*xo + y*yo  ;\n\n    /* compute the gradient */\n    Dx = 0.5 * (at(+1,0) - at(-1,0)) ;\n    Dy = 0.5 * (at(0,+1) - at(0,-1));\n\n    /* compute the Hessian */\n    Dxx = (at(+1,0) + at(-1,0) - 2.0 * at(0,0)) ;\n    Dyy = (at(0,+1) + at(0,-1) - 2.0 * at(0,0)) ;\n    Dxy = 0.25 * (at(+1,+1) + at(-1,-1) - at(-1,+1) - at(+1,-1)) ;\n\n    /* solve linear system */\n    Aat(0,0) = Dxx ;\n    Aat(1,1) = Dyy ;\n    Aat(0,1) = Aat(1,0) = Dxy ;\n\n    b[0] = - Dx ;\n    b[1] = - Dy ;\n\n    err = vl_solve_linear_system_2(b, A, b) ;\n\n    if (err != VL_ERR_OK) {\n      b[0] = 0 ;\n      b[1] = 0 ;\n      break ;\n    }\n\n    /* Keep going if there is sufficient translation */\n\n    dx = (b[0] > 0.6 && x < (signed)width - 2 ?  1 : 0)\n    + (b[0] < -0.6 && x > 1 ? -1 : 0) ;\n\n    dy = (b[1] > 0.6 && y < (signed)height - 2 ?  1 : 0)\n    + (b[1] < -0.6 && y > 1 ? -1 : 0) ;\n\n    if (dx == 0 && dy == 0) break ;\n  }\n\n  /* check threshold and other conditions */\n  {\n    double peakScore = at(0,0) + 0.5 * (Dx * b[0] + Dy * b[1]) ;\n    double alpha = (Dxx+Dyy)*(Dxx+Dyy) / (Dxx*Dyy - Dxy*Dxy) ;\n    double edgeScore ;\n\n    if (alpha < 0) {\n      /* not an extremum */\n      edgeScore = VL_INFINITY_D ;\n    } else {\n      edgeScore = (0.5*alpha - 1) + sqrt(VL_MAX(0.25*alpha - 1,0)*alpha) ;\n    }\n\n    refined->xi = x ;\n    refined->yi = y ;\n    refined->x = x + b[0] ;\n    refined->y = y + b[1] ;\n    refined->peakScore = peakScore ;\n    refined->edgeScore = edgeScore ;\n\n    return\n    err == VL_ERR_OK &&\n    vl_abs_d(b[0]) < 1.5 &&\n    vl_abs_d(b[1]) < 1.5 &&\n    0 <= refined->x && refined->x <= (signed)width - 1 &&\n    0 <= refined->y && refined->y <= (signed)height - 1 ;\n  }\n#undef Aat\n#undef at\n}\n\n/* ---------------------------------------------------------------- */\n/*                                                Covarant detector */\n/* ---------------------------------------------------------------- */\n\n#define VL_COVDET_MAX_NUM_ORIENTATIONS 4\n#define VL_COVDET_MAX_NUM_LAPLACIAN_SCALES 4\n#define VL_COVDET_AA_PATCH_RESOLUTION 20\n#define VL_COVDET_AA_MAX_NUM_ITERATIONS 15\n#define VL_COVDET_OR_NUM_ORIENTATION_HISTOGAM_BINS 36\n#define VL_COVDET_AA_RELATIVE_INTEGRATION_SIGMA 3\n#define VL_COVDET_AA_RELATIVE_DERIVATIVE_SIGMA 1\n#define VL_COVDET_AA_MAX_ANISOTROPY 5\n#define VL_COVDET_AA_CONVERGENCE_THRESHOLD 1.001\n#define VL_COVDET_AA_ACCURATE_SMOOTHING VL_FALSE\n#define VL_COVDET_AA_PATCH_EXTENT (3*VL_COVDET_AA_RELATIVE_INTEGRATION_SIGMA)\n#define VL_COVDET_OR_ADDITIONAL_PEAKS_RELATIVE_SIZE 0.8\n#define VL_COVDET_LAP_NUM_LEVELS 10\n#define VL_COVDET_LAP_PATCH_RESOLUTION 16\n#define VL_COVDET_LAP_DEF_PEAK_THRESHOLD 0.01\n#define VL_COVDET_DOG_DEF_PEAK_THRESHOLD VL_COVDET_LAP_DEF_PEAK_THRESHOLD\n#define VL_COVDET_DOG_DEF_EDGE_THRESHOLD 10.0\n#define VL_COVDET_HARRIS_DEF_PEAK_THRESHOLD 0.000002\n#define VL_COVDET_HARRIS_DEF_EDGE_THRESHOLD 10.0\n#define VL_COVDET_HESSIAN_DEF_PEAK_THRESHOLD 0.003\n#define VL_COVDET_HESSIAN_DEF_EDGE_THRESHOLD 10.0\n#define VL_COVDET_GSS_BASE_SCALE 1.6\n\n/** @brief Covariant feature detector */\nstruct _VlCovDet\n{\n  VlScaleSpace *gss ;          /**< Gaussian scale space. */\n  VlScaleSpace *css ;          /**< Cornerness scale space. */\n  VlCovDetMethod method ;      /**< feature extraction method. */\n  double peakThreshold ;       /**< peak threshold. */\n  double edgeThreshold ;       /**< edge threshold. */\n  double lapPeakThreshold;     /**< peak threshold for Laplacian scale selection. */\n  vl_size octaveResolution ;   /**< resolution of each octave. */\n  vl_index numOctaves ;        /**< number of octaves */\n  vl_index firstOctave ;       /**< index of the first octave. */\n  double baseScale ;           /**< the base scale of the gss. */\n  vl_size maxNumOrientations ; /**< max number of detected orientations. */\n\n  double nonExtremaSuppression ;\n  vl_size numNonExtremaSuppressed ;\n\n  VlCovDetFeature *features ;\n  vl_size numFeatures ;\n  vl_size numFeatureBufferSize ;\n\n  float * patch ;\n  vl_size patchBufferSize ;\n\n  vl_bool transposed ;\n  VlCovDetFeatureOrientation orientations [VL_COVDET_MAX_NUM_ORIENTATIONS] ;\n  VlCovDetFeatureLaplacianScale scales [VL_COVDET_MAX_NUM_LAPLACIAN_SCALES] ;\n\n  vl_bool aaAccurateSmoothing ;\n  float aaPatch [(2*VL_COVDET_AA_PATCH_RESOLUTION+1)*(2*VL_COVDET_AA_PATCH_RESOLUTION+1)] ;\n  float aaPatchX [(2*VL_COVDET_AA_PATCH_RESOLUTION+1)*(2*VL_COVDET_AA_PATCH_RESOLUTION+1)] ;\n  float aaPatchY [(2*VL_COVDET_AA_PATCH_RESOLUTION+1)*(2*VL_COVDET_AA_PATCH_RESOLUTION+1)] ;\n  float aaMask [(2*VL_COVDET_AA_PATCH_RESOLUTION+1)*(2*VL_COVDET_AA_PATCH_RESOLUTION+1)] ;\n\n  float lapPatch [(2*VL_COVDET_LAP_PATCH_RESOLUTION+1)*(2*VL_COVDET_LAP_PATCH_RESOLUTION+1)] ;\n  float laplacians [(2*VL_COVDET_LAP_PATCH_RESOLUTION+1)*(2*VL_COVDET_LAP_PATCH_RESOLUTION+1)*VL_COVDET_LAP_NUM_LEVELS] ;\n  vl_size numFeaturesWithNumScales [VL_COVDET_MAX_NUM_LAPLACIAN_SCALES + 1] ;\n\n  vl_bool allowPaddedWarping ;\n}  ;\n\nVlEnumerator vlCovdetMethods [VL_COVDET_METHOD_NUM] = {\n  {"DoG" ,              (vl_index)VL_COVDET_METHOD_DOG               },\n  {"Hessian",           (vl_index)VL_COVDET_METHOD_HESSIAN           },\n  {"HessianLaplace",    (vl_index)VL_COVDET_METHOD_HESSIAN_LAPLACE   },\n  {"HarrisLaplace",     (vl_index)VL_COVDET_METHOD_HARRIS_LAPLACE    },\n  {"MultiscaleHessian", (vl_index)VL_COVDET_METHOD_MULTISCALE_HESSIAN},\n  {"MultiscaleHarris",  (vl_index)VL_COVDET_METHOD_MULTISCALE_HARRIS },\n  {0,                   0                                            }\n} ;\n\n/** @brief Create a new object instance\n ** @param method method for covariant feature detection.\n ** @return new covariant detector.\n **/\n\nVlCovDet *\nvl_covdet_new (VlCovDetMethod method)\n{\n  VlCovDet * self = vl_calloc(sizeof(VlCovDet),1) ;\n  self->method = method ;\n  self->octaveResolution = 3 ;\n  self->numOctaves = -1 ;\n  self->firstOctave = -1 ;\n  self->baseScale = VL_COVDET_GSS_BASE_SCALE ;\n  self->maxNumOrientations = VL_COVDET_MAX_NUM_ORIENTATIONS ;\n  switch (self->method) {\n    case VL_COVDET_METHOD_DOG :\n      self->peakThreshold = VL_COVDET_DOG_DEF_PEAK_THRESHOLD ;\n      self->edgeThreshold = VL_COVDET_DOG_DEF_EDGE_THRESHOLD ;\n      self->lapPeakThreshold = 0  ; /* not used */\n      break ;\n    case VL_COVDET_METHOD_HARRIS_LAPLACE:\n    case VL_COVDET_METHOD_MULTISCALE_HARRIS:\n      self->peakThreshold = VL_COVDET_HARRIS_DEF_PEAK_THRESHOLD ;\n      self->edgeThreshold = VL_COVDET_HARRIS_DEF_EDGE_THRESHOLD ;\n      self->lapPeakThreshold = VL_COVDET_LAP_DEF_PEAK_THRESHOLD ;\n      break ;\n    case VL_COVDET_METHOD_HESSIAN :\n    case VL_COVDET_METHOD_HESSIAN_LAPLACE:\n    case VL_COVDET_METHOD_MULTISCALE_HESSIAN:\n      self->peakThreshold = VL_COVDET_HESSIAN_DEF_PEAK_THRESHOLD ;\n      self->edgeThreshold = VL_COVDET_HESSIAN_DEF_EDGE_THRESHOLD ;\n      self->lapPeakThreshold = VL_COVDET_LAP_DEF_PEAK_THRESHOLD ;\n      break;\n    default:\n      assert(0) ;\n  }\n\n  self->nonExtremaSuppression = 0.5 ;\n  self->features = NULL ;\n  self->numFeatures = 0 ;\n  self->numFeatureBufferSize = 0 ;\n  self->patch = NULL ;\n  self->patchBufferSize = 0 ;\n  self->transposed = VL_FALSE ;\n  self->aaAccurateSmoothing = VL_COVDET_AA_ACCURATE_SMOOTHING ;\n  self->allowPaddedWarping = VL_TRUE ;\n\n  {\n    vl_index const w = VL_COVDET_AA_PATCH_RESOLUTION ;\n    vl_index i,j ;\n    double step = (2.0 * VL_COVDET_AA_PATCH_EXTENT) / (2*w+1) ;\n    double sigma = VL_COVDET_AA_RELATIVE_INTEGRATION_SIGMA ;\n    for (j = -w ; j <= w ; ++j) {\n      for (i = -w ; i <= w ; ++i) {\n        double dx = i*step/sigma ;\n        double dy = j*step/sigma ;\n        self->aaMask[(i+w) + (2*w+1)*(j+w)] = exp(-0.5*(dx*dx+dy*dy)) ;\n      }\n    }\n  }\n\n  {\n    /*\n     Covers one octave of Laplacian filters, from sigma=1 to sigma=2.\n     The spatial sampling step is 0.5.\n     */\n    vl_index s ;\n    for (s = 0 ; s < VL_COVDET_LAP_NUM_LEVELS ; ++s) {\n      double sigmaLap = pow(2.0, -0.5 +\n                            (double)s / (VL_COVDET_LAP_NUM_LEVELS - 1)) ;\n      double const sigmaImage = 1.0 / sqrt(2.0) ;\n      double const step = 0.5 * sigmaImage ;\n      double const sigmaDelta = sqrt(sigmaLap*sigmaLap - sigmaImage*sigmaImage) ;\n      vl_size const w = VL_COVDET_LAP_PATCH_RESOLUTION ;\n      vl_size const num = 2 * w + 1  ;\n      float * pt = self->laplacians + s * (num * num) ;\n\n      memset(pt, 0, num * num * sizeof(float)) ;\n\n#define at(x,y) pt[(x+w)+(y+w)*(2*w+1)]\n      at(0,0) = - 4.0 ;\n      at(-1,0) = 1.0 ;\n      at(+1,0) = 1.0 ;\n      at(0,1) = 1.0 ;\n      at(0,-1) = 1.0 ;\n#undef at\n\n      vl_imsmooth_f(pt, num,\n                    pt, num, num, num,\n                    sigmaDelta / step, sigmaDelta / step) ;\n\n#if 0\n      {\n        char name [200] ;\n        snprintf(name, 200, "/tmp/%f-lap.pgm", sigmaDelta) ;\n        vl_pgm_write_f(name, pt, num, num) ;\n      }\n#endif\n\n    }\n  }\n  return self ;\n}\n\n/** @brief Reset object\n ** @param self object.\n **\n ** This function removes any buffered features and frees other\n ** internal buffers.\n **/\n\nvoid\nvl_covdet_reset (VlCovDet * self)\n{\n  if (self->features) {\n    vl_free(self->features) ;\n    self->features = NULL ;\n  }\n  if (self->css) {\n    vl_scalespace_delete(self->css) ;\n    self->css = NULL ;\n  }\n  if (self->gss) {\n    vl_scalespace_delete(self->gss) ;\n    self->gss = NULL ;\n  }\n}\n\n/** @brief Delete object instance\n ** @param self object.\n **/\n\nvoid\nvl_covdet_delete (VlCovDet * self)\n{\n  vl_covdet_reset(self) ;\n  if (self->patch) vl_free (self->patch) ;\n  vl_free(self) ;\n}\n\n/** @brief Append a feature to the internal buffer.\n ** @param self object.\n ** @param feature a pointer to the feature to append.\n ** @return status.\n **\n ** The feature is copied. The function may fail with @c status\n ** equal to ::VL_ERR_ALLOC if there is insufficient memory.\n **/\n\nint\nvl_covdet_append_feature (VlCovDet * self, VlCovDetFeature const * feature)\n{\n  vl_size requiredSize ;\n  assert(self) ;\n  assert(feature) ;\n  self->numFeatures ++ ;\n  requiredSize = self->numFeatures * sizeof(VlCovDetFeature) ;\n  if (requiredSize > self->numFeatureBufferSize) {\n    int err = _vl_resize_buffer((void**)&self->features, &self->numFeatureBufferSize,\n                                (self->numFeatures + 1000) * sizeof(VlCovDetFeature)) ;\n    if (err) {\n      self->numFeatures -- ;\n      return err ;\n    }\n  }\n  self->features[self->numFeatures - 1] = *feature ;\n  return VL_ERR_OK ;\n}\n\n/* ---------------------------------------------------------------- */\n/*                                              Process a new image */\n/* ---------------------------------------------------------------- */\n\n/** @brief Detect features in an image\n ** @param self object.\n ** @param image image to process.\n ** @param width image width.\n ** @param height image height.\n ** @return status.\n **\n ** @a width and @a height must be at least one pixel. The function\n ** fails by returing ::VL_ERR_ALLOC if the memory is insufficient.\n **/\n\nint\nvl_covdet_put_image (VlCovDet * self,\n                     float const * image,\n                     vl_size width, vl_size height)\n{\n  vl_size const minOctaveSize = 16 ;\n  vl_index lastOctave ;\n  vl_index octaveFirstSubdivision ;\n  vl_index octaveLastSubdivision ;\n  VlScaleSpaceGeometry geom = vl_scalespace_get_default_geometry(width,height) ;\n\n  assert (self) ;\n  assert (image) ;\n  assert (width >= 1) ;\n  assert (height >= 1) ;\n\n  /* (minOctaveSize - 1) 2^lastOctave <= min(width,height) - 1 */\n  lastOctave = vl_floor_d(vl_log2_d(VL_MIN((double)width-1,(double)height-1) / (minOctaveSize - 1))) ;\n  if (self->numOctaves > 0) {\n      lastOctave = VL_MIN((vl_index)self->numOctaves - self->firstOctave - 1, lastOctave);\n  }\n\n  if (self->method == VL_COVDET_METHOD_DOG) {\n    octaveFirstSubdivision = -1 ;\n    octaveLastSubdivision = self->octaveResolution + 1 ;\n  } else if (self->method == VL_COVDET_METHOD_HESSIAN) {\n    octaveFirstSubdivision = -1 ;\n    octaveLastSubdivision = self->octaveResolution ;\n  } else {\n    octaveFirstSubdivision = 0 ;\n    octaveLastSubdivision = self->octaveResolution - 1 ;\n  }\n\n  geom.width = width ;\n  geom.height = height ;\n  geom.firstOctave = self->firstOctave ;\n  geom.lastOctave = lastOctave ;\n  geom.octaveResolution = self->octaveResolution ;\n  geom.baseScale = self->baseScale * pow(2.0, 1.0 / self->octaveResolution) ;\n  geom.octaveFirstSubdivision = octaveFirstSubdivision ;\n  geom.octaveLastSubdivision = octaveLastSubdivision ;\n\n  if (self->gss == NULL ||\n      ! vl_scalespacegeometry_is_equal (geom,\n                                        vl_scalespace_get_geometry(self->gss)))\n  {\n    if (self->gss) vl_scalespace_delete(self->gss) ;\n    self->gss = vl_scalespace_new_with_geometry(geom) ;\n    if (self->gss == NULL) return VL_ERR_ALLOC ;\n  }\n  vl_scalespace_put_image(self->gss, image) ;\n  return VL_ERR_OK ;\n}\n\n/* ---------------------------------------------------------------- */\n/*                                              Cornerness measures */\n/* ---------------------------------------------------------------- */\n\n/** @brief Scaled derminant of the Hessian filter\n ** @param hessian output image.\n ** @param image input image.\n ** @param width image width.\n ** @param height image height.\n ** @param step image sampling step (pixel size).\n ** @param sigma Gaussian smoothing of the input image.\n **/\n\nstatic void\n_vl_det_hessian_response (float * hessian,\n                          float const * image,\n                          vl_size width, vl_size height,\n                          double step, double sigma)\n{\n  float factor = (float) pow(sigma/step, 4.0) ;\n  vl_index const xo = 1 ; /* x-stride */\n  vl_index const yo = width;  /* y-stride */\n  vl_size r, c;\n\n  float p11, p12, p13, p21, p22, p23, p31, p32, p33;\n\n  /* setup input pointer to be centered at 0,1 */\n  float const *in = image + yo ;\n\n  /* setup output pointer to be centered at 1,1 */\n  float *out = hessian + xo + yo;\n\n  /* move 3x3 window and convolve */\n  for (r = 1; r < height - 1; ++r)\n  {\n    /* fill in shift registers at the beginning of the row */\n    p11 = in[-yo]; p12 = in[xo - yo];\n    p21 = in[  0]; p22 = in[xo     ];\n    p31 = in[+yo]; p32 = in[xo + yo];\n    /* setup input pointer to (2,1) of the 3x3 square */\n    in += 2;\n    for (c = 1; c < width - 1; ++c)\n    {\n      float Lxx, Lyy, Lxy;\n      /* fetch remaining values (last column) */\n      p13 = in[-yo]; p23 = *in; p33 = in[+yo];\n\n      /* Compute 3x3 Hessian values from pixel differences. */\n      Lxx = (-p21 + 2*p22 - p23);\n      Lyy = (-p12 + 2*p22 - p32);\n      Lxy = ((p11 - p31 - p13 + p33)/4.0f);\n\n      /* normalize and write out */\n      *out = (Lxx * Lyy - Lxy * Lxy) * factor ;\n\n      /* move window */\n      p11=p12; p12=p13;\n      p21=p22; p22=p23;\n      p31=p32; p32=p33;\n\n      /* move input/output pointers */\n      in++; out++;\n    }\n    out += 2;\n  }\n\n  /* Copy the computed values to borders */\n  in = hessian + yo + xo ;\n  out = hessian + xo ;\n\n  /* Top row without corners */\n  memcpy(out, in, (width - 2)*sizeof(float));\n  out--;\n  in -= yo;\n\n  /* Left border columns without last row */\n  for (r = 0; r < height - 1; r++){\n    *out = *in;\n    *(out + yo - 1) = *(in + yo - 3);\n    in += yo;\n    out += yo;\n  }\n\n  /* Bottom corners */\n  in -= yo;\n  *out = *in;\n  *(out + yo - 1) = *(in + yo - 3);\n\n  /* Bottom row without corners */\n  out++;\n  memcpy(out, in, (width - 2)*sizeof(float));\n}\n\n/** @brief Scale-normalised Harris response\n ** @param harris output image.\n ** @param image input image.\n ** @param width image width.\n ** @param height image height.\n ** @param step image sampling step (pixel size).\n ** @param sigma Gaussian smoothing of the input image.\n ** @param sigmaI integration scale.\n ** @param alpha factor in the definition of the Harris score.\n **/\n\nstatic void\n_vl_harris_response (float * harris,\n                     float const * image,\n                     vl_size width, vl_size height,\n                     double step, double sigma,\n                     double sigmaI, double alpha)\n{\n  float factor = (float) pow(sigma/step, 4.0) ;\n  vl_index k ;\n\n  float * LxLx ;\n  float * LyLy ;\n  float * LxLy ;\n\n  LxLx = vl_malloc(sizeof(float) * width * height) ;\n  LyLy = vl_malloc(sizeof(float) * width * height) ;\n  LxLy = vl_malloc(sizeof(float) * width * height) ;\n\n  vl_imgradient_f (LxLx, LyLy, 1, width, image, width, height, width) ;\n\n  for (k = 0 ; k < (signed)(width * height) ; ++k) {\n    float dx = LxLx[k] ;\n    float dy = LyLy[k] ;\n    LxLx[k] = dx*dx ;\n    LyLy[k] = dy*dy ;\n    LxLy[k] = dx*dy ;\n  }\n\n  vl_imsmooth_f(LxLx, width, LxLx, width, height, width,\n                sigmaI / step, sigmaI / step) ;\n\n  vl_imsmooth_f(LyLy, width, LyLy, width, height, width,\n                sigmaI / step, sigmaI / step) ;\n\n  vl_imsmooth_f(LxLy, width, LxLy, width, height, width,\n                sigmaI / step, sigmaI / step) ;\n\n  for (k = 0 ; k < (signed)(width * height) ; ++k) {\n    float a = LxLx[k] ;\n    float b = LyLy[k] ;\n    float c = LxLy[k] ;\n\n    float determinant = a * b - c * c ;\n    float trace = a + b ;\n\n    harris[k] = factor * (determinant - alpha * (trace * trace)) ;\n  }\n\n  vl_free(LxLy) ;\n  vl_free(LyLy) ;\n  vl_free(LxLx) ;\n}\n\n/** @brief Difference of Gaussian\n ** @param dog output image.\n ** @param level1 input image at the smaller Gaussian scale.\n ** @param level2 input image at the larger Gaussian scale.\n ** @param width image width.\n ** @param height image height.\n **/\n\nstatic void\n_vl_dog_response (float * dog,\n                  float const * level1,\n                  float const * level2,\n                  vl_size width, vl_size height)\n{\n  vl_index k ;\n  for (k = 0 ; k < (signed)(width*height) ; ++k) {\n    dog[k] = level2[k] - level1[k] ;\n  }\n}\n\n/* ---------------------------------------------------------------- */\n/*                                                  Detect features */\n/* ---------------------------------------------------------------- */\n\n/** @brief Detect scale-space features\n ** @param self object.\n **\n ** This function runs the configured feature detector on the image\n ** that was passed by using ::vl_covdet_put_image.\n **/\n\nvoid\nvl_covdet_detect (VlCovDet * self)\n{\n  VlScaleSpaceGeometry geom = vl_scalespace_get_geometry(self->gss) ;\n  VlScaleSpaceGeometry cgeom ;\n  float * levelxx = NULL ;\n  float * levelyy = NULL ;\n  float * levelxy = NULL ;\n  vl_index o, s ;\n\n  assert (self) ;\n  assert (self->gss) ;\n\n  /* clear previous detections if any */\n  self->numFeatures = 0 ;\n\n  /* prepare buffers ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */\n  cgeom = geom ;\n  if (self->method == VL_COVDET_METHOD_DOG) {\n    cgeom.octaveLastSubdivision -= 1 ;\n  }\n  if (!self->css ||\n      !vl_scalespacegeometry_is_equal(cgeom,\n                                      vl_scalespace_get_geometry(self->css)))\n  {\n    if (self->css) vl_scalespace_delete(self->css) ;\n    self->css = vl_scalespace_new_with_geometry(cgeom) ;\n  }\n  if (self->method == VL_COVDET_METHOD_HARRIS_LAPLACE ||\n      self->method == VL_COVDET_METHOD_MULTISCALE_HARRIS) {\n    VlScaleSpaceOctaveGeometry oct = vl_scalespace_get_octave_geometry(self->gss, geom.firstOctave) ;\n    levelxx = vl_malloc(oct.width * oct.height * sizeof(float)) ;\n    levelyy = vl_malloc(oct.width * oct.height * sizeof(float)) ;\n    levelxy = vl_malloc(oct.width * oct.height * sizeof(float)) ;\n  }\n\n  /* compute cornerness ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */\n  for (o = cgeom.firstOctave ; o <= cgeom.lastOctave ; ++o) {\n    VlScaleSpaceOctaveGeometry oct = vl_scalespace_get_octave_geometry(self->css, o) ;\n\n    for (s = cgeom.octaveFirstSubdivision ; s <= cgeom.octaveLastSubdivision ; ++s) {\n      float * level = vl_scalespace_get_level(self->gss, o, s) ;\n      float * clevel = vl_scalespace_get_level(self->css, o, s) ;\n      double sigma = vl_scalespace_get_level_sigma(self->css, o, s) ;\n      switch (self->method) {\n        case VL_COVDET_METHOD_DOG:\n          _vl_dog_response(clevel,\n                           vl_scalespace_get_level(self->gss, o, s + 1),\n                           level,\n                           oct.width, oct.height) ;\n          break ;\n\n        case VL_COVDET_METHOD_HARRIS_LAPLACE:\n        case VL_COVDET_METHOD_MULTISCALE_HARRIS:\n          _vl_harris_response(clevel,\n                              level, oct.width, oct.height, oct.step,\n                              sigma, 1.4 * sigma, 0.05) ;\n          break ;\n\n        case VL_COVDET_METHOD_HESSIAN:\n        case VL_COVDET_METHOD_HESSIAN_LAPLACE:\n        case VL_COVDET_METHOD_MULTISCALE_HESSIAN:\n          _vl_det_hessian_response(clevel, level, oct.width, oct.height, oct.step, sigma) ;\n          break ;\n\n        default:\n          assert(0) ;\n      }\n    }\n  }\n\n  /* find and refine local maxima ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ */\n  {\n    vl_index * extrema = NULL ;\n    vl_size extremaBufferSize = 0 ;\n    vl_size numExtrema ;\n    vl_size index ;\n    for (o = cgeom.firstOctave ; o <= cgeom.lastOctave ; ++o) {\n      VlScaleSpaceOctaveGeometry octgeom = vl_scalespace_get_octave_geometry(self->css, o) ;\n      double step = octgeom.step ;\n      vl_size width = octgeom.width ;\n      vl_size height = octgeom.height ;\n      vl_size depth = cgeom.octaveLastSubdivision - cgeom.octaveFirstSubdivision + 1 ;\n\n      switch (self->method) {\n        case VL_COVDET_METHOD_DOG:\n        case VL_COVDET_METHOD_HESSIAN:\n        {\n          /* scale-space extrema */\n          float const * octave =\n          vl_scalespace_get_level(self->css, o, cgeom.octaveFirstSubdivision) ;\n          numExtrema = vl_find_local_extrema_3(&extrema, &extremaBufferSize,\n                                               octave, width, height, depth,\n                                               0.8 * self->peakThreshold);\n          for (index = 0 ; index < numExtrema ; ++index) {\n            VlCovDetExtremum3 refined ;\n            VlCovDetFeature feature ;\n            vl_bool ok ;\n            memset(&feature, 0, sizeof(feature)) ;\n            ok = vl_refine_local_extreum_3(&refined,\n                                           octave, width, height, depth,\n                                           extrema[3*index+0],\n                                           extrema[3*index+1],\n                                           extrema[3*index+2]) ;\n            ok &= fabs(refined.peakScore) > self->peakThreshold ;\n            ok &= refined.edgeScore < self->edgeThreshold ;\n            if (ok) {\n              double sigma = cgeom.baseScale *\n              pow(2.0, o + (refined.z + cgeom.octaveFirstSubdivision)\n                  / cgeom.octaveResolution) ;\n              feature.frame.x = refined.x * step ;\n              feature.frame.y = refined.y * step ;\n              feature.frame.a11 = sigma ;\n              feature.frame.a12 = 0.0 ;\n              feature.frame.a21 = 0.0 ;\n              feature.frame.a22 = sigma ;\n              feature.peakScore = refined.peakScore ;\n              feature.edgeScore = refined.edgeScore ;\n              vl_covdet_append_feature(self, &feature) ;\n            }\n          }\n          break ;\n        }\n\n        default:\n        {\n          for (s = cgeom.octaveFirstSubdivision ; s < cgeom.octaveLastSubdivision ; ++s) {\n            /* space extrema */\n            float const * level = vl_scalespace_get_level(self->css,o,s) ;\n            numExtrema = vl_find_local_extrema_2(&extrema, &extremaBufferSize,\n                                                 level,\n                                                 width, height,\n                                                 0.8 * self->peakThreshold);\n            for (index = 0 ; index < numExtrema ; ++index) {\n              VlCovDetExtremum2 refined ;\n              VlCovDetFeature feature ;\n              vl_bool ok ;\n              memset(&feature, 0, sizeof(feature)) ;\n              ok = vl_refine_local_extreum_2(&refined,\n                                             level, width, height,\n                                             extrema[2*index+0],\n                                             extrema[2*index+1]);\n              ok &= fabs(refined.peakScore) > self->peakThreshold ;\n              ok &= refined.edgeScore < self->edgeThreshold ;\n              if (ok) {\n                double sigma = cgeom.baseScale *\n                pow(2.0, o + (double)s / cgeom.octaveResolution) ;\n                feature.frame.x = refined.x * step ;\n                feature.frame.y = refined.y * step ;\n                feature.frame.a11 = sigma ;\n                feature.frame.a12 = 0.0 ;\n                feature.frame.a21 = 0.0 ;\n                feature.frame.a22 = sigma ;\n                feature.peakScore = refined.peakScore ;\n                feature.edgeScore = refined.edgeScore ;\n                vl_covdet_append_feature(self, &feature) ;\n              }\n            }\n          }\n          break ;\n        }\n      }\n    } /* next octave */\n\n    if (extrema) { vl_free(extrema) ; extrema = 0 ; }\n  }\n\n  /* Laplacian scale selection for certain methods */\n  switch (self->method) {\n    case VL_COVDET_METHOD_HARRIS_LAPLACE :\n    case VL_COVDET_METHOD_HESSIAN_LAPLACE :\n      vl_covdet_extract_laplacian_scales (self) ;\n      break ;\n    default:\n      break ;\n  }\n\n  if (self->nonExtremaSuppression) {\n    vl_index i, j ;\n    double tol = self->nonExtremaSuppression ;\n    self->numNonExtremaSuppressed = 0 ;\n    for (i = 0 ; i < (signed)self->numFeatures ; ++i) {\n      double x = self->features[i].frame.x ;\n      double y = self->features[i].frame.y ;\n      double sigma = self->features[i].frame.a11 ;\n      double score = self->features[i].peakScore ;\n\n      for (j = 0 ; j < (signed)self->numFeatures ; ++j) {\n        double dx_ = self->features[j].frame.x - x ;\n        double dy_ = self->features[j].frame.y - y ;\n        double sigma_ = self->features[j].frame.a11 ;\n        double score_ = self->features[j].peakScore ;\n        if (score_ == 0) continue ;\n        if (sigma < (1+tol) * sigma_ &&\n            sigma_ < (1+tol) * sigma &&\n            vl_abs_d(dx_) < tol * sigma &&\n            vl_abs_d(dy_) < tol * sigma &&\n            vl_abs_d(score) > vl_abs_d(score_)) {\n          self->features[j].peakScore = 0 ;\n          self->numNonExtremaSuppressed ++ ;\n        }\n      }\n    }\n    j = 0 ;\n    for (i = 0 ; i < (signed)self->numFeatures ; ++i) {\n      VlCovDetFeature feature = self->features[i] ;\n      if (self->features[i].peakScore != 0) {\n        self->features[j++] = feature ;\n      }\n    }\n    self->numFeatures = j ;\n  }\n\n  if (levelxx) vl_free(levelxx) ;\n  if (levelyy) vl_free(levelyy) ;\n  if (levelxy) vl_free(levelxy) ;\n}\n\n/* ---------------------------------------------------------------- */\n/*                                                  Extract patches */\n/* ---------------------------------------------------------------- */\n\n/** @internal\n ** @brief Helper for extracting patches\n ** @param self object.\n ** @param[out] sigma1 actual patch smoothing along the first axis.\n ** @param[out] sigma2 actual patch smoothing along the second axis.\n ** @param patch buffer.\n ** @param resolution patch resolution.\n ** @param extent patch extent.\n ** @param sigma desired smoothing in the patch frame.\n ** @param A_ linear transfomration from patch to image.\n ** @param T_ translation from patch to image.\n ** @param d1 first singular value @a A.\n ** @param d2 second singular value of @a A.\n **/\n\nvl_bool\nvl_covdet_extract_patch_helper (VlCovDet * self,\n                                double * sigma1,\n                                double * sigma2,\n                                float * patch,\n                                vl_size resolution,\n                                double extent,\n                                double sigma,\n                                double A_ [4],\n                                double T_ [2],\n                                double d1, double d2)\n{\n  vl_index o, s ;\n  double factor ;\n  double sigma_ ;\n  float const * level ;\n  vl_size width, height ;\n  double step ;\n\n  double A [4] = {A_[0], A_[1], A_[2], A_[3]} ;\n  double T [2] = {T_[0], T_[1]} ;\n\n  VlScaleSpaceGeometry geom = vl_scalespace_get_geometry(self->gss) ;\n  VlScaleSpaceOctaveGeometry oct ;\n\n  /* Starting from a pre-smoothed image at scale sigma_\n     because of the mapping A the resulting smoothing in\n     the warped patch is S, where\n\n        sigma_^2 I = A S A\',\n\n        S = sigma_^2 inv(A) inv(A)\' = sigma_^2 V D^-2 V\',\n\n        A = U D V\'.\n\n     Thus we rotate A by V to obtain an axis-aligned smoothing:\n\n        A = U*D,\n\n        S = sigma_^2 D^-2.\n\n     Then we search the scale-space for the best sigma_ such\n     that the target smoothing is approximated from below:\n\n        max sigma_(o,s) :    simga_(o,s) factor <= sigma,\n        factor = max{abs(D11), abs(D22)}.\n   */\n\n\n  /*\n   Determine the best level (o,s) such that sigma_(o,s) factor <= sigma.\n   This can be obtained by scanning octaves from smallest to largest\n   and stopping when no level in the octave satisfies the relation.\n\n   Given the range of octave availables, do the best you can.\n   */\n\n  factor = 1.0 / VL_MIN(d1, d2) ;\n\n  for (o = geom.firstOctave + 1 ; o <= geom.lastOctave ; ++o) {\n    s = vl_floor_d(vl_log2_d(sigma / (factor * geom.baseScale)) - o) ;\n    s = VL_MAX(s, geom.octaveFirstSubdivision) ;\n    s = VL_MIN(s, geom.octaveLastSubdivision) ;\n    sigma_ = geom.baseScale * pow(2.0, o + (double)s / geom.octaveResolution) ;\n    /*VL_PRINTF(".. %d D=%g %g; sigma_=%g factor*sigma_=%g\\n", o, d1, d2, sigma_, factor* sigma_) ;*/\n    if (factor * sigma_ > sigma) {\n      o -- ;\n      break ;\n    }\n  }\n  o = VL_MIN(o, geom.lastOctave) ;\n  s = vl_floor_d(vl_log2_d(sigma / (factor * geom.baseScale)) - o) ;\n  s = VL_MAX(s, geom.octaveFirstSubdivision) ;\n  s = VL_MIN(s, geom.octaveLastSubdivision) ;\n  sigma_ = geom.baseScale * pow(2.0, o + (double)s / geom.octaveResolution) ;\n  if (sigma1) *sigma1 = sigma_ / d1 ;\n  if (sigma2) *sigma2 = sigma_ / d2 ;\n\n  /*VL_PRINTF("%d %d %g %g %g %g\\n", o, s, factor, sigma_, factor * sigma_, sigma) ;*/\n\n  /*\n   Now the scale space level to be used for this warping has been\n   determined.\n\n   If the patch is partially or completely out of the image boundary,\n   create a padded copy of the required region first.\n   */\n\n  level = vl_scalespace_get_level(self->gss, o, s) ;\n  oct = vl_scalespace_get_octave_geometry(self->gss, o) ;\n  width = oct.width ;\n  height = oct.height ;\n  step = oct.step ;\n\n  A[0] /= step ;\n  A[1] /= step ;\n  A[2] /= step ;\n  A[3] /= step ;\n  T[0] /= step ;\n  T[1] /= step ;\n\n  {\n    /*\n     Warp the patch domain [x0hat,y0hat,x1hat,y1hat] to the image domain/\n     Obtain a box [x0,y0,x1,y1] enclosing that wrapped box, and then\n     an integer vertexes version [x0i, y0i, x1i, y1i], making room\n     for one pixel at the boundary to simplify bilinear interpolation\n     later on.\n     */\n    vl_index x0i, y0i, x1i, y1i ;\n    double x0 = +VL_INFINITY_D ;\n    double x1 = -VL_INFINITY_D ;\n    double y0 = +VL_INFINITY_D ;\n    double y1 = -VL_INFINITY_D ;\n    double boxx [4] = {extent, extent, -extent, -extent} ;\n    double boxy [4] = {-extent, extent, extent, -extent} ;\n    int i ;\n    for (i = 0 ; i < 4 ; ++i) {\n      double x = A[0] * boxx[i] + A[2] * boxy[i] + T[0] ;\n      double y = A[1] * boxx[i] + A[3] * boxy[i] + T[1] ;\n      x0 = VL_MIN(x0, x) ;\n      x1 = VL_MAX(x1, x) ;\n      y0 = VL_MIN(y0, y) ;\n      y1 = VL_MAX(y1, y) ;\n    }\n\n    if ((x0 < 0 || x1 > (signed)width-1 || y0 < 0 || y1 > (signed)height-1) &&\n        !self->allowPaddedWarping) {\n      return vl_set_last_error(VL_ERR_EOF, "Frame out of image.");\n    }\n\n    /* Leave one pixel border for bilinear interpolation. */\n    x0i = floor(x0) - 1 ;\n    y0i = floor(y0) - 1 ;\n    x1i = ceil(x1) + 1 ;\n    y1i = ceil(y1) + 1 ;\n\n    /*\n     If the box [x0i,y0i,x1i,y1i] is not fully contained in the\n     image domain, then create a copy of this region by padding\n     the image. The image is extended by continuity.\n     */\n\n    if (x0i < 0 || x1i > (signed)width-1 ||\n        y0i < 0 || y1i > (signed)height-1) {\n     \n      vl_index xi, yi ;\n\n      /* compute the amount of l,r,t,b padding needed to complete the patch */\n      vl_index padx0 = VL_MAX(0, - x0i) ;\n      vl_index pady0 = VL_MAX(0, - y0i) ;\n      vl_index padx1 = VL_MAX(0, x1i - ((signed)width - 1)) ;\n      vl_index pady1 = VL_MAX(0, y1i - ((signed)height - 1)) ;\n\n      /* make enough room for the patch */\n      vl_index patchWidth = x1i - x0i + 1 ;\n      vl_index patchHeight = y1i - y0i + 1 ;\n      vl_size patchBufferSize = patchWidth * patchHeight * sizeof(float) ;\n      if (patchBufferSize > self->patchBufferSize) {\n        int err = _vl_resize_buffer((void**)&self->patch, &self->patchBufferSize, patchBufferSize) ;\n        if (err) return vl_set_last_error(VL_ERR_ALLOC, "Unable to allocate data.") ;\n      }\n\n      if (pady0 < patchHeight - pady1) {\n        /* start by filling the central horizontal band */\n        for (yi = y0i + pady0 ; yi < y0i + patchHeight - pady1 ; ++ yi) {\n          float *dst = self->patch + (yi - y0i) * patchWidth ;\n          float const *src = level + yi * width + VL_MIN(VL_MAX(0, x0i),(signed)width-1) ;\n          for (xi = x0i ; xi < x0i + padx0 ; ++xi) *dst++ = *src ;\n          for ( ; xi < x0i + patchWidth - padx1 - 2 ; ++xi) *dst++ = *src++ ;\n          for ( ; xi < x0i + patchWidth ; ++xi) *dst++ = *src ;\n        }\n        /* now extend the central band up and down */\n        for (yi = 0 ; yi < pady0 ; ++yi) {\n          memcpy(self->patch + yi * patchWidth,\n                 self->patch + pady0 * patchWidth,\n                 patchWidth * sizeof(float)) ;\n        }\n        for (yi = patchHeight - pady1 ; yi < patchHeight ; ++yi) {\n          memcpy(self->patch + yi * patchWidth,\n                 self->patch + (patchHeight - pady1 - 1) * patchWidth,\n                 patchWidth * sizeof(float)) ;\n        }\n      } else {\n        /* should be handled better! */\n        memset(self->patch, 0, self->patchBufferSize) ;\n      }\n#if 0\n      {\n        char name [200] ;\n        snprintf(name, 200, "/tmp/%20.0f-ext.pgm", 1e10*vl_get_cpu_time()) ;\n        vl_pgm_write_f(name, patch, patchWidth, patchWidth) ;\n      }\n#endif\n\n      level = self->patch ;\n      width = patchWidth ;\n      height = patchHeight ;\n      T[0] -= x0i ;\n      T[1] -= y0i ;\n    }\n  }\n\n  /*\n   Resample by using bilinear interpolation.\n   */\n  {\n    float * pt = patch ;\n    double yhat = -extent ;\n    vl_index xxi ;\n    vl_index yyi ;\n    double stephat = extent / resolution ;\n\n    for (yyi = 0 ; yyi < 2 * (signed)resolution + 1 ; ++yyi) {\n      double xhat = -extent ;\n      double rx = A[2] * yhat + T[0] ;\n      double ry = A[3] * yhat + T[1] ;\n      for (xxi = 0 ; xxi < 2 * (signed)resolution + 1 ; ++xxi) {\n        double x = A[0] * xhat + rx ;\n        double y = A[1] * xhat + ry ;\n        vl_index xi = vl_floor_d(x) ;\n        vl_index yi = vl_floor_d(y) ;\n        double i00 = level[yi * width + xi] ;\n        double i10 = level[yi * width + xi + 1] ;\n        double i01 = level[(yi + 1) * width + xi] ;\n        double i11 = level[(yi + 1) * width + xi + 1] ;\n        double wx = x - xi ;\n        double wy = y - yi ;\n\n        assert(xi >= 0 && xi <= (signed)width - 1) ;\n        assert(yi >= 0 && yi <= (signed)height - 1) ;\n\n        *pt++ =\n        (1.0 - wy) * ((1.0 - wx) * i00 + wx * i10) +\n        wy * ((1.0 - wx) * i01 + wx * i11) ;\n\n        xhat += stephat ;\n      }\n      yhat += stephat ;\n    }\n  }\n#if 0\n    {\n      char name [200] ;\n      snprintf(name, 200, "/tmp/%20.0f.pgm", 1e10*vl_get_cpu_time()) ;\n      vl_pgm_write_f(name, patch, 2*resolution+1, 2*resolution+1) ;\n    }\n#endif\n  return VL_ERR_OK ;\n}\n\n/** @brief Helper for extracting patches\n ** @param self object.\n ** @param patch buffer.\n ** @param resolution patch resolution.\n ** @param extent patch extent.\n ** @param sigma desired smoothing in the patch frame.\n ** @param frame feature frame.\n **\n ** The function considers a patch of extent <code>[-extent,extent]</code>\n ** on each side, with a side counting <code>2*resolution+1</code> pixels.\n ** In attempts to extract from the scale space a patch\n ** based on the affine warping specified by @a frame in such a way\n ** that the resulting smoothing of the image is @a sigma (in the\n ** patch frame).\n **\n ** The transformation is specified by the matrices @c A and @c T\n ** embedded in the feature @a frame. Note that this transformation maps\n ** pixels from the patch frame to the image frame.\n **/\n\nvl_bool\nvl_covdet_extract_patch_for_frame (VlCovDet * self,\n                                   float * patch,\n                                   vl_size resolution,\n                                   double extent,\n                                   double sigma,\n                                   VlFrameOrientedEllipse frame)\n{\n  double A[2*2] = {frame.a11, frame.a21, frame.a12, frame.a22} ;\n  double T[2] = {frame.x, frame.y} ;\n  double D[4], U[4], V[4] ;\n\n  vl_svd2(D, U, V, A) ;\n\n  return vl_covdet_extract_patch_helper\n  (self, NULL, NULL, patch, resolution, extent, sigma, A, T, D[0], D[3]) ;\n}\n\n/* ---------------------------------------------------------------- */\n/*                                                     Affine shape */\n/* ---------------------------------------------------------------- */\n\n/** @brief Extract the affine shape for a feature frame\n ** @param self object.\n ** @param adapted the shape-adapted frame.\n ** @param frame the input frame.\n ** @return ::VL_ERR_OK if affine adaptation is successful.\n **\n ** This function may fail if adaptation is unsuccessful or if\n ** memory is insufficient.\n **/\n\nint\nvl_covdet_extract_affine_shape_for_frame (VlCovDet * self,\n                                          VlFrameOrientedEllipse * adapted,\n                                          VlFrameOrientedEllipse frame)\n{\n  vl_index iter = 0 ;\n\n  double A [2*2] = {frame.a11, frame.a21, frame.a12, frame.a22} ;\n  double T [2] = {frame.x, frame.y} ;\n  double U [2*2] ;\n  double V [2*2] ;\n  double D [2*2] ;\n  double M [2*2] ;\n  double P [2*2] ;\n  double P_ [2*2] ;\n  double Q [2*2] ;\n  double sigma1, sigma2 ;\n  double sigmaD = VL_COVDET_AA_RELATIVE_DERIVATIVE_SIGMA ;\n  double factor ;\n  double anisotropy ;\n  double referenceScale ;\n  vl_size const resolution = VL_COVDET_AA_PATCH_RESOLUTION ;\n  vl_size const side = 2*VL_COVDET_AA_PATCH_RESOLUTION + 1 ;\n  double const extent = VL_COVDET_AA_PATCH_EXTENT ;\n\n\n  *adapted = frame ;\n\n  while (1) {\n    double lxx = 0, lxy = 0, lyy = 0 ;\n    vl_index k ;\n    int err ;\n\n    /* A = U D V\' */\n    vl_svd2(D, U, V, A) ;\n    anisotropy = VL_MAX(D[0]/D[3], D[3]/D[0]) ;\n\n    /* VL_PRINTF("anisot: %g\\n", anisotropy); */\n\n    if (anisotropy > VL_COVDET_AA_MAX_ANISOTROPY) {\n      /* diverged, give up with current solution */\n      break ;\n    }\n\n    /* make sure that the smallest singluar value stays fixed\n       after the first iteration */\n    if (iter == 0) {\n      referenceScale = VL_MIN(D[0], D[3]) ;\n      factor = 1.0 ;\n    } else {\n      factor = referenceScale / VL_MIN(D[0],D[3]) ;\n    }\n\n    D[0] *= factor ;\n    D[3] *= factor ;\n\n    A[0] = U[0] * D[0] ;\n    A[1] = U[1] * D[0] ;\n    A[2] = U[2] * D[3] ;\n    A[3] = U[3] * D[3] ;\n\n    adapted->a11 = A[0] ;\n    adapted->a21 = A[1] ;\n    adapted->a12 = A[2] ;\n    adapted->a22 = A[3] ;\n\n    if (++iter >= VL_COVDET_AA_MAX_NUM_ITERATIONS) break ;\n\n    err = vl_covdet_extract_patch_helper(self,\n                                         &sigma1, &sigma2,\n                                         self->aaPatch,\n                                         resolution,\n                                         extent,\n                                         sigmaD,\n                                         A, T, D[0], D[3]) ;\n    if (err) return err ;\n\n    if (self->aaAccurateSmoothing ) {\n      double deltaSigma1 = sqrt(VL_MAX(sigmaD*sigmaD - sigma1*sigma1,0)) ;\n      double deltaSigma2 = sqrt(VL_MAX(sigmaD*sigmaD - sigma2*sigma2,0)) ;\n      double stephat = extent / resolution ;\n      vl_imsmooth_f(self->aaPatch, side,\n                    self->aaPatch, side, side, side,\n                    deltaSigma1 / stephat, deltaSigma2 / stephat) ;\n    }\n\n    /* compute second moment matrix */\n    vl_imgradient_f (self->aaPatchX, self->aaPatchY, 1, side,\n                     self->aaPatch, side, side, side) ;\n\n    for (k = 0 ; k < (signed)(side*side) ; ++k) {\n      double lx = self->aaPatchX[k] ;\n      double ly = self->aaPatchY[k] ;\n      lxx += lx * lx * self->aaMask[k] ;\n      lyy += ly * ly * self->aaMask[k] ;\n      lxy += lx * ly * self->aaMask[k] ;\n    }\n    M[0] = lxx ;\n    M[1] = lxy ;\n    M[2] = lxy ;\n    M[3] = lyy ;\n\n    if (lxx == 0 || lyy == 0) {\n      *adapted = frame ;\n      break ;\n    }\n\n    /* decompose M = P * Q * P\' */\n    vl_svd2 (Q, P, P_, M) ;\n\n    /*\n     Setting A <- A * dA results in M to change approximatively as\n\n     M --> dA\'  M dA = dA\' P Q P dA\n\n     To make this proportional to the identity, we set\n\n     dA ~= P Q^1/2\n\n     we also make it so the smallest singular value of A is unchanged.\n     */\n\n    if (Q[3]/Q[0] < VL_COVDET_AA_CONVERGENCE_THRESHOLD &&\n        Q[0]/Q[3] < VL_COVDET_AA_CONVERGENCE_THRESHOLD) {\n      break ;\n    }\n\n    {\n      double Ap [4] ;\n      double q0 = sqrt(Q[0]) ;\n      double q1 = sqrt(Q[3]) ;\n      Ap[0] = (A[0] * P[0] + A[2] * P[1]) / q0 ;\n      Ap[1] = (A[1] * P[0] + A[3] * P[1]) / q0 ;\n      Ap[2] = (A[0] * P[2] + A[2] * P[3]) / q1 ;\n      Ap[3] = (A[1] * P[2] + A[3] * P[3]) / q1 ;\n      memcpy(A,Ap,4*sizeof(double)) ;\n    }\n\n  } /* next iteration */\n\n  /*\n   Make upright.\n\n   Shape adaptation does not estimate rotation. This is fixed by default\n   so that a selected axis is not rotated at all (usually this is the\n   vertical axis for upright features). To do so, the frame is rotated\n   as follows.\n   */\n  {\n    double A [2*2] = {adapted->a11, adapted->a21, adapted->a12, adapted->a22} ;\n    double ref [2] ;\n    double ref_ [2] ;\n    double angle ;\n    double angle_ ;\n    double dangle ;\n    double r1, r2 ;\n\n    if (self->transposed) {\n      /* up is the x axis */\n      ref[0] = 1 ;\n      ref[1] = 0 ;\n    } else {\n      /* up is the y axis */\n      ref[0] = 0 ;\n      ref[1] = 1 ;\n    }\n\n    vl_solve_linear_system_2 (ref_, A, ref) ;\n    angle = atan2(ref[1], ref[0]) ;\n    angle_ = atan2(ref_[1], ref_[0]) ;\n    dangle = angle_ - angle ;\n    r1 = cos(dangle) ;\n    r2 = sin(dangle) ;\n    adapted->a11 = + A[0] * r1 + A[2] * r2 ;\n    adapted->a21 = + A[1] * r1 + A[3] * r2 ;\n    adapted->a12 = - A[0] * r2 + A[2] * r1 ;\n    adapted->a22 = - A[1] * r2 + A[3] * r1 ;\n  }\n\n  return VL_ERR_OK ;\n}\n\n/** @brief Extract the affine shape for the stored features\n ** @param self object.\n **\n ** This function may discard features for which no affine\n ** shape can reliably be detected.\n **/\n\nvoid\nvl_covdet_extract_affine_shape (VlCovDet * self)\n{\n  vl_index i, j = 0 ;\n  vl_size numFeatures = vl_covdet_get_num_features(self) ;\n  VlCovDetFeature * feature = vl_covdet_get_features(self);\n  for (i = 0 ; i < (signed)numFeatures ; ++i) {\n    int status ;\n    VlFrameOrientedEllipse adapted ;\n    status = vl_covdet_extract_affine_shape_for_frame(self, &adapted, feature[i].frame) ;\n    if (status == VL_ERR_OK) {\n      feature[j] = feature[i] ;\n      feature[j].frame = adapted ;\n      ++ j ;\n    }\n  }\n  self->numFeatures = j ;\n}\n\n/* ---------------------------------------------------------------- */\n/*                                                      Orientation */\n/* ---------------------------------------------------------------- */\n\nstatic int\n_vl_covdet_compare_orientations_descending (void const * a_,\n                                            void const * b_)\n{\n  VlCovDetFeatureOrientation const * a = a_ ;\n  VlCovDetFeatureOrientation const * b = b_ ;\n  if (a->score > b->score) return -1 ;\n  if (a->score < b->score) return +1 ;\n  return 0 ;\n}\n\n/** @brief Extract the orientation(s) for a feature\n ** @param self object.\n ** @param numOrientations the number of detected orientations.\n ** @param frame pose of the feature.\n ** @return an array of detected orientations with their scores.\n **\n ** The returned array is a matrix of size @f$ 2 \\times n @f$\n ** where <em>n</em> is the number of detected orientations.\n **\n ** The function returns @c NULL if memory is insufficient.\n **/\n\nVlCovDetFeatureOrientation *\nvl_covdet_extract_orientations_for_frame (VlCovDet * self,\n                                          vl_size * numOrientations,\n                                          VlFrameOrientedEllipse frame)\n{\n  int err ;\n  vl_index k, i ;\n  vl_index iter ;\n\n  double extent = VL_COVDET_AA_PATCH_EXTENT ;\n  vl_size resolution = VL_COVDET_AA_PATCH_RESOLUTION ;\n  vl_size side = 2 * resolution + 1  ;\n\n  vl_size const numBins = VL_COVDET_OR_NUM_ORIENTATION_HISTOGAM_BINS ;\n  double hist [VL_COVDET_OR_NUM_ORIENTATION_HISTOGAM_BINS] ;\n  double const binExtent = 2 * VL_PI / VL_COVDET_OR_NUM_ORIENTATION_HISTOGAM_BINS ;\n  double const peakRelativeSize = VL_COVDET_OR_ADDITIONAL_PEAKS_RELATIVE_SIZE ;\n  double maxPeakValue ;\n\n  double A [2*2] = {frame.a11, frame.a21, frame.a12, frame.a22} ;\n  double T [2] = {frame.x, frame.y} ;\n  double U [2*2] ;\n  double V [2*2] ;\n  double D [2*2] ;\n  double sigma1, sigma2 ;\n  double sigmaD = 1.0 ;\n  double theta0 ;\n\n  assert(self);\n  assert(numOrientations) ;\n\n  /*\n   The goal is to estimate a rotation R(theta) such that the patch given\n   by the transformation A R(theta) has the strongest average\n   gradient pointing right (or down for transposed conventions).\n\n   To compensate for tha anisotropic smoothing due to warping,\n   A is decomposed as A = U D V\' and the patch is warped by\n   U D only, meaning that the matrix R_(theta) will be estimated instead,\n   where:\n\n      A R(theta) = U D V\' R(theta) = U D R_(theta)\n\n   such that R(theta) = V R(theta). That is an extra rotation of\n   theta0 = atan2(V(2,1),V(1,1)).\n   */\n\n  /* axis aligned anisotropic smoothing for easier compensation */\n  vl_svd2(D, U, V, A) ;\n\n  A[0] = U[0] * D[0] ;\n  A[1] = U[1] * D[0] ;\n  A[2] = U[2] * D[3] ;\n  A[3] = U[3] * D[3] ;\n\n  theta0 = atan2(V[1],V[0]) ;\n\n  err = vl_covdet_extract_patch_helper(self,\n                                       &sigma1, &sigma2,\n                                       self->aaPatch,\n                                       resolution,\n                                       extent,\n                                       sigmaD,\n                                       A, T, D[0], D[3]) ;\n\n  if (err) {\n    *numOrientations = 0 ;\n    return NULL ;\n  }\n\n  if (1) {\n    double deltaSigma1 = sqrt(VL_MAX(sigmaD*sigmaD - sigma1*sigma1,0)) ;\n    double deltaSigma2 = sqrt(VL_MAX(sigmaD*sigmaD - sigma2*sigma2,0)) ;\n    double stephat = extent / resolution ;\n    vl_imsmooth_f(self->aaPatch, side,\n                  self->aaPatch, side, side, side,\n                  deltaSigma1 / stephat, deltaSigma2 / stephat) ;\n  }\n\n  /* histogram of oriented gradients */\n  vl_imgradient_polar_f (self->aaPatchX, self->aaPatchY, 1, side,\n                         self->aaPatch, side, side, side) ;\n\n  memset (hist, 0, sizeof(double) * numBins) ;\n\n  for (k = 0 ; k < (signed)(side*side) ; ++k) {\n    double modulus = self->aaPatchX[k] ;\n    double angle = self->aaPatchY[k] ;\n    double weight = self->aaMask[k] ;\n\n    double x = angle / binExtent ;\n    vl_index bin = vl_floor_d(x) ;\n    double w2 = x - bin ;\n    double w1 = 1.0 - w2 ;\n\n    hist[(bin + numBins) % numBins] += w1 * (modulus * weight) ;\n    hist[(bin + numBins + 1) % numBins] += w2 * (modulus * weight) ;\n  }\n\n  /* smooth histogram */\n  for (iter = 0; iter < 6; iter ++) {\n    double prev = hist [numBins - 1] ;\n    double first = hist [0] ;\n    vl_index i ;\n    for (i = 0; i < (signed)numBins - 1; ++i) {\n      double curr = (prev + hist[i] + hist[(i + 1) % numBins]) / 3.0 ;\n      prev = hist[i] ;\n      hist[i] = curr ;\n    }\n    hist[i] = (prev + hist[i] + first) / 3.0 ;\n  }\n\n  /* find the histogram maximum */\n  maxPeakValue = 0 ;\n  for (i = 0 ; i < (signed)numBins ; ++i) {\n    maxPeakValue = VL_MAX (maxPeakValue, hist[i]) ;\n  }\n\n  /* find peaks within 80% from max */\n  *numOrientations = 0 ;\n  for(i = 0 ; i < (signed)numBins ; ++i) {\n    double h0 = hist [i] ;\n    double hm = hist [(i - 1 + numBins) % numBins] ;\n    double hp = hist [(i + 1 + numBins) % numBins] ;\n\n    /* is this a peak? */\n    if (h0 > peakRelativeSize * maxPeakValue && h0 > hm && h0 > hp) {\n      /* quadratic interpolation */\n      double di = - 0.5 * (hp - hm) / (hp + hm - 2 * h0) ;\n      double th = binExtent * (i + di) + theta0 ;\n      if (self->transposed) {\n        /* the axis to the right is y, measure orientations from this */\n        th = th - VL_PI/2 ;\n      }\n      self->orientations[*numOrientations].angle = th ;\n      self->orientations[*numOrientations].score = h0 ;\n      *numOrientations += 1 ;\n      //VL_PRINTF("%d %g\\n", *numOrientations, th) ;\n\n      if (*numOrientations >= self->maxNumOrientations) break ;\n    }\n  }\n\n  /* sort the orientations by decreasing scores */\n  qsort(self->orientations,\n        *numOrientations,\n        sizeof(VlCovDetFeatureOrientation),\n        _vl_covdet_compare_orientations_descending) ;\n\n  return self->orientations ;\n}\n\n/** @brief Extract the orientation(s) for the stored features.\n ** @param self object.\n **\n ** Note that, since more than one orientation can be detected\n ** for each feature, this function may create copies of them,\n ** one for each orientation.\n **/\n\nvoid\nvl_covdet_extract_orientations (VlCovDet * self)\n{\n  vl_index i, j  ;\n  vl_size numFeatures = vl_covdet_get_num_features(self) ;\n  for (i = 0 ; i < (signed)numFeatures ; ++i) {\n    vl_size numOrientations ;\n    VlCovDetFeature feature = self->features[i] ;\n    VlCovDetFeatureOrientation* orientations =\n    vl_covdet_extract_orientations_for_frame(self, &numOrientations, feature.frame) ;\n\n    for (j = 0 ; j < (signed)numOrientations ; ++j) {\n      double A [2*2] = {\n        feature.frame.a11,\n        feature.frame.a21,\n        feature.frame.a12,\n        feature.frame.a22} ;\n      double r1 = cos(orientations[j].angle) ;\n      double r2 = sin(orientations[j].angle) ;\n      VlCovDetFeature * oriented ;\n\n      if (j == 0) {\n        oriented = & self->features[i] ;\n      } else {\n        vl_covdet_append_feature(self, &feature) ;\n        oriented = & self->features[self->numFeatures -1] ;\n      }\n\n      oriented->orientationScore = orientations[j].score ;\n      oriented->frame.a11 = + A[0] * r1 + A[2] * r2 ;\n      oriented->frame.a21 = + A[1] * r1 + A[3] * r2 ;\n      oriented->frame.a12 = - A[0] * r2 + A[2] * r1 ;\n      oriented->frame.a22 = - A[1] * r2 + A[3] * r1 ;\n    }\n  }\n}\n\n/* ---------------------------------------------------------------- */\n/*                                                 Laplacian scales */\n/* ---------------------------------------------------------------- */\n\n/** @brief Extract the Laplacian scale(s) for a feature frame.\n ** @param self object.\n ** @param numScales the number of detected scales.\n ** @param frame pose of the feature.\n ** @return an array of detected scales.\n **\n ** The function returns @c NULL if memory is insufficient.\n **/\n\nVlCovDetFeatureLaplacianScale *\nvl_covdet_extract_laplacian_scales_for_frame (VlCovDet * self,\n                                              vl_size * numScales,\n                                              VlFrameOrientedEllipse frame)\n{\n  /*\n   We try to explore one octave, with the nominal detection scale 1.0\n   (in the patch reference frame) in the middle. Thus the goal is to sample\n   the response of the tr-Laplacian operator at logarithmically\n   spaced scales in 1/sqrt(2), sqrt(2).\n\n   To this end, the patch is warped with a smoothing of at most\n   sigmaImage = 1 / sqrt(2) (beginning of the scale), sampled at\n   roughly twice the Nyquist frequency (so step = 1 / (2*sqrt(2))).\n   This maes it possible to approximate the Laplacian operator at\n   that scale by simple finite differences.\n\n   */\n  int err ;\n  double const sigmaImage = 1.0 / sqrt(2.0) ;\n  double const step = 0.5 * sigmaImage ;\n  double actualSigmaImage ;\n  vl_size const resolution = VL_COVDET_LAP_PATCH_RESOLUTION ;\n  vl_size const num = 2 * resolution + 1 ;\n  double extent = step * resolution ;\n  double scores [VL_COVDET_LAP_NUM_LEVELS] ;\n  double factor = 1.0 ;\n  float const * pt ;\n  vl_index k ;\n\n  double A[2*2] = {frame.a11, frame.a21, frame.a12, frame.a22} ;\n  double T[2] = {frame.x, frame.y} ;\n  double D[4], U[4], V[4] ;\n  double sigma1, sigma2 ;\n\n  assert(self) ;\n  assert(numScales) ;\n\n  *numScales = 0 ;\n\n  vl_svd2(D, U, V, A) ;\n\n  err = vl_covdet_extract_patch_helper\n  (self, &sigma1, &sigma2, self->lapPatch, resolution, extent, sigmaImage, A, T, D[0], D[3]) ;\n  if (err) return NULL ;\n\n  /* the actual smoothing after warping is never the target one */\n  if (sigma1 == sigma2) {\n    actualSigmaImage = sigma1 ;\n  } else {\n    /* here we could compensate */\n    actualSigmaImage = sqrt(sigma1*sigma2) ;\n  }\n\n  /* now multiply by the bank of Laplacians */\n  pt = self->laplacians ;\n  for (k = 0 ; k < VL_COVDET_LAP_NUM_LEVELS ; ++k) {\n    vl_index q ;\n    double score = 0 ;\n    double sigmaLap = pow(2.0, -0.5 + (double)k / (VL_COVDET_LAP_NUM_LEVELS - 1)) ;\n    /* note that the sqrt argument cannot be negative since by construction\n     sigmaLap >= sigmaImage */\n    sigmaLap = sqrt(sigmaLap*sigmaLap\n                    - sigmaImage*sigmaImage\n                    + actualSigmaImage*actualSigmaImage) ;\n\n    for (q = 0 ; q < (signed)(num * num) ; ++q) {\n      score += (*pt++) * self->lapPatch[q] ;\n    }\n    scores[k] = score * sigmaLap * sigmaLap ;\n  }\n\n  /* find and interpolate maxima */\n  for (k = 1 ; k < VL_COVDET_LAP_NUM_LEVELS - 1 ; ++k) {\n    double a = scores[k-1] ;\n    double b = scores[k] ;\n    double c = scores[k+1] ;\n    double t = self->lapPeakThreshold ;\n\n    if ((((b > a) && (b > c)) || ((b < a) && (b < c))) && (vl_abs_d(b) >= t)) {\n      double dk = - 0.5 * (c - a) / (c + a - 2 * b) ;\n      double s = k + dk ;\n      double sigmaLap = pow(2.0, -0.5 + s / (VL_COVDET_LAP_NUM_LEVELS - 1)) ;\n      double scale ;\n      sigmaLap = sqrt(sigmaLap*sigmaLap\n                      - sigmaImage*sigmaImage\n                      + actualSigmaImage*actualSigmaImage) ;\n      scale = sigmaLap / 1.0 ;\n      /*\n       VL_PRINTF("** k:%d, s:%f, sigmaLapFilter:%f, sigmaLap%f, scale:%f (%f %f %f)\\n",\n       k,s,sigmaLapFilter,sigmaLap,scale,a,b,c) ;\n       */\n      if (*numScales < VL_COVDET_MAX_NUM_LAPLACIAN_SCALES) {\n        self->scales[*numScales].scale = scale * factor ;\n        self->scales[*numScales].score = b + 0.5 * (c - a) * dk ;\n        *numScales += 1 ;\n      }\n    }\n  }\n  return self->scales ;\n}\n\n/** @brief Extract the Laplacian scales for the stored features\n ** @param self object.\n **\n ** Note that, since more than one orientation can be detected\n ** for each feature, this function may create copies of them,\n ** one for each orientation.\n **/\nvoid\nvl_covdet_extract_laplacian_scales (VlCovDet * self)\n{\n  vl_index i, j  ;\n  vl_bool dropFeaturesWithoutScale = VL_TRUE ;\n  vl_size numFeatures = vl_covdet_get_num_features(self) ;\n  memset(self->numFeaturesWithNumScales, 0,\n         sizeof(self->numFeaturesWithNumScales)) ;\n\n  for (i = 0 ; i < (signed)numFeatures ; ++i) {\n    vl_size numScales ;\n    VlCovDetFeature feature = self->features[i] ;\n    VlCovDetFeatureLaplacianScale const * scales =\n    vl_covdet_extract_laplacian_scales_for_frame(self, &numScales, feature.frame) ;\n\n    self->numFeaturesWithNumScales[numScales] ++ ;\n\n    if (numScales == 0 && dropFeaturesWithoutScale) {\n      self->features[i].peakScore = 0 ;\n    }\n\n    for (j = 0 ; j < (signed)numScales ; ++j) {\n      VlCovDetFeature * scaled ;\n\n      if (j == 0) {\n        scaled = & self->features[i] ;\n      } else {\n        vl_covdet_append_feature(self, &feature) ;\n        scaled = & self->features[self->numFeatures -1] ;\n      }\n\n      scaled->laplacianScaleScore = scales[j].score ;\n      scaled->frame.a11 *= scales[j].scale ;\n      scaled->frame.a21 *= scales[j].scale ;\n      scaled->frame.a12 *= scales[j].scale ;\n      scaled->frame.a22 *= scales[j].scale ;\n    }\n  }\n  if (dropFeaturesWithoutScale) {\n    j = 0 ;\n    for (i = 0 ; i < (signed)self->numFeatures ; ++i) {\n      VlCovDetFeature feature = self->features[i] ;\n      if (feature.peakScore) {\n        self->features[j++] = feature ;\n      }\n    }\n    self->numFeatures = j ;\n  }\n\n}\n\n/* ---------------------------------------------------------------- */\n/*                       Checking that features are inside an image */\n/* ---------------------------------------------------------------- */\n\nvl_bool\n_vl_covdet_check_frame_inside (VlCovDet * self, VlFrameOrientedEllipse frame, double margin)\n{\n  double extent = margin ;\n  double A [2*2] = {frame.a11, frame.a21, frame.a12, frame.a22} ;\n  double T[2] = {frame.x, frame.y} ;\n  double x0 = +VL_INFINITY_D ;\n  double x1 = -VL_INFINITY_D ;\n  double y0 = +VL_INFINITY_D ;\n  double y1 = -VL_INFINITY_D ;\n  double boxx [4] = {extent, extent, -extent, -extent} ;\n  double boxy [4] = {-extent, extent, extent, -extent} ;\n  VlScaleSpaceGeometry geom = vl_scalespace_get_geometry(self->gss) ;\n  int i ;\n  for (i = 0 ; i < 4 ; ++i) {\n    double x = A[0] * boxx[i] + A[2] * boxy[i] + T[0] ;\n    double y = A[1] * boxx[i] + A[3] * boxy[i] + T[1] ;\n    x0 = VL_MIN(x0, x) ;\n    x1 = VL_MAX(x1, x) ;\n    y0 = VL_MIN(y0, y) ;\n    y1 = VL_MAX(y1, y) ;\n  }\n\n  return\n  0 <= x0 && x1 <= geom.width-1 &&\n  0 <= y0 && y1 <= geom.height-1 ;\n}\n\n/** @brief Drop features (partially) outside the image\n ** @param self object.\n ** @param margin geometric marging.\n **\n ** The feature extent is defined by @c maring. A bounding box\n ** in the normalised feature frame containin a circle of radius\n ** @a maring is created and mapped to the image by\n ** the feature frame transformation. Then the feature\n ** is dropped if the bounding box is not contained in the image.\n **\n ** For example, setting @c margin to zero drops a feature only\n ** if its center is not contained.\n **\n ** Typically a valua of @c margin equal to 1 or 2 is used.\n **/\n\nvoid\nvl_covdet_drop_features_outside (VlCovDet * self, double margin)\n{\n  vl_index i, j = 0 ;\n  vl_size numFeatures = vl_covdet_get_num_features(self) ;\n  for (i = 0 ; i < (signed)numFeatures ; ++i) {\n    vl_bool inside =\n    _vl_covdet_check_frame_inside (self, self->features[i].frame, margin) ;\n    if (inside) {\n      self->features[j] = self->features[i] ;\n      ++j ;\n    }\n  }\n  self->numFeatures = j ;\n}\n\n/* ---------------------------------------------------------------- */\n/*                                              Setters and getters */\n/* ---------------------------------------------------------------- */\n\n/* ---------------------------------------------------------------- */\n/** @brief Get wether images are passed in transposed\n ** @param self object.\n ** @return whether images are transposed.\n **/\nvl_bool\nvl_covdet_get_transposed (VlCovDet const  * self)\n{\n  return self->transposed ;\n}\n\n/** @brief Set the index of the first octave\n ** @param self object.\n ** @param t whether images are transposed.\n **/\nvoid\nvl_covdet_set_transposed (VlCovDet * self, vl_bool t)\n{\n  self->transposed = t ;\n}\n\n/* ---------------------------------------------------------------- */\n/** @brief Get the edge threshold\n ** @param self object.\n ** @return the edge threshold.\n **/\ndouble\nvl_covdet_get_edge_threshold (VlCovDet const * self)\n{\n  return self->edgeThreshold ;\n}\n\n/** @brief Set the edge threshold\n ** @param self object.\n ** @param edgeThreshold the edge threshold.\n **\n ** The edge threshold must be non-negative.\n **/\nvoid\nvl_covdet_set_edge_threshold (VlCovDet * self, double edgeThreshold)\n{\n  assert(edgeThreshold >= 0) ;\n  self->edgeThreshold = edgeThreshold ;\n}\n\n/* ---------------------------------------------------------------- */\n/** @brief Get the peak threshold\n ** @param self object.\n ** @return the peak threshold.\n **/\ndouble\nvl_covdet_get_peak_threshold (VlCovDet const * self)\n{\n  return self->peakThreshold ;\n}\n\n/** @brief Set the peak threshold\n ** @param self object.\n ** @param peakThreshold the peak threshold.\n **\n ** The peak threshold must be non-negative.\n **/\nvoid\nvl_covdet_set_peak_threshold (VlCovDet * self, double peakThreshold)\n{\n  assert(peakThreshold >= 0) ;\n  self->peakThreshold = peakThreshold ;\n}\n\n/* ---------------------------------------------------------------- */\n/** @brief Get the Laplacian peak threshold\n ** @param self object.\n ** @return the Laplacian peak threshold.\n **\n ** This parameter affects only the detecors using the Laplacian\n ** scale selectino method such as Harris-Laplace.\n **/\ndouble\nvl_covdet_get_laplacian_peak_threshold (VlCovDet const * self)\n{\n  return self->lapPeakThreshold ;\n}\n\n/** @brief Set the Laplacian peak threshold\n ** @param self object.\n ** @param peakThreshold the Laplacian peak threshold.\n **\n ** The peak threshold must be non-negative.\n **/\nvoid\nvl_covdet_set_laplacian_peak_threshold (VlCovDet * self, double peakThreshold)\n{\n  assert(peakThreshold >= 0) ;\n  self->lapPeakThreshold = peakThreshold ;\n}\n\n/* ---------------------------------------------------------------- */\n/** @brief Get the index of the first octave\n ** @param self object.\n ** @return index of the first octave.\n **/\nvl_index\nvl_covdet_get_first_octave (VlCovDet const * self)\n{\n  return self->firstOctave ;\n}\n\n/** @brief Set the index of the first octave\n ** @param self object.\n ** @param o index of the first octave.\n **\n ** Calling this function resets the detector.\n **/\nvoid\nvl_covdet_set_first_octave (VlCovDet * self, vl_index o)\n{\n  self->firstOctave = o ;\n  vl_covdet_reset(self) ;\n}\n\n/* ---------------------------------------------------------------- */\n/** @brief Get the max number of octaves\n ** @param self object.\n ** @return maximal number of octaves.\n **/\nvl_size\nvl_covdet_get_num_octaves (VlCovDet const * self)\n{\n  return self->numOctaves ;\n}\n\n/* ---------------------------------------------------------------- */\n/** @brief Get the GSS base scale\n ** @param self object.\n ** @return The base scale.\n **/\ndouble\nvl_covdet_get_base_scale (VlCovDet const * self)\n{\n  return self->baseScale ;\n}\n\n/** @brief Set the max number of octaves\n ** @param self object.\n ** @param o max number of octaves.\n **\n ** Calling this function resets the detector.\n **/\nvoid\nvl_covdet_set_num_octaves (VlCovDet * self, vl_size o)\n{\n  self->numOctaves = o ;\n  vl_covdet_reset(self) ;\n}\n\n/** @brief Set the GSS base scale\n ** @param self object.\n ** @param s the base scale.\n **\n ** Calling this function resets the detector.\n **/\nvoid\nvl_covdet_set_base_scale (VlCovDet * self, double s)\n{\n  self->baseScale = s ;\n  vl_covdet_reset(self) ;\n}\n\n/* ---------------------------------------------------------------- */\n\n/** @brief Set the max number of orientations\n ** @param self object.\n ** @param m the max number of orientations.\n **\n ** Calling this function resets the detector.\n **/\nvoid\nvl_covdet_set_max_num_orientations (VlCovDet * self, vl_size m)\n{\n  self->maxNumOrientations = m ;\n}\n\n/* ---------------------------------------------------------------- */\n/** @brief Get the octave resolution.\n ** @param self object.\n ** @return octave resolution.\n **/\n\nvl_size\nvl_covdet_get_octave_resolution (VlCovDet const * self)\n{\n  return self->octaveResolution ;\n}\n\n/** @brief Set the octave resolutuon.\n ** @param self object.\n ** @param r octave resoltuion.\n **\n ** Calling this function resets the detector.\n **/\n\nvoid\nvl_covdet_set_octave_resolution (VlCovDet * self, vl_size r)\n{\n  self->octaveResolution = r ;\n  vl_covdet_reset(self) ;\n}\n\n/* ---------------------------------------------------------------- */\n/** @brief Get whether affine adaptation uses accurate smoothing.\n ** @param self object.\n ** @return @c true if accurate smoothing is used.\n **/\n\nvl_bool\nvl_covdet_get_aa_accurate_smoothing (VlCovDet const * self)\n{\n  return self->aaAccurateSmoothing ;\n}\n\n/** @brief Set whether affine adaptation uses accurate smoothing.\n ** @param self object.\n ** @param x whether accurate smoothing should be usd.\n **/\n\nvoid\nvl_covdet_set_aa_accurate_smoothing (VlCovDet * self, vl_bool x)\n{\n  self->aaAccurateSmoothing = x ;\n}\n\n/* ---------------------------------------------------------------- */\n/** @brief Get the max number of orientations\n ** @param self object.\n ** @return maximal number of orientations.\n **/\nvl_size\nvl_covdet_get_max_num_orientations( VlCovDet const * self)\n{\n  return self->maxNumOrientations ;\n}\n\n\n/* ---------------------------------------------------------------- */\n/** @brief Get the non-extrema suppression threshold\n ** @param self object.\n ** @return threshold.\n **/\n\ndouble\nvl_covdet_get_non_extrema_suppression_threshold (VlCovDet const * self)\n{\n  return self->nonExtremaSuppression ;\n}\n\n/** @brief Set the non-extrema suppression threshod\n ** @param self object.\n ** @param x threshold.\n **/\n\nvoid\nvl_covdet_set_non_extrema_suppression_threshold (VlCovDet * self, double x)\n{\n  self->nonExtremaSuppression = x ;\n}\n\n/** @brief Get the number of non-extrema suppressed\n ** @param self object.\n ** @return number.\n **/\n\nvl_size\nvl_covdet_get_num_non_extrema_suppressed (VlCovDet const * self)\n{\n  return self->numNonExtremaSuppressed ;\n}\n\n\n/* ---------------------------------------------------------------- */\n/** @brief Get number of stored frames\n ** @return number of frames stored in the detector.\n **/\nvl_size\nvl_covdet_get_num_features (VlCovDet const * self)\n{\n  return self->numFeatures ;\n}\n\n/** @brief Get the stored frames\n ** @return frames stored in the detector.\n **/\nvoid *\nvl_covdet_get_features (VlCovDet * self)\n{\n  return self->features ;\n}\n\n/** @brief Get the Gaussian scale space\n ** @return Gaussian scale space.\n **\n ** A Gaussian scale space exists only after calling ::vl_covdet_put_image.\n ** Otherwise the function returns @c NULL.\n **/\n\nVlScaleSpace *\nvl_covdet_get_gss (VlCovDet const * self)\n{\n  return self->gss ;\n}\n\n/** @brief Get the cornerness measure scale space\n ** @return cornerness measure scale space.\n **\n ** A cornerness measure scale space exists only after calling\n ** ::vl_covdet_detect. Otherwise the function returns @c NULL.\n **/\n\nVlScaleSpace *\nvl_covdet_get_css (VlCovDet const * self)\n{\n  return self->css ;\n}\n\n/** @brief Get the number of features found with a certain number of scales\n ** @param self object.\n ** @param numScales length of the histogram (out).\n ** @return histogram.\n **\n ** Calling this function makes sense only after running a detector\n ** that uses the Laplacian as a secondary measure for scale\n ** detection\n **/\n\nvl_size const *\nvl_covdet_get_laplacian_scales_statistics (VlCovDet const * self,\n                                           vl_size * numScales)\n{\n  *numScales = VL_COVDET_MAX_NUM_LAPLACIAN_SCALES ;\n  return self->numFeaturesWithNumScales ;\n}\n\n\n\n/* ---------------------------------------------------------------- */\n/** @brief Get wether to compute padded warped patches  \n ** @param self object.\n ** @return whether padded warped patches are computed.\n **/\nvl_bool\nvl_covdet_get_allow_padded_warping (VlCovDet const  * self)\n{\n  return self->allowPaddedWarping ;\n}\n\n/** @brief Set wether to compute padded warped patches  \n ** @param self object.\n ** @param t whether padded warped patches are computed.\n **/\nvoid\nvl_covdet_set_allow_padded_warping (VlCovDet * self, vl_bool t)\n{\n  self->allowPaddedWarping = t ;\n}\n', 'message': 'covdet.c: improves doc\n', 'author_name': 'Andrea Vedaldi', 'lang': 'c'}