25-10-2012, 05:58 PM
Computing rank-convolutions with a mask
[attachment=37154]
INTRODUCTION
Motivation
Min-convolution and more generally, rank-convolutions (a. k. a. rank filters) have
important applications in a variety of areas, including signal processing, pattern
recognition, computer vision, and mathematical programming. For example, in
computer vision they have been used for object recognition, depth estimation, and
image restoration. Rank-convolutions such as the median-convolution have the
advantage of being more robust against certain types of noise.
Fast algorithms for computing ordinary convolutions are at the heart of a wide
range of applications. We expect that efficient algorithms for computing the minconvolution
and more generally, rank-convolutions, would also have an impact in a
variety of areas.
PRIOR WORK
In this account, we assume the dimension is d = 1. This is the case that received the
most attention; and the improvement produced by our algorithm in one dimension
is essentially the same as in higher dimensions, saving a factor of e(
p
K) where K
is the size of the mask.
For simplicity, we shall also assume m = n. In this case the brute force computation
of the one-dimensional min-convolution takes O(n2) operations (in the
RAM model with real arithmetic). We discuss previous attempts at improving this
quadratic behavior.
Early work: the slope transform
Bellman and Karush [1962] introduced a transform (the “maximum transform”)
which is an extension of the Legendre transform to not necessarily convex functions.
Bellman and Karush showed how this transform can be used to compute
the min-convolution of a pair of convex functions. Maragos [1995] rediscovered the
Bellman–Karush transform and called it the slope transform; this term has gained
acceptance in the mathematical morphology community. We note that the concept
was defined for continuous signals and some ad-hoc discretization was used for its
approximate calculation. Maragos saw that the slope transform plays a similar role
for morphological operators as the Fourier transform does for linear operators.
In analogy with the convolution theorem for the Fourier transform, the slope
transform of f
min g is the sum of the slope transforms of f and g. While the
slope transforms of sampled functions f, g : [n] ! R can be sensibly defined, and
computed in linear time, this does not lead to a fast min-convolution algorithm
because the slope transform is not invertible. The slope transform of h is identical to
the slope transform of the lower hull of h (the maximal convex function dominated
by h). The slope transform can be used to compute f
min g in O(n) time when
both f and g are convex, in which case the output is also convex.
Convexity assumptions
Under convexity assumptions, faster algorithms are known for min-convolution, but
not for the potentially more important case of rank-convolutions.
The only special case we are aware of where a fast algorithm is known for rankconvolutions
is the when the mask is an axis-parallel box. This case is common in
computer vision and image processing. Rank-convolutions in this case can be computed
in O(n log n) time; and min-convolution in O(n) (Gil and Werman [1993]).
Computing min-convolutions when f is arbitrary but g is convex has received
special attention because of its applications to sequence alignment [Eppstein 1989]
and to computing distance transforms of images [Felzenszwalb and Huttenlocher
2004]. As pointed out by Eppstein [1989], the problem can be solved in O(n) time
by using the totally monotone matrix search algorithm of Aggarwal et al. [1987].
When g is concave, the min-convolution can be computed in O(n(n)) time using
the matrix search algorithm of Klawe and Kleitman [1990]. Here is the extremely
slowly growing inverse Ackermann function. Eppstein [1989] combined the convex
and the concave cases and generalized them to an algorithm that computes the
min-convolution in O(nk(n/k)) time when g can be decomposed into a sequence
of k convex or concave segments.
APPLICATIONS
Applications of min-convolution
Bellman and Karush [1962] considered min-convolution in the context of optimization
problems in economics and operations research such as optimal distribution
of effort and allocation processes. Min-convolution plays an important role in signal
processing because it is closely related to the dilation and erosion of real valued
signals [Serra 1982; Maragos 1995]. Recently one and two-dimensional minconvolutions
have been crucial in developing a variety of fast algorithms in computer
vision [Felzenszwalb and Huttenlocher 2004; 2005; 2006; Crandall et al. 2005]
and sequential data analysis [Felzenszwalb et al. 2004]. The operation arises naturally
in the solution of sequence alignment problems [Eppstein 1989]. Sequence
alignment is widely used in computational biology to find similarities between
DNA/RNA/protein sequences, as well as for time-warping in speech/sound recognition
and other pattern matching situations [Sankoff and Kruskal 1983].