Confidence Scoring of Time Delay Based Direction of Arrival Estimates and a Generalization to Difference Quantities

(1)

(2)

Tampereen teknillinen yliopisto. Julkaisu 854 Tampere University of Technology. Publication 854

Tuomo Pirinen

Confidence Scoring of Time Delay Based Direction of Arrival Estimates and a Generalization to Difference Quantities

Thesis for the degree of Doctor of Technology to be presented with due permission for public examination and criticism in Sähkötalo Building, Auditorium S3, at Tampere University of Technology, on the 4^th of December 2009, at 12 noon.

Tampereen teknillinen yliopisto - Tampere University of Technology Tampere 2009

(3)

Thesis advisor

Professor Ari Visa

Department of Signal Processing Tampere University of Technology Finland

Pre-examiners

Docent Mats Bengtsson Signal Processing Laboratory Royal Institute of Technology Sweden

Docent Ville Pulkki

Department of Signal Processing and Acoustics Helsinki University of Technology

Finland

Opponent

Professor Martin Vermeer

Institute of Geoinformation and Positioning Technology Helsinki University of Technology

Finland

ISBN 978-952-15-2271-0 (printed) ISBN 978-952-15-2308-3 (PDF) ISSN 1459-2045

(4)

Abstract

Sensors are used for obtaining information from their operating environment. Recently, the use of multiple sensory units as arrays or networks has become popular. This has been caused by developments in sensor technology and the inherent application potential. Costs of sensory units and systems have decreased with developments in electronics. In addition, advances in communication technologies, such as wireless operation, make it easier to deploy systems with a large number of sensory units. Several applications exist for these systems in the areas of monitoring, control, surveillance, communications and multimedia devices.

With developments, come additional requirements. Sensor systems are expected to operate for long periods of time, possibly unattended. Furthermore, environmental and signal conditions may be adverse. As a result, errors caused by disturbances occur in system output and hardware malfunctions may develop between scheduled maintenance. Automatic operation is still expected and even if human operators are available, manual inspection of the data from individual units is not feasible in large systems. This raises the need for error-tolerant processing, that is able to assess the quality of produced data and detect potential malfunctions.

This thesis addresses these issues within acoustic direction of arrival (DOA) estimation. An array of microphones is utilized to acquire acoustic pressure signals from a far-field source.

Time differences of arrival (TDOAs) between the sensors are estimated and used to compute the direction estimate. Specifically, the plane wave slowness vector (SV) formulation of the problem is examined, allowing a linear model to be used for estimation.

In practice, signals are noisy and time delay estimates contain large errors making the direc- tional estimates inaccurate. This work examines confidence scores that can be used to evaluate the instantaneous estimation error and to remove highly erroneous delay estimates from the processing. A robust and scalableDOAestimator is introduced. It is further demonstrated with experiments that confidence scores can be used for signal activity detection, outlier removal and sensor failure compensation.

One of the examined confidence scores is based on closed-path properties ofTDOAs. This score is generalized beyond the plane waveDOAdomain to a difference quantity model. Ex- amples of difference quantities include voltages and spherical-waveTDOAs used in source lo- calization. The scoring principle is brought into a statistical framework and outlier detection is formulated as a hypothesis testing problem. An optimum detector is derived and its properties are analyzed. The results of this work provide simple and computationally light means for sensor arrays to diagnose their operation instantaneously in dynamic conditions.

(5)

Acknowledgments

This thesis is the result of research works carried out during 2002–2009 as a graduate student at the Department of Signal Processing, Tampere University of Technology (^TUT), and as a research visitor in the Speech Group of the International Computer Science Institute (^ICSI) during 2003–2004. The research was funded by theTUT Graduate School, the Finnish Air Force and the Academy of Finland grant 130483. Additional financial support from the Finnish Funding Agency for Technology and Innovation (TEKES), the Nokia Foundation, the Finnish Founda- tion for Technology Promotion, and the Emil Aaltonen Foundation is gratefully acknowledged.

I wish to express my deepest gratitude to my thesis adviser Prof. Ari Visa for his support and encouragement throughout the work. I would also like to thank Jari Yli-Hietanen for in- troducing an interesting research topic, collaborating on the research, and initially hiring me to work as a research assistant for the Audio Research Group at^TUT. The thesis was carefully pre-examined by Docent Mats Bengtsson and Docent Ville Pulkki whom I thank for their in- sightful and critical comments, which addressed many important points on the dissertation and stimulated several new thoughts on the research topic. In addition, I offer my gratitude to Prof. Martin Vermeer for agreeing to be the opponent for the public examination of the thesis.

Throughout the endeavor I have been blessed to work and become friends with superior colleagues. A very special thanks goes to Konsta Koppinen for all of his efforts, assistance and companionship. I wish to thank the spatial “dudes” Pasi Pertilä, Teemu Korhonen, Mikko Parviainen and Sakari Tervo for all of their contributions, which are far too numerous to be listed here. Working with them has been an absolute pleasure. I would also like to thank Anssi Klapuri, Tuomas Virtanen, Jouni Paulus, Heikki Huttunen, Matti Ryynänen, Juha Tuomi, Antti Eronen, Antti Pasanen, Matti Vihola, Teemu Saarelainen, Vesa Peltonen, Atte Virtanen and all other colleagues in the Audio Research Group and the Department of Signal Processing for their collaboration.

During the research I had the privilege to visit ^ICSI and the University of California at Berkeley (UCB) for one year. I thank ICSI and its director Prof. Nelson Morgan as well as TEKES and Riku Mäkelä for the visiting opportunity and the support during my stay. I wish to especially thank Adam Janin and Chuck Wooters for their friendship, ad- vice and proofreading of publication manuscripts. A heartfelt thanks to Andy Hatch, Patrick Chew, Jaci Considine, Juuso Rantala, Michael Ellsworth, Scott Otterson, Dave Gelbart, Barbara Peskin, Nikki Mirghafori, Andreas Stolcke, Scott McComas, Michael Ellis, David Johnson, Javier Macias, the late Jane Edwards and all of the friends, colleagues and co-authors atICSI

and elsewhere for a world-class research environment, company and good times.

(6)

Acknowledgments v

A data set for the experiments included in the thesis was recorded in August 2004 at the Center for New Music and Audio Technologies (CNMAT) at UCB. I am most grateful to Prof.

David Wessel for providing the ^CNMAT facilities for use and to Michael Zbyszy ´nski for his assistance during the recordings. Some of the experiments utilize data from the^IDIAPresearch institute, this was possible with the help of Iain McCowan and Guillaume Lathoud.

The thesis research could not have been initiated without the support of individuals in the Finnish Air Force, VTT Technical Research Centre, the Finnish Defence Forces Technical Research Centre and other collaborators. I extend my gratitude to all of them. I thank Kari Tanninen for many interesting questions, which I did not understand at the time he presented them — I now see the answers in this thesis. Panu Maijala arranged many of the initial mea- surements and his efforts and guidance are duly acknowledged.

I wish to acknowledge the help from Miika Huikkola with some mathematical details related to the research. I am also grateful to my present employer Sandvik Mining and Con- struction, my co-workers and particularly Research Manager Pauli Lemmetty for their support during the final stages of the work. The language of the dissertation was reviewed by Jaakko Ollila, whose services are greatly appreciated.

To a great extent, this thesis and the adventures leading to its completion were made possible by my mother Hilkka and my father Kari. Their continuous and unconditional encouragement have carried me forward. I thank them, and my sister Eriikka for their love and support.

I also wish to thank my grandmother Saimi for everything she has done and my grandfather Väinö, whose common sense and reason is beyond any comparison, for setting a supreme example.

Finally, and most importantly, I am eternally grateful for my family who has had to share this work, its burden and the time required to its completion. I thank my beloved, wonderful wife Elina for her love and support, and my sons Onni-Veikko and Oula for being there¹. You are the light of my life and I will always love you.

“And further, by these, my son, be admonished: of making many books there is no end;

and much study is a weariness of the flesh. Let us hear the conclusion of the whole matter:

Fear God, and keep his commandments: for this is the whole duty of man. For God shall bring every work into judgment, with every secret thing, whether it be good, or whether it be evil.”

Ecclesiastes 12:12–14

Tuomo Pirinen

Nokia, November 2009

1And if you don’t go to bed immediately, I will read the thesis to you one more time!

(7)

A Statistics of plane wave time differences of arrival 166 A.1 Two-dimensional case . . . 166 A.2 Three-dimensional case . . . 168 A.3 Covariance matrices . . . 168 B Examples of confidence scores in activity detection 169 B.1 MLSsource, 0 dBSNR . . . 169 B.2 MLSsource, -5 dbSNR . . . 175 B.3 MLSsource, -10 dbSNR . . . 181

(11)

Abbreviations

AD Analog-to-Digital

AMDF Average Magnitude Difference Function

AOA Angle Of Arrival

AVG AVeraGing within subarrays

BLUE Best Linear Unbiased Estimator

CNMAT Center for New Music and Audio Technologies (University of California at Berkeley)

CNT Count-Distance

CRLB Cramér-Rao Lower Bound

CSD Cross Spectral Density

DOA Direction Of Arrival

DQ Difference Quantity

EER Equal Error Rate

ESI Excitation Source Information

EWMA Exponentially Weighted Moving Average

FIM Fisher Information Matrix

GCC Generalized Cross Correlation

IRLS Iterated Reweighted Least Squares

LS Least Squares

LTS Least Trimmed Squares

MAD Median of Absolute Differences

MAE Mean Absolute Error

MEMS Micro-Electro-Mechanical Systems

(12)

Abbreviations xi

ML Maximum Likelihood

MLS Maximum Length Sequence

MMSE Minimum Mean-Squared Error

MSE Mean-Squared Error

MUSIC MUltiple SIgnal Classification

MVU Minimum Variance Unbiased (estimator)

MVDR Minimum Variance Distortionless Response

NCF Normalized Confidence Factor

PD Probability of Detection

PDF Probability Density Function

PFA Probability of False Alarm

PHAT Phase Transform

RFID Radio-Frequency Identification Device

RMSE Root Mean-Squared Error

ROC Receiver Operating Characteristic

SAD Sum of Absolute Difference

SLF Spatial Likelihood Function

SNR Signal-to-Noise Ratio

SRP Steered Response Power

SSD Sum of Squared Difference

SV Slowness Vector

TDE Time Delay Estimation

TDOA Time Difference Of Arrival

TDS Time Delay Selection

UMP Uniformly Most Powerful

WCC Weighted Cross Correlation

WLS Weighted Least Squares

(13)

Nomenclature

x Scalar.

|x| Absolute value ofx.

√x (Positive) square root ofx. x^∗ Complex conjugate ofx.

⌊x⌋,⌈x⌉ Nearest smaller integer ofx, nearest greater.

[x, y],(x, y) Closed interval fromxtoy, open interval.

i Imaginary unit.

A{·} Operator.

x Vector.

hx,yi Inner product ofxandy.

kxk_IND Norm induced by an inner product.

kxk2 Euclidean (l₂-) norm ofx.

|x| l₁-norm ofx.

A Matrix.

A^T,A^H Transpose ofA, Hermitian transpose.

|A| Determinant ofA.

tr{A} Trace ofA.

A⁻¹ Inverse ofA.

A⁺ Moore-Penrose pseudoinverse ofA.

f_x(x),f_x|y(x|y) Probability Density Function of random variablex, conditioned ony.

F_x(x) Cumulative distribution function of random variablex.

p(X),p(X|Y) Probability of eventX, conditional toY. x,xK Sample mean ofx, fromKsamples.

E{·} Expectation.

var{·} Variance.

l(y), l(y,x) Likelihood of parametery, given observationsx.

Λ(y), Λ(y,x) Log-likelihood ofy, givenx.

ℓ(x), L(x) Likelihood ratio ofx, logarithmic.

Q(·), Q⁻¹(·) Q-function, inverse.

med{·} Median.

(14)

Nomenclature xiii

y^ Estimate or measurement ofy.

xLS Least Squares (LS) approximation ofx.

bias{^y} Bias, the expectation of error, of estimatey.^

MSE{^y}, MSE{^y} Mean-Squared Error (MSE) of estimatey, sampled.^ RMSE{^y} Root Mean-Squared Error (RMSE) of estimatey.^ MAE{^y} Mean Absolute Error (MAE) of estimate^y.

J(y) Fisher Information Matrix (FIM) of parametery.

J⁻¹(y) Cramér-Rao Lower Bound (CRLB) ofy.

∡{x,y} Angle between vectorsxandy.

e∡ Angular error.

e_⊥ Euclidean error.

π Ratio between the circumference and diameter of a circle.

exp{·} Exponential function, exp{x}=e^x.

x→y xapproachesy.

xlim→yf(x) Limit off(x)whenxapproachesy. Z

f(x)dx Integral off(x).

∂

∂y, ∂ⁿ

∂yⁿ Partial derivative with respect toy,n-fold.

∇,∇y Gradient, with respect toy.

∇² Laplacian.

x(t)∗y(t) Convolution ofx(t)andy(t). X⇔Y Xif and only ifY.

F⁻¹{·} Inverse Fourier transform.

∀n For alln.

X Set.

x∈ X xis a member of setX.

#{·} Cardinality, number of elements in a set.

n! Factorial ofn.

n k

Choose function n

k

= n!

k!(n−k)!. {x}, {x|Y} Set with elementsx, such thatYholds.

T →Θ, T ↔Θ Mapping from setT to setΘ, bijective.

sup{·} Supremum, the least upper bound of a set.

max, max

y Maximum value of a set or a function, over the values ofy.

min, min

y Minimum value of a set or a function, over the values ofy.

argmax, argmax

y

Argument of the maximum value, over the values ofy.

argmin, argmin

y

Argument of the minimum value, over the values ofy.

(15)

List of Figures

2.1 Example receiver operating characteristic. . . 14

4.1 Difference between the spherical and plane wave models. . . 40

4.2 Relative error of the plane wave approximation. . . 41

4.3 Geometry of a plane waveTDOA. . . 43

5.1 The spherical coordinate system. . . 47

6.1 Examples ofTDOAambiguities. . . 60

6.2 Example ofTDOAquantization. . . 69

7.1 Sensor pair index as a function of the sensor indices. . . 72

7.2 Sensor indices as a function of the sensor pair index. . . 73

7.3 Possible values of a quantized 2-D slowness vector estimate. . . 84

7.4 Voronoi diagram for the lattice of Figure 7.3. . . 85

7.5 Angular quantization error as a function ofDOA. . . 85

7.6 Voronoi diagram in azimuth-elevation space for a 3-D array. . . 86

7.7 3-D illustration of the Voronoi diagram in Figure 7.6. . . 87

7.8 Array geometries used in propagation speed examples. . . 90

7.9 Cumulative distribution ofDOAestimation error in varying propagation speed. . 92

7.10 AngularRMSEofDOAestimation for biased speed of sound. . . 93

8.1 Maximum angular error as a function of parameterized norm of error. . . 96

8.2 Comparison of the norm of error and its lower bound as a function ofSNR. . . 97

8.3 Example ofDOAestimates at−10.5dBSNR. . . 98

8.4 Norm-based confidence scores for the estimates in Figure 8.3. . . 98

8.5 DOAestimates from a real data experiment. . . 99

8.6 Norm-based confidence scores for the estimates in Figure 8.5. . . 99

8.7 Illustration of the closed-path confidence factor principle. . . 101

8.8 Example ofTDOAselection usingNCFs. . . 104

8.9 Slowness vector estimation accuracy in additive Gaussian noise. . . 105

8.10 Slowness vector estimation accuracy in quantization. . . 106

8.11 Slowness vector estimation accuracy in uniform additive noise. . . 107

8.12 Slowness vector estimation accuracy in impulsive noise. . . 107

(16)

List of Figures xv

8.13 Video screenshots from the speech data experiment. . . 108

8.14 Configuration of the speech data experiment. . . 108

8.15 Example ofDOAestimates in the speech data experiment. . . 109

8.16 Slowness vector estimation accuracy in the speech data experiment. . . 110

9.1 Block diagram for activity feature computation. . . 114

9.2 Block diagram for activity threshold computation. . . 115

9.3 Recording set-up for the activity detection data. . . 117

9.4 Example of detection using feature F1. . . 118

9.7 Activity detection error rates as a function ofSNR. . . 121

9.8 AngularRMSEofDOAestimation with activity detection. . . 122

10.1 Examples of confidence factor grouping for sensor failure detection. . . 125

10.2 Example of simulated source movement. . . 127

10.3 State model of failure simulation. . . 127

10.4 Confusion matrix for detecting the number of failed sensors. . . 128

10.5 Average error ofDOAestimation methods in a multiple-failure scenario. . . 130

10.6 Cumulative distributions ofDOAestimation error from zero to five failures. . . . 131

10.7 Speech scenario used in the failure example. . . 132

10.8 Failure indicators in the speech data example. . . 133

10.9 DOAestimation errors and failure detection for the speech example. . . 133

11.1 Two examples of the difference quantity model. . . 135

11.2 Error bounds for a difference quantity estimate. . . 138

11.3 Ranges of a difference quantity and the closed path test statistic. . . 139

11.4 Probabilities of false alarm and detection as a function of error. . . 145

11.5 Average probability of false alarm as a function of size and acceptable error. . . . 146

11.6 Average probability of detection as a function of size and acceptable error. . . 146

11.7 Comparison of average probabilities of false alarm and detection. . . 147

11.8 Receiver operating characteristic of the outlier detector. . . 147

11.9 Equal error rates of the outlier detector. . . 148

B.1 Activity detection results forMLSsource, 0 dBSNR, feature F1. . . 169

B.4 Activity detection results forMLSsource, 0 dBSNR, feature V1. . . 172

B.7 Activity detection results forMLSsource, -5 dBSNR, feature F1. . . 175

(17)

xvi List of Figures

B.10 Activity detection results forMLSsource, -5 dBSNR, feature V1. . . 178

(18)

List of Tables

2.1 Outcomes of a binary hypothesis test. . . 11

3.1 Properties of selected wireless communication technologies. . . 32

5.1 Example of the behavior of the Euclidean distance in angular coordinates. . . 57

6.1 Weight functions of generalized cross correlation. . . 63

9.1 Potential conflicts in using conventional activity detection for spatial purposes. . 112

9.2 Parameters of the spatial activity detector. . . 116

9.3 Performance of spatial features in activity detection by signal type. . . 123

9.4 Accuracy ofDOAestimation with spatial activity detection. . . 123

10.1 An algorithm for detecting sensor failures. . . 126

10.2 Failure detection accuracies. . . 129

10.3 Average failure detection delays. . . 129

11.1 Examples of model variables for difference quantities. . . 136

(19)

xviii

(20)

1 Introduction

This chapter is an introduction to the thesis, describing briefly the scope of the work, the research problem, some applications for the results and giving a summary of the main contributions. An outline for the thesis along with a list of publications are given at the end of the chapter.

1.1 Signal processing

Asignalis a physical quantity capable of carrying information that is represented by the vari- ations of the value of the quantity. Digital signalsare discrete in amplitude or time, or in both.

Digital signals can be represented and are usually taken as the equivalent of sequences of numbers. Signal processingrefers to the act of converting a signal into another signal as well as to the fields of science, technology, and engineering devoted to the exploration of this act. These fields include the study of theory, methods, algorithms, systems, hardware, and applications for signal processing.

Afilteris any arrangement used to convert a signal into another. Adigital filterconverts a sequence of numbers into another sequence. For example, theFibonacci sequenceof numbers

h(n) = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,· · ·] (1-1) is the response of thelinear time-invariantdigital filter

y(n) =x(n) +y(n−1) +y(n−2) (1-2) to a unit impulse. The construction and operation of a filter is limited only by the potency of mathematics and the designer’s imagination. Therefore, many powerful mathematical tools, including linear algebra and statistics, are employable. The resulting filters can be utilized within any physical phenomenon that can be represented as a digital signal.

Estimation theoryis a branch of signal processing that considers the process of approximat- ing the value of a quantity by means of calculation. The calculations should be such that the approximation result, estimate, is as close as possible to the true value. The algorithm that produces the approximation is an estimation filter, called anestimator.

(21)

2 Introduction

1.2 Direction of arrival estimation

Sampling of signals can be conducted in time and in space. A signal sampled at multiple locations using asensor arrayis a spatial signal, and its value depends on the sensor location in addition to time. Utilization or manipulation of the space-time signal properties is called spatial processing. An important property of spatial signals is their mutual similarity — suitably sampled signals at disjoint locations correlate with each other. This correlation can be exploited in processing to amplify, enhance, separate, localize, suppress, detect or identify signals.

A spatial signal propagating as a wave arrives at sensors in an array at different time instances. The resulting Time Differences Of Arrival (TDOAs) depend on the relative locations of sensors and sources. These time differences are a fundamental spatial property, and a majority of spatial algorithms assume and utilize their existence.

Direction Of Arrival (DOA) estimation refers to estimating the direction of a signal source relative to an observer. This approach is typically employed when the distance of a signal source is large compared to the size of the receiving sensor array and wavefronts are approxi- mately planar.TDOA-basedDOAestimation techniques accomplish the task by first estimating theTDOAs between sensors in an array using Time Delay Estimation (TDE) methods, and then estimating the source direction using the time delay estimates. The task is challenging because

TDE algorithms are prone to large errors, outliers, in noisy conditions. Errors in TDOAs are difficult to detect and propagate to theDOAestimate.

A Slowness Vector (SV) describes the direction and speed of a propagating plane wave [1].

The relation betweenTDOAs and the slowness vector is linear and consequently theDOAesti- mation task is a linear problem within theSVmodel [2].

The two-step approach of estimatingDOA from TDOAs has a suboptimal performance in comparison to methods which operate directly on the received signals. Also, the above men- tioned outlier issues can be avoided to a great extent with other methods. However,TDOA- based methods are conceptually simple, well suited for arrays with a small number of sensors and provide an intermediate reduction of data which reduces the computational requirements.

1.3 Confidence and reliability

In common language,confidencerefers to the trust or faith placed in a person or a thing. Con- fidence results from the subjective perception of something or someone beingreliable. Confi- dence plays an important role in everyday life. As humans, we want to be able to trust the information we receive, such as news, weather forecasts and medical diagnoses. For instance, imagine an online banking system providing uncertain information of a person’s accounts. It is also important that we can rely on the people with whom we interact, such as family mem- bers and colleagues; or the machines and tools we operate, for instance, the vehicles we use for commuting and travelling.

The need for trust comprises of two conditions:

1. The objects of our operations or interactions must be truly reliable.

(22)

1.4 Objectives 3

2. We mustknow— have confidence — that they are reliable.

If only the first condition is met, no harm occurs but the situation may be awkward. For example, we may operate a reliable system but we have little or no confidence in it. Such a situation would be very uncomfortable, as one would constantly have to wonder about something being wrong, although there actually were no problems at all. In an extreme case, a perfectly reliable system, device, or piece of information might be ignored completely because the lack of confidence. For example, the launch of the space shuttle Discovery was delayed in March 2006 because of abnormal readings from a sensor in the hydrogen fuel tank, although there were no problems with the fuel or the tank itself.

In contrast, if only the latter condition is met, catastrophic events may result as a conse- quence of falsely relying on something that is in reality unreliable. For example, it has been proposed that one factor contributing to the Chernobyl power plant disaster in 1986 was false confidence on the equipment as there was no indication of danger in the control panels.

In engineering problems, the assessment of reliability is typically based on historical records or statistical models. The reliability of a component or a device can be determined using statistical analysis on the failure reports. A typical measure for device or component reliability is the failure rate, the number of failures per time unit.

Reliability and error assessment issues arise in signal processing when practical measured sensor signals and estimation is involved. Estimation theory is a scientific and engineering approach to meeting condition 1 in situations where the value of a quantity or a parameter must be determined from uncertain numerical data. In such scenarios, the second condition translates to finding means to evaluate the quality of produced data. Methods need to be objective and based on some absolute measure of the quality of the data. In this thesis, the output of such a method is called aconfidence score.

1.4 Objectives

This thesis examines confidence scores forTDOA-based DOAestimation within theSVmodel, especially for acoustic signals related to speech, music and surveillance applications. The work is motivated by the growing use of sensor systems and the increasing number of sensors in a system. These changes are a result of recent developments in electronics and communications that have reduced the cost of sensory units and systems [3] and increased computational capabilities. Sensor systems are expected to operate for long periods of time. In many applications the systems are unattended and must operate autonomously without operator control or other external support.

The costs for any system should be as low as possible, enabling the use of these systems in a greater number of applications and in larger quantities. Low-cost hardware, however, often has a lower quality and a larger probability of failures. This gives robustness a high emphasis, because prolonged operation increases the probability of failures between scheduled maintenance. In some cases maintenance may not be possible at all. Hardware failures may also occur if the sensor system deployment is automated or done remotely.

(23)

4 Introduction

Within the developments, it is important to consider methods for evaluating the quality of produced data and proper operation of the sensory units. Self-diagnosis capabilities are required for outlier identification and fault indication. This is an essential capability of advanced sensors [4]. The research work presented in this thesis was aimed to address the issues arising inTDOA-based single-sourceDOAestimation.

The objective of the research has been the development of signal processing methods for:

• Assessing the reliability of and errors inDOAestimates using confidence scores.

• Utilizing the confidence information to produce more accurate estimates.

• Relating theSVapproach to sensor array design issues.

• Using the confidence information to detect source activity without a prior signal model.

• Assessing sensor and system functionality based on the confidence information.

The work was conducted by investigating the following four research hypotheses:

H1 Prior knowledge on the propagation speed of a sound wave can be utilized in confidence scoring becauseDOAestimation via theSVmodel does not require information on speed.

H2 Source activity and sensor failure information are visible and detectable in temporal sequences of the confidence scores.

H3 An existing confidence scoring method [5] can be improved in terms of usability and performance.

H4 Confidence scoring principle [5] is generalizable beyond the plane waveDOAdomain.

1.5 Contributions

The research work on hypothesis H1 was an effort to detect and remove erroneous estimates from acousticDOAdata. It was desired to find methods for confidence scoring that can distinguish between “good” and “bad” data. A minimum error criterion based on the propagation speed was found [P1]. The criterion can be computed directly from measured data and used for reliability evaluation and outlier discarding [6]. This method makes it possible to detect erroneous estimates without complicated additional processing.

The failure part of hypothesis H2 was approached using confidence scores originally proposed in [5]. An algorithm was developed for detecting the failure of a single sensor in an array [P2] and further extended to multiple failure scenarios [P3]. With these methods,DOAestima- tion algorithms can overcome temporary or permanent malfunctions in the sensory units. The activity part of hypothesis H2 was addressed by purely experimental means [P5]. It was found that the methods introduced in [P4] are effective in activity detection. Reliable detection can be achieved without knowledge on prior source models, also for wideband signals.

From the observations made in the failure research, it became obvious that the confidence scores of [5] can be improved by normalization [P4]. This served to verify hypothesis H3.

The normalization simplifies parameter setting in the method and, most importantly, provides

(24)

1.6 Outline 5

means to scale theDOAestimator. The scaling can be done continuously between an accurate but sensitive least squares solution and a robust selection-based estimator, without changing the internal structure of the estimator.

Finally, the accumulated experience gave intuition on how to extend the confidence scoring principle. A generalized framework for exploiting redundancy of difference estimates in a sensor array was described in [P7]. A closed-path test statistic and its use for outlier detection in a sensor array were examined. The statistic was derived from a generalized difference quantity model. An optimum detector was formulated and threshold setting methods along with a description of detection performance were provided. A case study verified that the derived analytical results can be used as approximations when the statistical assumptions are not met.

The presented results, in combination with earlier works, verify that the method is effective and can be used for outlier detection and confidence scoring in estimation.

In addition to the hypotheses H1–H4, derivative results from the work include the use of lattices in characterizing the array performance [P6], combined weights for least squares to im- prove estimation accuracy [7] and performance increases for modern speech recognition systems when array processing is utilized for signal enhancement [8]. In summary, the achieved research results enable the sensor arrays to evaluate and diagnose their own operation without complicated additional processing.

1.6 Outline

This thesis consists of 12 chapters and two appendices. Contents following this introductory chapter are divided into two parts. Chapters 2–6 serve as introductory material and provide the necessary background for understanding the theory and research results that are presented in Chapters 7–12.

Chapter 2 is a preliminary chapter providing the mathematical concepts necessary for the later developments. The discussion involves random variables and the normal distribution, hypothesis testing, estimation theory and linear models. A brief treatise on sensor systems is given in Chapter 3 to provide a broader context for the research. Sensors, sensor arrays and sensor networks are discussed, with a description of needs for confidence scoring in such systems. Physics of propagating waves, their mathematical representations and phenomena of relevance to the thesis are explained in Chapter 4. The chapter also defines the concepts of

SVand TDOA. TDOA-based DOA estimation methods utilize TDEalgorithms in the first stage of processing. The TDE task is described in Chapter 6, together with the typical estimation methods and challenges.

Chapter 7 defines theSVestimation framework as a linear model and explains the conventional and more recently proposed approaches to the estimation problem. Design of arrays and some special estimation cases are briefly covered, including the results of publication [P6].

Confidence scores ofSVestimates are treated in Chapter 8. A norm-based lower bound for the estimation error is proposed and an improvement to the closed-path confidence scores of [5]

is devised. This chapter is based on publications [P1] and [P4]. Two applications of confi-

(25)

6 Introduction

dence scores are presented in Chapters 9 and 10. The former considers detection of activity within SVestimates, the latter sensor failure detection and compensation. Chapter 9 is based on publication [P5], Chapter 10 on [P2] and [P3].

Chapter 11 generalizes the closed-path confidence scoring results beyond the plane wave

DOAdomain. A difference quantity model is developed and the missing statistical background, parameter setting principles and accuracy analysis of outlier detection are developed. This chapter is based on publication [P7]. A concluding discussion is given in Chapter 12. Ap- pendix A derives some results on the statistics of plane waveTDOAs. Appendix B provides a set of results from the activity detection experiment described in Chapter 9.

1.7 Publications

This thesis contains the results of the following seven chronologically listed publications.

[P1] T. Pirinen, P. Pertilä, and A. Visa, “Toward intelligent sensors - reliability for time delay based direction of arrival estimates,”Proc. IEEE Int. Conf. Acoust., Speech, Signal Process., pp. 197–200, 2003.

[P2] T. Pirinen, J. Yli-Hietanen, P. Pertilä, and A. Visa, “Detection and compensation of sensor malfunction in time delay based direction of arrival estimation,”Proc. IEEE Int. Symp.

Circ., Systems, pp. 872–875, 2004.

[P3] T. Pirinen, J. Yli-Hietanen, "Time delay based failure-robust direction of arrival estimation,"Proc. IEEE Sensor Array, Multichan. Signal Process. Workshop, pp. 618–622, 2004 [P4] T. Pirinen, "Normalized confidence factors for robust direction of arrival estimation,"Proc.

IEEE Int. Symp. Circ., Systems, pp. 1429–1432, 2005.

[P5] T. Pirinen and A. Visa, "Signal independent wideband activity detection features for mic- rophone arrays," Proc. IEEE Int. Conf. Acoust., Speech, Signal Process., pp. 1109–1112, 2006.

[P6] T. Pirinen, "A lattice viewpoint for direction of arrival estimation using quantized time differences of arrival,"Proc. IEEE Sensor Array, Multichan. Signal Process. Workshop, pp.

50–54, 2006.

[P7] T. Pirinen, "A confidence statistic and an outlier detector for difference estimates in sensor arrays,"IEEE Sensors J., vol. 8, no. 12, pp. 2008-2015, 2008.

No other dissertation is based on any of the included publications. The author is the principal contributor of research ideas and work in all of the publications with the following exceptions:

Prof. Ari Visa provided parts of the text for Sections 1 and 7 of [P1], supervised the work on [P2] and assisted in finalizing the text and structure of [P5]. Dr. Tech. Pasi Pertilä wrote parts of the software used for pre-processing the acoustic data in [P1] and provided overall comments for [P2]. Lic. Tech. Jari Yli-Hietanen participated in the design of experiments,

(26)

1.7 Publications 7

contributed to small parts of text and provided benchmark code for implementing the CNT- andMAD- estimation methods in [P2] and [P3].

Material from publications [P1]–[P7] cIEEE 2003–2008. Used with permission.

(27)

2 Preliminaries

This chapter explains the key mathematical concepts utilized in the thesis, describing properties of random variables and the normal distribution, hypothesis testing, estimation theory and linear models. The chapter has been adapted from [9–12], with referenced exceptions.

2.1 Elementary properties of random variables

In this thesis, it has been chosen not to distinguish between random variables and their re- alizations in terms of notation. Let x ∈ R^Nbe a random variable with Probability Density Function (PDF)f_x(x). Theexpectationofxis

µ_x =E{x}= Z

xf_x(x)dx (2-1)

and thecovariance matrixofxis

Σ_x=E

(x−µ_x)(x−µ_x)^T

. (2-2)

Elements ofxareuncorrelatedif the covariance matrix is a diagonal matrix.

An affinely transformed random variabley=Ax+bhas expectation

µ_y=Aµ_x+b (2-3)

and the covariance matrix

Σ_y=AΣ_xA^T. (2-4)

Ifµ_x=0it follows thatµ_y=bandΣ_x=C_x, where C_x=E

xx^T

(2-5) is the correlation matrix ofx.

The sum ofMrandom variablesy=PM

i=1xihas expectation µ_y=

XM

i=1

µ_i (2-6)

whereµiis the expectation ofxi. Whenxiare uncorrelated, the covariance matrix ofyis Σ_y=

XM

i=1

Σi (2-7)

whereΣ_iis the covariance matrix ofxi. The matrixΣ_yis diagonal if eachΣ_iis diagonal. That is, when the elements of eachxiare uncorrelated and vectorsxiare uncorrelated.

(28)

2.2 Normal distribution 9

2.2 Normal distribution

2.2.1 Definition

A random variablex ∈ R^Nwith expectation µ_x and covariance matrixΣ_x is normally distributed if it has thePDF[9, pp. 34]

f_x(x) = 1 (√

2π)^Np

|Σ_x|exp

−1

2(x−µ_x)^TΣ_x⁻¹(x−µ_x)

. (2-8)

2.2.2 Conditional distributions

Letzbe a normally distributed random variable so that z=

"

x y

#

, µ_z =

"

µ_x µ_y

#

, and Σ_z=

"

Σ_x Σ_xy Σ_yx Σ_y

#

wherex andy are normally distributed random variables. The conditional distribution ofx givenyis normal with expectation

µ_x|y=µ_x+Σ_xyΣ_y⁻¹(y−µ_y) (2-9) and covariance matrix

Σ_x|_y=Σ_x−Σ_xyΣ_y⁻¹Σ_yx (2-10) whereΣ_x|yis theSchur complement[13, pp. 2] ofΣ_yinΣ_z[14].

For scalar random variablesxandywith respective expectationsµ_xandµ_y, variances σ_x andσ_x, as well as covarianceσ_x,ythe conditional expectation (2-9) reduces to

µ_x|y = µx+ σ²_x,y

σ²_y (y−µy) = µx+ σ_x σ_y· σ²_x,y

σ_xσ_y(y−µy) (2-11) and the conditional variance (2-10) to

σ_x|y = σ²_x−σ⁴_x,y σ²_y = σ²_x



1− σ²_x,y σ_xσ_y

!2

. (2-12)

Quantity σ²_x,y

σ_xσ_y is thecorrelation coefficientofxandy. [9, pp. 34–37, pp. 264–265]

2.2.3 Q-function

The probability of a scalar random variable to take a value less than or equal toxis given by the cumulative distribution function

F_x(x) = Zx

−∞

f_x(y)dy. (2-13)

A common error function related to the normal distribution is theQ-function Q(x) =

Z_∞

x

√1 2πexp

−y² 2

dy (2-14)

(29)

10 Preliminaries

that provides probabilities for the standard normal distribution (µ_x = 0 andσ²_x = 1). For other normal distributions, the result is available through normalizationQ((x−µ_x)/σ_x). The Q-function is monotonically decreasing andQ(x) =1−Q(−x). [9, pp. 472]

For the normal distribution the above integrals are not available in closed form. Instead, the probabilities have to be obtained from tabulation or an approximation algorithm [15]. The inverseQ-function, that gives the value of the random variable providing a desired cumulative probability, is denoted byQ⁻¹(x). Its values are likewise available from approximations only [16].

2.3 Binary detection

This section describes the basics of binary detection theory. The simple binary hypothesis testing problem is described with the standard Neyman-Pearson approach. The hypothesis selection is based on likelihood ratio tests. Test performance assessment using a Receiver Operating Characteristic (ROC) is explained. Finally, testing is expanded to composite binary hypotheses and the Karlin-Rubin theorem that are utilized later in the developments of Chapter 11. The discussion follows [9, Ch. 11].

2.3.1 Hypothesis testing

Hypothesis testing is a method of determining the state of a source. At a given time instant, the source is in some stateythat is not directly measurable. Instead, dataxgenerated by the source, observations, are available. The state can, for instance, be a distribution parameter or presence of a signal whose effect is indirectly visible from the observations. It is assumed that possible values of state — elements in the parameter space — are known and disjoint and that the value of the parameter determines the distribution of observations.

The hypothesis testing procedure proceeds as follows: First, an observationxis generated from the available data. Depending on the scenario, the observation may be a direct signal sample or a feature, statistic or estimate computed from the samples. Second, based on the observation, a ruleΦ(x) is used to select the state. That is, to determine the parameter or to accept or reject a hypothesis.

There are two approaches to hypothesis testing; the Neyman-Pearson approach and the Bayes approach. The Neyman-Pearson approach is intended mainly for binary hypotheses and it is based on fixing a desired probability of false alarms and optimising the probability of detection. The resulting optimum method is a likelihood ratio test. The Bayes approach is suited for multiple hypotheses. The approach is based on assigning costs to incorrect detections and possibly rewards to correct detections. The optimum test is formulated as one that minimizes the expectation of cost. In the Bayes approach it is assumed that the state is a random variable whose prior probabilities are known or otherwise available. The Bayes minimax- approach, which minimizes the expected worst-case cost, can be used when prior probabilities are unknown. The Neyman-Pearson approach is utilized in this thesis and described in the remainder of this section. The Bayes approach is not considered further.

(30)

2.3 Binary detection 11

Detection result Φ(x) =0 Φ(x) =1

False alarm H⁰ Correct negative Type I error True

hypothesis

Rejection False positive False acceptance Type II error Detection H¹ False negative Correct positive

False rejection Correct acceptance

Table 2.1: Outcomes of a binary hypothesis test.

2.3.2 Simple binary hypothesis testing

A binary hypothesis test is a test where a selection is made between two hypotheses, the null hypothesis H⁰ :y = y0and the alternative hypothesisH¹ : y = y1. In a simple test the state parametersyiconsist of a single element.

Adetectionoccurs whenH1is true and accepted by the test. Two types of errors may occur in the testing: false alarms and missed detections. A false alarm occurs whenH⁰is true but rejected by the test. A false alarm is also known as a type I error, false acceptance or false positive. A missed detection occurs whenH0is accepted by the test whenH1is true. A missed detection is also known as a type II error, false rejection, or false negative. Outcomes of a binary test are summarized in Table 2.1.

Performance of a test is described bysize, denoted byα, andpower. For simple tests, size is equal to the Probability of False Alarm (PFA), formallyp(Φ(x) =1|y0). Power is the Probabil- ity of Detection (PD), defined asp(Φ(x) =1|y1). In the Neyman-Pearson approach, tests are compared using the concept of best test of sizeα. This is the test having the largest probability of detection for probabilities of false alarm less than or equal to a given size.

2.3.3 Neyman-Pearson lemma

The Neyman-Pearson lemma provides the optimum test for a given sizeα. The lemma states that any test of the form

Φ(x) =







1 , f_x|y(x|y1)> vf_x|y(x|y0) γ , f_x|y(x|y1) =vf_x|y(x|y0) 0 , f_x_|_y(x|y1)< vf_x_|_y(x|y0)

(2-15)

for some0≤γ≤1is the best of its own size for testingH¹againstH⁰. Further, for every sizeα, there exists an optimum test with a constantγ. The lemma also warrants that the optimum test for a given sizeαis always of the above form¹. Here,f_x_|_y(x|yi)is the conditional probability

1Exceptions may exist if there arexsuch thatf_x|y(x|yi) =0.

(31)

distribution of observationsx given state yi, and v is a threshold. Outcome γ represents a randomized test that choosesΦ(x) =1with probabilityγandΦ(x) =0with probability1−γ, where0≤γ≤1.

The Neyman-Pearson lemma provides a general rule for testing a simpleH⁰vs. a simple H¹. First, the null hypothesis H⁰ is determined. Usually this is selected as the state that has the worst effects from rejection, as this provides a possibility to control the probability of worst events. That is, the false acceptance ofH⁰. Second, a test size is selected. This is set according to the application requirements, with the understanding that the size setting affects power.

Third, the threshold producing the specified size is computed. There is no general formula for obtaining the threshold, but typically it follows from the assumed conditional distributions of observations f_x|_y(x|yi). Often the threshold is set to produce the Equal Error Rate (EER), at which probabilities of false alarm and missed detection are equal.

2.3.4 Likelihood ratio tests

Neyman-Pearson optimal tests rely on the fundamental comparison between the conditional

PDFs of the observationsf_x|y(x|y0) ∼ vf_x|y(x|y1). Ifxis taken as fixed, andyiis taken as the variable, functionl(yi,x) =f_x|y(x|yi)is thelikelihoodof parameteryigiven observationx. The ratio

ℓ(x) = l(y0,x)

l(y1,x) = f_x|_y(x|y0)

f_x|_y(x|y1) (2-16)

is called thelikelihood ratioand its logarithmic version is thelog-likelihood ratio

L(x) =log(ℓ(x)). (2-17)

Using the likelihood ratio the fundamental comparison is ℓ(x) ∼ vand test (2-15) can be ex- pressed as

φ(x) =







1 , l(x)> v γ , l(x) =v 0 , l(x)< v

. (2-18)

With the log-likelihood ratio (2-17) the test becomes

φ(x) =







1 , L(x)> η γ , L(x) =η 0 , L(x)< η

(2-19)

whereη = log(v). The logarithmic form is used to simplify statistical expressions for some distributions, for instance, the Gaussian distribution. If the PDF of ℓ(x) or L(x) given yi is known, a method for computing the threshold can be obtained.

2.3.5 Composite binary hypothesis testing

In a composite hypothesis the parameters are sets consisting of several elements, such as a region in space. The hypotheses are defined asH⁰:y∈ Y⁰andH¹ :y∈ Y¹, whereYⁱdenote

(32)

2.3 Binary detection 13

the parameter sets. The parameter determines the conditional distribution of observations.

Because the parameter may take different values within a composite hypothesis, the observation distributions are not unique. Consequently,PDandPFAare dependent on the hypothesis element and are neither unique. Thus, they cannot be used to define size and power, which are both constant for a test with fixed parameters. This is contrary to the testing of simple binary hypothesis.

For composite tests, size is defined as the supremum² ofPFAs for the null hypothesis ele- mentsy∈ Y⁰

α= sup

y∈Y0

p(Φ(x) =1|y). (2-20)

An optimum test is defined as the Uniformly Most Powerful (UMP) test, a test with the largest

PDfor each H¹-element y ∈ y1. Existence of a UMP test is not guaranteed in general but a special case can be treated with the Karlin-Rubin theorem.

2.3.6 Karlin-Rubin theorem

Consider hypotheses where a space of scalar parameter values is partitioned in two regions such that H⁰ : y ≤ y^′ and H¹ : y > y^′. Assume further that the observations have non- decreasing likelihood ratios — the likelihood ofH¹ does not decrease whenxenlarges. The Karlin-Rubin theorem states that for such cases there exists anUMPtest with nonzero size and the test is of the form

φ(x) =







1 , x > v^′ γ , x=v^′ 0 , x < v^′

. (2-21)

Existence of properγandv^′is guaranteed for each size0 < α≤1, such that theUMPproperty is satisfied.

2.3.7 Receiver operating characteristic

Receiver Operating Characteristic (ROC) is a plot ofPFAagainstPD, that completely specify the test performance. This is the most useful single method for evaluating the performance of a binary test. An exampleROCcurve is given in Figure 2.1.

Likelihood ratio tests have concaveROCs. TheROCs of continuous likelihood ratio tests are above the main diagonal p(Φ(x) =1|y0) = p(Φ(x) =1|y1). If an arbitrary test was below the diagonal, an inverted test would give better results. In the case of non-trivial distributions, numerical integration is required to quantify performance and to obtainROC. The (non-log) threshold needed to obtain a givenPFAandPDfor a simple test can be obtained from the slope of theROCat the operating point.

TheROC is not a scalar measure of detector performance. If one is needed, EER, ratio of detections to all decisions, or area under theROCcurve can be used, for instances. Note that

2Supremum is the least upper bound of a set.

(33)

Probability of False Alarm (PFA)

ProbabilityofDetection(PD)

ROC PFA=PD EER

0 0.2 0.4 0.6 0.8 1

Figure 2.1: Example Receiver Operating Characteristic (ROC).

EERis theROC-curve point that has the smallest distance to the upper left corner of thePFA-PD

coordinate space.

2.3.8 Requirements for a practical detector

Important requirements for a detector are that it generalizes easily, its parameters are easy to adjust and that the effects of parameters on detection accuracy are known. For real-time applications, it is further essential to have the detection result available immediately after a new datum has arrived, without delay and waiting for further data. Practical situations may require some additional constraints to be set. Furthermore, it is desirable for the detector to be adaptive in the sense that changes in the operating environment, such as noise level, do not require intervention. Rather, the detector should adapt automatically in such situations. The rate of this adaptation should be adjustable. Finally, the detector should be relatively simple to design, modify and use.

2.3.9 Summary of Neyman-Pearson binary testing

This section provided the basics of Neyman-Pearson binary testing. The main assumption is that the parameter (state) value is unknown but not random, and possible states are known and disjoint. Simple and composite tests were treated. The Neyman-Pearson principle of detection is based on the prior observation distributions and aims to keep test size constant and maximize power. Testing can be reduced to likelihood ratios which simplifies the analysis and threshold selection. Test performance is completely characterized byROC. An optimum test for a composite hypothesis is given by the Karlin-Rubin theorem.

There are several practical issues that need to be addressed when the theory is applied.

Finding the threshold to yield the desired performance is crucial. The theorems warrant the existence of a threshold but the means to obtain the threshold are specific to each case. The ob-