The implementation of the Ridge Combo plugin was the core task of my BSc. thesis titled "Development of a Ridge based Distance Measure on Scalar Fields". It's purpose was loading, processing and visualizing 3D scalar data by generating ridge surfaces and then applying the developed distance measure. The following paragraphs offer a short introduction to the topic along with selected algorithmic details. Additionally you can download the complete ▷thesis (currently available in german only) and/or the actual ▷plugin for your ParaView installation (requires version 3.4.1). Follow the links to get more information.
Here is the theoretical background for ridge surfaces in a nutshell. Let's assume the given 3-dimensional scalar field is a continuous function. That means we can take a look at the second derivatives (Hessian \(H\)) to determine the curvatures in each direction at a specific point. A point \(x\) belongs to the ridge surface \(R\) if the directional derivative in the direction of the smallest eigenvector \(v_1\) of \(H\) equals zero. Aditionally, the eigenvalue corresponding to \(v_1\) has to be negative to assure maximum concavity.
| \(v_{1}g(x)=0\) | (1) |
| \(\lambda_{1}<0\) | (2) |
The ridge surface is equivalent to the zero-level isocontour defined by (1) and can be generated by simply applying a marching cubes algorithm to the field, followed by filtering vertices according to (2). In order to obtain better results in the actual implementation, (1) should be replaced by the following equation which produces the same field but ensures the continuity of eigenvectors.
| \(det(H^{0}g|H^{1}g|H^{2}g)=0\) | (3) |
The following normal distribution function might help you generating random scalar fields. Here \((m_X,m_Y,m_Z)\) are the center coordinates of a smooth (without infinity at its center) Metaball. Just place an arbitrary number of Metaballs in your simulation cube and assign to each voxel the sum of all Metaball distance values (you may right click to find an option to zoom in).
| \(m(X,Y,Z)=\frac{1}{(\sqrt{2\pi}\sigma)^{3}} e^{-\frac{(X-m_{X})^{2}+(Y-m_{Y})^{2}+(Z-m_{Z})^{2}}{2\sigma^{2}}}\) | (4) |
These figures show several Metaball based scalar fields represented by a set of evenly spaced isocontours. Note, that this representation has nothing to do with ridge surfaces yet.
The following distance functions are needed to define the ridge metric. The first one is the quadratic distance between two points.
| \(d_{E}^{2}(p_{1},p_{2})=(p_{1}-p_{2})^{2}\) | (5) |
Similarly the quadratic difference between two weights (\(\lambda_1\)).
| \(d_{L}^{2}(l_{1},l_{2})=(l_{1}-l_{2})^{2}\) | (6) |
And finally the relevance function of two weights. This means if the arithmetic mean of two weights is close to zero the corresponding points should not influence the ridge metric because they are considered irrelevant.
| \(m_{L}(l_{1},l_{2})=-\frac{1}{2}(l_{1}+l_{2})\) | (7) |
To measure the error between a point and its weight to a target ridge surface the following equation must be minimized. The idea is similar to the Hausdorff distance with a new definition of distance being a composition of (5), (6) and (7) (in the ridge metric sense).
| \(d_{e}(p_{1},l_{1},R_{2})=min\left[(d_{E}^{2}(p_{1},p_{2})+d_{L}^{2}(l_{1},l_{2}))\cdot m_{L}(l_{1},l_{2})\right].\) | (8) |
| \((p_{2},l_{2})\in R_{2}\) |
Equation (8) can now be used to calculate the one sided distance between two ridge surfaces. This is done by applying it to all points of \(R_1\).
| \(d_{r}(R_{1}, R_{2}) = \frac{1}{M_{1}}\sum\limits_{(p_{1},l_{1})\in R_{1}} d_{e}(p_{1}, l_{1}, R_{2})\) | (9) |
Finally the result needs to be divided by the sum of the relevance of all point pairs between the two surfaces. In other words, whenever (8) finds a point pair that minimizes the distance, its relevance will be added to \(M_1\).
| \(M_{1} = \sum\limits_{l_{1}\in R_{1}} m_{L}(l_{1}, l_{2}), \hphantom{x} l_{2} \in R_{2}, \hphantom{x} d_{e}(p_{1}, l_{1}, R_{2}) \rightarrow min\) | (10) |
Usually the value of the one sided distance does not stay the same if you swap the surfaces. In order to achieve symmetry, which is necessary for a metric space, equation (9) must be computed twice.
| \(d_{R}(R_{1}, R_{2}) =\) | |
| \(\frac{1}{M_{1} + M_{2}}\left(\sum\limits_{(p_{1},l_{1})\in R_{1}} d_{e}(p_{1}, l_{1}, R_{2}) + \sum\limits_{(p_{2},l_{2})\in R_{2}} d_{e}(p_{2}, l_{2}, R_{1})\right)\) | (11) |
The next section shows some results computed with ParaView using the Ridge Combo plugin.
To get an idea of the behavior of ridge surfaces please take a look at the following examples first. You can see how the surfaces connect the maxima generated by the previously mentioned Metaball based scalar field.
These are the same surfaces with the result of the ridge metric. Each line corresponds to a minimizing point pair in (8).
This approach is very insensitive to low weighted background noise. While marching cubes may still produce the surface at such a point, it will make very little difference to the actual metric since all point pairs are divided by the accumulated relevance as shown in (8). Also note that (8) needs a preprocessing step where all weights are rescaled to a value that matches the extent in euclidean space. The plugin does not provide a prodcedure to estimate a good scaling so this factor has to be set manually.
No comments:
Post a Comment