by BCMDS

Applications using microphone arrays, such as acoustic localization, generally require the locations of the microphones to be known. If these positions are not known when the array is constructed (e.g., a rectangular grid), then the locations must be determined, a problem known as position calibration. We have developed a rather simple technique for position calibration based upon the idea of multidimensional scaling.

Classical multidimensional scaling (MDS) is an algorithm for determining the
Euclidean coordinates of points, given only their interpoint distances.
For example, using the driving distances between cities given in a road atlas,
one can construct a map of the region, as shown below. Although the
driving distance is a rough approximation of the actual distance, the resulting
map is accurate because the algorithm computes a least-squares solution.

Classical MDS requires N^{2} measurements, where N is the number of
points (cities, microphones, etc.) whose coordinates are being estimated.
With a large number of points, it becomes increasingly difficult to obtain the
measurements necessary for running classical MDS. In such a scenario, it
is advantageous to take advantage of the redundancy in the squared-distance matrix to reduce the
number of measurements needed. By selecting a small number of the points
as basis points, one can estimate all the interpoint distances from only the
distance of each point to the basis points, a tremendous savings in the number
of measurements required, which are now linear in the number of points instead
of quadratic, as shown below.

The technique, which we call Basis-Point Classical MDS (BCMDS), is based on the
work of Young and Cliff, 1972. They showed that, in a P-dimensional space,
only P+1 basis points are necessary in order to estimate all the N(N-1)/2
interpoint distances necessary for classical MDS. Assuming that the basis
points are a subset of the microphones, then we need to measure just the
P(P+1)/2 distances between the basis points themselves, along with the
(P+1)(N-P-1) distances between each non-basis-point and each basis point.
The difference between classical MDS and BCMDS is illustrated below, with the
four microphones on the left being used as the basis points.

Classical MDS | BCMDS |

BCMDS is not only useful for large microphone arrays, in which it is
impractical to measure all the N^{2} interpoint distances, but it also
enables MDS to be used with a calibration target. In such a case four
speakers are placed on the calibration target, and their relative positions to
one another are computed using either classical MDS or some other technique.
Then each of the speakers, in turn, emits a known sound, and the distances
between the speaker and all the microphones iare computed by cross-correlating
the received signals with the known signal. The technique requires all the
microphones to be synchronized with one another and with the speakers.

BCMDS has been shown, through extensive simulations, to be capable of achieving accuracy on the order of 1 cm in everyday indoor environments. Details of the simulations and the algorithm can be found in the publications below.

- S. T. Birchfield and A. Subramanya,
**Microphone Array Position Calibration by Basis-Point Classical Multidimensional Scaling**,*IEEE Transactions on Speech and Audio Processing*, 13(5):1025-1034, September 2005 - A. Subramanya and S. T. Birchfield,
**Extension and Evaluation of MDS for Geometric Microphone Array Calibration**,*Proceedings of the 12th European Signal Processing Conference (EUSIPCO)*, Vienna, Austria, September 2004 - S. T. Birchfield,
**Geometric Microphone Array Calibration by Multidimensional Scaling**,*Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP)*, Hong Kong, April 2003