Fast algorithms in nD image analysis
Template library for multidimensional image processing and analysis
Multidimensional images templates and objects implemented with several separable algorithms for image processing and painting in C++. Several 2D and 3D usefull algorithms for processing and measurement are included.
Source code.
Sections of nD image
Orthogonal sections of n-dimensional image with dimensions 1 or n-1 can be calculated by simple algorithms using one programming cycle only. n-1-dimensional slicing of the array is used for visualization or analysis purposes. By iterating the slicing operation we can obtain section of arbitrary dimension. Traversing of rows and slices is used in separable algorithms like FFT, the Gaussian filter, Daubeschies wavelet filter or the squared Euclidean distance transform applying 1-dimensional operations on all rows successively in all directions.
Explanation.
Fast Fourier transform of real arrays
An inplace implementation of the real-valued n-dimensional FFT,
based on
ffteasy by G. Felder. The algorithm wraps the real array to complex array and then applies separable direct complex FFT for a direct operation, or calculates separable inverse complex FFT and unwraps the complex array to real array for inverse operation. The procedure for calculation of FT of convolution or correlation of two images are included as well as the procedure for calculation of FT of image with origin shifted to the centre of the image.
Source code.
Description.
Other separable nD transforms
Separable implementations of Gaussian filter, using either 1D convolution or fast recursive 1D algorithm (Young & van Vliet, 2002, Triggs & Sdika, 2006), of wavelet transform (Daubeschies, 1988), or of squared Euclidean distance transform (Breu et al., 1995).
- Young I.T., van Vliet L.J.: Recursive Gabor filtering, IEEE Trans. Signal Processing 50 (2002), 2798-2805.
- Triggs B., Sdika M.: Boundary conditions for Young-van Vliet recursive filtering, IEEE Trans. Signal Processing 54 (2006), 2365-2367.
- Daubeschies I.: Orthonormal bases of compactly supported wavelets, Communications on Pure and Applied Mathematics 41 (1988), 909-996.
-
Breu H., Gil J., Kirkpatrick D., Werman M.: Linear time euclidean distance transform
algorithms, IEEE Trans. PAMI 17 (1995), 529-533.
Gaussian description.
Recursive IA filters
There are several recursive implementation of image analysis filters with performance independent on filter kernel size, that can be easilly generalized to arbitrary dimension: erosion and dilation (van Herk, 1992), moving average (Glasbey and Jones, 1998) and median (Perreault and Hebert, 2009).
- van Herk M.: A fast algorithm for local minimum and maximum filters on rectangular and octagonal kernels. Pattern Recognition Letters, 13 (1992), 517-521.
- Glasbey C.A., Jones R.: Fast computation of moving average and related filters in octagonal windows. Pattern Recognition Letters, 18 (1997), 555-565.
- Perreault S., Hebert P.: Median filtering in constant time. IEEE Transactions on Image Processing, 16 (2007), 2389-2394.
Lipschitz filter
The well known two-pass chamfer distance algorithm in nD (Borgefors, 1984) applied to grayscale images (Štencel & Janáček, 2006).
- Borgefors G.: Distance transformations in arbitrary dimensions. CVGIP 27 (1984), 321-
345.
- Štencel M., Janáček J.: On calculation of chamfer distance and Lipschitz covers in digital images. Proceedings S4G, Editors R. Lechnerová, I. Saxl, V. Beneš, Prague, Union of Czech Mathematicians and Physicists, 2006, 517-522 (PDF)
ImageJ PlugIn
Graph cut regularization, segmentation or correspondence
Graph cut optimization enables updating the subsets of image elements or geometrical primitives simultaneously, which helps us solving various problems of image analysis and geometrical modelling.
- Boykov Y., Funka-Lea G.: Graph cuts and efficient N-D image segmentation. International Journal of Computer Vision 70 (2006), 109–131.
Description
Jiří Janáček