Modified back-to-front three dimensional reconstruction algorithm

• US 4,827,413 A
• Filed: 06/16/1987
• Issued: 05/02/1989
• Est. Priority Date: 06/16/1987
• Status: Expired due to Term

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Baldwin, David R., Thiel, Geoffrey L.
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): Kibby, Steven G.
• Application Number:
  US07/062,598
• Time in Patent Office: 686 Days
• Field of Search: 364/414, 364/521, 364/522, 364/413.19, 364/413.18, 340/727, 340/747
• US Class Current: 345/421
• CPC Class Codes: G06T 15/10 Geometric effects

Abstract

A method for displaying three dimensional imaging system data uses a modified Back To Front algorithm. With that algorithm, imaging system data are interpolated and converted into a series of vectors defined by a starting point in space and a length corresponding to consecutive non-zero imaging system data points. The vectors are transformed to an observer'"'"'s viewpoint coordinate system and plotted on a CRT display.

Claims

1. An apparatus for displaying a two dimensional image of a three dimensional object comprising:

(a) three dimensional imaging means for generating first data representing a property of said object at a plurality of points throughout said object;

(b) interpolating means, coupled to said imaging means, for generating from said first data, second data representing said property of said object in a plurality of parallel planes through said object;

(c) run length coding means for generating, along a plurality of paths in each of said parallel planes, a plurality of run length coded vectors having directions and lengths determined from said second data;

(d) rotating means for transforming each of said vectors to a coordinate system based upon a selected origin representing a viewpoint from which said object is to be viewed; and

(e) display means for visually displaying said transformed vectors.

2. An apparatus of claim 1 wherein said three dimensional imaging means also includes means for storing said first data.

3. An apparatus of claim 1 further comprising conversion means, coupled to said interpolating means, for thresholding said second data to a plurality of binary data values.

4. An apparatus of claim 3 wherein said run length coding means includes means for forming said vectors with starting points located at a first occurrence of one of said binary data values encountered along each of said paths having a first value, and with lengths equal to the consecutive number of said binary data values having a first value encountered along said paths.

5. An apparatus of claim 1 wherein said rotating means includes means for selecting a viewpoint in space from which to view said object.

6. An apparatus of claim 1 wherein said display means includes scan conversion means for storing in predetermined order, each of said transformed vectors located on each of said planes.

7. An apparatus of claim 6 wherein said scan conversion means stores said transformed vectors in predetermined order starting with the one of said planes located at a position farthest from said viewpoint.

8. An apparatus of claim 1 wherein said display means is a CRT.

9. A method for displaying a two dimensional image of a three dimensional object comprising the steps of:

(a) generating first data representing a property of said object at a plurality of points throughout said object;

(b) interpolating said first data to generate second data representing said property of said object in a plurality of parallel planes through said object;

(c) generating along a plurality of paths in each of said parallel planes a plurality of run length coded vectors having directions and lengths determined from said second data;

(d) transforming each of said vectors to a coordinate system based upon a selected origin representing a viewpoint from which said object is to be viewed; and

(e) displaying said transformed vectors on a display means.

10. The method of claim 9 wherein the step of generating said first data also includes storing said first data.

11. The method of claim 9 further comprising the step of thresholding said second data to a plurality of binary data values prior to the step of generating said run length coded vectors.

12. The method of claim 11 wherein the step of generating said run length coded vectors includes the substep of forming said run length coded vectors with starting points located at a first occurrence of one of said binary data values having a first value encountered along each of said paths and with lengths equal to the consecutive number of said binary data values having said first value encountered along said paths.

13. The method of claim 9 wherein the step of transforming each of said vectors further includes selecting a viewpoint in space from which to view said object.

14. The method of claim 9 wherein said step of displaying includes storing in predetermined order, each of said transformed vectors located in each of said planes.

15. The method of claim 14 wherein said step of storing in predetermined order further includes the step of starting with said plane located at a position farthest from said viewpoint.

16. The method of claim 9 wherein the step of displaying includes plotting a CRT image of said transformed vectors stored in predetermined order.