3% munmlum1mmlennmnmtwmmwmum 'HESIS ESR SITY LIBRARI IE lllllllllllllllllllllllllllll\llHII lelllll 3 1293 016918 This is to certify that the thesis entitled Learning-Based Three Dimensional Sound Localization Using a Compact Non-Coplanar Array of Microphones presented by Kamen Yankov Guentchev has been accepted towards fulfillment of the requirements for Master of Science degree in Computer Science WWW V Major professor Date 12 / 08 / 1997 0-7639 MS U is an Affirmative Action/Equal Opportunity Institution LIBRARY Michigan State Unlverslty PLACE IN RETURN BOX to remove this checkout from your record. TO AVOID FINE return on or before date due. MTE DUE MTE DUE DATE DUE use «mumps-p.14 LEARNING—BASED THREE DIMENSIONAL SOUND LOCALIZATION USING A COMPACT NON-COPLANAR ARRAY OF MICROPHONES By Kamen Yankov Guentchev A THESIS Submitted to Michigan State University in partial fulfillment Of the requirements for the degree Of MASTER OF SCIENCE Computer Science Department 1997 ABSTRACT LEARNING-BASED THREE DIMENSIONAL SOUND LOCALIZATION USING A COMPACT NON-COPLANAR ARRAY 0F MICROPHONES By Kamen Yankov Guentchev One Of the various human sensory capabilities is to identify the direction Of per- ceived sounds. The goal of this work is to study sound source localization in three dimensions using some of the most important cues the human uses. Having robotics as a major application, the approach involves a compact sensor structure that can be placed on a mobile platform. The Objective is to estimate the relative sound source position in three dimensional space without imposing excessive restrictions on its spatiO-temporal characteristics and the environment structure. Two types of features are considered, interaural time and level differences. Their relative effectiveness for localization is studied, as well as a practical way Of using these complementary pa- rameters. A two-stage procedure was used. In the training stage, sound samples are produced from points with known coordinates and then are stored. In the recognition stage, unknown sounds are processed by the trained system to estimate the 3D loca- tion Of the sound source. Results from the experiments showed under :I:3° in average angular error and less than i20% in average radial distance error. ACKNOWLEDGMENTS I would like to thank my advisor, Dr. John Weng for the productive guidance through- out my thesis research. Special thanks go to Dr. George Stockman for his support in my studies and scientific work in general, and for believing that an astronomer can be a good computer scientist, too. I would also like to thank the other members Of my committee, Dr. Moon-Jung Chung and Dr. Sridhar Mahadevan, for the useful comments and suggestions. I am very grateful to Shaoyun Chen for making SHOSLIF code available for use by this project and for having helped in many other ways. I would also like to thank all students in Pattern Recognition and Image Processing laboratory for assisting me in my experimental work and in the preparation of this thesis. Last but certainly not least, I would like to thank my dearest fiancee, Galia, who helped me in so many ways. I could not have completed this work without her invaluable help. She not only Spent many Sleepless nights helping me take samples from the experimental setup, preparing tables and graphics and proofing copies of the thesis but most importantly she always supported me morally and never let me stop believing I could achieve this goal. iii TABLE OF CONTENTS LIST OF TABLES LIST OF FIGURES 1 Introduction 1.1 The problem Of sound localization by machine ......... 1.2 Review Of related experimental work .............. 2 Theoretical problem and sensor structure 2.1 Parameters ............................ 2.2 Number and placement of detectors ............... 2.3 Geometric representation ..................... 2.3.1 From Intensity Ratios (IR) .................. 2.3.2 From Phase Differences (PD) ................. 3 Methodology 3.1 Feature Extraction ........................ 3.2 Source localization ........................ 4 Experimental setup and results 4.1 Experiment and results ...................... 4.1.1 Hardware ............................ 4.1.2 Experiment ........................... 4.1.3 Results ............................. 4.2 Program performance and details ................ 4.3 Implementation restrictions ................... 5 Conclusions 5.1 Discussion ............................. 5.2 Future research .......................... APPENDICES A Class “IADifl'”: Signal Preprocessing B Class “LinSrch”: Linear Search iv ...... 41 41 48 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 LIST OF TABLES Comparative timings Of various routines .................... Average error in azimuth for different values Of Scaling on ILD (x) and weighting coefficient (y) as plotted in Figure. 4.3 [degrees] .............. Standard deviation Of error in azimuth, for different values of Scaling on ILD (x) and weighting coefficient (y) as plotted in Figure. 4.4 [degrees] Average error in elevation for different values Of Scaling on ILD (x) and weight- ing coefl‘icient (y) as plotted in Figure. 4.5 [degrees] ............ Standard deviation Of error in elevation, for different values Of Scaling on ILD (x) and weighting coefficient (y) as plotted in Figure. 4.6 [degrees] Average error in distance for different values of Scaling on ILD (x) and weighting coefficient (y) as plotted in Figure. 4.7 [%] ................. Standard deviation Of error in distance, for different values of Scaling on ILD (x) and weighting coefficient (y) as plotted in Figure. 4.8 [‘70] ....... Error values for Scaling on ILD = 11 and weighting coefficient = 1 ...... 28 32 33 34 34 35 36 2.1 2.2 2.3 3.1 3.2 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 LIST OF FIGURES Two detectors and a sound source ....................... 8 Microphone placement on the array ...................... 10 Distances from source to four detectors .................... 11 Preselection according to Signal variance .................... 17 Typical cross-correlation curve with good Sharpness .............. 18 Training the system .............................. 23 Experimental setup .............................. 24 Distribution of error values for Azimuth .................... 26 Distribution of standard deviation for Azimuth ................ 27 Distribution of error values for Elevation ................... 28 Distribution of standard deviation for Elevation ................ 29 Distribution of error values for Distance .................... 30 Distribution of standard deviation for Distance ................ 31 Screen with signals and data dialog ...................... 37 vi Chapter 1 Introduction A sound produced by a point-source generates acoustic waves with Spherical symme- try, assuming uniform density Of the surrounding air and absence of obstacles or other sounds. It is known that the location Of the source can be established by detecting the front Of the propagating wave and computing the center Of the sphere [9][10]. Un- fortunately acoustical waves are not clearly distinguishable objects and such a task is not trivial in real environments even if real-life sources could be approximated by points [18]. Numerous studies have attempted to determine the mechanisms used by humans to achieve dimensional hearing [10][13][14]. Most phenomena have been rea- sonably explained in principle, although many aspects Of human dimensional hearing need further study. It is known that two Of the most important cues used by humans are the interaural differences: in time and level (ITD, ILD) [18] [24] [25]. Other cues relate to the spectral variations caused by diffractions at the head and pinnae [3]. For sounds with longer duration, cognitive processes start playing an important role, including dynamic head adjustments, high-level reasoning, etc. [25]. I 2 1.1 The problem Of sound localization by machine Sound localization can be used in many different applications: robot hearing, human- machine interfaces, monitoring devices, handicappers’ aids, etc, where other means fail for different reasons. The Obvious importance of building sound localization de- vices has prompted numerous efforts in the research community and a variety Of techniques has been developed. Driven by concrete application needs, sensor setups Of different implementations have seldom attempted to follow the human model. The number, size and placement of the sensors in such devices follow the specific needs of the task and are Optimized for accuracy, stability, ease Of use, etc. For example, a number of microphone subarrays have been placed on the walls with a goal to pick up the location of a speaker in a room [5] [6][7] [20]. In other studies a human model has been followed to some degree resulting in constraints in applicability and limited ac- curacy [19]. A significant amount of work has been devoted to devices with a limited functionality (e.g. constrained to localization in a single half-plane while still using large sensor structures) [8] [20] or the help of a non-acoustical modality has been used (e.g. vision)[8]. In contrast to large, fixed sensor arrays for special situations and environments, this work concentrates on a compact, mobile sensor array that is suited for a mobile robot to localize 3D sound sources with moderate accuracy. It should have the ability to be positioned arbitrarily in Space while being capable Of identifying the relative position Of an arbitrarily located sound source. It is necessary to point out that the human three dimensional sound localization capabilities, while amazingly accurate in some instances often have very serious limitations. The precision depends on various characteristics of the perceived sound: spectral contents, envelope variability as a function Of time, volume level, reverberation and echo, etc. It can be disappointingly 3 low and in some instances totally inconclusive [13]. Sometimes it can be convinc- ingly wrong (e.g. Franssen effect) [14]. One major diffference between human and engineering setup is the number of sensors available. Most authors distinguish a single parameter as the most significant factor for di- mensional sound localization. It is the interaural time difference (ITD) Of the sound as perceived by two sensors. Numerous studies report the ITD as the main cue in human dimensional hearing [24]. The clear geometrical representation Of the problem makes it the favorite feature tO be used when approaching such a task by a machine setup [4][5][7][8][12][16][17][20]. However, if we return to the physical aspect of the problem, it is clear that even three sensors (non-collinear) are not sufficient by them- selves tO establish unambiguously the three dimensional location of the sound source: Obviously there are two symmetrical solutions on each side Of the plane, containing the sensors. It is then reasonable to incease the number to four microphones, to localize arbitrarily placed sound sources. Another cue known tO have notable importance in human dimensional hearing is the interaural level differences (ILD). Surprisingly ILD have seldom been used in ac- tual system implementations because they are believed to have unfavorable frequency dependence and unreliability [18][19]. Another reason is the lack Of an explicit and stable relationship between ILD and source location which will allow for a simple al- gorithmic solution to be derived [18]. The learning approach used in this study does not have such limitations and it benefits from the added cues. Finally the processing Of the extracted features is one Of the dominating fac- tors for the success Of a localization procedure. Most works determine the ITD and then use either an iterative search algorithm to minimize a certain Objective function [15][19] [20], or an approximation model for which a closed-form solution can be de- rived [5] [6] The former is relatively Slow and thus, it may not reach real time speed. 4 The latter introduces model errors and cannot use more features for better accuracy. TO use both interaural time differences (ITD) and interaural level differences (ILD) while effectively dealing with the complex nonlinear relationships among these feature measurements and the solution, this work employs a learning based approach. It consists of a training phase and a performance phase. In the training phase, sounds from known 3D positions are generated for training the system, which builds a fast retrieval tree. In the performance phase, the system approximates the solution by retrieving the top match cases from the retrieval tree. This flexible framework allows for the use of more than one type of feature, and to deal with the 3D localization problem without imposing unrealistic assumptions about the environment, despite the compactness of the sensor structure. TO the best of my knowledge, this work is the first to use a compact non-coplanar sensor array for full 3D sound localization. In order to correctly evaluate the performance Of the system, initially a lin- ear search algorithm was used when searching for the nearest neighbors in the 12- dimensional input space. The obtained results were also used to evaluate the cor- rectness and the performance of the previsouly developed and tested with other im- plementations SHOSLIF procedure. It achieves a high Speed of retrieval due to its logarithmic time complexity O(log(n)), where n is the number Of cases learned and stored as necessary [22][23]. It was found that the results produced by SHOSLIF had identical precision with that Of the linear search, while its performance time was nearly 5 times faster, even with the relatively low dimensionality of the employed search Space. 5 1.2 Review Of related experimental work Extensive work on sound localization by microphone arrays has been performed by Michael Brandstein, in association with other authors at Brown University. A Sig- nificant effort in the theory Of Speech based sound localization is incorporated in a series Of publications [4] [5] [6] [7] Novel methods for estimating ITD and using it for the localization are presented, among which are a pitch-based approach to time delay estimation and a closed-form location estimator. The implementations concentrate on room oriented solutions - microphone arrays placed in room walls. The sound 10- calization is applied in three dimensions but one of the dimensions (the vertical axis) is highly restricted. The reported accuracy of localization is very high - the Space resolution is in the order Of centimeters. However, it is impossible to compare to the accuracy Of the work presented in this thesis, because the placement Of sensors is different. In the case Of room-oriented placement it is impossible to define a direction or distance from the array since the array surrounds the source. Phrthermore the application domain Of the room-oriented implementation is much more limited than that Of a free standing array. A model for 3D sound localization that uses both ITD and ILD is presented by Keith Martin of MIT in [19]. The work simulates the human auditory system and uses a binaural setup. Some assumptions and approximations of the real-life environment are made and as a consequence the system can only estimate angular direction but no distance. The experiments are performed in an idealized environment (e.g. noise is eliminated) and an angular accuracy of around 5° is achieved. All computations are performed Offline. One Of the applications with hybrid methodologies is the work of Udo Bub, Mar- tin Hunke and Alex Waibel at Carnegie Mellon University [8]. They use a second 6 modality (vision) to improve the performance Of the localization device by refining the location estimate, provided by the sound localization. Their approach involves the use of ITD only as determined by a linear array Of 15 microphones for redundancy. This setup limits their application to recognition in a Single half-plane in front Of the array. With acoustic means only, their system achieves an angular accuracy of around 5° and under 10% in distance with bacground noise only. This error is estimated from a single point in Space in front of the array. The authors indicate that competing noise can Significantly degrade the accuracy Of localization. Another work with a practical implementation is by Daniel Rabinkin et al. at Rutgers University [20]. Their system is limited to two-dimensional localization yet it uses two subarrays Of 4 coplanar microphones each, placed on room walls. It employs a DSP to estimate ITD by using a cross-power spectrum phase algorithm. Then a Space search algorithm minimizes the error between estimated and computed delays to produce a location estimate. The performance with the algorithms being run Offline is reported as a percentage Of deviation from a preset bound Of 6° and is reported as being generally lower than 20%. The performance from the online tests is reported as being from “moderately well” to “quite poor”. A number of other publications [3][11][12][13][14][15][16][17][25] treat theoretical aspects of auditory localization and the various methodologies used in practical sound source localization. However, there is no experimental work or actual implementations reported. The problem of full three dimensional sound source localization with a compact mobile structure, as examined by this thesis, has not been considered in any other work included in the scope of this survey. Chapter 2 Theoretical problem and sensor structure Required by versatile applications such as the dimensional hearing of a mobile robot, we cannot use room-oriented solutions [6] [20], which typically use a large intersensor distance, with all the sensors fixed in the room. In our case the sound source will necessarily be located outside of the sensor structure. Furthermore the distance to the source will generally be Significantly larger than the dimensions Of the sensor structure. Most of the sound sources that can be of interest for the purposes Of sound localization are compact enough to be assumed point—sources. If the source cannot be approximated by a point then the problem is different and for the case of a source Size comparable to the source-detector distance, the problem is outside the scope Of this work. The same applies to the case Of distinct sources Of comparable intensity. TO determine the minimum number of sensors and their Optimal placement, we need to look into the geometrical aspects Of the problem. 7 2. 1 Parameters From the front of the Spherical acoustic wave, the two main parameters that can be estimated are ITD and ILD. Assuming that the Speed of sound is constant, which is true only for uniform media (density, temperature, chemical and physical contents, etc.), we can claim that ITD is proportional to the difference Of the distances between each Of the detectors and the sound source: ITD ~ r1 — T2, (2.1) where r,- is the distance between the sound source and the i-th microphone, i = 1,2, and ~ indicates proportional (Fig. 2.1). Also Since the amplitude Of the sound wave, 1': Figure 2.1: Two detectors and a sound source or the intensity Of the sound, varies inversely with the square of the distance, the ILD is proportional to the difference between the inverse values Of the square Of the dis- tance. However if we take the difference we will be confronted with high-order terms in the equations which will lead to unnecessary complication Of the computations. A much Simpler form is provided by the ratio Of the two values: 2 7‘2 RD~— mm B Both parameters can be measured and if we are able to unambiguously define the geometric representation then we would have a good method for solving our problem. 2.2 Number and placement of detectors In order to determine the minimum number Of detectors necessary we will first have to consider the geometric representation. For each couple of microphone detectors, we can derive the locus Of the source points corresponding in three dimensional Space to a given measured value Of ITD or ILD. From equation (2.1) the locus is represented by a hyperboloid of two sheets Of revolution with foci 01 and D2. Depending on the Sign of the difference one Of the sheets contains the source location. Then from equation (2.2), for the matching ILD, it is less Obvious but the forthcoming calculations will Show the locus is a sphere [1][2][21]. The intersection of these surfaces defined by a number Of detector couples will determine the ambiguity Of the solution. It is clear that, apart from some Special cases, with three couples the intersection is two points located symmetrically on both Sides of the plane containing the three detectors. If four non-coplanar detectors are used the intersection is a single point. Because Of the assumed isotropy Of the locality, an equidistant structure seems reasonable. In the case Of four sensors this suggests a tetrahedron (Fig. 2.2). A mobile robot requires that the structure Of the sensor array be compact, while accuracy consideration requires a large array. In the experiment, an equal-side tetrahedron with a 20cm Side was used. 10 2 Figure 2.2: Microphone placement on the array 2.3 Geometric representation AS we established earlier in equations (2.1) and (2.2), we need only use the geomet- ric distances 1', between the detectors Dij and the sound source S. Without lOSS Of generality we assume the following locations of the four detectors in a Cartesian coordinate system: D1(0, 0, 0), D2(2a, 0,0), D3(0, 2a, 0), D4(0, 0, 2a). In this represen- tation the detectors are not equidistant: the distance between D1 and the rest will be 2a and the distance between any pair Of Dz, D3 and D4 will be 2x/2a (Fig. 2.3). 2.3.1 From Intensity Ratios (IR) We can define the following constants corresponding to the IRS: 11 2a '\ (X.Y.Z) p o‘ a o’ a‘ o‘ a c" c — o' a p o I" ‘ ‘- a o‘ 9‘ n u — n’ 5' n o n 0‘ a .- 1 .. 2 _ It 11 LL _ r 12 I3 [4 r1 _ __ [2. £2. _ _ 13 I4 __ _ __ L1 _ _ 14 l. . . .1 N ‘3‘1‘1 IQ tor- a“? *> 2a and therefore q,- C‘—_’ 1, which means the L,,- are Of the same order. Thus for layouts as the one used in this work (2.8) has a 13 unique solution and hence the same is true for (2.6) and (2.7). We also have a purely geometrical indication of that fact, which is however difficult to visualize. Consider the 3 spheres described by (2.6). Their centers are non-collinear and their radii are of the same order. Therefore in the worst case two of them intersect in a circle and the third intersects that circle in two points. The same can be said about the spheres derived from (2.7). Furthermore we know the two new points are not collinear with the first two Since the centers Of the second set Of Spheres does not lie in the same plane as those from the first set. Hence only one point can be the intersection of all Six Spheres, which suggests the uniqueness of the solution. AS was mentioned above, in our case cij E 1. That was helpful (although not necessary) in establishing the uniqueness of the solution. Unfortunately that brings up a problem for the practical computing of the exact location of the sound source, because that means Lij and Rij grow rapidly as W approaches 1. (The first derivative of Lij and Rij as functions of Cij has large values as Cij tends to 1, which means a large error in Lij and Rij when determined by cij ). However the geometrical representation of the problem Shows that we have an intersection of Spheres with very large radii but whose centers are far apart, which indicates that the solution is stable. Thus the solution is an intersection Of a number of spheres. The measurement error impacts both centers and radii of the Spheres but the error in radius is the one that determines the Shape of the solid, representing the margin of errors. It is wide when viewed from the sensors and flat when viewed from the Side. The actual impact of these Observations, as it will clearly be shown from the experiments, is that the ILD, which are a representation of the IR, will provide a good indication of the distance to the sound source but a poor estimate of the angle. 14 2.3.2 E‘om Phase Differences (PD) So far we have only considered the IR. Although the PD seem more promising for the purpose of obtaining an accurate solution they are much more difficult to deal with analytically. Before we had the only quadric surface with spherical symmetry - the sphere - and thus we were not concerned with rotated axes: the equation of the Sphere can only differ from its canonical form by a factor of translation, reflected as a constant term added to any of its variables. Unfortunately in the case of PD the locus of the possible solutions for each pair of detectors constitutes a hyperboloid of revolution of two Sheets. Let us redo some of the steps we did for the IR. We define analogically some constants: — (Pl-(P2 Cinclude class IADiff 41 42 { private: short #framel, tframe2, tsubframe; unsigned short marShift; unsigned short prescanHindow; double tsubVar; double bestShift, bestIratio. meanVar; unsigned short nSamples, nSubFrames; public: // default constructor IADiff(void); 'IADiff(void); //AGC first channel second channel 3 of samples/channel number of subframes double Init(const unsigned short, const unsigned short, const unsigned short. const unsigned short, // array with data samples const unsigned short t); //ret:Z used data ITD ILD score double IADcompute(doub1et , doublet , doublet ); private: // frame 1 frame 2 number of samples/ch size of X0 window short MaXCorr(const shortf] . const shortE], const unsigned shortt. const unsigned shortt, //sigma factor max R ratio s-threshold unsigned short&. doublet. doublet, const doublet); //ret:varience array w/data double PreScan(const short XEJ); //ret:avg var. variance double Variance(double[]); }; tendif Definitions Iinclude "IADiff.h" IADiff::IADiff() { const unsigned short Channels = 4; nSubFrames I 0; prescanHindow I 0; frameIINULL; frame2-NULL; subframe-NULL; subVar-NULL; maxShift I 12; } IADiff::'IADiff(void) { 43 delete framel, frame2, subframe, subVar; } double IADiff::Init(const unsigned short Chi, const unsigned short Ch2. const unsigned short nSamples. const unsigned short nSubFr, const unsigned short IData) { const unsigned short Channels I 4; unsigned int overflows1 I O. overflows2 = 0, uprange1=0, uprange2=0; double modfactor1, modfactor2; nSubFrames I nSubFr; prescanHindow I unsigned short(nSamples/nSubFrames); framel I new short [nSamples]; frame2 I new short [nSamples]; subframe I new short [prescanHindow]; // a buffer for storing the subframes subVar I new double [nSubFrames+2]; // holds the variance of each subframe + MAX t HIN marShift I 12; // the value of the maximum possible ITD for(int iIO; i205) : uprange1++; LL frame2[i]=short(Data[Channels*i+Ch2]-2047); if(frame2[i]II-2O47) overflows2++; else if(frame2[i]II2048) overflows2*+; if(abs(frame2[i])>205) uprange2++; } if(uprange1<0.01InSamp1es tt uprange2<0.01InSamples) // if there are <11 samples with amplitude >101 return(-1.0); // of ADRANGE - signal to increase gain modfactorIIoverflows1/double(nSamples); modfactor2Ioverflows2/double(nSamples); if(modfactor1 >I modfactor2) return(modfactor1); else return(modfactor2); short IADiff::HaXCorr(const short XE], const short YE]. const unsigned shortt N. const unsigned shortt n, unsigned shortt sigma. doublet Rmar, doublet ratio, const doublet sThreshold) { long Irjo, Irok; double Imeanx. ImeanY; _,int64 ISth, *StdY; double IRjo, that; long maxCIO; long i,j; meanXInew double In]; meanYInew double [n]; double sumX, sumY; ronnew long In]; rokInew long In]: SthInew _-int64 In]: StdYInew --int64 [n]; RjOInew double [n]; RokInew double [n]: // Computing the means of the two inputs // ‘44 meanXIOJIX[0];meanY[O]=Y[0]; for (i=1; i tinclude tinclude class LinSrch I private: double PI; unsigned int dimIAD, dimAngles, dimDist, dimLines; float sqscale, alpha; float IIdata; // array to store the training samples unsigned int KNN; // K-th Nearest Neighbor to be considered // array probed dist position index void insert(floatII , const float, const int, const unsigned int); public: // default constructor LinSrch(unsigned int, unsigned int, unsigned int. chart, float, float); ’LinSrch(void); 48 49 // signal control scale alpha void search(float*. floatt, float, float); 1: Sendif Definitions tinclude "LinSrch.h" LinSrch::LinSrch(unsigned int dimI. unsigned int dimA, unsigned int dimD, chart filename, float 38, float a) I } // The constructor reads the samples form the file and builds an array to hold them fstream samples; unsigned int nLines. i.j; float dataLineEISI: PII3.14159265358979323846; KNNI7; // K-th Nearest Neighbor to be considered sqscaleISS; alphaIa; dimIADIdimI; // dimension of IADs, i.e. how many numbers are there dimAnglesIdimA; // dimension of angular coordinates, i.e. from IAD to IAD+dimA-1 are angles dimDistIdimD; // dimension of distance-coordinates. i.e. from dimA to IAD+dimA+dimD are distances samples.open(filename, ioszzin); if(samples.fail()) exit(-1); nLinesIO; while(!samples.eof()) // count the number of lines in the file I for(iIO; i<15; i++) samples >> dataLine[i]; nLines++; } nLines--; samples.seekg(0); // reset the file samples.clear(); data I new float I[15]; // make the array to hold the data for(iIO; i<15; i++) data[i] I new float [nLines]; for(jIO; j> data[i][j]; if(i>=dimIAD tt iIKNN) // hit the bottom - throw it away! return; if(newDist