"Merge": Breakthrough Software for User-defined MMUs
Ray Ford, Roland Redmond,
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:
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 "firstname.lastname@example.org". 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 email@example.com.
Editors 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.