mathop.h File Reference

Math operations. More...

#include "generic.h"
#include <math.h>

Defines
#define	VL_LOG_OF_2 0.693147180559945
	Logarithm of 2 (math constant).
#define	VL_PI 3.141592653589793
	Pi (math constant).
#define	VL_EPSILON_F 1.19209290E-07F
	IEEE single precision epsilon (math constant).
#define	VL_EPSILON_D 2.220446049250313e-16
	IEEE double precision epsilon (math constant).
#define	VL_NAN_F (vl_nan_f.value)
	IEEE single precision NaN (not signaling).
#define	VL_INFINITY_F (vl_infinity_f.value)
	IEEE single precision positive infinity (not signaling).
#define	VL_NAN_D (vl_nan_d.value)
	IEEE double precision NaN (not signaling).
#define	VL_INFINITY_D (vl_infinity_d.value)
	IEEE double precision positive infinity (not signaling).
Typedefs
typedef float(*	VlFloatVectorComparisonFunction )(vl_size dimension, float const X, float const Y)
	Pointer to a function to compare vectors of floats.
typedef double(*	VlDoubleVectorComparisonFunction )(vl_size dimension, double const X, double const Y)
	Pointer to a function to compare vectors of doubles.
typedef enum _VlVectorComparisonType	VlVectorComparisonType
	Vector comparison types.
Enumerations
enum	_VlVectorComparisonType { VlDistanceL1, VlDistanceL2, VlDistanceChi2, VlDistanceHellinger, VlDistanceJS, VlKernelL1, VlKernelL2, VlKernelChi2, VlKernelHellinger, VlKernelJS }
	Vector comparison types. More...
Functions
float	vl_mod_2pi_f (float x)
	Fast `mod(x, 2 * VL_PI)`.
double	vl_mod_2pi_d (double x)
	Fast `mod(x, 2 * VL_PI)`.
int	vl_floor_f (float x)
	Fast `(int) floor(x)`.
int	vl_floor_d (double x)
	Fast `(int) floor(x)`.
float	vl_abs_f (float x)
	Fast `abs(x)`.
double	vl_abs_d (double x)
	Fast `abs(x)`.
float	vl_fast_atan2_f (float y, float x)
	Fast `atan2` approximation.
double	vl_fast_atan2_d (double y, double x)
	Fast `atan2` approximation.
float	vl_fast_resqrt_f (float x)
	Fast `resqrt` approximation.
double	vl_fast_resqrt_d (double x)
	Fast `resqrt` approximation.
float	vl_fast_sqrt_f (float x)
	Fast `sqrt` approximation.
double	vl_fast_sqrt_d (float x)
	Fast `sqrt` approximation.
vl_uint32	vl_fast_sqrt_ui32 (vl_uint32 x)
	Fast `sqrt` approximation.
vl_uint16	vl_fast_sqrt_ui16 (vl_uint16 x)
	Fast `sqrt` approximation.
vl_uint8	vl_fast_sqrt_ui8 (vl_uint8 x)
	Fast `sqrt` approximation.
char const *	vl_get_vector_comparison_type_name (int type)
	Get the symbolic name of a vector comparison type.
VlFloatVectorComparisonFunction	vl_get_vector_comparison_function_f (VlVectorComparisonType type)
	Get vector comparison function from comparison type.
VlDoubleVectorComparisonFunction	vl_get_vector_comparison_function_d (VlVectorComparisonType type)
	Get vector comparison function from comparison type.
void	vl_eval_vector_comparison_on_all_pairs_f (float result, vl_size dimension, float const X, vl_size numDataX, float const *Y, vl_size numDataY, VlFloatVectorComparisonFunction function)
	Evaluate vector comparison function on all vector pairs.
void	vl_eval_vector_comparison_on_all_pairs_d (double result, vl_size dimension, double const X, vl_size numDataX, double const *Y, vl_size numDataY, VlDoubleVectorComparisonFunction function)
	Evaluate vector comparison function on all vector pairs.
Variables
union {
}	vl_nan_f
	IEEE single precision quiet NaN constant.
union {
}	vl_infinity_f
	IEEE single precision infinity constant.
union {
}	vl_nan_d
	IEEE double precision quiet NaN constant.
union {
}	vl_infinity_d
	IEEE double precision infinity constant.

Detailed Description

Comparing vectors

mathop.h includes a number of functions to quickly compute distances or similarity of pairs of vector. Applications include clustering and evaluation of SVM-like classifiers.

Use vl_get_vector_comparison_function_f or vl_get_vector_comparison_function_d obtain an approprite function to comprare vectors of floats or doubles, respectively. Such functions are usually optimized (for instance, on X86 platforms they use the SSE vector extension) and are several times faster than a naive implementation. vl_eval_vector_comparison_on_all_pairs_f and vl_eval_vector_comparison_on_all_pairs_d can be used to evaluate the comparison function on all pairs of one or two sequences of vectors.

Let $\mathbf{x} = (x_1,\dots,x_d)$ and $\mathbf{y} = (y_1,\dots,y_d)$ be two vectors. The following comparison functions are supported:

	VlDistanceL1	$\sum_{i=1}^d \|x_i - y_i\|$	l1 distance (squared intersection metric)
	VlDistanceL2	$\sum_{i=1}^d (x_i - y_i)^2$	Squared Euclidean disance
$\chi^2$	VlDistanceChi2	$\sum_{i=1}^d \frac{(x_i - y_i)^2}{x_i + y_i}$	Squared chi-square distance
-	VlDistanceHellinger	$\sum_{i=1}^d (\sqrt{x_i} - \sqrt{y_i})^2$	Squared Hellinger's distance
-	VlDistanceJS	$\sum_{i=1}^d \left( x_i \log\frac{2x_i}{x_i+y_i} + y_i \log\frac{2y_i}{x_i+y_i} \right)$	Squared Jensen-Shannon distance
	VlKernelL1	$\sum_{i=1}^d \min\{ x_i, y_i \}$	intersection kernel
	VlKernelL2	$\sum_{i=1}^d x_iy_i$	linear kernel
$\chi^2$	VlKernelChi2	$\sum_{i=1}^d 2 \frac{x_iy_i}{x_i + y_i}$	chi-square kernel
-	VlKernelHellinger	$\sum_{i=1}^d 2 \sqrt{x_i y_i}$	Hellinger's kernel (Bhattacharya coefficient)
-	VlKernelJS	$\sum_{i=1}^d \left( \frac{x_i}{2} \log_2\frac{x_i+y_i}{x_i} + \frac{y_i}{2} \log_2\frac{x_i+y_i}{y_i} \right)$	Jensen-Shannon kernel

Remarks:: The definitions have been choosen so that corresponding kernels and distances are related by the equation:
$d^2(\mathbf{x},\mathbf{y}) = k(\mathbf{x},\mathbf{x}) +k(\mathbf{y},\mathbf{y}) -k(\mathbf{x},\mathbf{y}) -k(\mathbf{y},\mathbf{x})$
This means that each of these distances can be interpreted as a squared distance or metric in the corresponding reproducing kernel Hilbert space. Notice in particular that the or Manhattan distance is also a squared distance in this sense.

Author:: Andrea Vedaldi

Definition in file mathop.h.

Define Documentation

#define VL_EPSILON_D 2.220446049250313e-16

1.0 + VL_EPSILON_D is the smallest representable double precision number greater than 1.0. Numerically, VL_EPSILON_D is equal to $2^{-52}$ .

Definition at line 40 of file mathop.h.

Referenced by vl_fast_atan2_d(), vl_sift_calc_keypoint_descriptor(), vl_sift_calc_raw_descriptor(), and vl_sift_keypoint_init().

#define VL_EPSILON_F 1.19209290E-07F

1.0F + VL_EPSILON_F is the smallest representable single precision number greater than 1.0F. Numerically, VL_EPSILON_F is equal to $2^{-23}$ .

Definition at line 32 of file mathop.h.

Referenced by _vl_dsift_normalize_histogram(), normalize_histogram(), vl_fast_atan2_f(), and vl_pgm_write_f().

Enumeration Type Documentation

enum _VlVectorComparisonType

Enumerator:

VlDistanceL1	l1 distance (squared intersection metric)
VlDistanceL2	squared l2 distance
VlDistanceChi2	squared Chi2 distance
VlDistanceHellinger	squared Hellinger's distance
VlDistanceJS	squared Jensen-Shannon distance
VlKernelL1	intersection kernel
VlKernelL2	l2 kernel
VlKernelChi2	Chi2 kernel
VlKernelHellinger	Hellinger's kernel
VlKernelJS	Jensen-Shannon kernel

Definition at line 484 of file mathop.h.

Function Documentation

double vl_abs_d ( double x ) [inline]

See also:: vl_abs_f

Definition at line 169 of file mathop.h.

Referenced by vl_fast_atan2_d(), and vl_sift_detect().

float vl_abs_f ( float x ) [inline]

Parameters:

x

argument.

Returns:: abs(x)

Definition at line 155 of file mathop.h.

Referenced by vl_fast_atan2_f(), vl_sift_calc_keypoint_descriptor(), and vl_sift_calc_raw_descriptor().

vl_eval_vector_comparison_on_all_pairs_d	(	double *	result,
		vl_size	dimension,
		double const *	X,
		vl_size	numDataX,
		double const *	Y,
		vl_size	numDataY,
		VlDoubleVectorComparisonFunction	function
	)

See also:: vl_eval_vector_comparison_on_all_pairs_f

vl_eval_vector_comparison_on_all_pairs_f	(	float *	result,
		vl_size	dimension,
		float const *	X,
		vl_size	numDataX,
		float const *	Y,
		vl_size	numDataY,
		VlFloatVectorComparisonFunction	function
	)

Parameters:

	result	comparison matrix (output).
	dimension	number of vector components (rows of X and Y).
	X	data matrix X.
	Y	data matrix Y.
	numDataX	number of vectors in X (columns of X)
	numDataY	number of vectros in Y (columns of Y)
	function	vector comparison function.

The function evaluates function on all pairs of columns from matrices X and Y, filling a numDataX by numDataY matrix.

If Y is a null pointer the function compares all columns from X with themselves.

double vl_fast_atan2_d	(	double	y,
		double	x
	)			`[inline]`

See also:: vl_fast_atan2_f

Definition at line 262 of file mathop.h.

References vl_abs_d(), VL_EPSILON_D, and VL_PI.

float vl_fast_atan2_f	(	float	y,
		float	x
	)			`[inline]`

------------------------------------------------------------------

Parameters:

	y	argument.
	x	argument.

The function computes a relatively rough but fast approximation of atan2(y,x).

Algorithm

The algorithm approximates the function $ f(r)=atan((1-r)/(1+r)) $ , $r \in [-1,1]$ with a third order polynomial $ f(r)=c_0 + c_1 r + c_2 r^2 + c_3 r^3 $ . To fit the polynomial we impose the constraints

$\begin{eqnarray*} f(+1) &=& c_0 + c_1 + c_2 + c_3 = atan(0) = 0,\\ f(-1) &=& c_0 - c_1 + c_2 - c_3 = atan(\infty) = \pi/2,\\ f(0) &=& c_0 = atan(1) = \pi/4. \end{eqnarray*}$

The last degree of freedom is fixed by minimizing the $l^{\infty}$ error, which yields

$c_0=\pi/4, \quad c_1=-0.9675, \quad c_2=0, \quad c_3=0.1821,$

with maximum error of 0.0061 radians at 0.35 degrees.

Returns:: Approximation of atan2(y,x).

Definition at line 239 of file mathop.h.

References vl_abs_f(), VL_EPSILON_F, and VL_PI.

Referenced by vl_dsift_process().

double vl_fast_resqrt_d ( double x ) [inline]

See also:: vl_fast_resqrt_d

Definition at line 339 of file mathop.h.

Referenced by vl_fast_sqrt_d().

float vl_fast_resqrt_f ( float x ) [inline]

------------------------------------------------------------------

Parameters:

x

argument.

Returns:: approximation of resqrt(x).

The function quickly computes an approximation of $x^{-1/2}$ .

Algorithm

The goal is to compute $y = x^{-1/2}$ , which we do by finding the solution of $0 = f(y) = y^{-2} - x$ by two Newton steps. Each Newton iteration is given by

$y \leftarrow y - \frac{f(y)}{\frac{df(y)}{dy}} = y + \frac{1}{2} (y-xy^3) = \frac{y}{2} \left( 3 - xy^2 \right)$

which yields a simple polynomial update rule.

The clever bit (attributed to either J. Carmack or G. Tarolli) is the way an initial guess $y \approx x^{-1/2}$ is chosen.

See also:: Inverse Sqare Root.

Definition at line 311 of file mathop.h.

Referenced by vl_fast_sqrt_f().

double vl_fast_sqrt_d ( float x ) [inline]

See also:: vl_fast_sqrt_f

Definition at line 422 of file mathop.h.

References vl_fast_resqrt_d().

float vl_fast_sqrt_f ( float x ) [inline]

------------------------------------------------------------------

Parameters:

x

argument.

Returns:: approximation of sqrt(x).

The function computes a cheap approximation of sqrt(x).

Floating-point algorithm

For the floating point cases, the function uses vl_fast_resqrt_f (or vl_fast_resqrt_d) to compute x * vl_fast_resqrt_f(x).

Integer algorithm

We seek for the largest integer y such that $y^2 \leq x$ . Write $ y = w + b_k 2^k + z $ where the binary expansion of the various variable is

$x = \sum_{i=0}^{n-1} 2^i a_i, \qquad w = \sum_{i=k+1}^{m-1} 2^i b_i, \qquad z = \sum_{i=0}^{k-1} 2^i b_i.$

Assume w known. Expanding the square and using the fact that $ b_k^2=b_k $ , we obtain the following constraint for $ b_k $ and z:

$x - w^2 \geq 2^k ( 2 w + 2^k ) b_k + z (z + 2wz + 2^{k+1}z b_k)$

A necessary condition for $ b_k = 1 $ is that this equation is satisfied for $ z = 0 $ (as the second term is always non-negative). In fact, this condition is also sufficient, since we are looking for the largest solution y.

This yields the following iterative algorithm. First, note that if x is stored in n bits, where n is even, then the integer square root does not require more than $ m = n / 2 $ bit to be stored. Thus initially, $ w = 0 $ and $ k = m - 1 = n/2 - 1 $ . Then, at each iteration the equation is tested, determining $b_{m-1}, b_{m-2}, ...$ in this order.

Definition at line 412 of file mathop.h.

References vl_fast_resqrt_f().

Referenced by _vl_dsift_normalize_histogram(), normalize_histogram(), and vl_dsift_process().

vl_uint16 vl_fast_sqrt_ui16 ( vl_uint16 x ) [inline]

See also:: vl_fast_sqrt_f

vl_uint32 vl_fast_sqrt_ui32 ( vl_uint32 x ) [inline]

See also:: vl_fast_sqrt_f

vl_uint8 vl_fast_sqrt_ui8 ( vl_uint8 x ) [inline]

See also:: vl_fast_sqrt_f

int vl_floor_d ( double x ) [inline]

See also:: vl_floor_f

Definition at line 142 of file mathop.h.

Referenced by fast_expn(), vl_sift_calc_keypoint_orientations(), and vl_sift_keypoint_init().

int vl_floor_f ( float x ) [inline]

Parameters:

x

argument.

Returns:: (int) floor(x)

Definition at line 130 of file mathop.h.

Referenced by vl_dsift_process(), vl_sift_calc_keypoint_descriptor(), and vl_sift_calc_raw_descriptor().

vl_get_vector_comparison_function_d ( VlVectorComparisonType type )

See also:: vl_get_vector_comparison_function_f

Referenced by vl_kdforest_new().

vl_get_vector_comparison_function_f ( VlVectorComparisonType type )

Parameters:

type

vector comparison type.

Returns:: comparison function.

Referenced by vl_kdforest_new().

char const* vl_get_vector_comparison_type_name ( int type ) [inline]

Parameters:

type

vector comparison type.

Returns:: data symbolic name.

Definition at line 506 of file mathop.h.

References VlDistanceChi2, VlDistanceL1, VlDistanceL2, VlKernelChi2, VlKernelL1, and VlKernelL2.

double vl_mod_2pi_d ( double x ) [inline]

See also:: vl_mod_2pi_f

Definition at line 117 of file mathop.h.

References VL_PI.

float vl_mod_2pi_f ( float x ) [inline]

Parameters:

x

input value.

Returns:: mod(x, 2 * VL_PI)

The function is optimized for small absolute values of x.

The result is guaranteed to be not smaller than 0. However, due to finite numerical precision and rounding errors, the result can be equal to 2 * VL_PI (for instance, if x is a very small negative number).

Definition at line 105 of file mathop.h.

References VL_PI.

Referenced by vl_dsift_process(), vl_sift_calc_keypoint_descriptor(), and vl_sift_calc_raw_descriptor().

Variable Documentation

union { ... } vl_infinity_d [static]

For internal use only.

union { ... } vl_infinity_f [static]

For internal use only.

union { ... } vl_nan_d [static]

For internal use only.

union { ... } vl_nan_f [static]

For internal use only.

VLFeat.org

mathop.h File Reference

Defines

Typedefs

Enumerations

Functions

Variables

Detailed Description

Comparing vectors

Define Documentation

Enumeration Type Documentation

Function Documentation

Variable Documentation