A System for Automatic Cartographic Sounding Selection

SUI HAIGANG 1   ZHU XINYAN1  ZHANG ANMING2  WAN XIAOXIA3
1 Lab for Information Engineering in Surveying, Mapping And Remote Sensing (LIESMARS), Wuhan University, 129 Luoyu Road, Wuhan, Hubei,P.R.China, 430079 
2 Maritime Safety Administration of Tianjin , 31 DongTing Road,Tianjin,P.R.C,
3 The Printing School of Wuhan University, 129 Luoyu Road, Wuhan, Hubei,P.R.China,430079 

[Abstract]:  Soundings on nautical charts provide information about the shape of ocean bottom between chart depth curves. A single chart may have thousands of soundings posted on it. This paper describes a system for automatic cartographic sounding selection. In this system, a new algorithm for automated selecting soundings is developed. The algorithm is employed in such a way that it can guarantee (a)fast and accurate selecting sounding;(b) processing the circular depth curves;(c) solving the overplotting problems between depth curves and soundings;(d)keep selected soundings more ‘pretty’. The system is intensively tested using real data sets and its superiority has been revealed by the testing results.

[Key Words]: Sounding, Automatic Sounding selection, depth curves , Influence circle ,TIN

1.	Introduction
     Even if many of the steps involved in chart production have been automated, the compilation of nautical charts remains predominantly a task. One cartographic compilation task 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. 
Generally, 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 modeling or chart compilation tasks (Jones, 1986; MacDonald, 1984). Cartographic sounding selection is the process of selecting soundings for chart display to Convey information about the shape of the ocean bottom between depth curves. 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. So it is necessary to select a small number of suitable soundings which represent a large group of soundings adequately (S.R.Orass, 1975).
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. 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 pacing 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 base on linear interpolation between depth curves. Background soundings are usually the most numerous soundings on a chart. Soundings which show the least depths encountered when following the deepest part of a nautical channel or river are called limiting depths or controlling depths. Limiting depth soundings seldom account for more than a small percentage of all the soundings on a chart.
There are three major criteria (S.R.Oraas, 1975)involved in the selection of these soundings. First , in any small area of the chart, the shoalest sounding must be chosen. Second, the density of soundings must be such as to draw attention to dangerous area; that is, the spacing between soundings must decrease in shoal areas. This increase in density will lend to draw the navigator’s eye to that area. Third, the sounding pattern must be “pretty”. Here “pretty” means that the sounding pattern must have a relatively even spacing, the soundings must not lie on the shoreline or contours, and the soundings tend to support the other features on a chart.
Today, soundings are selected for chart display by tedious and costly manual methods. Most recent attempts to automate this task rely on data thining techniques that do not address the full complexity of the problem (Lepage and Holroyd,1989). More sophisticated automated selection techniques have been proposed, but they are all not very satisfactory. In this paper, the authors will present an algorithm for automatic cartographic sounding selection. 
The principal of the new algorithm
Before the begin of the new algorithm, let’s look through the procedure of sounding selection manually and try to learn something from it. The first thing the compiler does is to go over the sheet and sheet criteria in order to select the critical sounding. What is the critical sounding? Maybe the compiler themselves have difficulty in telling you. However, generally these critical soundings often represent the shoalest ones in a small area. It is necessary that all depth curves (that is essentially contour) intervals must have at least one sounding within them. Also if a depth curves shows a shoal area jumping into a deeper area, a sounding will be selected to support this. Some soundings may be critical because they show the existence of navigable channel. There are a number of other possible reasons for calling a critical sounding, but they will vary from compiler to compiler.
So the problem of producing a automatic sounding selection which perfectly imitates the present manual procedure is a very difficult one .The magnitude of the problem is not generally appreciated by hydrographers, compilers and the others who are not computer-oriented. The reason for this is that the human eyes is extremely good at discerning spatial relationships from a picture, so good in fact that determining these relationships. Unfortunately, the computer does not have a picture to work from but only a table of numbers.
Anyway if we want to select sounding automatically, then the following problems must be solved. The first problem is how to create the some kinds of background fill. In other words, we must be able to select soundings in non-critical areas in such a way that in general the shoalest soundings in any area is selected, a relatively regular pattern is produced and the spacing of the soundings varies according to the depth. The second problem is that we should create depth curves from the irregular soundings. This is important for the later work. The third problem is that we must adjust the relationship between the depth curves overplaying the soundings and those soundings overplayed by them. It is not desirable for depth curves to overplay selected soundings whether in deeper areas or flat areas. 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 overplaying that sounding. 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. The fourth problem is that we must process the circular depth curves that do not have soundings inside them. That means when selecting soundings we should consider the circular depth curves or process them after selecting process is finished.
Now, for these problems, we should put forward some ideas for solving them and this is the theory base of our algorithm. For the first problem, we introduce the term “influence circle” which means only the shoalest sounding will be chosen in all the soundings inside it and others will be eliminated. We employ two lists,one is the raw list which contains all the origin soundings, the other the selected list which contains the selected sounding. Then we sort the whole soundings by depth, the  shoalest sounding first. And the sorted result will be put inside the raw list. For one sounding inside it, the all soundings inside the influence circle whose center is this sounding should be checked and compared in order to select the shoalest sounding .Put this shoalest sounding into the selected list and update the raw list and the select list. In order to accelerate the search procedure, here we use the gird index. 
     As to the second problem ,here we use the TIN (Triangular Irregular Network) for producing depth curves. There are many algorithms forming TIN from irregular points (Victor J.D,1993, ZhiLin,Li,1990). Because of the excellent property of Delaunay triangulation, the Delaunay triangulation method is therefore employed here to implement these requirements. With the sophisticated algorithm, it is ensured to have high efficiency and good reliability. From TIN to depth curves, essentially this is the interpolation process. About Interpolation from TIN to contour there are many books and articles(Wang Zhizhuo,1979; Zhang  Zuxun 1996 etc. ).
For the third problem , the relationship between the soundings with the depth curves must be conformed.In fact,it requires that we make a search and compare among all the soundings and the depth curves. This is not very difficult. But it consumes much time. Again we employ the index mentioned previously for accelerate the speed. Another thing we don’t forget is that soundings here have their size and they are not single points.
As for the fourth problem, it is not complex. What we must do is just to readjust the selected soundings under considering the circular depth curves. This can be finished after the sounding selection process is completed. The operation judge the relationship between the soundings and the circular depth curves employed here is the known Polygon-Contain Algorithm.

The implementation of the new algorithm

In section 2, we discuss the principal of the new algorithm. But it is not very clear and how to complete the algorithm is still vague. So in this section, we will give the procedure of the new algorithm step by step. And the procedure is the following:
1).	Building index. That is, part the whole data set into n*m cells. The n value and m value are computed by the data envelope and the influence circle . For example, the width and the height of the data envelope is W and H separately, the radius of the influence circle is R, then we have:
                      ( 1 )
By this kind of index, we can find some values quickly.
Souding Select process. The radius of the influence Circle can be defined as :
       ( 2 )
here ,R is the radius of the influence circle , S is the sounding value ,a,b,c is defined by the user. From formular (2) it can be seen that the sounding is more deeper,the influence Circle is larger.
Step 2 can be divided into the following parts:
a.  Prepare the two lists: one is the raw list ,the other is the selected list.
b Sort the whole data set by depth ,the shoalest sounding first.And put the sorted result into the raw list .
c The first sounding in this list (the shoalest one) is selected and placed in the selected sounding list.
d From this sounding ,we use the index to search the all the soundings include the infulence circle whose center is this sounding. Eleminate other soundings except this one from the raw list..
e Examine the next sounding in the updated raw list and repeat step d until all the soundings in the raw sounding list is empty.
Creating TIN from irregular soundings by the Delaunay Triangulation method.
Interpolating depth curves(contours) from TIN..using defined contour interval :
Processing the circular depth curves. Resort the whole soundings and put the sorted result into the raw list.Searh all the circular depth curves and using the Polygon-Contain algorithm to judge the relationship between the soundings and the circular depth curves.
And readjust the selected list.
Solving the overplotting between the depth curves and the soundings. As the mentioned in the previous section ,This is the procedure of search and judge.Find all the overplotted soundings and highlight them.

It should be pointed that for obtaining a good result data proprocessing (data conversion etc.) and data postprocessing such as the depth curves must be modified because of the change of sounding values and so on. are necessaray.Fig 1 is the flow chart of the new algorithm.

4.System implementation

Based on the results obtained by this algorithm, it appears that cartographic sounding selection can be performed successfully on a computer. The selections made by the new algorithm are similar to those made by cartographers working from the same data sets. This algorithm has been used in the GIS software (GeoStar) that is developed by the GIS Center at Wuhan University for the project cooperated with the National Ministry of Communications and the Legend Company. In this section, a brief discussed on the system components will be given.
The system consists of the following core components:
A pre-processing module to convert outer data into the system, remove gross errors of soundings, and so on;
A module to build TIN and interpolate depth curves from TIN from thousands of irregular soundings.
A basic module to select soundings automatically;
A module to process the overplotting between depth curves and soundings, to process the circular depth curves.
A post-processing module to keep more pretty soundings and to do other tidy work.
An example is shown as Fig 2.The experimental data comes from Dalian Port.

5.Conclusions
This paper describes the automated selection of thousands of soundings. The principle and procedure of the new algorithm employed is given; and the main components of the system are summarized.  
From theoretical point of view, the technique described in this paper guarantees (a)fast and accurate selecting sounding;(b) processing the circular depth curves;(c) solving the overplotting problems between depth curves and soundings;(d)keep selected soundings more ‘pretty’
What should be developed in the future is how to accelerate the speed further and how to allocate the sounding more “pretty”.

6. References
Jones,R.W, Computer-Assisted Sounding Selection for the Shipboard Data System III, Oceans 86,hosted by the Washington D.C.Section of the Marine Technology Society,Washington,USA,1986,Vol.1,pp.141-147.
MacDonald.G, ComputerAssisted Sounding Selection Techniques, The International Hydrographic Review, 1984, LXI (1), pp.93-109.
S.R.Obaas:Automated Sounding Selection, The International Hydrographic Review ,Monaco, 1975,LII(2),pp.103-115.
Colin WARE etc, A system for cleaning high volume bathymetry,The International Hydrographic Review,Monaco,1992,LXIX(2),pp.74-94.
Victor J.D.Tsai: Delaunay triangulations in TIN creation::an overview and a linear-time algorithm, IJGIS,1993,Vol 7,No.6,pp.501-524.
Lepage,R.and Holroyd,P.N, Adventures in Interactive Compilation, The International Hydrographic Review,1989,LXVI(2),pp.29-42 
Li,ZhiLin, Sampling Strategy and Accuracy Assessment for Digital Terran Modelling, Ph.D Thesis, The University of Glasgow,1990.
Wang, Zhizhuo,The principal of Photogrammetry, Beijing, Surveying and Mapping Press , 1979。
Zhang, Zuxun, Zhang,Jianqing,Digital Photogrammetry，Wuhan,Wuhan Technical University of Surveying and Mapping Press, 1996。

Processing the circular depth curves

 Interpolating depth curves from TIN

    Sounding selection Process

  Creating TIN from irregular soundings 

  Solving the overplotting problem

    Building Sounding index 

Fig 1  The flow chart of the new algorithm.empolyed in the system

Fig 2  An example of sounding selection(Sounding with blank color is selected and  those with 
blue color is compressed ).