J. Cent. South Univ. Technol. (2008) 15: 738-741
DOI: 10.1007/s11771-008-0136-2
Fast recognition algorithm of underwater micro-terrain based on ultrasonic detection
LUO Bo-wen(罗柏文)1, ZHOU Zhi-jin(周知进)2, BU Ying-yong(卜英勇)1, ZHAO Hai-ming(赵海鸣)1
(1. School of Mechanical and Electrical Engineering, Central South University, Changsha 410083, China;
2. School of Mechanical and Electrical Engineering, Hunan University of Science and Technology,
Xiangtan 411201, China)
Abstract: An algorithm was proposed to fast recognize three types of underwater micro-terrain, i.e. the level, the gradient and the uneven. With pendulum single beam bathymeter, the hard level concrete floor, the random uneven floor and the gradient wood panel (8?) were ultrasonically detected 20 times, respectively. The results show that the algorithm is right from fact that the first clustering values of the uneven are all less than the threshold value of 60.0% that is obtained by the level and gradient samples. The algorithm based on the dynamic clustering theory can effectively eliminate the influences of the exceptional elevation values produced by the disturbances resulted from the grazing angle, the characteristic of bottom material and environmental noises, and its real-time capability is good. Thus, the algorithm provides a foundation for the next restructuring of the micro-terrain.
Key words: underwater micro-terrain; ultrasonic detection; single beam; exceptional elevation values; threshold value; dynamic clustering
1 Introduction
Underwater micro-terrain measure is important for exploitation of seabed mine resources and construction of hydraulic engineering. Light-wave-based and electromagnetic-wave-based methods, such as the underwater laser detecting, the three-dimensional photography, and the electromagnetic wave exploring, etc, are not implemented due to the disturbances resulted from water turbid and electromagnetic wave caused by the mining testing machine[1-5]. Ultrasonic is not sensitive to impurities in water, especially for light wave and electromagnetic wave. The velocity of ultrasonic in water is 
of that of light wave, hence, ultrasonic equipment can realize short range measure, for example, the single beam bathymeter, the multibeam bathymeter, the side scan sonar and the bathymetric side scan sonar etc[6]. Therefore, a pendulum single beam bathymeter was developed after considering the specific surrounding and methods of exploiting deep-ocean cobalt-rich crusts. However, the useful echo signals will be possibly concealed by useless echoes that are caused by grazing angle, characteristic of bottom material and environmental noises, etc, resulting in some exceptional elevation values. Digital micro-terrain can be pseudo produced easily if it is restructured by reverse engineering[6]. In this work, a fast recognition algorithm was proposed to effectively eliminate the influences of the exceptional data.
2 Fast recognition algorithm
In the granted error scopes, for example, the area error is under 5%, the volumetric error is under 5% and the uneven height of plane is under 2 cm, the micro-terrain can be simplified into three modes: the level, the slope and the uneven. If all of the detected data are given to establish three-dimensional coordinate XYZ, the elevation values of each row can be fitted into three patterns with 2D geometric features, namely the horizontal line, the gradient line and the curve in plane XZ. The fast recognition algorithm was established based on the three 2D geometric features.
2.1 Content on algorithm
Let a row of a sample set regarded by the detected data be
X, Z=R
Definition 1 Supposing a sample subset A, there exist
, F(x, z)∈Ω, Ω∈A and |zi-zj|≤ρ,
ρ＞0, i, j=1, 2, 3, …
where ρ is the granted error scope of the projects.
Let n=Dim(A), if n/l≥ε, the sample set S will be regressed as a line in plane XZ; ε is a threshold value of pattern recognition.
Definition 2 Supposing a gradient 
, let plane XZ turn to plane X′Z′, and a new sample set S′ must satisfy
, i=1, 2, 3, …, l (1)
The sample subset A is replaced by the new one A′. If A′ satisfies Definition 1, the sample set S will be regressed a horizontal line in plane XZ when α=0, or be a gradient line. But if A′ does not satisfy Definition 1, the sample set S will be a curve.
If Definition 1 is associated with Definition 2, the function of horizontal line will be
,
and that of gradient line will be
.
The curve must be regressed by the interrelated nonlinear regression algorithms.
2.1.1 Fuzzy forced partition
When sample set S is projected to the coordinate axis Z, sample set B={z1, z2, z3, zk, …, zl} with one dimension will be gained. B is divided into c classes to make the random sample zk in sample set B entirely belong to a certain class. Its result can be expressed as a c×l matrix, namely U=(uik)c×l, therefore,
(2)
where Bi (i=1, 2, 3, …, c) is expressed as the ith class.
2.1.2 Nearest neighbor decision-making rules
For a question of c-classification, if each class has Ni samples (i=1, 2, 3, …, c), ωi will be
, k=1, 2, 3, …, Ni (3)
where 
is the kth sample of the ith class ωi. The discriminant function of the decision-making rule based on the discriminant function of Eqn.(3) is as follows:
If
, i=1, 2, 3, …, c, the decision-
making will be 
.
2.2 Realization steps of algorithm
Step 1 Sample set B will be obtained to form multi-clustering in one dimension space when sample set S is projected to the coordinate axis Z. If the there exist gradients, the new sample set B will be obtained because it is projected to the coordinate axis Z′[7-8].
Step 2 By searching max(z) and min(z) in sample set B, the error scope ρ is regarded as the clustering interval, and the similar coefficient of samples is obtained as follows:
Step 3 The clustering with the densest samples is regarded as the fast clustering via the similar coefficient λ, and the representative point of samples as the core of sample set.
Firstly, sample set B is divided into l subsets, namely
, and then a cutting matrix of fuzzy forced partition is established as follows:
(5)
where the cutting matrix Uλ/2=(uij)l×l, and it satisfies
By searching one row or one column of the cutting matrix Uλ/2 that has the most number of uij=1, if the sequence number of this row or column equals k, then sample zk is the representative point of the first clustering, namely the core of sample set[9-13].
Step 4 Some centers of clustering are created using sample zk as the core, namely
, n=1, 2, 3, … (7)
According to the rule of the nearest neighbor decision-making, the percentage of the sample in the scope of each clustering (Mn±1/2ρ) to the total samples is calculated. If some samples are at the boundary of two neighboring clustering, they will belong to the clustering nearer the core of sample set[14-16].
Step 5 The above-mentioned algorithm is used to confirm a threshold value ε via large numbers of trained sample sets, namely the percentage of the sample that belongs to the first clustering to the total samples. If the percentage of a certain to validated sample set is less than ε, this set will be taken as the type of the curve, otherwise, as the horizontal or gradient line.
3 Application
3.1 Brief depiction on method of data collection
Fig.1 shows the sketch map of pendulum single beam bathymeter in section XZ at laboratory, where the frequency of ultrasonic transducer is 500 kHz, and beam angle β is 1.5?. When the ultrasonic is emitted to the bottom of cistern, the returned or dispersed echoes are produced. The receiver circuits receive the emitted ultrasonic signals and the echoed ones in the same time. After the signals are received every time, the ultrasonic transducer swings for 0.5?.
Fig.1 Sketch map of pendulum single beam bathymeter
The detected data for each row have 40 points, and the result of each point was acquired via relativity analysis of the emitted signals and the echoed ones. At the same time, the running machines go ahead along with orbit in the course of detecting.
3.2 Result analysis of detecting data
Due to some large gradients, only the dispersed echoes are received by the ultrasonic transducer. At the same time, the ultrasonic transducer also receives the echo produced by the submarine reverberation and something suspended in water. When the dispersed echoes of a detected point are secreted in the ones of interferential elements, the maximal value of relativity can be produced, but this value is impossibly true. In this way, the exceptional data are brought out.
The hard level concrete floor, the random uneven floor and the gradient wood panel (8?) were detected 20 times, respectively, to get the row data in each experiment, namely 40 detected points. Fig.2 shows the 8th sample set detecting the hard level concrete floor, and Fig.3 shows the bar map of each clustering sample distribution obtained from this set computed by the above-mentioned algorithm at ρ=10 mm and λ=0.625.
Fig.2 Sample data of micro-terrain elevation value
Fig.3 Bar map of each clustering sample distribution
Table 1 lists the percentage of the first clustering (ρ=10 mm) of 20 experiments, where the results of the gradient sample data are obtained after coordinate conversion, just the same as those of the level data. So the determination of a threshold value by the data of Table 1 only needs to distinguish the line or the curve.
The trained samples of data of the level and gradient floor are analyzed statistically, and the results are shown in Fig.4, indicating that the trained approximately samples obey the normal distribution. The maximum likelihood estimation is used to estimate their unknown parameters, and the parameters with a confidence level of 95% are listed in Table 2.
According to 3σ (σ is the mean square error) rule, the samples obeying normal distribution, whose probability is 95.45%, must fall into the interval [μ-2σ, μ+2σ], where μ is the mean value, namely [60.407 6, 89.967 4]. In this work, 60.0 was selected as the threshold value. The data of uneven floor in Table 2 are taken as the validated samples, and it is found that they are all less than 60.0. Thereby Step 5 is right.
Table 1 Percentages of the first clustering of three types of micro-terrains at laboratory (%)
Fig.4 Bar map of trained samples of level and gradient micro- terrains
Table 2 Estimated parameters of trained samples obeying normal distribution at confidence level of 95%
4 Conclusions
1) After synthesizing the working characters of the pendulum single beam bathymeter and the reasons for the exceptional elevation values of micro-terrain, a fast recognition algorithm of three patterns of micro-terrain, namely the level, the gradient and the uneven, is put forward. It is helpful to effectively eliminating the influences of the exceptional data before the digital micro-terrain is restructured.
2) The algorithm is based on the dynamic clustering theory. Its flexible ability is very strong. The clustering center can be adjusted dynamically based on the detecting precision and the geometrical characteristics of micro-terrain.
3) In the experiment, a threshold value of 60.0% is obtained by the trained samples, so the algorithm is very exact, and its power of anti-jamming is very strong.
References
[1] XIA Yi-min, BU Ying-yong, MA Zhi-guo, ZHAO Hai-ming, LUO Bo-wen. Modeling and simulation of ocean mining subsystem based on virtual prototyping technology [J]. Journal of Central South University of Technology, 2005, 12(2): 176-179.
[2] STEINVALL O K, KOPPARI K R, KARLSSON U C. Experimental evaluation of an airborne depth-sounding lidar [J]. Optical Engineering, 1993, 32(6): 1307-1321.
[3] QIN Xuan-yun, BU Ying-yong. Study on multilevel model of optimized cut depth in real-time mining of ocean cobalt-rich crusts [J]. Ocean Engineering, 2005, 23(3): 99-104. (in Chinese)
[4] YAMAZAKI T, SHARMA R. Morphological features of Co-rich manganese deposits and their relation to seabed slopes [J]. Marine Georesources and Geotechnology, 2000, 18(1): 43-76.
[5] REN Zhi-liang, HUANG Yu-ying. A new method for underwater electromagnetic passive ranging [J]. J Huazhong Univ Sci Tech, 2001, 29(5): 89-91. (in Chinese)
[6] LIU Jun. Study of micro-terrain detection system of single-beam based on fractal theory [D]. Changsha: Central South University, 2006. (in Chinese)
[7] ANTONIOL G, CECCARELLI M, MARATEA A, RUSSO F. Classification of digital terrain models through fuzzy clustering: An application [C]// Proceedings of 5th International Workshop on Fuzzy Logic and Application. Heidelberg: Springer-Verlag, 2005: 174-182.
[8] HIZIR S, MUZAILIN A, KHALED B. The application of fuzzy clustering to satellite images data [J]. Statistical Methods for Biostatistics and Related Fields, 2006, 11: 357-366.
[9] MA Jun, SHAO Lu. An optimal algorithm for fuzzy classification problem [J]. Journal of Software, 2001, 12(4): 578-581. (in Chinese)
[10] ROUBOS H, SETNES M. Compact and transparent fuzzy models and classifiers through iterative complexity reduction [J]. IEEE Trans Fuzzy Systems, 2001, 9(4): 516-524.
[11] ABE S, LAN M S. A method for fuzzy rules extraction directly from numerical data and its application to pattern classification [J]. IEEE Trans Fuzzy Systems, 1995, 3(1): 18-28.
[12] PAL N R. BEZDK J C. On cluster validity for the fuzzy c-mean model [J]. IEEE Trans Fuzzy Systems, 1995, 3(3): 370-379.
[13] MIN S H, INGOO H. Dynamic fuzzy clustering for recommender systems [C]// Proceedings of 9th Pacific-Asia Conference on Advances in Knowledge Discovery and Data Ming. Heidelberg: Springer-Verlag, 2005: 480-485.
[14] HO S Y, LIU C C, LIU S. Design of an optimal nearest neighbor classifier using an intelligent genetic algorithm [J]. Pattern Recognition Letters, 2002, 23(13): 1495-1503.
[15] ABDEL-DAYEM A R, EI-SAKKA M R. Fuzzy c-means clustering for segmenting carotid artery ultrasound images [C]// Proceedings of 4th International Conference on Image Analysis and Recognition. Heidelberg: Springer-Verlag, 2007: 945-948.
[16] ZHAI Yu-mei, ZHAO Rui-xing. K-nearest neighbor nonparametric estimation bootstrap model for weather probability forecasting [J]. Journal of System Simulation, 2005, 17(4): 786-788. (in Chinese)
(Edited by CHEN Wei-ping)
Foundation item: Project(50474052) supported by the National Natural Foundation of China
Received date: 2008-01-07; Accepted date: 2008-03-15
Corresponding author: LUO Bo-wen, Doctoral candidate; Tel: +86-731-8836819; E-mail: luobow75@126.com
