prefilter.h File Reference

Code to create the coefficient array for a b-spline. More...

#include <limits>
#include "common.h"
#include "poles.h"
#include "filter.h"

Go to the source code of this file.

Classes
struct	vspline::iir_filter_specs
	structure to hold specifications for an iir_filter object. This set of parameters has to be passed through from the calling code through the multithreading code to the worker threads where the filter objects are finally constructed. Rather than passing the parameters via some variadic mechanism, it's more concise and expressive to contain them in a structure and pass that around. The filter itself inherits its specification type, and if the code knows the handler's type, it can derive the spec type. This way the argument passing can be formalized, allowing for uniform handling of several different filter types with the same code. Here we have the concrete parameter set needed for b-spline prefiltering. We'll pass one set of 'specs' per axis; it contains: More...
class	vspline::iir_filter< in_type, out_type, _math_type >
	class iir_filter implements an n-pole forward/backward recursive filter to be used for b-spline prefiltering. It inherits from the 'specs' class for easy initialization. More...
struct	vspline::bspl_prefilter< _vtype, _math_ele_type, _vsize >
	class to provide b-spline prefiltering, using 'iir_filter' above. The actual filter object has to interface with the data handling routine ('present', see filter.h). So this class functions as an adapter, combining the code needed to set up adequate buffers and creation of the actual IIR filter itself. The interface to the data handling routine is provided by inheriting from class buffer_handling More...

Namespaces
namespace	vspline

Functions
template<unsigned int dimension, typename in_value_type , typename out_value_type , typename math_ele_type >
void	vspline::amplify (const vigra::MultiArrayView< dimension, in_value_type > &input, vigra::MultiArrayView< dimension, out_value_type > &output, math_ele_type boost=1, int njobs=vspline::default_njobs)
	amplify is used to copy input to output, optionally applying 'boost' in the process. If the operation is in-place and 'boost' is 1, 'amplify' returns prematurely. More...
template<unsigned int dimension, typename in_value_type , typename out_value_type , typename math_ele_type = typename vspline::common_math_ele_type < in_value_type , out_value_type >, size_t vsize = vspline::vector_traits < math_ele_type > :: size>
void	vspline::prefilter (const vigra::MultiArrayView< dimension, in_value_type > &input, vigra::MultiArrayView< dimension, out_value_type > &output, vigra::TinyVector< bc_code, static_cast< int >(dimension) > bcv, int degree, xlf_type tolerance=std::numeric_limits< math_ele_type > ::epsilon(), xlf_type boost=xlf_type(1), int njobs=default_njobs)
	'prefilter' handles b-spline prefiltering for the whole range of acceptable input and output. It combines two bodies of code to achieve this goal: More...

Detailed Description

Code to create the coefficient array for a b-spline.

Note: the bulk of the code was factored out to filter.h, while this text still outlines the complete filtering process.

B-spline coefficients can be generated in two ways (that I know of): the first is by solving a set of equations which encode the constraints of the spline. A good example of how this is done can be found in libeinspline. I term it the 'linear algebra approach'. In this implementation, I have chosen what I call the 'DSP approach'. In a nutshell, the DSP approach looks at the b-spline's reconstruction as a convolution of the coefficients with a specific kernel. This kernel acts as a low-pass filter. To counteract the effect of this filter and obtain the input signal from the convolution of the coefficients, a high-pass filter with the inverse transfer function to the low-pass is used. This high-pass has infinite support, but can still be calculated precisely within the bounds of the arithmetic precision the CPU offers, due to the properties it has.

I recommend [CIT2000] for a formal explanation. At the core of my prefiltering routines there is code from Philippe Thevenaz' accompanying code to this paper, with slight modifications translating it to C++ and making it generic. The greater part of this file deals with 'generifying' the process and to employing multithreading and the CPU's vector units to gain speed.

This code makes heavy use of vigra, which provides handling of multidimensional arrays and efficient handling of aggregate types - to only mention two of it's many qualities. Explicit vectorization is done with Vc, which allowed me to code the horizontal vectorization I use in a generic fashion. If Vc is not available, the code falls back to presenting the data so that autovectorization becomes very likely - a technique I call 'goading'.

In another version of this code I used vigra's BSplineBase class to obtain prefilter poles. This required passing the spline degree/order as a template parameter. Doing it like this allows to make the Poles static members of the solver, but at the cost of type proliferation. Here I chose not to follow this path and pass the spline order as a parameter to the spline's constructor, thus reducing the number of solver specializations and allowing automated testing with loops over the degree. This variant may be slightly slower. The prefilter poles I use are precalculated externally with gsl/blas and polished in high precision to provide the most precise data possible. this avoids using vigra's polynomial root code which failed for high degrees when I used it.

[CIT2000] Interpolation Revisited by Philippe Thévenaz, Member,IEEE, Thierry Blu, Member, IEEE, and Michael Unser, Fellow, IEEE in IEEE TRANSACTIONS ON MEDICAL IMAGING, VOL. 19, NO. 7, JULY 2000,

Definition in file prefilter.h.