0.2 Algorithm

Algorithm

We tried two methods that both can work with one of them having a better result. For both algorithms, we input the time delays between each microphone (microphone 1 through 4) and output the xy-coordinates.

Get time delays

First of all, to get the time delay information, we tried several methods to decide the time we get the pulse for each microphone. Method I is to catch the peak in certain time periods. In our Labview program, it checks every 0.5 second for at which time point the sound has the largest amplitude in the previous 0.5 second, and return that time point. Method II is to set an amplitude threshold, and return the first time point that is above the threshold. We set the threshold to be 0.5V to avoid the influence of noise and also catch the pulse we generate. In this method, we disable the threshold for 0.5 second after the program gets a time point to avoid the influence of imperfect pulse. By disabling the threshold, we ignore the sound that has amplitude above the threshold in this 0.5 second. After synchronizing the four microphones, we can get the time delays between each microphone.

Method i: direct equation solving

We measured the time delay of received sound among four microphones, t_12, t_13, and t_14, where t_AB stands for the time delay of microphone A minus that of microphone B. Based on the physics fact that d=v*t and v is a constant (340m/s in the air), we know the relative distance difference from the point to four corners, called d_12, d_13, and d_14.

Assume the coordinates of the point we are solving to be (x,y), the length of the panel to be a, and the width of the panel to be b. Using some simple geometric fact, we can represent the distance from the point to each microphone with (x,y), a, and b. By equating the differences of the calculated distances to the corresponding measured differences, d_12, d_13, and d_14, we get three equations. We solve equation 1 and 2 in Matlab, and get two possible x’s (called x1 and x2), and two possible y’s (called y1 and y2). Similarly, by solving equation 2 and 3 in Matlab, we can get possible x’s (called x3 and x4), and two possible y’s (called y3 and y4). Theoretically, there’s always a number that is both in the first set of x(x1 and x2) and the second set of x (x3 and x4), and that should be the x coordinate we want. The same holds for y coordinate.

In practice, due to the noise and errors, we can never get an exact same x or y in two sets. Therefore, we calculate the differences between x1 and x3, x1 and x4, x2 and x3, and x2 and x4, and find the pair with minimum difference. We then decide the average value of the pair to be the x coordinate. The same for y coordinate.

This method sometimes gives us results that far beyond our bounds and can be very unstable, so we try to develop a second method.

Method ii: match filter

Setting the resolution to be 1 cm, we divide the board to 1cm*1cm grid. For each point (m, n) on the grid, calculate the distance from this point to each microphone using geometric relations, and get the distance differences d_12, d_23, and d_34, where d_AB stands for the distance to microphone A minus distance to microphone B. Note that we use d_23 and d_34 instead of d_13 and d_14 as in the first method since we notice that it may introduce more error if we rely on one microphone (microphone 1) too much. Based on the physics fact that t=d/v and v is a constant (340m/s in the air), we get the theoretical time delays t_12, t_23, and t_34 for point (m, n).

Assume the corresponding measured time delay to be m_12, m_23, and m_34. For each point on the grid, we calculate the root-square-mean error between the measured time delays and the theoretical time delays:

We then find the point (x, y) in the grid that has the least error and return it as the xy coordinate.