How to find the position of points given relative distances ?

Hi,

I have found the relative distances between 4 microphones using cross-correlation. The values are not very accurate because of measurement noise or other noise in the recordings. Given the distances, is it possible to find the approximate positions of the microphones using the first one as the reference (position [0 0]) ? The likely positions are on circles whose radius are the given distances. The relative distances follow. The distance estimates may be wrong, so I am more interested in knowing if the problem can be solved in general, that is if the measurements were correct. Some sort of grid search maybe ? For simplification I have assumed that the microphones are on the same level, that is a 2D problem.

from mic. 1 to mic. 2: -4.915(m)

from mic. 1 to mic. 3: 2.571(m)

from mic. 1 to mic. 4: -5.123(m)

from mic. 2 to mic. 3: 5.162(m)

from mic. 2 to mic. 4: -0.212(m)

from mic. 3 to mic. 4: -5(m) % this one is very uncertain

Thanks in advance.

[Ted Shultz]

This is called Multilateration. In particular TDOA (time difference of arrival). The Wikipedia page has a possible solution algorithm you may want to try.

[Adam Danz]

"Given the distances, is it possible to find the approximate positions of the microphones using the first one as the reference"

It depends. Given just the distances and a reference point of mic #1, it will not be possible to compute the position of the microphones in the world without more information. To illustrate, imagine rotating the microphone layout about the pivot point at mic #1 (0,0). The distance between the mics hasn't changed and the reference point hasn't change but the world-coordinates of the microphones have changed.

If we can assume the position of a second mic the problem is solved. For example, if the distance between mic 1 and mic 2 is 5 and we can assume mic 2 shares the same y coordinate as mic 1, it would be farily straightforward to compute the coordinates of the other mics.

Answer 1

[Adam Danz]

This solution computes the coordinates of each microphone relative to mic #1 with the following assumptions.

1. The position of mic #1 is a fixed reference point
2. Mic #1 and #2 share the same y coordinate.

The code creates a 'real' microphone layout (red squared below) and then computes the distances between each mic. These distances are the input used to calculate the mic positions which are plotted in blue x's to confirm accuracy. It computes the internal angle 'c' and 'e' from the image below to find the position of mic #3 and #4. See comments in code for more detail.

Caveats

• incorrect distances will give you incorrect results
• to get the actual world coordinates of the micophones relative to mic #1, you'd merely need to rotate the results but the angle of rotation is currently unknown given only distances.
• Notice that the distance betweed mic #2 and #4 is not used. You could use that distance to test accuracy by comparing it to the distance between your calculated mic #2 and #4 positions.

%% Real mic positions (this is not known; it will be used to compute distances)
xy = [0 0;          % mic 1; reference, always at (0,0)
    2 0;            % mic 2
    2.5 4;          % mic 3
    -.5 3.5];       % mic 4

% Compute distances between all mics (these distances will already be known)
micDists = squareform(pdist(xy)); % micDists(i,j) is dist between xy(i,:) and xy(j,:)

% View layout
figure();
plot(xy(:,1),xy(:,2), 'rs','MarkerSize', 12, 'LineWidth',2,'DisplayName','Actual position')
text(xy(:,1)+.1,xy(:,2),{'mic 1','mic 2','mic 3','mic 4'})
axis equal
grid on
hold on

%% Calculate the position of each mic given the distances and reference point
% Use the law of cosines [1] to ...
% ...compute the angle c (between the lines at mic 1,2 and mic 1,3)
a = micDists(1,2); %distance between mic 1,2
b = micDists(1,3); %distance between mic 1,3
c = micDists(2,3); %distance between mic 2,3
ang_c = acos((a^2 + b^2 - c^2)/(2*a*b)); %radians


%...compute the angle e (between the lines at mic 1,4 and mic 1,3)
d = micDists(1,4); %distance between mic 1,2
e = micDists(4,3); %distance between mic 1,3
ang_e = acos((b^2 + d^2 - e^2)/(2*b*d)); %radians

% Define mic position 1 
mic1Pos = [0,0]; 

% Compute position of mic #2 with the following 2 assumptions
% * it shares the same y coordinate as mic 1
% * it's to the right of mic 2 on the graph 
%   You can switch that the 'left' with minimal changes below. 
mic2Pos(1) = mic1Pos(1) + micDists(1,2); 
mic2Pos(2) = mic1Pos(2); 

% Compute position of mic #3 [2]
mic3Pos(1) = mic1Pos(1,1) + micDists(1,3) * cos(ang_c); 
mic3Pos(2) = mic1Pos(1,1) + micDists(1,3) * sin(ang_c); 

% Compute the position of mic #4 [3]
mic4Pos(1) = mic1Pos(1,1) + micDists(1,4) * cos(ang_c + ang_e); 
mic4Pos(2) = mic1Pos(1,1) + micDists(1,4) * sin(ang_c + ang_e); 

% plot results on top of previous plot
plot([mic1Pos(1),mic2Pos(1),mic3Pos(1),mic4Pos(1)], ...
    [mic1Pos(2),mic2Pos(2),mic3Pos(2),mic4Pos(2)], ...
    'bx','LineWidth',2,'DisplayName', 'Computed position')
legend()

%% Notes 
%[1]Law of cosines:  https://www.mathsisfun.com/algebra/trig-solving-sss-triangles.html
%[2] the angle needed in the 3rd term is the angle that pivots about mic #1 between the x axis and mic #3
%[3] the angle needed in the 3rd term is the angle that pivots about mic #1 between the x axis and mic #4

Result

[Kamran]

My goodnees. Thanks very much Adam. I'ld need some time to digest this. I'll come back to you when I've finished understanding your answer.

Just a question for now. Would the sign of the estimated distances help to better resolve the solution ? I mean the estimated distance between the 1st and the 2nd mic are negative, based on the cross-correlation analysis. That would mean that the source is closer to mic. 2 than mic. 1. I guess I am just trying to limit the solution space. Even if I cannot get a precise location, I could define zones of possible locations of the microphones.

Thanks again,

Kamran

[Adam Danz]

"Would the sign of the estimated distances help to better resolve the solution ?"

Yes, the sign of the distance (ie, + means above or to the right of mic 1) would eliminate the assumption that box #2 is to the right (or left) of box #1 and it would eliminate the assumption that the boxes are in order. I'd be glad to help if you have any questions after you've had time to understand the answer.

[Kamran]

Thanks very much for your offer. I think I understand what is happening in your code. Very much obliged. I was thinking of solving system of equations when I started the thread. Didn't even think that there is a more elegant way to do it.

Cheers,

kamran

[Adam Danz]

Glad I could help!

Answer 2

[Aaron T. Becker's Robot Swarm Lab]

Matlab has the function cmdscale for this type of problem.