(, , ) proposed a helix transform for mapping multidimensional convolution operators to their one-dimensional equivalents. This transform proves the feasibility of multidimensional deconvolution, an issue that has been in question for more than 15 years. By mapping discrete convolution operators to one-dimensional space, the inverse filtering problem can be conveniently recast in terms of recursive filtering, a well-known part of the digital filtering theory.
 |
The helix filtering idea is schematically illustrated in Figure 10. The left plot (labeled ``a'' in the figure) shows a two-dimensional digital filter overlayed on the computational grid. A two-dimensional convolution computes its output by sliding the filter over the plane. If we impose helical boundary conditions on one of the axes, the filter will slide to the beginning of the next trace after reaching the end of the previous one (plot ``b''). As evident from plots ``c'' and ``d'', this is completely equivalent to one-dimensional convolution with a long 1-D filter with internal gaps. For efficiency, the gaps are simply ignored in a helical convolution program. The computational gain is not, however, in the convolution itself, but in the ability to perform recursive inverse filtering (deconvolution) in multiple dimensions. A multi-dimensional filter is mapped to its 1-D analog by imposing helical boundary conditions on the appropriate axes. After that, inverse filtering is applied recursively in a one-dimensional manner. Neglecting parallelization and indexing issues, the cost of inverse filtering is equivalent to the cost of convolution. It is proportional to the data size and to the number of non-zero filter coefficients.
 |
An example of two-dimensional recursive filtering is shown in Figure 11. The left plot contains two spikes and two filter impulse responses with different polarity. After deconvolution with the given filter, the filter responses turn into spikes, and the initial spikes turn into long-tailed inverse impulse responses (right plot in Figure 11). Helical wrap-around, visible on the horizontal boundaries, indicates the direction of the helix. () presents more examples and discusses all the issues of multidimensional helical deconvolution in detail.
As is known from the one-dimensional theory (), a stable recursive filtering requires a minimum-phase filter, which can be constructed with a spectral factorization algorithm. The Wilson-Burg spectral factorization method, described in the next section, is particularly convenient for helical filtering.