Difference between revisions of "Transform: Conformal Mapping Algorithms"

Latest revision as of 15:18, 25 April 2013

The methods described in this document use conformal mapping to transform points in a circular sector, circle, ellipse, or nearly circular region to points in a circle or rectangle.

Background

A conformal mapping, is a transformation w=f(z) that preserves local angles. An analytic function is conformal at any point where it has a nonzero first derivative. A complex function is analytic on a region R if it is complex differentiable at every point in R. In a conformal mapping, in any small neighborhood the relative angle and shape are preserved.

Notes

Note 1: In this text and figures <math>\theta</math>, <math>\theta_2</math> and <math>\theta_1</math> could be also written as theta, theta2 and theta1.

Note 2: In this text and figures <math>\alpha</math>, <math>\alpha_2</math> and <math>\alpha_1</math> could be also written as alpha, alpha2 and alpha1.

Circular Sector to Rectangle

The algorithm uses a 2D conformal mapping to convert a circular sector, defined by four user points at the sector corners, to a rectangle of the user specified size. The circular sector has an inner radius <math>r_{min}</math>, an outer radius <math>r_{max}</math>, and extends over an angle <math>theta = \alpha* \pi</math> radians, with <math>0 \le \alpha \le 1</math>.

Let, <math>z_1</math> and <math>z_2</math> belong to <math>r_{max}</math>, and <math>z_3</math> and <math>z_4</math> belong to <math>r_{min}</math>. The mapping to the user specified rectangle is performed in the following steps (1-6):

Step 1

The maximum radius can be facing to the top, bottom, right, or left. So the algorithm, first, determines which of 4 orientations is present.

Calculating the center of the circle to which the circular segment belongs

Step 2

Calculating the center of the circular segment. The center is calculated as a point <math>(x_c, y_c)</math> where two lines <math>(z_3, z_2)</math> and <math>(z_4, z_1)</math> cross. Therefore,

Equation 1

<math> x_c=\frac {x_3 * y_2) - (x_2 * y_3)} {(x-3 -x_2)} - \frac {(x_4 * y_1) - (x_1 * y_4)} {x_4 - x_1)} </math> <math> y_c = x_c \frac {y_4 -y_1} {x_4 -x_1} + \frac {(x_4 * y_1) - (x_1 * y_4)}{(x-4 - x_1)} </math>

Step 3

Calculating the angle of the sector in radians.

Transform Conformal Mapping : Calculating the angle of the circular segment

The angle is calculated as follows <math>\theta = \theta_2 - \theta_1. </math>

For the maximum radius facing to the left, we must take into account the discontinuity of the angle at the negative x axis. The angle changes from <math>-\pi to \pi</math>, so the equation for <math>\theta</math> is now:

<math> \theta = abs(\theta1) + abs(\theta2) - 2.0 * \pi </math>

The angle <math>\theta1</math> is along the line from center to <math>z_4 to z_1</math> in <math> -\pi</math> to <math>\pi</math> radians:

<math> \tan(\theta_1) = \frac{((y_1 - y_4)}{(x_1 - x4_)} => \theta_1 = \arctan{(y_1 - y_4)}{(x_1 - x_4)}</math>

the angle <math>theta_2</math> is along the line from center to <math>z_3 to z_2</math> in <math> -\pi to \pi </math> radians:

<math>\tan(\theta_2)= \frac{(y_2 - y_3)}{(x_2 - x_3)} => \theta_2 = \arctan\frac{(y_2 - y3_)}{(x_2 - x_3)}</math>

Note: In this text and figures <math>\theta</math>, <math>\theta_2</math> and <math>\theta_1</math> could be also written as \theta, \theta2 and \theta1

Step 4

For the conformal mapping, it requires that <math>r_{max} > 1 and 0 < r_{min} < 1</math>. Refer to "A Domain Decomposition Method for Conformal Mapping onto a Rectangle" Remark 4.7 (see "References" ). The transformation theory is based on a mathematical crosscut along the unit circle.

Therefore, the algorithm divides all the distances from the circular center by <math>\sqrt{r_{max}* r_{min}}</math>. It produces a value of r so that <math>1 < r <\sqrt{r_{max}* r_{min}}</math>

Step 5

To convert a circular sector to a rectangle, the algorithm uses the following transformation function

Equation 2

<math>w = f(z) = u + iv = \frac{\log(z)}{(i*\alpha* \pi)}</math>

Let <math>z =r*\exp(i*\theta)</math>

Then,

Equation 3

<math>w = \log \frac{(r*\exp(i*\theta))}{(i*\alpha* \pi)}</math> =>

<math> w= \frac{\theta}{(\alpha* \pi)} - i*\frac{\log(r)}{(\alpha* \pi)}</math>

<math> u = \frac{\theta}{(\alpha* \pi)}</math>,

<math> v = -\frac{\log(r)}{(\alpha* \pi)}</math>

Since conformal mapping requires that <math>f(z)</math> must be analytic on all points, the Cauchy-Riemann equations must be satisfied and <math>f'(z)</math> must not equal zero.

Satisfying the Cauchy-Riemann equations

Suppose that <math>f(z)=f(x+iy)=u(x,y)+iv(x,y)</math> is differentiable at the point z0=x0+iy0. Then, the partial derivatives of u and v exist at the point (x0, y0), and

Equation 4

<math> f'_x (z_0)=\lim _{\vartriangle x \to 0}\frac{\vartriangle z}{\vartriangle x} </math>

<math> f'_x(z_0) = \lim _{\vartriangle x \to 0} (\frac{\vartriangle u_x (x_0, y_0)+ i \vartriangle v_x (x_0, y_0)}{\vartriangle x}) = \lim _{\vartriangle x \to 0} (\frac{\vartriangle u_x (x_0, y_0)}{\vartriangle x} + \frac {i \vartriangle v_x (x_0, y_0)}{\vartriangle x}) = \frac {du}{dx} + i\frac{dv}{dx} </math>

<math> f'_x (z_0)=\lim _{\vartriangle x \to 0}\frac{\vartriangle z}{\vartriangle y} </math>

<math> f'_x(z_0) = \lim _{\vartriangle y \to 0} (\frac{\vartriangle u_y (x_0, y_0)+ i \vartriangle v_y (x_0, y_0)}{i \vartriangle y}) = \lim _{\vartriangle y \to 0} (\frac{\vartriangle v_y (x_0, y_0)}{\vartriangle y} - i \frac {\vartriangle u_y (x_0, y_0)}{\vartriangle y}) = \frac {dv}{dy} - i\frac{du}{dx} </math> Equating the real and imaginary parts gives

Equation 5

<math> u_x (x_0, y_0) = v_y (x_0, y_0)</math>

and

<math> u_y (x_0, y_0)= - v_x (x_0, y_0)</math>

The Cauchy-Riemann equations in polar form are:

Equation 6

<math> du/dr = (1/r)(dv/d\theta)</math>

<math> -dv/dr = (1/r) (du/d\theta)</math>

The first equation gives zero on both sides and the second equation gives <math>(\alpha* \pi)/r</math> on both sides, so the Cauchy-Riemann equations hold.

Satisfying the non zero first derivative

Equation 7

<math>f'(z) = 1/(i*\alpha* \pi *z)</math>,

<math> f'(z)=!0 </math> except at infinity.

Step 6

Now, the algorithm performs a conformal mapping from the circular segment to a rectangle of width 1 and height <math>log(r_{max}/r_{min})/\theta</math>. Values for f(z1), f(z2), f(z3), and f(z4) are as follows:

Note: In the equations below "alpha" stays for <math>\alpha</math>.

The region inside a circular sector is mapped to a rectangle: z1 is the upper right point on r_max, z2 is the upper left point on r_max, z3 is the lower left point on r_min, and z4 is the lower right point on r_min

Equation 8

Equation 9

Equation 10

Equation 11

Step 7

Then, the rectangle from step 6 is linearly scaled to a rectangle of user specified xDim and yDim. In cases when the maximum radius faces to the top, this gives us the following values for z1', z2', z3'and z4':

z1'= (xDim-1, 0),

z2'= (0, 0),

z3'= (0, yDim-1),

z4'= (xDim-1, yDim-1)

Note that the linear scaling of one rectangle to another is not a conformal mapping unless the width and height are scaled by the same factor.

Transformation: Circle to Rectangle

The user inputs 2 point VOIs. The first point is located at the center of the circle. The second point can be any point located on the actual circle

The algorithm uses a 2D conformal mapping to convert a circle to a rectangle of the user specified size. The circle has the radius r.

The user inputs 2 point VOIs. The first point is located at the center of the circle. The second point can be any point located on the actual circle. The user also inputs the X and Y dimensions (xDimDest and yDimDest) of the output image. See Figure 10. The algorithm performs three mappings to go from the circular area specified by the user to an output rectangle.

Mapping 1

Mapping 1 maps from the destination rectangle to a rectangle centered on the origin. This is the mapping from a rectangle with the edge points (0,0), (xDimDest-1, 0), (xDimDest-1, yDimDest-1), (0, yDimDest-1) to a rectangle with the edge points (-K,Kp), (K,Kp), (K,-Kp), (-K,-Kp).

Where K is the complete elliptic integral of the first kind using the modulus and Kp is the complete elliptic integral of the first kind using the complementary modulus:

<math> complementary-modulus = \sqrt {1 - m^2} </math>

where, the modulus m belongs to the interval [0,1] and is arbitrarily chosen as 0.5.

Mapping 2

Mapping 2 is a conformal mapping from the origin centered rectangle to the unit circle using:

Equation 12

<math> w=\sqrt{\frac{1- cn(z,m)}{1+cn(z,m)}} </math>

where z is the input complex number, w is the output complex number, and cn(z, modulus) is the Jacobian Elliptic function of type cn.

Mapping 3

The algorithm scales and translates from the unit circle to the user selected circle. It uses bilinear interpolation to find the contributions from the four nearest neighbors in the original user selected circle.

Transformation: Ellipse to Circle

This algorithm performs the conformal mapping of an ellipse to a circle with the user defined radius.

Let's consider the original ellipse as having a tilt theta with the X axis. Then the conformal mapping from an ellipse to a circle is done in three following steps.

In the first step, the algorithm translates the circle from the center of the destination square image to the origin, rotates the circle by the angle -theta and converts it to a unit disc by dividing the distance from the center by the radius.

The algorithm places the center of the circle on the center of the destination image. The algorithm considers only the points located on the destination circle, e.g. (j - yc)*(j - yc) + (i - xc)*(i - xc) less or equal radSq.

Then, it translates the circle to the image origin, so that

Equation 13

<math> xp=i-xc </math>

<math> yp=i-yc </math>

After that, it rotates around the circle by the angle -theta

Equation 14

<math> xrot = xp * \cos(\theta) + yp * \sin(\theta) </math>

<math> yrot = -xp * \sin(\theta) + yp * cos(\theta) </math>

And the following step scales the circle to a unit disc:

Equation 15

<math? xrot = \frac{xrot}{radius} </math> <math> yrot = \frac{yrot}{radius} </math>

In the second step, it maps from the unit disc to a standard ellipse on the X axis with foci at (-1,0) (1,0) and with the same major axis/minor axis ratio as the original ellipse.

Let 2*a = major axis, 2*b = minor axis of the original ellipse.

For an ellipse with its center at the origin and foci on the X axis:

Equation 16

[x2/a2] + [y2/b2] = 1

The standard ellipse used here has foci at (-1,0) (1,0) and is of the form:

Equation 17

(x2/cosh2 (xi)) + (y2/sinh2 (xi)) = 1

To scale from the original ellipse to the standard ellipse, the algorithm uses the following transform:

Equation 18

tanh(xi) = sinh(xi)/cosh(xi) = b/a = minor axis/major axis = axisRatio

xi = arg tanh(axisRatio)

xi = 0.5 * log((1 + axisRatio)/(1 - axisRatio))

To conformal map from the unit disc to the standard ellipse, the algorithm uses the following transform T1:

Equation 19

<math> T_1 = \sin \left [\frac{\pi}{2*K(s)}* F(\frac{z}{\sqrt{s}},s) \right ] </math>

Where, K(s) is the complete elliptic integral of the first kind and F is the incomplete or normal elliptic integral of the first kind such that:

Equation 20

<math> F (z,s) = \int_0 ^z \frac{dx}{\sqrt{(1-x^2) (1-s^2 * x^2)}} </math>

Because the elliptical integral functions in MIPAV all use the form:

Equation 21

<math> F (z,\phi) = \int_0 ^\phi \frac{d\theta}{\sqrt{(1-k^2\sin^2 (\theta))}} </math>

So x in the elliptical integral form used in equation 20 equals <math>sin(\phi)</math> in the elliptical integral form used in MIPAV, or <math>\phi = arcsin(x)</math>:

For complex z

Equation 22

<math> \arcsin(z)= -i *\log(i*z+\sqrt{(1-z^2)} </math>

To find s:

Equation 23

<math> u(s)=2xi, </math> <math> 0 \le s \le 1</math>

<math> u(s)= \frac{\pi}{2} * \frac {K(\sqrt{(1-s^2)}}{k(s)} </math>

Where u(s)Italic text decreases from <math>\infty</math> to 0 as s moves from 0 to 1.

In the third step, the algorithm maps from the standard ellipse to the original ellipse by rotating, scaling, and translating. It uses bilinear interpolation to find the contributions from the four nearest neighbors in the original ellipse space.

Transformation: Nearly Circular Region to Circle

Applying the algorithms

For the time being, please refer to the MIPAV HTML help Algorithms/TransformConformalMapping.html for the full documentation on how to apply these algorithms.

Circular Sector to Rectangle

TBD.

Circle to Rectangle

TBD.

Ellipse to Circle

TBD.

Nearly Circle to Circle

TBD.

References

See also:

• Reslice-Isotropic Voxels
• Hough Transform
• Transform
• Transform to power of 2
• Transform nonlinear