Fuzzy Application Library/Technical Applications/Sonar Systems
Fuzzy Technology Implemented in Sonar Systems
Anton Kummert, Atlas Elektronik GmbH, D28305 Bremen, Germany
Abstract
In this paper, applications of fuzzy algorithms in the domain of sonar systems are introduced which have been implemented in the latest generation of Atlas sonar equipment. The aim has been to provide an insight into the solution of problems from an applicationoriented point of view. Classification of DEMON spectra and automatic target tracking by means of fuzzy systems are introduced and demonstrated with examples. A short introduction to fuzzy technology is also given which supports the understanding of the algorithms presented.
I. Introduction
Modern techniques such as fuzzy algorithms are beginning to influence the design of sonar signal processing systems. The scope of this paper is not the presentation of new theoretical results in this area but an introduction to problems where such modern methods have been successfully applied. In other words, the applications of fuzzy theory discussed in Sections III and IV have been implemented in the latest sonar systems of Atlas Elektronik.
This paper is devoted to two sonar applications of fuzzy theory. The first is concerned with the automatic detection of the propeller shaft rate and number of propeller blades of ships and submarines by analysis of the DEMON spectrum. The second application is an automatic target traking system which incorporates two fuzzy modules. In particular, the main component of the socalled "traking filter" is itself a fuzzy system.
Fuzzy logic and the method of approximate reasoning led to new concepts in control theory and in the design of expert systems. These concepts imitate human thought processes better than do conventional methods. Besides the abovementioned applications, important notions from fuzzy theory are explained which are needed for the understanding of the fuzzy algorithms considered. Rulebased fuzzy systems can be used if human expert knowledge is available which can be expressed in the form of ifthen rules.
II. Basic Concepts of Fuzzy Theory
Before the applications of fuzzy theory in sonar systems introduced below can be discussed in detail, some basic concepts of this theory have to be considered. Those readers who are familiar with fuzzy systems can skip this section.
The efficiency of knowledgebased expert systems depends on the degree to which human knowledge can be reproduced. Classical mathematical logic, which is the basis of conventional inference machines, can formalise human knowledge and make it computable via algorithms to a very restricted degree only. To overcome the problems of binary logic, the theory of fuzzy logic was developed by Lotfi A. Zadeh [1]. He introduced fuzzy sets in order to describe and process inexact and incomplete data, which is often encountered in real situations. Since fuzzy logic is capable of dealing with linguistic information, it is ideal for serving as a basis for knowledgebased systems.
In contrast to classical logic, which knows only two crisp truth values, yes or no, true or false, 0 or 1, the concept of fuzzy logic is based on socalled "membership functions", which can take arbitrary values from the interval [0,1]. The membership function describes the degree to which an object belongs to a certain set. Large lists of references to the subject "fuzzy" can be found in [2]  [4]. Moreover, further important notions from the field of fuzzy systems which are beyond the scope of this paper are discussed in these publications.
Let A, for example, be the set of all possible numbers of spots on a die; we can then define the set "high number of spots" by means of a membership function. In the case of classical logic, the corresponding membership function is depicted in Fig. 1 where only the two crisp values 0 and 1 are admissible. In contrast to this, the fuzzy set "high number of spots", shown in Fig. 2, coincides much better with the human concept of "high", since smooth transitions between membership and nonmembership are possible.
Fig. 1: Crisp set "high number of spots"  
Fig. 2: Fuzzy set "high number of spots" 
The membership function is the essential component of a fuzzy set. Thus, the operations "intersection", "union" and "complement" of fuzzy sets are defined via the membership functions of the sets involved. The number of operators proposed in the literature is large. The reason for the variety of definitions for the operations "AND" (intersection) and "OR" (union) is the contextdependent way in which these operations are performed in human thinking. The choice of the appropriate operator is not trivial in practical situations and needs much experience and a proper analysis of the underlying problem.
Fuzzy inference is the most important operation in fuzzy expert systems and fuzzy controllers. In order to clarify this type of operation we first have to introduce the notion of "linguistic variable". A linguistic variable is a variable whose values are sentences in a natural language. The meaning attached to the values of a linguistic variable are fuzzy sets. This abstract explanation can be illustrated by the following example. We define a linguistic variable "distance". As the domain of interest (universe of discourse) we consider distances between 0 and 100 km. The linguistic variable "distance" can take as values the expressions {very near, near, medium, far, very far}. These expressions are the names of fuzzy sets whose membership functions are depicted in Fig. 3.
Fig. 3: Linguistic variable "distance" One of the essential operations of a fuzzy algorithm is inference. (large) 
The underlying knowledge is
represented by rules:
Rule 1: If
X_{1} = A_{11} ... and X_{i} = A_{1i} ... and X_{n}
= A_{1n} then Y = B_{1}
.
.
.
Rule m: If X_{1} = A_{m1} ... and X_{i}
= A_{mi} ... and X_{n} = A_{mn} then Y = B_{m}
X_{1},...,X_{n} and Y are linguistic variables, A_{1i},...,A_{mi} are possible values of the variable X_{i}, i = 1,...,n, and B_{1},...,B_{m} are possible values of the variable Y.
There exist different types of fuzzy inference ([2] and [3]) which can be divided into the following categories:
The terms approximate and plausible reasoning describe techniques which should not be confused with those used in probabilistic concepts. If the MAXMIN inference is used, then the rules are supposed to be absolutely true, i. e., the consequent term is true to that degree to which the antecedent term is fulfilled. In contrast to this, if approximate reasoning is applied, then not every rule is supposed to be absolutely true. For every rule there is a corresponding number from the interval [0,1] which represents the degree of confidence in this rule (0 = no confidence, 1 = full confidence). If we operate a fuzzy system, this rule weight is taken into account. If we consider plausible reasoning, then we try, on the basis of additional information, to deduce implications which are not given explicitly.
The mechanism of approximate reasoning will be explained in the following. General fuzzy systems can be described by Fig. 4. Essentially, they consist of blocks of the types "fuzzification", "rule base", and "defuzzification", which are interconnected. The interfaces with the environment are the fuzzification and defuzzification blocks. The expression "fuzzification" describes the conversion of a crisp value s into a fuzzy set with the special membership function depicted in Fig. 5. The expression "defuzzification" describes the conversion of a fuzzy set into a crisp value. The latter is often defined as the abscissa of the center of gravity of the area under the membership function of the fuzzy set considered (see Fig. 6).
Fig. 4: General form of a fuzzy system (large)  
Fig. 5: Membership function of acrisp value (large)  
Fig. 6: Defuzzification (large) 
The third element, the rule base, is depicted in Fig. 7, which comprises the socalled "production rules". The output value and the input values of a rule base are membership functions of fuzzy sets. To the output and to each input of a rule base we assign a linguistic variable (designated here as 0 and I_{1},..., I_{N} ). The elements of a rule base, the production rules, have already been introduced. The computational method with which such a rule base is processed is called "fuzzy inference".
Fig. 7: The rule base As can be seen from Fig. 4, the input of a rule base can either be connected to the environment by means of a fuzzification element or directly to the output of another rule base. Consequently, the input values of a rule base are membership functions. This is also the case if the input is directly connected to a fuzzification block, since in this case a membership function of the type depicted in Fig. 5 is involved. The general mode of operation of a rule base is explained in detail in the literature (see e. g. [3] and [4]). 
Naturally, different types of fuzzy algorithm have been proposed in the literature and it would be beyond the scope of this paper to give an overview. However, fuzzy concepts which seem to be distinct at the first sight often differ only with respect to terminology and are based on similar ideas. For instance, fuzzy associative memories, which are dealt with in [4], are nothing other than rule bases as defined above. Hence, our considerations have been restricted to those concepts which are of relevance for the applications introduced in this paper.
III. Detection of Propeller Shaft Rate and Number of Blades
Passive sonar systems are designed for the reception of underwater sound emitted by unknown vessels. These sound signals are either active pulses or engine noise superimposed on ambient noise. Some of these signals are amplitudemodulated, such as the sound caused by the cavitation of a ship's propeller. The characteristic frequencies of the modulating signal will be the topic of our further considerations.
The sound signals received by a passive sonar system are, on the one hand, used for the determination of target bearing and, on the other hand, for the classification of the sound emitter. One of the components of such a system demodulates the broadband noise signal for the detection of low frequency components of the envelope signal. In this context, the spectrum of the envelope signal (demodulated signal) plays an important role. This component of the signal processing algorithms of a passive sonar system is called DEMON analysis (detection of envelope modulation on noise). In this section, we examine how fuzzy technology has been applied to DEMON processing.
DEMON analysis requires the demodulation of the broadband receiver signal, and is often performed by processing the magnitude of the signal with a lowpass filter, and normalising the resulting spectrum to obtain a constant spectral noise background. The steps for the computation of the DEMON spectrum are summarized in Fig. 8.
Fig. 8: Computation of the DEMON spectrum (large) 
Human experts usually are able to determine the propeller shaft rate and the number of propeller blades of a detected vessel by analysing the waterfall representation of the DEMON spectrum (see Fig. 9). Our aim was to replace the human expert with a fuzzy system in order to automate this classification task.
Fig. 9: Example of the waterfall representation of a DEMON spectrum (large) 
Before the corresponding fuzzy algorithm is introduced, we shall examine the features of the DEMON spectrum which enable the classification task defined above to be accomplished. As already mentioned, cavitation caused by the ship's propeller produces intensitymodulated sound signals. Mathematically, such a signal can be described by
(1) 
where the quantities i _{*} f_{s} are modulation frequencies and n(t) is a broadband noise signal. In other words, the amplitude of the noise signal n(t) is modulated by a set of harmonics. Usually, the amplitudes A_{i} of these sine signals are much smaller than 1. The determination of the basic frequency f_{s} from the time signal s(t) is one of the tasks of the DEMON analysis.
The basic frequency f_{s} in Hz corresponds to the propeller shaft rate expressed in revolutions per second. Hence, f_{s} has to be determined. Furthermore, the number of propeller blades can be determined from the differences in height between the amplitudes A_{i}. More specifically, let B be the number of propeller blades; the amplitude of each Bth characteristic frequency line is then dominant. In Fig. 10 an example is given which implies B = 3. For convenience of notation we define the frequency
(2)  f_{B} = B f_{s}. 
We have developed a fuzzy algorithm that determines the two parameters f_{s} (propeller shaft rate) and B (number of propeller blades). DEMON spectra can become arbitrarily poor in practice so that even human experts would not be able to classify them correctly. Hence, it is desirable that the quality of the underlying DEMON spectra be indicated by the sonar system. A factor is provided by the fuzzy algorithm which makes it possible to judge the degree of confidence in the displayed values for f_{s} and B. Such a feature is of great importance for an operator, since nonsensical values can be suppressed by looking at the associated confidence factor.
Fig. 10: Possible distribution of the A_{i} for B = 3 
The algorithm itself is composed of conventional procedures (such as searching for maxima, computing distances between frequency lines, or determining the median of a set of numbers) and fuzzy modules. By using conventional techniques, approximately twenty candidates for f_{s} are determined. The details of this procedure are of no interest within the context of the topic of this paper.
In a second step, these twenty possible values for the shaft rate are tested by a fuzzy module which calculates a confidence value for each of them. Each of these confidence values is combined with a further confidence factor which has already been determined in the first step. The latter depends on a comparison between the frequency spacing of the largest lines of the DEMON spectrum and the candidate value for f_{s}. The propeller shaft rate candidate with the greatest resulting confidence factor is accepted and displayed.
The possible values for the number of propeller blades 3, 4, ..., 9 are multiplied by the value just determined for f_{s}, which provides seven candidates for f_{B} (see eq. (2)). These seven candidates are tested by a fuzzy module which calculates a confidence value for each of them. The candidate for f_{B} with the greatest confidence factor is accepted. Finally, the global confidence factor already mentioned is derived from the two confidence factors which have been associated with the accepted values for f_{s} and B. The number of propeller blades results from the relation B = f_{B}/f_{s}, where f_{B} and f_{s} are the two accepted values.
The two fuzzy systems mentioned above are depicted in Figs. 11 and 12. Obviously, they correspond to the general structure discussed in the last subsection. Both systems are connected to the environment via three input ports and one output port.
Fig. 11: Fuzzy system 1 (large)  
Fig. 12: Fuzzy system 2 (large) 
Let f_{s}^{(k)}, k = 1,...,K, be the candidates for f_{s}, f_{i}, i = 1,...,20, the frequency locations of the twenty strongest frequency lines of the DEMON spectrum, and A_{i}, i = 1,...,20, the corresponding amplitudes; we then define
(3) 
In other words, d_{ik} is a measure that indicates whether f_{i} can be interpreted as a harmonic of f_{s}^{(k)}. For each candidate f_{s}^{(k)}, the corresponding confidence factor is the mean of the output values c_{ik} of the fuzzy module, where i = 1,...,20 and k is fixed.
Similarly, f_{B}^{(k)}, k = 1,...,7, are the candidates for f_{B}, f_{i}, i = 1,...,4, the frequency locations of the four strongest frequency lines of the DEMON spectrum, and A_{i}, i = 1,...,4, the corresponding amplitudes. The distance
is a measure that indicates whether f_{i} can be interpreted as a harmonic of f_{B}^{(k)}. For each candidate f_{B}^{(k)}, the corresponding confidence factor is the mean of the output values w_{ik} of the fuzzy module, where i = 1,...,4 and k is fixed.
The rule bases contain sets of production rules which are not listed here. Examples are:
If d_{ik} = small and A_{i} = medium and f_{S}(k) = medium then c_{ik} = very high.
If d_{ik} = large and A_{i} = small and f_{S}(k) = medium then c_{ik} = medium.
For the above rules, the membership functions of the fuzzy sets "very low", "low", ..., "very high" of the linguistic variable c_{ik} are given in Fig. 13.
Fig. 13: Membership Functions (large)  
The two fuzzy systems have been designed by using the fuzzy development tool "fuzzyTECH 2.0" which incorporates a Cprecompiler. This means that production rules and membership functions can be edited by using a windowbased shell and that the resulting system is converted into C source code automatically. This source code can be compiled and linked into an executable file on the final hardware (signal processor of the sonar equipment). Hence, if powerful fuzzy development tools are available, the design and implementation of fuzzy algorithms are often easier than the implementation of conventional algorithms.
An example of the performance of the algorithm described above for the detection of fs and B from DEMON spectra is given in Figs. 14  17. In Fig. 14 an example of the waterfall representation of DEMON spectra is given where the intensity of the tracks obviously decreases with time. Note that, in contrast to the usual waterfall representations, the time and frequency axes have been interchanged to make the comparison with Figs. 15  17 easier.
The corresponding curve of the global confidence factor, which has been determined by the fuzzy algorithm, is shown in Fig. 15. And indeed, the decrease of the quality of the DEMON spectra with time is indicated by this curve. The propeller shaft rate in revolutions per minute and the number of propeller blades detected by the fuzzy systems are depicted versus time in Fig. 16 and Fig. 17, respectively. The correct values are 900  920 RPM and 3 blades, respectively. This performance is much better than that which has been achieved by the nonfuzzy algorithm yet used in Atlas sonar systems.
Fig. 14: Example of the waterfall representation of DEMON spectra (large)  
Fig. 15: Curve of the quality factor (large)  
Fig. 16: Detected propeller shaft rate / correct value » 900 RPM (large)  
Fig. 17: Detected number of propeller blades / correct value = 3 blades (large) 
IV. Automatic Target Tracking (ATT)
Automatic target tracking is an essential requirement for surveillance systems employing multiple sensors, together with computer subsystems, to interpret an environment that includes both true targets and false alarms.
In the following, we describe a fuzzy algorithm for the detection of tracks (targets) in a bearing/time record (BTR). For doing this, a socalled "tracker" is initialised for each observed target which tries to follow its movement. If a tracker is not initialised by a false alarm, then its trajectory should correspond to a track in the BTR considered. Essentially, this task is composed of two central features. The pairing of observations to trackers, and the prediction of the bearing of alreadydetected targets for the next time step. The latter is done by using socalled "tracking filters". Furthermore, the initialised trackers are judged by means of a confidence factor, which is also used for their termination. As will be shown, both the tracking filter and the evaluation of the trackers can be realized by fuzzy systems.
The basic data for automatic target tracking in sonar systems is the integrated magnitudesquared response of a scanning beam in a noise field which contains moving targets. This energy versus bearing representation will be called a "bearing spectrum" and is computed for consecutive time frames of length T (T depends on the integration time). In other words, after time T (e.g. one second) a new bearing spectrum can be analysed. The computation of bearing spectra can be done in several ways; however, a detailed discussion of these various methods would be beyond the scope of this paper.
Usually, the local maxima of the bearing spectra are determined and the corresponding bearings are interpreted as the locations of possible targets. In most cases, preprocessing of the bearing spectra is necessary before local maxima can be searched for. Otherwise, too many false alarms would be accepted. Nevertheless, some of the observations are due to noise and have to be suppressed during the actual tracking phase.
The detection of tracks in the waterfall representation of the bearing spectra can be made more difficult by gaps in the tracks, local maxima of the bearing spectrum which have been caused by noise, and tracks which are not smooth curves but fluctuate randomly around the ideal curve.
The tracking of detected targets is made more difficult by the crossing of tracks. The following situations can occur:
In practice, it is difficult to decide whether case 1 or case 2 is present since the corresponding patterns in the waterfall representation are very similar in both cases. Hence, further features have to be taken into account in order to make these two scenarios distinguishable. An example is given in Fig. 18 where on the lefthand side the touching of two tracks is shown and in the middle the crossing of two tracks. However, these differences are not visible in Fig. 18. The white areas next to the tracks are due to the fact that only local maxima have been displayed.
Fig. 18: Example of the waterfall representation of bearing spectra (large) 
The automation of the target detection and tracking process is the task of the fuzzy system introduced below. It is able to distinguish between the two cases "crossing of tracks" and "touching of tracks". Short gaps in tracks are bridged automatically and the end of a track is recognised within a short time. Naturally, in the case of a poor signaltonoise ratio, tracks are often blurred and false alarms can consequently occur. Hence, a confidence factor is assigned to each initialised tracker in order to improve the meaningfulness of the displayed results.
In general, batch or sequential approaches for automatic track detection could be considered. In the first case, the bearing spectra could be stored for a certain time interval and afterwards analysed in one step. In other words, the available threedimensional data record (amplitude versus bearing versus time) could be processed with known pattern recognition algorithms. However, a considerable lag between signal reception and signal analysis would be the result since a time record of approximately 510 minutes should be available. In order to be able to respond to the current situation instantaneously, such an approach cannot even be considered. Hence, the sequential approach has been adopted which is outlined in the following. After an initialization procedure has been executed, several possible tracks have been localised, i. e., trackers have been initialised. Their current bearing is stored. By taking into account the latest history of the trackers, the respective bearing for the next time step is predicted by means of tracking filters. Usually, the latter are realised by Kalman or a_filters. In our approach, however, a fuzzy tracking filter has been realised. As soon as observed data is available for the new time step an observation to tracks assignment has to be performed (data association). If observations occur which cannot be assigned to one of the trackers already initiated, they are considered as the beginning of possible new tracks.
Conversely, if no observation can be associated with a tracker already in existence, then penalty points are added to a score. Two different confidence measures are assigned to each tracker. The local confidence factor describes the short term behaviour and the global confidence factor takes into account the history of the tracker. More precisely, the data association is not performed exclusively, i.e., one observation can be assigned to several trackers in the case of crossings. However, different trackers are not treated equivalently with respect to the assignment of observations. The order in which trackers are processed depends on their current ranks. The latter are newly computed after every 16th time step and depend on the counts of the local confidence factors. These local confidence factors are also newly computed after every 16th time step and additionally increase or decrease the global confidence factors. The global confidence factor of each tracker influences the size of the corresponding gate for data association and terminates the tracker if it drops below a given boundary value. In other words, it represents a measure of the quality of the respective tracker. The computation of the local confidence factors is done by a fuzzy module.
The data association itself obeys the following rules. All existing trackers are processed in the order of their ranks. The tracker currently being considered is associated with that observation from the interior of a gate around its location which has the greatest amplitude. The assigned observation is marked. Observations which cannot be assigned to a tracker already in existence are considered as the locations of new tracks. The tracking filter predicts the bearing of each tracker for the next time step. The main component of the tracking filter is a fuzzy system. The further details of the tracking algorithm are of no interest within the context of this paper. Only the two fuzzy systems should be examined in more detail.
The fuzzy tracking filter estimates the momentary bearing rate of each of the targets already detected and predicts the corresponding bearing for the next time step (see Fig. 19). In other words, the predicted bearing results from
(4)  x_{p}(k+1) = x_{p}(k) + T v(k), 
where T is the sampling period. The bearing rate v(k) is nonlinearly computed from e(k), the difference between predicted, x_{p}(k), and observed bearing, x_{o}(k), for the time instant k.
 Fig. 19: The tracking filter(large) 
The main component of the tracking filter is the rulebased fuzzy system which has the following input signals:

prediction error e(k)
 change of e(k)
 lowpass filtered bearing rate v(k).
The use of fuzzy systems for tracking problems has been proposed in [4].
The second fuzzy module computes the increase or decrease of the local certainty factor for each active tracker to which an observation has been assigned. It consists of two rule bases and has the following input signals:

prediction error e(k) (difference between predicted and observed bearing),
 rank of the assigned observation (position in a list of all
observations sorted with respect to the corresponding amplitude of the bearing spectrum),
 magnitude of the difference between the rank of the assigned
observation and the rank of the observation assigned in the previous time step,
 magnitude of the difference between the numbers of the frequency bands
in which, respectively the present and the previous observation have been localised (the
bearing spectrum is computed for different frequency bands of the array signals).
The first input signal is a measure for the likelihood that the assigned observation is indeed the continuation of the track. A low rank of an observation indicates that it might be a false alarm. The third and fourth input signals are measures relating to the continuity of the observations.
Rule base 1 (cf. Fig. 20) combines input signals 3 and 4 to an intermediate quality variable q which is fed to rule base 2. The latter computes from input signals 1 and 2 and the intermediate variable q a number v Î [1, 1], which is added to the local confidence factor. Naturally, the whole set of production rules contained in the rule bases cannot be listed here. Examples are:
Fig. 20: Structure of the fuzzy system (large) Rule base 1: If input 3 = high and input 4 = high then q = low. If input 3 = low and input 4 = medium then q = medium. . . . Rule base 2: If input 1 = high and input 2 = high and q= low then v = very low. If input 1 = high and input 2 = low and q = medium then v = medium. . . . 
Many trackers (usually started by false alarms caused by noise) will be terminated shortly after initialization. Hence, only those trackers whose respective global confidence factor has crossed a certain boundary value will be considered as true targets and the corresponding bearing versus time curves (tracks) will be displayed. All other trackers are suppressed.
In Fig. 21, a simulated bearing versus time scenario (randomly fluctuating tracks with superimposed noise) is shown which contains (from left to right) the following situations:

a track which originates at the righthand side of the scenario,
 the touching of two tracks,
 the crossing of two tracks,
 a track with gaps,
 the touching of two tracks with a long common path,
 the origin of the first track.
The corresponding tracks detected by the automatic tracking algorithm described above are shown in Fig. 22. Connected branches of a track are marked with the same number which distinguishes between the situations "crossing" and "touching". Obviously, the different situations have been recognised correctly by the algorithm. Only the fifth situation (touching of two tracks with long common path) produced problems in the upper part. Due to the long common path, one of the two trackers had terminated before the bifurcation had been reached. Therefore, a new traker was initialized for the left branch of the bifurcation.
Fig. 21: Example of the waterfall representation of bearing spectra (large)  
Fig. 22: Detected tracks (large) 
V. Concluding Remarks
In this paper, rulebased fuzzy systems for classification problems and automatic target tracking have been discussed. Furthermore, a short introduction to fuzzy theory has been given. It schould be noted that the abovementioned applications of fuzzy logic have been already implemented in the latest generation of Atlas sonar equipment.
Acknowledgement
The author is grateful to the anonymous reviewers for their valuable comments and suggestions.
Literatur
[1]  L.A. Zadeh, "Fuzzy Sets", Information and Control, vol. 8, pp. 338  353, 1965. 
[2]  H.J. Zimmermann, "Fuzzy Set Theory and its Applications", Boston: Kluver, 1991. 
[3]  T. Tilli, "FuzzyLogik: Grundlagen, Anwendungen, Hard und Software", Munich: FranzisVerlag, 1991. 
[4]  B. Kosko, "Neural Networks and Fuzzy Systems  A Dynamical Systems Approach to Machine Intelligence", Englewood Cliffs: Prentice Hall, 1992. 