Constrained Shepard Method for Modeling and Visualization
of Scattered Data by
G. Mustafa, A. A. Shah and M. R. Asim
WSCG 2008
OUTLINE
1. INTRODUCTION 2. RELATED WORK
3. THE CONSTRAINED SHEPARD METHOD
4. IMPLEMETATION RESULTS 5. CONCLUSIONS & FUTURE
DIRECTION
6. QUESTIONS & ANSWERS
INTRODUCTION
• What is Visualization?
• Why Visualization?
• Visualization Process
DATA Empirical
Model
Geometric Model Interpolation Visualization
Mapping Rendering Image
Introduction (continued)
Empirical Modeling/Reconstruction
DATA Empirical
Model Interpolation
SCATTERED DATA METODS
• MESH BASED
Triangulation/Tetra Based Natural Neighborhood based
• MESHLESS
Introduction (continued)
MODIFIED QUADRATIC SHEPARD METHOD (MQS)
N
i
i N
i
i
X w
X Q X w X
F
1 1
i
) (
) ( ) ( )
(
( ) ( )
2 ) 1
( i i T i i
T i i
i X f g X X X X A X X
Q
Introduction (continued)
Weight Functions
2
) (
) ) (
(
X Rd
X d
X R w
i i
otherwise
X d
R if
X d
X R d
R i i i
0
) (
) )] (
(
[
(introduction (continued)
Loss of Positivity using MQS Method
0 50 100 150 200 250 300 350 -5
0 5 10 15 20 25
Time (sec)
O xy ge n L ev el ( % )
RELATED WORK
• Previous Work [1, 2, 3, 4]
• Problem with the previous methods
Efficiency Accuracy Continuity
Scalar invariance
(RELATED WORK continued)
Minima Free Algorithms
• Negative Value to Zero
(Xiao & Woodbury[7])
• Basis Function Truncation
• Dynamic Scaling
Algorithm
RELATED WORK (continued )
Minima/Zero Searching Algorithms
• Modified Positive Basis Function (Asim[1])
• Scaling & Shifting Algorithm (Asim[1])
• Constraining Radius of Participation
• Hybrid Algorithms
Piecewise continuous basis function
Blending Algorithm ( Brodlie, Asim & Unsworth[3])
• Fixed Point Scaling
• Dynamic Scaling
(Related work continued)
Scaling Solutions
(Fixed Point Scaling)
( ) ( )]
2 ) 1 (
[ i T i i T i i
i i
i X f K g X X X X A X X
Q
0 )]
( )
( ) (
[
. 0
i m
i T i m
i m
T i i i
m i
X X
A X
X X
X g K f
e i X
Q
m i i T ( m i ) ( m i ) T i ( m i )
i X f g X X X X A X X
Q
i i
i X f
Q ( )
Current Work (continued)
Scaling Factor
varies between 0 and 1
) ( m
i i
i i
X Q
f K f
K
K i
RELATED WORK (continued )
Execution Time
) ( m
i i
i i
X Q
f K f
N=30
25x25 grids
MQS Fixed Point Scaling
(Positive) Blending
Method
Execution Time (sec) .0170 .0640 .0670
RELATED Work (continued)
Minima of Quadratic Basis Function
1 2 3 4 5 6 7
-1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 3 3.5
x
y
wi i
i Ui
T i i
T Ui Ui Ui
R X
X
ConstrainT to
subject
X X A X X X
X g d X D
Minimize
( ) ( )
2 ) 1 (
0 50 100 150 200 250 300 350
-10 0 10 20 30 40 50
Time (sec)
Oxygen (%)
1 1.5 2 2.5 3 3.5
y
Previous Work (continue)
The Problem
Minima Searching
• Computationally Intensive
• Difficult to implement
• Convergence Problem
Current Work
The Constrained Shepard Method
N
i
i N
i
i
X w
X R X w X
F
1 1
i
) (
) ˆ (
) ( )
ˆ (
otherwise X
D X
X C
f X
Q if
X D
X X
X C
R i U m Ui Ui i i
) ˆ (
) ( )
(
) ˆ (
) ˆ (
) ( )
) ( ˆ (
Current Work (continued)
The K Value
0 100 200 300
-0.5 0 0.5 1 1.5 2 2.5
X
Y K=1/10
R1
R2 R3
0 100 200 300
-0.5 0 0.5 1 1.5 2 2.5
X
Y
K=K0 R1
R2 R3
0.5 1 1.5 2 2.5
Y
K=1/3 R1
R2 R3
0.5 1 1.5 2 2.5
Y
K=1/100 R1
R2 R3
Current Work (continued)
The K Value
1 2 3 4 5 6 7
-0.5 0 0.5 1
X
Y
R1 R2
K=K0 R3
0 0.5 1
Y
R1 R2
K=1/3 R3
0 0.5 1
R1 R2
R3 K=1/100
1 2 3 4 5 6 7
-0.5 0 0.5 1
X
Y
R1 R2
R3 K=1/10
• Maximum and minimum in the whole domain
• Use nearest from the Maxima and minima in the whole domain
Current Work (continued)
Approximation for constraints
Functions
Example 1: Graph of z=sin2(x)sin2(y)
0
1
2
3 0
0.5 1 1.50 0.5 1
y x
z
IMPLEMENTATION & RESULTS
Example : Lancaster Function Plot
0
1
2 0
0.5 1
0 0.5 1
Y X
Z
0
1
2
0 0.5
1 0 0.5 1 1.5
Y X
Z
0.5 1
Z
0.5 1
Z
IMPLEMENTATION & RESULTS (continued)
Performance Measures (Accuracy)
Root Mean Square (RMS) and Absolute Maximum (AM) Deviations)
Deviations
0 0.2 0.4 0.6 0.8 1 1.2 1.4
a S et 1 a S et 2 a S et 3 a S et 4
A . M . D ev ia tio ns
MQS Empirical Brodlie
Deviations
0 0.05 0.1 0.15 0.2 0.25
at a S et 1 at a S et 2 at a S et 3 at a S et 4
R .M .S . D ev ia tio ns MQS
Empirical
Brodlie
IMPLEMENTATION & RESULTS (continued) Performance Measures (Accuracy)
RMS and AM Jackknifing Errors
Jackknifing Errors
0 0.05 0.1 0.15 0.2 0.25 0.3
D at a S et 1 D at a S et 2 D at a S et 3 D at a S et 4
R .M .S . e rr o rs
MQS Empirical Brodlie
Jackknifing Errors
0 0.2 0.4 0.6 0.8 1 1.2 1.4
D at a S et 1 D at a S et 2 D at a S et 3 D at a S et 4
A .M . e rr o rs
MQS Empirical Brodlie
IMPLEMENTATION & RESULTS (continued)
Performance Measures (Accuracy)
Deviations (vs) Sample Size
0 0.01 0.02 0.03 0.04 0.05 0.06 0.07
0 100 200 300 400 500
Sample Size(N)
A. M. Deviations
MQS Empirical Brodlie
Deviations (vs) Sample Size
0 0.002 0.004 0.006 0.008 0.01 0.012 0.014 0.016
0 100 200 300 400 500
Sample Size(N)
R.M.S. Deviations
MQS Brodlie Empirical
IMPLEMENTATION & RESULTS (continued)
Performance Measures (Accuracy)
Jackknifing Errors (vs) Sample Size
0 0.005 0.01 0.015 0.02 0.025 0.03 0.035
0 100 200 300 400 500
Sample Size (N)
R.M.S. Errors
MQS Brodlie Empirical
Jackknifing Errors (vs) Sample Size
0 0.02 0.04 0.06 0.08 0.1 0.12
0 100 200 300 400 500
Sample Size(N)
A. M. Errors
MQS
Brodlie
Empirical
Sample Size (VS) Preprocessing Time
Preprocessing time (vs) sample size
0 0.1 0.2 0.3 0.4 0.5 0.6
0 100 200 300 400 500
Sample size (N)
Pr ep ro ce ss in g tim e (s ec ) MQS
Brodlie
Empirical
Components of Execution Time
(N=30 and 25x25grids)
Time Division
0 0.05 0.1 0.15 0.2 0.25
M Q S Em pi ric al Br od lie
To ta l T im e (s ec )
Execution
Setup
Positivity
Grids (VS) Execution Time
Execution time (vs) Grids
0 2 4 6 8 10 12 14
0 50 100 150 200
Ex ec ut io n Ti m e (s ec )
MQS
Brodlie
Empirical
CONCLUSION & FUTURE WORK
• Achievement
• Efficient Solution
• Accurate
• Easy to implement for n-D data
• C1 Continuity
• Scalar invariant
• Drawbacks
– No more quadratic precision
References
• [1] Asim M. R., “Visualization of Data Subject to Positivity Constraint,” Doctoral thesis, School of Computer Studies, University of Leeds, Leeds, England, 2000.
• [2] Asim M. R, G. Mustafa and K.W. Brodlie, “Constrained Visualization of 2D Positive Data using Modified Quadratic Shepard Method” Proceedings of The 12th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision, Czeck Republic, 2004, pp 9-13.
• [3] Brodlie, K. W., M.R. Asim, K. Unsworth, “Constrained Visualization Using the Shepard Interpolation Family,” Computer Graphics Forum, 24(4), Blackwell Synergy, 2005, pp. 809–820.
• [4] Franke, R. and G. Neilson, “Smooth Interpolation of Large set of Scattered Data,” International Journal of Numerical Methods in Engineering, 15, 1980, pp 1691-1704.
• [5] Renika R. J., “Multivariate Interpolation of Large Set of Scattered Data. ACM Transactions on Mathematical Software, 14 (2), 1988, pp 139-148.
• [6] Shepard, D., “A two-dimensional interpolation function for irregularly spaced data,” Proceedings of 23rd National Conference, New Yark, ACM, 1968, pp 517-523.
• [7] Xiao, Y and C. Woodbury, “Constraining Global Interpolation Methods for Sparse Data Volume Visualization,” International Journal of Computers and Applications, 21(2), 1999, 56-64.
• [8] Xiao, Y., J.P Ziebarth, B. Rundell, and J. Zijp, “The Challenges of Visualizing and Modeling Environmental Data,” Proceedings of the Seventh IEEE Visualization (VIS'96), San Francisco, California, 1996, pp 413-416.
• [9] William F. G., F. Henry, C. W. Mary and S. Andrei, “Real-Time Incremental Visualization of Dynamic Ultrasound Volumes Using Parallel BSP Trees,” Proceedings of the 7th IEEE Visualization Conference (VIS’96), San Francisco, California, 1996, page 1070-2385.
• [10] Fuhrmann A. and E. Gröller, “Real-Time Techniques for 3D Flow Visualization,” Proceedings of the IEEE Visualization 98 (VIZ’98), 1998, pp 0-8186-9176.
• [11] Wagner, T. C., M.O. Manuel, C. T. Silva and J. Wang, “Modeling and Rendering of Real Environments,” RITA, 9(2), 2002, pp 127- 156.
• [12] Park S.W., L. Linsen, O. Kreylos, J. D. Owens, B. Hamann, “A Framework for Real-time Volume Visualization of Streaming Scattered
