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)`
long int	vl_floor_f (float x)
	Floor and convert to integer.
long int	vl_floor_d (double x)
	Floor and convert to integer.
long int	vl_ceil_f (float x)
	Ceil and convert to integer.
long int	vl_ceil_d (double x)
	Ceil and convert to integer.
long int	vl_round_f (float x)
	Round.
long int	vl_round_d (double x)
	Round.
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

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}$ .

#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}$ .

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

Function Documentation

double vl_abs_d ( double x ) [inline]

See also:: vl_abs_f

float vl_abs_f ( float x ) [inline]

Parameters:

x argument.

Returns:: abs(x)

long int vl_ceil_d ( double x ) [inline]

See also:: vl_ceil_f

long int vl_ceil_f ( float x ) [inline]

Parameters:

x argument.

Returns:: lceilf(x)

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

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).

double vl_fast_resqrt_d ( double x ) [inline]

See also:: vl_fast_resqrt_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.

double vl_fast_sqrt_d ( float x ) [inline]

See also:: vl_fast_sqrt_f

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.

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

long int vl_floor_d ( double x ) [inline]

See also:: vl_floor_f

long int vl_floor_f ( float x ) [inline]

Parameters:

x argument.

Returns:: Similar to (int) floor(x)

vl_get_vector_comparison_function_d ( VlVectorComparisonType type )

See also:: vl_get_vector_comparison_function_f

vl_get_vector_comparison_function_f ( VlVectorComparisonType type )

Parameters:

type	vector comparison type.

Returns:: comparison function.

char const* vl_get_vector_comparison_type_name ( int type ) [inline]

Parameters:

type	vector comparison type.

Returns:: data symbolic name.

double vl_mod_2pi_d ( double x ) [inline]

See also:: vl_mod_2pi_f

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).

long int vl_round_d ( double x ) [inline]

Parameters:

x argument.

Returns:: lround(x) This function is either the same or similar to C99 lround().

long int vl_round_f ( float x ) [inline]

Parameters:

x argument.

Returns:: lroundf(x) This function is either the same or similar to C99 lroundf().

Variable Documentation

union { ... } vl_infinity_d [static]

union { ... } vl_infinity_f [static]

union { ... } vl_nan_d [static]

union { ... } vl_nan_f [static]

VLFeat.org

Defines

Typedefs

Enumerations

Functions

Variables

Detailed Description

Comparing vectors

Define Documentation

Enumeration Type Documentation

Function Documentation

Variable Documentation