Advances in Imaging and Electron Physics (eBook)

Peter W. Hawkes (Herausgeber)

eBook Download: EPUB

2011 | 1. Auflage
328 Seiten
Elsevier Science (Verlag)
978-0-08-046276-9 (ISBN)

Infos

Advances in Imaging and Electron Physics merges two long-running serials-Advances in Electronics and Electron Physics and Advances in Optical and Electron Microscopy. This series features extended articles on the physics of electron devices (especially semiconductor devices), particle optics at high and low energies, microlithography, image science and digital image processing, electromagnetic wave propagation, electron microscopy, and the computing methods used in all these domains.

Inhalt

front cover 1
Title page 4
copyright 5
table of contents 6
front matter 8
Contributors 8
Preface 10
Future Contributions 12
body 18
Retrieval of Shape from Silhouette 18
Introduction 18
Reconstructing Three-Dimensional Shapes: General Techniques 18
Shape from Silhouettes 20
The Visual Hull 22
Definitions and General Properties 25
The Visual Hull of an Object Relative to a Viewing Region 25
The External Visual Hull 27
The Internal Visual Hull 29
Algorithms for Computing the Visual Hull 30
The Aspect Graph 31
The Boundary Surfaces of the Visual Hull 32
Computing the Visual Hull in 2D 33
Computing the Visual Hull of a Set of Polygons. 33
Computing IVH(SP). 35
Computing the Visual Hull of Curved 2D Objects. 35
Polyhedral Objects 37
Lines Making Two Contacts. 39
Lines Making Three Contacts. 41
The Algorithm for Computing VH. 43
Solids of Revolution 49
Smooth Curved Objects 51
Understanding 3D Shapes from Silhouettes: Hard and Soft Points 54
How Many Silhouettes Does the Best Reconstruction Require? 60
Interactive Reconstruction 61
The Interactive Reconstruction Approach 62
A General Approach to Interactive Reconstruction. 63
An Interactive Algorithm for Convex Polyhedra. 63
The Strategy of NEXT. 64
Reconstruction with Unknown Viewpoints 66
Writing the Sets of Inequalities 68
Three Silhouettes. 68
Four Silhouettes. 70
Five or More Silhouettes. 72
Writing and Solving the Sets of Inequalities 72
Practical Object Reconstruction 74
Surface Reconstruction 77
Volumetric Reconstruction 80
Space Carving 82
Image-Based Visual Hull 84
References 85
Projective Transforms on Periodic Discrete Image Arrays 92
Introduction 93
Overview of FRT 95
Connections Between FRT and Other Discrete Formalisms 101
Applications of Discrete Projective Transformations 103
Summary of Chapter Content 104
Discrete Projections in Continuous Space: A Review of CT Methodology 105
Definition of the Continuous Space Radon Transform 105
Important Properties of the Radon Transform 106
Fourier Slice Theorem 106
Convolution Property 107
Inversion or Reconstruction from Projections 107
Tomographic Reconstruction from Acquired Projections 109
Data Acquisition 109
Fourier Inversion (FI) 109
Filtered Back-Projection (FBP) 111
Algebraic Reconstruction Techniques (ART) 112
Maximum Entropy or Maximum Likelihood Methods (ME) 114
Alternative Representation of the Radon Transform 114
Motivation for Discretization of the Radon Transform 116
Discrete Radon Transform Formalisms 117
Generalized DRT 117
Uniqueness and Resolution in Digital Reconstruction from Projections 119
The Mojette Transform 121
The Fast Slant Stack 125
Finite Radon Transform 128
Discrete Periodic Radon Transform 129
Orthogonal Discrete Periodic Radon Transform 131
Finite Radon Transform over Arbitrary Arrays, ZN2 133
Sampling Function, upsilonN(x,y) 135
Multiresolutional Correction for upsilonN(x,y) in Back-Projection 136
Filtered Back-Projection 137
Finite Radon Projection Angle Properties 139
Best Lines to Describe the Subgroups in Zp2 139
Maximum FRT Gap Length, dmax 139
Common FRT and Farey Angles 141
Determining xm and ym 142
Angular Distribution of the FRT Projection Set 143
The FRT Applied to Arrays of Higher Dimensions, ZpN 148
Discrete Lines in ZpN 148
N-D FRT Based on Discrete Line Sums 149
Properties of Direction Vectors and Subgroup Generators in Zp3 151
Defining Projections from the Discrete Fourier Slice Theorem 152
3D FRT Based on Discrete Plane Sums 153
Discrete Tomographic Reconstruction 154
Reconstruction Using Large p 155
Importance of FRT Projections Associated with Large dm 157
Reconstruction Using Pooled Projection Data 158
Wrap Factors on Prime Arrays 159
Primes with Common Wrap Factors 160
Coincident Projection Segments 161
Reconstruction Technique 163
Reconstruction via the Frequency Domain 163
Fourier Analysis of ADRT Projections 165
Reconstruction Technique 165
Algebraic Inversion and Filtered Back-Projection 167
Image Analysis and Processing with the FRT 169
Image Compression 170
2D Image Convolution 170
Image Representation 171
Sliding and Scaling Window FRT 171
Adaptive Transform for View Window Translation 172
Relative Implementation Time, eta 174
Adaptive ADRT Transform for View Window Translation 175
Adaptive Transform for View Window Scaling 175
Reducing View Window Size (p'' < p')
Enlarging View Window Size (p'' > p')
Applications of Redundancy in FRT Projections 178
Injecting Redundancy into the DRT Projections 180
FRT Ghost Functions 181
Key Requirements 181
Reconstructing I from Redundant DRT Projections 182
Cryptography 183
Future Directions 186
Acnowledgments 189
References 189
Ray Tracing in Spherical Interfaces Using Geometric Algebra 196
List of Symbols 197
Introduction 198
Finite Skew Rays 199
Paraxial Skew Rays 200
Finite Meridional Rays 201
Outline 203
Geometric Optics 203
Clifford (Geometric) Algebra Cl3,0 203
Propagation 205
Propagation Distance and Normal Vector 206
Passover and Concavity Functions 206
Some Special Cases 207
Refraction 208
Asymmetric Exponential Form 208
Symmetric Exponential Form 209
Addition Form 210
Product Form 211
Reflection 211
Asymmetric Exponential Form 211
Antisymmetric Exponential Form 211
Addition Form 212
Product Form 212
Other Alternative Forms 212
Finite Skew Rays 213
Spherical Coordinates 213
Radial Basis Vector 213
Products of Radial Vectors 215
Addition of Radial Vectors 216
Propagation 218
Refraction 219
Reflection 220
Paraxial Skew Rays 220
Paraxial Approximations and Sign Functions 220
Paraxial Angle and Axial Direction Function 221
Sum and Difference of Two Paraxial Angles 222
Relative Direction and Concavity Functions 223
Propagation 225
Initial Relative Position 225
Propagation Distance 226
Final Position 226
Normal Vector 227
Refraction 228
Angles of Incidence and Refraction 228
Refracted Ray 229
Reflection 231
Finite Meridional Rays 232
Polar Coordinates 232
Propagation 234
Refraction 235
Polar Angle of Refracted Ray 235
Bessel-Conrady Refraction Invariant 236
Reflection 237
Polar Angle of the Reflected Ray 237
Reflection Identities 238
Summary and Conclusions 239
Acknowledgment 240
References 240
Prolate Spheroidal Wave Functions and Wavelets 242
Introduction 243
Notation and Background 244
Shannon Sampling Theorem 245
Maximization Problem 246
The Lucky Accident 248
Another Lucky Accident (How Lucky Can You Get?) 250
Finite Approximations 253
Some Properties of Prolate Spheroidal Wave Functions 253
Fourier Transforms 254
Discrete Orthogonality 255
A Sampling Theorem Based on PSWFs 258
Discrete Sequences 260
Impulse Trains 261
Discrete Wavelet Theory 261
The Shannon System 262
An Introduction to Orthogonal Wavelet Theory 263
Multiresolution Analysis 263
Example 265
Mother Wavelet 266
Prolate Spheroidal Wavelets 268
PS Wavelets in Paley-Wiener Space 269
Dilation Equations 270
Mother Wavelet 272
Approximation by PS Wavelet Series 274
Numerical Example 276
What's Wrong with Wavelets 279
Differentiation 280
Translation 282
Other Operators 284
Dilation 284
Multiplication by Trigonometric Functions 284
Convolution. 284
Two Applications 286
Density Estimation with PSWFs 286
PS Semiwavelets in Density Estimation 290
Computerized Tomography 293
Background 293
Reconstruction Algorithm 295
Computer Implementation 298
Higher Dimensions 299
Maximization in Higher Dimensions 300
An Eigenvalue Problem 300
Examples 302
Sampling Function 303
Examples 303
The PS Wavelets 304
Scaling Function 304
Change of Scale 306
Mother Wavelet 308
Computation of PS Scaling Functions 308
References 310
Index 314

Textauszug

Retrieval of Shape from Silhouette

Andrea Bottino; Aldo Laurentini    Dipartimento di Automatica e Informatica, Politecnico di Torino, 10129, Torino, Italy

I INTRODUCTION

A Reconstructing Three-Dimensional Shapes: General Techniques

The reconstruction of three-dimensional (3D) shapes is a fundamental research field in computer vision. A large number of techniques have been discussed and implemented, depending first on the type of sensors used. Active 3D scanning is currently a leading technology. Most active 3D scanners use ranging techniques (time of flight, phase comparison) or triangulation with laser beams. Their main feature is producing depth maps that are close to the final 3D shape (Figure 1).

Figure 1 3D scanners.

However, 3D scanners are expensive and are affected by several limitations. They are rather invasive, different equipments are required for scanning objects of different sizes, scanning outdoor large scenes presents several problems, and scanning times are not adequate for real time applications, such as capturing the shape of objects in motion.

For these reasons, in several practical situations traditional image-based computer vision approaches are more effective. For instance, an important emerging area usually requiring image-based approaches is the analysis of human body movements (Figure 2).

Figure 2 The analysis of posture and motion of the human body is a popular computer vision area.

Several passive approaches, based on 2D images captured by inexpensive cameras, have been proposed, usually referred to as shape from X, where X stands for some image feature that can be used as a 3D shape cue (Aloimonos, 1988). Among them are stereo (disparity), texture, motion, focus, shading, and silhouettes. An advantage of image-based approaches is that they can easily supply 3D textured reconstructed objects. Actually, most of these approaches require textured objects, or lines called image contours.

Some of these approaches, such as shape from shading (Zhang et al., 1999), require a number of hypotheses and conditions that seldom take place in practice. The most effective approaches are shape from stereo and shape from contours. Shape from stereo requires images from (at least) two cameras and matching algorithms for determining corresponding points in the two images (Trucco and Verri, 1998). From the different positions in the images of the corresponding points (stereo disparity), and camera geometry, it is easy to find the 3D position of a point. Shape from motion in principle is an extension of shape from stereo, since it considers multiple images of the same objects taken with the same camera from different relative positions, and also requires finding correspondences in the various images. The purpose of this work is to discuss the theory and practice of shape from silhouettes.

B Shape from Silhouettes

Many algorithms for reconstructing 3D objects from two-dimensional (2D) image features are based on particular lines called image contours. Actually, these lines can be also used for recognizing 3D objects. This approach mimics to some extent the human vision, since we are often able to understand the solid shape of an object from a few image lines laid out on a plane (Gibson, 1951; Koenderink and van Doorn, 1979).

In general, from an image of a 3D object we can extract various kinds of lines, separating areas of different intensities or colors. Some of them are not directly related to the 3D shape, and correspond to different surface properties, or to abrupt changes of the incident light. Other lines are directly related to the surface of the object. They are usually called edges and occluding contours (see Figure 3).

Figure 3 Different types of image lines.

The edges are the projections of the creases of the object (surface normal discontinuities), and are not present in images of smooth surface objects. The lines called occluding contours (apparent contours, limbs) are the projection onto the image plane of the contour generators of the objects. A contour generator is a locus of points of the object surface where there is a depth discontinuity along the line of sight.

The lines related to the 3D shape (occluding contours and edges) produce line drawings that can be organized into the aspect graph, a user-centered representation of 3D objects first proposed by Koenderink and van Doorn (1979).

With the word silhouette we indicate the area of the image bounded by the contours that occlude the background. Sometimes the word silhouette is used for the boundary of this area. The idea of using silhouettes to reconstruct 3D shapes was first introduced in the pioneering work of Baumgart (1974). Since then, several variations of the shape from silhouettes methods have been proposed. For example, Martin and Aggarwal (1983) and Kim and Aggarwal (1986) used volumetric descriptions to represent the reconstructed shape. Potemesil (1987), Noborio et al. (1988), and Ahuja and Veenstra (1989) used octree data structure to accelerate the reconstruction process. Shape from silhouettes has also been used by Szeliski (1993) to build a noninvasive 3D digitizer using a turntable and a single camera. Other recent techniques (Kutulakos and Seitz, 2000; Matusik et al., 2001; Slabaugh et al., 2003) stem from this idea.

In principle, reconstruction from silhouette requires backprojecting the silhouettes from the corresponding viewpoints to obtain solid cones. They are bounded by the circumscribed cones formed by the half-lines tangent to the object. Since the object must lie inside each cone, it must also lie inside their intersection R, which summarizes the information provided by all silhouettes and viewpoints (Figure 4). This reconstruction technique is called volume intersection (VI).

Figure 4 Volume intersection. © 2003 IEEE.

Silhouette-based techniques are popular because silhouettes are usually easy to extract from images. This operation is particularly fast and robust with controlled background, or for objects in motion with respect to the background. Another important feature of the silhouette-based techniques is that they are convenient for real time applications.

However, one drawback of this approach is that, depending on the object, the information provided by its silhouettes could be insufficient to fully understand a 3D concave shape. The problem, qualitatively perceived by several researchers in the field, received a full quantitative solution in Laurentini (1994).

This chapter is organized as follows. First we discuss the theoretical problems raised by silhouette-based image understanding. In particular, we present and develop the concept of the visual hull of an object, which allows questions such as whether the 3D shape of an object be fully understood from its silhouettes to be answered. We will see that this geometric entity allows this and other basic questions related to the silhouettes approach to be answered. It will be shown that the visual hull and the aspect graph of an object are strictly related. The computation of the visual hull will be discussed for polyhedra, object of revolution, and smooth surface objects. In general, VI supplies an object that is not coincident with the object to reconstruct: the problem of inferring the real shape from the object reconstructed will be also discussed, introducing the concepts of hard and soft points. Based on these concepts, we will show how an interactive reconstruction approach can be outlined. Finally we will deal with the problem of reconstructing an object when we have its silhouettes, but no information about the relative positioning of the corresponding viewplanes.

The last part of the chapter is devoted to survey practical shape from silhouettes algorithms.

II THE VISUAL HULL

Reconstructing as well as recognizing 3D objects using silhouettes requires facing some problems inherent to the approach. An intuitive analysis of some examples will help focus the problems raised by this technique. Let us consider the concave objects O1 and O2 in Figure 5. The difference between them consists of a small cube inside the concavity. It is not difficult to intuitively realize that this cube does not affect any of the silhouettes of the object, provided that the corresponding viewpoint is not “too close” to the object (a precise formulation of this statement will be given later). The example shows that we might not be able to distinguish different concave objects using their silhouettes.

Figure 5 O1 and O2 cannot be either exactly reconstructed or distinguished using their silhouettes. © 1994 IEEE.

Let us consider now the reconstruction from silhouettes of O1 and O2. Since the silhouettes relative to not “too close” viewpoints are equal for the two objects, we cannot exactly reconstruct either O1 or O2. On the contrary,...

Produkt-Details

• Erscheint lt. Verlag: 29.7.2011
• Sprache: englisch
• Themenwelt: Sachbuch/Ratgeber
• Themenwelt: Naturwissenschaften ► Physik / Astronomie ► Optik
• Themenwelt: Technik ► Bauwesen
• Themenwelt: Technik ► Elektrotechnik / Energietechnik
• Themenwelt: Technik ► Maschinenbau
• ISBN-10: 0-08-046276-6 / 0080462766
• ISBN-13: 978-0-08-046276-9 / 9780080462769