Home | About | Journals | Submit | Contact Us | Français |

**|**HHS Author Manuscripts**|**PMC2858241

Formats

Article sections

- Abstract
- 1 Introduction
- 2 Truncated Expansions in Cartesian and Polar Coordinates
- 3 Filtered Image
- 4 Interconversion between polar and Cartesian coordinates
- 5 Numerical Examples
- 6 Conclusions and Discussions
- References

Authors

Related links

IEEE Trans Image Process. Author manuscript; available in PMC 2010 April 21.

Published in final edited form as:

IEEE Trans Image Process. 2007 August; 16(8): 1946–1955.

PMCID: PMC2858241

NIHMSID: NIHMS182124

Department of Mechanical Engineering Johns Hopkins University

ude.uhj@7krapw ude.uhj@cgerg Telephone: +1-410-516-6451 Fax: +1-410-516-7254

See other articles in PMC that cite the published article.

In this paper we propose an algorithm for lossless conversion of data between Cartesian and polar coordinates, when the data is sampled from a two dimensional real-valued function (a mapping : ^{2} ) expressed as a particular kind of truncated expansion. We use Laguerre functions and the Fourier basis for the polar coordinate expression. Hermite functions are used for the Cartesian coordinate expression. A finite number of coefficients for the truncated expansion specifies the function in each coordinate system. We derive the relationship between the coefficients for the two coordinate systems. Based on this relationship, we propose an algorithm for lossless conversion between the two coordinate systems. Resampling can be used to evaluate a truncated expansion on the complementary coordinate system without computing a new set of coefficients. The resampled data is used to compute the new set of coefficients to avoid the numerical instability associated with direct conversion of the coefficients. In order to apply our algorithm to discrete image data, we propose a method to optimally fit a truncated expression to a given image. We also quantify the error that this filtering process can produce. Finally the algorithm is applied to solve the polar-Cartesian interpolation problem.

In two dimensional real space (^{2}), polar and Cartesian coordinates are very common and widely used. Many measurement devices such as ultrasound equipment and radar systems gather data in polar coordinates [8], [9]. On the other hand, since conventional display systems have a rectangular grid and corresponding mathematical expressions are more straightforward (e.g., the Euclidean distance between points is easy to compute and products of Fourier expansions follow naturally), Cartesian coordinates are widely used for image display and most mathematical manipulations. Therefore, in order to display data obtained from polar-coordinate-based transducers and deal with them using Cartesian-based mathematical tools, we need a concrete way of converting between polar and Cartesian coordinates. Of course, existing coordinate conversion techniques and interpolation methods have been suggested before, including: [5], [6], [9]. However, all of these techniques are approximate in nature, and so the conversion from polar to Cartesian and back (or Cartesian to polar and back) results in the destruction of some information. Existing methods are therefore not a lossless process. And if one restricts the discussion to Fourier expansions (i.e., Fourier series in Cartesian coordinates and Fourier-Hankel transform in polar coordinates) then there will never be an exact conversion. Even though one can reconstruct a bandlimited function to within a desired error bound using an optimal sampling window with Fourier-based analysis techniques [7], it is generally not possible to describe the same function as simultaneously bandlimited in both of these two classical bases ^{1}. The basis considered in this work is therefore special.

Conversion between polar and Cartesian coordinates is given as

$$(x,y)\iff (\rho ,\theta ),\phantom{\rule{1em}{0ex}}x=\rho \phantom{\rule{thinmathspace}{0ex}}\mathrm{cos}\phantom{\rule{thinmathspace}{0ex}}\theta ,\phantom{\rule{1em}{0ex}}y=\rho \phantom{\rule{thinmathspace}{0ex}}\mathrm{sin}\phantom{\rule{thinmathspace}{0ex}}\theta .$$

Using this relation, we can have two representations of a two dimensional real-valued function(mapping : ^{2} ) as

$${f}^{c}(x,y)={f}^{p}(\rho ,\theta ),$$

where the superscripts, (·)^{c} and (·)^{p} denote the representation in the Cartesian and polar coordinate systems, respectively. If the function is continuous, the conversion is very straightforward and has no ambiguity. However, if the function is defined on a discrete and equally spaced grid, the conversion can not be defined in the same way, because the two grid systems are not matched as shown in Fig.1. Therefore, when we display the data from a polar grid on a Cartesian grid, we have to perform interpolation computations to obtain data on the Cartesian grid using the data available on the polar grid. A similar problem can occur in tomographic reconstructions [4].

In Section 2 we investigate the truncated expansions of a two-dimensional function both in the Cartesian and polar coordinate systems. In Section 3 we show how to compute a set of coefficients that specifies the truncated expansion fit to given discrete data. The error in this filtering process is investigated. In Section 4 we show that the two sets of coefficients have a special relationship, with which we define the lossless coordinate conversion of a two dimensional function. In Section 5 we show how our algorithm works with numerical examples. Section 6 gives conclusions and discussions.

In this section we review Hermite and Laguerre functions, and how they are used to construct orthonormal expansions of functions over two-dimensional domains.

*Hermite polynomials* are well known in the literatures [12] [13], and are generated by the Rodrigues formula

$${H}_{n}\left(x\right)={(-1)}^{n}{e}^{{x}^{2}}\frac{{d}^{n}}{{\mathit{dx}}^{n}}\left({e}^{-{x}^{2}}\right).$$

The *Hermite functions* are defined as

$${h}_{n}\left(x\right)=\frac{1}{{2}^{n\u22152}\sqrt{n!\sqrt{\pi}}}{H}_{n}\left(x\right){e}^{-\frac{{x}^{2}}{2}}.$$

(1)

Note that the set {*h _{n}*(

$$\sqrt{n+1}{h}_{n+1}\left(x\right)=\sqrt{2}{\mathit{xh}}_{n}\left(x\right)-\sqrt{n}{h}_{n-1}\left(x\right).$$

This recurrence formula is very useful to evaluate the Hermite functions of high orders.

The set {*h _{n}*(

$$f\left(x\right)=\underset{n=0}{\overset{\infty}{\Sigma}}{\widehat{f}}_{n}{h}_{n}\left(x\right),$$

where

$${\widehat{f}}_{n}={\int}_{-\infty}^{\infty}f\left(x\right){h}_{n}\left(x\right)\mathit{dx}.$$

Approximately, a function can be expanded as a truncated Hermite series.

$$f\left(x\right)\approx \underset{n=0}{\overset{N}{\Sigma}}{\widehat{f}}_{n}{h}_{n}\left(x\right),$$

where *N* is a large nonnegative integer.

If the domain of a function is two-dimensional, we can employ the two-dimensional Hermite series.

$${f}^{c}(x,y)=\underset{m=0}{\overset{\infty}{\Sigma}}\underset{n=0}{\overset{\infty}{\Sigma}}{\widehat{f}}_{\mathit{mn}}{h}_{m}\left(x\right){h}_{n}\left(y\right),$$

where Hermite series coefficients are defined as

$${\widehat{f}}_{\mathit{mn}}={\int}_{-\infty}^{\infty}{\int}_{-\infty}^{\infty}{f}^{c}(x,y){h}_{m}\left(x\right){h}_{n}\left(y\right)\mathit{dxdy}.$$

(2)

Also we can use a truncated expansion of the form

$${f}^{c}(x,y)=\underset{m=0}{\overset{N}{\Sigma}}\underset{n=0}{\overset{N}{\Sigma}}{\widehat{f}}_{\mathit{mn}}{h}_{m}\left(x\right){h}_{n}\left(y\right),$$

(3)

where *N* is a large nonnegative integer. We will use the slightly different form as follows:

$${f}^{c}(x,y)=\underset{m=0}{\overset{N}{\Sigma}}\underset{n=0}{\overset{N-m}{\Sigma}}{\widehat{f}}_{\mathit{mn}}{h}_{m}\left(x\right){h}_{n}\left(y\right),$$

(4)

or equivalently,

$${f}^{c}(x,y)=\underset{m=0}{\overset{N}{\Sigma}}\underset{n=0}{\overset{m}{\Sigma}}{\widehat{f}}_{n,m-n}{h}_{n}\left(x\right){h}_{m-n}\left(y\right),$$

(5)

The reason why we use (4) or (5) instead of (3) will be explained in Section 4.

It should be noted that finite Hermite expansions have some drawbacks. For example, they do not preserve the truncation limit under shifts, while Fourier expansions do. Furthermore, since the Hermite functions decay exponentially outside of a bounded region, it is important to center the image of interest within this region to obtain the highest resolution for a given truncation. Despite these shortcomings, the Hermite function expansions are superior for Cartesian-polar coordinate conversions for the reasons shown in the rest of the paper.

The *associated Laguerre polynomials* are also well known and given by the Rodrigues formula,

$${L}_{n}^{k}\left(x\right)=\frac{{e}^{x}{x}^{-k}}{n!}\frac{{d}^{n}}{{\mathit{dx}}^{n}}\left({e}^{-x}{x}^{n+k}\right).$$

The associated Laguerre polynomials are orthogonal over [0, ∞) with respect to the weighting function *x ^{k}e*

$${\int}_{0}^{\infty}{x}^{k}{e}^{-x}{L}_{m}^{k}\left(x\right){L}_{n}^{k}\left(x\right)\mathit{dx}=\frac{(n+k)!}{n!}{\delta}_{m,n}.$$

On the other hand, the *Fourier series* expansion of a one dimensional function with period 2*π* is defined as:

$$f\left(x\right)=\frac{1}{\sqrt{2\pi}}\underset{k=-\infty}{\overset{+\infty}{\Sigma}}\widehat{f}\left(k\right){e}^{\mathit{ikx}},$$

where

$$\widehat{f}\left(n\right)=\frac{1}{\sqrt{2\pi}}{\int}_{0}^{2\pi}f\left(x\right){e}^{-\mathit{inx}}\mathit{dx}.$$

Using the Laguerre polynomials and the Fourier basis, one can define orthonormal basis functions in two-dimensional polar coordinates as follows [1].

$${\chi}_{m,n}(\rho ,\theta )={(-1)}^{(m-\left|n\right|)\u22152}\sqrt{\frac{[(m-\left|n\right|)\u22152]!}{\pi [(m+\left|n\right|)\u22152]!}}{\rho}^{\left|n\right|}{L}_{(m-\left|n\right|)\u22152}^{\left|n\right|}\left({\rho}^{2}\right){e}^{-{\rho}^{2}\u22152}{e}^{-\mathit{in}\theta},$$

(6)

where (*m* − |*n*|) and (*m* + |*n*|) are even numbers. If we define *Y _{mn}*(

$${Y}_{\mathit{mn}}\left(\rho \right)={(-1)}^{(m-\left|n\right|)\u22152}\sqrt{\frac{2[(m-\left|n\right|)\u22152]!}{[(m+\left|n\right|)\u22152]!}}{\rho}^{\left|n\right|}{L}_{(m-\left|n\right|)\u22152}^{\left|n\right|}\left({\rho}^{2}\right){e}^{-{\rho}^{2}\u22152},$$

$${Z}_{n}\left(\theta \right)=\frac{1}{\sqrt{2\pi}}{e}^{-\mathit{in}\theta},$$

then *χ _{m,n}*(

$${\chi}_{m,n}(\rho ,\theta )={Y}_{\mathit{mn}}\left(\rho \right){Z}_{n}\left(\theta \right).$$

A two-dimensional function in polar coordinates can be expressed as

$${f}^{p}(\rho ,\theta )=\underset{m=0}{\overset{\infty}{\Sigma}}\underset{n=-m}{\overset{m}{\Sigma}}{\stackrel{~}{f}}_{m,n}{\chi}_{m,n}^{\ast}(\rho ,\theta ),$$

(7)

where the Laguerre-Fourier coefficients are

$${\stackrel{~}{f}}_{m,n}={\int}_{0}^{2\pi}{\int}_{0}^{\infty}{f}^{p}(\rho ,\theta ){\chi}_{m,n}(\rho ,\theta )\rho d\rho d\theta ,$$

(8)

and *χ** is the complex conjugate of *χ*. Note that the integer variable *n* in (7) increases by multiples of 2. A truncated expansion can be written in the form

$${f}^{p}(\rho ,\theta )=\underset{m=0}{\overset{M}{\Sigma}}\underset{n=-m}{\overset{m}{\Sigma}}{\stackrel{~}{f}}_{m,n}{\chi}_{m,n}^{\ast}(\rho ,\theta ),$$

(9)

where *M* is a positive large integer.

One of the major contributions of this paper is to establish the equivalence of (4) and (9), and to find how *N* and *M* and * _{mn}* and

When data is obtained from discrete images, we can not directly apply (2) and (8) to this data to get the truncated expansion. In this section, we propose a way to obtain truncated expansions corresponding to a discrete image. Sampling of these expansions defines a filtering^{2} of the original image. We investigate the difference between the original image and its truncated (filtered) version. Of course, for this to be a filter, the number of coefficients must be less than or equal to the number of values specified on the grid. Otherwise, no information (or noise) would be rejected from the original image, and the excess degrees of freedom would need to be constrained in some way, since they would not be determined by the original image. A filtering method using Hermite expansions in the Cartesian coordinates is presented in the manuscript [14]. A brief summary of results are presented here without derivation. A detailed filtering method using Laguerre-Fourier expansions in polar coordinates will be presented.

* _{xy}* is a given

$$f(x,y)=\underset{m=0}{\overset{N}{\Sigma}}\underset{n=0}{\overset{N-m}{\Sigma}}{\widehat{f}}_{\mathit{mn}}{h}_{m}\left(x\right){h}_{n}\left(y\right),$$

where _{m−1,n−1} is the (*i, j*) element of the matrix, and given by

$$\widehat{F}={\left({H}^{T}H\right)}^{-1}{H}^{T}{\stackrel{-}{F}}_{\mathit{xy}}H{\left({H}^{T}H\right)}^{-1},$$

where *H _{i,j}* =

The matrix *H* depends on the truncation limit *N* and a series of *x _{i}*. For a given

$${x}_{i}=-R+2R(i-1)\u2215(M-1),$$

where *R* is the range of *x _{i}* and

Contour plot of logarithm of condition number of *H*^{T}H depending on truncation limit and range of *x*_{i} (*M* = 301)

Choice of the range of *x _{i}* is related to the effect of scaling factor in Hermite transform. Basically the Hermite transforms of the similar functions

Fig.3 shows a 301×301 brain scanning image and corresponding Hermite-filtered image with the truncation limit, 240. The normalized error between the original and the filtered version is 5.0%. For the truncation limits, 150 and 200, the errors are 10.2% and 6.9% (The images are not shown), respectively. The normalized error is defined as *I* − *I _{F}*/

Original and Hermite-filtered images. Original image from http://www.med.univ-angers.fr/discipline/radiologie/Intlatlas/t1ax11.html

As in Cartesian coordinates, for a given array of *M _{ρ}* ×

$$C=\underset{p=1}{\overset{{M}_{\rho}}{\Sigma}}\underset{q=1}{\overset{{M}_{\theta}}{\Sigma}}{|{\stackrel{-}{f}}^{p}({\rho}_{p},{\theta}_{q})-\underset{m=0}{\overset{N}{\Sigma}}\underset{n=-m}{\overset{m}{\Sigma}}{\stackrel{~}{f}}_{m,n}{\chi}_{m,n}^{\ast}({\rho}_{p},{\theta}_{q})|}^{2}{\rho}_{p}.$$

For a fixed *ρ _{p}*, we consider the two functions.

$$g\left({\theta}_{k}\right)={\stackrel{-}{f}}^{p}({\rho}_{p},{\theta}_{k}),$$

$$h\left({\theta}_{k}\right)=\underset{m=0}{\overset{N}{\Sigma}}\underset{n=-m}{\overset{m}{\Sigma}}{\stackrel{~}{f}}_{m,n}{\chi}_{m,n}^{\ast}({\rho}_{p},{\theta}_{k})=\underset{m=0}{\overset{N}{\Sigma}}\underset{n=-m}{\overset{m}{\Sigma}}{\stackrel{~}{f}}_{m,n}{Y}_{m,n}\left({\rho}_{p}\right){Z}_{n}^{\ast}\left({\theta}_{k}\right)$$

where *k* = 1, 2, …, *M _{θ}*. When the two functions are defined on an equally spaced grid on a circle, Parseval's equality for the discrete Fourier transform (DFT) tells us

$$\underset{k=1}{\overset{{M}_{\theta}}{\Sigma}}{|g\left({\theta}_{k}\right)-h\left({\theta}_{k}\right)|}^{2}=\frac{1}{{M}_{\theta}}\underset{l=0}{\overset{{M}_{\theta}-1}{\Sigma}}{|\mathcal{F}{\left(g\right)}_{l}-\mathcal{F}{\left(h\right)}_{l}|}^{2},$$

where the DFT is defined as

$$\mathcal{F}{\left(g\right)}_{l}=\underset{j=0}{\overset{{M}_{\theta}-1}{\Sigma}}g\left({\theta}_{j}\right){e}^{-2\pi \mathit{ijl}\u2215{M}_{\theta}}.$$

The DFT of ${Z}_{n}^{\ast}\left({\theta}_{k}\right)$ gives

$$\mathcal{F}{\left({Z}_{n}^{\ast}\left({\theta}_{k}\right)\right)}_{l}=\underset{j=0}{\overset{{M}_{\theta}-1}{\Sigma}}{Z}_{n}^{\ast}\left({\theta}_{j}\right){e}^{-2\pi \mathit{ijl}\u2215{M}_{\theta}}=\frac{1}{\sqrt{2\pi}}\underset{j=0}{\overset{{M}_{\theta}-1}{\Sigma}}{e}^{2\pi \mathit{ij}(n-l)\u2215{M}_{\theta}}=\frac{{M}_{\theta}}{\sqrt{2\pi}}{\delta}_{l,n}.$$

With these relations, the cost function can be rewritten as

$$C=S\underset{p=1}{\overset{{M}_{\rho}}{\Sigma}}\underset{l=0}{\overset{{M}_{\theta}-1}{\Sigma}}{|\mathcal{F}{\left({\stackrel{-}{f}}^{p}\left({\rho}_{p}\right)\right)}_{l}-\frac{{M}_{\theta}}{\sqrt{2\pi}}\underset{m=0}{\overset{N}{\Sigma}}\underset{n=-m}{\overset{m}{\Sigma}}{\stackrel{~}{f}}_{m,n}{Y}_{m,n}\left({\rho}_{p}\right){\delta}_{l,n}|}^{2}{\rho}_{p},$$

where *S* is a constant, which is not important in minimizing the cost function. Changing the order of summations gives

$$C=S\underset{l=0}{\overset{{M}_{\theta}-1}{\Sigma}}\underset{p=1}{\overset{{M}_{\rho}}{\Sigma}}{|\mathcal{F}{\left({\stackrel{-}{f}}^{p}\left({\rho}_{p}\right)\right)}_{l}\sqrt{{\rho}_{p}}-\frac{{M}_{\theta}}{\sqrt{2\pi}}\underset{n=-N}{\overset{N}{\Sigma}}\underset{m=\left|n\right|}{\overset{N}{\Sigma}}{\stackrel{~}{f}}_{m,n}{Y}_{m,n}\left({\rho}_{p}\right)\sqrt{{\rho}_{p}}{\delta}_{l,n}|}^{2}.$$

Note that in the fourth summation, the variable, *m* is increasing by multiples of 2. For the filtering to be possible, the number of sample data should be greater than or equal to the number of coefficients, which means *M _{θ}* ≥

$$\begin{array}{c}\hfill C=S\underset{l=0}{\overset{N}{\Sigma}}\underset{p=1}{\overset{{M}_{\rho}}{\Sigma}}{|\mathcal{F}{\left({\stackrel{-}{f}}^{p}\left({\rho}_{p}\right)\right)}_{l}\sqrt{{\rho}_{p}}-\frac{{M}_{\theta}}{\sqrt{2\pi}}\underset{n=0}{\overset{N}{\Sigma}}\underset{m=\left|n\right|}{\overset{N}{\Sigma}}{\stackrel{~}{f}}_{m,n}{Y}_{m,n}\left({\rho}_{p}\right)\sqrt{{\rho}_{p}}{\delta}_{l,n}|}^{2}\hfill \\ \hfill +S\underset{l=N+1}{\overset{{M}_{\theta}-1}{\Sigma}}\underset{p=1}{\overset{{M}_{\rho}}{\Sigma}}{\left|\mathcal{F}{\left({\stackrel{-}{f}}^{p}\left({\rho}_{p}\right)\right)}_{l}\sqrt{{\rho}_{p}}\right|}^{2}.\hfill \end{array}$$

Since the second term is constant, the first term is all that is of interest when performing minimization. The new cost function is

$$C=\underset{l=0}{\overset{N}{\Sigma}}\underset{p=1}{\overset{{M}_{\rho}}{\Sigma}}{|\mathcal{F}{\left({\stackrel{-}{f}}^{p}\left({\rho}_{p}\right)\right)}_{l}\sqrt{{\rho}_{p}}-\frac{{M}_{\theta}}{\sqrt{2\pi}}\underset{m=l}{\overset{N}{\Sigma}}{\stackrel{~}{f}}_{m,l}{Y}_{m,l}\left({\rho}_{p}\right)\sqrt{{\rho}_{p}}|}^{2}.$$

(10)

For a fixed *l*, let us define the following two vectors and a matrix.

$$\begin{array}{c}\hfill {b}_{l}={\left[\mathcal{F}{\left({\stackrel{-}{f}}^{p}\left({\rho}_{1}\right)\right)}_{l}\sqrt{{\rho}_{1}}\phantom{\rule{1em}{0ex}}\mathcal{F}{\left({\stackrel{-}{f}}^{p}\left({\rho}_{2}\right)\right)}_{l}\sqrt{{\rho}_{2}}\phantom{\rule{1em}{0ex}}\cdots \phantom{\rule{1em}{0ex}}\mathcal{F}{\left({\stackrel{-}{f}}^{p}\left({\rho}_{{M}_{\rho}}\right)\right)}_{l}\sqrt{{\rho}_{{M}_{\rho}}}\right]}^{T}\hfill \\ \hfill {x}_{l}={\left[{\stackrel{~}{f}}_{l,l}\phantom{\rule{1em}{0ex}}{\stackrel{~}{f}}_{l+2,l}\phantom{\rule{1em}{0ex}}\cdots \phantom{\rule{1em}{0ex}}{\stackrel{~}{f}}_{2[(N-1)\u22152]+l,l}\right]}^{T},\hfill \end{array}$$

and

$${A}_{l}=\frac{{M}_{\theta}}{\sqrt{2\pi}}\left(\begin{array}{ccc}\hfill \sqrt{{\rho}_{1}}{Y}_{l,l}\left({\rho}_{1}\right)\hfill & \hfill \sqrt{{\rho}_{1}}{Y}_{l+2,l}\left({\rho}_{1}\right)\hfill & \hfill \vdots \hfill \\ \hfill \sqrt{{\rho}_{2}}{Y}_{l,l}\left({\rho}_{2}\right)\hfill & \hfill \ddots \hfill & \hfill \vdots \hfill \\ \hfill \cdots \hfill & \hfill \cdots \hfill & \hfill \sqrt{{\rho}_{{M}_{\rho}}}{Y}_{2[(N-l)\u22152]+l,l}\left({\rho}_{{M}_{\rho}}\right)\hfill \end{array}\right),$$

where [*n*/2] = *n*/2 if *n* is even and [*n*/2] = (*n* − 1)/2 if *n* is odd. The cost function is

$$C=\underset{l=0}{\overset{N}{\Sigma}}{\parallel {b}_{l}-{A}_{l}{x}_{l}\parallel}^{2}.$$

Even though *b _{l}* and

$${x}_{l}={\left({A}_{l}^{T}{A}_{l}\right)}^{-1}{A}_{l}^{T}{b}_{l}.$$

The matrix *A _{l}* is determined by the truncation limit and the range of

Contour plot of logarithm of condition number of *A*_{0} depending on truncation limit and range of *ρ* (*M*_{ρ} = 151)

In this section we find the relationship between the representations of a function in polar and Cartesian coordinates when the truncated expansions in (5) and (9) are used. Furthermore, we relate the truncation limits, *N* and *M*, so that there is no loss of information during conversion.

The Laguerre polynomials and the Fourier basis can be written in terms of the Hermite polynomials as follows [2].

$${e}^{\mathit{im}\theta}{\rho}^{m}{L}_{n}^{m}\left({\rho}^{2}\right)=\frac{{(-1)}^{n}}{{2}^{2n+m}n!}\underset{r=0}{\overset{n}{\Sigma}}\underset{s=0}{\overset{m}{\Sigma}}{i}^{s}{C}_{n}^{r}{C}_{m}^{s}{H}_{2r+m-s}\left(x\right){H}_{2n-2r+s}\left(y\right),$$

(11)

where $\rho =\sqrt{{x}^{2}+{y}^{2}}$ and *θ* = atan(*x, y*). The function atan(*x, y*) returns the four-quadrant inverse tangent, which is the angle between the vectors (*x, y*)^{T} and (1, 0)^{T}.

Using (1), (6) and (11), we can express *χ _{mn}*(

$$\begin{array}{c}\hfill {\chi}_{\mathit{mn}}(\rho ,\theta )=\underset{r=0}{\overset{(m+n)\u22152}{\Sigma}}\underset{s=0}{\overset{-n}{\Sigma}}{i}^{s}\sqrt{\frac{(2r-n-s)!(m+n-2r+s)!}{{2}^{m}\left(\frac{m-n}{2}\right)!\left(\frac{m+n}{2}\right)!}}\hfill \\ \hfill \times {C}_{\frac{m+n}{2}}^{r}{C}_{-n}^{s}{h}_{2r-n-s}\left(x\right){h}_{m+n-2r+s}\left(y\right),\hfill \end{array}$$

where *n* ≤ 0, *x* = *ρ* cos *θ* and *y* = *ρ* sin *θ*. If we use a new variable, *α* = 2*r* − *n* − *s*, then the double sum is ${\Sigma}_{r=0}^{(m+n)\u22152}{\Sigma}_{\alpha =2r}^{2r-n}$. If we define the combination symbols to be zero when they can not be defined (e.g. ${C}_{2}^{-1},{C}_{3}^{4}=0$), we can extend the limits of the summations as ${\Sigma}_{r=0}^{[m\u22152]}{\Sigma}_{\alpha =2r}^{m}$, where [*m*/2] = *m*/2 if *m* is even and [*m*/2] = (*m* − 1)/2 if *m* is odd. PFinally we change the order of summations to get

$$\begin{array}{c}\hfill {\chi}_{\mathit{mn}}(\rho ,\theta )=\underset{\alpha =0}{\overset{m}{\Sigma}}\sqrt{\frac{\alpha !(m-\alpha )!}{{2}^{m}\left(\frac{m-n}{2}\right)!\left(\frac{m+n}{2}\right)!}}\left[\underset{r=0}{\overset{[\alpha \u22152]}{\Sigma}}{i}^{2r-n-\alpha}{c}_{(m+n)\u22152}^{r}{C}_{-n}^{2r-n-\alpha}\right]\hfill \\ \hfill \times {h}_{\alpha}\left(x\right){h}_{m-\alpha}\left(y\right).\hfill \end{array}$$

For *n* > 0, we use the fact that ${\chi}_{m,n}={\chi}_{m,-n}^{\ast}$. Substituting this *χ _{mn}* and (5) in (8) gives

$${\stackrel{~}{f}}_{p,q}=\underset{n=0}{\overset{p}{\Sigma}}{G}_{n}(p,q){\widehat{f}}_{n,p-n},$$

(12)

where

$${G}_{n}(p,q)=\{\begin{array}{cc}\hfill \sqrt{\frac{n!(p-n)!}{{2}^{p}\left(\frac{p+q}{2}\right)!\left(\frac{p-q}{2}\right)!}}{\Sigma}_{r=0}^{[n\u22152]}{C}_{\frac{p+q}{2}}^{r}{C}_{-q}^{n-2r}{i}^{2r-q-n}\hfill & \hfill \text{if}\phantom{\rule{thinmathspace}{0ex}}q\le 0,\hfill \\ \hfill \sqrt{\frac{n!(p-n)!}{{2}^{p}\left(\frac{p+q}{2}\right)!\left(\frac{p-q}{2}\right)!}}{\Sigma}_{r=0}^{[n\u22152]}{C}_{\frac{p-q}{2}}^{r}{C}_{q}^{n-2r}{(-i)}^{2r+q-n}\hfill & \hfill \text{if}\phantom{\rule{thinmathspace}{0ex}}q>0\hfill \end{array}\phantom{\}}.$$

A similar equation has been shown in [1]. However, (12) specifically tells us how we can compute the Laguerre-Fourier coefficients using the Hermite coefficients. This equation also contains some other important properties, as described below.

First, the Laguerre-Fourier coefficients () can be computed by linear combination of the Hermite coefficients (). Secondly, * _{p,q}* is determined only by a set {

$${f}^{p}(\rho ,\theta )=\underset{p=0}{\overset{N}{\Sigma}}\underset{q=-p}{\overset{p}{\Sigma}}{\stackrel{~}{f}}_{p,q}{\chi}_{p,q}^{\ast}(\rho ,\theta ).$$

Note that this is directly derived from (5) without approximation. Comparing this to (9), we come to know that the truncation limits in (5) and (9), *N* and *M* should be equal in order for there to be no loss during conversion.

The Hermite polynomials can be written in terms of the Laguerre polynomials and the Fourier basis as follows [2].

$$\begin{array}{c}\hfill {H}_{l}\left(x\right){H}_{k-l}\left(y\right)=\mathit{Re}({(-i)}^{k-l}\underset{r=0}{\overset{l}{\Sigma}}\underset{s=0}{\overset{k-l}{\Sigma}}{(-1)}^{r}{C}_{l}^{r}{C}_{k-l}^{s}(r+s)!{e}^{i(k-2r-2s)\theta}{\rho}^{(k-2r-2s)}\hfill \\ \hfill \times {L}_{r+s}^{k-2r-2s}\left({\rho}^{2}\right)),\hfill \end{array}$$

(13)

where ${C}_{n}^{k}=n!\u2215(k!(n-k)!)$, *x* = *ρ* cos *θ*, *y* = *ρ* sin *θ* and *Re*(*c*) gives a real part of a complex number, *c*. To evaluate the associate Laguerre polynomial, ${L}_{m}^{n}$ for *n* < 0, we use the formula [2]

$$m!{\rho}^{n}{L}_{m}^{n}\left({\rho}^{2}\right)={(-1)}^{n}(m+n)!{\rho}^{-n}{L}_{m+n}^{-n}\left({\rho}^{2}\right).$$

(14)

Depending on *r* and *s* in (13), the superscript of the Laguerre polynomial may be positive or negative. Using (14), one can rewrite (13) with only positive superscript of Laguerre polynomials. Then, applying (1) and (6) to the new version of (13), we can express the Hermite coefficients in terms of the Laguerre-Fourier coefficients as

$${\widehat{f}}_{l,k-1}=\mathit{Re}\left\{\underset{j=0}{\overset{k}{\Sigma}}{D}_{j}(l,k-l){\stackrel{~}{f}}_{k,2j-k}\right\},$$

(15)

where

$${D}_{j}(l,k-l)=\underset{r=0}{\overset{l}{\Sigma}}{(-1)}^{j-r}{(-i)}^{k-l}{C}_{l}^{r}{C}_{k-l}^{j-r}\sqrt{\frac{(k-j)!j!}{{2}^{k}l!(k-l)!}}.$$

This relationship is also linear and localized. In addition, the truncation limits, *N* and *M* should be equal for lossless conversion.

Now we can conclude that the following two expressions are equivalent.

$${f}^{p}(\rho ,\theta )=\underset{p=0}{\overset{N}{\Sigma}}\underset{q=-p}{\overset{p}{\Sigma}}{\stackrel{~}{f}}_{p,q}{\chi}_{p,q}^{\ast}(\rho ,\theta )\iff {f}^{c}(x,y)=\underset{m=0}{\overset{N}{\Sigma}}\underset{n=0}{\overset{m}{\Sigma}}{\widehat{f}}_{n,m-n}{h}_{n}\left(x\right){h}_{m-n}\left(y\right),$$

(16)

where *x* = *ρ* cos *θ* and *y* = *ρ* sin *θ*, and the constraints described below are in effect.

Since *f* is a real-valued function, in the Cartesian coordinate expression there are $\frac{(N+1)(N+2)}{2}$ coefficients that are real numbers. On the other hand, since *n* is increasing by 2 in the polar coordinate expression, there are $\frac{(N+1)(N+2)}{2}$ coefficients that are complex numbers, which means there are (*N* + 1)(*N* + 2) independent real numbers. However, since _{p,0} is a real number and ${\stackrel{~}{f}}_{p,q}={\stackrel{~}{f}}_{p,-q}^{\ast}$, there are exactly $\frac{(N+1)(N+2)}{2}$ independent real numbers in both expressions.

As shown in (16), once we have a truncated expansion in either of the two coordinate systems, we can easily evaluate the function on the complementary grid. This can be rewritten as

$${f}^{p}(\rho ,\theta )={f}^{c}(\rho \phantom{\rule{thinmathspace}{0ex}}\mathrm{cos}\phantom{\rule{thinmathspace}{0ex}}\theta ,\rho \phantom{\rule{thinmathspace}{0ex}}\mathrm{sin}\phantom{\rule{thinmathspace}{0ex}}\theta )=\underset{m=0}{\overset{N}{\Sigma}}\underset{n=0}{\overset{m}{\Sigma}}{\widehat{f}}_{n,m-n}{h}_{n}\left(\rho \phantom{\rule{thinmathspace}{0ex}}\mathrm{cos}\phantom{\rule{thinmathspace}{0ex}}\theta \right){h}_{m-n}\left(\rho \phantom{\rule{thinmathspace}{0ex}}\mathrm{sin}\phantom{\rule{thinmathspace}{0ex}}\theta \right),$$

(17)

$${f}^{c}(x,y)={f}^{p}(\sqrt{{x}^{2}+{y}^{2}},\mathrm{atan}(x,y))=\underset{p=0}{\overset{N}{\Sigma}}\underset{q=-p}{\overset{p}{\Sigma}}{\stackrel{~}{f}}_{p,q}{\chi}_{p,q}^{\ast}(\sqrt{{x}^{2}+{y}^{2}},\mathrm{atan}(x,y)).$$

(18)

Suppose filtered data is provided on one coordinate grid (i.e., polar or Cartesian). Evaluation on the complementary coordinate grid is possible without using the truncated expansion associated with the complementary grid by simply resampling when the expansions in (16) are equivalent. It is important to realize that the justification for doing this is the lossless interconversion between these expansions when the compatible truncation limits are enforced via filtering. In other words, the mathematical invertibility of (12) and (15) in exact arithmetic is what justifies resampling.

In principle, given a truncated expansion in one coordinate system, we can find the complementary expansion by implementing (12) or (15). However, in practice there may be an obstacle in computing them. The factorials and the combinations $\left({C}_{n}^{m}\right)$ for large arguments introduce some numerical error during computation. To overcome this, we use a resampling technique. Given a set of , we sample appropriate points of *f ^{p}*(

Fig.7(a) shows how we perform the interconversion for a given image initially defined on a Cartesian coordinate grid. For the image on a rectangular grid, we compute the Hermite coefficients using the filtering process suggested in Section 3.1. The truncated Hermite expansion gives the filtered image as shown in Fig. 3. Then we evaluate the Hermite expansion on the polar grid. Since we know that the sampled values are sample values of a truncated expansion on the polar grid, we can compute the exact coefficients of the truncated Laguerre-Fourier expansion using the method in Section 3.2. If we again evaluate the truncated Laguerre-Fourier expansion on a Cartesian coordinate grid, the image is the same (to within machine precision) as the original Hermite filtered image. The double arrows in Fig. 7 indicate that the process is reversible. Fig. 8(a) is resampled data on polar grid using the truncated Hermite expansion. We compute the exact Laguerre-Fourier coefficients using this resampled data. Again, if we resampled data on Cartesian grid using the truncated Laguerre-Fourier expansion, we have the resulting image shown in Fig. 8(b), which is the same as the filtered image of Fig. 3(b). The normalized error between the two is 3.5 × 10^{−14}, which illustrates the lossless interconversion when the filtering process in Cartesian coordinates is applied.

Images from interconversion with data on Cartesian grid. (a) Reconstructed data on polar grid with Hermite expansion (b) Reconstructed data on Cartesian grid with Laguerre-Fourier expansion

Similarly, Fig.7(b) shows the interconversion for a given image on a polar coordinate grid. For the image on the polar grid, we compute the Laguerre-Fourier coefficients using the filtering process. Fig. 9(a) is resampled data on a Cartesian grid using the truncated Laguerre-Fourier expansion. We compute the exact Hermite coefficients using this resampled data. When we resampled data on a polar grid using the truncated Hermite expansion, the resulting image shown in Fig. 9(b) is the same as the filtered image of Fig. 6(d). The normalized error between the two is 3.3 × 10^{−14}, which illustrates the lossless interconversion when filtering in polar coordinates is applied.

Images from interconversion with data on polar grid. (a) Reconstructed data on Cartesian grid with Laguerre-Fourier expansion (b) Reconstructed data on polar grid with Hermite expansion

As we mentioned earlier, the data obtained from a transducer or sensor in polar coordinates often needs to be displayed on a Cartesian coordinate grid. Since equally spaced grids in the two coordinate systems do not match as shown in Fig.1, one needs to compute a new set of data that fit on a Cartesian grid. Displaying the data from the polar grid on the Cartesian grid directly introduces two problems. First, it is hard to determine where to assign data at (*r*, *θ*) on the Cartesian grid. The data may be assigned to (*r* cos *θ*, *r* sin *θ*) on the Cartesian grid, but the equally spaced Cartesian grid can not capture (*r* cos *θ*, *r* sin *θ*) completely. Secondly, even if one assigned the data to the approximate position, there can be some vacant pixels in areas far from the origin as shown in Fig. 10(a). And while local interpolation methods exist (e.g., bivariate linear), these use only local features and are not reversible.

With data provided on a polar coordinate grid, we compute the Laguerre-Fourier coefficients by the filtering process. Evaluating the truncated Laguerre-Fourier expansion onto a Cartesian coordinate grid gives the interpolated image as shown in Fig. 10(b). Since the interpolated image can also be viewed as being sampled from a truncated Hermite expansion, we then can apply existing image processing methods associated with the Hermite transform [10] [11].

In the strict meaning of interpolation, our algorithm has a drawback in that the filtering process introduces some error with respect to the original image, and that error persists through the coordinate conversion process. However, we show that the error can be controlled at the expense of the truncation limit and the actual error does not leave critical artifacts on the image as shown in Fig. 3 and Fig. 6. Furthermore, our algorithm also suggests a filtering method for images that enables us to convert the images between polar and Cartesian coordinates without loss.

In this paper we have proposed a new method of interconverting images between polar and Cartesian coordinate systems without loss of information after the filtering process. We defined the filtering process and assessed the error that the filter can produce. Using truncated expansions, we investigated the relationship between the two representations of a function in polar and Cartesian coordinates. Some special functions such as the Laguerre polynomials, the Fourier basis and the Hermite functions were used.

Conversion between the coordinates systems boiled down to conversion of the coefficients of the two truncated expansions on the polar and Cartesian coordinates. We found that the two sets of coefficients are linearly and locally related. From the equation expressing the relationship, we uncovered a special truncation limit for the two expansions, which guarantees lossless conversion.

Based on the equivalence of the two truncated expansions in polar and Cartesian coordinates, we could get an image on a new coordinate system by resampling the points from the truncated expansion on the original coordinate system. Additionally, we showed that this technique can be applied to the interpolation problem. With the filtered image on the polar grid, we could obtain an image on a Cartesian grid without losing any information or having missing pixels by using a resampling technique.

In our expansions, an image (and its extension to values all over ^{2}) is defined by (*N*^{2}) coefficients. The Hermite filtering process is of (*N*^{3}), because we invert a *N* × *N* matrix. Resampling the Hermite expansion on polar coordinates is of (*N*^{4}), while (*N*^{3}) computations are required in resampling it onto Cartesian coordinates. The Laguerre-Fourier filtering process is of (*N*^{4}), since we invert a *N* × *N* matrix *N* times. Note that we invert the matrices regardless of Fourier transform. Even when employing the fast Fourier transform, minimizing (10) still needs (*N*^{4}). Resampling the Laguerre-Fourier expansion on the polar and Cartesian coordinates needs (*N*^{3}) and (*N*^{4}), respectively. Therefore, the total complexity of interconversion is (*N*^{4}). If the constants in (12) and (15) are precalculated, the direct conversion of those coefficients is of (*N*^{3}). However, the direct computation introduces numerical error as explained in Section 4.3. Even though it is possible, the complexity of the whole interconversion process does not change because the sampling process on the complementary grid needs (*N*^{4}) computations. There presently are not fast algorithms for the Hermite-function and Laguerre-Fourier transforms. This is an active area of research, and as the situation changes, our algorithm may become faster.

Finally, we showed how we can use our algorithm to interpolate an image on the polar grid and have an interpolated image on the Cartesian coordinates. If the original image is filtered in the way we suggested in this paper, the interpolated image does not lose information of the original filtered image. Therefore, we also propose a new filtering process that enables the interpolation between the polar and Cartesian coordinate systems.

This work was performed with support from the National Institutes for Health under grant R01GM075310, and the NSF-Funded JHU Center for Computer-Integrated Surgical Systems and Technology

^{1}The term ‘band limited’ is used commonly to denote truncated Fourier expansions, but can also be used more generally to describe truncated expansions in any orthogonal basis. Generally, a truncated expansion in one basis will not be truncated in another. In order to avoid any confusion, we use the word ‘truncated’ in the context of Hermite/Laguerre-Fourier expansions, since these are generally not band limited in the Fourier sense.

^{2}Since this filter is not shift-invariant, it is not a general filter used in Fourier-based image processing. However, we call it a filter in the sense that it performs as a low-pass filter in the Hermite expansion.

1. Massey Richard, Refregier Alexandre. Polar shapelets. Mon. Not. R. Astron. Soc. 2005;363:197–210.

2. Kimel Isidoro, Elias Luis R. Relations between Hermite and Laguerre Gaussian modes. IEEE Journal of quantum electronics. 1993 September;29(9):2562–2567.

3. Refregier Alexandre. Shapelets: I. A method for image analysis. Mon. Not. R. Astron. Soc. 2003;338:35–47.

4. Chen Zikuan, Ning Ruola. Filling the Radon domain in computed tomography by local convex combination. Applied Optics. 2003 December;42(35) [PubMed]

5. Basoglu Chris, Kim Yongmin, Chalana Vikram. A Real-time scan conversion algorithm on commercially available microprocessors. Ultrasonic Imaging. 1996 October;18(4):241–260. [PubMed]

6. Berkhoff AP, Huisman HJ, Thijssen JM, Jacobs EMGP, Homan RJF. Fast scan conversion algorithms for displaying ultrasound sector images. Ultrasonic Imaging. 1994;16(2):87–108. [PubMed]

7. Knab John J. The sampling window. IEEE Transactions on Information Theory. 1983;29(1):157–159.

8. Chang Dah-Chung, Wu Wen-Rong, Jeng Jianbn-Hwa. An efficient architecture of ultrasonic scan conversion forimplementing the cubic convolution interpolation. Nuclear Science Symposium, IEEE. 1997 November;2:1546–1550.

9. Julier Simon J., Uhimaun Jeffrey K. A Consistent, Debiased Method for converting between polar and Cartesian coordinate systems. Proc. SPIE. 1997;3086:110–121.

10. van Dijk Antoon M., Martens Jean-Bernard. Feature-based image compression with steered hermite transforms. Proceedings, International Conference on Image Processing, IEEE. 1996 September;1:205–208.

11. Martens Jean-Bernard. Local orientation analysis in images by means of the hermite transform. IEEE Transactions on Image Processing. 1997;6(8):1103–1116. [PubMed]

12. Chirikjian GS, Kyatkin AB. Engineering Applications of Noncom-mutative Harmonic Analysis. CRC Press; Boca Raton, FL: 2001.

13. Vilenkin NJ, Klimyk AU. Representation of Lie Groups and Special Functions. 1-3. Kluwer Academic Publ.; Dordrecht, Holland: 1991.

14. Park W, Chirikjian GS. Lossless rotation of Hermite-filtered images. IEEE Transactions on Image Processing. submitted.

PubMed Central Canada is a service of the Canadian Institutes of Health Research (CIHR) working in partnership with the National Research Council's national science library in cooperation with the National Center for Biotechnology Information at the U.S. National Library of Medicine(NCBI/NLM). It includes content provided to the PubMed Central International archive by participating publishers. |