Documentation - C API

imopv.h File Reference

Vectorized image operations. More...

#include "generic.h"

Defines

Image convolution flags
#define VL_PAD_BY_ZERO   (0x0 << 0)
 Pad with zeroes.
#define VL_PAD_BY_CONTINUITY   (0x1 << 0)
 Pad by continuity.
#define VL_PAD_MASK   (0x3)
 Padding field selector.
#define VL_TRANSPOSE   (0x1 << 2)
 Transpose result.

Functions

Image convolution
void vl_imconvcol_vf (float *dst, int dst_stride, float const *src, int src_width, int src_height, int src_stride, float const *filt, int filt_begin, int filt_end, int step, unsigned int flags)
void vl_imconvcol_vd (double *dst, int dst_stride, double const *src, int src_width, int src_height, int src_stride, double const *filt, int filt_begin, int filt_end, int step, unsigned int flags)
 Convolve image along columns.
void vl_imconvcoltri_f (float *dest, vl_size destStride, float const *image, vl_size imageWidth, vl_size imageHeight, vl_size imageStride, vl_size filterSize, vl_size step, int unsigned flags)
 Convolve an image along the columns with a triangular kernel.
void vl_imconvcoltri_d (double *dest, vl_size destStride, double const *image, vl_size imageWidth, vl_size imageHeight, vl_size imageStride, vl_size filterSize, vl_size step, int unsigned flags)
 Convolve an image along the columns with a triangular kernel.
Integral image
void vl_imintegral_f (float *integral, vl_size integralStride, float const *image, vl_size imageWidth, vl_size imageHeight, vl_size imageStride)
 Compute integral image.
void vl_imintegral_d (double *integral, vl_size integralStride, double const *image, vl_size imageWidth, vl_size imageHeight, vl_size imageStride)
 Compute integral image.
void vl_imintegral_i32 (vl_int32 *integral, vl_size integralStride, vl_int32 const *image, vl_size imageWidth, vl_size imageHeight, vl_size imageStride)
 Compute integral image.
void vl_imintegral_ui32 (vl_uint32 *integral, vl_size integralStride, vl_uint32 const *image, vl_size imageWidth, vl_size imageHeight, vl_size imageStride)
 Compute integral image.
Distance transform
void vl_image_distance_transform_d (double const *image, vl_size numColumns, vl_size numRows, vl_size columnStride, vl_size rowStride, double *distanceTransform, vl_uindex *indexes, double coeff, double offset)
void vl_image_distance_transform_f (float const *image, vl_size numColumns, vl_size numRows, vl_size columnStride, vl_size rowStride, float *distanceTransform, vl_uindex *indexes, float coeff, float offset)

Detailed Description

This module provides the following image operations:

  • Separable convolution. The function vl_imconvcol_vf() can be used to compute separable convolutions.
  • Convolution by a triangular kernel. The function vl_imconvcoltri_vf() is an optimized convolution routine for triangular kernels.
  • Distance transform. vl_image_distance_transform_f() is a linear algorithm to compute the distance transform of an image.
Remarks:
Some operations are optimized to exploit possible SIMD instructions. This requires image data to be properly aligned (typically to 16 bytes). Similalry, the image stride (the number of bytes to skip to move to the next image row), must be aligned.
Author:
Andrea Vedaldi

Function Documentation

void vl_image_distance_transform_d ( double const *  image,
vl_size  numColumns,
vl_size  numRows,
vl_size  columnStride,
vl_size  rowStride,
double *  distanceTransform,
vl_uindex indexes,
double  coeff,
double  offset 
)
vl_imconvcol_vd ( double *  dst,
int  dst_stride,
double const *  src,
int  src_width,
int  src_height,
int  src_stride,
double const *  filt,
int  filt_begin,
int  filt_end,
int  step,
unsigned int  flags 
)
Parameters:
dstdestination image.
dst_stridewidth of the destination image including padding.
srcsource image.
src_widthwidth of the source image.
src_heightheight of the source image.
src_stridewidth of the source image including padding.
filtfilter kernel.
filt_begincoordinate of the first filter element.
filt_endcoordinate of the last filter element.
stepsub-sampling step.
flagsoperation modes.

The function convolves the column of the image src by the filter filt and saves the result to the image dst. The size of dst must be equal to the size of src. Formally, this results in the calculation

\[ \mathrm{dst} [x,y] = \sum_{p=y-\mathrm{filt\_end}}^{y-\mathrm{filt\_begin}} \mathrm{src}[x,y] \mathrm{filt}[y - p - \mathrm{filt\_begin}] \]

The function subsamples the image along the columns according to the parameter step. Setting step to 1 (one) computes the elements $\mathrm{dst}[x,y]$ for all pairs (x,0), (x,1), (x,2) and so on. Setting step two 2 (two) computes only (x,0), (x,2) and so on (in this case the height of the destination image is floor(src_height/step)+1).

Calling twice the function can be used to compute 2-D separable convolutions. Use the flag VL_TRANSPOSE to transpose the result (in this case dst has transposed dimension as well).

The function allows the support of the filter to be any range. Usually the support is filt_end = -filt_begin.

The convolution operation may pick up values outside the image boundary. To cope with this edge cases, the function either pads the image by zero (VL_PAD_BY_ZERO) or with the values at the boundary (VL_PAD_BY_CONTINUITY).

vl_imconvcol_vf ( float *  dst,
int  dst_stride,
float const *  src,
int  src_width,
int  src_height,
int  src_stride,
float const *  filt,
int  filt_begin,
int  filt_end,
int  step,
unsigned int  flags 
)
vl_imconvcoltri_d ( double *  dest,
vl_size  destStride,
double const *  image,
vl_size  imageWidth,
vl_size  imageHeight,
vl_size  imageStride,
vl_size  filterSize,
vl_size  step,
int unsigned  flags 
)
Parameters:
destdestination image.
destStridedestination image stride.
imageimage to convolve.
imageWidthwidth of the image.
imageHeightheight of the image.
imageStridewidth of the image including padding.
filterSizesize of the triangular filter.
stepsub-sampling step.
flagsoperation modes.

The function convolves the columns of the image image with the triangular kernel

\[ k(t) = \frac{1}{\Delta^2} \max\{ \Delta - |t|, 0 \}, \quad t \in \mathbb{Z} \]

The paramter $ \Delta $, equal to the function argument filterSize, controls the width of the kernel. Notice that the support of $ k(x) $ as a continuous function of $ x $ is the open interval $ (-\Delta,\Delta) $, which has length $ 2\Delta $. However, $ k(x) $ restricted to the ingeter domain $ x \in \mathcal{Z} $ has support $ \{ -\Delta + 1, \Delta +2, \dots, \Delta-1 \} $, which counts $ 2 \Delta - 1 $ elements only. In particular, the discrete kernel is symmetric about the origin for all values of $ \Delta $.

The normalization factor $ 1 / \Delta^2 $ guaratnees that the filter is normalized to one, i.e.:

\[ \sum_{t=-\infty}^{+\infty} k(t) = 1 \]

Algorithm

The function exploits the fact that convolution by a triangular kernel can be expressed as the repeated convolution by a rectangular kernel, and that the latter can be performed in time indepenedent on the fiter width by using an integral-image type trick. Overall, the algorithm complexity is independent on the parameter filterSize and linear in the nubmer of image pixels.

See also:
vl_imconvcol_vd for details on the meaning of the other parameters.
vl_imconvcoltri_f ( float *  dest,
vl_size  destStride,
float const *  image,
vl_size  imageWidth,
vl_size  imageHeight,
vl_size  imageStride,
vl_size  filterSize,
vl_size  step,
int unsigned  flags 
)
vl_imintegral_d ( double *  integral,
vl_size  integralStride,
double const *  image,
vl_size  imageWidth,
vl_size  imageHeight,
vl_size  imageStride 
)
Parameters:
integralintegral image.
integralStrideintegral image stride.
imagesource image.
imageWidthsource image width.
imageHeightsource image height.
imageStridesource image stride.

Let $ I(x,y), (x,y) \in [0, W-1] \times [0, H-1] $. The function computes the integral image $ J(x,y) $ of $ I(x,g) $:

\[ J(x,y) = \sum_{x'=0}^{x} \sum_{y'=0}^{y} I(x',y') \]

The integral image $ J(x,y) $ can be used to compute quickly the integral of of $ I(x,y) $ in a rectangular region $ R = [x',x'']\times[y',y''] $:

\[ \sum_{(x,y)\in[x',x'']\times[y',y'']} I(x,y) = (J(x'',y'') - J(x'-1, y'')) - (J(x'',y'-1) - J(x'-1,y'-1)). \]

Note that the order of operations is important when the integral image has an unsigned data type (e.g. vl_uint32). The formula is easily derived as follows:

\begin{eqnarray*} \sum_{(x,y)\in R} I(x,y) &=& \sum_{x=x'}^{x''} \sum_{y=y'}^{y''} I(x,y)\\ &=& \sum_{x=0}^{x''} \sum_{y=y'}^{y''} I(x,y) - \sum_{x=0}^{x'-1} \sum_{y=y'}^{y''} I(x,y)\\ &=& \sum_{x=0}^{x''} \sum_{y=0}^{y''} I(x,y) - \sum_{x=0}^{x''} \sum_{y=0}^{y'-1} I(x,y) - \sum_{x=0}^{x'-1} \sum_{y=0}^{y''} I(x,y) + \sum_{x=0}^{x'-1} \sum_{y=0}^{y'-1} I(x,y)\\ &=& J(x'',y'') - J(x'-1,y'') - J(x'',y'-1) + J(x'-1,y'-1). \end{eqnarray*}

vl_imintegral_f ( float *  integral,
vl_size  integralStride,
float const *  image,
vl_size  imageWidth,
vl_size  imageHeight,
vl_size  imageStride 
)
See also:
vl_imintegral_d.
vl_imintegral_i32 ( vl_int32 integral,
vl_size  integralStride,
vl_int32 const *  image,
vl_size  imageWidth,
vl_size  imageHeight,
vl_size  imageStride 
)
See also:
vl_imintegral_d.
vl_imintegral_ui32 ( vl_uint32 integral,
vl_size  integralStride,
vl_uint32 const *  image,
vl_size  imageWidth,
vl_size  imageHeight,
vl_size  imageStride 
)
See also:
vl_imintegral_d.