Home · Pages · Index · Overviews

Convolver Class Reference

Direct convolution of a filter at any location within an Array. More...

 #include <filters.h>

Routines

Convolver Routines

Convolver * Make_ConvolverG (Array *target I, Double_Array *filter C, Coordinate *anchor C)

Double_Array * Convolver_Filter (Convolver *c)
Coordinate * Convolver_Anchor (Convolver *c)
Indx_Type Convolver_Index (Convolver *c)
Coordinate * Convolver_Coordinate (Convolver *c)

void Place_Convolver (Convolver *c M, Index_Type p)
void Move_Convolver_Forward (Convolver *c M)
void Move_Convolver_Backward (Convolver *c M)

double Convolve (Convolver *c)
double Convolve_Segment (Convolver *c, Indx_Type offset, Size_Type span)

void Free_Convolver (Convolver *c F)
void Kill_Convolver (Convolver *c K)
void Reset_Convolver ()

Convolution Filters

Double_Vector * Gaussian_FilterG (double sigma, int radius)
Double_Vector * Box_FilterG (int radius)

Double_Array * Filter_PowerG (Double_Vector *filter F, int power)
Double_Array * Filter_ProductG (Double_Array *filter1 F, Double_Array *filter2 F)

Double_Array * LOG_FilterG (int n, double sigma, int radius)
Double_Array * DOG_FilterG (int n, double sigma1, double sigma2, int radius)
Double_Array * DOB_FilterG (int n, int radius1, int radius2)

Double_Array * ALOG_FilterG (int n, double *sigma, int *radius)
Double_Array * ADOG_FilterG (int n, double *sigma1, double *sigma2, int *radius)
Double_Array * ADOB_FilterG (int n, int *radius1, int *radius2)

Double_Matrix * Gabor_FilterG (double aspect, double sigma, double wavelen, double phase
                          double orient, int radius1, int radius2)

Detailed Description

A Convolver object is basically a Frame coupled with a PLAIN_KIND, FLOAT64_TYPE filter array of the same shape, that is created by calling Make_Convolver with the target array for the frame, the filter array (that also defines the shape of the frame), and the offset anchor for the frame. The added functionality is that one can request the convolution of the filter with the underlying array of the frame at the current position of the frame. This is accomplished with a direct, brute-force calculation of the convolution in time proportional to the size of the filter by calling Convolve. One can also request the convolution of a portion of a filter with Convolve_Segment. One can get the filter array, the anchor, and the index or coordinate of the current Convolver postion with the routines Convolver_Filter, Convolver_Anchor, Convolver_Index, and Convolver_Coordinate. In all four instances, one is being give a pointer to the object and not a reference (i.e. don't free or kill the pointer!).

A Convolver object is inherently short-lived and therefore Mylib does not realize the full repertoire of generic routines for the class, but simply allows one to free and/or kill a convolver with Free_Convolver and Kill_Convolver, and to reset the class (by killing all freed convolvers) with Reset_Convolver.

The convolution of a small array over a window at every position in an array is a common operation for smoothing noise, detecting edges, and computing derivatives at a point within an image. Mylib has optimized routines for performing such operations over an entire array or slice (see the Filters module) when such operations can be further optimized over a brute-force computation, such as when a multi-dimensional filter is separable, e.g. there exist functions g and h such that f(x,y) = g(x)h(y). A Convolver is useful in those cases where such optimizations are not possible, or the filter is only required at a sparse subset of an array, e.g. a Region. The class contains the routines described in the remainder of this overview that help one build common filters for use with a Convolver.

Gaussian_Filter produces a 1-dimensional filter with a specifiable standard deviation sigma. The domain of the Gaussian function is the entire real line, so one must specify the support or range of values radius that the filter is over. The resulting array is of length 2*radius+1 and the anchor of the filter should be given as radius as this is where the center of the Gaussian is located. Because of the implied truncation, the values in the filter are scaled up a bit so that their sum is 1 as should be true of any cumulative distribution function. Gaussian filters of multiple dimensions are separable, and therefore a possibly asymmetric n-dimensional Gaussian filter can be built up with n-1 calls to Filter_Product with a different Gaussian filter for each dimension, and a symmetric n-dimensional Gaussian filter can be created with a single call to Filter_Power. For example:

 Double_Array AGaussian(int n, double *sigma, int *radii)
 { Double_Array *filter = Gaussian_Filter(sigma[0],radii[0]);
   int           i;
   for (i = 1; i < n; i++)
     filter = Filter_Product(Gaussian_Filter(sigma[i],radii[i]),filter);
   return (filter);
 }

produces an n-dimensional Gaussian filter with standard deviation sigma[i] and support radii[i] in dimension i. Similarly Box_Filter produces a one-dimensional box or average filter because it too is separable.

On the otherhand, the Laplacian of Gaussian (LOG) and difference of Gaussian (DOG) filters are not separable, so the routines LOG_Filter, DOG_Filter, ALOG_Filter, and ADOG_Filter build n-dimensional symmetric and assymmetric filters directly. While a difference of boxes (DOB) filter is separable, the class provides routines DOB_Filter and ADOB_Filter to build them directly. Since these filters are generally used as edge and blob detectors, the values are offset equally by the minimal amount that makes the sum of all the elements sum to 0.

Finally, the class provides the special Gabor_Filter which is a 2D-filter that realizes the receptor field found in neurons of the retina and has generally been found to be useful in detecting texture and orientation.


Routine Documentation

Convolver * Make_ConvolverG (Array *target I, Double_Array *filter C, Coordinate *anchor C)

Creates a convolution object given a target array target and a FLOAT64_TYPE filter and an anchor point anchor relative to the filter, that can dynamically be placed at different positions with the array. The filter is assumed to be a small array (of any dimensionality) that is to be convolved with elements of the array at points of interest. Implicitly the convolver object has a Frame whose shape is the same as filter and whose anchor point is anchor. When the convolver is placed at a position the anchor point of the underlying frame is placed at the position a convolution at that point would take place with the current window of the frame when so positioned.

Double_Array * Convolver_Filter (Convolver *c)

Returns a pointer to the filter array for Convolver c. This is not a reference, one should not free or kill this pointer.

Coordinate * Convolver_Anchor (Convolver *c)

Returns a pointer to the anchor point for Convolver c. This is not a reference, one should not free or kill this pointer.

Indx_Type Convolver_Index (Convolver *c)

Returns the current index of position of Convolver c.

Coordinate * Convolver_Coordinate (Convolver *c)

Returns a pointer to the Coordinate corresponding to the current index or position of Convolver c. This is not a reference, one should not free or kill this pointer.

void Place_Convolver (Convolver *c M, Index_Type p)

Places convolver c at index p of its target array. Conceptually the anchor of the filter is placed over the coordinate corresponding to p and the frame of the filter is then offset with respect to the anchor. For example, if p corresponds to the coordinate (2,3,4) in a 3D array, and the anchor of the filter is (-3,2,5), then the 0-origin of the filter corresponds with the point (2-(-3),3-2,4-5) = (5,1,-1). Note carefully that the filter need not lie within the array and therefore the current boundary effect applies to all off-array elements that may be convolved with the filter.

void Move_Convolver_Forward (Convolver *c M)

Advance the current position of the convolver c forward by one.

void Move_Convolver_Backward (Convolver *c M)

Move the current position of the convolver c backward by one.

double Convolve (Convolver *c)

Return the value of the convolution of c at its current position.

double Convolve_Segment (Convolver *c, Indx_Type offset, Size_Type span)

Return the convolution of c at its current position, over just the subrange [offset,offset+span) of indices in the filter.

void Free_Convolver (Convolver *c F)

Free the convolver c. Beware, a Convolver is a short-lived object and therefore does not have the full repertoire of object primitives: it can be created, freed and/or killed, that's it.

void Kill_Convolver (Convolver *c K)

Kill the convolver c. Beware, a Convolver is a short-lived object and therefore does not have the full repertoire of object primitives: it can be created, freed and/or killed, that's it.

void Reset_Convolver ()

Reset the Convolver class by killing all freed convolvers in the free pool of the class.

Double_Vector * Gaussian_FilterG (double sigma, int radius)

Generates a 1-dimensional Gaussian filter with standard deviation sigma. A Gaussian technically has an infinite domain but the routine only samples radius pixels from both sides of its maximum at 0, so that the returned vector is of length 2*radius+1. The elements are normalized so that they sum to 1.

Double_Vector * Box_FilterG (int radius)

Generates a 1-dimensional vector of length 2*radius+1 whose elements have the value 1/(2*radius+1).

Double_Array * Filter_PowerG (Double_Vector *filter F, int power)

Generates a (power)-dimensional filter from a 1-dimensional separable filter. For example Filter_Power(Gaussian_Filter(0.5,2),3) produces a symmetric 5x5x5 3-dimensional Gaussian filter.

Double_Array * Filter_ProductG (Double_Array *filter1 F, Double_Array *filter2 F)

Generates an m+n-dimensional filter by taking the product of m-dimensional filter1 and n-dimensional filter2, where filter1 is providing the outer dimensions and filter2 the inner dimension. That is, the order of the operands is important. Formally, f(x·y) = filter1[x]*filter2[y], where f is the product, and x and y are m- and n-dimensional coordinates, respectively.

Double_Array * LOG_FilterG (int n, double sigma, int radius)

Generates an n-dimensional Laplacian of Gaussian (LOG) filter with standard deviation sigma and support radius (i.e. each dimension will be of length 2*radius+1). Formally, the Laplacian of a Gaussian Gσ is:

   ΔGσ(x1, x2, …) = Gσ(x1, x2, …) (Σi xi2 / σ4 - n / σ2)

The elements are normalized so they sum to 0.

Double_Array * DOG_FilterG (int n, double sigma1, double sigma2, int radius)

Generates an n-dimensional filter that is the difference of Gaussians (DOG) where a Gaussian with a standard deviation of sigma2 is subtracted from a Guassian with a standard deviation of sigma1, and where the support of the filter in each dimension is radius (i.e. each dimension is of length 2*radius+1 with the maximum of the filter at the center of the array). A DOG filter approximates an LOG filter when sigma2 = 1.6sigma1. The elements are normalized so they sum to 0.

Double_Array * DOB_FilterG (int n, int radius1, int radius2)

Generates an n-dimensional filter that is the difference of box filters (DOB) where a filter of radius radius2 is subtracted from a filter of radius1. The DOB is in some sense an even simpler form of a DOG filter, which in turn is an approximation of a DOG filter. The support of the filter in each dimension is the greater of radius1 and radius2.

Double_Array * ALOG_FilterG (int n, double *sigma, int *radius)

Generates an n-dimensional Laplacian of Gaussian (LOG) filter with standard deviations sigma[i] and support radius[i] in each dimension i. Formally, the Gaussian is Gσ1(x1)·Gσ2(x2)· … ·Gσn(xn) as Guassian filters are separable, and its Laplacian is:

   Gσ1(x1)·Gσ2(x2)· … ·Gσn(xn) (Σi xi2 / σi4 - Σi 1 / σi2)

The elements are normalized so they sum to 0.

Double_Array * ADOG_FilterG (int n, double *sigma1, double *sigma2, int *radius)

Generates an n-dimensional filter that is the difference of Gaussians (DOG) where an assymmetric Gaussian with standard deviations of sigma2[i] is subtracted from an assymetric Guassian with standard deviations sigma1[i], and where the support of the filter in each dimension i is radius[i] (i.e. each dimension is of length 2*radius[i]+1 with the maximum of the filter at the center of the array). A DOG filter approximates an LOG filter when sigma2[i] = 1.6sigma1[i]. The elements are normalized so they sum to 0.

Double_Array * ADOB_FilterG (int n, int *radius1, int *radius2)

Generates an n-dimensional filter that is the difference of box filters (DOB) where a filter of shape radius2 is subtracted from a filter of shape radius1. The DOB is in some sense an even simpler form of a DOG filter, which in turn is an approximation of a DOG filter. The support of the filter in each dimension i is the greater of radius1[i] and radius2[i].

Double_Matrix * Gabor_FilterG (double aspect, double sigma, double wavelen, double phase
                          double orient, int radius1, int radius2)

Generates a 2-dimensional Gabor filter with the given parameters of size radius1 x radius2. Basically a Gabor filter is an assymmetric Gaussian of standard deviations σ = sigma and σ/(α = aspect) convolved with a sine wave of wavelength λ = wavelen offset by phase φ = phase and then rotated by angle θ = orient. Formally:

   Gabor(i,j) = e(x2 + (αy)2)/(2σ2) cos( λx+φ)

   where x = i cosθ + j sinθ and y = j cosθ - i sinθ