<figure><img src="image_1.png" /></figure>

HAL
open science

# Identification Effectiveness of the Shape Recognition Method Based on Sonar

Teodora Dimitrova-Grekow, Marcin Jarczewski

► To cite this version:

Teodora Dimitrova-Grekow, Marcin Jarczewski. Identification Effectiveness of the Shape Recognition Method Based on Sonar. 14th Computer Information Systems and Industrial Management (CISIM), Sep 2015, Warsaw, Poland. pp.244-254, 10.1007/978-3-319-24369-6_20. http-01444469

HAL Id: hal-01444469

https://inria.hal.science/hal-01444469

Submitted on 24 Jan 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Identification Effectiveness of the Shape
Recognition Method based on Sonar

Teodora Dimitrova-Grekow and Marcin Jarczewski

Faculty of Computer Science, Bialystok University of Technology,
Wiejska 45A, Bialystok 15-351, Poland
t.grekow@pb.edu.pl, m.jarczewski@o2.pl

**Abstract.** Sonars are among the most popular navigation elements used in autonomous vehicles. Beside their well known properties, they have unexplored specifics offering interesting information. In this paper, we present the results of an experiment with the drawbacks of sonars. Our approach combined the regular information obtained from a sonar system with information deriving from measurement aberration. The experiments with an ultrasonic range measurement system of a mobile robot showed that the usually neglected sonar drawbacks could be unusually helpful. This paper emphasizes the effectiveness of identification, which was calculated based on the ratio of the quantities of parallelepipeds to cylinders. The experimental results are presented. Further work aims to implement this idea on a robot on an HCR base. Another possibility is also suitable implementation of map building with a relative degree of confidence.

**Keywords:** shape recognition, sonar signal, features extraction, signal analysis, mobile robotics

# 1 Introduction

Sonar sensors are famous for their robustness and unambiguous acting for quite narrow and strictly defined work conditions. To obtain satisfying accuracy in distance measurement, one has to pay attention mainly to the applied sensor, the send signal, and the method of processing the received echo-information. All attempts to identify objects using sonar have to deal with the following problems:

- physical properties of objects: size, shape, material of which the object is made, the surface of the object;

- relationship between the sensor and the object, such as distance, angle;

- complexity and number of objects to recognize;

- repositioning, the physical properties of objects at a time;

- external factors, such as temperature and humidity.

The most common way to use ultrasonic sensors today are sonar arrays, con-
taining from 3 to 16 and more sensors. In contrast to a quite irrelevant, single
sonar sensor measurement, a data sequence from a sonar array allows compensation of the drawbacks of the acoustic signals to some level. In this paper, we present a complimentary attempt: in addition to the classical signal recovery and ridding of bad echoes, we sorted them and brought them into use. In our experiment, we tested shape distinguishing using simple objects, such as cylinders and parallelepipeds. A set of shape recognition rules was set and implemented in a real-time system: NXT robot. The tests have proved the off-line assumptions and calculations.

An important aspect of the study was to estimate the possibility of not only identifying the objects, but also their exact orientation and collocations. Hence, building maps to a relative degree of confidence [1] is a future aim.

## 2 Related Work

The most popular uses of ultrasonic signals are distance establishment and obstacle detection [2], localization [3] and avoidance [4]. It should not be forgotten, though, that sonar sequences contain much information about the environment [5] from such sources as inferential echo signals from all possible reflection surfaces in the environment the robot is acting in [6].

Although the sonar possesses a set of well known advantages, such as its wide accessibility, relative good accuracy and low costs, its main disadvantage are connected with the conical emission area of the signal. That is the origin of faked measurements occurring in the signal sequences. The more complex the structure of the environment, the more additional complicating and disturbing echoes arise. That complicates too much for direct use of sonar data for object recognition or topological localization. An well-known way to solve these problems is using neural networks [7], [8], [9], genetic algorithms [10], Fuzzy Artmap [11], Hough transform [12] or an extended Kalman filter [13]. Researches involved the analysis of a two objects based on Continuously Transmitted Frequency Modulated ultrasonic sensor [14].

All these methods require quite many calculations and the real-time work of sonar-based systems at times significantly slows down. But on the other hand all these approaches consider only ultrasonic echoes, neglecting measurements in which a non echo comes back etc.

In our work, we took into account not only the 'regular' information, delivered from sonar sensors, but also 'hidden' information. We acted on signal features, which were the result of the specific interaction between the sonar sensor and certain objects. In comparison to the mentioned methods, we used minimal computation, simultaneously keeping a very high identification effectiveness of shape recognition.

The first information about use of sonar shortcomings are described in [15]. In this article, we present enriched experience and extended explanation of the identification effectiveness using our shape recognition method.
## 3 System Structure

We present a complimentary attempt: beside the classical signal recovery and ridding of the bad echos, we sorted them and brought them in use. In our experiment, we tested shape distinguishing using simple objects, such as cylinders and parallelepipeds. A set of shape recognition rules was set and implemented in a real-time system: NXT robot. Each of the mobile robots was used as an independent data collecting vehicle. So far, the tests have proved the offline assumptions and calculations.

Considering the specificity of sonar signals, the first stage of research involved data processing (Fig. 1). The information gathered from the sonar system was treated in different ways while searching for the most relevant interpretation. The robot route is straight passing beside the obstacles. The robot maintains a path parallel to the wall.

Observing the collected data gathered from the sonar sensors, we noticed a number of interesting dependencies between the received reflections and the history of scanning. Finally, a set of object features enabling effective object recognition emerged. This can be considered the separate second stage of the study. The most essential features are described in the next section.

<figure><img src="image_3.png" /><figcaption>Fig. 1. Stages of the system</figcaption></figure>

We used a simple set of objects: two types of solids - parallelepipeds and cylinders. The tests shown in the third section were done on several different sizes of each type. The final, third stage of our system was developing recognition rules, which had been applied to the real-time test vehicle and proved the primary idea - to get more than the usual noise using only very simple tools.

In our experiments, we achieved over 80% accuracy in shape recognition. The experimental results are shown in the last section. The further work aims an implementation in mobile robot localization. A hybrid location method is being developed to test the pattern recognition approach in real-time conditions. Its
main point is building a relative confidence degree map to defining the vehicle
location. The method is described generally at the end of the article.

4 Simple Shape Recognition Method

The most common approach to shape recognition is to consider shape context.
The features used in this methodology are based on complex data related di-
rectly to the analyzed objects. We present a shape recognition method that also
uses indirect data, such as reflections, which we called "glitters" in this paper.
To implement our approach, we consider the following steps: (1) primary data
collection, (2) initial features extraction, (3) final features extraction (4) shape
recognition rules building.

For all these phases, the robot passed a distance *D* scanning the environment
along its path and gathering data (Fig. 1).

4.1 Primary Data Collection

Walking a certain distance, the experimental vehicle collects a set of distance
measurements. The raw data are processed twice:

a First, the raw sonar data it was smoothed so that the registered shapes became sharper and more reliable. The results of this smoothing was very appreciable and observable if one visualizes the data stream.

b Simultaneously, all data exceptions and irregularity were counted exactly, related, and compared.

All data irregularities were removed (Fig. 2). Among the registered values,
there were many 'glitters' - reading exceptions observed by comparison with
neighboring ones. Their quick smoothing facilitated further processing of the
received signal. Simultaneously, these irregularities were statistically assessed.

4.2 Initial Features Extraction

The first features extraction was based on regularly shaped data, obtained from
double smoothed sonar sequences. The secondary correction was focused on
larger 'exceptions' and smoothing of the discovered shapes (Fig. 2). The so-
called 'exceptions' were a result of overlapping echoes from various objects and
measurements made in sequence. This will be especially useful in the future
development of the system in the navigation area.

The very first phase of the research used a single object scene: the robot
scanned and saved data from a single object. It was indispensable to extract
all the necessary information for effective object recognition. After many obser-
vations, based on the acoustic rules and simplification derived from the chosen
work conditions, several important dependencies were found.
<figure><img src="image_4.png" /><figcaption>Fig. 2. Raw sonar measurements and real objects</figcaption></figure>

The adjustment scheme was empirically determined during the experiments and was part of a continued refinement-cast. The primary consideration allowed to appoint one of the most important features, used in further features determination.

**Minimal measured distance:** *D*<sub>MIN</sub> The meaning of this parameter is useful for detecting if it is an edge, side or cylinder. The minimal value itself is very important, but it becomes meaningful only after colligation with 10 to 30 contiguous distances.

## 4.3 Final Features Extraction

The main idea of our approach is based on investigating the irregularities in sonar measurements, taking into account the sequences in which they appear and the rules of this irregularity. The extracted features were used for building the shape recognition rules. Every file with data saved from the sonar was interpreted as a vector. The most important selected characteristics were:

**Wall-greater distances:** *D*<sub>OV</sub> - percentage of measurements greater than the distance to the wall *N*<sub>W</sub>
The source of such values can be different: NXT sonars use value '255' as an error measurement; normally it should mean 255 cm, but in fact it means non-response was registered; even if the obstacle is so near that the reflections of the send signal cannot reach the receiver. The total value of $D_{OV}$ is calculated as follows:

$$D_{OV} = \frac{(N_{255} + N_{GW})}{N} \qquad (1)$$

Where:

$N_{255}$ - number of '255' values,

$N_{GW}$ - number of values greater than the distance to the wall,

N - total number of measurements.

**Alien echos:** $D_{NR}$ - percentage of measured distances less than $N_{W}$ although no object is displaced at the spot

Obviously, this is the result of delayed or side reflections:

$$D_{NR} = \frac{N_{LLW}}{N} \qquad (2)$$

Where:

$N_{LLW}$ - number of values less than the distance to the wall, cached in the object's free space.

## 4.4 Shape Recognition Rules

A set of $D_{NR} = f(D_{OV})$ characteristics for ca. several hundred vectors were built. Some of them will be shown in the next section. A linear dependence (Fig. 3), which was implemented and loaded on the robot for online tests, resulted from the characteristic families. This is the most important, next to the extraction of features, step in the process of object recognition. When the optimal set of features has been selected, it is time to create a classifier. There are three different methods:

1. The concept of similarity - the simplest and most common approach, known as 'template matching'.

2. Probabilistic approach: includes methods based on the Bayesian decision rule, maximum likelihood or density estimation.

3. Building of decision limitations based on optimizing some error criteria: Fisher's linear discriminant, multilayer perceptions, decision tree.

Our approach was based on the first method. We studied the features extracted out in the previous subsection, as well as their behavior and relations to each other. This allowed us to discriminate parallelepipeds and cylinders with minimum calculations. An optimization of these observations is proof of the simple reliance between $D_{OV}$ and $D_{NR}$.
<figure><img src="image_5.png" /><figcaption>Fig. 3. Distinguishing parallelepipeds and cylinders</figcaption></figure>

Example of the dependency $D_{NR} = f(D_{OV})$ is visualized in Fig. 3. The optimal clustering generated a linear function which was different for every group of objects. In fact, a rule generalizing these differences can be found. Objects clustering was determined by linear function $F_{CL}(x) = ax + b$. Points located on the same side of the line belong to the same cluster.

Finding the best function consists of several steps:

1. Defining points in a certain distance from each other on the x and y axes: the parameters $D_{OV}$ and $D_{NR}$ got integer values from 0 to 100. Thus, we assumed that if the distance between two points is greater than 1, it is a sufficient condition to set an optimal line.

2. Then, a collection of lines for each of these points is appointed. Or for each point a dozen simple lines are determined. They all differ by a factor. The difference between the lines is 2. In a single group, at least a few thousand had been checked.

3. By evaluating the test collection, the best of the lines was selected.

# 5 Identification Effectiveness

Because of observations of various orientations of the parallelepipeds, the difference in the number of scanned cylinders and parallelepipeds was significant. Therefore, in order to ensure objective evaluation, a secondary factor $S$ was introduced, depending on the total number of cylinders $C$, and the total number of parallelepipeds $P$. In this way, we could save the $S = P/C$. Thanks to the difference in the number of measurements, it will not affect final effectiveness.
The effectiveness of R identification was calculated based on the ratio of the quantity of parallelepipeds to cylinders on the same side of the line. Indexes O stand for objects over the line and U for those under. So, for both cases $R_U$ and $R_O$ we obtain:

$$R_U = S_U(S_U + C_U P) \qquad (3)$$

$$R_O = C_O \frac{P}{S_O + C_O P} \qquad (4)$$

Hence, we get $R_1$:

$$R_1 = (R_U \frac{C_U P + S_U}{S + C} + R_O \frac{C_O P + S_O}{S + C})100 \qquad (5)$$

Later, you could make the opposite assumptions that under the line there are cylinders and over parallelepipeds:

$$R_2 = 1 - R_1 \qquad (6)$$

And finally:

$$R = \max(R_1, R_2) \qquad (7)$$

# 6 Tests and Experimental Results

Through the experiments we conducted, we found that the most appropriate way to obtain satisfactory and relevant shape recognition requires splitting the measurements into several groups, considering the minimum read distance. This range clustering was determined during the hundreds of tests. We generalized several variants considering the specific effectiveness for separate distance fractions and the complex effectiveness for the total experiment.

Here we present an optimal division of the distance ranges, where the complex effectiveness manifest stability. Groups, to which we assigned individual points were:

a) 8 - 25 cm,

b) 26 - 40 cm,

c) 41 - 60 cm,

d) 61 - 80 cm,

e) 81 - 120 cm.

In the realization of this study, we conducted over 500 tests divided into two sets:

- Teaching set - used exclusively for deriving proper clustering for the objects,

- Testing set - serving only for the evaluation of clustering effectiveness.
<figure><img src="image_6.png" /><figcaption>**Fig. 4.** Clustering functions for different data groups: a) 8-25 cm; b) 26-40 cm; c) 41-60 cm; d) 61-80 cm; e) 81 - 125 cm</figcaption></figure>
The results of the clustering function derive are shown as a set of graphs. The tests, repeated several hundred times, proved the calculated accuracy. When interpreting them, you should take into account that for the largest distances (> 100cm) most of the test objects were hardly 'visible' thus parameters $D_{OV}$ and $D_{NR}$ were almost the same. Figure 4 shows the end selected separating lines or clustering function $F_{CL}()$ for all five distance groups. The dependency between the function parameters are not the center of attention for this issue. To make things more clear, X-points are all unrecognized or incorrectly recognized figures.

The lowest effectiveness of the clustering function $F_{CL}()$ was 74.05% - refers to the nearest group of objects (Fig. 5). Its main weaknesses were parallelepipeds parallel to the robot path. The best effectiveness 96.15% was reached in the third group 41-60 cm. The linearity is changing is non linear, but possesses a logical rule: The hardware unfortunately disallows work with longer distances.

<figure><img src="image_7.png" /><figcaption>Fig. 5. Effectiveness for the distance groups</figcaption></figure>

# 7 Conclusions

The focus of this paper was identification effectiveness, which was calculated using the ratio of the number of parallelepipeds to cylinders. We considered not only the 'regular' information, delivered from sonar sensors, but also 'hidden' information and acted on signal features, which were the result of the specific interaction between the sonar sensor and certain objects.

The results of our experience with sonar drawbacks substantiate the developed method of simple shape recognition. Our approach combines the regular information obtained from the sonar system with measurements of aberration derivative. This original approach minimizes calculations for real-time implementation.

We presented a shape recognition rule: linear function $F_{CL}()$ expressing the dependencies between the sonar signal features in the described conditions. The
average accuracy we achieved was 86.28%. The tests on the robot Lego Mindstoms NXT proved the effectiveness of function $F_{CL}$().

Our further plans are to find general rules for shape distinguishing and also position recognition, which we partly touched on in our studies.

We intend to explore new features based on acoustic signal dependencies and additionally to increase the number of ultrasonic receivers. Further work also aims to use a new mobile robot on the HCR base, which will allow to implement this shape recognition method in building building a relative degree of confidence maps.

**Acknowledgments.** This paper is supported by the S/WI/1/2013.

## References

1. Dimitrova-Grekow T.: A hybrid algorithm for self location. In: PAK, vol. 11, pp. 11631166 (2013)

2. Del Castilloa G., Skaara S., Cardenasb A., Fehr L.: A sonar approach to obstacle detection for a vision-based autonomous wheelchair. In: Robotics and Automation IEEE Journal, vol. 54, pp. 967981 (2006)

3. Choi J., Choi M., Nam S.Y., Chung W. K.: Autonomous topological modeling of a home environment and topological localization using a sonar grid map. In: Autonomous Robots Journal, vol. 30, pp 351-368 (2011)

4. Lenser S., Veloso M.: Visual sonar: Fast obstacle avoidance using monocular vision. In: Intelligent Robots and Systems, vol. 1, pp. 886-891 (2003)

5. Ohtani, K., Baba, M.: Shape recognition for transparent objects using ultrasonic sensor array. In: SICE, Annual Conference, 2007, pp. 18131818, (2007)

6. Kiyoshi O., Masamichi M., Hiroyuki T., Keihachiro T.: Obstacle arrangement detection using multichannel ultrasonic sonar for indoor mobile robots. In: Journal Artificial Life and Robotics, vol. 15, pp. 229-233 (2010)

7. Vossiek, M., et al.: An ultrasonic multi-element sensor system for position invariant object identification. In: IEEE Ultrasonics Symposium Proceedings, pp. 12931297, (1994)

8. Dror,I.E., et al.: Three-dimensional target recognition via sonar: a neural network model. In: Neural Networks, vol.8 ,pp. 149160, (1995).

9. Kuc, R.: Biomimetic sonar locates and recognizes objects. In: IEEE Journal of Oceanic Engineering, vol. 22, pp. 616624, (1997)

10. Baba, M., et al.: 3D shape recognition system by ultrasonic sensor array and genetic algorithms, in: Proceedings of the 21st IEEE Instrumentation and Measurement Technology Conference, pp. 19481952, (204)

11. Streilein, W.W., et al.: A neural network for object recognition through sonar on a mobile robot. In: Intelligent Control, held jointly with IEEE International Symposium on Computational Intelligence in Robotics and Automation, Intelligent Systems and Semiotics, pp. 271276, (1998)

12. Yap T.N., Shelton CR.: SLAM in large indoor environments with low-cost, noisy, and sparse so-nars. In: Proceedings of IEEE international conference on robotics and automation:, pp. 1395-401, (2009)
13. Joong-Tae P., Jae-Bok S., Se-Jin Lee M.K.: Sonar Sensor-Based Efficient Exploration Method Using Sonar Salient Features and Several Gains. In: Journal of Intelligent and Robotic Systems, vol. 63, pp.pp. 465-480 (2011)

14. Worth P., McKerrow Ph.: An approach to object recognition using CTFM sensing. In: Sensors and Actuators, vol.179, pp. 319-327, (2012)

15. Dimitrova-Grekow, T., Jarczewski, M.: Sonar Method of Distinguishing Objects Based on Reflected Signal Specifics. In: LNCS vol. 8502, pp 506-511, Springer, Berlin Hei-delberg, (2014)