Efficient Gaussian Distance Transforms for Image Processing

This paper presents Gaussian distance transform (GDT) of images and demonstrates its applications to image partition and image filtering. The time complexity of the naive implementation of GDT is quadratic on the image size and is thus computationally intractable for real time applications and for high resolution images. To address this issue, we investigate the properties of GDT and show that GDT can be conducted in linear lime using well known matrix search algorithms. Experimental results are provided to show the applications of GDT to image partition and image filtering.

This work was supported by a Faculty of Science and Engineering Research and Development Committee Small Grants Program of Curtin University.

Authors and Affiliations

1. School of Electrical Engineering, Computing and Mathematical Sciences, Curtin University, Kent Street, Bentley, WA, 6102, Australia

   Senjian An, Yiwei Liu, Wanquan Liu & Ling Li

Corresponding author

Correspondence to Senjian An .

Editors and Affiliations

1. Deakin University, Burwood, VIC, Australia

   Jianxin Li

2. The University of Queensland, St. Lucia, QLD, Australia

   Sen Wang

3. Flinders University, Bedford Park, SA, Australia

   Shaowen Qin

4. Dalian Neusoft University of Information, Dalian, China

   Xue Li

5. Beijing Institute of Technology, Beijing, China

   Shuliang Wang

Appendix: Proof of Theorem 1

Consider the optimization problem (5)

The core problem is the following 1D grid optimization with a given sequence f(i) with length l.

Later we will show that this sequence transform problem can be solved in O(l) time. The matrix J can be obtained by calling the sequence transform (18) m times, for \(y_1=1,2,\cdots m\), each time setting \(f(i)=J(y_1,i)\) where \(i=1,2,\cdots ,n\). This procedure takes O(mn) time. Then based on J, the matrix \(VT_{\gamma }\) can be obtained by calling (18) n times, for \(x_2=1,2,\cdots ,n\), each time setting \(f(i)=J(i,x_2)\) where \(i=1,2,\cdots ,m\). This procedure takes O(mn) time. So the total time complexity is linear in terms of the matrix size.

Now we show the sequence transform (18) can be solved in linear time. First we prove that this problem is related to a well-known matrix search problem in combinational optimization.

A matrix A is called a Monge Matrix if it satisfies the so-called Monge Property

A is called Inverse Monge Matrix if the above the inequalities hold in the reverse directions, i.e.,

An handy property of Monge matrices for us to check its Monge property is that the Monge property (or inverse Monge property) holds if and only if it holds for adjacent rows and adjacent columns, that is, it suffices to check

for Monge property, or

for inverse Monge property.

Another property of inverse Monge matrices is that inverse Monge matrices are totally monotone matrices and its row maxima can be found in \(O(n+m)\) time by SMAWK algorithm [1]. Note that reversing the order of its rows turns a Monge matrix into an inverse Monge matrix. And therefore, the row maxima of a Monge matrix can also be found in linear time by SMAWK algorithm.

Next, we show that the sequence transform (18) is equivalent to a Monge matrix search problem. Define

then we have

Lemma 2

Let A be defined as in (23). Then A is an inverse Monge matrix if \(p\ge 1\).

Proof: Let

To prove the inverse Monge property of A, it suffices to show \(\delta \ge 0\).

When \(i=j\), then \(\delta =2>0\). Now assume that \(i\not = j\) and let \(s\triangleq \vert i-j\vert \). Note that \(s\ge 1\). Then \(\delta =(s+1)^p+(s-1)^p-2s^p\). Now let \(t=\frac{1}{s}\) and \(\xi (t)=\delta /(s^c)=(1+t)^p+(1-t)^p-2\). Note that \(t\in (0,1]\) and \(\mathrm {sign}(\delta )=\mathrm {sign}(\xi )\). Consider the derivative of \(\xi (t)\)

Note that \(\xi (0)=0\) and \(\xi (t)\) is a non-decreasing function in [0, 1]. Therefore \(\xi (t) \ge 0\) for any \(t\in [0,1]\) and \(\delta \ge 0\). So A is an inverse Monge matrix.

   \(\square \)

Lemma 3

Let A be defined as in (23) except that all diagonals A(i, i) are defined as \(-\infty \). Then A is a Monge matrix.

Proof: Let

To prove the Monge property of A, it suffices to show that \(\delta \le 0\).

When \(i=j\), \(\delta <0\) since the diagonals are \(-\infty \). Now assume that \(i\not = j\) and let \(s\triangleq \vert i-j\vert \). Note that \(s\ge 1\). Then \(\delta =(s+1)^p+(s-1)^p-2s^p\). Now let \(t=\frac{1}{s}\) and \(\xi (t)=\delta /(s^p)=(1+t)^p+(1-t)^p-2\). Note that \(t\in (0,1]\) and \(\mathrm {sign}(\delta )=\mathrm {sign}(\xi )\). Consider the derivative of \(\xi (t)\)

Note that \(\xi (0)=0\) and, when \(p\in [0,1]\), \(\xi (t)\) is a non-increasing function in [0, 1]. Therefore \(\xi (t) \le 0\) for any \(t\in [0,1]\) and thus \(\delta \le 0\) which implies that A is a Monge matrix.

In summary, the 1D sequence transform problem is equivalent to a Monge matrix search problem which can be solved in linear time, and therefore concluding the proof of Theorem 1.

   \(\square \)

Reprints and permissions

© 2019 Springer Nature Switzerland AG

Policies and ethics