Visualization and storage algorithms associated with processing point cloud data

• US 7,804,498 B1
• Filed: 09/15/2005
• Issued: 09/28/2010
• Est. Priority Date: 09/15/2004
• Status: Active Grant

• Current Assignee: Bradley K. Herman, Carl S. Riddell, Kyle Ellison, Lewis N. Graham
• Original Assignee: Bradley K. Herman, Carl S. Riddell, Kyle Ellison, Lewis N. Graham
• Inventors: Riddell, Carl S, Graham, Lewis N, Ellison, Kyle, Herman, Bradley K
• Primary Examiner(s): Hajnik; Daniel F
• Application Number:
  US11/227,300
• Time in Patent Office: 1,839 Days
• Field of Search: None
• US Class Current: 345/419
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 15/00 3D [Three Dimensional] image rendering
• CPC Class Codes: G06T 17/20 Finite element generation, e.g. wire-frame surface description, tesselation

Abstract

A plurality of algorithms for interpreting and displaying point cloud data are disclosed. Typically, a virtual grid is constructed over point cloud data, with intersections of the grid at a predetermined spacing that may be dependent on density of the point cloud. Several methods are implemented that utilize tuple data from tuples near a respective intersection to populate intersections of the grid with data. In most embodiments, the intersections of the grid correspond to pixels in a raster image. The tuple data may be manipulated to determine Nyquist spacing of points in a point cloud and portions thereof, develop monoscopic and stereoscopic images, and enhance selected features of an image. Additional algorithms are disclosed that reduce storage and computational requirements during processing of point clouds. Such algorithms use a tiled grid structure wherein processing and data storage proceeds in one or a few of the tiles at a time.

Claims

1. A method for organizing tuples of a point cloud wherein said tuples contain data related to physical features comprising:

constructing a virtual grid having a plurality of intersections over said point cloud of tuples, said intersections spaced in accordance with a desired spatial frequency, each intersection of said intersections associated with a predetermined data structure,

subdividing said virtual grid into tiles of a predetermined size, each tile of said tiles containing a plurality of said intersections,

developing a plurality of separate tile records, one tile record for each said tile,

storing tuple data from said tuples falling in each said tile in a respective said tile record so said tuple data related to a selected region of said point cloud is quickly retrievable by accessing only said tuple data stored in those said tile records associated with said selected region,

defining an overlap tile along each boundary where two adjacent said tiles meet, said overlap tile extending into each of said adjacent tiles so that said tuples in said overlap tile may be treated as belonging to one or the other or both of said adjacent tiles,

when a region in said point cloud is selected, triangulating only said tuples in said tiles and said overlap tiles of a selected said region into a linked triangulated network, with tuples in said overlap tiles along edges of said selected region allowing completion of a triangulation process, eliminating a need for triangulating all tuples in an adjacent tile and increasing computational speed of the process,

populating at least most of said predetermined data structures with data interpolated from said triangulated network, said triangulated network extending into said overlap tiles, and,

using said data in said data structures to develop a display of said physical features in said selected region.

2. A method as set forth in claim 1 further comprising:

developing said triangulated network in one said tile, said triangulated network including said overlap tiles associated with said one tile,

storing said triangulated network associated with said one tile and associated said overlap tiles,

repeating said developing a triangulated network and storing said triangulated network until all said tiles and associated said overlap tiles of said virtual grid are separately triangulated and stored.

3. A method as set forth in claim 2 further comprising:

retrieving a group of separately stored triangulated networks associated with a plurality of adjacent said tiles and said associated overlap tiles, said group representative of only said selected region, and wherein said triangulated overlap tiles cause adjacent said tiles to match at their edges, forming a single triangulated network from a retrieved said group of stored triangulated networks.

4. A method as set forth in claim 3 further comprising:

interpolating pixel values from said single triangulated network, associated with said at least one tile and associated said overlap tiles,

developing an image from interpolated said pixel values.

5. A method as set forth in claim 2 further comprising retrieving said separately triangulated networks containing said selected region and forming a single triangulated network therefrom in order to rapidly display said physical features of said selected region.

6. A method as set forth in claim 1 wherein said using said data in said data structures to develop said physical features of said selected region further comprises:

defining said selected region as a footprint for a monoscopic metric analysis image within said virtual grid,

selecting at least one tuple parameter for interpolation,

associating intersections within said footprint with respective pixels of said display,

populating a respective said data structure for each said intersection with an interpolated said at least one tuple parameter from said triangulated network,

using said pixels of said display to display interpolated said at least one parameter values as a monoscopic metric analysis image of said features, said monoscopic metric analysis image usable as a digital orthophoto.

7. A method as set forth in claim 6 wherein said at least one tuple parameter further comprises selecting said at least one tuple parameter from the group comprising:

a height attribute from said triangulated network,

an intensity from said triangulated network,

a return intensity and using an interpolated return intensity to modulate a classification of a nearby tuple,

a return intensity using a second selected attribute of a nearby tuple.

8. A method as set forth in claim 1 further comprising:

establishing a stereo exaggeration value,

developing a pair of tiled overlapping triangulated networks of said selected region, a first said tiled overlapping triangulated network for a right eye and a second said tiled overlapping triangulated network for a left eye,

interpolating pixel values for said first tiled overlapping triangulated network and pixel values for said second tiled overlapping triangulated network using said stereo exaggeration to shift said first tiled overlapping triangulated network and said second tiled overlapping triangulated network, and,

populating pixels of a right image with shifted interpolated said pixel values for said first tiled overlapping triangulated network and pixels of a left image with shifted interpolated said pixel values for said second tiled overlapping triangulated network to provide a stereo pair of images.

9. A method as set forth in claim 1 wherein said populating at least most of said predetermined data structures with said data obtained at said intersections further comprises:

defining surfaces within triangles of said triangulated network,

extrapolating from said surfaces at said intersections to obtain said data for populating said predetermined data structures.

10. A method as set forth in claim 9 further comprising introducing a parallex parameter in interpolated said tuple data for developing a pair of stereo images that provide stereoscopic viewing.

11. A method as set forth in claim 1 wherein said display is a raster image comprising pixels.

12. A method as set forth in claim 11 further comprising associating said pixels of said raster image with respective said intersections, and computing values of each pixel of said pixels using a populated said predetermined data structure of a respective said intersection based upon said tuple data.

13. A method as set forth in claim 11 further comprising selecting said desired spatial frequency of said intersections to be similar to or the same as spacing of said pixels of said raster image.

14. A method a set forth in claim 11 further comprising associating said pixels of said raster image with respective said intersections until at least most of said pixels are assigned a value based on a populated said data structure of respective said intersections.

15. A method as set forth in claim 11 further comprising determining from said display whether or not a density of populated said predetermined data structures of said intersections meets a Nyquist sampling criteria for said desired spatial frequency.

16. A method as set forth in claim 1 further comprising:

receiving a sequential list of said tuples,

for each said tuple of said sequential list of said tuples, determining a nearest said intersection in said virtual grid,

populating said predetermined data structure associated with said nearest intersection using said tuple data from a first-found said tuple nearest said intersection,

disregarding tuple data from other said tuples near a previously-populated said intersection, thereby thinning said tuple data.

17. A method as set forth in claim 1 further comprising designating as void a pixel associated with an unpopulated said data structure, and assigning at least a color to a void said pixel.

18. A method as set forth in claim 17 further comprising determining conformance to Nyquist sampling criteria of said point cloud by displaying said color assigned to void said pixels in said display.

19. A method as set forth in claim 1 wherein each said data structure is populated using only a portion of said tuple data.

20. A method as set forth in claim 1 further comprising:

developing surfaces from triangles of said triangulated network,

for each intersection of said intersections that falls within a triangle of said triangulated network, locating a nearest tuple from a vertex of a respective said triangle, and,

assigning a color to a pixel associated with said intersection nearest said vertex based on a first selected attribute of said nearest tuple.

21. A method as set forth in claim 20 further comprising assigning an intensity to at least some of said colors based on a second selected attribute of said nearest tuple, for developing details about said surfaces.

22. A method as set forth in claim 1 further comprising:

assigning a plurality of priorities to a corresponding plurality of attributes of said tuples,

with respect to each said intersection wherein at least two said tuples of differing priority are nearby, considering a priority of said priorities of each of said at least two tuples,

inserting attribute data from a said tuple of said at least two tuples having a highest priority of said plurality of priorities into said data structure corresponding to said intersection, whereby visualization of higher priority said attributes is enhanced on said display.