Keywords

1 Introduction

Feature extraction is an important way to visualize flow fields in scientific computing. Feature visualization obtains meaningful structures from data fields, overcoming the disadvantages of traditional visualization methods. For 2D flow fields, topology analysis [1] is a traditional visualization based on feature extraction. Most methods based on topology analysis [2–4] work well in 2D feature extraction, but can not be simply extended to 3D flow fields. For example, the vortex core line reported in [5] can not be detected by topology analysis.

With such problems, methods based on Clifford algebra were developed to detect flow features [6], where multi-vector filter masks are predefined and used to convolve with the underlying flow fields to determine features. The main drawback of these methods is the heavy convolution, because it has to be applied on the whole field. Although Hitzer et al. [7] proposed the Clifford Fourier transformation to accelerate it, there is still an overhead to be cut down.

On the other hand, information theory was applied to measuring the complexity of streamlines [8]. And an information-theoretic framework was proposed and used for flow visualization [9–11]. With the information theory, flow field complexity can be measured with flow field entropy. The more complicated the areas are, the higher the entropy values are. This gives us some kinds of information about the structures in the underlying field.

With the motivation to make feature extraction easier, we propose a new method to extract features for 3D flow fields. In this method, we first compute the entropy of the flow field according to information theory, and then choose high entropy regions to do the Clifford convolution with multi-vector filter masks. Finally, features are determined on the convolution results. This method integrates information computing into flow field Clifford convolution, and increases the efficiency of feature extraction by avoiding most of unnecessary convolutions.

The remainder of this paper is organized as follows. Section 2 briefly reviews the related work. Section 3 gives our approach, including some basics about Clifford algebra and flow field entropy. Test results are included in Sect. 4. The final is the conclusions.

2 Related Work

In flow visualization, feature extraction is often used to simplify and visualize flow fields in large scale. And many methods have been proposed for flow feature extraction. Here, we only briefly review the work directly related to our method.

Based on the scalar product between two arbitrary vectors, Heiberg et al. [12] defined a scalar convolution on flow vector fields, and presented a template matching method to extract features in vector fields. It can detect most of flow features, for example, vortices, swirling flow, diverging, converging, etc. In [6], Ebling and Scheuermann proposed a pattern matching method based on Clifford convolution. This method can detect flow features, but its computation is heavy. In [7], Hitzer extended Fourier transform to Clifford algebra and got the accelerated Clifford convolution.

On the other hand, information theory was introduced for flow visualization. Chen and Jäenicke [8] presented an information-theoretic framework for flow feature analysis and visualization. Wang et al. [9] presented a block-wise technique to analyze the important aspect of time-varying data. In [10], Furuya and Itoh applied information theory to measure the complexity of existing streamlines based on the distribution of the tangent orientations. In [11], Xu et al. gave an information-theoretic framework for flow visualization, where the information of vector fields is measured by Shannon’s entropy. In [13], Tao et al. proposed an information-theoretic framework, which applied dual information channels to solve streamline selection and viewpoint selection problems in flow visualization.

3 Our Approach

3.1 Overview

In this paper, we propose a feature extract method for 3D flow fields. This method shares the framework of pattern matching that is based on Clifford convolution, but includes a processing of region selection that is guided by flow field entropy. In the traditional pattern matching, convolution operator has to be applied on the whole input field. For some regions, however, there is no need to do convolution, since no meaningful features are contained in them. In order to reduce redundant overhead, we calculate the flow field entropy firstly, and then restrict the flow field convolution to regions with high entropy values. By this means, we can identify flow patterns and features precisely and efficiently. As a whole, our method works as followed.

  1. (1)

    Initially, the input flow field is normalized and converted to a multi-vector field.

  2. (2)

    Multi-vector filter masks are prepared for different flow patterns and features.

  3. (3)

    Calculate the flow field entropy according to the information theory of flow field, and get the entropy field of the input field.

  4. (4)

    Find out all local maxima in the entropy field, and put them into the candidates of potential feature points.

  5. (5)

    For each candidate points, do the pattern matching using predefined multi-vector filter masks in the framework of Clifford convolution. If the neighborhood region of the candidate point matches with one mask, it is then recognized as a feature with the corresponding pattern.

  6. (6)

    All flow patterns and features obtained in previous step are visualized with streamlines.

To help the understanding of our method, some concepts and processes are further described in the following subsections.

3.2 Vector Field Clifford Convolution

Convolution operator is usually applied to scalar fields. If X is a scalar field and Y is a scalar-value filter, the convolution between X and Y is defined as:

$$ S_{n} (r) = \int {\int {\int { < X_{n} (\xi ),Y(r - \xi ) > d\xi } } } $$
(1)

Ebling and Scheuermann [6] extended the convolution operator to vector field by using the geometric product of multi-vectors given in the Clifford algebra framework [14]. In the Clifford algebra, there are 8 basis blades, \( \{ 1,e_{1} ,e_{2} ,e_{3} ,e_{1} e_{2} ,e_{1} e_{3} ,e_{2} e_{3} ,e_{1} e_{2} e_{3} \} \), which form an eight-dimensional algebra space whose bases are in fact 3D vectors. The general elements in this algebra are called multi-vectors. A multi-vector of an n-dimensional Clifford algebra is a linear combination with real coefficients of the \( 2^{n} \) basis blades. The rule of multiplication operator is defined by the following equations:

$$ 1e_{j} = e_{j} ,\quad j = 1,2,3 $$
(2)
$$ e_{j} e_{j} = 1,\quad j = 1,2,3 $$
(3)
$$ e_{j} e_{k} = - e_{k} e_{j} ,\quad j,k = 1,2,3,j \ne k $$
(4)
$$ (e_{1} e_{2} e_{3} )^{2} = e_{1} e_{2} e_{3} e_{1} e_{2} e_{3} = e_{1} e_{1} e_{2} e_{3} e_{2} e_{3} = - e_{2} e_{2} e_{3} e_{3} = - 1 $$
(5)

The multiplication of two vectors a and b can be written as:

$$ \begin{aligned} {\mathbf{ab}} & = (a_{1} e_{1} + a_{2} e_{2} + a_{3} e_{3} )(b_{1} e_{1} + b_{2} e_{2} + b_{3} e_{3} ) \\ & = (a_{1} b_{1} + a_{2} b_{2} + a_{3} b_{3} ) + (a_{1} b_{2} - a_{2} b_{1} )e_{1} e_{2} \\ & \quad + (a_{2} b_{3} - a_{3} b_{2} )e_{2} e_{3} + (a_{3} b_{1} - a_{1} b_{3} )e_{3} e_{1} \\ & = < {\mathbf{a}},{\mathbf{b}} > + {\mathbf{a}} \wedge {\mathbf{b}} \\ \end{aligned} $$
(6)

The Clifford multiplication is in fact a convolution of a point in the vector field with a 1 × 1 filter mask. Therefore, if X is a 3D multi-vector filter mask and Y is a 3D multi-vector field, then the discrete convolution between X and Y can be defined as:

$$ C(j,k,l) = \sum\nolimits_{p = - m}^{m} {\sum\nolimits_{q = - m}^{m} {\sum\nolimits_{r = - m}^{m} {X(p,q,r)Y(j - p,k - q,l - r)} } } $$
(7)

where \( j,k,l,p,q,r \) are coordinates of grid nodes, m is the dimension of the grid of the filter mask and \( (j,k,l),(p,q,r) \) are grid nodes.

Given a filter mask with fixed direction, it will not match all the kind of the corresponding features in different directions. So we have to rotate the filter mask in a great deal of directions, which will cost too much computation time. As we can see in Eq. (6), however, \( < {\mathbf{a}},{\mathbf{b}} > \) is the inner product, and \( {\mathbf{a}} \wedge {\mathbf{b}} \) is the outer product of the two vectors. So their multiplication gives us the sine and cosine of the angle between two vectors as follow:

$$ < {\mathbf{ab}} >_{0} = < {\mathbf{a}},{\mathbf{b}} > = \left\| {\mathbf{a}} \right\|\left\| {\mathbf{b}} \right\|\cos\alpha $$
(8)
$$ \left\| { < {\mathbf{ab}} >_{2} } \right\| = \left\| {{\mathbf{a}} \wedge {\mathbf{b}}} \right\| = \left\| {\mathbf{a}} \right\|\left\| {\mathbf{b}} \right\|\sin \alpha $$
(9)

where α is the angle between a and b. Therefore, when we get the discrete convolution between X and Y as shown in Eq. (7), we can estimate the angle between X and Yfrom the following equations:

$$ < C(j,k,l) >_{0} \approx \eta \cos \alpha $$
(10)
$$ < C(j,k,l) >_{2} \approx \eta \sin \alpha $$
(11)

where \( \eta = \sum\nolimits_{p,q,r} {| X(p,q,r) | \le \sum\nolimits_{p,q,r} 1 } \), \( | X(p,q,r) | \) is the magnitude of vector \( X(p,q,r) \). With the estimated angle, we can directly rotate the filter mask to the desired direction, and do the Clifford convolution to detect features, avoiding checking all possible directions.

3.3 Flow Field Information Entropy

In our method, we introduce information entropy theory to reduce the calculation of Clifford convolution. Information theory provides a theoretical framework to quantitatively measure the information contained in a distribution of data values. In flow fields, flow directions around flow features are often in a high degree of variation, and then have high entropy values.

Given a random variable \( X \) with a sequence of possible values \( \{ x_{1} ,x_{2} , \ldots ,x_{n} \} \), if the probability for \( X \) to have the value x i is p(x i ), then the information content for the random variable X can be computed using Shannon’s entropy:

$$ H(x) = - \sum\nolimits_{{x_{i} }} {p(x_{i} )\log_{2} p(x_{i} )} $$
(12)

Xu et al. [11] took Shannon’s entropy to compute the information of a vector field, where a map is created to approximate the probability mass function \( p(x) \). For 3D vector fields in our consideration, a unit sphere is firstly divided into 642 uniform bins by the icosahedrons subdivision method [15]. Then a map is built from vectors to bins. With the map, the probability of the vectors in the bin \( x_{i} \) can be defined as:

$$ p(x_{i} ) = \frac{{C(x_{i} )}}{{\sum\nolimits_{i = 1}^{n} {C(x_{i} )} }} $$
(13)

where C(x i ) is the number of vectors in the bin x i . With the probabilities calculated here, we can get the flow field entropy according to the Eq. (12).

In practice, the flow field entropy is calculated in local regions. Given a grid point, a local neighborhood around the point, whose sizes are 3 × 3 × 3, is used to build the map and get the estimated probability. By this means, we can get a scalar field which is called entropy field. The value in the entropy field shows the degree of vector variation in its neighborhood. Such a 2D example is given in Fig. 1, where regions with higher degree of variation have higher entropy values, and they are considered to contain more information than others. The entropy \( H(x) \) is convex and reaches its maximum when p(x i ) is equal for all \( x_{i} \). We use this property of entropy field to reduce the overhead of Clifford convolution.

Fig. 1.
figure 1

Example of entropy field for a vector field (a) is the vector field visualized by streamlines, and (b) is its the entropy field, where warmer colors indicate higher entropy values.

Full size image

3.4 Multi-vector Filter Masks

Multi-vector filter masks can be regarded as very small vector fields, each of which contains a kind of flow patterns that is defined by the vectors. With predefined filter masks, we can detect the desired features through pattern matching. For 3D flow fields, interesting features [16] include as vortices, critical points, convergence, divergence, etc. We can design a representative filter masks for each of them. Two example masks are shown in Fig. 2. Due to the length limitation, other masks are not included in this paper.

Fig. 2.
figure 2

Examples of multi-vector filter masks (a) is for sink point, (b) is for saddle point.

Full size image

4 Test Results

To evaluate the performance of our feature extraction method, we compared it with the topology-based method [17] where feature points are located by flow field interpolation.

Firstly, the flow field shown in Fig. 3(a) was used to test the method. This is a vortex field with a core line. Due to the fact that no critical point exists in this field, the topology-based method can not find out the core line, which is the important feature of this field. For our method, it found the feature point as shown in Fig. 3(b). When a few streamlines associated with the feature point were rendered, we got the results in Fig. 3(c), where we can notice a straight line through the feature point. This line is the vortex core line.

Fig. 3.
figure 3

Test results for the flow field with a vortex core line (a) is the flow field shown by streamlines, (b) is the feature point found by our method, and (c) is the flow pattern around the feature point, where the vortex core line is disclosed.

Full size image

For general flow fields, both our method and the topological method can find the same features, but our method is general faster than the later. For example, for the flow field in Fig. 4(a), it cost 926 ms for the topological method to find out the feature point shown in Fig. 4(b), while it was only 208 ms for our method. The flow pattern around the feature point was clearly disclosed by streamlines in Fig. 4(c).

Fig. 4.
figure 4

Test results for a simple flow filed (a) is the original field, (b) is the feature point in the field, and (c) is the flow pattern around the feature point.

Full size image

Figure 5 gives another test results for a complex flow field. This field was generally visualized by streamlines in Fig. 5(a), where it is hard to capture the flow pattern. For this field, our method got the feature points shown in Fig. 5(b), and further built the flow patterns in Fig. 5(c) with a few streamlines.

Fig. 5.
figure 5

Test results for the complex flow field (a) is the original field, (b) is the feature points, and (c) is the flow patterns built with feature points and a few streamlines.

Full size image

5 Conclusions

We present a new method in this paper to extract features in 3D flow fields. The main advantage of our method is that it can extract various types of flow features in a unified and efficiency way. Our method is based on the Clifford algebra convolution, but it reduces the cost of convolution by the computing of flow field entropy. Test results show that our method improves the extraction of flow features. Currently our method is only suitable for flow fields defined on rectangular grids. It would be extended to arbitrary grids in future.