-This article presents efficient algorithm to calculate Hausdorff distance metric and heuristic algorithm
that maximizes amount of intersecting points in two point sets very quickly. Performance and precision research of those algorithms is presented. It is shown that algorithm is applicable for real time position tracking using “Kinect” device.
INTRODUCTION
“Kinect” sensor is a motion tracking device presented by
“Microsoft”. It is one of the most popular motion tracking
devices used at home. “Kinect’s” application programmable
interface presents external applications with current human
position [
with information about human body parts.
Therefore, it is applicable when information about separate
body parts is needed. However, it is shown by some researches
[
Specialized algorithms are needed to process data from other data streams and compare them to a template. All data streams present the user with large amount of data compared to preprocessed skeleton stream. Thus, they require efficient algorithms to process them if real time or near real time tracking is required.
The easiest and simplest to process data stream is body
index stream. If only one human is tracked this stream is easily
deduced to a binary matrix where 1 represents a pixel that
belongs to human body, 0 – that is does not. Hausdorff distance
metric is a good metric for this kind of data [
= { 1, 2, … , } are finite sets of points. Then Hausdorff distance is defined as follows: ( , ) = max(ℎ( , ), ℎ( , )), kur ℎ( , ) = max min‖ − ‖ ∈ ∈ (1) (2)
Here ‖ − ‖ could be any distance metric between points and , e, g., Euclidean norm or 2 norm. Semantically this metric shows the distance to the most distance point from the other set corresponding to a chosen distance metric.
Looking at (2) formula it is trivial to see that direct calculation of the metric has computational complexity of (
) because all points of both sets must be compared. If ≈ , complexity approaches to ( 2) and is not applicable for real time use.
II.
HAUSDORFF DISTANCE CALCULATION METHODS
Yanir Taflev presents an open source solution to compute
metric [
Hausdorff distance is then equal to the maximum value of both distance matrices.
Hausdorff distance matrix is calculated by constructing initial matrix first. A value of 0 is assigned to every point of set and
∞ for all other points. For all points of set the matrix is traversed in squares of increasing size and a value of square edge length is assigned if the value of that point is not less that the length of square edge. Chebyshev distance is computed because of such matrix construction.
Algorithm is implemented in C# language and is used in
C# framework “Shape Matching Framework”.
“ElasticSearch” client created by “Vivid Solutions” is an
open source Java project [
The computed distance is approximate. The algorithm is not given by “Vivid Solutions”. The implementation is used to compare geometries in “Elastic
Princeton University’s resolving library “RgResolve” uses
Hausdorff algorithm’s Java implementation [
The distance is calculated using Euclidean norm. result of the algorithm must not depend on where the human is standing. A transformation of human’s silhouette is needed before computing Hausdorff distance. It must move the silhouette to the position where it would intersect with the template the most. distance calculation algorithm:
These requirements must be met by efficient Hausdorff
Execution time is close to 30 ms with “Kinect’s” body index stream data Algorithm must find an optimal linear transformation that makes the template and user’s silhouette be oriented in such a way that the amount of intersecting points is maximum and the Hausdorff distance is minimum
Say that we have two finite sets of points =
= { 1, 2, . . , }. Let us assume that the human will be oriented vertically in the frame, i.e., the normal vector of the base that the user is standing on is vertical. This assumption eliminates the need of rotation transformation. Two linear transformations need to be made: scale and shift. Say that the center point of set is . The shape will be scaled using this point as the center. Say that optimal scale coefficient is , optimal shift transformation vector - ⃗. Then the transformed point set is = { 1, 2, … , } = ( 2− +⃗) , … , + ( − +⃗)
cardinality function ( , ) = | ∩ | = + ( − + − )
If silhouettes of template and human belong to the same sequence of movement, we can assume that these transformation parameters will stay constant during the process of matching. Thus, they can be calculated in the beginning and used later. This should speed up the tracking even more. Then = 1 − 1 = ℎ2 ℎ1 = + ( − + ) (8) (9) (10) (11)
Proposed Hausdorff distance calculation algorithm Proposed algorithm is based on Yanir Taflev’s ideas, but is better optimized for speed. The use of this algorithm eliminates the need to convert data from two-dimensional matrix to other formats, e.g., a list of points. Chebyshev distance is used as distance metric. Firstly, a two-dimensional matrix is set up. All points with coordinates that belong to the silhouette are set to 0, others – with ∞. A point queue is constructed. Initially it consists of all points that belong to the silhouette. A point is taken from the queue and 8 surrounding equidistant points are analyzed. The distance from the original points to those surrounding points is always 1, so the distance from the other silhouette to those points cannot be larger than the original point’s distance increased by one. If this value is less than already computed value for this point, this value is updated and the point is added to the queue. Distance is calculated for all points this way. All points that do not belong to the other set are then removed because they do not contribute to Hausdorff distance. Elements of this matrix show the differences between the silhouettes. Two such matrices must be calculated, so the computation of them can be made parallel – their computation is independent.
To reduce the amount of calculation matrix edges without silhouette points are cut. The resulting cut matrix is minimum rectangle matrix that contains all the points that belong to silhouette.
Common maximum of both matrices is Hausdorff distance. Algorithm pseudocode is given below.
matrices ← template matrix and user matrix
find common left upper corner of matrices
find common right lower corner of matrices
∀ matrix ∈ matrixes
do initialize queue and ret
while queue ≠ ø
do p ← take from queue
val ← get p value from ret
val ← val + 1
ret ← min(r, val) ∀adjacent point
r to p
opposing matrix to 0
max(res2))
set
points
of
res
that
do
not
belong
to
hausdorff distance = max(max(res[
Precise calculation of such function is computationally intensive, so heuristic algorithm is used instead.
A fast and quite accurate heuristic for scale transformation is to compute scale coefficient as the ratio of heights of the two shapes. If template and user are in similar positions, e.g., both are standing, both silhouettes could be made the same height. Then = ℎ , where ℎ
METHOD OF RESEARCH
Two properties of the algorithm are evaluated: performance and precision.
To evaluate performance different types of frames are set up. The frames differ in size and distance between silhouettes. Used frame sizes are 10% to 300% “Kinect’s” frame size in steps of 10%. For each frame size, real human silhouette is analyzed. Performance is measured when the human and the template are in similar parts and in opposite parts of the frames. Performance is compared to other existing algorithms’ performance. Each measure is run 10 times and execution time average is found. Three modifications of the proposed algorithm are measured – Hausdorff distance only, Hausdorff distance with transformation and Hausdorff distance with cached transformation parameters. Algorithm should work in less than 30 ms, i.e., faster than “Kinect’ produces frames.
To evaluate precision different real human silhouettes are used. Best possible transformation is found using brute force algorithm, Hausdorff distance is calculated using the optimal transformation, then Hausdorff distance is found using the transformation calculated using proposed algorithm and the error is evaluated.
V.
RESEARCH RESULTS
Execution times of all algorithms and all frame sizes are shown in figure 1. Same silhouettes were used, but scaled. Silhouettes were around a third of the frame apart.
Unit value in diagrams represents algorithm with cached transformation performance when frame size is equal to “Kinect’s” frame size. This time is 26 ms for distant silhouettes and 21 ms for close silhouettes on “Intel i7-3770K” processor (3.5 GHz). Maximum acceptable value on those scales are 1.15 for distant silhouettes and 1.43 for close silhouettes. These values are hardware-dependent and presented for approximate evaluation. The processor used is a little more powerful than “Kinect’s” system requirements (i7 series processor, 3.1 GHz clock frequency).
Algorithm performance comparison, distant silhouettes 14
The diagram reveals that “Elastic Search” algorithm is the slowest, “RgResolve” – better, Y. Taflev’s algorithm would be applicable up to frame size of 0.6 “Kinect 2” frame size. This is close to “Kinect 1” frame size. Performance of proposed algorithm varies and no clear dependency is visible, but execution times slowly increase with increasing frame size. It could be caused by parallel nature of the algorithm. Threads are spawned by the runtime and operating system and determination of their performance could be difficult to predict. Nevertheless, frame sizes of around 1.3 “Kinect’s” frame size and smaller are processed faster than in 1.15 relative units and 1.7 and less – in 2 relative units.
Figure 2 shows the result of similar measurements, but the distance between the silhouettes was minimized. Other algorithms had little to no impact because of this change, but proposed algorithm performed better under those conditions. 1.5 relative units is reached at around 1.4-1.5 “Kinect’s” frame size, 2.5 – at around 1.8-2 times larger frames than “Kinect’s”. At round 3 “Kinect’s” frame sizes performance increase is around 1.5 times compared to distant silhouette test.
Algorithm performance comparison, close silhouettes 0,1 0,3 0,5 0,7 0,9 1,1 1,3 1,5 1,7 1,9 2,1 2,3 2,5 2,7 2,9
Frame edge size in Kinect's frames Yanir Taflev Proposed algorithm Proposed algorithm with calculated transformation Proposed algorithm with cached transformation RgResolve
ElasticSearch Algorithm precision was tested using different human silhouettes. Average error was 3.8%, minimum error – 0% (exact result), maximum error – 15.5%, median error – 2.7%. Data set size – 21 silhouettes.
VI.
CONCLUSIONS
The proposed algorithm performs faster than existing open source alternatives to calculate Hausdorff distance, but high variation of execution speed is observed because of parallelism involved in the calculations. Despite that, the algorithm in the worst case works faster than in 30 ms with “Kinect 2” recommended hardware, therefore it is applicable for human motion tracking using “Kinect” sensors. Proposed algorithm is precise if applied for human motion tracking and proposed heuristic is worth applying, because it adds little to execution times and precision loss is low.
Proposed algorithm works faster with silhouettes in the same part of frame than distant silhouettes. If this algorithm is applied for human motion tracking and recommended transformations are applied, this will always be the case and comparison will always be fast.
Algorithm is well suited for human position tracking when the human does not change his position relative to sensor, only his pose changes, or the human moves together with the template silhouette. In this case proposed heuristics work well and near-precise value of minimum Hausdorff distance with Chebyshev metric is found in short time.