Publications

International Hydrographic Review, Monaco, LXIX(1), March 1992

 

AUTOMATED CARTOGRAPHIC SOUNDING SELECTION
By Steven Zoraster and Stephen Bayer

Abstract

Soundings on nautical charts provide information about the shape of the ocean bottom between chart depth curves. A single chart may have thousands of soundings posted on it. Today, the selection of soundings for chart display is usually performed manually. This paper describes a computer system, which automatically selects soundings for display on a nautical chart. The system is composed of several computer programs, which make use of a grid-based model of the ocean bottom. The ocean bottom model is initialized by gridding the depth curves and shoreline displayed on the nautical chart. Soundings, which deviate from the ocean bottom model, are selected for chart display. Based on initial results obtained from testing these programs, it appears that a significant part of the work required to select soundings for chart display can be automated.

INTRODUCTION

Even though many of the steps involved in chart production have been automated, the compilation of nautical charts remains predominantly a manual task. The potential negative impact from inaccurate chart compilation along with the arcane requirements of chart design have limited the use of computers to supporting interactive revision of charts originally compiled by hand (KERR, 1985). Most research aimed at automating chart compilation has emphasized interactive techniques (LUCKEY, et al. 1987; BOSSLER, et al. 1989; LEPAGE AND HOLYROD 1989).

One cartographic compilation task unique to chart design is the selection of soundings to display on a chart. Soundings on a chart provide information about the shape of the ocean bottom between chart depth curves. Today, soundings are selected for chart display by tedious and costly manual methods. Most recent attempts to automate this task rely on data thinning techniques that do not address the full complexity of the problem (LEPAGE and HOLYROD, 1989; BELL, et al. 1989). More sophisticated automated selection techniques have been proposed, but without providing estimates of the computational complexity involved or any examples of the selection results (LOOMIS and KALL, 1990).

This paper describes computer programs developed for the specific purpose of selecting soundings for chart display. These programs were developed as the result of research performed for the National Ocean Service (NOS) which is part of the United States National Oceanic and Atmospheric Administration (NOAA). Examples are included which show the results of using these programs on test data supplied by NOS. Judging by the results achieved in our initial testing of these programs, it appears that a significant part of the work needed to select soundings for char display can be automated. For example, Figure 1 shows automatically selected soundings for part of the geographic area covered by NOS Chart 14382, "Upper Niagara River." The soundings were selected from a recent hydrographic survey performed to update that chart. The soundings in Figure 1, and the depth curves interactively interpreted on a cartographic workstation, are similar to the manual compilation made by NOS cartographers working independently from the same survey data.

The rest of this paper is organized as follows: Section 2 provides additional background material on the sounding selection problem; Section 3 describes the sounding selection programs; Section 4 describes program test procedures and test results; Section 5 discusses the test results; and Section 6 presents conclusions.

THE SOUNDING SELECTION PROBLEM

Sounding selection can be divided into two parts: "hydrographic" sounding selection and "cartographic" sounding selection. Hydrographic sounding selection involves thinning hydrographic survey data down to a more easily managed subset which is still dense enough to support planned bathymetric modelling or chart compilation tasks (JONES 1986; MacDONALD 1984). One example of hydrographic sounding selection is thinning survey data to produce a dense presentation of soundings without overplotting from which chart depth curves can be developed. The presentation of this type of data is called a smooth sheet in the United States and a fair sheet in most other countries.

Cartographic sounding selection is the process of selecting soundings for chart display to convey to the chart user information about the shape of the ocean bottom between depth curves. The soundings posted on a chart are only a small subset of the soundings used to support compilation of the chart depth curves, but there still may be thousands of soundings on a single chart.

Soundings posted on a nautical chart can be separated into three basic types; prime soundings, background soundings, and limiting depth soundings. Prime soundings mark ocean bottom features which deviate significantly in depth from the bottom depth which would be expected based on linear interpolation between chart depth curves. Prime soundings tend to be distributed irregularly over a chart and are concentrated in areas of high relief. Because they serve as aids to safe navigation, prime soundings are usually selected with a shoal bias. To a chart user trying to navigate outside designated channels, prime soundings are the most important soundings on the chart. However, prime soundings are only a small percentage of the soundings shown on a chart.

Background soundings are selected to present a regular pattern of soundings over the entire chart. The desired pattern is triangular or rectangular with the spacing between soundings increasing with depth. Background soundings make it easier to estimate ocean bottom depth between widely spaced or convoluted depth curves. Although background soundings do not delineate significant ocean bottom features, particular background soundings are often selected because they do deviate from the depth, which would be expected based on linear interpolation between depth curves. And like prime soundings, background soundings are often selected with a shoal bias. Background soundings are usually the most numerous soundings on a chart.

Soundings which show the least depth encountered when following the deepest part of a natural channel or river are called limiting depths or controlling depths. Limiting depth soundings seldom account for more than a small percentage of all the sounding on a chart. 

THE CARTOGRAPHIC SOUNDING SELECTION PROGRAMS

The computer programs described in this paper were originally developed to select only prime soundings (ZORASTER, 1990), but they have been extended to select background soundings as well. Selection of prime and background soundings accounts for the largest part of the entire cartographic sounding selection process.

Depth curves plan a crucial role in both manual and automatic sounding selection. In our selection process the importance of each sounding is determined by how closely that sounding's depth can be estimated in interpolation between bracketing depth curves. By using depth curves to guide sounding selection, the automated selection process mimics the steps by which a cartographer manually selects soundings for display on a nautical chart.

Our sounding selection system incorporates a grid-based model of the ocean bottom. The ocean bottom model is initialized from depth curves and shorelines using a proprietary curve-to-grid transformation program. At each iteration of the sounding selection process, certain soundings which deviate from the current ocean bottom model are selected for chart display and the ocean bottom model is modified by a local adjustment procedure to honor those selected soundings. As soundings are selected for chart display, nearby soundings which have not yet been selected are eliminated from further consideration to avoid overcrowding of soundings on the final chart. The selection process stops when all soundings have been chosen for chart display or have been eliminated from consideration because they were near selected soundings.

INITIALIZATION OF THE OCEAN BOTTOM MODEL

The grid-based ocean bottom model used by the sounding selection program is initialized by a curve-to-grid transformation program which accepts as input digitized chart depth curves and shorelines. The depth curves can be produced by digitizing them off a paper chart, by manually or interactively contouring smooth sheet data, or by the use of a computer-contouring algorithm. The shorelines may be digitized off existing charts or collected from photogrammetric sources.

The curve-to-grid transformation program starts the grid initialization process by computing four different estimates of the ocean depth at each grid node. The four estimates for a target grid node are obtained by performing linear interpolation between bracketing pairs of depth curves found along each of four search profiles passing through the node. Search profiles are oriented along grid rows, grid columns, and grid diagonals, as shown in Figure 2. The four depth estimates at each grid node are averaged using a weighting function which emphasizes the depth estimate from the profile with the largest slope.

The use of search profiles in model initialization can be made very efficient, but it can leave small local anomalies in the ocean bottom model. The final step in model initialization is a smoothing process applying a two dimensional Laplacian convolution operator to eliminate those anomalies (SMITH and WESSEL, 1990). The convolution operator is constrained by the input depth curve levels so that all grid nodes of the smoothed model bell in the correct depth curve interval. This surface modeling process is similar to the program used by the United States Geological Survey to create 30-meter DEM models from digitized contour data (RINEHART and COLEMAN, 1988).

Linear interpolation along search profiles, combined with constrained Laplacian smoothing of the entire grid, produces an ocean bottom model which is linear between depth curves. This provides an initial reference model against which to compare soundings in order to decide which soundings should be displayed on a chart.

OCEAN BOTTOM SEGMENTATION

After the initial ocean bottom reference model has been created, the model along with the set of soundings available for selection are passed to the program that actually selects soundings for display. The first step in that program is to partition the soundings into segments corresponding to ocean bottom regions bounded by depth curves, shorelines or chart boundaries. Sounding selection will be performed independently in distinct ocean bottom segments. The method used to segment the ocean bottom model relies on an auxiliary grid the same size as the ocean bottom model grid. Segment numbers are assigned to nodes in the auxiliary grid using a raster-based, area fill technique derived from computer graphics (PAVLIDIS, 1982). Each sounding is assigned to an ocean bottom segment by finding its position relative to the auxiliary grid. At the same time sounds are assigned to ocean bottom segments, the levels of the two chart depth curves which bound each sounding are recorded.

SOUNDING SELECTION

After the initial ocean bottom model is established and all the soundings are assigned to ocean bottom segments, the sounding selection process can start. Based on the ocean bottom model, "residuals" are calculated at each sounding. Residuals are the difference between the true depth of the sounding and the depth of the current ocean bottom model at the same location:

RESIDUAL = (sounding depth - model depth).

Soundings shallower than the model will have negative residuals and soundings deeper than the model will have positive residuals.

When each sounding has been assigned a residual, the program selects one sounding for each ocean bottom segment by comparing the residuals of all the soundings in that segment. The program default choice is to pick the sounding with maximum absolute residual for each segment. The program user has three options of biasing the selection process in favor of shoaler soundings. The first shoal bias option involves multiplying all negative residuals by a constant factor larger than 1 before the absolute value calculation is performed. The second, and strongest shoal bias option entails controlling the selection process so that all possible sounding which are shallower than the current ocean bottom model are selected before any soundings which are deeper than the current model are selected. The third shoal bias is a modification of the second. For this last option, soundings deeper that the ocean bottom model can be selected, but only during every nth iteration, where n is usually 5 or more.

After a sounding is selected, soundings in a circular neighborhood around that sounding and in the same ocean bottom segment are eliminated from further consideration. This prevents overcrowding of soundings on the chart. The radius of the circular neighborhood is a function of the depth of the selected sounding and is calculated by a piece-wise linear "cut-out" function which is user defined. The cutout function is specified by picking cutout circle radii at each depth curve level. Normally the size of the cutout circles increases with sounding depth.

Once a sounding has been selected within each ocean bottom segment, the ocean bottom model within each segment is adjusted to reflect this new information. The adjustment process changes the depths at nearby grid nodes to smoothly integrate the depth of the selected sounding into the model. The change for any grid node near a selected sounding is determined by use of the adjustment function:

CHANGE = RESIDUAL * (1.0 + COSINE(PI*D/R))/2.

Where RESIDUAL is the deviation between the sounding and the ocean bottom model, D is the distance between the grid node and the selected sounding, and R is the range at which the adjustment function goes to 0. The adjustment function has 0 slope at the selected sounding at distance R from the selected sounding. In our sounding selection program R is a function of the depth of the selected sounding. For all our tests, R has been fixed at twice the radius of the cutout circle within which all nearby soundings are eliminated from consideration.

After the grid adjustment, sounding residuals are recalculated and again soundings are selected, based on their residuals, one for each segmented area of the ocean bottom model. This process of residual calculation, sounding selection, sounding elimination, and model adjustment is repeated until all soundings have been selected or have been eliminated because they were too near selected soundings.

At the start of the selection process residuals for most selected soundings are relatively large and the selected soundings are concentrated in parts of the chart where the bottom relief is greatest. These selected soundings are prime soundings. As the selection process continues, sounding residuals become smaller on average and the selected soundings begin to develop a regular pattern over the survey area. The soundings selected towards the end of the selection process are background soundings.

BOTTOM FEATURE DELINEATION

Adjusting the ocean bottom around each selected sounding helps capture the full detail of the ocean bottom, which can be depicted through the selected soundings. Assume, for example, that there is a sounding near a selected sounding with a residual of the opposite sign. Furthermore, assume that soundings is far enough away from the selected sounding not to be eliminated after the selection, but within the range of the adjustment function applied around the selected sounding. After the bottom adjustment the magnitude of the residual of the example sounding will increase, thereby increasing the probability that sounding will be selected for chart display. An increased probability of selection is desirable because the example sounding, and any other nearby soundings with comparable residuals, serve to delineate the size of the feature marked by the previously selected sounding. On the other hand, if such an example sounding deviates from the ocean bottom model in the same direction as the previously selected sounding and deviates by about the same amount, then the magnitude of its residual will be reduced by the adjustment process, making the example sounding less likely to be selected. A decreased probability of selection is desirable in this case because soundings with residuals in the same direction but with smaller magnitude add relatively little information about the shape of the ocean bottom.

ELIMINATION OF SOUNDINGS WHICH MIGHT OVERPLOT DEPTH CURVES

The density of soundings posted on a chart is reduced where the chart depth curves run close together. Knowledge about fluctuations in the ocean depth on either side of such steep areas may be important, but a navigator is unlikely to pay much attention to multiple soundings wedged between depth curves and possibly overplotting them. The curve-to-grid transformation program includes code which automatically marks grid nodes where the ocean bottom is steep enough to force depth curves to coalesce. These particular grid nodes are recognized in the sounding selection program and sounding near these nodes are not considered during the sounding selection process.

Even in relatively flat areas of a chart it is not desirable for depth curves to overplot selected soundings. If a particular sounding is important enough to include on a chart, then the depth curve should be broken or shaped so as to avoid overplotting that sounding. Our sounding selection system includes a program which marks sounding that would overplot depth curves when plotted at chart scale. These soundings can be eliminated from consideration before using the cartographic sounding selection program, or highlighted for special attention by the cartographer after the sounding selection process is completed.

ALGORITHM TESTING

The programs described in this paper have been implemented in FORTRAN 77 and tested on a DEC VAX 750 against data sets provided by NOS. The data sets included NOS charts and digital soundings from recent hydrographic surveys performed to update those charts.

The survey data provided by NOS for that part of NOS Chart 14832 shown in Figure 1 was processed using proprietary gridding, contouring, and curve-editing algorithms originally developed for use in the petroleum industry. Approximately two full man-days were required to compile depth curves from a smooth sheet prepared at 1/2 chart scale. (As part of this research effort we have developed a smooth sheet generation program to thin survey data to a density which would not cause overplotting on a smooth sheet. Details of that smooth sheet generation program will be published in a later paper.) The smooth sheet had approximately 5,000 soundings on it, about one-half the number of soundings provided in the original survey, and covered approximately three times as much river area as is shown in Figure 1. Most of the two-man days were spent interactively editing the depth contours generated automatically by the gridding and contouring code. The development of chart depth curves was a new experience for the authors of this paper, so a great deal of learning was involved in the interactive compilation process. We estimate that less than one full man-day would have been sufficient to complete the work if the operator had been a cartographer familiar with the interactive capabilities of our contour editing software.

The section of Chart 14832 presented in this paper is a navigable river channel, therefore for our fist test the soundings were selecting using the shoal first bias option. These are the results shown in Figure 1. As noted earlier, the selected soundings closely matched the soundings selected by manual techniques from this same survey. For comparison soundings were also selected for the same area using the selection bias option based on the maximum absolute sounding residual with negative residuals being multiplied by a factor 1.3 before the absolute value calculation was performed. This option selected more deep soundings for chart display. The results of this selection are shown in Figure 3.

 

 

Survey data provided by NOS covering a part of NOS Chart 11378, "Santa Rosa Sound to Dauphin Island," tended to support the depth curves previously shown on the cart. For that test case depth curves and shorelines were digitized off the chart and interactively edited to bring them into alignment with the new survey data. It took several iterations and at least two full man-days to modify the digitized depth curves into agreement with the new survey data. Again, we believe that a cartographer familiar with our contour editing software could have complete the process in a much shorter time period. Figure 4 shows soundings selected automatically for 1/2 of the test area. The soundings were selected using the modified version of the shoal first bias option that allowed the selection of deep soundings every sixth iteration of the selection process. The overall density and pattern of soundings shown in Figure 4 is similar to the density and pattern for the same area on the existing NOS Chart 11378.

The two tests discussed in this section and three other test sets provided by NOS contained between 9,000 and 14,000 survey soundings. In all cases less than 60 CPU minutes on the VAX 750 were required to generate smooth sheet data sets at 1/2 the final chart scale; identify soundings which would overplot depth curves; generate the initial ocean bottom models; and then perform sounding selection. The VAX 750 represents 12 year old computer technology and by a conservative estimate the same amount of computation would have required less than 5 CPU minutes on one of the state-of-the-art RISC-based workstations now being produced by SUN, HP and other computer manufactures.

DISCUSSION OF TEST RESULTS

The agreement between the soundings selected manually by NOS cartographers and the soundings selected by our programs provides strong encouragement for those who believe that cartographic sounding selection can be largely automated. Furthermore, the success achieved in the generation of smooth sheets and in the interactive generation and editing of depth curves from NOS data sets suggests that large parts of the hydrographer's work involved in chart compilation can be automated.

Once programs for cartographic sounding selection have been validated for use in chart production and maintenance, there are strong justifications for using them in chart compilation. The possibility of speeding up the chart compilation and revision process is only the most obvious justification. Another justification is the ability to perform automatic quality assurance during chart compilation.

Quality assurance can be supported by colour coding selected soundings according to their deviation from the ocean bottom model or by flagging and posting input soundings which fall into the wrong depth curve interval. Furthermore, standardization in chart design could be achieved by making program default parameters functions of the chart scale and the type of area being charted, such as river channel, open ocean, or harbor area.

One aspect of our selection process - the use of grid-based ocean bottom models - deserves further explanation. The alternative of using a triangulated irregular network (TIN) to model the ocean bottom from the depth curves was considered and rejected. TINS are difficult to build from contour or depth curve data; a TIN defined on a large set of depth curve vertices and selected soundings is likely to take up a very large amount of computer memory; and there was no simple way to adjust a TIN-based ocean bottom model within a circle around a selected sounding.

CONCLUSION

Based on the results obtained during this research effort, it appears that cartographic sounding selection can be performed successfully on a computer. The selections made by our programs are similar to those made by cartographers working from the same data sets. These results should encourage charting agencies to emphasize the use of computers in the compilation of nautical charts.

Acknowledgement

This material is based on work supported by the United State Department of Commerce under contract 50-DKNA-9-00195. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the Department of Commerce.

References

BELL, R.D., CHAPESKIE, R.E., CROWTHER, W.S., HOLMAN, KR., JACKSON, D.M., and ORAAS, S.R., 1989: Nautical Chart Production Using Digital and Interactive Compilation, Lighthouse, Vol 40, Fall, pp. 25-29.

BOSSLER, J.D., PENDLETON, D.L., SWETNAM, G.F., VITALO, R.L., SCHWARZ, C.R., APLER, S., and DANLEY, H.P., 1988: Knowledge-Based Cartography: The NOS Experience, The American Cartographer, Vol. 15, No. 2, (April), pp. 149-161.

JONES, R.W., 1986: Computer Assisted Sounding Selection for the Shipboard Data System III, Ocean 86, hosted by the Washington D.C. Section of the Marine Technology Society, Washington D.C., USA, Vol. 1, pp. 141-147.

KERR, A.J., 1985: Navigation Chart Design, The Journal of Navigation, Vol. 38, No. 1, (January), pp. 56-70.

LEPAGE, R. and HOLROYD, P.N., 1989: Adventures in Interactive Compilation, The International Hydrographic Review, LXVI(2), pp. 29-42.

LOOMIS, T.J. and KALL, D.J., 1990: Sounding Selection and Depth Curve Generation From a Topologically-Integrated GIS, Proceedings, U.S. Hydrographic Conference '90, Norfolk, Virginia, USA, pp. 98-107.

LUCKEY, S., PENDLETON, D. and WALTON, F. 1987: Knowledge-Based Cartography: Capturing Cartographic Expertise, Proceedings of the 1987 ASPRS-ACSM Annual Meeting, Vol. 3, pp. 154-161.

MACDONALD, G. 1984: Computer-Assisted Sounding Selection Techniques, The International Hydrographic Review, LXI(1), pp. 93-109.

PAVLIDIS T., 1982: Algorithms for Graphics and Image Processing, Computer Science Press, Rockville, Md., USA.

RINEHART, R.E. and COLEMAN, E.J., 1988: Digital Elevation Models Produced from Digital Line Graphs, Proceedings of the 1988 ASPRS-ACSM Annual Meeting, Vol. 2, pp. 291-299.

SMITH, W.H.F. and WESSEL, P. 1990: Gridding With Continuous Curvature Splines in Tension, Geophysics, Vol. 55, No. 3, (March), pp. 293-305.

ZORASTER, S., 1990: The Automatic Selection of Prime Soundings for Nautical Chart Compilation, Lighthouse, Vol. 41, No. 1, pp. 9-14.