Transcript Presentation (PowerPoint File)

Efficient Visualization and
Interrogation of Terascale
Datasets
Gheorghe Craciun, Ming Jiang
Raghu Machiraju
The Ohio State University
Roy Rong, Li Hua, Sridhar Dusi, Jaya Nair, Sajjit
Thampy
James Fowler David Thompson Bharat Soni
Engineering Research Center, Mississippi State
University
Hari Iyer
William Schroeder
Rensselaer Polytechnique Institute
Visualization
CT, MRI, Laser,
Ultrasound
Numerical Simulations
Iso-Surfaces
Find Implicit Surface
s = f(x,y,z)
More Iso-surfaces
Particle Tracing
State-Of-Affairs ?
Simulations, scanners
Concurrent
Presentation
Retrospective
Analysis
Representation
Another Real Problem !
Data is too complex;
What is a good iso-value ?
Bottom Line ...
•
•
•
•
Exploration and visualization too slow !
Large parameter space
Too much information
Cumbersome display and interaction devices
understanding
amount
Solution ?
• Goal: Maximize information (features) access
while minimizing data rate
• One Method
–
–
–
–
–
Seek features
Rank them
Access data in view frustum
Give cues for interesting visual filters
Visualization
Solution …
Explore large (terascale) datasets:
•
•
•
•
•
•
•
Detect features that may be of importance
Segment features into regions-of-interest (ROI)
Rank ROIs, rank information within ROIs
Compress data and grid for ROIs
Progressive visualization of ROIs
Allow user to change order of progression
Provide exploration tools to determine features
Why Feature-Based ?
Magnitude Based
Missing !
Reconstructed
1% Rate
Feature Based
Is This Data Mining ?
• Yes !
• It is structure-based
• Basic premise --Features and their shapes are correlated
manifestations of simulation parameters
• Once shapes are determined do all mining on
shape descriptors !
Progressive Visualization
ROIs displayed with successively increasing
resolution (fidelity)
EVITA System Operation
Background is ROI 0
EVITA System
Final Goal !!
EVITA System Demo
Interrogative Techniques
Scatter Plots
Characteristic Curves
EVITA System
Preprocessor
Server
Client
Research Issues
Feature Detection:
• Detection of significant features in
wavelet domain
• Ranking of features for visualization
• Tracking features through space & time
• Really Structure or Region Mining !!
Research Issues
Coding & Compression:
• Efficient compression of vector fields &
grids
• Embedded coding of significant features
• Interactive ROI trans-coding
Research Issues
Visualization:
• Interrogative techniques
• Interactors for 4D space-time navigation
Research: Wavelet Transform
Feature Detection:
• Detection of significant features in wavelet
domain
• Design feature preserving transforms
• Basic Premise: Transformations should not
destroy features and their shapes
Wavelet Analysis
w
L=(1/2,1/2)
K=(1/2,-1/2)
K
L
N sample points
O(N) Algorithm
N coefficients
L
K
L
K
Discontinuity As A Shape !
Popular Filter 1
Popular Filter 2
Complicated Discontinuity !
Stream Function
Popular Filter 2
PDE FrameworkModel Equations
• Application of linear filter = evolving solution of PDE
• S is function and Dx, Dt are space and scale (time)
resolutions
• Going from fine to coarse scales
s / t  a(Dx j / Dt )(s / x)
 (1/ 2!)(Dx 2 / Dt )(b  a 2 )( 2 s / x 2 )
j
 (1/ 3!)(Dx 3 / Dt )(c  3ab  2a3)( 3s / x3)
j
 (1/ 4!)(Dx 4 / Dt )(d  4ac  3b 12a 2b  6a 4 )( 4 s / x 4 )
j
5 /c,
a,xb,
 (D
Dtd:
) moments of filter coefficients
Analysis of Wavelet Schemes
Haar (Wave Equation):
•phase shift – shapes move
•amplitude damping – shapes change
s/ t  (1/ 2)(Dx j / Dt)(s/ x) (1/ 8)(Dx j 2 / Dt)( 2 s/ x 2 )  (Dx j 3 / Dt)
Linear (Heat Equation) :
• no phase shift
• Shape change but not location
s/ t  (1/ 4)(Dx j 2 / Dt)( 2 s / x 2 )  (1/12)(Dx j 4 / Dt)( 4s / x 4 )  (Dx j 6 / Dt)
Total Variation Diminishing
S|sln+1-skn+1| < S |snl-skn|
•Need more for shapes
•Limiting growth of functions
•Will not allow for new maximas or minmas …
Filter Design Axioms for A
•Partition of Unity
a
• Symmetric Function
k
k
1
ak  a k ,
k j
(

1
)
k ak  0,
•Accuracy of order p for smooth data 
k
•TVD
ak  ak 1  0,
•Stable Transform
• Distance to Sinc Function
• Implement as filter bank
High res
A
Low res
Examples
• (1/4, 1/2, 1/4) is shortest filter that, for p=1,
satisfies axioms – linear TVD
• Filter of length 5 that satisfies axioms for largest
possible p(1/16, 1/4, 3/8, 1/4, 1/16) and p=4.
• Design can be achieved through optimization
procedure
• Find something close to ideal filter (since filter)
TVD Scheme
s / t  (1/ 4)(Dx
2
j
/ Dt)( 2 s / x 2 ) 
(1/ 24)(Dx j 4 / Dt)( 4s / x 4 )  (Dx j 6 / Dt)
Linear Symmetric TVNI:
• no phase shift, amplitude decrease
Feature Preservation
Total Variation Diminishing (TVD)
TVD
3D Results
Original
Image
Cubic wavelet
Result (not
TVD)
TVD wavelet
Result
Research: Feature Detection
• Objective: Identify different types of
features for CFD solutions on structured
grids
• Feature catalog
–
–
–
–
–
Stationary and transient shocks
Expansion regions
Vortices
Separation and attachment lines
Regions of separated flow
Basic Approach
•
•
•
•
Inexpensive method to find core !
Should be easily done at all scales
Involve underlying physics
Portela (1997):
– A vortex is comprised of a core region
surrounded by swirling streamlines
• Design algorithm based on intuition
– Detect vortex core region
– Verify using swirling streamlines
• Feature matching and feature tracking are
straightforward
3D Rankine Vortex
Detection Algorithm
• Point-based approach using ideas from
combinatorial topology
– Sperner’s Lemma:
• Every properly labeled subdivision of a simplex
has an odd number of distinguished simplices
– Brouwer’s Fixed Point Theorem:
• Every continuous mapping has a fixed (critical)
point - ( to stirring coffee in cups  )
Sperner’s Lemma
At least one subtriangle in a Sperner labeling
receives all three labels: {A, B, C}
Vector Field Labeling
2D vector field
Labeling scheme
2D Algorithm
• Simple and efficient!
• Point-based approach:
– Label neighbors
• Combinatorial:
– Locally check for
complete triangles
2D Results
Rankine Vortices
Wake Simulation
3D Algorithm
• Requires computing
vortex direction:
– Vorticity (physics)
– Real eigenvector
• Combinatorial:
– Project 6
neighborhood vectors
on plane
– Locally check for
complete tetrahedrons
Bent Helical Vortex
Delta Wing Dataset
Research: Interrogative Vis
• Objective: Identify important function
values to browse and interrogate
• Provide an easy interface
Which Iso-value ?
Every organ has an iso-value ?
Which ones are important ?
Essentially Seek …
Find Transitions - No Model
Use localized higher order moments
– Two Material-mixture model
– Assume a localized probability model
– Determine moments, cummulants
– Determine “minimas” and “maximas”
x
i 0
i
w
1
M  2
w
w 2 1
xi  w2
mk 
1
2
w
w2 1
 ( xi  M )
i 0
w
k
Boundary, Material Interface
Left-Boundary Region
On-Boundary Region
Right-Boundary Region
Non-Boundary Region
Boundary Detection
Kurtosis
Boundary Detection
Skew
Tooth Dataset - Skew
Delta Wing - Kurtosis
Computational Method
In presence of a interface !
•Skew, S, has a zero-crossing.
• Kurtosis, K, has a minima of –2
Computational Method
•Determine S, K in all volume
K
DS
DK
– DS
0
0
f
-2
S
• Count for each function value
samples which do and do not
satisfy the rules
• Find votes D (=difference)
•The functions with non-zero
votes, D, are winners !
• Plot curve D vs. func. value
Summary
●
Reduce Data first !
●
Make sure you do not mess it up 
●
Mine structures – get shapes
●
Need to devise cheap techniques
●
Use Fine techniques in small regions
Summary
●
Cross discipline boundaries
●
This work is collaboration between
1 mathematician,
1 electrical engineer,
1 aerospace engineer,
2 computer scientists
●
Get into applications
●
CS abstractions alone cannot solve the problem
Acknowledgements
●
NSF Career Award
●
NSF Large Data Visualization Program
●
NSF ITR Program
●
Mitsubishi Electric Research Laboratories
●
DoD MSRC program
●
Many Graduate Associate Colleagues
Questions ?