A previous article on this site outlined how to extract digital elevation models from topographic maps using BLACKART in combination with WinTopo Pro, a commercial raster-to-vector conversion program. Since writing that article, I have completed considerable work on a graphics front end for BLACKART. Some BLACKART utilities surpass those available in WinTopo Pro and even R2V, a more expensive raster-to-vector conversion utility that was the subject of an earlier article. The purpose of this tutorial is to highlight some of the features of BLACKART by walking through first a simple example, and then in a follow-up article a more complex example.
The demonstration file is an approximately 1km square subset of a USGS topographical map of Glover Peak in the Wind River range in central Wyoming, USA. The use of a USGS topographical map for a contour line extraction example is really cheating for a couple of reasons. In the first place, there is no point in conducting such an extraction since high quality DEMs for the entire United States are already available for free. More significantly, USGS topographical maps are very well-behaved from a contour extraction perspective. The features that make them so will become clearer when we (somewhat unsuccessfully) tackle a real world problem in the next article.
USGS topos are relatively uncluttered with non-contour data. They use a very limited number of known colors and the colors are completely unaliased in the source .tiff files. They are available in high resolutions so that the contour lines are not blurred or distorted excessively. For this reason, USGS topographic maps are probably as easy to segment of any in the world. A review of the literature on the subject indicates that there is not much information on the subject of topographic map segmentation and contour line extraction. However, when a journal article can be found, USGS topo maps are commonly used because they are so much easier to work with than alternatives. However, an automatic extraction method is of little value if it will not work for problems that are much more difficult than presented by USGS topo maps.
That being said, I will start off first with the USGS topo map described above in order to illustrate the use of the BLACKART contour extraction tools. The first image to the right is the source image. It is a very favorable image for contour extraction for a few reasons. Because it is of an area above the treeline, the background is a single neutral color. As will be seen, the actual background color is of little consequence to BLACKART. However, when multiple background colors are present, the problem can become more challenging. This is because the contour lines will change color in order to contrast with the new background. The contour lines usually become confounded or aliased in that certain pixel colors that are in the background of the first region are often present in large numbers in the contour lines of the second region. Since segmentation of the image according to color is a primary method used to separate desirable features from undesirable ones, this presents problems to any segmentation strategy as it makes simple bandwidth filtration infeasible. More on this problem later. For now, we will attack the problem at hand and examine these other issues in more detail later.
The easiest way to remove unwanted information is by band pass filtration. Although this is a poor strategy for many images, as will be seen in the next article, it will work for our well-behaved USGS topo because all USGS topos are composed of a maximum of thirteen unaliased colors.. Select Image|Query Pixel Value|Enabled. This feature allows you to determine the RGB color value of any pixel in the image by clicking on it. The color value will be displayed on the diagnostics screen.
This is not our purpose at the moment however. Whenever a pixel is queried, its color value is stored in memory. Up to sixteen color values are stored for use in the Range and Value band pass filters. For now we will be using a single stored value and the Range filter.
This filter is normally used to remove a range of pixel values, for example all pixels that have RGB color values between 0xaaaaaa and 0xffffff. It can also remove all pixels having a single pixel value by simply setting the upper and lower range limits to the target RGB value.
BLACKART makes this relatively easy. In our example, click on any black text object, for example the 'G' in Glover Peak. Next, select Image|Filter|Range. Select 'Load Value' and then 'Submit'. All of the black text will immediately disappear from the image. (If at any time you make a mistake or do not like the result, select 'Undo'. Note that only one level of Undo is supported.) Do the same for the two blue pixel values in the glacial lakes on the map. These can be removed just as easily. The filtered image is the second from the top.
So far, this has gone relatively quickly. However now there are only brown and white pixels left, and further attacks on color features are not possible. Other automated strategies are available, for example pattern recognition. However, the image is so simple we can resort to hand editing to complete our separation
We will first get rid of the elevation values embedded in the contour lines by simply erasing them. Select Graphics|Tool Palette|Pen Width and select 6. Then select Graphics|Erase. Move the cursor over the text and press the left mouse button. Holding down the button, erase the text. There are broken and isolated pixels in the areas of some of the black text. Erase these as well. When you are done cleaning the image, select Graphics|Copy Bitmap. This copies the screen image to the logical data array. (It is important that this be done because all the editing will be lost otherwise.) The results of our work so far are shown in the third image.
Once the erasures are complete, it is time to binarize the image. Binarization maps an image in 24-bit RGB color space to 8-bit color space where all pixels are either 0x00 or 0xff. This conversion is necessary for subsequent processing. Select Image|Binarize and then hit 'Submit'. It is possible to change the background color to which white (0xff) will be assigned. Since the background is white, the default 0xffffff values is the appropriate one. After binarizing, the image will consist only of black and white pixels. It is now necessary to thin the contour lines. Select Image|Thin. It may be necessary to apply the thinning algorithm a couple of times to completely skeletenize the contour lines. The result is shown in the fourth image.
Now we will attempt to automatically close small gaps in the contour lines. Select Image|Clean Image|Connect Lines. A dialog box will be presented. You will be prompted to input the search radius. This is the distance that the algorithm will search from each endpoint in the process of looking for another endpoint to connect to. Examine the image and estimate a likely separation difference. Note: the computation time increases geometrically with the search radius. The greater the number of pixels, the greater the computation time required. For this example I chose a 20 pixel search radius. This value closed many of the gaps. It also resulted in some errors as some breaks were connected in ways that are obviously incorrect, i.e. causing crossed contour lines. These must be corrected by manual editing. Use the eraser tool to remove these problems.
We could use the drawing tool to close the remaining contour line gaps by selecting Graphics|Draw and sketching in the appropriate contours. However, it is more precise and easier to use the digitizing tool. The digitizing tool is designed for tracing contour lines. This is the traditional way to extract contour lines from topographical maps. In this method, the operator laboriously traces over contour lines on a paper map using a digitizing tablet. We will use the digital tool to repair breaks. Select Image|Digitize Contour|Enable. Then select Graphics|Tool Palette|Marker Color and set the marker color to red. When you click your cursor over the image, a marker will be dropped. Clicking more markers will drop more waypoints. Double clicking will draw a line connecting the points. (Note: if the final marker is within fifteen pixels of the starting pixel, a closed loop will be formed, i.e. the first point will be connected to the last point.)Use this tool to close as many of the gaps as you can. Closing gaps is not essential for successful tagging, but it does make the process go a lot quicker. Don't forget to disable your tools after you are done using them. Failure to do so can produce some interesting but unwanted results.
Another classic problem related to contour line extraction is handling areas of high gradient, i.e. where contour lines are very close together. Often, contour lines are grouped so closely together that they join into one blurred mess. Although this test image was carefully chosen so that it does not suffer from this problem, many maps do. Since the contour lines will be interpolated, this problem can be handled by thinning the contour lines. This and other specialized techniques will be discussed in the next article.
In the present case, we only need to do some cleanup work in the area to the east and west of Glover peak. Using the eraser tool with a pen width of six, erase the fragmented pixels in the region where the text appeared. Then, using the eraser tool with a pen width of one, careful scribe white lines between any contour lines that appear to be touching. If you do not get all of them, don't worry as we will recover the rest during the tagging operation, which is next. However, repair work distracts from the tagging operation and can cause you to make errors, so try to get as many as possible now. When you are done, use the despeckling tool to clean up any solitary pixels. First click on a background white pixel. This tells the algorithm to look for pixels that are surrounded by exactly eight white pixels. the select Image|Despeckle 8-Bit (The corresponding 24-bit tool is used for RGB image cleanup.) All lone black pixels should disappear. Make a final check of the image, erasing any spurs, isolated pixel clusters, and other imperfections before we start the final stage of tagging. Our map at this point is shown in the fifth image.
The purpose of tagging is to assign elevation values to the contour lines. Some commercial programs first convert the contour lines to vectors before assigning elevation values. BLACKART works entirely with raster images as there is really not much point in converting from raster to vector and then back to raster again for interpolation. Tagging must be done manually using human intelligence as there is no intelligence left in the image that could possibly allow this to be done automatically. The goal of any tagging routine is to do this as efficiently as possible. BLACKART has some powerful tools for this purpose.
Before we begin, it is a good idea to save the image just in case something goes wrong later on. Select File|Save Bitmap Array from the graphics window menu. This will allow you to save the file as an .elv file. This is a simple ASCII format with a two integer header indicating the number of rows and columns. BLACKART can read this file and allow you to resume processing where you left off when you saved the file. Alternatively, the file can be saved and read in index file format.
I like to start from he highest peak and then work my way down. You may develop your own technique. For now, key in the elevation of the top of Glover Peak. In order to make this part easier, you may want to call up a reference image. Select File|Open Reference Image from the main window and open the topo map. From this image we can see that the peak elevation is 12068 feet. We will use this value to get the most accurate interpolation possible. Using the draw tool, put a dot at the top of the peak. Draw a dot on the top of the lesser peak at the left of the image (11164 feet) in the same manner. In general, you will want to take advantage of every known elevation on the map, including sea level, indicated lake elevations, surveyed ground control points or GPS data, etc. The interpolation algorithm will use all of them to advantage.
Now select Image|Tag|Set Elevation Value. The Elevation Control Panel will be displayed. This panel can stay visible during the whole tagging process. Allowing it to do so greatly facilitates the tagging process. Enter the Glover Peak elevation in the text box. Uncheck the auto increment box. Set the 'Tag Enabled' radio button true and the 'Show Disabled' to true. Select 'Submit'. Now click on the mark at the top of the peak. The elevation 12068 will be assigned. Key in the elevation of the lesser peak and click 'Submit'. Click on that marker and the elevation of 11164 will be assigned. In general, you will want to take advantage of every known elevation on the map, including sea level, indicated lake elevations, surveyed ground control points or GPS data, etc. The interpolation algorithm will use all of them to advantage.
Now it is time to start assigning the elevations to the contour lines. Returning to Glover Peak, if the peak elevation is 12068, then the first contour line must be 12060 since the contour lines are at 20 foot intervals. Enter 12060 into the Elevation Control Panel text box. Check the 'Auto Increment' box and enter an increment value of minus 20 (-20). Click on 'Submit'. Select the highest contour line. When successfully tagged, the elevation will be briefly displayed and the line will turn color.
I chose not to have the elevation permanently displayed for a couple of reasons. From a practical standpoint, they do not help much because when the contour lines are close together it is impossible to tell which elevation goes to which contour line. They also clutter up the image a lot. Instead, I provided an elevation querying tool. This can be enabled from the main menu bar or more conveniently by setting the 'Show Enabled' radio button to true and the 'Tag Enabled' radio button to false on the Elevation Control Panel. Now when you click on a contour line, its elevation will be momentarily displayed. You will use this tool a lot during the tagging process.
Continue tagging lines, moving from the top of the mountain towards one of the valleys. If you are lucky, tagging will proceed smoothly down the slope with the elevation automatically decrementing by 20 feet each time. The more likely case is that you will encounter some problem. Two typical ones are discovering segmented contour lines and two lines that contact. In the first case you will want to tag the segment with the same value as the line that you just tagged. But if the elevation has is automatically decrementing, merely selecting this line will assign it the wrong value. Moreover, each successive line tagged will be 20 feet too low.
The remedy is to select 'Reload Last' from the Elevation Control Panel. Un check the 'Auto Increment' check box. Now you can click on all the segments of the contour line and the same (correct) value. When you are done, check the 'Auto Increment' box and select 'Resume'. The elevation value where you left off will be loaded and you can resume tagging until you encounter the next problem. Alternatively, right click on the broken line. Subsequent right clicking will assign the current elevation value to a contour line without incrementing. This allows you to tag multiple contour lines with the same value. Left clicking on a contour line resumes tagging at the next (decremented) contour line. For the case of joined contour lines, you can disable tagging and querying by setting 'Tag Disabled' and 'Show Disabled' to true and then using the drawing and erasing tools. After you 'Copy Bitmap' you can resume tagging where you left off. By manipulating the utilities on the control panel, you can work your way through the tagging process relatively painlessly.
When the tagging is done, carefully check your work using the elevation query tool. However, if you do not catch your error here, it is likely that you will catch it and repair it in the next step. The tagged image appears in the sixth figure above. Save your work as an elevation file again. Now select File|Input Data from the graphics window menu file. A dialog box will prompt you for processing information. Enter 1000 Laplacian Iterations and 0 LSQR iterations and select 'Submit'. This will allow us to run a test interpolation to make sure that we have not missed or mis-assigned any contour lines. (Note: do not close the graphics window.)
Now select 'Run' from the main menu. BLACKART will run an interpolation on your tagged contour file. When it is done, view the interpolated DEM by selecting View from the main menu. Although the interpolation in not of very high quality, untagged contour lines will show up starkly on the interpolated image. By comparing the interpolated image with the tagged contour image, and using the elevation query tool, bad contour lines can be fixed
When you are satisfied that the tagged image is correct, run a real interpolation by adding more Laplacian and LSQR iterations. For this test image, I used 10,000 Laplacian and 1000 LSQR iterations. As discussed in the BLACKART documentation, the Laplacian iterations used to compute the initial estimate run about ten times faster than the LSQR iterations. The correct number and combination of iterations is a matter of trial and error as this will differ for different topographies and file sizes.
The interpolated image is the seventh image on the right. The eight image is a 3-D rendering. It was produced by saving the file as a USGS ASCII DEM and then importing into 3DEM. This is a pretty decent image that might be improved with additional preparation and higher iterations.
In the next article, we will use more powerful image processing tools to attack less cooperative input images.
Note:BLACKART has been under continuous development since around June, 2003. It is a strictly alpha release with no stable release yet available. I have discovered significant problems almost every week and have published 32 revisions since version 3.xx was released. Many of these problems were created during the process of fixing other problems or adding necessary features. Others, like the severe memory leak problem that was just corrected in revision 32 lay dormant for many weeks and was not discovered until I took some time off from programming to do some testing.
Since there are still a few features that I wish to add for this version, it is possible that I may induce other problems before I wring out all the bugs and freeze a stable release. I appreciate the patience of anyone who has taken the time to experiment with the program.