SIFT - Definition. More...

#include "sift.h"
#include "imopv.h"
#include "mathop.h"
#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stdio.h>

Macros
#define	VL_SIFT_BILINEAR_ORIENTATIONS 1
	Use bilinear interpolation to compute orientations. More...

#define	EXPN_SZ 256

#define	EXPN_MAX 25.0

Functions
double	fast_expn (double x)
	Fast \(exp(-x)\) approximation. More...

void	fast_expn_init ()
	Initialize tables for fast_expn. More...

static void	copy_and_upsample_rows (vl_sift_pix dst, vl_sift_pix const src, int width, int height)
	Copy image, upsample rows and take transpose. More...

static void	_vl_sift_smooth (VlSiftFilt self, vl_sift_pix outputImage, vl_sift_pix tempImage, vl_sift_pix const inputImage, vl_size width, vl_size height, double sigma)
	Smooth an image. More...

static void	copy_and_downsample (vl_sift_pix dst, vl_sift_pix const src, int width, int height, int d)
	Copy and downsample an image. More...

VlSiftFilt *	vl_sift_new (int width, int height, int noctaves, int nlevels, int o_min)
	Create a new SIFT filter. More...

void	vl_sift_delete (VlSiftFilt *f)
	Delete SIFT filter. More...

int	vl_sift_process_first_octave (VlSiftFilt f, vl_sift_pix const im)
	Start processing a new image. More...

int	vl_sift_process_next_octave (VlSiftFilt *f)
	Process next octave. More...

void	vl_sift_detect (VlSiftFilt *f)
	Detect keypoints. More...

static void	update_gradient (VlSiftFilt *f)
	Update gradients to current GSS octave. More...

int	vl_sift_calc_keypoint_orientations (VlSiftFilt f, double angles [4], VlSiftKeypoint const k)
	Calculate the keypoint orientation(s) More...

vl_sift_pix	normalize_histogram (vl_sift_pix begin, vl_sift_pix end)
	Normalizes in norm L_2 a descriptor. More...

void	vl_sift_calc_raw_descriptor (VlSiftFilt const f, vl_sift_pix const grad, vl_sift_pix *descr, int width, int height, double x, double y, double sigma, double angle0)
	Run the SIFT descriptor on raw data. More...

void	vl_sift_calc_keypoint_descriptor (VlSiftFilt f, vl_sift_pix descr, VlSiftKeypoint const *k, double angle0)
	Compute the descriptor of a keypoint. More...

void	vl_sift_keypoint_init (VlSiftFilt const f, VlSiftKeypoint k, double x, double y, double sigma)
	Initialize a keypoint from its position and scale. More...

Variables
double	expn_tab [EXPN_SZ+1]

Detailed Description

Author: Andrea Vedaldi

Macro Definition Documentation

◆ EXPN_MAX

#define EXPN_MAX 25.0

fast_expn table max

◆ EXPN_SZ

#define EXPN_SZ 256

fast_expn table size

◆ VL_SIFT_BILINEAR_ORIENTATIONS

#define VL_SIFT_BILINEAR_ORIENTATIONS 1

Function Documentation

◆ _vl_sift_smooth()

static void _vl_sift_smooth	(	VlSiftFilt *	self,
		vl_sift_pix *	outputImage,
		vl_sift_pix *	tempImage,
		vl_sift_pix const *	inputImage,
		vl_size	width,
		vl_size	height,
		double	sigma
	)

static

Parameters

self	SIFT filter.
outputImage	output imgae buffer.
tempImage	temporary image buffer.
inputImage	input image buffer.
width	input image width.
height	input image height.
sigma	smoothing.

◆ copy_and_downsample()

static void copy_and_downsample	(	vl_sift_pix *	dst,
		vl_sift_pix const *	src,
		int	width,
		int	height,
		int	d
	)

static

Parameters

dst	output imgae buffer.
src	input image buffer.
width	input image width.
height	input image height.
d	octaves (non negative).

The function downsamples the image d times, reducing it to 1/2^d of its original size. The parameters width and height are the size of the input image. The destination image dst is assumed to be floor(width/2^d) pixels wide and floor(height/2^d) pixels high.

◆ copy_and_upsample_rows()

static void copy_and_upsample_rows	(	vl_sift_pix *	dst,
		vl_sift_pix const *	src,
		int	width,
		int	height
	)

static

Parameters

dst	output image buffer.
src	input image buffer.
width	input image width.
height	input image height.

The output image has dimensions height by 2 width (so the destination buffer must be at least as big as two times the input buffer).

Upsampling is performed by linear interpolation.

◆ fast_expn()

double fast_expn ( double x )

inline

Parameters

x argument.

The argument must be in the range [0, EXPN_MAX] .

Returns: approximation of \(exp(-x)\).

◆ fast_expn_init()

void fast_expn_init ( )

inline

◆ normalize_histogram()

vl_sift_pix normalize_histogram	(	vl_sift_pix *	begin,
		vl_sift_pix *	end
	)

inline

Parameters

begin	begin of histogram.
end	end of histogram.

◆ update_gradient()

static void update_gradient ( VlSiftFilt * f )

static

Parameters

f	SIFT filter.

The function makes sure that the gradient buffer is up-to-date with the current GSS data.

Remarks: The minimum octave size is 2x2xS.

◆ vl_sift_calc_keypoint_descriptor()

void vl_sift_calc_keypoint_descriptor	(	VlSiftFilt *	f,
		vl_sift_pix *	descr,
		VlSiftKeypoint const *	k,
		double	angle0
	)

Parameters

f	SIFT filter.
descr	SIFT descriptor (output)
k	keypoint.
angle0	keypoint direction.

The function computes the SIFT descriptor of the keypoint k of orientation angle0. The function fills the buffer descr which must be large enough to hold the descriptor.

The function assumes that the keypoint is on the current octave. If not, it does not do anything.

◆ vl_sift_calc_keypoint_orientations()

int vl_sift_calc_keypoint_orientations	(	VlSiftFilt *	f,
		double	angles[4],
		VlSiftKeypoint const *	k
	)

Parameters

f	SIFT filter.
angles	orientations (output).
k	keypoint.

The function computes the orientation(s) of the keypoint k. The function returns the number of orientations found (up to four). The orientations themselves are written to the vector angles.

Remarks: The function requires the keypoint octave k->o to be equal to the filter current octave vl_sift_get_octave. If this is not the case, the function returns zero orientations.; The function requires the keypoint scale level k->s to be in the range s_min+1 and s_max-2 (where usually s_min=0 and s_max=S+2). If this is not the case, the function returns zero orientations.

Returns: number of orientations found.

◆ vl_sift_calc_raw_descriptor()

void vl_sift_calc_raw_descriptor	(	VlSiftFilt const *	f,
		vl_sift_pix const *	grad,
		vl_sift_pix *	descr,
		int	width,
		int	height,
		double	x,
		double	y,
		double	sigma,
		double	angle0
	)

Parameters

f	SIFT filter.
grad	image gradients.
descr	SIFT descriptor (output).
width	image width.
height	image height.
x	keypoint x coordinate.
y	keypoint y coordinate.
sigma	keypoint scale.
angle0	keypoint orientation.

The function runs the SIFT descriptor on raw data. Here image is a 2 x width x height array (by convention, the memory layout is a s such the first index is the fastest varying one). The first width x height layer of the array contains the gradient magnitude and the second the gradient angle (in radians, between 0 and \( 2\pi \)). x, y and sigma give the keypoint center and scale respectively.

In order to be equivalent to a standard SIFT descriptor the image gradient must be computed at a smoothing level equal to the scale of the keypoint. In practice, the actual SIFT algorithm makes the following additional approximation, which influence the result:

Scale is discretized in S levels.
The image is downsampled once for each octave (if you do this, the parameters x, y and sigma must be scaled too).

◆ vl_sift_delete()

void vl_sift_delete ( VlSiftFilt * f )

Parameters

f	SIFT filter to delete.

The function frees the resources allocated by vl_sift_new().

◆ vl_sift_detect()

void vl_sift_detect ( VlSiftFilt * f )

The function detect keypoints in the current octave filling the internal keypoint buffer. Keypoints can be retrieved by vl_sift_get_keypoints().

Parameters

f	SIFT filter.

Index GSS

Index matrix A

◆ vl_sift_keypoint_init()

void vl_sift_keypoint_init	(	VlSiftFilt const *	f,
		VlSiftKeypoint *	k,
		double	x,
		double	y,
		double	sigma
	)

Parameters

f	SIFT filter.
k	SIFT keypoint (output).
x	x coordinate of the keypoint center.
y	y coordinate of the keypoint center.
sigma	keypoint scale.

The function initializes a keypoint structure k from the location x and y and the scale sigma of the keypoint. The keypoint structure maps the keypoint to an octave and scale level of the discretized Gaussian scale space, which is required for instance to compute the keypoint SIFT descriptor.

Algorithm

The formula linking the keypoint scale sigma to the octave and scale indexes is

\[ \sigma(o,s) = \sigma_0 2^{o+s/S} \]

In addition to the scale index s (which can be fractional due to scale interpolation) a keypoint has an integer scale index is too (which is the index of the scale level where it was detected in the DoG scale space). We have the constraints (Detector see also the "SIFT detector"):

o is integer in the range \( [o_\mathrm{min}, o_{\mathrm{min}}+O-1] \).
is is integer in the range \( [s_\mathrm{min}+1, s_\mathrm{max}-2] \). This depends on how the scale is determined during detection, and must be so here because gradients are computed only for this range of scale levels and are required for the calculation of the SIFT descriptor.
\( |s - is| < 0.5 \) for detected keypoints in most cases due to the interpolation technique used during detection. However this is not necessary.

Thus octave o represents scales \( \{ \sigma(o, s) : s \in [s_\mathrm{min}+1-.5, s_\mathrm{max}-2+.5] \} \). Note that some scales may be represented more than once. For each scale, we select the largest possible octave that contains it, i.e.

\[ o(\sigma) = \max \{ o \in \mathbb{Z} : \sigma_0 2^{\frac{s_\mathrm{min}+1-.5}{S}} \leq \sigma \} = \mathrm{floor}\,\left[ \log_2(\sigma / \sigma_0) - \frac{s_\mathrm{min}+1-.5}{S}\right] \]

and then

\[ s(\sigma) = S \left[\log_2(\sigma / \sigma_0) - o(\sigma)\right], \quad is(\sigma) = \mathrm{round}\,(s(\sigma)) \]

In practice, both \( o(\sigma) \) and \( is(\sigma) \) are clamped to their feasible range as determined by the SIFT filter parameters.

◆ vl_sift_new()

VlSiftFilt* vl_sift_new	(	int	width,
		int	height,
		int	noctaves,
		int	nlevels,
		int	o_min
	)

Parameters

width	image width.
height	image height.
noctaves	number of octaves.
nlevels	number of levels per octave.
o_min	first octave index.

The function allocates and returns a new SIFT filter for the specified image and scale space geometry.

Setting O to a negative value sets the number of octaves to the maximum possible value depending on the size of the image.

Returns: the new SIFT filter.

See also: vl_sift_delete().

◆ vl_sift_process_first_octave()

int vl_sift_process_first_octave	(	VlSiftFilt *	f,
		vl_sift_pix const *	im
	)

Parameters

f	SIFT filter.
im	image data.

The function starts processing a new image by computing its Gaussian scale space at the lower octave. It also empties the internal keypoint buffer.

Returns: error code. The function returns VL_ERR_EOF if there are no more octaves to process.

See also: vl_sift_process_next_octave().

◆ vl_sift_process_next_octave()

int vl_sift_process_next_octave ( VlSiftFilt * f )

Parameters

f	SIFT filter.

The function computes the next octave of the Gaussian scale space. Notice that this clears the record of any feature detected in the previous octave.

Returns: error code. The function returns the error VL_ERR_EOF when there are no more octaves to process.

See also: vl_sift_process_first_octave().

Variable Documentation

◆ expn_tab

double expn_tab[EXPN_SZ+1]

fast_expn table

VLFeat.org

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ EXPN_MAX

◆ EXPN_SZ

◆ VL_SIFT_BILINEAR_ORIENTATIONS

Function Documentation

◆ _vl_sift_smooth()

◆ copy_and_downsample()

◆ copy_and_upsample_rows()

◆ fast_expn()

◆ fast_expn_init()

◆ normalize_histogram()

◆ update_gradient()

◆ vl_sift_calc_keypoint_descriptor()

◆ vl_sift_calc_keypoint_orientations()

◆ vl_sift_calc_raw_descriptor()

◆ vl_sift_delete()

◆ vl_sift_detect()

◆ vl_sift_keypoint_init()

◆ vl_sift_new()

◆ vl_sift_process_first_octave()

◆ vl_sift_process_next_octave()

Variable Documentation

◆ expn_tab