PMCCPMCCPMCC

Search tips
Search criteria 

Advanced

 
Logo of nihpaAbout Author manuscriptsSubmit a manuscriptHHS Public Access; Author Manuscript; Accepted for publication in peer reviewed journal;
 
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

Interconversion between Truncated Cartesian and Polar Expansions of Images

Abstract

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 : R2 [mapsto] R) 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.

Keywords: Coordinate conversion, Image processing, truncated expansions, Interpolation

1 Introduction

In two dimensional real space (R2), 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)(ρ,θ),x=ρcosθ,y=ρsinθ.

Using this relation, we can have two representations of a two dimensional real-valued function(mapping : R2 [mapsto] R) as

fc(x,y)=fp(ρ,θ),

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].

Figure 1
Equally spaced grids

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.

2 Truncated Expansions in Cartesian and Polar Coordinates

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

2.1 Truncated Hermite Expansions in Cartesian Coordinates

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

Hn(x)=(1)nex2dndxn(ex2).

The Hermite functions are defined as

hn(x)=12n2n!πHn(x)ex22.
(1)

Note that the set {hn(x)} is orthonormal, which means hm(x)hn(x)dx=δmn. The Hermite functions satisfy the recurrence formula

n+1hn+1(x)=2xhn(x)nhn1(x).

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

The set {hn(x)} for n = 0, 1, 2… forms a basis for the set of square-integrable functions on the line [12]. Due to this fact and their orthonormality, any f [set membership] L2(R) can be expanded as

f(x)=Σn=0f^nhn(x),

where

f^n=f(x)hn(x)dx.

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

f(x)Σn=0Nf^nhn(x),

where N is a large nonnegative integer.

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

fc(x,y)=Σm=0Σn=0f^mnhm(x)hn(y),

where Hermite series coefficients are defined as

f^mn=fc(x,y)hm(x)hn(y)dxdy.
(2)

Also we can use a truncated expansion of the form

fc(x,y)=Σm=0NΣn=0Nf^mnhm(x)hn(y),
(3)

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

fc(x,y)=Σm=0NΣn=0Nmf^mnhm(x)hn(y),
(4)

or equivalently,

fc(x,y)=Σm=0NΣn=0mf^n,mnhn(x)hmn(y),
(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.

2.2 Truncated Expansions in polar coordinates using Laguerre functions and Fourier basis

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

Lnk(x)=exxkn!dndxn(exxn+k).

The associated Laguerre polynomials are orthogonal over [0, ∞) with respect to the weighting function xkex,

0xkexLmk(x)Lnk(x)dx=(n+k)!n!δm,n.

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

f(x)=12πΣk=+f^(k)eikx,

where

f^(n)=12π02πf(x)einxdx.

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

χm,n(ρ,θ)=(1)(m|n|)2[(m|n|)2]!π[(m+|n|)2]!ρ|n|L(m|n|)2|n|(ρ2)eρ22einθ,
(6)

where (m − |n|) and (m + |n|) are even numbers. If we define Ymn(r) and Zn(θ) as

Ymn(ρ)=(1)(m|n|)22[(m|n|)2]![(m+|n|)2]!ρ|n|L(m|n|)2|n|(ρ2)eρ22,

Zn(θ)=12πeinθ,

then χm,n(ρ, θ) can be decomposed as

χm,n(ρ,θ)=Ymn(ρ)Zn(θ).

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

fp(ρ,θ)=Σm=0Σn=mmf~m,nχm,n(ρ,θ),
(7)

where the Laguerre-Fourier coefficients are

f~m,n=02π0fp(ρ,θ)χm,n(ρ,θ)ρdρdθ,
(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

fp(ρ,θ)=Σm=0MΣn=mmf~m,nχm,n(ρ,θ),
(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 fmn and fm,n are related.

3 Filtered Image

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 filtering2 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.

3.1 Filtered Images in Cartesian Coordinates

Definition

[F with macron]xy is a given M × M image matrix. The Hermite-filtered image function f(x, y) is given by

f(x,y)=Σm=0NΣn=0Nmf^mnhm(x)hn(y),

where fm−1,n−1 is the (i, j) element of the matrix, and F given by

F^=(HTH)1HTFxyH(HTH)1,

where Hi,j = hj−1(xi). The Hermite-filtered image is sampled from this function on the grid points of the original image.

The matrix H depends on the truncation limit N and a series of xi. For a given M × M image, xi is determined by

xi=R+2R(i1)(M1),

where R is the range of xi and i = 1, 2, …, M. This means that the image is mapped to [−R, R] × [−R, R] in the Cartesian coordinates. Fig. 2 shows the logarithm of the condition number of HTH when the size of the image is 301×301. Since the small condition number of HTH guarantees the stability in its inversion as well as the invertibility, 21 appears to be a good number for the range of xi, making it possible to choose a larger truncation limit with which the Hermite filtered image can describe more details of the original image.

Figure 2
Contour plot of logarithm of condition number of HTH depending on truncation limit and range of xi (M = 301)

Choice of the range of xi is related to the effect of scaling factor in Hermite transform. Basically the Hermite transforms of the similar functions f(x) and f(10x) illustrates a weakness of Hermite expansions. However, when we get a truncated expansion fit to a given discrete data, we can choose the scaling factor so that the difference between the filtered image and the original image is small and the matrix inversion is stable in the filtering process. Since in Fig. 2, the available truncation limit is maximized at the range, 21, this range can be chosen as a near-optimal scale regardless of the image of interest.

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 ||IIF||/||I||, where I and IF are the original image matrix and its Hermite-filtered version, respectively.

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

3.2 Filtered Images in Polar Coordinates

As in Cartesian coordinates, for a given array of Mρ × Mθ sample points on a polar grid, fp(ρp, θq), we minimize the following cost function to get the Laguerre-Fourier coefficients.

C=Σp=1MρΣq=1Mθ|fp(ρp,θq)Σm=0NΣn=mmf~m,nχm,n(ρp,θq)|2ρp.

For a fixed ρp, we consider the two functions.

g(θk)=fp(ρp,θk),

h(θk)=Σm=0NΣn=mmf~m,nχm,n(ρp,θk)=Σm=0NΣn=mmf~m,nYm,n(ρp)Zn(θk)

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

Σk=1Mθ|g(θk)h(θk)|2=1MθΣl=0Mθ1|(g)l(h)l|2,

where the DFT is defined as

(g)l=Σj=0Mθ1g(θj)e2πijlMθ.

The DFT of Zn(θk) gives

(Zn(θk))l=Σj=0Mθ1Zn(θj)e2πijlMθ=12πΣj=0Mθ1e2πij(nl)Mθ=Mθ2πδl,n.

With these relations, the cost function can be rewritten as

C=SΣp=1MρΣl=0Mθ1|(fp(ρp))lMθ2πΣm=0NΣn=mmf~m,nYm,n(ρp)δl,n|2ρp,

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

C=SΣl=0Mθ1Σp=1Mρ|(fp(ρp))lρpMθ2πΣn=NNΣm=|n|Nf~m,nYm,n(ρp)ρpδ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θN + 1 in the θ direction. The cost function is

C=SΣl=0NΣp=1Mρ|(fp(ρp))lρpMθ2πΣn=0NΣm=|n|Nf~m,nYm,n(ρp)ρpδl,n|2+SΣl=N+1Mθ1Σp=1Mρ|(fp(ρp))lρp|2.

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

C=Σl=0NΣp=1Mρ|(fp(ρp))lρpMθ2πΣm=lNf~m,lYm,l(ρp)ρp|2.
(10)

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

bl=[(fp(ρ1))lρ1(fp(ρ2))lρ2(fp(ρMρ))lρMρ]Txl=[f~l,lf~l+2,lf~2[(N1)2]+l,l]T,

and

Al=Mθ2π(ρ1Yl,l(ρ1)ρ1Yl+2,l(ρ1)ρ2Yl,l(ρ2)ρMρY2[(Nl)2]+l,l(ρMρ)),

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

C=Σl=0NblAlxl2.

Even though bl and xl consist of complex numbers, the pseudo inverse approach is still possible because Al is a matrix of real numbers. As long as the condition number of Al is small, we can have the minimizer as

xl=(AlTAl)1AlTbl.

The matrix Al is determined by the truncation limit and the range of ρ, much like H was in the case of Cartesian coordinates. Fig.4 shows the condition numbers of A0, when Mρ = 151. 21 and 240 are the best choice for the range of ρ and the truncation limit, respectively. In that case, Fig. 5 shows the condition number of Al with respect to l. Since the maximum condition number appears at l = 0, the choice is safe. Fig.6 shows a brain image expressed in polar coordinates and corresponding Laguerre-Fourier-filtered images with different truncation limits.

Figure 4
Contour plot of logarithm of condition number of A0 depending on truncation limit and range of ρ (Mρ = 151)
Figure 5
Logarithm of condition number of Al(Mθ = 151, N = 240)
Figure 6
Original and Laguerre-Fourier-filtered images viewed in a polar coordinate array

4 Interconversion between polar and Cartesian coordinates

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.

4.1 Laguerre-Fourier coefficients in terms of Hermite coefficients

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

eimθρmLnm(ρ2)=(1)n22n+mn!Σr=0nΣs=0misCnrCmsH2r+ms(x)H2n2r+s(y),
(11)

where ρ=x2+y2 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(ρ, θ) as

χmn(ρ,θ)=Σr=0(m+n)2Σs=0nis(2rns)!(m+n2r+s)!2m(mn2)!(m+n2)!×Cm+n2rCnsh2rns(x)hm+n2r+s(y),

where n ≤ 0, x = ρ cos θ and y = ρ sin θ. If we use a new variable, α = 2rns, then the double sum is Σr=0(m+n)2Σα=2r2rn. If we define the combination symbols to be zero when they can not be defined (e.g. C21,C34=0), we can extend the limits of the summations as Σr=0[m2]Σα=2rm, 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

χmn(ρ,θ)=Σα=0mα!(mα)!2m(mn2)!(m+n2)![Σr=0[α2]i2rnαc(m+n)2rCn2rnα]×hα(x)hmα(y).

For n > 0, we use the fact that χm,n=χm,n. Substituting this χmn and (5) in (8) gives

f~p,q=Σn=0pGn(p,q)f^n,pn,
(12)

where

Gn(p,q)={n!(pn)!2p(p+q2)!(pq2)!Σr=0[n2]Cp+q2rCqn2ri2rqnifq0,n!(pn)!2p(p+q2)!(pq2)!Σr=0[n2]Cpq2rCqn2r(i)2r+qnifq>0}.

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 (f) can be computed by linear combination of the Hermite coefficients (f). Secondly, fp,q is determined only by a set {fn,p−n}(n = 0, 1, …, p). In other words the relationships are localized. Thirdly, it tells us how the truncation limit should be determined in order for the coordinate conversion to be lossless. Since we started with (5), p in (12) cannot exceed N. Therefore, the Laguerre-Fourier coefficients from (12) are fp,q, (p = 0, 1…N,q = −p, −p + 2, …p). We reconstruct the two-dimensional function, fp(ρ,θ) as

fp(ρ,θ)=Σp=0NΣq=ppf~p,qχp,q(ρ,θ).

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.

4.2 Hermite coefficients in terms of Laguerre-Fourier coefficients

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

Hl(x)Hkl(y)=Re((i)klΣr=0lΣs=0kl(1)rClrCkls(r+s)!ei(k2r2s)θρ(k2r2s)×Lr+sk2r2s(ρ2)),
(13)

where Cnk=n!(k!(nk)!), x = ρ cos θ, y = ρ sin θ and Re(c) gives a real part of a complex number, c. To evaluate the associate Laguerre polynomial, Lmn for n < 0, we use the formula [2]

m!ρnLmn(ρ2)=(1)n(m+n)!ρnLm+nn(ρ2).
(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

f^l,k1=Re{Σj=0kDj(l,kl)f~k,2jk},
(15)

where

Dj(l,kl)=Σr=0l(1)jr(i)klClrCkljr(kj)!j!2kl!(kl)!.

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

4.3 Interconversion between Truncated Hermite and Laguerre-Fourier Expansions

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

fp(ρ,θ)=Σp=0NΣq=ppf~p,qχp,q(ρ,θ)fc(x,y)=Σm=0NΣn=0mf^n,mnhn(x)hmn(y),
(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 (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 (N+1)(N+2)2 coefficients that are complex numbers, which means there are (N + 1)(N + 2) independent real numbers. However, since fp,0 is a real number and f~p,q=f~p,q, there are exactly (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

fp(ρ,θ)=fc(ρcosθ,ρsinθ)=Σm=0NΣn=0mf^n,mnhn(ρcosθ)hmn(ρsinθ),
(17)

fc(x,y)=fp(x2+y2,atan(x,y))=Σp=0NΣq=ppf~p,qχp,q(x2+y2,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 (Cnm) for large arguments introduce some numerical error during computation. To overcome this, we use a resampling technique. Given a set of f, we sample appropriate points of fp(ρ, θ) using (17) and then compute the Laguerre-Fourier coefficients using the method described in Section 3.1. For an arbitrary image, there is loss of information in filtering process, but applying it to resampled data from a truncated expansion gives exact coefficients (to within machine precision). The whole process and the numerical examples will be presented in the next section.

5 Numerical Examples

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.

Figure 7
Block diagram of interconversion of data given in different coordinate systems
Figure 8
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.

Figure 9
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.

Figure 10
Interpolation using interconversion method

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.

6 Conclusions and Discussions

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 R2) is defined by O(N2) coefficients. The Hermite filtering process is of O(N3), because we invert a N × N matrix. Resampling the Hermite expansion on polar coordinates is of O(N4), while O(N3) computations are required in resampling it onto Cartesian coordinates. The Laguerre-Fourier filtering process is of O(N4), 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 O(N4). Resampling the Laguerre-Fourier expansion on the polar and Cartesian coordinates needs O(N3) and O(N4), respectively. Therefore, the total complexity of interconversion is O(N4). If the constants in (12) and (15) are precalculated, the direct conversion of those coefficients is of O(N3). 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 O(N4) 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.

Acknowledgements

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

Footnotes

1The 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.

2Since 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.

References

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.