Home - Table of Contents

"Merge": Breakthrough Software for User-defined MMUs

Ray Ford, Roland Redmond, Steve Barsness
University of Montana, Missoula

The basic specification of a merge program that would meet the specific needs of digital land cover mapping originated from meetings between Roly Redmond, Zhenkui Ma, and Ray Ford at the University of Montana during summer 1992. Intuitively, Merge is an image transformation operation which takes as primary inputs a raster image, a minimum map unit (MMU), and a similarity function. It then produces as output a transformed image in which all raster areas smaller than the MMU have been eliminated by being "merged into" their neighboring areas. The MMU value is a simple integer that expresses a measure of image resolution, i.e., areas smaller than the MMU are considered as too small to be of interest at this particular level of processing. Both the input and output images are assumed to contain 8-bit classified values, as might result from a prior image classification pass or merge operation (e.g., using a smaller MMU value). The similarity function defines a numerical measure of similarity between each possible pair of class values in the input image; for an image with N class values, similarity can be encoded as a N x N array of real numbers.

Though processing details are quite intricate, the general merge process can be expressed in simple intuitive terms, as (a) all pixels comprising areas in the input image larger than the selected MMU "survive" unchanged in the output image, and (b) all pixels in areas smaller than the selected MMU are subject to being changed, as the areas in which they reside are combined with their larger neighbors. The actual processing details satisfy four additional principles. First, mergers always assign small areas in toto to larger neighbors, so that the resulting boundaries exhibit a hierarchical scaling property. Second, the selection of a particular neighbor for a "merge target" is based on maximum similarity between its class value and the class value of the "to be merged" area. Third, additional optional parameters can be used to identify exceptional cases of particular class values or regions of the image not to be altered by the merge process. Finally, a number of specific ordering and special processing rules guarantee that the processing is both predictable and repeatable and does not contain any "random" processing effects.

Though Drs. Ford, Redmond, and Ma continued to develop and refine the precise Merge specification, the basic definition was settled during summer 1992, and the search for an algorithm that could effectively scale-up to allow "large" images to be processed on local workstations began at that time. The initial processing goal was single-pass processing of a complete Landsat TM scene. This target of roughly 8000 x 8000 pixels (an input image of about 64MB) seemed far away at first, but we carefully refined our algorithm to make steady process toward that goal. Some prominent milestones from the development include the following:

  • By spring 1993, Dr. Ford had outlined the basic computational issues and approaches and had prototypes running that could process 1/4 TM scenes (roughly 2K x 2K pixels) in about 5 hours of execution time. Revising and re-engineering the algorithms to scale-up to larger images proved to be a laborious task, but progress continued throughout 1993. By summer 1993, Dr. Ford was able to successfully process full TM scenes at small MMUs in a single pass (in about 30 hours).
  • By winter 1993/94, one of Dr. Ford’s graduate students, Jin Guo, had implemented enhancements that reduced processing time dramatically for small MMUs (to about 2 hours). By spring 1994, another of Dr. Ford’s students, Kathy Kahl, completed a project focusing on algorithm animation of the merge process. Later in 1994, Dr. Ma implemented a version of merge with additional enhancements that reduced processing time even more, while adding specific features of interest in land cover mapping. With a continuing sequence of minor adjustments, Dr. Ma’s version became the standard used in processing at University of Montana’s Wildlife Spatial Analysis Lab (WSAL) and remained the best available version for several months.
  • During 1995/96, Dr. Ford used the "merge problem" as the focus of a year-long system design course for computer science graduate students, and out of that effort emerged a major algorithm design breakthrough that has led to the current best version ("MegaMerge") and its successors. Steve Barsness radically redesigned some critical components of merge, producing a new family of implementations that offered breakthroughs on three processing frontiers:
  1. significantly reduced processing time (about 10 minutes for full TM scene),
  2. significantly enhanced ability to process imagery larger than a full TM scene in a single pass (from an 8K x 8K maximum to up to 20K x 30K pixels),
  3. processing requirements in time and space that are relatively independent of MMU size, image complexity, and other data-specific factors. The versions arising from Barsness’ work at last exhibited the sort of reliable and robust execution that had long been lacking in prior versions.

From 1992 through 1996, Dr. Ford and his students had been working on the merge problem without funding from the GAP program. As WSAL analysts and others began to use the Barsness’ versions, it became clear that all parties would profit from the creation of a single more robust, standard version of this code. A contract was signed in summer 1997 to fund the creation of an official version tailored to the needs of GAP users (now called "MegaMerge"). The contract calls for the code to be available for the most commonly used GIS platforms, UNIX workstations including Sun, IBM, SGI, HP, and Dec Unix. The implementation team (Steve Barsness and Ray Ford) quickly implemented the desired feature set, then set about assuring that the code would execute reliably on a wide range of input data values, and on the range of supported platforms.

Through the efforts of the implementation team and cooperation of various GAP users volunteering their facilities as "beta host" sites, the code has now been extensively tested on all the targeted platforms. It was officially released in "beta" form to GAP users on September 15, 1997, and is now being used and evaluated, prior to formal acceptance testing. Following acceptance, the implementation team will release a final version of the code and accompanying documentation. Meanwhile, the code and extensive documentation is available on-line at the UM-Merge Project Web site, at http://www.cs.umt.edu/MERGE.

Independently, both Dr. Ford and Mr. Barsness continue research and development efforts to adapt the code to new applications (such as 3-D imagery), enhance performance, and produce versions appropriate for other platforms (particularly PCs running some version of Windows). Additional information on the application of "merge" to other classes of 2-D and 3-D imagery can be obtained via e-mail to "ford@cs.umt.edu". Additional information on Steve Barsness’ newest version "GigaMerge" and Windows implementations of "MegaMerge" can be found on the Web at http://www.cyberport.net/glacier/gisor obtained via e-mail to sjb@cyberport.net.

Editor’s note: MegaMerge is currently undergoing beta testing. Once we receive all the testers’ comments, we will post them on the electronic bulletin board on the GAP home page.

Home - Table of Contents