|
The Reconstruction Algorithm
|
|
An overview of the 3 step iterative process in the poxel algorithm
|
|
The interative reconstruction process consists of three phases. As depicted in this Figure
|
|
|
The quality of the correspondence between multiple observations is a measure of our confidence that this location in space is filled
|
|
In the first phase we measure the quality of the correspondence between multiple observations of each point in space. The quality of this correspondence is a measure of our confidence that this location in space is responsible for some portion of the observations. This situation is illustrated in this Figure
, in which three images observe a particualr voxel. If we assume that each image has an unobstructed view of the voxel, the quality of their correspondence is an indication of the likelyhood of the presence of a uniformly colored object at that location in space.
|
|
In general however, each observation will not be completely unobstructed. Initally we begin with the null-hypothesis, that each location in space equally contributes to each observation. However, as we progress though successive iterations, the distribution with change.
|
|
Thus the quality of a correspondence, qi(x,y,d) between a observation from camera i at location (x,y) at a depth of d and the observations from the remaining cameras is discribed by:
|
|
qi(x,y,d) = e|pxli(x,y) - pxlavg-i(x,y)|2 / σ 2
|
|
which is a Gaussian weighting of the distance between pxli(x,y), the observation in i, and
|
|
pxlavg-i(x,y) = sumjneq ipxlj(x,y) PoxelidCDFj(x,y,d)
|
|
is the average observation from the remaining cameras weighted, by the probability that they are not occluded, and contribute to the observation. The calculation of PoxelidCDFj(x,y,d), the probability that a given voxel is unoccluded, will be discussed below.
|
|
|
The integral of all the poxels which can contribute to a given point in a camera must integrate to one.
|
|
The quailty of correspondence measurements qi(x,y,d) for all locations (x,y) in all observed observed images i, can then be used to update our estimates of the probability of contribution of each voxel to each observation, PoxelPDFi(x,y,d). To do this we make use of the following assumption: each non-background color observation is generated by something in the volume (see this Figure
). Equivalently, with probability one there is a cause for each observation. Thus the integral of all the poxels which can contribute to a given point in a camera must integrate to one. Yielding the streightforward update rule:
|
|
PoxelPDFi(x,y,d) = qi(x,y,d) / sumk(qi(x,y,k))
|
|
|
The quailty of correspondence measurements can be used to update our estimates of the probability of contribution of each voxel to each observation.
|
|
The use of a special background color can be eliminated by extending the definition of our space to include a region at infinity. However, care must be taken when viewing this volume to prevent the background observed from one point of view from occluding the virtual camera at another point of view.
|
|
Once we have updated our poxel estimates, we can proceed to compute the probability that each voxel is unoccluded, PidCDFj(x,y,d). The probability that a voxel is occluded is equal to 1 minus the sum of the probabilities of closer voxels being seen. Thus to compute the probability of occlusion we first compute the cumulative probability distribution (CDF) of the PoxeljPDF by integrating along the ray from the observation image through the poxel space, and keeping track of each of the partial sums. It is important that this integration be ordered so that nearer pixels occlude farther ones. Numerically:
|
|
PoxelCDFi(x,y,d) = sumk<d(PoxelPDFi(x,y,k))
|
|
We then compute the differential cumulative probability distribution (dCDF), which is the difference between the CDF and the PDF:
|
|
PoxeldCDFi(x,y,d) = PoxelCDFi(x,y,d) - PoxelPDFi(x,y,d)
|
|
PoxeldCDFi(x,y,d) is the probability that a ray is absorbed by some closer voxel, which is also the probability that the voxel is occluded (this Figure
). To compute the probability that a voxel is unoccluded we simply take its probability complement:
|
|
PoxelidCDFi(x,y,d) = 1 - PoxeldCDFi(x,y,d)
|
|
|
The differential cumulative probability distribution is the probability that a ray is absorbed by some closer voxel and is also the probability that the voxel is occluded
|
|
|
|
The inverse differential cumulative probability distribution is the compute the probability that a voxel is unoccluded.
|
|
Once computed the PoxelidCDF is used to restimate the quality of the correspondences. The computation of the correspondence qualities will change due to new beliefs about occlusion encapsulated in the PoxelidCDF.
|
|
|
In cases where high levels of occlusion are found, the idCDF is low, indicating that that observation has little bearing on the correspondence quality.
|
|
|
Alternatively, in cases where little occlusion is expected the idCDF is high, resulting in a large contribution to any resulting mismatch.
|
|
Two cases are illustrated in Figures
*
*
above.
|
|
After several iterations of the system (again see this Figure
) the system converges to the distribution in which all the poor correspondences have been explained by occlusions or transparances.
|
Page loaded on May 01, 2024 at 08:57 AM.
Page last modified on
2006-05-27
|
Copyright © 1997-2024, Jeremy S. De Bonet.
All rights reserved.
|
|
