Research
Surface Reconstruction DEM Error Visualization Student Research & Projects Publications & Presentations GIS & CG Links

My research is a combination of Computational Geometry and Computer Graphics, as applied to Geographic Information Systems (GIS). The main areas currently under investigation are:

  • Surface Reconstruction - creating a 3D (actually 2.5D) surface from 2D sources, such as contour lines (isolines) or other sparse data arranged on a grid. The data is interpolated or otherwise used to create a digital elevation model (DEM). A DEM is useful for visualization and analysis of a particular region. Some of this work has been done in conjunction with Wm. Randolph Franklin (Electrical, Engineering, and Systems Engineering Department, Rensselaer Polytechnic Institute)
  • DEM Error - many DEMs are constructed from less-than-perfect data, and along with the computations necessary to create the final surface, errors are inevitable. This research seeks to determine the severity of the error.
  • Visualization - while many packages exist to view DEMs and other data, this research concentrates on viewing DEM error.
  • Interdisciplinary Research - I am in collaboration in other areas with researchers such as Mike Smith (School of Earth Sciences and Geography, Kingston University, London) and John Grady (Department of Sociology, Wheaton College).

Surface Reconstruction Algorithms


Figure 1		 Assume we start with a digitized contour map of Mt. Washington, N.H. (Figure 1). The white space indicates areas where elevations must be computed.

A traditional method for interpolating a surface from contours is to use a partial differential equation that models a thin plate being draped over the data points (Figure 2). This yields the surface at right (colors go from blue=low elevation to red=high elevation).
Figure 2

Figure 3 		Obviously, the surface in Figure 2 is not terribly smooth. One way to improve the surface is to create a thin plate approximation instead of interpolation. This allows some of the original contour points to vary slightly, creating a smoother, albeit less accurate, surface. Furthermore, one of the reasons that the surface "scallops" in Figure 2 is because of the difference in curvature of successive contours. In our Intermediate Contour Method, we first compute new contours in between the original data. The thin plate approximation is then applied to the new data set, yielding a measurably smoother result while preserving the accuracy of the surface (Figure 3).

Following the idea that more data = better surface, we find additional data in the Gradient Lines Method. In this algorithm, "gradient paths" that follow the steepest slope from contour to contour are computed. This creates a sort of mesh that can then be filled in with various interpolating or approximating algorithms. Here, we fill in the mesh with inverse distance weighting and finish the surface with a Gaussian smoothing function (Figure 4).


Figure 4
More information on these and other techniques can be found in the publications section below.
Surface Reconstruction Animation

It takes many iterations of the thin plate method to completely fill in a regular grid of elevation points. This animation shows how a sample contour map is filled in with a thin plate approximation after intermediate contours are computed.

DEM Error Visualization

A newer area of research is DEM error visualization. Traditional GIS have many capabilities to compute DEM error, but they require the user to go through many complex steps. Often, the result is simply a number or a 2D visualization. This research seeks to make the process much easier and faster, as well as give a better error visualization.

Our current system, DEMEV (DEM Error Viewer; see Figure 5) has visualizations for relief, raster height colors, slope, height classes, curvature error, local difference error. The user can dynamically change the view, including the sun position, vertical exageration, and so forth. In addition, various statistics can be generated. The latest innovation is a vertical "profile cutter" that allows one to view a desired profile within the context of the 3D surface visualization.

See the papers section below for more information.


Figure 5
Undergraduate Research/Project Opportunities

There are some interesting research project or senior thesis opportunities for interested students. In particular, I need both a front and back end to my research code (described above). The front end would involve creating a nice GUI for the program. The back end would involve displaying the output graphically, allowing the user to manipulate the resulting terrain. Nate Buggia '99 developed a simple surface viewer (Figure 6), complete with lighting and shadows, among other things for a COMP 399 - Advanced Computer Graphics course.

In the summer of 2001, Trevor Agnitti '02, Nick Doolittle '03, and Greg Williams '03 tackled the problem. The resulting system is shown in Figure 7. Trevor worked on the GUI, Nick worked on surface reconstruction techniques, and Greg worked on the overall object-oriented design and much of the graphics. The system allows a researcher to view and evaluate two different surface reconstruction techniques at the same time.

The group presented their work at the Consortium for Computing in Small Colleges at Worcester State in April, 2002. The abstract "A Surface Reconstruction Research Environment" appears in the conference proceedings, The Journal of Computing in Small Colleges. This work evolved into a major research paper (source code available) in Computers & Geosciences.

Pat Sagui '04 completed a project in COMP 399 - Advanced Computer Graphics in the fall of 2003. He modeled a scene from a Lord of the Rings movie that includes many complex graphics ideas, such as lighting, textures, and fog (Figures 8 and 9).

Steven Bowe '05 did some research work for me over the summer of 2004, funded by a Mars Fellowship. He worked on finding ways to visually present errors found in digital elevation models. He presented a poster of the work at Wheaton's Academic Festival in 2005 as well as at the Consortium for Computing Sciences in Colleges at Providence College in April, 2005. His abstract appears in the proceedings as well (see below under Student Publications).

A nice GUI for a DEM error visualization system was implemented by Sarah Milewski '07 in the summer of 2006. This system gives traditional GIS users a quick way to check the validity of DEM data without going through many complex steps using traditional software. This ongoing research is shown in Figure 5.

Computer Graphics (COMP 365) is usually a prerequisite in order to work on these projects, but I do have others that do not require graphics programming experience.
Figure 6


Figure 7


Figure 8


Figure 9

Visualization of Social Stratification

This current research is being done in conjunction with John Grady of Wheaton's Department of Sociology. The idea is to use metaphors to create easy-to-use visualizations in order to see patterns in socio-economic data gathered from the US Census. The Java applets allow the user to compare different social classes, ethnic backround, job type, and income in a dynamic way. With the help of students, we have created web-based prototypes using three different metaphors:
The Target

This is the original metaphor, where the center of a dart board represents the highest income level and the rings representing progressively lower levels. Each "hit" represents 160,000 individuals at that income level.

Click to run Target 1.0

Students Sarah Milewski and Chris Stuetzle, both of the Class of 2007, implemented a newer applet of The Target which addressed some of the shortcomings of the original version.

Click to run Target 2.0

Mountain Climber

In this metaphor, the goal is to climb to the peak of a mountain, where the highest income levels exist. The different "mountains" can be moved or stacked to more easily compare desired parameters. This is a nice improvement over The Target.

This applet was implemented by Sarah Milewski '07 and Chris Stuetzle '07.

Click to run MountainClimber

Census Squared

Students Ben Burrage, Robby Grossman, Dave Machado, all from the Class of 2007, implemented this metaphor, wherein equal-size boxes are stacked on top and next to one another so as to allow easy comparisons. The more income, the more a box is filled. Although this is perhaps a less-strong metaphor, the regularity of each box makes it much easier to move about and stack to produce data patterns. This implementation also has no inherent clustering effect that both The Target and Mountain Climber have, as the area gets smaller as the income level rises in both of the latter implementations.

Click to run CensusSquared

Publications
  • Gousie, M. B. and Milewski, S. A System for 3D Error Visualization and Assessment of Digital Elevation Models. In Proceedings of the 2007 IEEE International Geoscience and Remote Sensing Symposium (IGARSS '07) (Barcelona, 2007).

  • Gousie, M. B. A Robust Web Programming and Graphics Course for Non-Majors. In Proceedings of the 37th SIGCSE Technical Symposium on Computer Science Education (Houston, 2006), pp. 72-76.

  • Gousie, M. B. Digital Elevation Model Error Detection and Visualization. In The 4th Workshop on Dynamic & Multi-dimensional GIS (Pontypridd, Wales, UK, 2005), C. Gold, Ed., ISPRS, pp. 42-46. [PostScript][pdf]

  • Gousie, M. B. and Franklin, W. R. Augmenting Grid-Based Contours to Improve Thin Plate DEM Generation. Photogrammetric Engineering & Remote Sensing 71, 1 (2005), pp. 69-79.

  • Gousie, M. B. and Franklin, W. R. Constructing a DEM from Grid-based Data by Computing Intermediate Contours. In GIS 2003: Proceedings of the Eleventh ACM International Symposium on Advances in Geographic Information Systems (New Orleans, 2003), E. Hoel and P. Rigaux, Eds., pp. 71-77. [PostScript] [pdf]

  • Gousie, M. B., Williams, G., Agnitti, T., and Doolittle, N. CompSurf: An Environment for Exploring Surface Reconstruction Methods on a Grid. Computers & Geosciences 29, 9 (2003), 1165-1173. New version of source code available (8/04): CompSurf v2.0 (Developed on Linux platform.)

  • Gousie, M. B. Teaching Computer Graphics in a Small Department. In Journal of Computing in Small Colleges, Proceedings of the Fifth Annual CCSC Northeastern Conference (2000), pp. 194-202. Winner of conference Best Paper award. [PostScript][pdf]

  • Franklin, R and Gousie, M. Terrain Elevation Data Structure Operations. In 19th International Cartographic Conference & 11th General Assembly of the International Cartographic Association (ICA) (1999).

  • Gousie, M and Franklin, R. Converting Elevation Contours to a Grid. In Proceedings, Eighth International Symposium on Spatial Data Handling (1998), T. Poiker and N. Chrisman, Eds., pp. 647-656. [PostScript][pdf]

  • Gousie, M. B. Contours to Digital Elevation Models: Grid-Based Surface Reconstruction Methods. PhD thesis, Rensselaer Polytechnic Institute, 1998. [PostScript][pdf]
Student Publications
  • Stuetzle, C. Computer Modeling and Visualization of Luminescent Crystals: The Role of Energy Transfer and Upconversion. Honors Thesis, Wheaton College, 2007. See full text.

  • Bowe, S. Error Detection and Visualization in Digital Elevation Models. In Journal of Computing Sciences in Colleges, Proceedings of the Tenth Annual CCSC Northeast Conference (2005), pp. 103-104.

  • Williams, G. An Autoscheduling Optimizer for Perl. Honors Thesis, Wheaton College, 2003.

  • Williams, G., Doolittle, N., and Agnitti, T. A Surface Reconstruction Research Environment. In Journal of Computing in Small Colleges, Proceedings of the Seventh Annual CCSC Northeast Conference (2002), pp. 301-302.
Recent Presentations
  • How Good Is Google Earth? Department of Computer Science Seminar, Siena College, Albany, NY, October 2007.

  • Can You Trust Google Earth? Department of Mathematics and Computer Science Seminar Series, Wheaton College, October 2007.

  • Smith, M.J., Rose, J., and Gousie, M.B. A Method of Quantifying Subglacial Sediment Transport/Deformation. Poster presented at Geomorphology & Earth System Science, BGRG International Conference, Loughborough, UK, June 2006.

  • Math for Non-Mathers: Using Math and Programming in Everyday Life. Wheaton College Faculty Lunch Series, March 2, 2005.

  • Targeting Social Stratification, presented by John Grady at the International Visual Sociology Association (IVSA) Annual Conference, San Francisco, August 12, 2004. [Talk in HTML][Prototype System only]

  • The Role of Digital Logic in the Computer Science Curriculum. Panel discussion with Hoffman, et al. at CCSC-NE, April 23, 2004. In Journal of Computing Sciences in Colleges, Proceedings of the Ninth Annual CCSC Northeastern Conference (2004), pp. 5-9.

  • Thunderstorms, Orange Slime, and Boiling Mud, with B. Dyer and G. Collins. Part of the Puzzles in Science series, Wheaton College, 2003.

  • Implementing the Architecture, Assembly Language and Operating Systems Components of Curriculum 2001. Panel discussion with Wilkens, et al. at CCSC-NE, April 25, 2003. In Journal of Computing Sciences in Colleges, Proceedings of the Eighth Annual CCSC Northeastern Conference (2003), pp. 118-122.

  • Building a Surface Reconstruction Research Environment. Williams College Computer Science Colloquium, April 5, 2002. [Slides in PostScript][Slides in pdf]

  • Making a Mountain out of a (Math) Model. Wheaton College Faculty Lunch Series, October 26, 2000.

  • Improving Terrain Reconstruction on a Grid. Williams College Computer Science Colloquium, 1998.
GIS and CG Links (Updated 7/3/2007)

Journals/Organizations:

There are various places to get USGS data and GIS information, including:

  • Census Bureau Geography - shows all US Census Bureau products, maps, and resources.
  • Geography and GIS - a nice set of links for the GIS researcher, including links to GIS information for every state (click on "GIS Links").
  • USGS Home Page - has general information and links to SDTS-formated DLG data.
  • EROS Data Center - access to USGS 1:250,000 scale DEMs and 1:2M/1:100K DLGs, among others. Some of my own test data was retrieved from this site.
  • Bureau of Land Management (BLM) home page - access to GIS information and MetaData.
  • Bueau of Land Management Geospatial Information Center - contains some Windows utilities and some data.
  • geodata.gov - another source of US data, not limited to maps.
  • Environmental Protection Agency - contains some GIS and mapping related information, including some data here.
  • Maptech - free maps of just about anyplace in the US. Also offers commercial mapping software.
  • Xerox - home page of Xerox PARC - go here to see DLG information. Xerox used to have a database of map data in various formats, including DEM and DLG, but I don't know if this is still the case.
  • The University of Edinburgh - all sorts of GIS information, including Bruce Gidding's DEM Data Catalogue and some data from the UK. The USGS itself recommends this catalog for DEM retrieval.
  • Earth Science and Geology Links - from the Illinois State Geological Survey, this page has a large number of links to many interesting GIS related sites, all indexed by category.
  • GIS Glossary and more - from ESRI (Environmental Systems Research Institute, Inc.), the makers of ARC/INFO and the desktop version ArcView GIS.
  • MapInfo - makers of PC-based GIS software.
  • manifold.net - GIS, mapping, database, and 3D software; also a source of map data.
  • Terra-Server - look at any quadrangle in the U.S. and some areas of the world.
  • TopoZone - commercial topo map site. These are not data maps, but you can look at topos from just about any place in the U.S.

Some Computational Geometry (CG) sources:

More general links:

Last updated