9512.net
甜梦文库
当前位置:首页 >> >>

Mobile Robot Sonar for Target Localization and Classification


Mobile Robot Sonar for Target Localization and Classification1

LINDSAY KLEEMAN2 and ROMAN KUC3

Abstract
A novel sonar array is presented that has applications in mobile robotics for localization and mapping of indoor environments. The ultrasonic sensor localizes and classifies multiple targets in two dimensions to ranges of up to 8 meters. By accounting for effects of temperature and humidity, the system is accurate to within a millimeter and 0.1 degrees in still air. Targets separated by 10 mm in range can be discriminated. The error covariance matrix for these measurements is derived to allow fusion with other sensors. Targets are statistically classified into four reflector types: planes, corners, edges and unknown. The paper establishes that two transmitters and two receivers are necessary and sufficient to distinguish planes, corners and edges. A sensor array is presented with this minimum number of transmitters and receivers. A novel design approach is that the receivers are closely spaced so as to minimize the correspondence problem of associating different receiver echoes from multiple targets. A linear filter model for pulse transmission, reception, air absorption and dispersion is used to generate a set of templates for the echo as a function of range and bearing angle. The optimal echo arrival time is estimated from the maximum crosscorrelation of the echo with the templates. The use of templates also allows overlapping echoes and disturbances to be rejected. Noise characteristics are modeled for use in the maximum likelihood estimates of target range and bearing. Experimental results are presented to verify assumptions and characterize the sensor.

1Work

performed while L. Kleeman was on sabbatical leave at the Intelligent Sensors Laboratory, Department of Electrical Engineering, Yale University. 2 Author for correspondence, Intelligent Robotics Research Centre, Department of Electrical and Computer Systems Engineering, Monash University, Wellington Rd, Clayton 3168, AUSTRALIA. 3Intelligent Sensors Laboratory, Department of Electrical Engineering, Yale University, PO Box 208284, New Haven CT 06520-8284, USA.

2

1. Introduction
Ultrasonic sensors provide a cheap and reliable means for robot localization and environmental sensing when the physical principles and limitations of their operation are well understood. This paper presents models and approaches that allow sensors composed of multiple transmitters and receivers to be exploited in a systematic, robust and accurate manner. A sensor design is presented that approaches the fundamental physical limitations of sonar in terms of accuracy and discrimination. The performance is limited only by the physical properties of air, the reflectors and noise. The objective of our research is to investigate the optimal deployment of ultrasonic transducers and the associated signal processing for indoor robotics applications. We concentrate on environments composed of specular surfaces, such as smooth walls, bookcases, desks and chairs, that reflect acoustic energy analogous to a mirror reflecting light. Rough surfaces can be treated with other techniques (Bozma and Kuc 1991). The applications of primary interest are robot localization from sensing known environmental features, such as wall and corner positions (Leonard and Durrant-Whyte 1991, Nagashima and Yuta 1992, Manyika and Durrant-Whyte 1993), and conversely, mapping of unknown environments for later use for localization and navigation (Bozma and Kuc 1991a, Iijima and Yuta 1992, Bozma and Kuc 1991, Elfes 1987, Crowley 1985, Moravec and Elfes 1985). Obstacle avoidance (Kuc 1990, Borenstein and Koren 1988) is another application of the sensor. A classification standard for indoor target types emerging is that of planes, corners and edges (Bozma and Kuc 1991a, Barshan and Kuc 1990, Peremans et al 1993, Sabatini 1992, Leonard and Durrant-Whyte 1991, McKerrow 1993). The sensor approach presented here is novel in the sense that it classifies all three target types with the one stationary sensor, simultaneously in some cases, with high accuracy and discrimination. Our approach has higher speed and accuracy, particularly in bearing, compared to single transducer systems that rely on multiple displaced readings and wheel odometery for target classification (Bozma and Kuc 1991, McKerrow 1993, Leonard and Durrant-Whyte 1991). Sonar sensors have been reported previously that can classify two of the three target types -- Barshan and Kuc (1990) discriminate planes and corners based on pulse amplitude measurements; and Peremans et al (1993) uses time of flight (TOF) to classify planes and edges and employs sensor movement to distinguish corners and planes. Three dimensional sonar target classification based on pulse amplitude measurements is proposed in (Hong and Kleeman 1992), where statistical tests are derived for classifying planes and concave corners of two and three intersecting orthogonal planes. Other sonar array sensors that report range and bearing to targets have been reported (Munro et al 1989, Yang et al 1992, Suoranta 1992, Manyika and Durrant-Whyte 1993) and proposed (Sabatini 1992). This paper is organized as follows: Section 2 establishes that a minimum of two transmitters and two receivers are required to classify planes, corners and edges without sensor movement. The physical separation of the receivers is considered in Section 3 in relation to the important problem of establishing correspondence between multiple echoes on two receivers. A solution is proposed that does not require additional transducers over the minimum for classification of planes, corners and edges. In Section 4 we consider the design of a sensor module called a vector sensor that can measure both range and bearing to an ultrasonic target. In Section 5, the

3 vector sensor module is included as a component of a minimal transducer arrangement for classifying planes, corners and edges. The interaction of the sensor to the three target types is derived and used to establish a statistical test for classifying targets. In Section 6 pulse shape is modeled as a function of range, transmitter and receiver angles, and air characteristics. These results allow the optimal estimation of distance of flight (DOF) as described in Section 7 where error models are developed based on experiments. Strategies for handling overlapping echoes and noise disturbances are discussed in Section 8 and experimental results are presented in Section 9 to verify the performance of the sensor. Conclusions and future extensions are given in the final section of the paper. Throughout the paper, the terms transducer, transmitter and receiver refer to individual ultrasonic devices, while sensor refers to a combination of transducers and intelligence required to actively sense the environment.

2. Minimum Sensor Requirements
In this section, the minimum requirements of an array of transducers are established in order to identify commonly occurring primitive reflector types in an indoor environment. The reflector types agreed upon in the literature (Barshan and Kuc 1990, Peremans et al 1993, Sabatini 1992, Leonard and Durrant-Whyte 1991, McKerrow 1993) and considered in this paper are planes, corners and edges. A plane reflector is assumed to be smooth and reflect ultrasound specularly. The corner is assumed to be a concave right angle intersection of two planes. An edge represents physical objects such as convex corners and high curvature surfaces, where the point of reflection is approximately independent of the transmitter and receiver positions. These reflector types are considered in two dimensions in this paper. For a mobile robot, vertical planes, corners and edges are of interest. Since the robot is assumed to move in a horizontal plane, the vertical coordinates of environmental features do not provide essential information for localization and map building for localization. The work presented here can be extended to three dimensional targets, if required, by o including a second sensor that is rotated by 90 . Although transmitters and receivers are considered separately, they may be combined into one physical transducer. We use the construct of virtual images borrowed from an optical context. The virtual image of a transducer in a plane is obtained by reflecting the true position of the transducer about the plane. The virtual image of a transducer in a corner is obtained by reflecting about one plane and then the other which results in a reflection about the line of intersection of the planes. First, we establish that one transmitter and any number of receivers are insufficient to distinguish corners from planes in any orientation. Any receiver in a transducer array will see the virtual image of the transmitter sensor reflected in the plane or corner. The sensing problem is entirely equivalent to replacing the reflector and transmitter by a transmitter placed at the position of the virtual image transmitter. No matter how many receivers are present, the corner and plane are indistinguishable in terms of distance of flight when only one transmitter is employed, as illustrated in Figure 1(a). Note however that the virtual image orientation of the transmitter is reversed between the plane and the corner. With this orientation of plane, it is conceivable to distinguish planes from corners using the amplitude of the received pulse, since the amplitude is a function of the absolute value of angles of transmission and reception (Barshan and Kuc 1990). However, the two virtual images are identical

4 in orientation when the plane is aligned with the transmitter as shown in Figure 1(b). Therefore in general, planes and corners are not distinguishable with just one transmitter.
Plane

Plane R R arbitarily positioned

R

Virtual image

Virtual image R arbitarily positioned

T

T' Corner

T Corner R

T'
R

T

T'

T

T'

(a)

(b)

Figure 1 Indistinguishability of planes and corners using DOF. (a) Plane not aligned with Transmitter (T) - virtual images observed at Receiver (R) are indistinguishable with DOF but distinguishable with amplitude of echo pulse. (b) Plane aligned with Transmitter - virtual images indistinguishable between plane and corner. Can any number of transmitters and one receiver distinguish planes from corners? The construction in Figure 2 shows the virtual image, Rplane, of a receiver in an arbitrarily positioned plane. If the vertex of a corner is positioned at the intersection between the line joining the receiver to its image and the plane, then the receiver sees the same DOF for both transmitters. Moreover, for planes aligned with the receiver, the virtual images in the plane and corner coincide exactly in orientation. This case renders the corner and the plane indistinguishable, even with pulse amplitude measurements. Therefore, for the general case of any orientation, at least two transmitters and two receivers are required for differentiation of planes and corners.
Virtual image of receivers Rcorner R Rplane

T1

... Tn

Figure 2 - Virtual images of a receiver in a plane and corner for n transmitters.

5 As will be seen below, the configuration of two transmitters and two receivers is sufficient to discriminate planes, corners and edges, and hence the important result follows: Two transmitters and two receivers are necessary and sufficient for discriminating planes, corners and edges in two dimensions. Designs of sensors have been published (Peremans et al 1993, Sabatini 1992) with one transmitter and three receivers, that can discriminate planes from edges and corners from edges, but require movement of the sensor to discriminate planes from corners. The sensor movement is equivalent to placing another transmitter at the new location. The use of three receivers provides redundancy that can be exploited in an attempt to solve the correspondence problem, described in the next section.

3. The Correspondence Problem and Receiver Separation
In an ideal environment containing only one reflector, each echo is directly attributed to the reflector. In practice many reflectors are present and multiple echoes are observed on each receiver channel. The correspondence problem is how to associate echoes on different receivers with each other and ultimately to physical reflectors. The more general association problem of mapping multiple observations to multiple physical sources occurs in many areas of robotics and computer vision. When an incorrect association is made between incoming echoes on different receivers, gross errors can occur. For example a reflector's bearing can be incorrectly reported by a large margin, producing phantom targets unrelated to physical objects. The effect on robot navigation and mapping depends on the robustness of higher level interpretation of sensor readings. Four equally spaced receivers R1, R2, R3 and R4 are shown in Figure 3. An echo is received on R1 and we wish to find the corresponding echoes on R2, R3 and R4 for the same wave front. For a given angular beam width of the receivers, the extremes of arrival directions are represented by the dashed and dotted wave fronts in Figure 3. These arrival directions define the search time intervals on receiver channels R2, R3 and R4 about the arrival time of the echo on R1. The ends of the search time intervals are shown with dotted and dashed pulse outlines. Note that the search interval spreads in proportion to the separation between R1 and the other receiver, and thus increasing the chance of incorrect associations. For widely-spaced receivers, occlusion problems can result in the absence of an echo on the other receiver and no association is then possible.

6

R1

R2

.?.

R3

............??...........

R4

.....................???.................... Time

Figure 3 - Illustration of the association problem with varying receiver spacing. Consider the transmitter and receiver, T/R1, and receiver, R2, spaced d apart as in Figure 4. Initially, suppose for the sake of simplicity that transmitters and receivers can span the full 180o beam width. For an echo TOF on receiver R2 of t0 and speed of sound of c, an echo on R1 in the TOF interval [t0-d/c, t0+d/c] is possible for a reflector in front of the transmitter (the extreme reflector positions lie above and below R1 on the line through R1 and R2). This range of TOFs then needs to be searched for a corresponding echo on receiver R1. Any other reflector that lies in between the circles defined by TOFs of t0-d/c and t0+d/c can generate an additional echo that causes a correspondence problem. The area of this region of ambiguity is π ct d and is a measure of sensor susceptibility to correspondence errors. In the more 0 2 general case of a beam width of 2α and with ct0>>d we need to search arrival times on R1 in the range [t0-dsinα/c, t0+dsinα/c] and the area of the region of ambiguity is approximately αc t0d sinα. Reflectors must therefore be separated in range by at least d 2 sin α to avoid correspondence problems. The sensor presented later in this paper has d=35mm and α=30, requiring a reflector range separation of approximately 9 mm. The approach taken in this paper is to attempt to minimize correspondence errors at the earliest possible stage in processing - at the sensor level. This is achieved by reducing the minimum reflector separation or the area of the region of ambiguity by reducing the receiver separation, d.

7

d possible reflector positions

x1+x2=t0/c

x1

R2 d T/R1

x2

region of correspondence

Figure 4 - Region of ambiguity - reflectors in this region cause a correspondence problem. A possible disadvantage of small receiver separation is that less accurate bearing information may be extracted from arrival times in the presence of noise. With the sensor design described later in the paper, high accuracy in bearing angle has been achieved despite the receivers being spaced as close as the transducers physically allow. Due to our closely-spaced receivers, correspondence problems are rare and are handled by simply discarding the measurements that have a correspondence ambiguity. Other approaches are to use information such as echo power and shape to resolve ambiguity. Redundant receivers can be employed also, such as in three receiver systems (Peremans et al 1993). However, the presence of noise in the received signals or certain geometric arrangements may still cause unreliable correspondences.

4. Vector Sensor
In this section we show how two receivers can be combined to form a vector sensor which measures bearing to a target in addition to the range available from one receiver. The vector sensor will be used later as a useful building block in a sensor. Just one transducer and the echo pulse amplitude can be employed to extract the absolute value of the angle of arrival as described in (Barshan and Kuc 1990, Hong and Kleeman 1992, Sabatini 1992). However, we require the sign of the arrival angle for a complete sensor system. Moreover, the use of amplitude measurements as a means of bearing estimation is avoided in this paper due the requirement to detect edges and cylinders whose reflected echo amplitude depends on the geometric properties of the target, such as surface curvature. In a two dimensional plane, the angle of reception of an echo can be found from the arrival times of two receivers. For plane wave fronts as shown in Figure 5, the angle to the normal of the receivers, θ, is given by

8

θ = sin -1

FG c t IJ H d K
diff

(1)

where tdiff is the difference in arrival times, c is speed of sound and d is the receiver separation.

R1

plane wave

d

d sin θ θ R2

Figure 5 - Plane wave arrival at two receivers. In practice, a plane wave front is an approximation for a spherical wave front emerging from a point source. The point source may be attributed to a reflector with high curvature such as an edge or cylinder and consequently acts as a point source at the range of the reflector. Alternatively, the point source can arise due to the virtual image of a transmitter reflected in a plane or corner and acts as a point source with twice the range as the reflector. Both these cases are modeled as the point source P in Figure 6, where r1 and r2 are the distances from P to the receivers R1 and R2. For planes and corners r1 and r2 are directly available from the DOFs from the transmitter to receivers. In the case of an edge reflector, r1 is half the DOF for a transmitter at the same position4 as R1 and r1-r2 is the difference in DOFs.
P

r2 R2 A d 90?θ θ

r1

B R1

Figure 6 - Point source geometry for two receivers.

4 With an edge reflector and a transmitter at different position to R1, r and r can be still expressed as 1 2 function of DOFs and the transmitter position.

9

From the cosine rule on triangle APB: r22 = d2 + r 2 ? 2d r cos( 90 ? θ) 1 1 and hence θ = sin?1 (2)

FG d + r ? r IJ H 2dr K
2 2 1 2 2 1

(3)

A three dimensional vector sensor can be constructed by extending the two dimensional structure as shown in Figure 7.

T/R

R

R

Figure 7 - Three dimensional vector sensor configuration.

4.1. Bearing Estimate Errors
In this section we relate the standard deviation of the difference in DOF of two receivers to the bearing estimate error. This result is useful for providing bearing error estimates from experimental data. The bearing estimate of the vector sensor is based on equation (3). The angle θ can be rewritten as a function of r1 and the difference in DOF ?r = r1 ? r2 . The partial differentiations of equation (3) with respect to each variable gives ?θ r ? ?r = 1 ??r r d cosθ 1 and ?r2 ? d2 ?θ = 2 ?r 2r d cosθ 1 1 We can now determine the standard deviation of our bearing estimate, σθ ?θ ?θ r ? ?r ?r2 ? d2 1 σθ = σ ?r + σr = σ ?r + 2 σr ??r ?r 1 r d cosθ 2r d cosθ 1 1 1 1 (6) (5) (4)

For targets in the transducer beam width ?r<<d<<2r1, equation (6) can be approximated by

10 σθ ≈ 1 d σ ?r ? 2 σr 2r cosθ 1 d cosθ 1

(7)

The second term in equation (7) is much smaller than the first and can be ignored in practice. For small bearing angles we have the approximation σθ ≈ σ ?r d (8)

5. Application of Vector Sensor to Plane/Corner/Edge Identification
The sensor arrangement employed in experiments reported in this paper is shown in Figure 8. There are two receivers and two transmitters which is the minimum required to identify planes, corners and edges. The two receivers are closely spaced to minimize any correspondence ambiguity and also to form a vector sensor as described in the previous section. The transmitters are spaced sufficiently to perform reflector classification at the furthest range conceived for the sensor of 5 to 7 meters. The transducers are Polaroid 7000 series devices (Polaroid 1987). The sensor arrangement has one less receiver than other published systems (Peremans et al 1993, Sabatini 1992). This is a significant saving due to the data capture and processing requirements of a receiver channel. The deployment of a second transmitter in the sensor is comparatively cheap in terms of hardware, but does incur an additional measurement delay since transmitters need to be fired alternately. The sensor is stationary for results reported this paper. At the expense of sensor accuracy, onboard robot odometry measurements can compensate for a moving sensor. A future smart sensor may be able to exploit the absence of reflectors at certain ranges to overlap transmission.
T/V

T/R

R

T

35mm

225mm

Figure 8 - Sensor arrangement, T=transmitter R=receiver V=vector receiver. The sensor arrangement is interfaced to a 33 MHz 386 PC via a Biomation 8100 dual channel transient recorder with 8 bit conversion at a sample rate of 1 MHz as shown in Figure 9. The PC controls the firing of the transmitters and the triggering and control of the Biomation transient recorder. All processing and display of the received data are performed on the PC. The interface electronics consists of two simple receiver preamplifiers and two single transistor transmitter circuits. A 300V DC power supply provides the transducer biasing.

11

T2 Trigger and fire control Interface Electronics R2 PC 386 Trigger Control Biomation Dual channel 8 BIT ADC 1MHz R1 data R2 data R1/T1

Digital data

Figure 9 - Experimental Setup for Sensor. The interaction of the sensor with each of the reflector types is derived in the Sections 5.1, 5.2 and 5.3. Statistical tests for classification into plane, corner, edge or unknown reflector type are derived from these geometrical relationships in Section 5.4.

5.1.

Plane Geometry

Figure 10 shows the sensor encountering a plane reflector. Note that the two receivers and transmitter labeled as T/V act as a transmitter and vector receiver at the location of the transmitter when bearing is estimated using equation (3). This is possible due to the assumption of a plane reflector allowing the distance to be known to the point source that is the virtual image in this case.
VIRTUAL IMAGE T2

T2'

α1 b r2 b cos α1 b

T1/V α2 α1

β

T1/V' r1 A b sin α1

Figure 10 - Sensor image in plane reflector. From the geometry in Figure 10, the range, r2, and bearing, α2, of the virtual image T2' are functions of the range, r1, and bearing, α1, of the virtual image T1'. Consequently, we can write r2plane(r1, α1) and α2plane(r1, α1). From triangle T1/V T2' A, the bearing difference between the two transmitters is

12

β plane and

= tan ?1

FG b cos α IJ H r ? b sin α K
1 1 1

(9) (10)

α 2 plane (α1 , r1 ) = α1 + β plane r2 plane (α1 , r1 ) = ( r1 ? b sin α1 )2 + ( b cos α1 )2

(11) r12 ? 2 r1 b sin α1 + b 2 = Note that the plane must be sufficiently wide to produce the two reflections. For r1>>b, the plane must be at least (b cosα1)/2 wide.

5.2.

Corner Geometry

The virtual image of the sensor in a corner is obtained by reflecting the sensor about one plane of the corner and then the other plane. This gives rise to a reflection through the point of intersection of the corner as shown in Figure 11. The situation is similar to the plane except that the angle between the transmitter images, β, is opposite in sign: b cos α1 β corner = ? tan ?1 (12) r1 ? b sin α1 α 2corner (α1 , r1 ) = α1 + β corner (13)

FG H

IJ K

r2corner (α1 , r1 ) =

r12 ? 2 r1 b sin α1 + b 2

(14)

To be seen fully by the sensor, the corner must subtend an arc of approximately tan-1(2b/r1).

T2

b VIRTUAL IMAGE T1/V r1 α2 α1 ?β b cos α1 b r2 α1 A b sin α1 T1/V'

T2'

Figure 11 - Sensor image in corner reflector.

13

5.3.

Edge Geometry

An edge represents physical objects such as convex corners and high curvature surfaces, where the point of reflection is approximately independent of transmitter and receiver positions. Consequently, the reflection from an edge has equal bearings from each transmitter (α2edge(r1, α1) =α1). The DOF r2edge is obtained from the cosine rule: r2edge (α1 , r1 ) = r1 / 2 + ( r2 ? r1 / 2 ) = r1 + r12 + 4 b 2 ? 4 r1b sin α1 2
T2

(15)

b

r2 - r1/2

edge reflector T1/V α1 = α2 r1/2

Figure 12 - Sensor with an edge reflector.

5.4.

Geometric Hypothesis Testing

In this section we determine statistical tests for discriminating between planes, corners and edges. We assume that our reflectors are geometrically perfect in the sense that planes are perfectly flat and edges act as a point reflector. Imperfections in reflectors will be discussed in conjunction with experimental data in Section 9. From the previous three sections, the differences between planes, corners and edges can be seen in terms of the sensor perception. To discriminate planes, corners and edges, the angle difference between bearings of the two transmitters can be used, since it is β for a plane, -β for a corner and 0 for an edge. The DOF information can be exploited to aid differentiation of edges from corners and planes. For example in Figure 13 the bearing and DOF are shown for the three reflector types at a range of b 0.5 meters. For small bearing angles and range much larger than b, β ≈ . Also for r1 b2 the DOF r2 the difference between a corner or plane and an edge is approximately . 2 r1 As ranges increase these margins decrease while standard deviations of errors in bearing and DOF increase, and a range limit for the sensor discrimination capability is reached at the range where the margins and errors are equal.

14 There are four measurements, denoted by the vector m, consisting of two pairs of DOF and bearing. The DOF and bearing errors are assumed to be zero mean jointly Gaussian random variables with a covariance matrix R. The Gaussian assumption and the covariance matrix R are discussed in relation to experimental data in Section 7. Given a hypothesis of a reflector type, the maximum likelihood estimator (MLE) (Whalen 1971) for the range and bearing to the reflector type is derived below. Since no a priori probabilities of reflector types are known, we settle for using the conditional probabilities of the measurements given reflector hypotheses, prob(m| reflector), to discriminate among the reflector types. As can be seen in Figure 13 the DOF and bearing of T2 as function of those of T1 are approximately straight lines. The linear model in the following equation holds r for all three reflector types of plane, corner and edge for the approximation of 1 ≈ 1 , r2 r1 >> b . We obtain the model by a first order Taylor expansion around the T1 and measurements of DOF mr1 and bearing mα1 . m = Hx + n where 1 0 LM OP LMM 0 0 PP, H = MM ?rr m=M ? MM mr ? r (mr , mα ) P M ?α Nmα ? α (mr , mα )Q MN ?r
2 2 2 1 1 2 1 1

(16)

2 1 2

1

0 1 0 1 ?r2 r1 ? mr1 0 1 ≈ ,x= ?α1 α1 ? mα1 1 ? b cos( mα1 ) ?α 2 0 1 ?r1

OP PP PP PQ

LM MM MN

OP PP PQ

LM N

OP Q

and n is zero mean Gaussian noise with covariance matrix R. From (Whalen 1971  p376), the MLE for x, denoted x is given by
 x = H' R ?1H

c

h

?1

H' R ?1m

(17)

and is unbiased with covariance matrix H' R ?1H . That is, we can determine the accuracy of the position estimate of the reflector and could use this in a Kalman filter for map building or localization similar to (Leonard and Durrant-Whyte 1991).

c

h

?1

15

40 30 20 10 0 plane edge corner

1150

plane/corner

edge

1100

1050

1000
-10 -20 -30

950

900
-40 alpha1 (degrees ) ->

alpha1 (degrees ) ->

Figure 13 - Received angle and DOF for transmitter 2 for r1=1 meter. We can evaluate the confidence associated with each target type hypothesis by examining the noise residual of our MLE for each reflector. The weighted sum of square errors, S
  S = ( Hx ? m )' R ?1 ( Hx ? m )

(18)

has a chi-square distribution with four degrees of freedom (Papoulis 1984). A 95% confidence corresponds to S≤ 0. 71 and 80% to S≤ 1. 65. If none or more than one reflector type has an acceptable confidence level then the target is classified as unknown. This situation arises when the errors in the bearing and range are too large to effectively discriminate reflector types. The sensor will then report lack of discrimination - an important feature. It is also possible (but unlikely) that a range/bearing measurement may match, to an acceptable confidence level, more than one other range/bearing measurements derived from the other transmitter. We adopt the "fail safe" approach and classify all the ambiguous range/bearing measurements as unknown. This approach effectively avoids the correspondence problem of associating range/bearing measurements on different transmitters. More sophisticated approaches are left for future research.

6. Modeling Pulse Shape
Estimating bearing and range to reflectors depends on an accurate TOF estimate. The maximum likelihood estimate of TOF of an echo pulse with additive Gaussian white noise is obtained by finding the maximum of the correlation function of the received pulse with the known pulse shape (Woodward 1964). Knowing the pulse shape in the absence of noise is important for determining TOF and also for identifying overlapping echoes and disturbances as discussed in Section 8. Modeling pulse shape is therefore considered important for robustness and performance of the sensor design. Note that the pulse amplitude is also modeled in this section but is not employed in the arrival time determination.

16

h trans s(t) θ T hair

Reflector h refl

h rec θ rec(t) R

Figure 14 - Linear pulse model. The pulse shape depends on many factors: transducers, excitation, angles to the transmitter and receivers, dispersion and absorption with distance of travel in air, and reflector properties. We assume a linear model for these effects illustrated in Figure 14. Let s(t) be the sending excitation applied to the transmitter, then the signal recorded at the receiver is given by
r rec(t , θT , rT , θ R , rR ) = s(t ? c ) ? htrans (t , θ T ) ? 1

ρ

hair (t , r ) ? hrefl (t ) ? hrec (t , θ R )

(19)

where ? is the convolution operator and the h's are impulse responses due to the transmitter at angle θT to axis, air absorption and dispersion, the reflector, and the receiver at angle θR to normal incidence. The distance r is defined as the total DOF rT+rR, where rT is from the transmitter to the reflector and rR from the reflector to the receiver. For plane and corner reflectors, ρ is defined to be the sum rT+rR, since a spherical wave front can be modeled as coming from a virtual transmitter at range rT+rR. For edge reflectors, ρ is defined as the product rTrR, since energy is effectively re-radiated from the point source located at the edge. The proportion of energy reradiated from the edge is dependent on the area profile presented to the incoming wave front (Sasaki and Takano 1992) and is not considered further in this paper. Since air is assumed to be a linear medium, the following property holds hair (t , r1 + r2 ) = hair (t , r1 ) ? hair (t , r2 ) (20)

The transducers are much further from the reflector compared to their size, and therefore the impulse responses due to the transmitter and receiver can be further refined as (Kuc and Siegel 1987): htrans (t , θ T ) = hθ (t , θ T ) ? hT (t ) hrec (t , θ R ) = hθ (t , θ R ) ? hR (t ) (21)

where hT and hR are the impulse responses of the transmitter and receiver at normal angle of transmission and incidence. Note that the same impulse response, hθ, due to

17 angular dependence applies to transmitter and receiver, due to reciprocity between transmitter and receiver. From equations (20) and (21), equation (19) can be rewritten as: ρ r rec( t , θ T , rT , θ R , rR ) = ref (t ? ) ? hθ (t , θ T ) ? ref hair (t , r ? rref ) ? hθ (t , θ R ) (22) c ρ where 1 ref (t) = s(t) ? hT (t) ? hair (t, rref ) ? hrefl (t) ? hR (t) (23) ρref is obtained by storing a reference echo pulse from a plane5 aligned to the transmitter and receiver at a range rref/2. A typical value of rref/2 is 1 meter. For separate transmitter and receiver, ref(t) can be obtained from a corner positioned as in Figure 15. The remaining functions, hθ and hair, are determined from the transducer diameter and calibration respectively as described in Sections 6.2 and 6.3 below. A matrix of templates of received pulse shapes can be generated off-line for discrete angles and ranges. The appropriate range can be selected from an approximate estimate of the arrival time, and the angles chosen from the best correlation match as described in Section 7.

T

R

Figure 15 - Collecting a reference pulse with separate transmitter and receiver.

6.1. Transmitted Pulse Shape
The pulse shape seen at the receiver is determined by equation (19). We have control over the excitation, s(t), and the selection of transducer in determining the pulse shape. There are many different approaches to choosing the excitation - gated square waves and chirps (Polaroid 1982, Sasaki and Takano 1992) and even Barker coding (Peremans et al 1993). The main objectives are (i) accurate TOF estimates, (ii) fine discrimination of targets, (iii) large range capability, and (iv) simplicity. Objectives (i) and (ii) suggest a wide bandwidth pulse, and (iii) a large energy content, while (ii) suggests a narrow pulse width or a coded sequence of narrow pulses (Peremans et al 1993). A narrow pulse with large amplitude is chosen for simplicity and wide bandwidth. A wide bandwidth pulse has a sharp auto correlation peak and low side peaks and allows a better estimate of TOF as described in Section 7.1.

5

A plane reflector was found in practice to adequately represent corners, cylinders and edges pointing towards the sensor in terms of echo pulse shape. Pulses from edges with one plane facing away from the sensor are inverted in amplitude (Sasaki and Takano 1992) and are not implemented in this paper.

18 The pulse is generated by approximating an impulse applied to the transmitter with a rectangular pulse of 10 ?sec duration and 300V amplitude on a Polaroid 7000 transducer. The protective cover of the transducer is removed to eliminate reverberation, thereby producing shorter cleaner pulses. The echo pulse is AC coupled and amplified with two operational amplifiers. A typical pulse shape at 1 meter from a plane reflector is shown in Figure 16. The pulse duration is 50 ?sec which corresponds to a range discrimination of 9 mm. A narrow pulse also results in a low computational burden in the correlation calculations employed in TOF estimation.

0

10

20

30

40

50

60

T ime (us ec)->

Figure 16 - Received pulse shape from a plane reflector at 1 meter range.

6.2. Angle Dependence
The angular impulse response hθ can be obtained from the transducer shape. The received amplitude is proportion to the area exposed to the pressure impulse, and thus the response is the height profile as the impulse grazes past the surface at an angle α to the surface normal. For a circular transducer, the impulse response has the shape of the positive half of an ellipse with width equal to the propagation time across the face of the transducer, tw=Dsin(|α|)/c, where D is the transducer diameter (Kuc and Siegel 1987). That is

R 4c cos α | h (t , α ) = S πD sin α |0 T
θ

F 2t I 1? G J Ht K
w

2

, ?

tw
2

<t<

tw
2

(24)

, otherwise

Echoes measured from a combined transmitter/receiver at angles 5o, 10o, 15o and 20o from normal to a plane are shown in Figure 17, where good agreement between experimental results and results generated from hθ ? ref ? hθ can be seen. The latter echoes contain an enhanced relative level of noise due to their small amplitudes. Correlation values of 0.96 or higher are obtained between the experimental and o o predicted pulse shapes over the range 0 to 20 . Moreover the best correlation match o was within 1 of the measured angle. This suggests using the pulse shape as a means of estimating the absolute value of the arrival angle of an echo. In practice, however little additional information is obtained from the pulse shape since the bearing estimate obtained from the arrival times of two receivers in the vector sensor is an order of magnitude more accurate.

19 Due to the wide bandwidth of the pulse, no nulls or side-lobes occur in the transducer angular beam pattern. This can be explained by observing that positions of nulls and peaks in narrow band pulses are a function of frequency and thus a wide bandwidth pulse adds a continuum of nulls and peaks at varying positions giving a net smooth beam pattern. The beam pattern obtained from the energy of the pulse hθ ? ref ? hθ is plotted in Figure 18. The small ripples are due to discrete time sampling of the impulse response hθ.
0.2 0.1 0 0 -0.1 -0.2 T ime (us ec) 0.04 0.03 0.02 0.01 0 -0.01 0 -0.02 T ime (us ec) 10 20 30 40 50 60 70 0.000 -0.010 -0.020 T ime (us ec) 0 10 20 30 40 50 60 70 0.030 0.020 0.010 10 20 30 40 50 60 70 0.08 0.06 0.04 0.02 0 -0.02 0 -0.04 -0.06

10

20

30

40

50

60

70

T ime (us ec)

Figure 17 - Experimental and predicted echoes at 5o, 10o, 15o, 20o to transducer.
0 -5 -10 -15 -20 -25 -30 -35 -30 -20 -10 0 10 20 30

Angle (degrees )

Figure 18 - Beam pattern corresponding to the pulse shape.

6.3. Ultrasound Absorption and Dispersion in Air
The air propagation medium absorbs sound energy as a complicated function of temperature, humidity and frequency. Measured data (Weast and Astle 1978) of absorption losses of still air at 20o C are plotted in Figure 19. The same data measurements report the speed of sound, c(f,h) against frequency, f, and humidity, h at 20o C. The phase delay per meter, ψ(f,h), can be calculated as follows:

20 ψ ( f , h) = 2π f c( f , h )

(25)

To within a linear phase delay, ψ(f,h) fits a minimum phase model for the absorption versus frequency. The minimum phase is derived from the attenuation using the discrete Hilbert transform (Kuc 1988) and is consistent with minimum phase properties of physical systems. The inverse discrete Fourier transform is used to generate the impulse response for air at 20o C, denoted hair20(t, r). An example is shown in Figure 20 for 50% humidity and 4 meter propagation distance.

3.5 3 2.5 dB/m 2 1.5 1 0.5 0 100 % Humidity

AAAAAAAAAAAA A AAAAA AA AAA AAAAA AAAAAAAAAAAA AAAAA AAAAA AA AAAAAAAA AAAA A AAA AAAAA AAAAAAAA AAAAA AAAAA A A AAAAAAAA AAAAA AAAA A AAAAA AAAAAAAA AAAAAAAAA AAAAAAAA AAAAA AAAA AAAAAAAA AAAAAAAAA AAAAA AAAA A AAAAA AAAA A A AAAAA AAAAAAA AAAAA AAAAA AAAAAAAAAAAA AAAAA AAAAAAAAAAAA A AAAAA AAAAAAA AAAAA AAAAAAAAA A AAAAAAAA AAAAAAAAAAAA A A AAAA AAAAAAA AAAAA AAAAAAAAA A AAAAAAAAAAAA AAAAA AAAA AAAAA A AAAAAAAA AAAAAAAAAAAA A AAAA A AAAAAAA AAAAAAAA A AAAAAAAAA AAAAA AAAAAAAAA A AAAAAAA AAAAA AAAAAAAAA A AAAAAAAA AA AAAAAAAAAAAA AAA AAAAA A AAAAAAAA A AAAA AAAAAAAA AA AAAAAAAAAAAA AAAA AA A A AAAA A AA AAAA AAAAA A AAAAAAAA AAAAAAAAAAAA AAA AAAAA AAAAA AA A A AAAAAAAAA A AA AAAAA AAAAAAAA A AAAAAA A AAAAAAAA A A A AAA AAAAAAAA AA AAAAA A AAAAAAAA AAAAAAAA AA AAA AAAAAAAA A AAAAAAAAAAAAAAAA AAAAA AAAAAAAAAAAAAAAA AAAAA A AAAAAAAA AAAAAAAA A AAAAA AAAAAAAAA AAAA AAAAA A A AAAAAAAA AAAAAAAA A AAAAA AAA AAAAA AAAAA AAAAA AAAAA AAAA AAAA AAAA AAAAAAAAAAAA AAA AAAAAAAA A AAAAAAAAAAAAAAAA AAAAA AAAAAAAAAAAA AAAAA AAAAAAAAAAAA A AAAAAAAA A AAAAA AAAAAA AAAA AAAAA AAAAAAAAAAAA AAAAA A A A AAAAAAAA AAAA A A AAAAAA AAAAAAAAAAAA AAAAAAAAAAAA A AAAAAAAAAAAA AAAAAAAAAAAA A AAAAAAAAAAAA AAAAAAAAAAAA A AAAAA AAAAAA AAAAA A A AAAAAA AAAAAAAA A AAAAA AAAA A A AAAAA AAAAAA AAAAAAAA AAAAAAAAAAAA AAAAA AA AAAAAAAAAAAA AAAAA AAAAAAAAAAAAAAAA A AAAAAAAAAAAA A AAA AAAAAAAA A AAAAAA A AAAAAAAAA AAAAAAAA A AAA A AAAA AAAAA AAAAA AAAAAAAAAAAAAAAA A A A AAA A AAAAAAAA AAA A AAAAA A AAAAAAAAAAAA AA AA AAAAAAAAAAAA AAAAAA AA AA AA AAAA AAAAAAAA A AAAAAAAAAAAAAAA A A A AAAAAAAAAAAA AAAAAAAA AAAAAAAAAAA AA AAAAAAAAAAAA AAA AAAAA A AAAA A AA A AA A AAAA A A A AAAAAAAA AAA A AA AAAA AAAAAAAA AAAAAAAA AA AAAAAAAAAAAA AAA A AAAA A AAAAAAAAA A AA AAAAAAAA A AA A A AAA AAAA AAAA AAAA AAAAAAAA AAAAAAAAAAAAAAAAAAA A A AAAAAAAAAAAA AAA AAAAAAAA A AAAAA AAAAA A A A AAAAAAAA AAAAA AAAA AAA AAAAAAAA AAAAAAAAAAAA AAAAAAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAA AAA AAAAAAAA A AAAA AAAAAAAAA AAAAAAAA A AAAA A A AAAAAAAAAAAA AAAA AAAAAAAA A A AAAA A AAAAAAAA A A A AAAAAA AAAAAAAAAAAA AAAAA AAAA A A AAAAAAAAAAAA AAAAAAAAA A AAAA A AAAAAAAAAAAA AAAAAAAAA AAAAAAAA A AAAAAAAA A AAA AAAA AA AAAAA AAAAA AAAAAAAA A AAA A AAAAAAAA AAAA A AAAAAAAAAAAAAAAA AAAAAAAAA A AAAA AAAAAA AAAA AAAAAAAAA A AA AAAA AAAA A A AAA AAAAAAAAA AAAAAAAAAAAA AAAAAAAAAAAA A A AAAAAAAA AAAAAAAA AAA AAAAA AAAA AA AA AAAAAAAAAAAA AAAAAAAAA AAAAAAAA A A A AAA A AAAAAAAA A AAAAA AAA A AAA AAAAAAAAAAAA AAAAAAAAAA AAAAA A AAA AAAAAAAA AAA AAAAA AAAAAAAAA AAAAAAAAAA AAAAAAAA AAAAAAAAAAAAAAAAAAA AAAA AA AAAAA AAA AAAAAAAAA AAAAAAAA A AAAAAAAAA A A AAAAAAAA A AAAA AAA A AAAAAAAA AAAAAAAA AAAAAAAAAAAAAA AAAAA AAAAAAAA A AAAA AAAAAAA A A A A AAA A AAAAAAAA A AAA AAAAA A AAA A AA AAAAAAAA AAAAAAAAAAAAA AAAAAAAAA AAAAAAAA AAA A AAAA AAAA AAAAAAA AA AAAA AAA AAAAAAAA A AA AAA AAAAAA A A AAA AAA AAAA A A A A AAAAAAAA A AAAAA AAAAA AAAAA A AAAAA AAAAAAAA AAAAAAAAAA AAAAAAAAA A AAA AAAA AAA A AAAA AAAA A AAAAAAAAA A AAAAAAAA AAA AAAAAAAAAAAA AAAAAA AAAAAAAAAAAAAAAA AAAAAAAA AAAAA AAA A AAAAA AAAAA A AAAAAAAAAA AAAAA AAAAAA AAAAA AAAAAAAA AAAAAAAAAAAA AAAAAAAA A AAAAAA AAAAAAAA AAA AAAA AAA AAAAAAAA A A AAAA AAAAA A A AAAAAAAAA AAAAA AAAAAAAA A AAAAAAA A AAAA A AAAAA AAAAAAAA A AAAA AAA AAAA AAA AAAAAAAA A AAAAAAAA AAAAAAA AAAAAAA AAAAAAAA AAAAAAAAAAAA AAAAAAAA AAAAAAAAAAAA AAAAAAAA AAAAA AAAAA AAAAAAAA A AAAAAAAA AAAAAAA A AAAAA AAAAA AAA AAAAAAAA A AAAA A A A AAAAAAAAA A A AAAAAAAA AAAAAAAA AAAAAAA AAAAAAAA AAAAAAAAAAAA A AAAAAAAAAAAA AAAAAAAA A A AAAAAAAAA A A AAAAAAAAA AAAAAAA AAAAAAAAAAAAAAAA AAAAA AAAAAAAA AAAAAAAAAAAA AAAA AAAAAAAA AAAAAAAA A A AAAAA AAAAAAAAA A A AAAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAA AAAAAAAAAAAA AAAAAAAA AAA AAAAA AAAAAAAAA AAAAAAAAA AAAAAAAA A AAAAAAAA AAA AAA AAAAAAAAA AAAAA AAAAAAAAAAAA AAA AAAA AAA A AAAAA AA AAAA A AA A A A A AAAAAA AAAAAAAAA AA AAAAA AAAAA A AAAAA A AAAAAAAAAAAAAAAAAAA A AAAAAAAA A AAAAAAAA AAAAAAAA A AAA A AAAAAAAAA AA AAAAAAAAAAAAAAAA AAAAAAAA AAAAAAAAAAAA AAAAAAAA AAAAAAA AA AAAAA AAAAAAAAAAAA A AAAAAAAAAAAA AAA AAAA AAA AAAAA AA AA AAAAAAAAA AAAAAAAA A AAAAAAAA A AAAAAAAA AAAAAAAAAAAA AAAAAAAA AAAA A A A AAA AAAAA AAA A AAAA AA A AAAA A AA AAA A AAA AAAAA AAAA AAAAAAAAAAAAAAAAAAA AAA AAAAAAAA AAAAAAAAAAA AAA AAAAAAAAA AA AAAAAA AAAAAAAAA AAAAA AAAAA AAAAAAAA AAA AAAAAAAAA AAAA AAAAAAAA A AAAA AAAAAAAAAAAAAAA AAAAAAAAAAAA A A AAAA AA AA AAAAAAAA A AAAAA A AA AAAAA A AAAAA AAAAAAAA AAAAAA AAAAA AAAA A AAAAAAAA A AA AAA A A AA AAAAAAAAAAAAAAAA AA A AAA A AAAAAAAAA AAAAAAAA AAA AA A A A AAAA AAAAAAAAAAAAAAAA AA AA AAA AAAAAAAAA AA AAAAAAAA AAA AAAAAAAAA A A AAAAAAAAA AAAAA AAAAAAAA AA AAAAAAAA AAAAA AAAAAAAA AAAAAAAAA AAAA AAAA A A AA AAAA A AA A A AAAA AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAAA AAAA AAA AAAAAAAAA A A AAAAAAAAAAAA AAA AAAAAAAA A AAAAAAAA AAAAAAAAAAAA AAAA A AA A AAAAAAAAA AAAA AAAAAAAA AAAA A AAAAA A A AAAAAAAAAAAAAAAA AAAAAAAAA AAAAAAAAA AA AAAAAAAA A AAAAAAAAA AAAAA AA AAAA AAAAA AAAA AAAA AAAAAAAA AAAAA AAAAAAAA AAAAAAAA A AAAAA AAAAAAAAA A AAAA AAAAAAAAAAAAAAAA AAAA A AAAAA A A A A A A AAAAAAAAAAAA A AAAAA AAAAA AAAAAAAA AAAAAAAAAA AAAAAAAAA AAAAA AAAAAAAAA A AAAAAAAAA AAAAAAAA A AAAAAAAAAAAAAAAA A AAAAAAAAAAAAAAA AAAAA AAAA AAAAA AAAAAAAA AAAAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAA AAAAA AAAAA AAAAAAAA AAAAAAAAAAAAAAAA A A A AAAA A AAAAAAAAAAAAAAAA AAAAAAAA AAAAA AAAAA AAAAA AAAAAAAAAAAA AAAAA AAAAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAAA AAAAA AAAAA AAAAAAAA A AAAAAAAAAAAA AAAAAAAAA A AAAAA A AAAAAAAAAAAAAAAA AAAAAAAA AAAAA AAAAAAAAA AAAAA A A AAAAAAA AAAAAAAAAAAAAAAA AAAA A A AAAAA AAAAAAAAA AAAAA AAAA A AAAAAAAAAAAA A A AAA A A AAAA AA AAAAAAAAA AAAAAAAAAAAA A AAAAA A AAAAA A A AAAA AAA AAAAAAAA AAAAA AAAAA AAAAAAAAA AAAA A AAA AAAAAA A AAAAAAAAAAAA AAAAA AAAAAAAAA A A AA AAAAAA AAAAAAAA AAAAAAAAA A AAAAAAAAA A AAAA AAAAAAAA AAAA AAA AAAA AAAAA A AAA AAAA AAA AAAAAAAA AAAAAAAAA AAAAA AAAA AAAAAAAAA AAAAAAAA A AAAAAAAAA A AAAAA A AAA A AAAA AAAA AAAAAA AA AAAAAAAA AAAAA A AAAAA AAAAAAAAA AAAAA AAAAA AAAAAAAAA A AAAA A AAAA A AA AAAAAA AAAAAAAA A AAA A AAAAAAAA AAAA AAAAAAAAAAAA AAAA AA A AAAA AA A AAAA A AAAAA AAAAAAAA AA AA A

AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA

3-3.5 2.5-3 2-2.5 1.5-2 1-1.5 0.5-1 0-0.5

80

60

40

20

0

10

20

30

40

50

60

70

80

Freq (kHz)

Figure 19 - Absorption loss (dB/m) as a function of frequency and humidity in still air at 20o C - data derived from Weast and Astle (1978).

0.12 0.1 0.08 0.06 0.04 0.02 0 0 5 10 15 20 25 30 35 T ime (us ec)

Figure 20 - Impulse response of air at 50% humidity, 4 m travel and 20o C. The absorption loss of air is a function of temperature and the data at 20o C is therefore not sufficient for estimating the impulse response. In practice it is only necessary to produce an impulse response function that fits the observed data well. Our approach is to use scaled versions of the 20o C data to account for variations in temperature. The scale factor can be interpreted by observing that the absorption per meter at the actual temperature and humidity can be approximated by an absorption at o 20 C and possibly different humidity, h, over a new distance of scale meters. In

21 addition to our reference pulse, ref, we collect another pulse, ref2, from a plane at a range, (rref+rsep)/2. Given values of h and scale, we can predict ref2 with predict (t , h, scale ) = ref (t ) ? hair 20 (t , h, scale. rsep ) A squared error cost function is now defined cost ( h, scale) = min ∑ ref 2(t ) ? predict (t ? τ, h, scale)
τ t

(26)

a

f

2

(27)

The minimum over τ is necessary to ensure alignment between the two pulses. In practice the minimum is approximated using parabolic interpolation on the minimum three square errors spaced by the 1 ?sec inter-sample time of the pulses. Without interpolation, troublesome local minima are introduced into the cost function. The cost function is plotted in Figure 21 for a set of data collected under conditions of 60% humidity, 25o C and rsepof 4 meters. The variable dist in Figure 21 is defined as 4 scale meters. The minimum occurs at 40% humidity and dist=5.4m. The simplex algorithm (Press 1990) is employed as a robust technique for finding the location of the global minimum of the cost function. The experimental data, ref2, at 3 meters range and the pulse, predict, that minimizes the cost function, cost, are plotted in Figure 22. The root mean squared error per sample is 1.8 mV which is comparable to the noise level in this experimental data. The reference pulse shape at 1 meter can be seen in Figure 16 and is quite different to that of Figure 22. In order to test the model, predicted and experimental data are compared at ranges different to the 1 and 3 meters used for calibration. These are shown in Figure 23 at 2 meters and 5 meters range. The estimated impulse response of air thus performs well for both interpolation and extrapolation.

0.00145 0.00125 0.00105 0.00085 0.00065 0.00045

AA AA AAAA AA AAAA AA AAAA AA AAAA AAAA AAAA AAAAAA AAAA AAAA AAA AAAA AAAAAA AAAA AAAA AAA AAAA AAAAAA AAAA AAAA AAA AAAA AAAA AAAA AAA AAAAAA AAAA AAAAAA AAAA AAAA AAA AAAA AAAAAA AAAA AAA AAAAA AAAA AAAAAAAA AAAA AAAA AAAAAA AAAAAAA AAAA AAAA AAAA A AAAA AAAAAA AAAAAAA AAAA AAAA AAAA A AAAA AAA AAAA AAAA AAAAAA AAAAAA AAAA AAA AAAAA AAAAAAAAAAAAAAAA A A A AAAAAA A AAAAAAAA AAAAAAAAAAAAAAA AA AAAAAAAAAA A AAAA AAA AAAAAAAA AAAA AAAA A A AAA AAAAA AAAAAAAAAAAA A AA AAA AAAA AAAAAAAAAA AA A AAAA AAAAAAAAAAAAAAAAA AAAAA AAAA AAAAAAAA AAA A A AAAAAAAAAA AAAA AAAA AAAAAAA AAAA AAAA AAAA AAAAA AAA AAA AAAA A AAAA AAA AAAAAAAA AAAAAAAA AAA A A AA AAAA AAAAAAA AAAA AAAAA AA AA AAAAAAAAAAAA AAAA AAAAAAA A AA AAAAA AAA AAAAAAAA AAAAAAAA AAAAAA AAAAAAAA AAA A AAAA AAAA AAAA AAAAA AA AAAA AAAA AAA AAA AAAA AAAAAAA AAAA AAAA AAAA AAAAAAAA AAAAAAAA AAAAA A AA AAAA AAAAA A AA AA AAAAAAA AAAAAAA AAAAAAAA AAAAAAAAAA AAAA AAAA AAAA AAAAA AA AAAAAAA AAAAAA AAAAAAA A AAAA AAAA AAAA AAAAAAAA AAAAA AAAA A AAAAAAAAAA A AAAAAAAA AAAAAAAAAAAAAAAAAAA A A AAAAA AAAA AAAAA AAAA AAAAA A AA A AAA AAAA AAA AA AAAAA AAAAAA AAAAA A AA AAAA AAAA AAA AAAAAA AAAAA AAAAAA AAAAAAA A AAAA AAAA AAAA AAAAAAA AAAAAA A AAAA AAAAA A AAAAAA A AAAAAAAAAAAAAA AA AAAAAAAA AAAAA A AAAAAA A AAAAAA AAA AAAAAAA AAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAA AAAA AAAAA AAA AAAAA A AAAA AAAAAAA AAAA A AAA AAAAA AAAAA AAA AAAAAAAAAA AAA AAAA AAAAAAAAAAAAAAAA AAAA AAAAA A AAAAAAAAA AAA AAAAAAAA AAA AAAA A AAAA AAA AAAA AAAAAAAA AAA AAAAAAAAAA AAAA AAAAA AA AAAA AAAAAAAAAAAAAAAA AAAAA AAAA AAAA AAAAAAAA AAAA AAAAAA A AAAA AAA AA A AA A A AAA AA AAAAAAAAAAAAAAAAAAAAAAAAA AAA A AAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAA AAA AAAA AAAAA AAAA AAAAA AAAA AAAAA AAAAAAAA AAAAAAA AAAAAAAA AAAAAAAAAAAA AAAA AAA A AAA A A AA AAAAAA AAAAA AAA AAAAA AAAA AAAA A AAAA AAAAAA A AAA A AA AAAAAAAAAAAA AAAA AAAA AAAA AA AAAA AAAA AAAA AAAA AAAA AAAA AAAA AA AAAAA AAAA AAAAAA AAAAA AAAA AAAAA AAAA AAAAAAAAAAAA AAA AAAA AAAA AAA AAAA AAAA AAAA AAA AAAAAA AAAA AAAA AA AAAA AAAAAAA AAAA AAAA A AA AAAAAA AAAAAAAAAAAAAAAA AAAAAA AAAAAAAAAAAAAAA AAAA AAAA AAAA AA AAAA AAAA AAAAAAA AAAA AAAAAAA AAAA AAAAAAA AAAA AAA AAAAAAA AAAAAAAA AAAAA AAAA AAAAAAAAAAAAAAAAAAAAAAAAA AAA AAAA AAAAAAA AAAA AAAAAAAA AAAAAAAAAA AAAA AAA AAAAAA AAAAAAAA AAAAAA AAAAA AAAA AAAAAAAAAAAAAA AAAAAA AAA AAA AAAA AAA AAAA AAAAA AAAA AAA AAAAAAAA AAAAAAA AAAAAAA AAAA AAAA AAAA AAAAAAAAAAAAAAA AAAAAA AAAAAAAAAAAAAA AAAAAA AAAAAAAA AAAA AAAA AAAA AAAA AAAA AA AAA AAAAAAA AAAAAA AAAAAAA AAAA AAAAAA AAAAAAAAAAAAAA AAAAAAA AAAAAAA AAAA AAAAAAA AAAA AAA AAAAAAA AAAA AAAA AAAAAAA AAAA AAAAAAAAAA AAAAAAAAAAAAAA A AAAA AAAAAAAA AAA AAAAAA AAA AAAAAAAAAA AAAAAAAAAAAA AAAA AAAAAAA AAAA AAAAAAAAAAA AAAA AAAA AAA A AAAA AAAAAAAAAA AAAAAAAAAA AAA AAAAAA AAA AAAAAA AAAAA AAAA AAAA AAA AAAAAA AAA AAAAAA AAA AAAAAAAAAA AAAAAAA AAAAAAA AAAA AAAAAAA AAAAAAAAAAAAAAAAAAAAAAA AAAA AAAAAAA AAAAAA AAA AAAAAAAAAA AAAAAAA AAAA AAAA AAA AAA AAAA AAAAAA AAAAAAAAAA AAAAAAAAA A A AAAAAAAAA AAA A AAAA AAAA AAAA AAAA AAAAAAAAAA AAAAAAAAAAAAAAAAAA AAAAAAAAAAAA AAA AAA AAAAAAAA AAA AAAAAA AAA AAAAAA AAA AAAAAAAAAA AAAAAAAAAAA AAAAA AAAAAAAA A AAAAAAAA AAAA AAAAAA AAA AAA AAAA AAAAAAAA AAAA A AAAA AAAAAAAA AAAA A AAAAAAAAAA AAA AAAAAA AAA AAAA AAA AAAAAAAAA AAAAAAAAAAA AAAAAA AAAAAAAAAA AAA AAAA AAAA AAAA AAAA AAA AAAA AAA AAA AAAAAAAAAAA AAA AAAA AAA AAAAAAAA AAAAAAAA AAAA A AAAA A AAA AAA AAA AAAA A AAAA AAAAAAA AAAAAA AAA AAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAA AAAAAA A AAA AAAAAAAA AAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAA AAAAAAAA AAAAA A AAAA AAAAA A AAAAAA A AAAA AAA AAAA AAAAAAAAAAA AAAA AAAAAAA A AAAAAAAA AAA AAAA AAAAAAAA AAAAA AAAA AAA AA A AAAAA A AAAA A A AAAAAA AAAA AAAAAAAAAAAA AAA AAAAA AA AAAAAA AAA AAAAAA AAA AAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAA AAA AAAA A AAAA AAAAA AAAAAAAAAA AAAAAAA A A AAAAAAAAA AAAA AAAAAAAAAAAAAAAAAAAAA AAA AAAA AAAAAAAAAAAA AAAAAAA AAAA AAA AAA AAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAA AAAAAAAAAAAA AAAAA A AAAAAA AAAAAA AAAA AAAA A AAAAAA AA A AAAA AAAAAAAA AAAAAA AAAAA A AAA AAAA AAAAA AAAAAAAAAAAAAAA AAAAAAAAAAAA AAA AAAAAAAAA AAAAAAA AAA AAAAAAAAAAAAAAAAAAAAAAAAAAA AA AAAAA AAAA AAAAAA A AAAAAAA AAA AAAAAAA AAAA AAAA AAAAA A AA A A AA AAAAA AAAAAAAA AAAAAAAAA AAAAA AAAAAAAA AAAAAAA A AAAA AAA A AAA AAAA A AAAA AAAA AAAA AAAAAAAAAAAAAAAAAAAAA AAAAAAAAAA AAAAAAAAAAAAAA AAAAAAAAAAAAAA AA AAAAAAAAA AAAA AAA A AAAAAAAAAAAAA AAAAAA AAAA AAAAA AAAAAAAAAA AAAAAAA AAAAAAAA AAA AAAAAAAAAAAA AAA AAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAA AAAA AAAAAAAA AAAAAAAAAA AAAAA AAAA AAAAAAAAAAAA AAA AAAAAAAA AAA AA AAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAA AAAAAAAAA AAAAAAAAAAAAAAA A AA AAAAAAA AAAAAAAA AAA AAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAA A AAAA AAAAAAA AAAA AAAAAAAAAAAAAAAA AAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAA A AAA AAAA A AAAAAAA A A AAAA A AAAAAA AAAAAAAAAA AAA AAAA AAA AAAA AAAA AAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAA AAAAAAAAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAA AAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAA AAAAAAA AAAAAAAAAAA AAAAAAAAAA AAAAAAAAAAAAAAAAAAAAA AAAAAA AAAA AAAA AAA AAAA AAAA AAAAAAAAAA AAAAA AAAAAAAA AAAAAA AAAAAA AAAA AAAAAAAAAAAAAA A AAAAAAA AAAA AAA AAAA AAA AAAAAA AAAAAAAAAAAAAAA AAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAA AAAAAAA AAA AAAA AAAAAAAAAA AAAAAAA AA AAAAAAA AAAAAAAAAAAAA AA AAAAAAA AAAAAAAAAAAA AAAAAAAAAA AAAA AAA AAAA AAA AAAA AAA AAAA AAA AAAAAAAAAA AAA AAAA AAA AAAA AAAA AAAAAAA AAAA AAA AAAAAAAAAA AAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAA AAAA AAAAAAAAAAAA AAA AAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAA AAAAAAAAAA AAA AAAAAAAAAAA AAAAAA AAAAAAA AAAAAAAAAAAAAAAAAAAAA AAAA AAA AAAA AAAAAAA AAAA AAAAAAA AAAAAA AAAAAAA AA AAAAAAAAAAAA AAAAAAAAAA AAA AAAAAA AAAAAAAAAA AAA AAAA AAAAAAA AA AAAAAAAAAA AAAA AAAAAA AAAAAAA AAA AAA AAAA AAAAAAAA A AAAA AAAAAAAAAAA AA AAAAAA AAA AAAA AAAAAAA AAA AA AAAAAAA AAAAAAAAAAAAAA AAAAAAAA AAAAAAAAAAA AAA AAAAAAA AAAA AAAAAAAAAAAA AA AAAA AAAAAAAAAAAAAA AAAAAA AAAAAAAAAAAA AAA AAAA AAAAAAA AAAAAA AAAAAAAAAAAA AAAAAAAAAA AAAAAAAAAAAAAA AAAAAA AAA AAAAAAAA AAAA AA AAAAAAAAAA AAA AAAA AAAAAAAAAAAAAAAAAAAAAAAAA A AAAAAAAAAAAAAAAAAAA AAAAAAA AAAAAAA AAA AAAA AAAAAAA AAA AAAAAAAAAAAA AAA AAAAAAAAAAAAAAAA A AAA A A AAAAAAAA AAAA AAAAAAAAAAAA AAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA A AAAAAAAA AAA AAAAAA AAAAAAAAAA AAAAAAAAAAAAAAAAAAAAA AAA AAAAAA AAAAAAAAAA AAA AAAA AAAAAAAAAA AAAAAAA AAAA AAAAAA AAAAAAAAAA A AAAAAAAA AAA AAA AA AAAAAAA AAAAAAA AAAA AAAAAAA AAAA AAA AAAA AAAAAAAAAAAA A A AAAA AAAAAAAA AAAA A AAA AAAA AAAA AAA AAAAAAAAAA AA AAAA AAA AAAA A AAAA AAAA AAAA A AAAAAAAAAAA AAA AAAA AAA AAAA AAAAAAAAAA AAAAAA AAAA AAAA AAAA AAA AAAA AAAAAAA AAAAAAAA AAA AAAAAA AAA AAAAAA AAAAAAAAAA AAA AAAAAAAAAA AAAAAAAA AAAAAAAAAA AAAAAAA AAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAAAAAAAAAA AAAAAA AAA AAAA AAAAAAAA AAAA AAAAAAAA AAAAA A AAAAAA AAAAAAAA AAAA A AAAA AAAAAAAAAA AAA AAAAAA AAAAAAAAAA A AAA AAAA AAAAA AAAAAAAAAA AAAAAA AAAAAAAAAAA AA AAAAAAAAAA AAAAAAAAAA AAAAAAAA AAAAAAAAAAAAAAAAAAAAAA AAA AAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA A AAA AAAAAAAAAA AAA AAAAA AAA AAAAAA A AAAAAAA AAAA AAA AAA AAAA AAA AAA A AAA A AAAA AAAA A AAAA AAAA AAAAA AAAAAAAAAAAA AA AAAA AAAAAAAAAAAAAAAAAA AAAAAAAAAA AAAAAAAAAA AAAAAAAAAAAAAA AAAAAAAAAAAAAAAAA AAAAAAA AAAA AAAAAAA AAAA AAAAAAAAAAAAAAAAAAAAA AAAAA AAAAAAAAAA A AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAA AAAAAAAA AAAAAAAAAAAAAAAAAAA A A AAAA AAAAAAA AAA AAAAAA AAA AAAAAA AAAAAAAAAAAA AAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAA AAAAAA AAA AAAAAAAA AAA AAAA AAAAAAAAAAAAAAAA AAAAAAA AAAAAAAA AA AAAAAAAAAA AAAAAAAAAAAA A A AAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAA AAAA AAA AAAA AAAAAAA AAAA AAAAAAA AAAA AAAAAAA AAAA A AAAAAAAAAAAAAAAAAA AAAA AAAA AAAAAA AAAAAAA AAAAA A AAAA AAAAA AAA AAAAAAAA AAAAAAA AAAAAA A A AAAA A AAA AAAAAAAA AAAAAAAA AAAA AAAA AAAA AAAA AAAA AAA AAA A AAA AAAA AAAA AAA AAAA AAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAA AAAAAAAAAAAA AAAAAAAAAAAAAAAAAA AAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAA AAA AAAAA AAAAAA AAAAAAAAAAAA A AAAAAA AAAAAAA AAA AAAAAA AAA AAAAAAAAAAAAAAAAAAAA AA AA AAAAAAAA AAA AAAAAA AAAA A AAA AAAA A AAAAAAAAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAAAAAAAA AAAA A AAAAAAA AAAAAAAAAA AAAAAAA AAAAAAAA AAAA AAAAAAAA AA A AAAAAAAAAAAAAAAAAA AAAAAA AAAAAAAAAAA AA AAAA AAAA AAAAAAAAAAAAAAAAAAAA A AAAA AA AAAA A AAA AAAAA AA AAAA AAA AAAA AAA AAAAAAAA AAA AA AAAAAAA AAAAAA AAAAA AAAAAAA AAAA AAA AAAAAA A AAAA AAAA AA AAAAAAAAA AAAAA AAAAAA AAAAAAAAA AAAAAA AAAAA AAA AAAAAAA AAAA AAAAA A AAAA AAAA A AAAA AAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAA AAAAAAA AAAAAAAAAAAAAAAAAA AAAA AAAA AAAAAAA AAAA AA AAAAAA AAA AAAAAAAAAA AAAAAAA AAA AAA A AAAA AA AAAA AAAA AAA AAAAAA AAAA AAAAAAA AAAA AAAA AAAA AAAA AA AAAAAAAAAAAAAAAA AAAA AAAA A A AAAA AAAA AAAAAAAA A AAAA AAAA A AAAAA AAAA AAAAA AA AAAA AAAA AAAA AAA AAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAA AAAA AAAAA AA AAAAA AAAAAA AAAAAA A AAAAAAA AAA A AA AAAAA AAAA A AAAAAAA AAAA AAAAAAAA AAAA

AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA AAAAA

0.00125-0.00145 0.00105-0.00125 0.00085-0.00105 0.00065-0.00085 0.00045-0.00065 0.00025-0.00045

0.00025 50 % humidity

45

40

35

5.25

5.5

5.75

6

Dist (m)

Figure 21 - Square error cost function for estimating hair.

22

0.05 0.04 0.03 0.02 0.01 0 -0.01 -0.02 -0.03 T ime (us ec)-> 0 10 20 30 40 50

Figure 22 - Experimental and best match predicted data for absorption modeling (3 meter range).

0.04 0.03 0.02 0.01

0.004 0.003 0.002 0.001

0 -0.01 -0.02 -0.03 T ime (us ec) 30 40 50 60 70 80 0 -0.001 -0.002 T ime (us ec) 30 40 50 60 70 80

Figure 23 - Predicted and measured pulses at 2 and 5 m ranges.

7. Distance of Flight Estimation
In the previous section we showed that in the absence of noise, the echo pulse shape can be predicted with a linear model. In this section we consider the problem of estimating the DOF of the echo in the presence of noise. From a calibrated value of the speed of sound, the DOF can be obtained from an estimate of the TOF, which will be shown to depend on our predicted echo pulse shape. The receiver noise is approximated by white Gaussian band-limited noise. The background receiver noise was measured by not sending a pulse and analyzing the received signal. The spectrum and distribution of the noise measured at a receiver is shown in Figure 24. The skew (normalized third moment) and Kurtosis (normalized fourth moment) (Larsen and Marx 1985) of the noise distribution are 0.26 and 3.46 and are 0 and 3 for a Gaussian distribution respectively. When the receiver bias voltage was removed, little change in the noise level occurred, suggesting that the noise is dominated by amplifier noise. The gain of the amplifier was designed to roll off at around 500 kHz and this will be assumed to be the bandwidth of the noise. With the sample rate at twice the noise bandwidth, the noise samples can then be assumed to be uncorrelated with each other (Woodward 1964). Moreover the power

23 spectral density of the noise, N0, defined as the mean noise power per unit bandwidth can then be shown to be N0 = σn2 = 2 Ts σ n 2 W (28)

where W is the noise bandwidth and is half the receiver sampling frequency, σ n 2 is the variance of a noise sample, and Ts is the sampling period.
Nois e S pectrum
0 -10 -20 -30 -40 -50 -60 -70 F req (kH z)

160 140 120 100 80 60 40 20 0

Voltage

Figure 24 - Receiver noise spectrum and histogram from 512 samples on R2. From the theory of radar (Woodward 1964), the maximum likelihood estimator for the arrival time of a pulse with additive white Gaussian noise is the time τ that maximizes the cross correlation, Cor ( τ, θ T , θ R ) , between the received pulse with noise, p(t),and the actual pulse shape, rec(t , θT , rT , θ R , rR ) :

Cor ( τ, θ T , θ R ) =

z z z
b a b b 2 a a

p(t )rec(t ? τ, θ T , rT , θ R , rR ) dt (29)
2

p (t ) dt rec (t , θ T , rT , θ R , rR )dt

Note that the correlation, Cor ( τ, θ T , θ R ) , has been normalized to be between -1 and 1 and achieves 1 only when the echo pulse is exactly the same shape as the predicted pulse. The correlation also gives a measure of the degree of similarity between the two pulse shapes. The limits of integration, a and b are selected to cover the pulse duration. The parameters rR and rT can be adequately estimated from the approximate location of the pulse and so are not included as parameters in Cor ( τ, θ T , θ R ) . The angles to the normals of the transducers, θR and θT need not be known at this stage, rather the best match of a set of templates generated from a set of angles is used. For ranges of the reflector much larger than the transmitter separation, it is sufficient to use templates rec(t , θT , rT , θ R , rR ) with θR and θT equal, as in Figure 25. This limits the template search time with little effect on accuracy. Moreover the templates are normalized to unity energy so that the second integration in the denominator of equation (29) is not required.

24

1.00 0.95 0.90 0.85 0.80 0.75 0.70 0.65 0.60 0 2 4 6 8 10 12 14 16 18 20 Angle(degrees )

Figure 25 - Measured correlation against θR =θT for a plane at 10o inclination to θ transmitter and receiver. In practice, discrete time versions of the signals are only available and so Cor ( τ, θ T , θ R ) is evaluated at discrete times (1 ?sec apart in our sensor) with summations rather than the integrals. To achieve sub-sample resolution, parabolic interpolation is performed on the maximum three samples of Cor ( τ, θ T , θ R ) to find a better estimate of the position of the maximum. If the three maxima y0, y1, and y2 occur at integer sample numbers 0,1 and 2, the parabolic estimate of the position of the maximum is maxpos = y2 ? 4 y1 + 3 y0 2( y2 ? 2 y1 + y0 ) (30)

7.1. Distance of Flight Jitter
The estimate of DOF described above inevitably has errors due to receiver noise and actual physical variations in the TOF due to random properties of air, such as turbulence, local temperature fluctuations and gradients. These DOF estimate errors, called jitter here, need to be characterized so that the level of confidence of measurements and reflector discrimination can be determined. We start by examining the jitter attributed to receiver noise. From Woodward (1964), when the energy of a pulse, E, is much larger than the noise power spectral density, N0 , the standard deviation of the correlation estimate of arrival time, σR, is σR = 1 B N0 2E (31)

where Β is the bandwidth of the pulse defined by the normalized second moment of the pulse power spectrum: B = 2π

z

F ( f ? f0 ) df
2

z

2

F df

2

(32)

where F is the Fourier transform of the pulse, f is frequency and f0 is the centroid of the power spectrum defined by:

25

f0 =

z z

F f df F df
2

2

(33)

For a typical reference echo pulse, f0 is 65 kHz and Β/2π is 21 kHz. Equation (31) and (28) combine to give σR = σn B

∑ rec( kTs )2
k

(34)

where the integer sample number k sums over the pulse duration. The noise standard deviation on R1 is 0.96 mV and on R2 is 0.55 mV and can be assumed to be uncorrelated with a measured correlation coefficient of 0.02. From equation (34) and measured pulses at a range of 3 meters from an aligned plane (plane and sensor normals aligned), the results in the Table I are obtained for the standard deviations of the DOF due to amplifier noise. TABLE I Estimated DOF errors due to amplifier noise. Stdev (mm) Transmitter 1 Transmitter 2 Receiver 1 0.022 0.023 Receiver 2 0.015 0.013 We now examine measured DOF data for an aligned plane at 3 meters range. Figure 26 shows the data plotted in time sequence. The standard deviation of the DOF data is 0.4 mm and has been found to depend on air flow conditions in the laboratory - the results here were collected with computer fans and air conditioning vents operating as might be the case in a typical office environment. From the results in Table I, it is clear that the jitter is not dominated by thermal noise in the amplifier. The jitter in the triggering of the data capture system has a standard deviation of less than 0.5 ?sec or 0.17 mm from measurements and manufacturers specifications. Therefore most of the DOF jitter is attributed to variations in the TOF of the pulses through air. The transmitters fire at approximately one second intervals in Figure 26 and there is a noticeable jitter correlation between receivers and also between receivers with different transmitters. The correlation between the jitter on two receivers listening to the same pulse is 0.997. The standard deviation of the difference between estimates of DOF on the two receivers for the same pulse is 0.040 mm. Table I implies the contribution due to amplifier noise is . 0232 +. 0132 =0.027 mm or about half . The distribution of the jitter with 350 samples appears to be Gaussian as shown in Figure 27 and has a skew of -0.03 and Kurtosis of 2.82. The distribution of the difference of DOF for the two receivers with the same pulse, called jitter difference, also appears Gaussian with a skew of -0.14 and Kurtosis of 2.89. The correlation between the jitter difference and jitter is -0.1 to -0.2 for the combinations of receivers and transmitters. The correlation is 0.73 between jitter on DOF of a pulse from T1 and the successive pulse from T2 on the same receiver. The correlation

26 between jitter differences on successive transmitters is 0.45. Therefore the covariance matrix R of Section 5.4 has significant off-diagonal elements. Correlation coefficients for experimental data at other DOFs are plotted in Figure 30. These are discussed in the next section. The results above can be explained by local variations of the speed of sound slow enough to show correlation after times in the order of seconds. The spatial correlation of the speed of sound variations is high compared to the receiver spacing. This is necessary for high bearing accuracy with closely spaced receivers. These effects are most likely caused by the slow mixing of air of different temperatures, like a cold draft on a Winter's night. The increased fluctuation of DOF with increased air flow observed in the laboratory is consistent with this view. Other authors have reported similar results (Brown 1985 and Peremans 1993). Figures 28 and 29 show the standard deviation of 400 samples of measured DOF and difference in DOF for a range of 0.5 m to 5 m of an aligned plane. The standard deviation at DOF less than 2 meters is mostly due to the data capture triggering component of 0.17 mm as discussed above. This data shows the effect of distance in the jitter of measurements and it can be seen that the jitter is somewhat spurious due to local air currents in the laboratory. The difference jitter in Figure 29 shows a more definite trend with distance. The difference jitter due to the amplifier noise is shown as the solid line and approaches the actual difference jitter as the range increases due to declining signal to noise ratio.
Distance of flight

6.010

meters

6.005

6.000

5.995 1 51 101 151 Sample 201 251 301

Figure 26 - Measured DOF against sample for an aligned plane at 3 meters range. The top two traces are from transmitter T1 with receivers R1 and R2, and the bottom two closely spaced traces are T2 with R1 and R2.

27

Dis tance of F light E rror His togram 45 40 35 30 25 20 15 10 5 0

Dis tance error

Figure 27 - Measured distribution of DOF and Gaussian distribution with same standard deviation.
0.0004

0.0003 Stand dev DOF (m)

0.0002 T2 T1 0.0001 T1model

0 1 2 3 4 5 DOF (m) 6 7 8 9 10

Figure 28 - Standard deviation of measured DOF (400 samples each meter) and model for an aligned plane.

28

8.00E-05 Diff2 Stand Dev Difference in DOF (m) 6.00E-05 Diff1 diff_amp Diff1_model 4.00E-05

2.00E-05

0.00E+00 1 2 3 4 5 6 DOF (m) 7 8 9 10

Figure 29 - Standard deviation of measured difference in DOF for an aligned plane (triangles from T1, squares from T2) and the estimate amplifier noise (line) from measured echo energy, bandwidth and a fitted noise spectral density. The dashed line is that used in the model.

0.6

0.5

T1T2 T1T2_model Diff1Diff2

Correlation Coefficients

0.4

0.3

Diff1Diff2_model T1Diff1 T1diff1_model

0.2

0.1

T2Diff2 T2Diff2_model 1 2 3 4 5 6 7 8 9 10

0

-0.1 DOF (m)

Figure 30 - Significant correlation coefficients of measurements and model for an aligned plane.

7.2. A Model for Distance of Flight and Bearing Errors
A simple model is presented for the standard deviation of the DOF and bearing estimates of the sensor. The model is employed for the statistical discrimination of planes, corners and edges presented in Section 5.4. We consider three contributions. The first contribution, nair, is due to fluctuations in the speed of sound, and the second, ntrig, is due to jitter in the data capture triggering. The third contribution, namp, is due to the amplifier noise and is estimated from known pulse and amplifier noise characteristics. The noise in the DOF from transmitter T (1 or 2) and receiver R (1 or 2) is denoted by ndofTR

29 ndofTR = nairTR + ntrigTR + nampTR (35)

and is described in terms of noise variables n's which are each independent, zero mean, Gaussian, unity variance random variables: nairTR = σ air ka na + kalocal naT + ( ?1) R?1 ( kdiff ndiff + kdifflocal ndiffT ) ntrigTR = σ trig ktrig ntrigT + ( ?1) nampTR = σ ampTR nampTR

c

c

R ?1

ktrigdiff ntrigdiffT

h

h
(36)

where the k's are fixed constants defined to have a sum of squares of 1 within each contribution so that nair's and ntrig's all have variances σair2 and σtrig2. Each term in equation (36) has a physical explanation. The terms kana and kdiffndiff are due to the jitter and jitter difference common to all four DOF measurements. The kalocalnaT and kdifflocalndiffT terms account for correlation between receiver measurements taken at the same time. The ktrigntrigT is the jitter in triggering the data capture system common to both receivers and ktrigdiffntrigdiffT is the trigger jitter in the difference of the receivers. The σampTRnampTR term is the independent contribution due to amplifier noise on each receiver/transmitter combination and σampTR is obtained from cσR in equation (34) and is a function of the amplifier noise, pulse energy and bandwidth, all of which are known by the sensor software. The jitter variance attributed to air, σair, is assumed to be proportional to the DOF, dof
2 σ 2 = σ a dof air

(37)

This makes the reasonable assumption that the air path is composed of many independent jitter elements whose net sum is the overall contribution. From equation (36) we can evaluate the variances of the DOF
2 σ 2 T1 = σ 2 + σ trig + σ 2 1 ndof air ampT

(38)

2 From equation (8), the bearing noise, nαT and its noise variance,σ nα T from transmitter T is given by

nαT =

2σ air kdiff ndiff + kdifflocal ndiffT + 2 σ trig ktrigdiff ntrigdiffT + σ ampT1nampT 1 ? σ ampT 2 nampT 2 4σ (k
2 air 2 diff

c

h

2 σ nα T =

+k

2 difflocal

) + 4σ k d

2 2 trig trigdiff 2

d + σ2 1 + σ2 2 ampT ampT

(39) The covariance matrix R of the measurement noise vector [ndof11 nα1 ndof21 nα2]T is given by

30

LMσ σ R=M MMσ NMσ
σ ndof11nα1 =

2 ndof11 ndof11nα1 ndof11ndof21 ndof11nα 2

σ ndof11nα1 σ 2α 1 n σ ndof21nα1 σ nα1nα 2

σ ndof11ndof21 σ ndof21nα1 σ 2 21 ndof σ ndof21nα 2

σ ndof11nα 2 σ nα1nα 2 σ ndof21nα 2 σ 2α 2 n

OP PP PP Q

(40)

Each of these components is a simple function of σ's, k's and d:
2 2 2 2 2 σ 2 ( kdiff + kdifflocal ) + 2 σ trig ktrigdiff + σ 2 11 air amp

d

(41)
2 2 2 σ air kdiff

2 2 σ ndof11ndof21 = σ 2 ( ka + kdiff ) ,σ ndof11nα 2 = air

2 2 σ 2 kdiff air

σ ndof21nα 2 =

2 2 2 2 2 σ 2 ( kdiff + kdifflocal ) + 2 σ trig ktrigdiff + σ 2 21 air amp

d

,σ ndof21nα1 =

d

,σ nα1nα 2 =

2 4 σ 2 kdiff air

d2

d

The above model has been fitted, using a spreadsheet with trial and error, to the experimental data in Figures 28, 29 and 30, and reasonable agreement has been obtained. The following values have been employed: σ a = 0. 0001 m 0.5 , ka = 0. 83, kalocal = 0. 55, kdiff = 0. 044 kdifflocal = 0. 01, σ trig = 0. 00017 m, ktrigdiff = 0. 04, ktrig = 0. 9992 The values of half of the constants are approximately independent of air conditions experienced in the laboratory. Over four experiments under varying air conditions, the following constants varied significantly: σ a = 0. 00008 ? 0. 0003 m 0.5 , ka = 0. 83 ? 0. 93, kalocal = 0. 35 ? 0. 55, kdiff = 0. 023 ? 0. 049 A calibration procedure may be necessary in practice if high precision error estimates are required by an application. The experimental results for an aligned plane have been presented to show the jitter effects due to the air propagation medium. More generally, the covariance matrix for off-axis planes and other reflectors share the same air propagation and data capture jitter characteristics but have different components due to amplifier noise, since the bandwidth and energy of the pulses are dependent on the angle of transmission and reception and reflector efficiency. Since the bandwidth and energy are easily predicted from our linear model, we can estimate our covariance matrix R for all received pulses. The bandwidth versus range and angle is plotted in Figure 31. Note that as bandwidth decreases, the amplifier noise contribution to the jitter increases and the overall error becomes less correlated as a result.

31

25

20 Bandwidth (kHz)

15

10

20 18 16 14 12 10 8

6

4 2

5

AAAA AAAAAAAAAAAAA AAAAAAAAA AAAAAAA AAAA AA AAAA AAAAAA A AAAAAAAAAAAAA AAAA A AAAAAAAAAAAAA AAAA AAAAAAAAAAAAA AAAA AAAAAAAAAAAAA AAAA AAAAAAA AAA AAAAAAAAAAAAAAA AAAA AA AAAA AA AAAA AAAAAAAAAAAAAA AAAAAAAAAAAAAAA AAAA AAAAA AAAAAA AAA AAAA AA AAAAA A AAAAAAAAAAA AAAAAAAAAAAAA A A AAAA AAAA AA AAAA A AAAAAAAAAAAAAAAA AAAAAAAA AAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAA A AAAAAAAAAAAAAAAAAAAAAAAAA AAAA AAAAAAAAAAA AAAA AAAAAAAAAAAAAAAA AA A AAAA AAAA A AAAAAAAAAAAAA AAAAAAAAAAAA AAAAAAAA AAAAAA AAAAAAAAAAAA AA AAAA AAAA AAAA AAAA AAAA AAAA AAAAAAAAAAAAAAAAA AAAAAAAAAAA A AAAA AAAAAAAA AAAAAA AAAAAAAAAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAAAAAA AAAAAAAA AAAA AAAA AAAAAAAA AAAAAAAA AAAA AAAAAAAAAAAAA AA AAAA AAAAAAAA AAAA AAAA AAAA AAAA AAAA AAAAAAAA AAAAAAAA AAAAAAAAAAA A AAAA AAAAAAAA AAAAAA AAAA AAAAAA A AA AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAAAAAA AAAAAAAA AAAAAAAA AAAAAA AAAA AAAA AAAA AAAA AAAA AAAAAAAA AAAAAAAA AAAAAAAAAAAAAAA AAAA AAAAAAAA AAAAAAAA AAAA AAAAAA A AAAA AAAA AAAA AAAAAAAAA AAAA AAAA AAAA AAAAAAAA AAAAAAAA AAAAAAAAAAAAAAA AA AAAAAAAA AAAA AAAAAAAA AAAAAA AA AAAA AAAAA AAAA AAAA AAAA AA AAAA AAAAAAAA AAAAAAAA AAAAAAAAAAAAAAA AAAA AAAA AAAAAAAA AAAAAAAA AAAAAAAA AA AA AAAA AAAAAAAA AAAAAAAA AAAAAA AAAA AAAAA AA AAAA AAAA AAAA AAAAAA AAAAA AA AAAAAAAA AAAA AAAAAAAA A AAAAA AAAA AAAAAAAA AAAA AAA AAAA A AAAA AAAA AAA A AAAAAA AAAAAAAAAAAAA A AA AAAAAAAAAAAAAAAAAAAA AAAAA AAAA AAAA AAAAAAAA AAAAAA A AA AAAA AAAAAA AAAAA AAAA AAAAAA AAAAAA AAAA AAAAAAAAAA AAA AAAA AA AAAA AAAA A AA AAAA AAAAAAA AAAAAA AAAAA AAAA AAAAA AAAAAA AAAA AAAA AAAAAAAAAAAAAA AAA AAAA AA AAAAAA AA AAAAAAAAA AAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAAA AA AAAAAAAAAAAAAAAAA AAAAAAAAAAA A AAAAAAAA AAAAAA AAA AAAA AAAA AAAA AAAAAAAAAA AAAAAA AAAA A AAAAAAAAAAA AAAAAAAA AAAAAA AAAAA AA AAAAAAAA AAA AAAAA A AAAA AAAA AAAA AA AAAAAA AAAAAAAAA AAAAAA AA AAAAA AAAAAAAAA AAAAAAAAAAAAAAA AAAAAA AAAAAAAAAAAAA AAAA A AAAAAAAAAAAAAAAAAAAAAAAAAAA AAAA AAAAAA AAAAAAAAAAAA AAAAAAAA AAAAAAAAAAA AAAA A AA AAAAAAAAAA AAAA AAAA A AAAAAAAAAAA AAAA AAAAAA AAAA AAAAAAAA AAAAAA AAAA AA AAA AAAAAAA AAAA AAAA AAAAAAAA AAAAAAAA AAAA AAAA AAAA AAA AA AAAA AAAA AAAAA A AAAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAA AAAA AAAAAA AAAAAAAA AAA A AA AAA AAAAAAAAA A AAAA AA AAAA AAAAAA AAAAAA AAAAAAAAA AAAAAAAA AAAAAAAAAAA AAAA AAAA AAAAAAAA AAAAAA AAAA AAAAAA AAAAAAAAAAAAAAA AAAAAA AAAAAAAAAAAAA AAAAA AAAA AAAAA AAA AAA AA AAAA AAAA AAAA AAAAA AAAA AAAA AAAAAA AA AAAAA AAAAAAAAAAAAAAAA AAAAAAAA AAAA AAAAA AAAAA AAAAAAAAAAAA AAAA AAA AAAA AAAA AAA AAAA AAAA AAAAAA AAAAAA AAAAAA AAAA AAAA AAAAAAAAAAAAA AAAAA AAAA AAAA A AAAAAA AAAA AAAAAAAA AAAAAAAAAAAAAAA AAAA AAAA AAAAAAAA AAAA AAAA AAAA AAAA AAAAAAAA AAAA AAAAA AAAAAA AAAAAA AAAAAAAAAAAAAAAAAA AAAAAAAA A AAAAA AAAA A AAAA A AAAAAA AAAAAAAAAAAA AAAA AAAAAAAA AAAAAA A AAAAAAAAAAAAAAAA AAAAAAAA AAAAAAAA A AAAA AAAAAAAAAAA AAAAAAAA AAAA AAAAA AAAA AA AAAAAAAA AAAA AAAAA AAAA AAAAAA A AAAA AAAA AAAA AAAAAAAA AAAAAA AAAAAA AAAAAAAAAAAAA AAAA AAAA AAAA AAAA AAAA AAAAAA A AAAA AAAAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAAAAAA AAAAAA A AAAA A AAAA AAA AAAAAAAA AAAA AAAAAAAAAA A AAAA AAAA AAAAAAAA AAAAAAAA AAAA AAAAAAAAAAA AAAA AAAA AAAA AAAAAAAA AAAA AAAA AAAA AAAA AAAAA AAAA AAAA AAAA AAAAAAAAAA A AAAA AAAA AAAAAAAA AAAA AAAA AAAAAAAA AAAA AAAA AAAA AAAAAAAA AAAAAAAA AAAA AAAAAAAA AAAA AAAAAAAA AAAAAAAAAAAAA AAAA AAAA AAAAAAAA AAAAAAAA AAAA AAAA AAAA AAAAAAAA AAAAAAAAAA AAAA AAAAAAAA AAAA AAAAAAAA AAAAAA A AAAA AAAAAA AAAA AAAA AAAA AAAAAA AAAAAA AAAA AAAAAA AAAA A AAAAAAAA AAAA AAAA AAAAA AA AAAA AAAAAAAAAA AAAAAA AAAA AAAAAAAA AAAAAA AAAA AAAA AAAAAA AAAAAA AAAAAA AAAA AAAAAAAA AAAAAAAAA AAAAA AAAAAA AAAAAA AAAAAAAA AAAAAA AAAAAA AA AAAAA AA AAAAAAAA AAAAAAAAAA A A AAAAAA AAAAAAAAAAAAAAAAAA A AAAAAAAAAAAAA AAAAA AAAAAAAAAA AA AAAAAA AAAAAAAA AAAA AAAAAAAAA AAAAAAAAAA AAAAAAAAAAAAAAAAAA AAA AAAAAAAAAA AAAAAAAAAAA AAAAAA AAAAAA AAAA A AAAAAAAA A AAAAAA A AAAAAA A AAAAAAAAAAAAAAAAAAAAAAAAAAA A AAAAAA AAAAA AAAAAA AA AA AAA AAA AAAAAAAAAAAAAAAAA AAAAAAA AAAAAAAAAA AAAAAAAAAAA AAAAAAAA AAAA AAAAAA AAA AAAAAAAAAAA AAAAAAAAAAAA AAAAAAAAAAAA AAAAAA AAAA AAAAAA A A AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAA AAAAAAAA AAAA AAAAAAAA AAAA AAAAA AA AA A A AAAAAAAA AAAAAAA AAAAAAAAAAAAAAAAAAAAAA AAAAAAAA AAA AAAAAAAAAA AA A A AAAA AAAAAAAAAAAAAAAAA AAAAAA AAAAAAAAAAAAAA A AAAAAAA AAA AAAA AAAAAAAAAAAAA AAAAAAAA AAAA AAAAAA AAAAAAAAAAAAAAAAA AAAAAAAAAA AAAAAA A AAAA AAAAAA AA AA AAAA AAAA AAAAA AAAAAA AAAA A AAAA A AAAA AAAA AAAAAAAA A AAAA A AAAA AAAAAA AAAA AAAAAA AAAA AAAA AAAA AAAA AAAA AAAAAAAA AAAAAA AAAAAA A AAAA AAAAAA AA AAAA AAAAA AAAA AAAA AAAAAA A AAAA AAAA AAAAAAAA AAAA AAAAA AAAA AAAA AAAA AAAAAAAA AAAA AAAA AAAA AAAA AAAA AAAAAAAA AAAAAAAAAAAAAAAA AAAAAAAA AAAAAA A AAAA AAAA AAAAAAAAAAAAA AAAA AAAA AAAAAAAA AAAA AAAAAAAA AAAA AAAA AAAAAAAA AAAAAAAA AAAA AAAAAAAAAAAAAAAA AAAA A AAAA AAAAAAAA AAAA AAAA AAAA AAAA AAAAAAAA AAAA AAAAAAAAAAAAAAAA AAAAAAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAAAAAA AAAA AAAAAAAAAAAAAAAAAAAAAAAAA AAAA AAAA AAAA AAAAA AAAA AAAA AAAA AAAA AAAA AAAAAAAAAAAAAAAAA AAAA AAAAAAAAAAAAA AAAAAAAA AAAAAAAAAAAAAAAAA AAAAAAAA AAAA AAAA AAAA AAAA A AAAAAAAAAAAAAAAAA AAAA AAAAAAAAAAAAA AAAAAAAA AAAA AAAAAAAAAAAAA AAAA AAAA AAAA AAAAAAAA AAAA AAAA AAAA AAAA AAAA AAAAAAAA AAAA AAAAAAAA AAAA AAAA A AAAA AAAAAAAA AAAAAAAA AAAA AAAAAAAA AAAA AAAA AAAA AAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAA AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA AAAAAAAA AAAAAAAAAAAAAAAAAAAA AAAA AAAAA AAAA AAAA AAAAAAAA AAAA AAAA AAAA AAAAAAAA AAAA AAAA AAAAAAAAA AAAA AAAAAAAA AAAAAAAA AAAA AAAAAAAA AAAA A AAAA AAAAAAAAAAAAAAAA AAAAAAAA AAAA AAAA AAAAAAAA AAAA AAAAAAAA AAAA AAAAA AAAAAAAAAAAAAAAAAAAAA AAAAAAAA AAAA AAAAAAAA AAAAAAAA AAAA AAAA AAAAAAAA A AAAA AAAA AAAAAAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAAAAAAAAAAAAAAAAAAAAAAA AAAA AAAA AAAAAAAA AAAA AAAA AAAAAAAAAAAAA A AAAAAAAA AAAA AAAA AAAA AAAA AAAAAAAA AAAA AAAA AAAA AAAA AAAA AAAAA AAAA AAAAAAAAAAAA AAAA AAAA AAAAAAAA AAAA AAAA AAAAAAAAA AAAAAAAA AAAA AAAAAAAA AAAA AAAA AAAAAAAA AAAA AAAA AAAAAAAA AAAA AAAA AAAA AAAA

AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAA AAAA

20-25 15-20 10-15 5-10 -5

Angle (degrees)

1 2 3 4 5 6 Range (m)

Figure 31 - Bandwidth (Β/2π) of echoes versus range and angle to transducer. Β π

8. Rejecting Overlapping Echoes and Disturbances with Templates
In cluttered environments there is the possibility that echoes from different reflectors may overlap at a receiver. This can result in errors in arrival time estimation. In Figure 32, the estimated arrival time of an echo pulse is considered when an identical but delayed pulse is added. The error is defined as the difference between the actual arrival time of the first pulse and the estimate of arrival time based on the maximum correlation, defined in equation (29), of the overlapping pulses with the original pulse. A reference pulse at 1 meter range from an aligned plane is employed in Figure 32. Errors of up to 3 ?sec can occur which are sufficient to disturb the bearing estimate significantly. Also plotted in Figure 32 is the correlation between the reference pulse and the overlapping pulses. We reject arrival time estimates when the correlation coeefficient is below a threshold of 0.8. This eliminates almost all overlapping pulses. We do not attempt to separate overlapping pulses in this paper. The correlation drops to below 0.8 when there is detectable error in the arrival time estimate, with the exception of closely spaced overlapping pulses separated by less than 5 ?sec. Noise disturbances that do not match the pulse shape are rejected also based on the correlation coefficient.

0

32

3.0 2.5 2.0 1.5 1.0 0.5 0.0 -0.5 -1.0 -1.5

Correl

Error

0

10

20

30

40

50

60

70

1.0 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.0

Delay between pulse and overlapping pulse (usec)

Figure 32 - Error introduced when two equal pulses overlap.

9. Experimental Results
9.1. Absolute Accuracy Tests
The tests described in this section are designed to test the accuracy of the mean readings of the sensor. This establishes that our sensor estimates are unbiased and that the standard deviation of the readings then can be assumed to represent approximately the true error standard deviations. We test both the range and bearing accuracies, taking care to assess the accuracy of our test procedures. Test 1 - Range using Aligned Plane We positioned an acrylic plane at 200 mm increments from 2 meters up to 4 meters using a tape measure for range and the reflection of a laser off the plane for alignment. At each point 100 readings were taken. The plane was repeatedly positioned at 3 meters to assess the accuracy of the physical positioning. The speed of sound was calibrated by using a straight line fit to the measurements and the errors are shown in Figure 33. The standard deviations of the sets of 100 measurements are plotted with a dashed line. The measurement errors at 3 meters reflect the position accuracy of the plane and indicate that the sensor readings have very little bias in the mean range.

33

0.0008 0.0006 0.0004 0.0002 0 -0.0002 -0.0004 -0.0006 Range (m) 2 2.5 3 3.5 4

Figure 33 - Absolute Errors (points) in Mean Range and Standard Deviation of measurement (dotted line). Test 2 Bearing at 4 meters with a corner. We took measurements in a direction perpendicular to the sensor look direction. At a range of 4 meters we moved a corner in 200 mm increments to 1 meter off axis and then back to 0 and then -1 meter off axis. The results are shown in Figure o o 34 where it can be seen that the errors are less than 0.2 over a 20 range. Moreover, there is no apparent bias in our measurements compared to the standard deviation.
Bearing error and standard deviation (degrees) 0.8

0.6

0.4

0.2

-15

-10

-5

0 -0.2

5 10 Angle (degrees) ->

15

Figure 34 - Measured errors in bearing angle (points) and standard deviation of measurements (line) of a corner at range of 4 meters.

9.2.

Imperfect Reflector Effects

Due to the high precision of the sensor, effects due to undulations and deviations from flatness in planes and corner surfaces may become significant. The statistical hypothesis test in Section 5.4 will reject planes that cause deviations from a perfect image in the order of 0.2o (10 mm at 3 m) which can occur in some indoor surfaces. For this reason the hypothesis test needs to be relaxed when imperfect

34 reflectors are anticipated in the environment. However, if for example environmental features of interest to robot localization are known to be geometrically well formed, such as doors, flat walls, windows and right-angled corners, the statistical test of Section 5.4 should be used since it will reject other imperfect targets not of interest. A glass sheet gave good experimental results within the confidence level of the test. A Lucite cast acrylic sheet deviated from flatness sufficiently to exceed our confidence level threshold.

9.3.

Classification Experiments.

In order to account for imperfections in our test reflectors, such as acrylic planes and "cylindrical" edges, we have relaxed our criterion for classifying geometric targets in this section. For experimental purposes we have employed thresholds on m in equation (16), to allow for the imperfections in our test reflectors. The thresholds employed in the data are 0.8o in bearing and 2.4 mm in DOF. These values still allow discrimination of planes and corners to a range of 8 meters and edges to a range of 2 meters. We define regions of detectability in which the reflector is classified correctly on more than 50% of readings and incorrectly less than 1% - the remainder being "unknown" classifications. Only on the boundaries of the regions does the 50% classification success occur, with nearly 100% successful classifications occurring within the boundary. Figures 35 and 36 show the results of the sensor classification performance. The limitations are primarily due to the signal to noise ratio of the receiver. There are limits to detecting reflectors near the sensor due to the sharp angle to normals of the transducers to the reflector, since all transducer beam widths must overlap to detect and classify a reflector. Another limitation is in the template set used. We have employed pulse templates from 0o to 20o in steps of 1o in bearing, and assumed that the transmitter angle to normal equals the receiver angle. For planes and edges very close to the sensor these angles can be quite different, producing unrecognizable pulse shapes that are below the correlation threshold. The same problem occurs for angles much greater than 20o. Although a larger template set could have expanded the beam width, signal amplitudes at large angles are small and have poor signal-to-noise ratios. The large cylinder was not recognized as a point at close ranges due to the difference o in reflection points from the two transmitters exceeding the 0.8 threshold. The sensor has less range for the cylinders compared to planes and corners due to the smaller reflected energy detected at the receiver.
1.5

Y-axis
1

T2
0.5 0 0 -0.5 1 2 3 4 5 6 7 8
plane

R2 T1/R1 0 X-axis
-1 X (m) ->

Figure 35 - Axis Definition and Measured Region of Detectability for a Plane.

35

1 0.8 0.6 0.4 0.2 0 -0.2 0 -0.4 -0.6 -0.8 -1 X (m) -> 1 2 3 4 5 6 7
Corner

0.4

13 mm 0.3 diameter

165 mm diameter

0.2 0.1 0 -0.1 0 -0.2 -0.3 X (m) -> 0.5 1 1.5 2 2.5 3 3.5

Figure 36 - Measured Regions of Detectability for Corner and Edges.

9.4.

Sensor Discrimination

To demonstrate the best discrimination achieved by the sensor, two 13 mm diameter cylinders 1 meter tall were positioned at a range of 750 mm with centres 30 mm apart and rotated until the sensor could only just discriminate the targets as shown in Figure 37. The difference in range of the cylinders is 10 mm and difference in o bearing is 1.9 . The limiting factors were the correspondence problem of associating the two echoes on each receiver and overlapping of the pulses. We reject arrival times when there is any possibility of ambiguity. This means reflectors must be separated in range by at least 9 mm, as discussed in Section 3. Echo overlap also becomes a limitation at range separations around 10 mm.

0.08

0.07
S ens or reports point reflectors

Cylindrical targets

0.06

0.05

0.04 0.74

0.75

0.76

0.77

X (m) ->

Figure 37 - Resolution demonstration of the sensor with two closely space cylindrical targets, plotted in meters with 10 mm grid.

36

9.5.

Multiple Target Demonstration

To demonstrate simultaneous multiple target identification, a cylindrical table leg is positioned near a corner in the field of view of the sensor as shown in Figure 38. All three target types are correctly classified and localized simultaneously with one measurement cycle of the sensor. Note that the corner orientation is not reported by the sensor since only the position of corners can be determined by the sensor. The orientation and the position of the normal of planes are reported. The echo data from both transmitters and receivers is shown in Figure 39, where the echoes are labeled with their target type.
0.2 0.15 0.1 0.05 0 -0.05 -0.1 -0.15 X (m) -> 1 1.1 1.2 1.3 1.4 1.5
E dge reported Plane reported
AAAAAAA AAAAAAA AAAAAAA AAAAAAA AAAAAAA AAAAAAA AAAAAAA

Corner reported

Figure 38 - Multiple target classification demonstration - a 25 mm diameter table leg is seen as an edge, and a corner and plane are reported (distances in meters).

37

2 1 0 -1 -2
E dge P la ne Co rne r

2 1 0 -1 -2 2 1 0 -1 -2
E dge P la ne Co rne r

2 1 0 -1 -2

0

200

400 T i m e ( u s e c ) ->

600

Figure 39 - Received echo data corresponding to Figure 38.

9.6.

Processing Speed

The software for the sensor was implemented in C on a PC 386 running at 33 MHz. Echo pulses were identified by looking for maxima above the noise floor and above neigbouring peaks within a pulse width. This meant that the correlation processing was performed only on the actual candidates for the echo and not the entire signal. When all 20 templates were correlated with each echo, the processing and sensing time was the order of a 1 second for one reflector. This includes graphic display and communications overhead to the data capture system. A faster approach and almost as accurate is to correlate every second template angle with each echo until a local maximum in template angle occurs. This results in three times the speed for one reflector. The template matching process naturally lends itself to parallel processing arrival times could be extracted on both receivers from both transmitters in parallel. The association of these arrival times is trivial due to the sensor arrangement of closely spaced receivers. Parallel processing would conceivably allow data processing to be performed at the maximum measurement rate determined by the speed of sound. Measurement rates of the order of 10 Hz could be achieved with the sensor range of 7 meters.

38

10. Conclusions and Future Work
A novel sonar sensor configuration and processing approach has been presented that can accurately classify and localize planes, corners and edges without sensor movement. This has been achieved by adopting physical models for transmission, propagation, reflectance and reception of ultrasonic pulses combined with optimal arrival time processing, all with a reasonable computational burden. The sensor range and bearing accuracy and target discrimination are often limited only by the fundamental properties of the transducer, air and reflectors, rather than the sensor data processing. This paper has shown theoretically that two transmitters and two receivers are necessary and sufficient for classifying the useful indoor geometric targets of planes, corners and edges. This minimal configuration has been implemented as an experimental prototype. Range and bearing measurements with errors less than a millimeter and 0.1 degrees have been verified out to 8 meters range. Discrimination of targets separated by as little as 10 mm has been achieved due the narrow pulse shape emitted from the transmitter. Thus the sensor has the capability to work effectively in cluttered environments. A template matching approach has been effective in optimally estimating the echo arrival times. Echo shapes for different transmitting and receiving angles and ranges are generated and stored. By choosing the best correlation match between the incoming echo and the template set, the optimal arrival time can be estimated. Two arrival times from the stereo receivers generate a bearing estimate. By transmitting two pulses from different transmitters, targets can be classified as planes, corners, edges or unknown. Maximum likelihood estimators for classifying echoes into these target types have been presented in this paper. A novel feature of the sensor design is the close spacing of the receivers. This significantly reduces the possibility of ambiguity in associating arrival times from the two receivers to physical targets. Bearing accuracy is still maintained in practice due to the optimal arrival time estimation. The complete received signals are processed by the sensor, as compared to first echo systems such as the Polaroid ranging module. This means that distant targets are not masked by close targets as occurs with the Polaroid ranging module. All targets that return recognizable echoes are reported in our sensor. Improvements to the sensor are now discussed. The template set can be extended beyond the 20o maximum applied in this paper, for better results at close ranges. The approximation of equal transmitter and receiver angles in the template set could also be improved by calculating the transmitter angle for each receiver angle in the template set at close ranges. Extensions have been presented to allow future three dimensional target classification. A useful modification to the sensor is to employ a three dimensional vector receiver in place of the two dimensional vector receiver presented in the paper. This will allow the rejection of phantom targets due to the pulse propagation not in the horizontal plane. For example, reflections from the intersection of a floor and wall could be recognized as not in the horizontal plane of the sensor. The two dimensional sensor presented here falsely recognizes this reflector as a second plane beyond the wall. The problem of multiple reflections (apart from single corners) has not been addressed in this paper and is a fundamental limitation of all sonar systems. For

39 example, for an edge to be classified and localized incorrectly by the sensor both transmitters need to produce the same multiple reflection effect which is unlikely in practice. Reflectors illuminated by the pulse first bouncing off a plane and back via the same plane are more easily incorrectly localized. These errors appear indistinguishable to the sensor from real targets at the virtual image location. The errors must be rejected by higher level reasoning and different sensor viewpoints that avoid the intervening plane. The next stage of research is the incorporation of these sensors into a working mobile robot for experiments in localization and map building. With the high accuracy and reliable target classification of the sensors we hope to achieve autonomous robot localization with sonar in unknown indoor environments. By classifying targets when sensed, rather than by merging multiple views as with single transducer systems, the sensor provides significant advantages in associating targets for map merging and localization tasks. The high bearing and range accuracy also reduces the possibility of incorrect measurement association and of course improves map and localization accuracy. More complex object recognition and docking tasks can be attempted, such as finding doorways and battery recharging ports. Adaptations of the sensor are also envisaged for obstacle avoidance tasks. For example, a single transmitter and three receivers could produce range, azimuth and elevation of target without geometric classification. Due to our ability to predict accurately the pulse shape as it propagates, it is conceivable that a high repetition pulse rate sonar system could be developed where incoming pulses can be associated with the firing cycle from their shape and amplitude. Thus pulse rates higher than that dictated by the transmit receive delay may be then possible.

References
Barshan, B. and Kuc, R. 1990. "Differentiating sonar reflections from corners and planes by employing an intelligent sensor", IEEE PAMI, Vol 12, No 6, pp 560569. Borenstein, J. and Koren, Y. 1988 (April). "Obstacle avoidance with ultrasonic sensors", IEEE Journal Robotics and Automation, , pp 213-218. Bozma, O. and Kuc, R. 1991. "Characterizing pulses reflected from rough surfaces using ultrasound", The Journal of the Acoustical Society of America, Vol 89, No 6, pp 2519-2531. Bozma, O. and Kuc, R. 1991a. "Building a sonar map in a specular environment using a single mobile sensor" IEEE PAMI Vol 13 No. 12, pp. 1260-1269. Brown, M. K. 1985 (Dec.). "Feature extraction techniques for recognizing solid objects with an ultrasonic sensor", IEEE Journal Robotics and Automation, pp. 191-205. Crowley, J. L. 1985 (March). "Navigation for an intelligent mobile robot", IEEE Journal Robotics and Automation, , pp. 31-41. Elfes, A. 1987. "Sonar-based real world mapping and navigation", IEEE Trans Robotics and Automation, pp. 249-265. Hong, M. L. and Kleeman, L. 1992 (May). "Analysis of ultrasonic differentiation of three dimensional corners, edges and planes", IEEE International Conference on Robotics and Automation, Nice, France pp 580-584.

40 Iijima, J. and Yuta, S. 1992. "Searching unknown 2-D environment by a mobile robot with a range sensor", Computers Elect. Engineering Vol 18 No 1 pp 83-98. Kuc, R. 1988. Introduction to Digital Signal Processing, New York: McGraw-Hill. Kuc, R. 1990 (July). "A spatial sampling criterion for sonar obstacle detection", IEEE Trans Pattern Analysis and Machine Intelligence, Vol 12, pp. 686-690. Kuc, R. and Siegel, M. W. 1987 (Nov.). "Physically based simulation model for acoustic sensor robot navigation", IEEE PAMI, Vol 9, No 6, pp 766-778. Larsen, R. J. and Marx, M. L. 1985. An Introduction to Probability and its Applications, Englewood Cliffs: Prentice-Hall. Leonard, J. F. and Durrant-Whyte, H. F. 1991. "Mobile robot localization by tracking geometric beacons", IEEE Transactions Robotics and Automation Vol. 7 No 3, pp 376-382. Manyika, J. M. and Durrant-Whyte, H. F. 1993 (May). "A tracking sonar sensor for vehicle guidance", Proceedings IEEE Robotics and Automation Conference, Atlanta Georgia, pp. 424-429. McKerrow, P. J. 1993 (Feb.). "Echolocation - from range to outline segments", Proceedings Intelligent Autonomous Systems-3, Pittsburgh, pp. 238-247. Moravec, H. P. and Elfes, A. 1985. "High resolution maps from wide angle sonar", Proceedings IEEE Robotics and Automation Conference, pp. 116-121. Munro, W. S. H. et al 1989. "An ultrasonic vehicle guidance system", Proceedings of IROS 89, Tsukuba Japan, pp.224-227. Nagashima, Y. and Yuta, S. 1992 (July). "Ultrasonic sensing for a mobile robot to recognize an environment - measuring the normal direction of walls", Proceedings of IROS 92, Raleigh NC, pp. 805-812. Papoulis, A. 1984. Probability, Random Variables, and Stochastic Processes, 2nd edition New York: McGraw-Hill Book Company. Peremans, H., Audenaert, K. and Van Campenhout, J. M. 1993. "A high-resolution sensor based on tri-aural perception", IEEE Trans on Robotics and Automation, Vol 9, No 1, pp. 36-48. Polaroid Corporation 1982. Ultrasonic Range Finders. Polaroid Corporation 1987. Data sheet for Series 7000 transducer, Ultrasonic components group, 119 Windsor St, Cambridge MA 02139 USA.. Press, W. H. et al 1990. Numerical Recipes in C, the Art of Scientific Computing, Cambridge NY: Cambridge Uni Press. Sabatini, A. 1992. "Active hearing for external imaging based on an ultrasonic transducer array", Proceedings of IROS 92, Raleigh, pp. 829-836. Sasaki, K. and Takano, M. 1992. "Classification of object's surface by acoustic transfer function", Proceedings of IROS 92, Raleigh, pp 821-828. Suoranta, R. 1992 (Oct.). "Novel ultrasonic beamforming method based on nonlinear filtering", 1992 IEEE Ultrasonic Symposium, Tucson, Arizona. Weast, R. C. and Astle, M. J. (Editors) 1978. CRC Handbook of Chemistry and Physics, 59th edition, Boca Raton, Florida: CRC Press. Whalen, A. D. 1971. Detection of Signals in Noise, Orlando: Academic Press Inc. Woodward, P. M. 1964. Probability and Information Theory with Applications to Radar, 2nd edition, Oxford: Pergamon Press. Yang, M., Hill, S. L. and Gray, J. O. 1992. "Design of ultrasonic linear array system for multi-object identification", Proceedings of IROS 92, Raleigh, pp. 16251632.


赞助商链接

更多相关文章:
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图