A Distribution-Based Approach to Tracking Points in Velocity Vector Fields

People | Project Description | A Local Descriptor for Vector Fields | Vector Field Properties for Tracking Points | Vector Spin-Image Parameters

Results | Experimental Setup | Time Complexity | References

People

Project Description

We address the problem of tracking points in dense vector fields. Such vector fields may come from computational fluid dynamics simulations, environmental monitoring sensors,
or dense point tracking of video data. To track points in vector fields, we capture the distribution of higher-order properties (e.g., properties derived from the gradient of the velocity vector field) in a novel local descriptor called a vector spin-image. Our distribution-based approach has a number of advantages over methods that use topology analysis to track points in vector fields. The local distributions are robust to noise, adaptable to changes in the feature, and can be used to extrapolate the location of features after they have disappeared. We describe the vector spin-image data structure, the higher-order properties we record to track vector field points, and show results of tracking points in the simulated flow through a diesel engine cylinder.

A Local Descriptor for Vector Fields

In developing a local descriptor for vector fields, our goals are similar to those for surface points. The descriptor must be robust to noise, invariant to transformations, discriminating, and efficient to generate and compare. We apply concepts form shape contexts and spin-images to create a local descriptor for vector fields which we call a vector spin-image.

We compare the spin-image for surface data (left) to the vector spin-image (right). The spin-image is indexed by the distance α from the central point and the depth β from the central point's tangent plane. We define the vector spin-image indices as the distance α from the central pint and the dot-product β between the vector at the central point and that of the neighbor. We then bin (count) the number of neighbors (within a given radius around the central point) based on their α and β values, resulting in a 2D histogram. Because areas far from the central point are deemed less important in a local descriptor, we use a log scale for radius α to achieve lower resolution in these areas as prescribed in shape contexts[1]. In below-left equation, rmin is the radius of the bin containing the central point. rmax is the maximum support of the spin-image; and i goes from 0 to I where I+1 is the total number of radial bins (concentric rings). The below-right image illustrates the set of radius in a vector field.

Equarion 1

Vector Field Properties for Tracking Points

Vector orientation alone often cannot capture essential differences between vector fields such as the strength of the flow feature of a vortex or fixed point. Given two sinks of different strengths, our initial vector spin-image would not be able to distinguish between them. By storing vector magnitude in addition to orientation, we can discriminate between points in the two fields. But because both vector orientation and magnitude are zeroth-order properties, they fail for tracking fixed points. In below figure, all sigularites are found similar with the selected center point on vector orientation and vector magnitude. This is due to the fact that the vector field vanishes at fixed points, and the dot-product (vector orientation) between a zero-valued vector and any other vector will be the same regardless of the type of fixed point (i.e., sink, source, saddle, etc.).

self-similarity test
Vector Field
Vector Orientation
Vector Magnitude
pick a center point in the field

We found that some first-order properties based on the velocity gradient tensor enable us to overcome this limitation and distinguish between different fixed points. From [2], we know that for a point P, the velocity tensor is:

It can be decomposed by this way:

The first-order properties are:

, , , , .

Vector Spin-image Parameters

Now we have 7 properties: the 5 first-order properties plus the 2 zeroth-order properties. To incorporate the seven properties into an algorithm for tracking points through
dense vector fields, we must address the following issues: (1) selecting the appropriate range and resolution for vector spin-images to sufficiently capture the properties, (2) combining the different properties into a unified approach, and (3) updating and adapting vector spin-images as we track changing points through the vector field.

(1) For the flow field inside a diesel engine cylinder shown as blow figure, we can get 10 2D planar vector fields by cut the cylinder from top to bottom. The range of each property of each vector field is shown as the below table. In particular, dilation, rotation, and stretch strengths and tensor magnitude change dramatically from the top to the bottom.

Position of slice along engine cylinder range of vector direction range of vector magnitude range of strength of rotation range of strength of dilation range of strength of stretch range of direction of stretch range of Tensor Magnitude
10% [-1, 1] [0, 5.8839] [-31.8186, 60.2079] [-39.5980, 47.2219] [0, 62.6266] [-1, 1] [0, 87.3220]
20% [-1, 1] [0, 3.5721] [-20.1451, 38.4981] [-26.0022, 26.9086] [0, 42.5276] [-1, 1] [0, 59.2650]
30% [-1, 1] [0, 2.7673] [-12.8981, 35.6685] [-25.1324, 24.6326] [0, 37.2668] [-1, 1] [0, 51.7284]
40% [-1, 1] [0, 2.0657] [-15.2411, 28.8230] [-22.5314, 22.7302] [0, 31.2475] [-1, 1] [0, 43.0416]
50% [-1, 1] [0, 1.5851] [-13.9184, 22.2907] [-18.0417, 18.0296] [0, 24.2587] [-1, 1] [0, 33.4091]
60% [-1, 1] [0, 1.2120] [-10.7470, 16.5160] [-13.5284, 13.4903] [0, 18.1427] [-1, 1] [0, 24.9622]
70% [-1, 1] [0, 0.9149] [ -6.0537, 12.2564] [ -9.8581,  9.8679] [0, 13.4417] [-1, 1] [0, 18.4787]
80% [-1, 1] [0, 0.6808] [ -3.9423,  8.8158] [ -6.9598,  7.0467] [0,  9.6562] [-1, 1] [0, 13.2572]
90% [-1, 1] [0, 0.5078] [- 1.9439,  6.1132] [- 4.7034,  4.8752] [0,  6.6815] [-1, 1] [0,  9.1580]
100% [-1, 1] [0, 0.3872] [- 1.2977,  4.1206] [- 3.0410,  3.2730] [0,  4.4800] [-1, 1] [0,  6.1340]

To maintain a reasonable number of bins while achieving descriptive distributions, we apply the following strategies: (1) each spin-image in a 2D slice covers only the range of
values within the slice rather than defining a global range that covers the entire range of values throughout the dataset; (2) we normalize the range of values to be between 0 and 1 for all positive-valued properties (e.g., magnitude) and between -1 and 1 for all others; and (3) we use the log scale given by Equation 1 to bin vector field properties. In general,
we have found a bin resolution of 10 for distance and 20 for all other properties to be sufficient (total of 200 bins).

(2) The seven properties described in Section 4 can be combined into a single vector spin-image of seven dimensions discretized into 20 bins per property (10 for distance). With
7 properties, such a distribution would contain 207*10 bins for a total of 12.8 billion bins. Computing, storing, and comparing these high-dimensional vector spin-images would be considerably expensive and wasteful in that there will be many bins with zero or near zero values. Instead, we leverage the additive nature of the difference function. We compute the ¦Ö2 differences between the distributions for each property and combine them into one total difference value:

For 7 properties, k=7. By treating the vector field properties separately, we can weigh some properties more than others via wj in the equation above. We have found that
weighing vector orientation by 0.7 and the remaining properties equally by 0.05 effectively tracks both fixed and regular points.

(3) A key advantage of distribution-based tracking is the ability to adapt as the feature changes. For example, if a selected fixed point disappears, we can extrapolate its position
afterwards. To ensure that the vector spin-image for a selected point adapts as the vector field evolves from one slice to the next, we update the range of vector field properties
and average the vector spin-images that have a difference of 1% or less with respect to the query spin-image.

Results

Please download the video(7MB) to see the tracking results.

Experimental Setup

Hardware: Genuine Intel T2050 CPU 1.60GHz, 1GB of RAM

Software: We use Visual Studio .net 2003 to implement the algorithm, Matlab to plot the distributions and Χ² statistics distance.

Time Complexity

Computing and comparing vector spin-images is linearly dependent on the number of bins (determined by the range and resolution of each property). We have found a bin resolution of 10 for distance and 20 for all other properties to be sufficient. The average time to compare the vector spin-images of a single point to all other vector spin-images in a slice (9,659 pairs of points compared) is 0.5 secs.

References

[1] A.Frome, D.Huber, R.Kolluri, T.Bulow, and J.Malik. Recognizing objects in range data using regional point descriptors. Proc. of European Conf. on Computer Vision (ECCV), 3:224-237, 2004.

[2] E. Zhang, H. Y. Z. Lin, and R. Laramee. Asymmetric tensor analysis for flow visualization. IEEE Transactions on Visualization and Computer Graphics (TVCG), 5(1):106¨C122,
2009.

Updated March 28, 2009