In the last article I demonstrated a general technique for extracting DEMs from well-behaved USGS topographic maps. Although extracting DEMs from USGS topo maps is useful to illustrate many BLACKART features, USGS topos present the easiest possible extraction problem. This article demonstrates a technique for the more difficult "real world" extractions from maps likely to be available for this type of work.

The target is a subset of a map included with the 26th edition Appalachian Mountain Club (AMC) White Mountains Guide for the Mt. Washington region of northern New Hampshire, USA. I scanned this paper map into .bmp format using an old Opti Pro 400 small-format flatbed scanner (the inexpensive kind that is used in office applications). This map is much more typical of the types of maps that are commonly available for many regions where high resolution DEM coverage is not. Let us first review the differences between this map and the one that was the subject of the previous article.

The map is much more cluttered with non-contour data than the previous example. In addition to the contour lines, the makers of this map included information on trails and streams. The map also has one vertical coordinate grid line. These will be particularly problematic because from an image processing standpoint, they are similar to the target contour lines that we wish to extract.

Land use information is included as well. There are three background shades present in the map. There is also a lot of descriptive text on the map, including contour elevations, peak elevations, peak names, watercourse names, trail names and other information. Background colors themselves are easy to handle, but they usually mean that the contour lines will be composed of different pixel colors, depending on the background over which a particular line is overlaid. Text is another difficult-to-handle artifact when separating contour lines.

Although there are not broad areas of closely spaced contour lines, there is one area toward the center of the map where two contour lines touch. There are several other areas where contour lines are close enough together that they will have to be handled.

When I started working on the BLACKART image processing modules I hoped to develop a semi-automated technique for the separation of all of these unwanted objects and features from the target contour line data. I attempted several strategies: principally bandwidth filtration, pattern recognition, edge detection and object masking. Although I came close to my objective, none of these proved completely successful. Before I present the workable technique that I currently use, let's briefly examine the ones that didn't work.

Bandwidth filtration takes advantage of color to discriminate one set of objects from another. I created three primary filtration tools to separate pixels by color: filter by value, filter by range, and byte-level filtration. The first problem with the bandwidth filtration approach is the large number of colors present in the image. Although the image appears to have only a few shades of green, red, blue, brown and black, close examination will show that it is actually composed of tens of thousands of individual pixel colors (63,508 tp be exact). That is because a standard .bmp image (as well as other common formats such as .tif) contains 24 bits of data, allowing over sixteen million possible colors. Although most images do not come close to spanning the whole RGB color space, they do contain a lot of colors. Subtle differences in tone in the image are achieved by dithering pixels of many different colors. A brown contour line will be composed of thousands of individual pixels of many shades of red, blue, green, yellow, etc. Moreover, some of these very same pixel colors will also appear in the green background, the blue streams, and so on. In short, it is not possible to separate contour lines composed of so many different pixel colors.

So the successful use of this strategy required reducing the number of colors to a more manageable number. This is commonly done through unsupervised clustering, that is grouping of pixels into a specified number of classes using a computer algorithm. Clustering algorithms exist that will select the optimal group of colors (the number of which is specified by the user) and will then test each pixel for the best match from among the groups. BLACKART contains one such algorithm that works very well.

Although the reduction of the total number of colors in the image to some optimal number like five or six greatly improves the situation, it does not eliminate the problem. Unless only two or three groups are specified (and this will not work because it does not allow enough discrimination among perhaps a dozen object types), the application of clustering algorithms will always result in the same color pixel being present in both the target (contour lines) and one or more of the unwanted objects (i.e. background, text, etc.). As a result, application of a bandwidth filter after clustering can remove much of an unwanted object, but will almost always remove significant portions of some of the contour lines as well. After many frustrating hours investigating different combinations of clustering parameters and bandwidth filtration parameters, I concluded that a different or at least an additional strategy was needed.

I next attempted to take advantage of the characteristic patterns that contour lines, text, and background objects possessed. I experimented with several types of patterns, for example groups of pixels commonly found in lines and surrounding neighbor patterns. The most useful was a type of flood fill pattern that I call 'Web Removal' on the Image menu. This tool is so named because it is especially good at removing the "web" of background color that spans two contour lines. The map image can be cleaned considerably without removing contour line pixels by combining clustering to reduce the number of colors with the web removal tool. This algorithm changes pixels that have the same color as the pixel under the cursor to white (0xffffff) by "flowing" from one adjacent pixel to the next until all connected pixels of the specified color are converted. While this method can work well at removing background colors while leaving the contour lines undisturbed, it had several problems. The most important was that it required a very clean clustering separation between the background and the contour lines. This is often difficult to achieve. It was not very good at removing text. Although it worked well for 90 percent of the image, removing the remaining ten percent of the objects was very tedious. The resulting image suffered from the problem that plagued many of the techniques with which I experimented. It resulted in a messy, noisy image with large and confusing contour line gaps that were hard to reconnect either automatically or manually. Editing this type of image often resulted in an overly sparse image missing too much valuable contour line data.

I experimented with another technique, masking, to attack the text. The method required clicking on a target text pixel with the Image|Query Pixel option enabled (to acquire the pixel RGB value) and then filtering all pixels except that color out of the image using the Image|Filter|Range option. This typically left much of the text plus some pixels that were part of contour lines in the filtered image. The pixels that were part of the contour lines could be removed from the mask using the eraser tool set to a wide pen width (40 pixels). Once the mask was cleaned up, it could be NANDed to the original image. This had the effect of removing the mask from the target image. Although this was fairly effective at removing the text and other unwanted objects, it was less than completely effective. The reason was that although much of the text was removed, there were always at least a few pixels of a different color that were part of the text that remained behind after masking. These cluttered up the gap left by the deleted text. The repeated application of text removal masks left a very messy image with a lot of big gaps confused with a lot of noise. I added a tool for the removal of pixel groups comprised of less than the specified number of pixels. However even with this tool, the results were less than desired. An example of a text mask created from the target image and the result of NANDing the mask with the target image using BLACKART is shown at the upper right.

The best result I was able to achieve after sharpening, clustering, contrast stretching, masking, binarization, thinning, and cleaning is also shown to the right. It is obvious that it is not a very satisfactory image and would require a lot of editing to make it useful, if this was even possible.

This led me to the development a technique that did work. It may seem unsatisfying because it is far from automatic, and it may not be very new. I call it patching. In short, rather that removing offending objects explicitely, they are simply covered with a patch of white pixels. Then the digitizing tool is used to connect the contour lines over the patch. This is repeated for all text, stream and road objects until only a clean contour map remains. At this point, the background can be removed either by bandwidth filtering or by masking. I will illustrate the technique using the target map.

The first step is to apply the unsharp mask tool to the input image. This can be done by selecting Image|Filter|Unsharp Mask. I selected a sharp multiplier of 0.85 initially, and then re-applied the mask using a sharp multiplier of 0.90 a few times. This had the effect of increasing the contrast of the image, and in particular it increased the contrast between the contour lines and the background, which helps in the separation. The original image and the sharpened image are shown to the right.

The next step was to classify the image. This is done by selecting Image|Classify Pixels. When the dialog box was presented, I selected the default settings, requesting five pixel groups and one pass. The classified image with only five colors is shown next. (Note: this is not a particularly high fidelity classification, but this does not matter for our purposes. Increasing the number of passes would improve the color matching, but I was not interested in a close color match, just a valid grouping.)

Now the patching can begin. Select Graphics|Clip Text|Enable. This will allow you to place a white rectangle "patch" over for example a text object on the map. The next image shows such a patch placed over a large text object. I typically place a few patches at a time and then digitize the contours, and then repeat the process until complete. To digitize the contours, set the pen color and marker colors to something that will show up well and are not used elsewhere in the image. This will insure that they will not be filtered inadvertently later on of conversely, that they can be filtered if desired (in the case of any stray markers) without affecting the rest of the image. I chose red for the lines and blue for the markers. Set the pen width equal to the zoom factor (The zoom factor is displayed at the bottom of the main window.) Select Image|Digitize Contour|Enabled. Now simply click on a contour line on one side of the patch and double click on the corresponding contour line on the other side. Repeat for all broken contour lines. The result of connecting across a few patches is shown in the next image.

Continue this procedure until all the text is effectively removed from the image. There are also many other more irregular objects, including roads, trails and watercourses. I removed these similarly using the eraser tool. I then connected the contour lines across the resulting missing data region using the digitizing tool as before. (Tip: to remove the last marker from the image, select Image|Despeckle). The resulting image after repetition of this process is shown next.

Now it is time to remove the background. There are three colors. I removed two of them using bandwidth filtration, and the third using masking. I will explain the masking technique because I have not specifically covered it previously. Examination of the image showed that one of the green background colors, 0xaad7a4, appeared extensively in the contour lines. Bandwidth filtering this color would result in the loss of a lot of data. So I decided to remove this background color by preparing a mask and then essentially subtracting the mask from the base image.

First save the base image by selecting File|Save Image. Now select Image|Query Pixel Value and clicked on a target green pixel. Select Image|Filter|Range. When the dialog box appears, select 'Load Value' and uncheck the 'Keep/Discard' toggle and clicked 'Submit'. The resulting image is shown next. Notice that it contains a lot of contour line "ghosts". The next step will be to remove these. Select Graphics|Tool Palette and set the pen width to 40. Select Graphics|Erase. Using the eraser tool, erase all the green contour lines. Then save the image (under a different name, like 'mask1') by selecting File|Save Image. Close the image. Open the previous image. Open the mask image by selecting File|Open Reference Image from the main menu. Now select Image|Array Operations|NAND Image. The mask will be subtracted from the original. The result of the masking and filtering is shown in the next image.

The subsequent operations, including binarization, thinning, cleaning and hand editing and tagging are exactly as covered in the preceding article. The tagged image is shown next. I then interpolated the image as before using 10,000 Laplacian and 1000 LSQR iterations. This yielded a high quality DEM characteristic of the Franklin algorithm. The rendered image from 3DEM is shown in the in the last image to the right.

This article summarizes only some of the work that I have attempted over the last several months. Although the technique outlined is not very automated, it does have several advantages:

1) It is applicable to any contour map image, regardless of size.
2) It is easy to stop the work and then pick it up again later (save the image as an .elv file). 3) It can handle a wide spectrum of image quality.
4) It can handle virtually any unwanted artifact, including crowded contour lines (see next article).
5) It preserves as much of the source contour line data as is possible, thereby eliminating human digitizing error to a large degree.
6) It efficiently uses human intelligence for a task for which it is uniquely suited and for which digital image processing is particularly unsuited: large scale pattern recognition and intuition regarding contour line re-attachment.

The recent release of 90m SRTM DEM coverage for most of the world except Africa seems to make BLACKART somewhat of an anachronism. However, it is clear that the program has the capability of producing DEMs of much higher resolution than the 90m SRTM product. Even this sample map pulled from the back of a field guide with its 100 vertical foot contour spacings should have a much higher data density (particularly in mountianous areas) than international SRTM DEMs. Despite the work required to construct custom DEMs, there will probably be a place for this approach until the release of the 30m SRTM data set world wide.