An Interpolated Volume Data Model
于丹近况Tianqiu Wang
Department of Computer Science and Engineering
tiwang@cs.ucsd.edu
Simone Santini National Center for Biomedical Rearch ssantini@ncmir.ucsd.edu
Amarnath Gupta
San Diego Supercomputer Center
gupta@sdsc.edu University of California San Diego
Abstract
1Introduction
Reprenting volume data is an important task in many fields,from medicine[1]to physics and geology.
V olumes are generated by collecting discrete measurements over a finite region of space,and this collection process leads nat-urally to two obrvations:first,what is usually called a volume is in reality a function f:V→M from a volume V to a measurement space M;cond,the volume—which is commonly understood to be a continuum—is in reality reprented as a discrete(finite,in fact)t of samples.
Most volume data models carry the discreteness of the measurements all the way to the level of the abstract data type.Many a model,for instance,consider a volume as a rectangular arrangement of cubic elements called“voxels”that is,esntially,as a three-dimensional array[2].From the point of view of storing volume data into a databa and querying them,this solution has the obvious advantage of relying on a data type(the array)that is already available in commercial databas and for which a sizable literature ex-ists on issues like their effects on query optimization[3,4]. We argue,however,that a discrete data type is not the best way to model a continuum such as a volume at an abstract level:thefiniteness of the sample should be confined to the internal reprentation,while the abstract data model should be continuous.
Consider,as a simple example,a“one dimensional vol-ume”that is,an interval on a line.Assume that the mea-surements available for this volume consist of a single real Permission to copy without fee a
ll or part of this material is granted pro-vided that the copies are not made or distributed for direct commercial advantage,the VLDB copyright notice and the title of the publication and its date appear,and notice is given that copying is by permission of the Very Large Data Ba Endowment.To copy otherwi,or to republish, requires a fee and/or special permission from the Endowment. Proceedings of the29th VLDB Conference,
Berlin,Germany,2003
Figure1:A simple“one dimensional”volume.
Figure2:Results of the query on the one dimensional vol-ume example.
value v,so that the volume can be reprented as a curve in the cartesian plane,as in Figure1.The discrete repren-tation of the volume is constituted of the points marked by cross.Assume now that the following query is pod: return all the sub-volumes for which it is v<b
or v>a
where a and b are suitable constants.A query on the dis-crete t would return all the points in the data model that is,it would return a single,connected volume.In reality,by considering the volume as a continuum(which allows us to introduce the further hypothesis of continuity of the vol-ume functions),it is clear that the query should return three parate pieces,as in Figure2.In two or three dimensions, using the discrete model at the abstract data type level can result not only in the union of disconnected components, but in other topological defects as well.In particular,holes may disappear,as exemplified in the surface in Figure3. In three dimension,other topological defects are possible, such as an incorrect homotopy number(which happens,for instance,when the“hole”of a torus isfilled).Note that in many cas the precision afforded by the grid is sufficient for the application at hand(if not,presumably,there would
怎么画大象Figure3:Topological defect(the disappearing of a hole)conquent to the discrete reprentation of a two-dimensional volume.
have been a denr measurement grid to begin with),so that the error committed in placing the boundary at a loca-tion instead of another within a grid cell can be regarded as negligible;yet,the u of a discrete model can produce results that,although metrically within an acceptable pre-cision,are topologically incorrect.
One obvious way of obtaining a continuous model is by interpolating the measurements.The u of interpolated data as an abstract data type is not new,and some principles regarding their u have begun to be established.In[5],for example,it is argued that the interpolation function and the underlying discrete data t should be kept hidden,and that only the continuous model should be visi
笔记本清灰怎么清ble in the abstract data type.From the point of view of our application,the model in[5]suffers from two drawbacks.First,while the continuum(which is there considered as an infinite rela-tion)is ud in the query condition,there appears to be no way to return it as the result of a query:onlyfinite relations are returned.Second,the model in[5]doesn’t include the explicit reprentation of the boundaries of a bounded con-tinuum,so that the topology problems outlined previously would not disappear.
In our model,volumes are not infinite relations,but data types.This means that,at least conceptually,they are not tables,but elements that are stored in columns of tables. They are,in other words,first class values and,among other things,can be returned as results of queries.This doesn’t mean,of cour,that the underlying data can’t be stored in tables.If this is the ca,however,care must be taken to ensure that the volumes returned as query results and, potentially,exported out of the databa still have access to the underlying reprentation in a way that is transparent to the ur.This and other reprentation issues will be considered in the next ction.
2The volume model
In this ction,we will briefly discuss the two principal aspects of our volume model,namely the abstract data type that is exported(including the algebra that manipulate it) and the reprentation upon which the model is bad.2.1The abstract data type
Formally,a volume is a continuous function f:V→M,where V is a three dimensional clod,compact,and bounded t,and M is a measurement space that we will assumed endowed with the structure of a vector space and such that all the components of M are named.That is,M is reprented as M=(N1:T1,...,N n:T n),where N i are names and T i are data types.The measurement space M is specific to each volume,and it goes without saying that two volumes f1:V→M1and f2:V→M2which share the same domain but map into different measurement spaces should be regarded as instances of two different data types.
A special volume type is what we call the mask.Formally, a mask is a volume that maps to the data type unit(the“bot-tom”data type,with one value only).A mask is uniquely identified by its domain V and will be ud mostly to“cut”pieces from other volumes.
The most important operations of the volume algebra are summarized in Table1.Other operations are defined for determining the bounding box of a volume,returning the points in its reprentation,creating a volume,determining its homotopy number,and so on,but they are not esntial for the discussion that follows.哪些属于有氧运动
The lection operator l extracts from a volume the portions that satisfy the condition C.Since in o
ur model volumes are always connected,the operation returns a t of connected components,each one reprented as a vol-ume,rather than a single volume.The condition C can be bad on the values of the volume(being expresd in terms of the names of the measurement space M)or on the coor-dinates of the points,using the conventional name$pt to reprent a volume point and$pt.x,$pt.y,$pt.z for its coordinates.The next operation,for instance,returns the sub-volumes of f:V→[meas:R]compod of points with negative x coordinate and such that their meas value is at least5:
f2=l(f,$pt.x≤0and meas≥5)(1) Note that the conditions meas>5or$pt.x<0would be illegal becau they would not return a clod t that is, they would return a t that,according to our definition,is not a volume.
The projection operator works on the measurement space much like the synonymous relational algebra oper-ator.The interction(resp.union)operator acts as a t interction(union)on the domain of its arguments and us the operator op to compute the values associated to the points of the resulting domain.If f1:V1→M1, f2:V2→M2,and op:M1×M2→M,then
intrs(f1,f2,op):V1∩V2→M(2) and similarly for union.The common operators supported natively in our data type are addition(“+”),subtraction(“-”),multiplication by a scalar(“*”)and join( ).
Name U Description
affine V1=affine(A,V)Applies an affine transform to a volume
l{V}=l(V,C)Selects from V bad on the condition C.
proj V=proj(V,[C1,...,C n])Projects out columns in the measurement space. intrs V=intrs(V1,V2,op)Algebraic interction
union V=union(V1,V2,op)Algebraic union
inside t=inside(p,V)Checks is a point belongs to the domain of a volume. val v=val(p,V)Value of volume V at point p.
Table1:Operations of the volume
algebra
Figure4:Boundaries of a volume at creation time.
2.2Reprentation
Our abstract data model is compatible with a number offi-
nite reprentations:the only requirement is that thefinite
reprentation allows the definition of a suitable interpo-
lation function.This is true,in general,for all repren-
tation that considers point measurements.It doesn’t hold
for“voxel”model,for which the measurement is associ-
ated with afinite volume,unles some additional assump-
tion is made as to the location of the measurement inside
the volume.Several measurement structures accommodate
this model,from a regular grid of measurement points,to
an irregular tetrahedral grid,to a t of disconnected points
(also called a“point cloud”).
In our current implementation,the measurements are
arranged in a regular parallelepipedal grid.The interpo-
lation function ud is a configuration parameter deter-
mined during the installation of the system;in the follow-
ing we will always make reference to the common ca of
a tri-linear interpolation function.When a volume is cre-
ated,its boundaries are determined naturally by the grid
on which the volume is defined,as exemplified,for a two-
dimensional volume,in Figure4.Any topological error
with respect to the real data introduced by this repren-
tation would fall below the measurement precision,and
would be undetectable.
When a volume is obtained by cutting pieces of another
volume,for example with a lection operation,the bound-
aries if the volume
教育学的概念will not in general be aligned with the grid.Approximating the boundary with points on the grid would introduce the topological problems outlined in the previous ction.In order to avoid the problems,we al-low the boundary of the volume to be displaced with re-spect to the data grid by registering,for each boundary cell,Figure5:Boundaries of a
volume dispalced with respect to the
grid.
Figure6:Boundaries of three-dimensional volume. the position of the boundary inside it.The resulting model is that of a piecewi linear boundary,as exemplified for a two-dimensional volume,in Figure5.In order to extend the interpolation up to the boundary,it is necessary to keep a number of points not belonging to the volume.There pahntom points are reprented by cross in Figure5.
In volumes,the specification of the boundary is a bit more complicated.First,the boundary itlf is a piecewi linear surface rather than a simpler piecewi linear curve; cond,the relation between a portion of the boundary and a parallelepipedal cell must take into account a larger num-ber of possibilities,some of which are illustrated in Fig-ure6Once the various possibilities have been accounted for,however,we have the reprentation of a continuous piecewi bi-linear surface up to which we can interpolate the volume values,and that can be placed at arbitrary posi-tions with respect to the grid points.
Afinal issue that we want to discuss briefly here aris when volumes are returned as results of queries.The “things”that are returned are volume objects and,tofix the ideas,let us say that the results are exported from the databa as java objects(which is actually the ca in our
implementation).This volume object must carry with it its internal reprentation that is,the grid of of volume points and phantom points necessary for its computation.
Carrying along the reprentation can be a problem when the volume is reprented by thousands or tens of thousands of points(a typical volume for a human brain de-rived from an MRI scan has between100,000and500,000 points).Especially if the volume object is to be nt over a communication network,such large data t can make the communication extremely slow.All this is more un-reasonable if we consider that the ur(or the application) that requested the volume to begin with might not need to access all the points in the reprentation to carry out the computation that is needed:if all that is necessary is to call methods to,say,measure the volume(which is usually kept in a parate variable and doesn’t have to be computed on thefly),keeping the reprentation is uless.
To avoid moving around inordinate amounts of data,we allow the volume object to have a virtual reprentation. That is,while the volume object travels around the sys-tem,its reprentation stays in the databa.The various methods,instead of accessing a local reprentation,issue dtaba queries to access just enough of the internal rep-rentation to do their job.Clearly,every volume has the possibility to be“grounded”into a local reprentation by calling a suitable method.This will create a full local repre-ntation for the volume object independent of the databa and is uful,in addition to the ca in which the repren-tation is manageably small,if there is the risk that during the life of the volume object the databa will be updated. 3The Demo
In this demonstration we show the basic functionality of our volume data model.We will consider examples from biology(brain MRI data)and volumes of measurement from quantuum physics.The data model is similar in the two cas,but the operations that are commonly ud are quite different.In the cond ca,for instance,one is often interested in conditions on the behavior of local differential operators,such as zero-flow surfaces,while in the biologi-cal ca one has a mix of value homogene-ity)and geometric ditions on curvature). We hope,with the two applicationfields,to highlight the generality andflexibility of our model.
The system is bad on a commercial databa(specifi-cally,the Oracle9i databa),augmented with specialized functions to manipulate our volume data model.We will demonstrate various operations specifying queries both us-ing a graphical ur interface and entering them directly in SQL augmented with the volume algebra operations.
The demo testbed includes utilities to translate the vol-umes that are created as results to queries into standard graphic formats that can be ud by volume display pro-grams,as well as a volume display program that we will u to give a more visual demonstration of the query re-sults.4Acknowledgements
与女生聊天找话题
The work prented in this paper was done under the aus-pices and with the funding of NIH project NCRR RR08 605,Biomedical Imaging Rearch Network,which the au-thors gratefully acknowledge.
References
[1]A.Toga and P.Thmpson,“Multimodal brain atlas,”
in Medical Image Databas(S.Wong,ed.),Kluwer Academic,1998.
[2]J.D.F.amd Andries Van Dam and S.K.Feiner,Intro-
duction to Computer Graphics.Addison-Wesley,1993.
[3]A.P.Marathe and K.Salem,“A language for maniplat-
ing arrays,”in Proceedings of the23rd VLDB Confer-ence,Athens,pp.46–55,1997.
[4]A.Alcantara and B.Buckles,“Supporting array types
in monoid comprehensions.”
形象的意思小白角[5]S.Grumbach,P.Rigaux,and L.Segoufin,“Manipulat-
ing interpolated data is easier than you thought,”in The VLDB Journal,pp.156–165,2000.
