User:Tedburke/Sandbox

Draft Solution of the Tapping Localisation Problem

Introduction

This is a draft solution for what we are currently referring to as the tapping localisation problem. The problem relates to an experimental human-machine interface which is under development. A rectangular board sits on a horizontal surface. At each corner of the board is an accelerometer which senses vibrations. When the board is "tapped", vibrations propagate outwards in all directions from the point of impact. Because the distance from the point of impact to each corner is different, the vibrations are detected by each accelerometer at a different time. Knowing only the dimensions of the rectangle and the time at which each accelerometer sensed the impact, the objective is to calculate at what point on the board the tap occurred. This is the tapping localisation problem.

It is easy to think of many other problems which resemble this one - e.g. finding the epicentre of an earthquake using readings from multiple measurement stations or identifying the position of an audio source using a microphone array - so it must certainly have been solved before. However, since the problem seemed like a straightforward geometrical one, we tried to solve it ourselves from first principles. Unfortunately, although we have a working solution (as described below), it is not an entirely satisfactory one. Part of the solution is carried out using an iterative numerical method - something which my instinct tells me should not be necessary. Nevertheless, a purely analytical solution has so far eluded us, so what follows will have to do for the moment.

Assumptions and Notation

The tapping area is assumed to be a rectangle of width $w$ and height $h$. As shown in the diagram below, the four corners of the rectangle are as follows:

• A is the bottom left corner, at coordinates (0,0)
• B is the bottom right corner, at coordinates (w,0)
• C is the top right corner, at coordinates (w,h)
• D is the top left corner, at coordinates (0,h)

At time $t_{0}$, a "tap" occurs at a point $p=(x,y)$ somewhere inside the rectangle. There is one accelerometer at each corner of the rectangle. Each accelerometer detects the tap only when the resulting vibrations have propagated out from $p$ as far as its location. The speed of propagation, $v$, is assumed to be constant throughout the medium.

Initially, $v$ is not known. Also, when a tap occurs, the time of impact is not known initially. All that we have to work with are the times at which the tap's vibrations reach each of the accelerometers. These four times are $t_{a},t_{b},t_{c}$ and $t_{d}$.

Obviously, $t_{a},t_{b},t_{c}$ and $t_{d}$ are greater than $t_{0}$ (i.e. no accelerometer can detect the tap before it occurs). Furthermore, the propagation speed, $v$, is constant and positive.

Finally, $a,b,c$ and $d$ are the distances from $p$ to corners $A,B,C$ and $D$ respectively.

Applying Pythagoras' Theorem

Using Pythagoras' theorem we can the following expressions for $a^{2},b^{2},c^{2}$ and $d^{2}$ in terms of $x$ and $y$.

$a^{2}=x^{2}+y^{2}$

$b^{2}=(w-x)^{2}+y^{2}$

$c^{2}=(w-x)^{2}+(h-y)^{2}$

$d^{2}=x^{2}+(h-y)^{2}$

Combining these equations in two pairs yields the following two equations.

$a^{2}+c^{2}=2x^{2}+2y^{2}-2wx-2hy+w^{2}+h^{2}$

$b^{2}+d^{2}=2x^{2}+2y^{2}-2wx-2hy+w^{2}+h^{2}$

It is clear from these that

$a^{2}-b^{2}+c^{2}-d^{2}=0$

Propagation Delays

We can also express a, b, c and d in terms of the detection times $t_{a},t_{b},t_{c},t_{d}$ and the unknowns $t_{0}$ (the time at which the tap occurred) and $v$ (the propagation speed).

$a=v(t_{a}-t_{0})$

$b=v(t_{b}-t_{0})$

$c=v(t_{c}-t_{0})$

$d=v(t_{d}-t_{0})$

As we did above with the corresponding pythagorean expressions, we now write expressions for $a^{2},b^{2},c^{2}$ and $d^{2}$.

$a^{2}=v^{2}(t_{a}-t_{0})^{2}$

$b^{2}=v^{2}(t_{b}-t_{0})^{2}$

$c^{2}=v^{2}(t_{c}-t_{0})^{2}$

$d^{2}=v^{2}(t_{d}-t_{0})^{2}$

Now, since we know that $a^{2}-b^{2}+c^{2}-d^{2}=0$, we can write

$v^{2}\left((t_{a}-t_{0})^{2}-(t_{b}-t_{0})^{2}+(t_{c}-t_{0})^{2}-(t_{d}-t_{0})^{2}\right)=0$

We know that v, the propagation velocity cannot be zero. Therefore, we can say that

$(t_{a}-t_{0})^{2}-(t_{b}-t_{0})^{2}+(t_{c}-t_{0})^{2}-(t_{d}-t_{0})^{2}=0$

If we multiply out each square term above, then rearrange the equation, it yields the following expression for $t_{0}$, the first of our unknowns.

$t_{0}={\frac {1}{2}}\left({\frac {t_{a}^{2}-t_{b}^{2}+t_{c}^{2}-t_{d}^{2}}{t_{a}-t_{b}+t_{c}-t_{d}}}\right)$

N.B. There are some problems with this formula. Firstly, the denominator $t_{a}-t_{b}+t_{c}-t_{d}$ will be equal to zero for certain tapping points in the rectangle (e.g. the centre). Secondly, when the denominator is non-zero but small, the expression will be very sensitive to small errors in the time measurements. However, for the time being I'm not going to worry about these problems.

Since $t_{a},t_{b},t_{c}$ and $t_{d}$ are all known (i.e. they were detected directly from the accelerometer readings), we can now determine exactly how long before the first readings were detected the actual tap took place.

We define four new time variables, $\tau _{a},\tau _{b},\tau _{c}$ and $\tau _{d}$, which record the actual propagation time taken for the tap vibrations to travel from $p$ to each of the four corners.

$\tau _{a}=t_{a}-t_{0}$

$\tau _{b}=t_{b}-t_{0}$

$\tau _{c}=t_{c}-t_{0}$

$\tau _{d}=t_{d}-t_{0}$

Scale Replica Rectangle

We now construct a scale replica of the original rectangle using $\tau _{a},\tau _{b},\tau _{c},\tau _{d}$ in place of the lengths $a,b,c,d$. The width and height of our scale replica ($w_{s}$ and $h_{s}$ respectively) are not known initially, but by specifying the lengths of the four lines joining $p_{s}$ to each of the corners $A_{s},B_{s},C_{s},D_{s}$, they will be uniquely determined.

The four corners of our scale replica rectangle are

• $A_{s}$ is the bottom left corner, at coordinates $(0,0)$
• $B_{s}$ is the bottom right corner, at coordinates $(w_{s},0)$
• $C_{s}$ is the top right corner, at coordinates $(w_{s},h_{s})$
• $D_{s}$ is the top left corner, at coordinates $(0,h_{s})$

The relative proportions of $\tau _{a},\tau _{b},\tau _{c}$ and $\tau _{d}$ are exactly the same as those of $a,b,c$ and $d$. The point $p_{s}=(x_{s},y_{s})$ within our replica rectangle corresponds to $p$ within the original rectangle.

Applying Pythagoras' theorem again,

$\tau _{a}^{2}=x_{s}^{2}+y_{s}^{2}$

Therefore,

$y_{s}={\sqrt {\tau _{a}^{2}-x_{s}^{2}}}$

From the rectangle, we can also write these two equations:

$w_{s}=x_{s}+{\sqrt {\tau _{b}^{2}-y_{s}^{2}}}$

$h_{s}=y_{s}+{\sqrt {\tau _{d}^{2}-x_{s}^{2}}}$

Combining these two equations,

${\frac {x_{s}}{w_{s}}}-{\frac {y_{s}}{h_{s}}}+{\frac {\sqrt {\tau _{b}^{2}-y_{s}^{2}}}{w_{s}}}-{\frac {\sqrt {\tau _{d}^{2}-x_{s}^{2}}}{h_{s}}}=0$

Multiplying all terms by $h_{s}$ gives

${\frac {h_{s}}{w_{s}}}x_{s}-y_{s}+{\frac {h_{s}}{w_{s}}}{\sqrt {\tau _{b}^{2}-y_{s}^{2}}}-{\sqrt {\tau _{d}^{2}-x_{s}^{2}}}=0$

Since our replica rectangle has the same proportions as the original one, ${\frac {h_{s}}{w_{s}}}={\frac {h}{w}}$, we can write

${\frac {h}{w}}x_{s}-y_{s}+{\frac {h}{w}}{\sqrt {\tau _{b}^{2}-y_{s}^{2}}}-{\sqrt {\tau _{d}^{2}-x_{s}^{2}}}=0$

Now, substitute in the previous expression for $y_{s}$ in terms of $x_{s}$.

${\frac {h}{w}}x_{s}-{\sqrt {\tau _{a}^{2}-x_{s}^{2}}}+{\frac {h}{w}}{\sqrt {\tau _{b}^{2}-\tau _{a}^{2}+x_{s}^{2}}}-{\sqrt {\tau _{d}^{2}-x_{s}^{2}}}=0$

We should now be able to solve for $x_{s}$, the only unknown in the previous equation. However, I've spent quite a few hours trying to hammer out an expression for $x_{s}$ in terms of $\tau _{a},\tau _{b},\tau _{d},w$ and $h$ and I'm embarrassed to say that my efforts have been fruitless. Having been frustrated in my search for an elegant analytical solution, I've had to shelve my pride and settle for a numerical solution for the time being.

Numerical solution for $x_{s}$

Since we know that $x_{s}$ is real and positive (as are $\tau _{a},\tau _{b},\tau _{c},\tau _{d}$), we can immediately identify some bounds within which it must lie.

$x_{s}<\tau _{a}\,$

$x_{s}<\tau _{d}\,$

$x_{s}^{2}>\tau _{a}^{2}-\tau _{b}^{2}\quad {\mbox{for}}\quad \tau _{a}>\tau _{b}$

$x_{s}^{2}>0\quad {\mbox{for}}\quad \tau _{a}\leq \tau _{b}$

The first three of these conditions arise from the fact that if they are violated, square root terms in our equation will become imaginary (and we know $x_{s}$ must be real).

The value of $x_{s}$ can be estimated with arbitrary precision using the following iterative algorithm. First define a function $f(x)$.

$f(x_{s})={\frac {h}{w}}x_{s}-{\sqrt {\tau _{a}^{2}-x_{s}^{2}}}+{\frac {h}{w}}{\sqrt {\tau _{b}^{2}-\tau _{a}^{2}+x_{s}^{2}}}-{\sqrt {\tau _{d}^{2}-x_{s}^{2}}}$

The desired value of x_s is that for which $f(x_{s})=0$. We define variables $x_{min}$ and $x_{max}$ and assign them the following initial values:

$x_{min}=\left\{{\begin{array}{ll}{\sqrt {\tau _{a}^{2}-\tau _{b}^{2}}}&,\tau _{a}>\tau _{b}\\\\0&,\tau _{a}\leq \tau _{b}\end{array}}\right.$

$x_{max}=\min {\left(\tau _{a},\tau _{d}\right)}$

I'm making the assumption here that $f(x_{s})$ is monotonic on the interval $x_{min}<x_{s}<x_{max}$ (and hence that there is only one solution for $f(x_{s})=0$ in that interval). Based on my visual inspection of the geometry in this problem, the solution is unique. However, it would probably be advisable to revisit this to confirm that the assumption is valid.

Now, perform the following steps as many times as necessary.

1. Set $x_{s}={\frac {x_{min}+x_{max}}{2}}$
2. If $f(x_{s})\times f(x_{min})<0$ then set $x_{min}=x_{s}\,$. Otherwise, set $x_{max}=x_{s}\,$
3. If $x_{max}-x_{min}<\epsilon \,$ for some predefined tolerance $\epsilon \,$ then cease iterating and take the current value of $x_{s}\,$ as the final value. Otherwise, repeat from step 1 above.

What is happening here is that $x_{min}$ and $x_{max}$ begin on opposite sides of the zero-crossing point of $f(x_{s})$. Each iteration of the algorithm ratchets $x_{min}$ and $x_{max}$ closer to each other, but keeps the zero-crossing point in between them. At each iteration, the distance between $x_{min}$ and $x_{max}$ is reduced by half. After several iterations, there will only be a very short distance between $x_{min}$ and $x_{max}$ and the zero-crossing point is known to be somewhere in that very small range.

Finally, calculate $p=(x,y)$

Now, we have the value of $x_{s}$, the x-coordinate of the point we seek in the scale replica square. To find $y_{s}$, we simply use the following equation from above.

$y_{s}={\sqrt {\tau _{a}^{2}-x_{s}^{2}}}$

We also need to find out the width and height of the replica rectangle. For this, we can use the following equations from above.

$w_{s}=x_{s}+{\sqrt {\tau _{b}^{2}-y_{s}^{2}}}$

$h_{s}=y_{s}+{\sqrt {\tau _{d}^{2}-x_{s}^{2}}}$

Now that we know the values $x_{s},y_{s}$ and $w_{s},h_{s}$, we can easily find the actual point, $p$, at which the tap occurred in the original (unscaled) rectangle. Simply scale $(x_{s},y_{s})$ using the ratio of the dimensions of the replica rectangle to those of the original rectangle.

$x={\frac {w}{w_{s}}}x_{s}$

$y={\frac {w}{w_{s}}}y_{s}$

These are the coordinates of $p$, the point at which the tap occurred.

Summary of calculation

To recap, here is the sequence of calculations required to find $p=(x,p)$ when $t_{a},t_{b},t_{c},t_{d},w$ and $h$ are given.

First, find $t_{0}$:

$t_{0}={\frac {1}{2}}\left({\frac {t_{a}^{2}-t_{b}^{2}+t_{c}^{2}-t_{d}^{2}}{t_{a}-t_{b}+t_{c}-t_{d}}}\right)$

Next calculate $\tau _{a},\tau _{b},\tau _{c}$ and $\tau _{d}$:

$\tau _{a}=t_{a}-t_{0}$

$\tau _{b}=t_{b}-t_{0}$

$\tau _{c}=t_{c}-t_{0}$

$\tau _{d}=t_{d}-t_{0}$

Define the function $f(x_{s})$:

$f(x_{s})={\frac {h}{w}}x_{s}-{\sqrt {\tau _{a}^{2}-x_{s}^{2}}}+{\frac {h}{w}}{\sqrt {\tau _{b}^{2}-\tau _{a}^{2}+x_{s}^{2}}}-{\sqrt {\tau _{d}^{2}-x_{s}^{2}}}$

Calculate initial values for $x_{min}$ and $x_{max}$:

$x_{min}=\left\{{\begin{array}{ll}{\sqrt {\tau _{a}^{2}-\tau _{b}^{2}}}&,\tau _{a}>\tau _{b}\\\\0&,\tau _{a}\leq \tau _{b}\end{array}}\right.$

$x_{max}=\min {\left(\tau _{a},\tau _{d}\right)}$

Perform the following steps as many times as necessary.

1. Set $x_{s}={\frac {x_{min}+x_{max}}{2}}$
2. If $f(x_{s})\times f(x_{min})<0$ then set $x_{min}=x_{s}\,$. Otherwise, set $x_{max}=x_{s}\,$
3. If $x_{max}-x_{min}<\epsilon \,$ for some predefined tolerance $\epsilon \,$ then cease iterating and take the current value of $x_{s}\,$ as the final value. Otherwise, repeat from step 1 above.

Calculate $y_{s}$:

$y_{s}={\sqrt {\tau _{a}^{2}-x_{s}^{2}}}$

Calculate $w_{s}$:

$w_{s}=x_{s}+{\sqrt {\tau _{b}^{2}-y_{s}^{2}}}$

Finally, calculate $p=(x,y)$:

$x={\frac {w}{w_{s}}}x_{s}$

$y={\frac {w}{w_{s}}}y_{s}$