Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

PhD Presentation

No description
by

Irving Cruz

on 16 April 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of PhD Presentation

Isolated faces are not displaced. Faces of C disjoint with

C and vice versa.
Ph.D. Thesis
Programa de Doctorat en Computació
Departament de Llenguatges i Sistemes Informàtics

by: Irving A. Cruz-Matías

Advisor: Dr. Dolors Ayala

Contribution to Structural Parameters Computation: Volume Models and Methods
Introduction
Background
Main
Contributions
Practical
Applications
Conclusions
and F.Work
Outline
Representation Models
Structural Parameters
Model Simplification
An Improved
Decomposition Model
Connectivity
Lossless Orthogonal
Simplification
Sphericity and
Roundness
Virtual Porosimeter
CUDB-based
Virtual Porosimeter
MIP simulation that does not require the
skeleton computation.

Washburn’s equation:
D
= − (4W γ
cos
θ)/ρ . Each pressure ρ
is ρ related to a representative diameter
D
.

Iterative process that computes for each diameter
D
the
invaded region
R
:

Discarding process.

Narrow throats detection.

Mercury intrusion simulation.
Discarding Process
Pore regions smaller than the current
diameter
D
are discarded.
Three ABC-sorted CUDB are scanned.
Faster opening-like operation.
Narrow
Throats Detection
Treatment
of the Void Space
An OPP may have any number of rings on
faces, through holes and shells.
Merging
Faces Optimization
Two theorems:


Shape Preservation
Lossless
Progressive Encoding
Progressive Extreme Vertices Encoding (PEVE) stores the extreme vertices of the sequence of BOPP only once.
Quality Distortion
Quality distortion curves of 12 test datasets
as a function of the percentage of total bytes
decoded (transmitted).
Comparison
with similar methods
Octree-based method:
Smaller storage size.
Better indication of the shape.
Motivation
Objectives
Devise a new compact representation model
for binary volumes that allows fast
neighborhood operations.
Samples
Porous materials: Solid and pore space →
Binary volumes.




Pore space → Collection of pores interconnected by throats.





Real samples generate huge datasets.
Structural Parameters
In-silico experimentation = Mathematical
models + computers.
Imaging acquisition technologies + computer capabilities = processing and visualization of scientific data.
Structural
Parameters Computation
Porosity, pore-size distribution.
Helps to interpret characteristics of porous samples.
Suitability of biomaterials to form new tissues.

Connectivity.
Topology-preservation evaluations.
Used to measure the strength of bones or materials.

Sphericity and roundness.
Used in geology to classify particles and measure
their resistance to crushing or fragmenting.
Objetives
Bio-CAD refers to the computation of structural
parameters:
Physical properties of a sample
Used in biomaterials, medicine,
mineralogy, geology, etc.
Voxel Model
Commonly used to represent medical
and scientific data.
Regular decomposition into a set of identical
cubic cells.






Binary voxel model → porous and solid spaces.
High memory and computational
power requirements.
Extreme Vertices
Model (EVM)

Extreme vertices: ending vertices of maximal segments.
ABC-ordering, Cuts (C), Slices, Sections (S).
Low memory footprint.
Fast Boolean operations:
Recursive operations.
Ordered Union of
Disjoint Boxes (OUDB)
Disjoint boxes derived by splitting an OPP at every internal cut.
Six different ABC-OUDB models.
Efficient for neighborhood operations,
e.g. volume and CCL.
Roundness
A true 3D roundness index is impractical.

Several methods use 2D projections (silhouettes).

Krumbein's chart: Roundness of pebble silhouettes.
Orientation,
Sphericity and Roundness
Orientation → rotation angles around a set
of orthogonal axes.

Sphericity = how spherical is a particle. Wadell's sphericity:


Manual measures of
S
are very difficult. Alternatives use the three representative axes, e.g: Ψ=(c /ab)

Roundness = sharpness of a particle's edges and
corners. Wadell's 2D roundness:
Connectivity
Pore-size Distribution
Model Simplification
Extensively applied to triangular meshes using geometric or morphological operations.

Representations such as octrees or BSP are used to simplify the geometry and topology.

Lossy and lossless methods preserve
the original topology or obtain an
approximated shape.
Bounding Volumes
Sometimes it is desirable to compute a bounding approximation, e.g.:
Fast collision detection between massive models.
Volume of interest computation.

Bounding structures: AABB, spheres, slab cut balls, etc.

Some simplification methods produce
hierarchies of either polygonal meshes
or polygonal convex volumes.
Binary Space Partition (BSP) tree
Other Representations
To reduce the memory footprint and
improve the performance:
Octree
Hierarchical Structures

Boundary Representations
Kd-tree
Contructive Solid
Geometry (CSG)
etc.
B-Rep
Chain Codes
Semi-boundary and Shell
Extreme Vertices Model & Ordered Union of Disjoint Boxes
etc.
Concise representation scheme for orthogonal
pseudo-polyhedra (OPP).
XYZ (8 boxes) XZY (7 boxes) YZX (9 boxes)
Usually computed with a mercury intrusion porosimeter (MIP).
Mercury intrusion at increasing pressures.

Washburn's equation → pore-size histogram.
D
= -(4
W
γ
cos
θ) / ρ

Toxic products, samples cannot be reused.
Virtual porosimetry simulates MIP → Flood-fill methodology.

Alternatives: Heuristic methods and granulometry.

Skeleton computation is a very
time-consuming process.
Connectivity is related to genus.

Can be estimated from the Euler-Poincaré characteristic, χ:






Some methods use skeletons and
alternative models like EVM.
From a voxel model: χ = n - n + n - n

In theory of homology (betti numbers): χ = h - h + h

From a polyhedron: χ = V - E + F - R = 2(S - g)
0 1 2 3
0 1 2
2 1/3
Later methods give values linearly correlated with this chart.
Compact Union of Disjoint Boxes Model (CUDB)
A cell decomposition representation that improves OUDB:
YZX-OUDB
YZX-CUDB
Less number of boxes. Several contiguous boxes are merged into one.
Implicit order among boxes that defines their adjacency is lost; however, adjacency information is preserverd in the boxes.
i
i
i
X-discarding
Y-discarding
Resulting pore
region
Orthogonal throats
Single oblique
throat
General oblique
throat
i
Mercury
Intrusion Simulation
CCL applied to the partitioned pore space.

A labeled region
R
is produced.
Comparison with a skeleton-based method
Two strategies: Inclined rectangle and L-shape.
i
Pore-size distribution.
Connectivity Computation
Method derived from the classical method
used with a voxel model.
Computing
Unitary Elements
Per each box, the number of enclosed voxels,
faces, edges and vertices are computed.
Compared with a voxel-based and a previous
EVM-based method.

Tested with a collection of 15 datasets.

All methods produce exactly the same results.

Fast computation of χ, < 1 second in all tests.

0 1 2 3
1 0 2
All possible overlaping regions are
taking into account.
Possible configurations of a box β with its backward neighbors.
i
Up to two orders of magnitude faster than the voxel-based method.

Up to an order of magnitude
faster than the EVM-based
method.
Total genus
computation
Narrow throats are removed from the pore space to prevent the mercury invasion.
Max. difference: < 12% (inclined rectangle) < 3% (L-shape).
MIP simulation up to an order of magnitude faster.
It require a CUDB-represented object.
The contribution of unitary elements per box
are computed using the expresion suitable for the voxel model.
χ = n - n + n - n
Genus is computed applying CCL to get the connected components and cavities.
h = h + h - χ
Method Performance
EVM-Roundness Correlation
Correlation with Krumbein’s chart = -0.898.

Computing OBB from the voxel model = -0.902.
Orientation
Oriented bounding box (OBB) used to get
the three representative axes of an object.

OBB computed with the covariance method using extreme vertices instead of voxels.
Maximum volume difference < 8.5%.

Faster computation.
Orthogonal
Throats Detection
Boxes in CUDB have neighboring boxes in the
A and B-direction. Othogonal throats are detected in
A-direction.

An orthogonal throat exists between consecutive boxes if the following conditions are satisfied:
Oblique
Throats Detection
An oblique throat exists between consecutive boxes if the following conditions are satisfied:
EVM-represented oblique throat created with the Bresenham’s algorithm.
EVM-Roundness
A 3D roundness index using a ray-casting-like approach based on EVM. Three steps:
2. Transform the model such that the reference ellipsoid is in the origin.
3. Trace rays to each extreme vertex and
compute the deviation from the ellipsoid's surface.
1. Compute the OBB → Inscribed ellipsoid.


Correlation with a previous 3D roundness index = -0.938
Publications

I. Cruz-Matías
and D. Ayala. A New Lossless Orthogonal Simplification Method for 3D Objects Based on Bounding Structures. Graphical Models, (Acceptable for publication provided minor revisions are made), 2013.
M. Garcia-Valles, H. Hafez,
I. Cruz-Matías
, E. Vergés, M. Aly, J. Noguées, D. Ayala, and S. Martínez. Calculation of viscosity-temperature curves for glass obtained from four wastewater treatment plants in Egypt. Journal of Thermal Analysis and Calorimetry, 111:107–114, 2013.
J. Rodríguez,
I. Cruz
, E. Vergés, and D. Ayala. A connected-component-labeling-based approach to virtual porosimetry. Graphical Models, 73:296-310, 2011.

I. Cruz-Matías
and D. Ayala. Merging faces: A New Orthogonal Simplification of Solid Models. DGCI 2013, volume 7749 of LNCS, pages 143–154. Springer-Verlag, 2013.
I. Cruz-Matías
and D. Ayala. An Efficient Alternative to Compute the Genus of Binary Volume Models. GRAPP 2013, pages 18–26, Barcelona, Spain, 2013.
D. Ayala, E. Vergés, and
I. Cruz-Matías
. A Polyhedral Approach to Compute the Genus of a Volume Dataset. GRAPP 2012, pages 38–47, Rome, Italy, 2012.
I. Cruz-Matías
and D. Ayala. Orthogonal Simplification of Objects Represented by the Extreme Vertices Model. GRAPP 2012, pages 193–196, Rome, Italy, 2012.

J. Rodr ́ıguez,
I. Cruz
, E. Vergés, and D. Ayala. Skeletonless Porosimeter Simulation. XX Spanish Computer Graphics Conference-CEIG 2010, pages 49–56. Ed. Ibergarceta, 2010.
Journals
International Conferences
National Conferences
Acknowledgments
Acknowledgments to the CICYT projects TIN2008-02903 and TIN2011-24220, and to the Doctoral grants of MAEC-AECID and
CONACYT-México.
Thanks for your attention
Questions?
Basic Merging
Displacement in pairs of OPP's faces in the
direction of their corresponding normal vector.
Orthogonal Simplification
A level-of-detail sequence of bounding OPP (BOPP)
that satisfy the next properties:
PEVE and
Structural Parameters
Pore-size distribution: A simplified sample retains enough relevant information and is processed faster.

Connectivity: Datasets containing big holes preserve its genus until approximations with 10% of the elements.

Sphericity is better preserved than roundness throughout the simplification.
Incremental method:
Subset property:
Any BOPP contains the previous one.
Finiteness
: The sequence is finite and ends with
the AABB shared by all BOPP.
New cuts that represent the merged faces and replace the original cuts are computed as:
A void space is given by :
The removal of
vSpace
closes the void space.
Two EVM properties that permit to perform unions and differences in some cases as simple point-wise
XOR operations.
Original
with shape
preservation
without shape preservation
CUDB-based collision algorithm used to detect 2D isolate faces.
EV classiffied into 3 categories.
B
A
BSP-based method:
Faster run-time.
Maintain better the concavities.
BP-Octree-based method:
Faster run-time.
Better indication of the shape.
Less storage cost.
Silica nano
CT dataset
Industrial uses of silica sand depend on its
purity and physical characteristics.
Grain Properties Computation
The more round and spherical are the particles, the more resistant they are to crushing or fragmenting.
Conclusions
Future Work
CUDB:
A decomposition model, CUDB.
An EVM-based lossless simplification method
for OPP. Compared with similar methods:
Virtual porosimeter.
Connectivity
Orientation and roundness index.
Pore space partitioning using a different approach to virtual porosimetry, e.g. compute all throats at once and analyze paths that connect the solid space.
Simplification method:
An EVM or CUDB-based data
structure to encode
time-varying datasets.
CUDB produces an optimal number of disjoint boxes ?
Computation of the CUDB complement.
Method that preserves the connectivity.
Extend the comparison to other methods.
Developed Methods
CUDB implemented as an object with
a set of properties and methods.
Straightforward by doing a traversal
of the boxes.
Area (2D) and volume (3D) computation:
EVM ←→ CUDB conversion.
Similar conversions than OUDB.
Developed Methods (2)
Exact collision detection.
Connected Component Labeling (CCL).
Detection of connected components in graph theory.
Depth-first or breadth first search.
Takes advantage of the implicit order of boxes in CUDB.
Objects are tested simultaneously instead of in pairs.
EVM→CUDB. Compacting on the fly.
Three ABC-sorted CUDB are scanned.
Inclined rectangle L-Shape Skeleton-based method.
CUDB Performance
Less elements than EVM and OUDB.

CCL computation up to two orders of magnitud faster than the
OUDB-based method.
OUDB CUDB
Thirty 3D models of rocks.
Lossy Simplification
Merging faces strategy takes consecutive
cuts in pairs. Merging conditions:

Data Structure
for Progressive Encoding
Unique (U): It appears once.
Consecutive (C): It has a consecutive occurrence.
Sporadic (S): It appears several times.
Maximum value for the distance.
Maximum number of EV in the last BOPP.
Theorem: The number of times a S-vertex can appear is <=2 (2D) and <=4 (3D).
Practical Application
Preprocessing: Conversion to 8-bit voxel model, scaling, binary threshold filter, and noise reduction.
A 32-bit gray scale dataset in RAW format with dimensions 131x281x332 of a silica nano CT.
Smaller storage and better performance
than OUDB.
Three structural parameters methods with better run time than reference methods.
Better indication of the shape.
In some cases: Faster run time and
less stoge.
The method computes all the objects for successive values of displacement
d
.
Two queries of simplification:
CCL process

Extreme vertices
: ending vertices of maximal segments.
ABC-ordering
: Sorted set of extreme vertices.
Cuts (C)
. Set of EV lying on a plane → FD and BD.
Slices: Prismatic region between cuts.
Sections (S)
: Set of polygons, base of each slice.
Extreme
Vertices Model (EVM)
Low memory footprint.
Fast Boolean operations.
A new approach for virtual porosimetry, which avoids the skeleton computation.
A method to compute the connectivity of binary volumes based on the proposed representation model.
Geometric methods to evaluate the sphericity and roudness.
A method to simplify binary volume and general orthogonal pseudo-polyhedra, in a lossless way.
Develop two practical applications using datasets coming from real
samples.
?
Full transcript