Apparatus for producing a flattening map of a digitized image for conformally mapping onto a surface and associated method

• US 6,697,538 B1
• Filed: 07/28/2000
• Issued: 02/24/2004
• Est. Priority Date: 07/30/1999
• Status: Active Grant

• Current Assignee: Brigham and Women's Hospital Incorporated, Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Original Assignee: Wisconsin Alumni Research Foundation (University of Wisconsin System)
• Inventors: Kikinis, Ron, Haker, Steven, Angenent, Sigurd B., Tannenbaum, Allen R.
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): PATEL, KANJIBHAI B
• Application Number:
  US09/627,512
• Time in Patent Office: 1,306 Days
• Field of Search: 382/285, 382/173, 382/203, 382/241, 708/274, 708/446, 708/270, 716/20, 345/418, 345/653, 700/182
• US Class Current: 382/285
• CPC Class Codes: G06T 15/10 Geometric effects
• CPC Class Codes: G06T 19/00 Manipulating 3D models or images for computer graphics
• CPC Class Codes: G06T 2219/021 Flattening

Abstract

A computerized apparatus and associated method and program code on a storage medium, for producing a flattening map of a digitized image. This image may be initially synthetically produced as discrete data or as quasi-discrete image data of a real object—and the original image data may be stored as two-, three-, or four-dimensional dynamic coordinate data. Once produced, the flattening map can be conformally mapped onto the computer generated surface (whether 2-D, 3-D, or any of the dynamically-varying family of surfaces) for display on a computer-assisted display apparatus in communication with a processor. The apparatus and associated method and program code include constructing a first set of data comprising a plurality of discrete surface-elements to represent at least a portion of a surface of the digitized image, and performing a flattening function on the first set of data to produce the flattening map. The flattening function includes computing, for each discrete surface-element, a solution to each of two systems of linear equations formulated from finding a numerical solution to a selected partial differential equation (PDE), and can be performed on each of a series of data sets changing over time to produce a corresponding series of flattening maps.

Claims

1. A computerized apparatus for producing a flattening map of a digitized image, comprising:

a processor for constructing a first set of data comprising a plurality of discrete surface-elements to represent at least a portion of a surface of the digitized image, and performing a flattening function on said first set of data to produce the flattening map; and

said flattening function to comprise computing, for each said discrete surface-element, a solution to each of two systems of linear equations formulated from finding a numerical solution to a selected partial differential equation (PDE) derived by applying a Laplace-Beltrami operator.

2. The apparatus of claim 1 wherein said discrete surface-elements are triangulated elements, said two systems of linear equations have been formulated by applying a finite-element approximation comprising a sparse matrix, and said PDE is a second order PDE.

3. The apparatus of claim 2 wherein said two systems of linear equations comprise the expressions D_x=a, D_y=−

b, D_x and D_y represent elements of said sparse matrix with a and b denoting associated vectors, z=x+iy where z represents the flattening map; and

said second order PDE comprises the expression, $\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>z=\left(\frac{\partial <br><br>}{\partial <br><br>u}-i<br><br>\frac{\partial <br><br>}{\partial <br><br>v}\right)<br><br>{\mathrm{\delta <br><br>}}_p,$

where p represents a point on an embedded surface, Σ

, of genus zero, u and v represent conformal coordinates defined in proximity to said point p, δ

_p denotes the Dirac delta function at said point p, Δ

denotes said Laplace-Beltrami operator on Σ

\{p}, and i represents square root of −

1.

4. The apparatus of claim 3 wherein said flattening function further comprises identifying values for the variables D_PQ, a_Q and b_Q, where D_PQ denotes a matrix, a_Q and b_Q denote associated vectors, said embedded surface, Σ

, is a triangulated surface, P and Q are a pair of vertices with PQ as an edge of a first and second triangle PQR and PQS, using at least the following expressions;

$D_{\mathrm{PQ}}=-\frac{1}{2}<br><br>\left\{\cot <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\angle <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>R+\cot <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\angle <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>S\right\},\text{\hspace{1em}<br><br>}<br><br>P\ne <br><br>Q$$D_{\mathrm{PP}}=-\underset{P\ne <br><br>Q}{\sum <br><br>}<br><br>D_{\mathrm{PQ}}$$a_Q-i<br><br>\text{\hspace{1em}<br><br>}<br><br>b_Q=\{\begin{array}{cc}0,& Q\notin <br><br>\left\{A,B,C\right\}\\ \frac{-1}{<br><br>B-A<br><br>}+i<br><br>\frac{1-\mathrm{\theta <br><br>}}{<br><br>C-E<br><br>},& Q=A\\ \frac{1}{<br><br>B-A<br><br>}+i<br><br>\frac{\mathrm{\theta <br><br>}}{<br><br>C-E<br><br>},& Q=B\\ i<br><br>\frac{-1}{<br><br>C-E<br><br>},& Q=C,\end{array}$

wherein ∠

R is an angle at vertex R in a triangle PQR, ∠

S is an angle at vertex S in a triangle PQS, and ABC represents points of a triangle in whose interior said point p lies.

5. The apparatus of claim 1 wherein:

the digitized image is of a cortical structure said surface of which is at least partially smoothed upon said constructing said first set of data, said surface-elements are selected from the group consisting of triangulated areas, random-shaped areas, surface points, pixels, sub-pixels, cells, sub-cells, segments, and sub-segments;

said PDE comprises the expression, $\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>z=\left(\frac{\partial <br><br>}{\partial <br><br>u}-i<br><br>\frac{\partial <br><br>}{\partial <br><br>v}\right)<br><br>{\mathrm{\delta <br><br>}}_p,$

where p represents a point on an embedded surface, Σ

, of genus zero, u and v represent conformal coordinates defined in proximity to said point p, δ

_p denotes the Dirac delta function at said point p, Δ

denotes said Laplace-Beltrami operator on Σ

\{p}, and i represents square root of −

1; and

the flattening map is then conformally mapped onto a spherical surface that is displayed on a computer-assisted display apparatus in communication with said processor.

6. The apparatus of claim 1 wherein:

the digitized image is a computer-generated 3-D image, said surface-elements having been selected from the group consisting of triangulated areas, random-shaped areas, surface points, pixels, sub-pixels, cells, sub-cells, segments, and sub-segments;

said PDE comprises the expression, $\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>z=\left(\frac{\partial <br><br>}{\partial <br><br>u}-i<br><br>\frac{\partial <br><br>}{\partial <br><br>v}\right)<br><br>{\mathrm{\delta <br><br>}}_p,$

where p represents a point on an embedded surface, Σ

, of genus zero, u and v represent conformal coordinates defined in proximity to said point p, δ

_p denotes the Dirac delta function at said point p, Δ

denotes said Laplace-Beltrami operator on Σ

\{p}, and i represents square root of −

1; and

the flattening map is then conformally mapped onto a computer-generated 3D surface that is displayed on a computer-assisted display apparatus in communication with said processor.

7. The apparatus of claim 6 wherein the 3-D image changes shape over time such that said construction of said first set of data further comprises constructing a series of said first sets of data correspondingly over time and said flattening function is performed on each of said series of said first sets to produce a corresponding series of the flattening maps.

8. A computerized apparatus for producing a flattening map of a digitized image for conformally mapping onto a computer-generated surface, comprising:

a processor for constructing a first set of data comprising a plurality of discrete surface-elements to represent at least a portion of a surface of the digitized image, and performing a flattening function on said first set of data to produce the flattening map; and

said flattening function to comprise computing a numerical approximation of the solution to a selected partial differential equation (PDE), $\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>z=\left(\frac{\partial <br><br>}{\partial <br><br>u}-i<br><br>\frac{\partial <br><br>}{\partial <br><br>v}\right)<br><br>{\mathrm{\delta <br><br>}}_p,$

for said first set of data, where p represents a point on an embedded surface, Σ

, of genus zero, u and v represent conformal coordinates defined in proximity to said point p, δ

_p denotes the Dirac delta function at said point p, Δ

denotes a Laplace-Beltrami operator on Σ

\{p}, and i represents square root of −

1.

9. The apparatus of claim 8 wherein said flattening function has been derived by initially applying a finite-element approximation to formulate two sparse systems of linear equations, and said computing said numerical approximation further comprises computing a solution to each of said two sparse systems for each said discrete surface-element.

10. The apparatus of claim 9 wherein:

the digitized image is of an object, said plurality of discrete surface-elements comprises an extraction of said surface that is of genus zero, and said surface-elements are triangulated elements;

said two systems of linear equations comprise the expressions

11. A method for producing a flattening map of a digitized image, comprising:

constructing a first set of data with a processor, said data comprising a plurality of discrete surface-elements to represent at least a portion of a surface of the digitized image; and

performing a flattening function on said first set of data to produce the flattening map, said flattening function to comprise computing, for each said discrete surface-element, a solution to each of two systems of linear equations formulated from finding a numerical solution to a selected partial differential equation (PDE) derived by applying a Laplace-Beltrami operator.

12. The method of claim 11 wherein:

said two systems of linear equations comprise the expressions D_x=a, D_y=−

b, D_x and D_y represent elements of said sparse matrix with a and b denoting associated vectors, z=x+iy where z represents the flattening map;

said selected PDE comprises the expression, $\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>z=\left(\frac{\partial <br><br>}{\partial <br><br>u}-i<br><br>\frac{\partial <br><br>}{\partial <br><br>v}\right)<br><br>{\mathrm{\delta <br><br>}}_p,$

where p represents a point on an embedded surface, Σ

, of genus zero, u and v represent conformal coordinates defined in proximity to said point δ

_p denotes the Dirac delta function at said point p, Δ

denotes said Laplace-Beltrami operator on Σ

\{p}, and i represents square root of −

1;

and said flattening function further comprises identifying values for the variables D_PQ, a_Q and b_Q, where D_PQ denotes a matrix, a_Q and b_Q denote associated vectors, said embedded surface, Σ

, is a triangulated surface, P and Q are a pair of vertices with PQ as an edge of a first and second triangle PQR and PQS, using the following expressions;

$D_{\mathrm{PQ}}=-\frac{1}{2}<br><br>\left\{\cot <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\angle <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>R+\cot <br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{\angle <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>S\right\},\text{\hspace{1em}<br><br>}<br><br>P\ne <br><br>Q$$D_{\mathrm{PP}}=-\underset{P\ne <br><br>Q}{\sum <br><br>}<br><br>D_{\mathrm{PQ}}$$a_Q-i<br><br>\text{\hspace{1em}<br><br>}<br><br>b_Q=\{\begin{array}{cc}0,& Q\notin <br><br>\left\{A,B,C\right\}\\ \frac{-1}{<br><br>B-A<br><br>}+i<br><br>\frac{1-\mathrm{\theta <br><br>}}{<br><br>C-E<br><br>},& Q=A\\ \frac{1}{<br><br>B-A<br><br>}+i<br><br>\frac{\mathrm{\theta <br><br>}}{<br><br>C-E<br><br>},& Q=B\\ i<br><br>\frac{-1}{<br><br>C-E<br><br>},& Q=C,\end{array}$

wherein ∠

R is an angle at vertex R in a triangle PQR, ∠

S is an angle at vertex S in a triangle PQS, and ABC represents points of a triangle in whose interior said point p lies.

13. The method of claim 12 wherein:

said step of computing a solution to each of two systems results in a plurality of piecewise linear harmonic functional expressions comprising an expression for x and an expression for y;

$x=\underset{Q}{\sum <br><br>}<br><br>x_o<br><br>{\mathrm{\phi <br><br>}}_o$$y=\underset{Q}{\sum <br><br>}<br><br>y_o<br><br>{\mathrm{\phi <br><br>}}_o$

and the method further comprises the steps of conformally mapping x and y according to said expression z=x+iy onto a preselected computer-generated surface, and displaying on a computer-assisted display apparatus said conformal mapping.

14. A method for producing a flattening map of a digitized image for conformally mapping onto a computer-generated surface for display, the method comprising the steps of:

constructing a first set of data comprising a plurality of discrete surface-elements to represent at least a portion of a surface of the digitized image; and

performing a flattening function on said first set of data to produce the flattening map;

said flattening function to comprise computing a numerical approximation of the solution to a selected partial differential equation (PDE), $\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>z=\left(\frac{\partial <br><br>}{\partial <br><br>u}-i<br><br>\frac{\partial <br><br>}{\partial <br><br>v}\right)<br><br>{\mathrm{\delta <br><br>}}_p,$

for said first set of data, where p represents a point on an embedded surface, Σ

, of genus zero, u and v represent conformal coordinates defined in proximity to said point p, δ

_p denotes the Dirac delta function at said point p, Δ

denotes a Laplace-Beltrami operator on Σ

\{p}, and i represents square root of −

1.

15. The method of claim 14 wherein:

the digitized image is of a cortical structure said surface of which is at least partially smoothed upon said constructing said first set of data, said surface-elements are selected from the group consisting of triangulated areas, random-shaped areas, surface points, pixels, sub-pixels, cells, sub-cells, segments, and sub-segments, and said flattening function further comprises initially applying a finite-element approximation to formulate two sparse systems of linear equations; and

further comprising the steps of conformally mapping the flattening map onto said computer-generated surface and displaying said conformal mapping on a computer-assisted display apparatus.

16. The method of claim 14 wherein the digitized image is of an object, said plurality of discrete surface-elements comprises an extraction of said surface that is of genus zero, and said surface-elements are triangulated elements;

and further comprising the steps of conformally mapping the flattening map onto said computer-generated surface and displaying said conformal mapping on a computer-assisted display apparatus.

17. A computer executable program code on a computer readable storage medium for producing a flattening map of a digitized image, the program code comprising:

a first program sub-code for constructing a first set of data comprising a plurality of discrete surface-elements to represent at least a portion of a surface of the digitized image; and

a second program sub-code for performing a flattening function on said first set of data to produce the flattening map, said second sub-code comprising instructions for computing, for each said discrete surface-element, a solution to each of two systems of linear equations formulated from finding a numerical solution to a selected partial differential equation (PDE) derived by applying a Laplace-Beltrami operator.

18. The program code of claim 17 wherein:

said two systems of linear equations have been formulated by applying a finite-element approximation;

the digitized image is a computer-generated 3-D image;

said surface-elements are triangulated elements; and

further comprising a third program sub-code for conformally mapping the flattening map onto a computer-generated 3D surface for display on a computer-assisted display apparatus.

19. A computer executable program code on a computer readable storage medium for producing a flattening map of a digitized image to be conformally mapped onto a computer-generated surface for display, the program code comprising:

a first program sub-code for constructing a first set of data comprising a plurality of discrete surface-elements to represent at least a portion of a surface of the digitized image; and

a second program sub-code for performing a flattening function on said first set of data to produce the flattening map;

said second sub-code comprising instructions for computing a numerical approximation of the solution to a selected partial differential equation (PDE), $\mathrm{\Delta <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>z=\left(\frac{\partial <br><br>}{\partial <br><br>u}-i<br><br>\frac{\partial <br><br>}{\partial <br><br>v}\right)<br><br>{\mathrm{\delta <br><br>}}_p,$

for said first set of data, where p represents a point on an embedded surface, Σ

, of genus zero, u and v represent conformal coordinates defined in proximity to said point p, δ

_p denotes the Dirac delta function at said point p, Δ

denotes a Laplace-Beltrami operator on Σ

\{p}, and i represents square root of −

1.

20. The program code of claim 19 wherein said flattening function has been derived by initially applying a finite-element approximation to formulate two systems of linear equations, and said second sub-code further comprises instructions for computing a solution to each of said two systems of linear equations;

and further comprising a third program sub-code for said conformal mapping of the flattening map onto said computer-generated surface and displaying said conformal mapping on a computer-assisted display apparatus.