需要检测所有的最长公共子序列(alcs).ppt

计算机辅助文物复原中的若干问题研究 潘荣江 panrj@sdu.edu.cn 山东大学计算机科学与技术学院 2005 年 11 月 基础知识 1 图形学的研究内容 2 3D data types 3 2?-D Data 4 Reconstruction 5 Range Acquisition Methods Main Themes Imaging Representing 2D images Modeling Representing 3D objects Rendering Constructing 2D images from 3D models Animation Simulating changes over time Modeling--Design Graphics for Engineering and Architectural System Modeling--Reconstruction 3D Data Types Point Data “Point clouds” Advantage: simplest data type Disadvantage: no information on adjacency / connectivity Volumetric Data Regularly-spaced grid in (x,y,z): “voxels” For each grid cell, store Occupancy (binary: occupied / empty) Density Other properties Popular in medical imaging CAT scans MRI 3D Data Types Advantages: Can “see inside” an object Uniform sampling: simpler algorithms Disadvantages: Lots of data Wastes space if only storing a surface Most “vision” sensors / algorithms returnpoint or surface data 3D Data Types Surface Data Polyhedral Piecewise planar Polygons connected together Most popular: “triangle meshes” Smooth Higher-order (quadratic, cubic, etc.) curves Bézier patches, splines, NURBS, subdivision surfaces, etc. 3D Data Types Advantages: Usually corresponds to what we see Usually returned by vision sensors / algorithms Disadvantages: How to find “surface” for translucent objects? Parameterization often non-uniform Non-topology-preserving algorithms difficult Implicit surfaces (cf. parametric) Zero set of a 3D function Usually regularly sampled (voxel grid) Advantage: easy to write algorithms that change topology Disadvantage: wasted space, time 2?-D Data Image stores an intensity / color alongeach of a set of regularly-spaced rays in space Range image stores a depth along each of a set of regularly-spaced rays in space Not a complete 3D description does not store objects occluded (from some viewpoint) View-dependent scene description 2?-D Data This is what most sensors / algorithmsreally return Advantages Uniform parame