Marc Levoy
Computer Science Department
Stanford University
Click on a picture to see an uncompressed .tif file.
Click on the .tcl file to edit the spreadsheet source code using Emacs.
Click on the .sht file to run the spreadsheet program on that .tcl file.
epi_4in1point_convolve5.tcl
epi_4in1point_convolve5.sht
epi_4in1cyl_convolve5.tcl
epi_4in1cyl_convolve5.sht
epi_4in1cyl_notex_convolve5.tcl
epi_4in1cyl_notex_convolve5.sht
Some experiments with new backprojection filters.
In epi_4in1point_convolve5, the top row shows the previously used filter from Kak and Slaney ("-dbackprojection" option in the spreadsheet program).. The second row shows a filter from Tanaka79 ("-tbackprojection") with a = 0.0. This should be the ideal correction filter, i.e. with no frequency cutoff, although of course the filter table is finite. The third row shows a Tanaka79 filter with a = 0.25, which is supposedly equal to a filter from Shepp and Logan74. Shown below each filter is, from left to right, the filtered epipolar image, the filtered backprojection, and a constrast-enhanced version to amplify small artifacts. Both Tanaka filters look cleaner than the Kak filter. The two Tanaka filters are different from one another, but I can't judge their relative merits.
In epi_4in1cyl_convolve5, the top row shows the Kak filter, the middle row shows the Tanaka filter with a = 0.0, and the bottom row shows the Tanaka filter with a = 0.9, an extreme value. The bottom row is definitely too thin. The middle row looks cleaner than the top row, but only slightly.
In epi_4in1cyl_notex_convolve5, the top row shows the Kak filter, the middle row shows the Tanaka filter with a = 0.0, and the bottom row shows the Tanaka filter with a = 0.25, the Shepp and Logan value. This set of comparisons seems to show that the Kak filter is sharpest, the Shepp filter is blurrier, and the ideal filter is blurriest. This succession is in line with the succession of filter shapes (leftmost column of opened cells), in which the ideal rises slowest from its negative lobes, the Shepp faster, and the Kak actually overrises, then settles back down.
In summary, the so-called ideal correction filter looks possibly the best. That's convenient, because it simplifes derivations in higher dimensions!
Note that reconstructions using the Kak filter with small kernels aren't good. See epi_4in1disk_convolve3 and epi_longkernel.
epi_variance_unfilt.tcl
epi_variance_unfilt.sht
epi_variance_unfilt2.tcl
epi_variance_unfilt2.sht
epi_variance_filt.tcl
epi_variance_filt.sht
epi_variance_filt2.tcl
epi_variance_filt2.sht
epi_variance_filt2a.tcl
epi_variance_filt2a.sht
Trying to extract features from untextured scenes by computing the variance of rays passing through each scene voxel. Compare to epi_diffcolor, which is a derivative with respect to angle at each voxel.
epi_variance_unfilt shows the case of unfiltered backprojection. The top row of cells (and the top table below) shows the unmasked case. Cell c5 shows basic backprojection, divided by 4.0 for normalization, and cell c7 shows the square of the (normalized) backprojection. This is E(X)^2, u^2 (u means the "mean") if we assume an unbiased estimator. Cell l5 shows the backprojection of a squared epipolar image (visible in column g), again divided by 4.0. This is E(X^2). Finally, cell m7 shows the difference E(X^2) - u^2, which is the variance (see derivation in Hoel, p. 94). The variance drops near the object surfaces, but is not zero. This is due to pollution from unmasked rays. For comparison, the same result for each of the four slabs is shown in cells m1 through m4. In these cells, there is no pollution of the frontmost objects as seen from each direction. These are therefore black (zero variance), as expected.
The second row of cells (and the second table below) shows the occupancy-masked (but not occupancy-multiplied) case. The mask employed was a perfect (synthetic) mask derived from the Inventor cross-section (see cell b5 in epi_variance_filt2). In this case, cell d5 is divided by the actual visibility (cell f5), which ranges from 0.0 to 3.3 (nearly 4.0). The variance drops to zero near the object surfaces, as desired. Cell l8 shows a ramped version with the centers of the objects themselves masked out. This is a nice result. However, features are blurred due to the use of unfiltered backprojection. Presumably, features in the variance image are consequently also blurred.
epi_variance_unfilt
For the first three images, "snoop" is of pixel (50,110) (just below green cube), green component (1). In all tables, "proj()" means "backprojection of". proj() is divided by 4.0 in unmasked case or sum(visibility) in masked case, and optionally normalized (in epi_variance_filt2 and filt2a).
unfiltered unmasked backprojection X (a1) proj(X) (c5) proj(X)^2 (c7) X^2(g1) proj(X^2) (l5) diff (m7) maxval snoop maxval snoop maxval maxval snoop maxval snoop maxval 255 164 210 26638 44100 65025 32254 48412 5615 11866
unfiltered occupancy-masked (but not occupancy-multiplied) backprojection X (a1) proj(X) (d5) proj(X)^2 (d7) X^2(g1) proj(X^2) (i5) diff (j7) maxval snoop maxval snoop maxval maxval snoop maxval snoop maxval 255 207 254 42930 64931 65025 50077 64964 7146 16229
epi_variance_filt shows the case of filtered backprojection (using the standard backprojection filter). Negative values in backprojections (due to occlusions) are clamped to zero throughout. These clamping cells are left in the pipeline in all cases, which explains what appears to be unnecessary cells in these other cases. (I forgot how to use "max" to clamp; hence the convoluted code for clamping.) This case doesn't work at all; the terms of of vastly unequal magnitude, and the results are garbage.
epi_variance_filt
filtered unmasked backprojection X (a1) proj(X) (c5) proj(X)^2 (c7) X^2(g1) proj(X^2) (l5) diff (m7) maxval snoop maxval snoop maxval maxval snoop maxval snoop maxval 255 8 29 73 829 65025 1697 7562 1623 6733
filtered occupancy-masked (but not occupancy-multiplied) backprojection X (a1) proj(X) (d5) proj(X)^2 (d7) X^2(g1) proj(X^2) (i5) diff (j7) maxval snoop maxval snoop maxval maxval snoop maxval snoop maxval 255 11 73 127 5331 65025 2851 20899 2723 16929
In epi_variance_filt2, I tried scaling E(X) (u) up to 255.0 before squaring it and E(X^2) up by the same amount (in this case implicitly after it is squared). This inserts a missing normalization into the backprojection process. Usually, the lack of such normalization is unimportant, but in the presence of non-linear operators (like squaring), it is suddenly important. As in the other images, cells m1 through m4 show these results for unmasked backprojection for each of the four slabs. epi_variance_filt2a is the same except that cells m1 through m4 show these results for masked backprojection. This begins to show low variances near object surfaces, but only in some places.
epi_variance_filt2
filtered unmasked backprojection, scaled up to 255.0 X (a1) proj(X) (c5) proj(X)^2 (c7) X^2(g1) proj(X^2) (l5) diff (m7) maxval snoop maxval snoop maxval maxval snoop maxval snoop maxval 255 75 255 5738 65024 65025 15029 66972 9291 18229
filtered occupancy-masked backprojection, scaled up to 255.0 X (a1) proj(X) (d5) proj(X)^2 (d7) X^2(g1) proj(X^2) (i5) diff (j7) maxval snoop maxval snoop maxval maxval snoop maxval snoop maxval 255 39 255 1556 65023 65025 9957 72990 8402 30484
epi_variance_filt2a
"snoop" here is of left slab, pixel (31,131) (left of green cube), green (1). The "diff" for this pixel is visible in cell m4. The multiplier for cell d4 is 255.0/29.116 = 8.7581. Multiplying this by d4 gives 59, and squaring gives 3551, as shown in register temp23. Multiplying i4's 918 by the same 8.7581 gives 8044 (in register tempm3, not shown in table). Subtracting 8044 - 3551 = 4493 (in register temp43).
filtered occupancy-masked backprojection, scaled up to 255.0, left slab only X (a4) proj(X)(d4) proj(X)^2(temp23) X^2(g4) proj(X^2)(i4) diff(temp43,m4) maxval snoop maxval snoop maxval maxval snoop maxval snoop maxval 255 7 29 3551 65024 65025 918 8979 4493 65024 additional scaling (x8.75 x1.52) to make u^2 match sum(X^2) in pixel (31,131): 255 7 29 8205 150229 65025 918 8979 -160,0 16226 under these same conditions, pixel (50,110) (just below green cube): 9 4528 1131
I think I've decided that normalization is impossible in the case of filtered backprojection unless we know the (spatially varying) pattern of streaks introduced by occlusions, i.e. unless cell f5 (the visibility mask), which we use to normalize the backprojections, includes streaks. I wonder if it is possible to compute such an image?
epi_variance_unfilt2 compares untextured (top row) and textured (bottom row) scenes. From left to right are the mean, standard deviation (sqrt of variance), a ramped mask derived from the stddev, and the variance of the back and left slabs. Not surprisingly, the untextured scene gives lower variances for unoccluded features like the left side of the green cube, but the textured scene gives better results for occluded features like the left side of the central white cube. These results are for masked backprojection. See epi_variance_tex and epi_variance_texes for examinations of per-slab variance for the textured scene using unmasked backprojection.
epi_4in1disk_convolve3.tcl
epi_4in1disk_convolve3.sht
Demonstration that filtered backprojection using a small version of the backprojection filter kernel doesn't produce good results, at least on untextured objects.
The object is the same disk used in epi_4in1disk_convolve2, and the filter is the same (old) backprojection filter. From top to bottom, the cells (and closeups) show filtered backprojections using kernels of (reflected) length 9 pixels (the usual), 21 pixels, 41 pixels, and 255 pixels. The latter is the length used in epi_4in1disk_convolve2. Clearly, a 9-pixel filter creates significant artifacts.
Interestingly, these artifacts don't arise in textured images. See epi_longkernel below.
epi_longkernel.tcl
epi_longkernel.sht
Some experiments to evaluate the effect of using short backprojection filter kernels, as I have been doing.
The leftmost two columns of cells show the Tanaka (ideal) correction filter (see epi_4in1point_convolve5), and the rightmost columns show the usual Kak filter. The leftmost cells in each pair of columns is c5, the filtered backprojection, and the rightmost cells are g8, the unramped, unblurred mask obtained using the usual gradient operators. From top to bottom are shown the untextured scene with a 9-tap filter, the untextured scene with a 41-tap filter, the textured scene with a 9-tap filter, and the textured scene with a 41-tap filter. There is a noticeable improvement in the performance of the Kak filter applied to the untextured scene when the kernel is lengthened (top row, right pair of cells, versus second row, right pair of cells), but little difference when applied to the textured scene (third and fourth rows). In particular, the background is "cleaner", i.e. closer to gray (i.e. to zero) when the kernel is lengthened. The Tanaka filter (right pair of columns) is not particularly sensitive to kernel length.
In conclusion, the validity of my experiments thus far on textured scenes are validated, but I should either lengthen my filter or switch to Tanaka's filter when using untextured scenes.
epi_reproject3.tcl
epi_reproject3.sht
epi_reproject4.tcl
epi_reproject4.sht
Experiments with different occupancy-based and visibility-based normalizations during and after occupancy-masked backprojection and their effects on creation of a second occupancy mask. Compare to epi_reproject and reproject2 (in log #1).
In epi_reproject3, cell c5 shows filtered backprojection of the textured scene. A short Tanaka filter was used. Cell g8 shows the resulting unramped and unblurred mask. The next two columns of cells show occupancy-masked backprojection and resulting second masks. The ramped but unblurred mask was used in the second backprojection. The middle row shows the default case, which should be equivalent to the results in epi_reproject2 (except that a zillion other things have changed). The top row shows the effect of dividing the backprojection by the summed visibility (cell f5). Weak features (like the topmost sphere) get weaker, but features in heavily occluded regions (like the bottom edge of the green cube and the top edge of the central white cube) get stronger. The bottom row shows the effect of multiplying by the summed visibility instead of dividing. Weak features are strengthened, but features in heavily occluded regions almost disappear. This is clearly the wrong direction to go.
The rightmost two columns show the result of the -nooccmultiply option, which causes each backprojected ray to *not* be multiplied by local occupancy before being added to the result for the voxel. Not multiplying by occupancy causes weak features to be strengthened. Dividing by summed visibility afterwards reweakens these same features a bit, but strengthens features in heavily occluded regions. This seems to be the right combination of methods. See epi_reproject5,6 for further comparisons and discoveries.
In epi_reproject4, three iterations of this reprojection were performed, forming a sequence of four masks in all. The case described above is shown in the bottom row. Here, the mask very slowly fades out (losing about 20/255.0 in value at each pixel per iteration), but doesn't change character noticeably. In the middle row, ramped and blurred masks are used in each reprojection (and are shown here). The weak right wall of the green cube seems to improve on each iteration, but the masks still fade out. In the top row, the ramping is changed to eliminate this fadeout. Now the green cube stays nearly constant in value, and its right wall improves. The topmost sphere still fades out. Nevertheless, this is possibly my best backprojection-only iteration to date, as well as my best mask to date, at least for the green cube.
By the way, since I'm no longer multiplying color by opacity during occupancy-masked backprojection, I can now validly add the backprojections of the individual slabs together in preparation for forward projection. I had previously decided that I couldn't (see epi_color_correct5 in log #1.) However, since I am no longer multiplying color by opacity during backprojection, I must now perform this multiplication during forward projection. I have therefore added this multiplication by occupancy to the forward projection code. As with backprojection, it can be disabled using -nooccmultiply.
epi_reproject5.tcl
epi_reproject5.sht
epi_reproject6.tcl
epi_reproject6.sht
More comparisons regarding occupancy multiplication and visibility normalization. Essentially a continuation of epi_reproject3,4.
In epi_reproject5, cells c5, c6, f7, and e7 shows the first filtered backprojection, unclamped and clamped, and the usual mask derived from it, unblurred and blurred. The row of cells to the right of f7 show an occupancy-masked and visibility-masked backprojection with -occmultiply. The first two cells use the blurred mask (cell e7), and the second two use the unblurred mask (cell f7). The second row uses -nooccmultiply, i.e. no occupancy masking, with no visibility normalization of the sum of the four backprojections. The third row includes visibility normalization, i.e. the sum of the four backprojections is divided by the sum of the visibility masks, which is visible at the bottom.
Two effects are evident in this image. First, the features in visibility-masked backprojections, whether occupancy-masked or not, tend to shift toward the outside of the opaque cubes, since rays are erased as they pass through the occupancy mask toward the inside. This shifts the placement of features in the recomputed (i.e. second) mask. I hadn't noticed this effect before. Visibility normalization helps fix this problem, but since visibility is typically low inside an opaque cube, the normalization may be unstable. See epi_causal for a further demonstration and discussion of this problem. Second, although visibility normalization evens out the bottom edge of the green cube in the second mask, it skews the magnitudes of the bottom edge of the central white cube. Normalization also nearly erases the white sphere.
A fundamental problem here, and possibly the cause of the adverse skew effects I'm seeing, is that the visibility mask is dropping to zero as we cross the cube boundary. This drop should have two effects. First, where visibility is low, the results normalization are unstable, as noted above. Second, what I'm really interested in visibility in the region around each point on the object surface but *before* the rays actually strike the surface and visibility begins to drop. In summary, I have both a division-by-zero problem and a self-shadowing problem.
In epi_reproject6, I compare normalizing the backprojection versus normalizing the second mask, and I try some nonlinear ramping in both cases. The top row represents, from left to right, a second mask computed from a backprojection generated with -nooccmultiply from the blurred mask (from cell e7), a division of this mask by the visibility mask (from cell f5), and a division of this mask by the sqrt of the visibility mask (from cell f6). The second row shows second masks computed from normalized backprojections as in the other examples where the normalizations are performed alternatively with the visibility mask or with the sqrt mask.
Applying the normalization to the mask seems to yield approximately the same results as applying it to the backprojection, despite the presence of some non-linear operators in my mask generation (i.e. gradient) pipeline. Using the sqrt of the visibility mask seems to yield results halfway between normalizing and not normalizing; some edges are improved, some are degraded, and the sphere is weakened but only somewhat. This is basically a compromise solution.
In another experiment (not shown), I tried normalizing the backprojection of each individual slab by that's slab's visibility mask. This doesn't work at all; it violates the theory of filtered backprojections, leading to huge streak artifacts.
See also my discussion of visibility normalization versus color equalization in epi_occupdate3,4.
An attempt to introduce a shadow bias in the visibility masks. It doesn't work.
The left column of cells show unbiased visibility masks for each slab, and the sum is shown in cell f5. The right column shows biased masks (by 2 voxels), with the sum to the right. For reference, cell f7 shows the mask, which is the usual unblurred mask.
The reason biasing doesn't work is simple. Since biases are in a single direction (horizontal or vertical), but (parallel projection) views within a slab have a variety of directions (-45 degrees to +45 degrees), the bias is appropriate only for one view within the slab. Thus, front-facing walls (relative to each slab) are biased correctly, but side walls are not. The correct solution for biasing is to bias along the vector field direction.
In an experiment (not shown), I tried biasing using the vector field. Specifically, backproject_bias.c_ allows biasing along a one-slab vector field as it is being computed. Unfortunately, this isn't good enough; one must bias along the full-surround vector field in order to avoid double edges. Unfortunately, the latter is tricky. First, the full-surround vector field may point back toward you, in which case you would presumably clamp the bias to zero. Second, the full-surround vector field has saddles and sinks, i.e. areas of zero magnitude. Third, the field disappears just where you need it, at object surfaces.
epi_diffcolor.tcl
epi_diffcolor.sht
epi_diffcolor2.tcl
epi_diffcolor2.sht
Trying to extract features from scenes by computing the derivative of color with respect to angle for the rays passing through each scene voxel. Compare to epi_variance, which is a mean-adjusted L-2 norm at each voxel.
In epi_diffcolor, the top four cells show unfiltered backprojection, and the lower four cells show filtered backprojection. Differencing directionally adjacent rays makes no sense in the case of filtered backprojection due to the backprojection filter; these lower four results are included only for completeness. Within each set of four, the top row shows results for the untextured scene, and the second row shows results for the textured scene. Within each row, the left cell shows unmasked backprojection, and the right cell shows visibility-masked but not occupancy-masked backprojection using a previously computed standard (unblurred) occupancy mask. To facilitate comparison with epi_variance, the top row includes one extra cell, a backprojection masked using the perfect (synthetic) mask.
The case of unfiltered backprojection of the untextured scene is clearly best, In theory, derivative (or variance) pipelines should yield a clean line of zeros at the object faces on a textured scene. The reason they do not is because for a color discontinuity (or high-frequency texture), the variance drops to zero only right at the surface, and this drop may not be detected in the context of a discrete-space (i.e. voxel array) implementation. I finally understand and analyze this problem, at least for variance pipelines, in epi_variance_tex. An additional factor in unfiltered backprojections is that there is blurring among adjacent voxels. This may excacerbate the lack of a clean zero-variance zone at the surface. Filtered backprojection, however, cannot be employed in a derivative pipeline because backprojection filtering is only valid if the rays are summed at a voxel, not if they are differenced and then the absolute value taken. So it seems that derivative pipelines are doomed to work only on untextured scenes (or scenes that contain only low-frequency textures), at least when discrete scene representations (i.e. voxel arrays) are employed. Unfortunately, this problem also arises when two differently colored faces abut (see the discussion in epi_diff_opacity).
Returning to the images, note that the red cube (upper-right) does not yield as low a sum of differences, probably because it is specular. (Later experiments suggest that the absence of the red cube is more due to its darkness. See epi_difference.) These results looks similar to those in epi_variance_unfilt. According to theory, the latter should be sharper due to the squaring. Moreover, the latter should be more sensitive to smooth but non-constant (or bi-modal) distributions, such as a homogeneously colored cube on a differently colored background, as compared to the sum of differences, which will respond to this situation only at two places - at the cube's two silhouette edges. Unfortunately, these derivative experiments were not run on each slab individually, and the consequent pollution makes it difficult to verify this hypothesis. See epi_occupdate, which includes experiments on individual slabs, for a further discussion (and partial resolution) of this issue.
In epi_diffcolor2, several iterations of differencing are tried. The top row shows the sum of differences, the second row shows the max of R,G,B, and the third row shows a nonlinear (inverse) ramping thereof. From left to right, each ramping is more nonlinear, and on each backprojection the overall opacity is cranked up. Cell b7 shows the last ramping (a power of 20) applied directly to the first mask to verify that the iteration is actually improving the mask. It is. In particular, each iteration reduces pollution. For example, the improvement in the homogeneity of the mask for the white sphere is dramatic. The center cube is still a mess, however, and the red cube is still missing. These effects are possibly due to my application of nonlinear rampings without first adjusting for differences in the visibility (i.e. light strength) of different features and for relative color (i.e. darkness). The second problem is disscussed in greater depth at the end of epi_occupdate and is addressed in epi_difference.
In another experiment (not shown), I tried several iterations of variance, but I can't seem to extract a good mask from the first iteration, probably due to pollution. In retrospect, I should have tried extracting masks from the backprojections of individuals slabs rather than from the combined backprojection of all slabs; cells m1 through m4 in epi_variance_unfilt suggest that this might have worked better, at least in the first iteration.
All of these results should be interpreted with caution because real (i.e. digitized) imagery will contain noise, degrading the contrast between homogenously colored voxels and others. And of course voxels in homogenously colored concavities cannot be reconstructed at all using this technique; in that case, texture is essential.
epi_occupdate.tcl
epi_occupdate.sht
epi_occupdate2.tcl
epi_occupdate2.sht
Using a nonlinear ramping of the derivative of color with respect to angle to compute on-the-fly, i.e. per voxel row, an occupancy mask and thereby mask further backprojection within each slab. (In the implementation, the starting occupancy mask is initialized to all-transparent, and backprojection is performed -nooccmultiply, so the only masking performed is that which arises from the ramped derivatives.)
In epi_occupdate, the 2nd and 3rd to rightmost two columns represent the results for two backprojections with alternative rampings. The top row of cells show the color derivatives as in epi_diffcolor, the second row shows the opacity mask for the front slab, and the third row shows the product of the opacity masks for the four slabs. The rightmost column shows the other three slabs for the ramping used in the 2nd to rightmost column. Observe that the backprojected derivatives fade out toward the back of the scene due to the masking. The gradually decreasing scene visibility can be appreciated in column g of the spreadsheet. The leftmost of these two columns is ramped so as to accumulates nearly zero opacity, i.e. to perform essentially no masking. To verify my computations, the column to its left shows results from unmasked backprojection and a nonlinear ramping thereof. Note that these two columns match. The extreme leftmost column shows an alternative nonlinear ramping of the unmasked derivatives. In epi_occupdate2, several other rampings of the masked backprojection are shown.
The ramping consists of taking the max of R, G, and B, dividing the sum-of-weights-normalized sum-of-derivatives by diff_prescale, raising it to the diff_power, then multiplying by diff_postscale. The effect of diff_postscale is to decide what value of the normalized summed derivative maps to 1.0 before the power function is applied. The maximum normalized derivatives range from 8 to 18, so setting diff_prescale to 12 performs some clamping. The effect of diff_postscale is to map the ramped derivatives to occupancy Thus, a setting of 0.01 means that the maximum occupancy will be 0.01, which explains why this column is nearly identical to the unmasked case. The rampings in the various columns of the two images are as follows:
epi_occupdate
column 1 2 3 4 diff_prescale 18 12 12 12 diff_power 10 10 10 10 diff_postscale n/a n/a 0.01 0.05
epi_occupdate2
column 1 2 3 diff_prescale 12 12 12 diff_power 20 20 20 diff_postscale 0.3 0.2 0.1
If the generated occupancies are too high (e.g. column 1 in epi_occupdate2), the backprojections fade out too quickly and the entire center of the scene becomes opaque. If a more reasonable mapping is used, then many sources of pollution dissappear. For example, compare the reconstructions in the unmasked case (cell d5) and masked case (Reg528) in epi_occupdate. The improvement in the homogeneity of the mask for the white sphere is even more dramatic than after several iterations of masked backprojection in epi_diffcolor2. However, these two pipelines are not precisely comparable due to the second of the two problems described next. This problem particularly affects the periphery of the masks in epi_occupdate.
This pipeline has two problems. First, highly nonlinear rampings followed by on-the-fly occupancy updating are difficult to control. Column 4 of epi_occupdate looks good, but its parameters were selected to optimize the appearance of the front slab, and its features (the white sphere and the tilted cyan cube) look much better than the features of the other slabs. In particular, the green cube looks relatively poor. The difficulty of controlling these rampings becomes even more evident in epi_difference.
Second, low derivatives with respect to angle arise in two kinds of voxels: those near (or inside) homogeneously colored objects, and those through which only dark colors (or a black background) are seen. These low derivatives, visible in the "waist" of the backprojections, e.g. at the left and right sides (centered top-to-bottom) of cell c1 in epi_occupdate. lead to false highs in the occupancy masks, e.g. in cell d1 in epi_occupdate. When masks were derived from the summed backprojections of all four slabs, no waist was left unpolluted by streaks (see epi_diffcolor2), hence the derivatives in these waist positions were high, hence the derived mask was low. When masks are derived individually from each slab, if the masks are multiplied together before being used for anything, the problem still disappears, as evident in cell d5 in epi_occupdate. However, if the individual masks are used on-the-fly as there are in the right half of epi_occupdate, then the waists affect the backprojection. See epi_difference for an addressing of this problem, and epi_occupdate3 for another attempt at on-the-fly mask computation with this problem fixed.
Since this image represents my first exposure to derivatives of backprojections of individual slabs, it enables me to test my earlier hypothesis (from epi_diffcolor) that derivaties work better than variance in the presence of smooth but non-constant distributions. Compare cell m1 of epi_variance_unfilt to cell c1 of epi_occupdate. Both respond with zero on the surface of the white sphere, which exhibits a smooth variation in shading, but the derivative is nearly zero also in the interior of the sphere, while the variance is not. Whether or not this behavior is important for segmentation is unclear.
epi_difference.tcl
epi_difference.sht
epi_difference2.tcl
epi_difference2.sht
Various attempts to distinguish the case of low derivative due to low color variation with respect to angle and low derivative due to dark colors. Correcting for dark colors is necessary to eliminate the waist of high values from the one-slab occupancy masks in preparation for a repeat of the epi_occupdate pipeline.
In epi_difference, cells c1 and c5 show the color and max of R,G,B of the derivative of the backprojection of the front slab, and cells b1 and b5 show the backprojections themselves. Registers temp30 and temp40 show the result of scaling and clamping, then of inverting this derivative. Register temp50 is a scaled version of cell b5, although the scaling is 1.0 in this image. Register temp60 shows the result of multiplying temp40 by temp50, thus scaling response by luminance. Note that the waists disappear. Cells d1 through d4 show highly nonlinear rampings of temp60 for the four slabs. Successful -occupdate'ing requires a clean mask, hence the extremely nonlinear ramping. Unfortunately, this luminance scaling also erases any contribution from the (dark) red cube. The next pipeline fixes this problem.
In epi_difference2, division before inversion is used instead of multiplication afterwards. Cells b3 and k7, and c3 and l7, show the backprojection and derivative of the back slab (see cell a3), similar to epi_difference. Register temp22 shows the result of dividing the derivative by the backprojection. The waists are brightened, but not the areas of low derivative due to low color variation. A small constant was added to cell k7 before using it as a divisor to avoid division by zero. While not strictly necessary in the pipeline, this finesse improves the displayed cells. (See however note below about equalizing masked backprojections.) Cell temp42 shows the result of scaling, clamping (in this case cutting off about half of the range), and inverting. Note that the left waist is now moderately dark. Finally, cells m1 through m4 show the nonlinear rampings for the four slabs. The combined (my multiplication) mask is shown in cell m5. It looks pretty good, although it shows the effects of pollution. More importantly, the masks of the individual slabs are waist-free and therefore more suitable for use in an -occupdate pipeline.
To compare these two waist removal methods, the last few steps in the multiplication pipeline from epi_difference is applied to the back slab and shown in registers tempz42, 62, and 72 (which was unfortunately ruined by colormap craziness) along the bottom of epi_difference2. While multiplication removes the waists, it also severely darkens the (dark) red cube. Division, on the other hand, equalizes the green and red cubes. Compare register tempz62 to cell m3. tempz62 has not been ramped yet; ramping it (which should have been visible in tempz72) would make the inequality worse. Clearly, division is better.
In later experiments that compute variance of masked backprojections, the "small constant" added before division becomes a problem, since there are many areas of perfectly zero color in any strongly masked backprojection. See epi_equalization for a comparison of post-multiplication versus pre-division equalization methods for strongly masked backprojections.
epi_occupdate3.tcl
epi_occupdate3.sht
epi_occupdate4.tcl
epi_occupdate4.sht
New attempt at on-the-fly mask computation with the problems of waists and dark colors fixed.
In epi_occupdate3, the leftmost column shows backprojections and derivatives without masking (sorry for the colormap craziness in cell c1). The second column shows new results with masking. Cells m1 through m4 and m5 show the new division pipeline applied to the unmasked derivatives; these match epi_difference2. Cells j1 through j4 show masks computed from the masked derivatives, with division-based color equalization using the masked backprojections; these match the on-the-fly masks in cells i1 through i4 up to scale (verified visually). Note that color correction using unmasked backprojections doesn't work well.
Comparing cells m5 and j5, there are two differences in technique. First, cell j5 includes on-the-fly masking. This is evident in the smoother white sphere, as usual. Second, the levels of the other features have degraded. This is an example of a common problem in these pipelines: parameters of highly nonlinear rampings that are chosen to optimize performance for one feature or slab perform erratically on other features or slabs.
As an example of the sensitivity of these pipelines to ramping parameters, in epi_occupdate4, cells i1 through i4 (which are identical to j1 through j4 up to scale) are combined in a different way. First, their additive inverse is taken, then these inverses for all four slabs are multiplied together, then another additive inverse is taken and the result nonlinearly ramped. The final result, shown in Reg197 and cell e7 (two different powers in the nonlinear ramping step), looks much better than the old result, shown here in cell g5, although the underlying structure of the input images is the same. To underscore these problems, the same alternative combining pipeline is applied to cells m1 through m4, the occupancy masks obtained from unmasked derivatives. Because their levels are different (0.0 to 1.0 for cell m3 versus 0.0 to 0.027 for cell i3), their response to this alternative pipeline is completely different, as shown in the top row of cells.
Compared to epi_occupdate, Reg197 (or cell e7) is mostly an improvement, mainly due to the division-based color equalization. Note for example that in cell e7 of epi_occupdate4 the red cube and yellow sphere (at top) are nearly as bright as the other objects, while in Reg528 of epi_occupdate, they are much dimmer. These new results also compare favorably to the non-on-the-fly iterations in epi_diffcolor2 (cell j7). In this case, although the color equalization is better in the new result, I judge the removal of pollution to be better in the old result. Perhaps the free parameters of my on-the-fly pipeline could be tuned somewhat. See epi_diff_opacity and epi_diff_power for some experiments along these lines.
By the way, color equalization via division solves not only the problems of waists and and dark objects, but when used in the context of masked backprojections, it also solves the problem of visibility normalization (see epi_reproject5,6). Specifically, since the divisor, which is the summed masked backprojected color, is darker in heavily occluded areas, the division normalizes the derivative for visibility.
epi_occupdate5.tcl
epi_occupdate5.sht
Aside from the question of on-the-fly versus non-on-the-fly iteration addressed in the above experiments, the epi_occupdate* pipelines differ from the epi_diffcolor* pipelines in that the epi_occupdate* pipelines are restricted to taking into account only the camera views from one slab at a time. It is an open question whether, at least for derivative-based pipelines, this is a good idea. This experiment explores this issue of per-slab versus non-per-slab masks in the context of derivative-based pipelines.
Compared in this image is a straightforward mask (cell a6) (with color equalization and nonlinear ramping) generated from summed unmasked backprojections (cells a5 and c5) against one (cell d6) generated from summed masked backprojections (cells d5 and f5) where the masking was on-the-fly per-slab (using slightly more opacity than in epi_occupdate4 - probably too much opacity), and against masks generated directly from a product of per-slab masks. To represent the product-of-masks pipelines, two cases are shown: on-the-fly masking (cell e7) as in the above experiments, and unmasked (cell m5) backprojections. Missing, unfortunately, is a comparison to a mask generated from the product of per-slab masks each generated from unmasked backprojections.
Cell a6 in epi_occupdate5 actually differs from cell e7 in epi_occupdate4 in two ways. First, it is based on unmasked backprojections. Second, it is based on summed backprojections, i.e. all four slabs at once. I've proven over time that masks computed from masked backprojections (e.g. cell d6 in epi_occupdate5) are better than masks computed from unmasked backprojections. See for example epi_diffcolor2. So I don't buy the argument that I should revert to unmasked backprojections.
Regarding the second question of per-slab masks versus masks from summed backprojections, I have noticed in the past that the latter, because they provide less "surround" data, usually lead to poorer masks. See for example the convincing demonstration in epi_newgrads2. In the present context, compare for example the white slab in cell e7 of epi_occupdate4 (masked using on-the-fly per-slab masks) and cell b7 of epi_diffcolor2 (non-per-slab mask, i.e. summed backprojection, first iteration). The sphere computed using per-slab masks exhibits "wings" pointing in the directions of the four slabs, whereas the sphere computed from a summed backprojection has no wings.
Although this comparison suggests that per-slab masks are to be avoided, on-the-fly masking does offer an advantage in that it achieves in some sense many iterations at once, one per voxel row, although on limited data. The choice we face is thus like Gauss-Seidel versus Jacobi iteration, but where the Gauss-Seidel version is restricted to running only on subblocks of the matrix at a time, if such a thing were possible. Even a concentric circle on-the-fly masking algorithm, if such a thing could be written, does not consider 360 degrees of data at once at each voxel.
My intuition is that the many iterations of on-the-fly masking (one per voxel row) do not convey an advantage that outweighs the disadvantage of computing masks from backprojections of only one slab at a time. The correlary of this intuition is that a few iterations of backprojection using masks computed from summed backprojections (as in epi_diffcolor2) extract more advantage from the process of iteration than many iterations using masks computed from individual slabs. Thus, I should not pursue -occupdate any further.
epi_diff_opacity.tcl
epi_diff_opacity.sht
epi_diff_power.tcl
epi_diff_power.sht
An exploration of the effect of adjusting opacity and the nonlinearity of the ramping in the -occupdate pipeline.
Each row in these images shows the masked (unfiltered) backprojection of color (cell e1) for the front slab, the masked backprojection of the magnitude of the derivative (cell f1), the visibility (cell g1) and shadow (cell h1) masks, the derived opacity mask (cell i1), and the combined opacity masks of the four slabs (cell j5).
In epi_diff_opacity, the parameters for the three rows are:
row color_offset diff_prescale diff_power diff_postscale top 2.0 10.0 10.0 0.005 middle 2.0 10.0 10.0 0.05 bottom 2.0 10.0 10.0 0.5
As these experiments demonstrate, very low opacity leads to occlusion that rises only slowly with depth, as evidenced by the fuzzy shadow map in the top row. The maximum occlusion achieved (in the back of the slab) is also low, leading to poor pollution elimination. Very high opacity, on the other hand, leads to premature occlusion, which destroys everything, as seen in the bottom row.
In epi_diff_power, the parameters for the three rows are:
row color_offset diff_prescale diff_power diff_postscale top 2.0 10.0 3.0 0.01 middle 2.0 10.0 10.0 0.01 bottom 2.0 10.0 30.0 0.01A very low exponent leads to a fuzzy shadow map, as in the case of very low opacity in the previous experiment, but the maximum occlusion is higher here, so pollution elimination is better. Of course, this solution is hardly better than setting opacity proportional to distance from the camera; it improves performance on objects near the front and back of the scene, but not in the middle. This behavior seems in evidence here; although the white sphere looks less polluted in cell j5 of epi_diff_power than in Reg1413 of epi_diff_opacity, the central white cube looks about the same in the two images. A very high exponent, on the other hand, is hard to control and equalize across the four slabs, leading to the poor performance seen here. Specifically, although the mask for the front slab looks good, the masks for the other slabs (not shown) are weak, leading to poor pollution elimination overall.
Reg1165 of epi_diff_power emphasizes a problem with derivative pipelines in general that has not yet been discussed. At the juncture of the cyanish and greenish faces of the tilted cyan cube, there is no voxel in which the derivative drops to zero. This yields a hole in the mask. By letting light leak through this hole to voxel rows behind it, on-the-fly masking seems to excacerbate this flaw, but it also appears after a few iterations of non-on-the-fly masking (see cell j7 of epi_diffcolor2). The problem seems to arise wherever two differently colored faces abut. This can be seen as a special case of what happens in textured scenes (see epi_diffcolor). I finally understand and analyze this problem, at least for variance pipelines, in epi_variance_tex.
epi_happy_backproj.tcl
epi_happy_backproj.sht
epi_happy_backproj2.tcl
epi_happy_backproj2.sht
epi_happy_backproj3.tcl
epi_happy_backproj3.sht
epi_happy_backproj4.tcl
epi_happy_backproj4.sht
epi_happy_backproj5.tcl
epi_happy_backproj5.sht
Experiments with filtered backprojection of Inventor renderings of strips of the decimated high-resolution vrip'ed happy buddha mesh.
epi_happy_backproj shows an untextured strip through the chest just above the amulet, lit with three colored directional lights. Cell a1 shows the front slab, cell a5 shows the synthetic cross section, cells c5 and c6 shows the unclamped and zero-clamped filtered backprojection, and cell g8 shows a ramped mask computed using the standard gradient pipeline. The result is awful; the mask is nearly empty.
epi_happy_backproj2 shows the effect of adding texture to the same scene by randoming changing the colors of the mesh vertices. The .iv file is shown in Composer in the upper-right, and a blowup of the mask in cell g8 is shown in the lower-right. Texture clearly improves performance, but the result is still not stellar.
epi_happy_backproj3 shows an untextured strip through the skirt. The Composer view shows that even without explicit texture there is some coloration in the vertices. (I don't know where this came from.) Nevertheless, performance is poor; geometry could not possibly be extracted from this result.
epi_happy_backproj4 shows the skirt strip textured with a B&W grid. This grid is somewhat too fine for the rendering, leading to aliasing in the epipolar images and consequently noise in the mask. However, this result is at least slightly encouraging.
epi_happy_backproj5 shows three iterations of masked backprojection on the same scene as epi_happy_backproj4. The brighter mask (Reg1028) is a more nonlinearly ramped version of the result of the last iteration (Reg859). Blurred masks (cell e7) were used throughout. This is my best result yet, but I'm not sure I could convert this into geometry, and I'm not sure I want to; it isn't very pretty. See epi_happy_backproj6 for a three-iteration run using unfiltered backprojection.
See epi_happy_twotex for an interesting experiment with two textures, one positionally shifted with respect to the other.
epi_happy_diffcolor.tcl
epi_happy_diffcolor.sht
epi_happy_diffcolor2.tcl
epi_happy_diffcolor2.sht
epi_happy_diffcolor3.tcl
epi_happy_diffcolor3.sht
epi_happy_diffcolor4.tcl
epi_happy_diffcolor4.sht
Experiments with the color derivative pipeline on the happy buddha strips.
epi_happy_diffcolor shows the untextured strip through the chest. Cells b1 and c1 show the backprojected color and its derivative for the front slab, and cells b5 and c5 show the same thing for the summed backprojections of all slabs. Cells b7 and c7 show the max of R,G,B of the cells above them, and cell c6 shows a color-equalized and nonlinearly ramped version of cell c7. For comparison, cell m5 shows the result of computing masks separately to the four slabs and multiplying the results together. As I've already concluded, masks should be computed from summed backprojections (as in cell c6), not from individual slabs (as in cell m5). The results aren't terrible, but concave features are filled in. Look for example at the hanging drapery "island" in the upper-left corner of the scene and the space between the necklace strands at the bottom.
epi_happy_diffcolor2 shows three iterations of this pipeline. The iterative code was adapted from epi_diffcolor2, but includes color equalization. I see little improvement, and the increasingly dark center makes color equalization increasingly unstable, making the center increasing harder to ramp. More importantly, I see little attenuation of streaks from iteration to iteration. I'm not sure why.
epi_happy_diffcolor3 shows one iteration of the derivative pipeline applied to the skirt strip. The results are terrible - fuzzy and full of holes. Evidently, the scene is too highly textured for the derivative pipeline. This is depressing.
epi_happy_backproj4 shows the skirt strip textured with a B&W grid. Even worse. What did I expect?
epi_happy_twotex.tcl
epi_happy_twotex.sht
A surprisingly successful attempt to use two textures, one positionally shifted with respect to the other, in order to improve the masks obtained from filtered backprojection.
The two Composer windows show two different textures mapped onto the buddha's skirt strip. The two textures are visible to the left of these windows. One is a half-phase-shifted version of the other. The two masks, obtained using the three-iteration pipeline of epi_happy_backproj5, are shown in cells s6 and s7. Cell r7 shows the max of the two masks. Adding the two masks together was also tried, with similar results. In this experiment, nonblurred masks were used in all iterations, but the masks shown in this image are the blurred versions from the final iteration. The combined mask looks pretty good! Compare it for example with the final mask from epi_happy_backproj5. I might be able to get geometry out of this mask!
What this experiment proves is the importance of using a good texture and a well matched filter. In these experiments, the filter is probably reasonably well matched to the texture, but the texture doesn't cover the interval between cycles with useful information, leading to holes in the mask. Using two phase-shifted versions of the texture improves the results. A more uniform texture would probably have also improved the results. Although this experiment doesn't prove it, I further hypothesize that using multiple shifted versions of a texture as I've done here is probably a good way to make up for an imperfect match between filter and texture, thereby improving the robustness of the overall pipeline.
One problem with this multi-texture approach is that it requires multiple acquisitions, one per texture. A more fundamental objection is that it requires projecting textures on the object. If I am willing to do this, then why not use structured light scanning, which requires acquiring far fewer images?
epi_aperture.tcl
epi_aperture.sht
Quick experiment to evaluate the improvement obtained by performing aperture antialiasing. All previous experiments (including log #1) did not include it. The scene is the standard advanced scene of cubes and spheres.
The top row of cells includes pixel antialiasing (4 x 4 samples), but no aperture antialiasing. The bottom row includes both (4 x 4 x 4 x 4, so 256 samples per camera position). Although the difference is evident in the epipolar image, as seen in the blowups, the better sampling makes almost no difference at all in the filtered backprojections shown at right.
In another experiment (not shown), I examined the effect of the aperture antialiasing on the derivative pipeline. It makes almost no difference.
epi_variance_tex.tcl
epi_variance_tex.sht
epi_variance_tex2.tcl
epi_variance_tex2.sht
Further examination of variance for textured scenes. Unfiltered backprojection is used, but unmasked (unlike epi_variance_unfilt).
In epi_variance_tex, the standard advanced scene is used, and only the back slab is shown. Cell c3 shows the backprojection, and cell f6 shows the variance prior to color equalization and conversion into an opacity mask. Looking at the top side of the green cube, the variance is high everywhere except on the surface, as expected. Note, however, that the variance on the surface oscillates between low and high, the high-variance voxels being nearly indistinguishable from nearby non-surface voxels. As shown in the accompanying blowups, voxels with high variance correspond to the transition zone between adjacent black and green stripes, i.e. lying astride color discontinuities on the surface. Given a pipeline with "reasonable" resampling, it seems impossible to avoid computing a high variance for voxels lying astride color discontinuities.
By contrast, look at the top of the yellow sphere. Its texture is blurrier, i.e. there are no discontinuities in color, and so the variance in voxels on the surface is always low. Herein lies the key to a successful variance-based surface detector; use a blurry texture. Also, avoid other discontinuities, e.g. from polygon coloring or from illumination. If necessary, blur the epipolar image itself. The result will be a thick layer of low-variance voxels. The true location of the object surface is in the middle of this layer.
In epi_variance_tex2, a similar effect is shown for the untextured chest of the buddha, although in this case the discontinuity is gradual enough that the variance stays low. The blowups are centered on a voxel at the tip of the cross-section of the left necklace strand. In this case, it is a change in illumination that is causing the color discontinuity; the lights illuminating the left and right sides of the necklace strand are blue and yellow, respectively, and their combined illumination produces a few nearly white voxels at the tip itself. The cells from the top down show the synthetic cross-section, the filtered backprojection, the (unfiltered) variance, and (in cell e8) the min of R,G,B of the color-equalized variance. The opacity mask derived from cell e8 is shown in cell e9. As the blowups show, the variance at the tip is high, but not after color equalization. Thus, a surface is detected, as it should be, at the tip of the strand. Of course, the concave space between the two strands are (incorrectly) filled in, as noted in epi_happy_diffcolor.
It is interesting to rethink Seitz's voxel coloring algorithm in light of this new insight. Using a blurry texture will insure that his surface contains no holes, but in the context of his front-to-back sweep algorithm, the *first* row voxels found to have low variance will become the detected surface, masking any further processing. Since using a blurrier texture also leads to a thicker layer of low-variance voxels, his algorithm will not place the surface in its true location, but instead at some distance (or bias) in front of the true location. Worse, that distance will vary locally with the texture. In the yellow sphere, the texture is sinusoidal, so the variance within an angular interval of constant width varies sinusoidally. This gives rise to a layer of low-variance voxels whose thickness oscillates sinusoidally. This can be seen in the blowup at lower-right. In a sweep algorithm such as Seitz's, the surface he extracts will be the lower (or upper) envelope of such a layer. His surface will therefore be sinusoidal, not flat.
Taken in the context of Seitz's CVPR '97 paper, this last criticism - that his surfaces undulate - is not entirely fair. In the context of his view interpolation application, an undulating surface still satisfies his definition of a "consistent scene", i.e. he can interpolate a correct view from it. However, the first criticism - that his surface placement is biased - *is* fair. Moreover, his pipeline is obviously sensitive to the frequency content of the texture - sensitive to the point of being fragile. Of course, my pipelines are also fragile.
By the way, as Seitz's algorithm is currently implemented, his voxels receive (unweighted) contributions from all image pixels that map to the 2D-image-space bounding box of the voxel, rather than from a reasonable resampling of the backprojected images. This will add an aliasing problem to the bias problem I describe above. In my implementation, by contrast, I use better resampling, but this may harm me in that it introduces blurring among adjacent voxels, possibly excacerbating the lack of a clean zero-variance zone at the surface. Filtered (as opposed to unfiltered) backprojection could conceivably alleviate this blurring, but it cannot be employed in a derivative or variance pipeline, as discussed in epi_diffcolor and epi_variance_filt2.
The order of ray -> voxel interpolation versus squaring is wrong in this pipeline, leading to excessive texture-induced patterns in the variance. This problem is fixed in epi_varupdate.
epi_variance_texes.tcl
epi_variance_texes.sht
epi_variance_texesa.tcl
epi_variance_texesa.sht
New attempt to compute a mask from the variance of a textured scene. This time, I am computing per-slab masks, even though that is usually suboptimal, in order to make low-variance voxels detectable. (In epi_variance_unfilt2, which summed the variances of the four slabs, I had no idea how to proceed.) I am also varying texture frequency (as discussed above in epi_variance_tex) and the color equalization method (a new idea). The standard advanced scene is used, with the red cube made diffuse. Unfiltered backprojection is used throughout.
In epi_variance_texes, the top and middle rows shows a scene with the usual texture frequency, but applied to all objects. The bottom row shows a scene with a texture of half the frequency on all objects. From left to right are the epipolar images for the back slab (e.g. cell a3), its unfiltered backprojection (cell d3), its variance (cell f3), its variance divided by its backprojection (cell g3), the sum of R,G,B (cell h3), a nonlinear ramping of the additive inverse (cell i3), and the sum of the masks for the four slabs (cell i5). The top row differs from the middle row in that the divisor used for color equalization of the top row is a double-"blur"ed version of the backprojection. Incorrect boundary voxels in the blurred images where replaced by unblurred voxels to keep the blurred image clean up to its boundaries.
Computing per-slab masks is what makes the pipeline work at all, as noted above. Lowering the texture frequency (from stripe32 to stripe16, or stripe16 to stripe8, depending on the primitive) thickens the layer of low-variance voxels, as discussed in epi_variance_tex. Blurring the backprojection before using it to equalize the variance reduces the tendency of this equalization to reintroduce the texture pattern into the variance, which is pleasingly homogenously low previous to equalization. Skipping color equalization is not an option; it causes voxels which saw the background, which is black, to end up opaque. I wish I could think of another way to distinguish between these cases, but this method seems to work for now. (I later realized that the order of ray -> voxel interpolation versus squaring is wrong in this pipeline, explaining some but not all of the excessive texture-induced patterns in the variance. This problem is fixed in epi_varupdate.)
In epi_variance_texesa, I use the top row of epi_variance_texes (with a slightly difference nonlinear ramping) to experiment with different ways of combining R,G,B and the masks from the four slabs. From left to right in the middle row are sum(R,G,B), min(R,G,B), and max(R,G,B). For each of these three methods, the bottom row shows two methods of combining the four slabs, sum(1,2,3,4) on the left and product(1,2,3,4) on the right. Thus, the lower-leftmost cell here corresponds to the upper-rightmost cell in epi_variance_texes except for the change in ramping.
Sums of masks exhibit "wings", which products of masks largely eliminate. min(R,G,B) strengthens the pure green and pure red cubes, but severely weakens the others. sum(R,G,B) at left or max(R,G,B) at right seem best. Cell i5 in the upper-right corner shows a different ramping of the cell in the lower-right (product(1,2,3,4) over max(R,G,B)).
Although the upper-right cells in these two images are the most promising masks I have yet obtained from a variance pipeline running on a textured scene, they have several problems. First, they still exhibit some wings due to being derived from per-slab masks. Second, although the texture frequency employed was low enough to create a good layer of low-variance voxels if viewed head-on, the frequency is too high if viewed obliquely. This happens in the only available (i.e. non-occluded) views of the upper-right face of the tilted cyan cube, so its variance is not uniformly low and its mask contains holes. Third, despite being computed per-mask, since there is no masking, there is pollution. This gives rise for example to the bright stripe through the mask of the top face of the dark red cube; this stripe is due to pollution from the yellow sphere.
See epi_perslab for another comparison of per-slab and summed-backprojection variance computations, in that case masked using a mask derived from backprojection + gradient.
epi_diff_texes.tcl
epi_diff_texes.sht
New attempt to compute a mask by applying the derivative pipeline with on-the-fly masking to the textured scene. This time, I am varying texture frequency (as discussed above in epi_variance_texes). color equalization method (a new idea).
The bottom row of cells shows employs a high-frequency texture (stripe_32 or 16) and the top row employs a low-frequency texture (stripe_16 or 8). On the bottom row, the rightmost cell shows the mask computed per-slab but from unmasked backprojections. The next cell (to its left) shows the mask computed from on-the-fly masked backprojections. Using on-the-fly masking clearly reduces pollution. The cell its its left uses a more strongly nonlinear ramping. On the top row, both cells use on-the-fly masking, with two alternative rampings.
A derivative pipeline is seems to be improved by lowering the frequency of the texture, but only slightly. More importantly, none of these results show hole-free edges on the objects. This is because the summed magnitude of derivative is not homogeneous, as can be seen in cell c4 (for the left slab). (The backprojection itself is shown in cell b4). Neither was the variance, but this result is worse.
epi_happy_backproj6.tcl
epi_happy_backproj6.sht
epi_happy_backproj6a.tcl
epi_happy_backproj6a.sht
Three iterations of masked *unfiltered* backprojection on the same scene as epi_happy_backproj5. In epi_happy_backproj6, unblurred masks are used throughout, except for cell s7, which shows the blurred version of the final mask. In epi_happy_backproj6a, blurred masks are used throughout, making it more comparable to epi_happy_backproj5. However, the ramping used on the masks, and the opacity applied during masked backprojection, is slightly different than was used in epi_happy_backproj5.
As usual, unfiltered backprojection emphasizes corners excessively, but in general the mask isn't too horrible. As with filtered backprojection, iteration seems to improve things. Interestingly, though, iteration excacerbates the streaks that connect nearby bright spots. If I raise the opacity applied during backprojection even slightly (not shown), they spiral out of control and the mask begins to look like a convex hull. The problem seems worse here than when filtered backprojection is used. Thus, filtered backprojection seems superior in this example, even though it is theoretically unjustified for opaque scenes.
epi_varupdate.tcl
epi_varupdate.sht
epi_varupdate2.tcl
epi_varupdate2.sht
epi_varupdate3.tcl
epi_varupdate3.sht
epi_varupdate4.tcl
epi_varupdate4.sht
I finally implement Seitz's actual algorithm, which is variance-based (as opposed to derivative-based) on-the-fly mask updating. I also fix an outstanding problem in the order of ray -> voxel interpolation versus squaring in my previous pipelines. Finally, I start computing the standard deviation (sqrt of variance) rather than the variance. This makes more sense as an input to color equalization, which divides by backprojected color, not by its square.
The details of the interpolation versus squaring problem are as follows. My backprojection pipeline, when computing the contribution by a ray to a voxel, linearly interpolates among adjacent rays. Thus, my previous variance pipelines, which consisted of separate backprojections for mean (u) and squared color (X^2), when computing the contribution to a voxel by a ray carrying X^2, have been linearly interpolating among squared colors. This is wrong, and it has been leading to excessive texture in the variance. The correct procedure is to linearly interpolate among colors to compute a contribution, then square the interpolated contribution. The present on-the-fly variance computation pipeline does this.
In epi_varupdate, I run this new pipeline on the standard advanced scene with high-frequency texture (stripe_32 or 16). The upper-left cells show the unmasked (unfiltered) backprojection of the back slab and below it the color-equalized standard deviation for this slab. The remaining cells consist of 5 columns of on-the-fly masked backprojection with varying opacities. From top to bottom are the generated mask for the back slab, the associated shadow mask, and the composite mask for the four slabs, computed as the sum of the four per-slab masks. Although all masks and shadows appear to have identical minmaxes, this is only because of automatic ramping by the spreadsheet; the actual max(opacity) and min(visibility) is given in the table below (the former as var_postscale). The parameters for each column were:
color_offset 1.0 var_minval 0.0 var_maxval 5.0 var_power 30.0 col var_postscale minval(visibility) 1 0.0 1.0 2 0.05 0.96 3 0.1 0.69 4 0.2 0.50 5 0.5 0.29
The only interesting effect evident in this image is the breakup of the mask at high opacities (Reg359 and especially Reg397). This is a direct effect of the causal nature of the sweep algorithm. Note also that it is difficult to obtain significant occlusion, i.e. low minval(visibility), without incurring breakup of the mask. More will be said on this later, under epi_varupdate3.
In epi_varupdate2, I repeat this experiment with a different nonlinear ramping, in particular a higher power. The top row of cells are identical to the lower-right three cells in epi_varupdate. The parameters for each column in this image are:
color_offset 1.0 var_minval 0.0 var_maxval 5.0 var_power 50.0 col var_postscale minval(visibility) 3 0.1 0.91 4 0.2 0.82 5 0.5 0.58 6 1.0 0.32
At this power level, the mask is more resistant to breakup at high opacities, but weak features (like the central white cube) are lost.
In epi_varupdate3, I try to identify a specific feature whose extraction is improved by this pipeline. The front slab is examined, and the feature whose extraction I focus on is the bottom edge of the central white cube. The cells shown are, from left to right, the masked backprojection, the color-equalized standard deviation, the visibility mask, the shadow mask, and the occupancy (i.e. opacity) mask. The rampings used in the previous two experiments showed no improvement, so in this experiment I use var_minval to clamp part of the mask to zero variance, hence to maximum opacity. Essentially, I am introducing a thresholding operator into my pipeline. The actual opacity to which these voxels are set depends on var_postscale, as follows:
color_offset 1.0 var_minval 0.3 var_maxval 4.0 var_power 30.0 row var_postscale minval(visibility) 1 0.01 0.79 2 0.1 0.07 3 0.5 0.0003
In the top row, opacity is low, so no occlusion takes place (remember to overlook the automatic ramping of the visibility masks that is performed by the spreadsheet). This causes the central cube to be polluted by the cyan-black texture of the tilted cyan cube, leading to high variance there. In the middle row, opacity is moderate, occlusion takes place (min(visibility) drops from 0.79 to 0.07), the pollution is reduced, and the variance of the central cube drops. The corresponding occupancy masks don't show much improvement, however, probably due to the extremely nonlinear ramping used to derive them. In the bottom row, opacity is too high, leading to breakup of the mask and consequent degradation of the desired occlusion.
To conclude, although I have observed the expected benefit of this algorithm, the algorithm is extremely fragile, and the benefit is modest. More specifically, high-frequency textures lead to thin features in the mask, and these develop holes at oblique angles, as evident in epi_varupdate and epi_varupdate2 (and as discussed in epi_variances_texesa). Low-frequency textures, on the other hand, lead to thicker mask features, which are more resistant to holes. However, the thickness of these features undulates with the texture. If opacity is set low, the features, despite their undulations, serve to occlude features deeper in the scene, as desired, but they occlude only slightly, and the derived benefit is small. If the opacity is set high, the causal sweep algorithm leads to only the front envelope of the features being detected. Given their undulations, this produces a mess, as shown in cell p1 of epi_varupdate3.
In epi_varupdate4, I show a sequence of runs that nicely summarizes my conclusions. The high-frequence texture is used, and the front slab is examined. The top row of cells shows the color-equalized standard deviation, and the bottom row shows the corresponding mask. The parameters are:
color_offset 1.0 var_minval 0.2 var_maxval 4.0 var_power 30.0 col var_postscale minval(visibility) 1 0.003 0.94 2 0.01 0.83 3 0.05 0.39 4 0.1 0.16 5 0.3 0.013
If opacity is too low (columns 1 and 2), no masking occurs, and the bottom edge of the central white cube is weak. If opacity is too high (column 5), the mask breaks up, and the central cube suffers again. Only if opacity is perfectly chosen (columns 3 and 4) is there a benefit
epi_happy_varupdate.tcl
epi_happy_varupdate.sht
epi_happy_varupdate2.tcl
epi_happy_varupdate2.sht
Application of new variance-based on-the-fly masking pipeline to textured happy buddha skirt strip.
In epi_varupdate, the bottom row shows the case of low opacity (var_postscale = 0.01), hence no masking. From left to right are the backprojection of the front slab, its color-equalized standard deviation, its occupancy mask, and the sum of the four per-slab masks. The top two rows (in wrapped fashion) show the case of moderate opacity (0.2). Also shown are the visibility and shadow masks.
Some benefit of on-the-fly masking can be observed, but it is slight. In particular, Reg322 (with masking) shows extraction of features near the right side of the skirt that are missing in cell p1 (without masking). This benefit can be traced back to the backprojection and variance cells (as in epi_varupdate3). However, the combined mask from the on-the-fly masking case (Reg356) also shows some mask breakup along the top edge of the skirt and some excessively thick low-variance areas along the upper-right portion of the mask. Some variance clamping was used (as explained in epi_varupdate3), which explains this thickening, but without clamping, little benefit of on-the-fly masking is obtainable.
In epi_varupdate2, the experiment is repeated with no clamping (var_minval = 0.0) and a less severely nonlinear ramping (var_power = 10.0). In this case, virtually no benefit of on-the-fly masking is observed.
Interestingly, the mask obtained without on-the-fly masking (i.e.g cell p5) is the best result I have ever gotton for the top edge of the skirt. Just for fun, I ran my usual gradient operator over it, producing cells g7 (unblurred) and e7 (blurred). Cell g7 compares favorably in some spots to my best (blurred) mask from non-iterated filtered backprojection, e.g. cell e7 in epi_backproject5. Similarly, I noticed that my best result from running the unmasked variance pipeline on the standard advanced scene, e.g. Reg263 in epi_varupdate, compares favorably to my best occupancy mask from filtered backprojection, e.g. cell q8 in epi_newgrad2. In particular, the edges are thinner in the variance pipeline. Note that the textures employed in the two experiments are of the same frequency, at least on most of the objects. However, the variance pipeline performs poorly on heavily occluded objects, such as the central white cube, in on-the-fly masking is both fragile and doesn't help much. In the next experiment, I try a combination.
epi_backproj_variance.tcl
epi_backproj_variance.sht
epi_backproj_variance2.tcl
epi_backproj_variance2.sht
epi_backproj_variance3.tcl
epi_backproj_variance3.sht
Experiments with combinations of backprojection-based and variance-based masks, neither with on-the-fly masking or iteration of any kind.
The leftmost column of epi_backproj_variance shows standard filtered backprojection of the advanced scene with texture on all objects. From top to bottom are the filtered backprojection, the unblurred mask, and the blurred mask (cell e7). The rightmost column shows the unmasked variance pipeline. From top to bottom are the sum of the four per-slab masks (cell p5), the mask obtained by running my usual gradient operator on this first mask, and the blurred version thereof (cell p7). The center column shows two combinations of backprojection and variance-based masks: cell h3 shows the product of cell e7 and cell p5, and cell h6 shows the sum of cell e7 and cell p7. The product (cell h3) is weaker than either of its inputs, as expected, but the edges are pleasingly thin (due to the variance mask), free of bulges (due to the backprojection mask), free of free-space aliases and noise (due to the variance mask), and free of streaks (due to the backprojection mask). Actually, backprojection masks can also have streaks; I need to think some more about streaks. At any rate, this is a clean but conservative mask. By contrast, the sum (cell h6) is stronger than either of its inputs, but exhibits a variety of unwanted artifacts.
The left half of epi_backproj_variance2 shows two nonlinear rampings of the unmasked variance pipeline running on the textured happy buddha skirt strip. From left to right are the variance-based mask (e.g. Reg233), the mask (e.g. Reg287) obtained by running my usual gradient operator on this first mask, and the blurred version thereof (e.g. Reg301). The right half shows standard filtered backprojection (cell c5) and the (blurred) mask (cell e7) obtained by running my usual gradient on it. Cell e6 shows the sum of these two masks. It is stronger than either of its inputs with no ill effects (other than an unexplained waist at the bottom).
The middle column of epi_backproj_variance3 shows the usual filtered backprojection and blurred mask running on the standard advanced scene, but with untextured white sphere and shiny red cube. The right column shows the summed color-equalized standard deviation and summed mask derived from the same unmasked per-slab variance-based pipeline used in the previous experiments. The left column shows the color-equalized standard deviation and mask derived from a jury-rigged unmasked variance-based pipeline running on a summed backprojection of all four slabs (rather than per-slab). Each cell in the bottom row shows the product of the two masks above it. Clearly, variance-based pipelines do not run well on unmasked summed backprojections, due undoubtedly to pollution. See epi_perslab for another demonstration of this fact.
epi_back_var_reproject.tcl
epi_back_var_reproject.sht
First attempt to use both pipelines in an iteration. Some random conclusions follow.
Changing the size of the blurring kernel from 3x3 to 6x6 has no apparent effect on color equalization. Neither does applying the 3x3 blur twice in succession.
Blurring a variance-derived mask before using it in second, masked variance pipeline does not noticeably decrease breakup if the opacity is too high.
See epi_back_var_reproject2 for a later try.
Experiments demonstrating the spatial shift or mask breakup that accompanies all iterative schemes that employ masked backprojection. (See epi_reproject5 for my initial discovery of this problem.)
The left column of cells shows my standard backprojection + gradient pipeline running on the standard advanced scene with high-frequency texture everywhere. The second column shows masked backprojection + gradient where masking employs the blurred mask (cell e7) from the first backprojection with a high opacity scaling factor (1.0), as evidenced in the visibility and shadow masks visible in cell columns i and j. Notice how the edges of the green cube move outward in the second iteration.
The third column of cells shows an unmasked variance pipeline with a Tcl-code implementation of color equalization and conversion from u^2 and X^2 through standard deviation to an occupancy mask. (Color equalization employed a summed unmasked backprojection isotropically blurred by a 4x4 box filter. This is incorrect and pollutes the resulting mask, but in my analysis below I pay little attention to this mask, so my conclusions are still valid.) The implementation used parameter settings equivalent to the following settings of the C-code implementation:
The fourth column shows a globally masked (not on-the-fly masked) variance pipeline where masking employs the same blurred mask (cell e7) used in the second column and a moderately high opacity scaling factor (0.5), as evidenced in the visibility and shadow masks visible in cell columns m and n. Note how the right edges of the cyan cube break up in the second iteration. By the way, this experiment demonstrates that a non-on-the-fly masked variance pipeline suffers mask breakup just like an on-the-fly masked variance pipeline, although presumably in a different way since there is only one feedback step, not one per voxel row. In another experiment (not shown), I verified that this breakup varies with the opacity scaling factor just like on-the-fly masking varied withcolor_offset 1.0 var_minval 0.0 var_maxval 4.0 var_power 20.0
In conclusion, the causal nature of masked backprojection causes artifacts in both a backprojection + gradient pipeline and a masked variance pipeline, whether masking is on-the-fly or not. This is a classic self-shadowing problem, and it is fundamental to discrete representations. On the other hand, while these artifacts are typically noticeable in the second iteration, i.e. after one feedback step, they typically only become objectionable in the third iteration. This suggests that multiple iterations, including on-the-fly masking, cannot be applied to these representations. However, it does not rule out a single iteration if the benefit is sufficiently large.
epi_equalization.tcl
epi_equalization.sht
Quick experiment comparing post-multiplication versus pre-division color equalization methods for strongly masked backprojections. See epi_difference for the background on this comparison.
The top row of cells shows my currently accepted pre-division method for color equalization, i.e. division of the standard deviation by masked color (plus a small constant to avoid division by zero) before applying the nonlinear ramping. On the left is an unmasked variance pipeline, and on the right is a heavily masked variance pipeline. (The mask was a heavily blurred backprojection + gradient mask, shown in cell h7 in epi_perslab below.) This top row of cells is snapshotted from epi_causal. The bottom row of cells shows my previously rejected (in epi_difference) post-multiplication method for color equalization, i.e. multiplication of of the nonlinearly ramped occupancy mask by masked color. Again, on the left is an unmasked variance pipeline, and on the right is a heavily masked variance pipeline.
The pre-division pipeline works tolerably well in the unmasked case, although small waists are visible. If the ramping were more nonlinear, these waists would disappear. However, in the heavily masked case, there are many areas of perfectly zero color, causing these waists to become more prominant, essentially ruining the mask. I can think of no combination of small constants, max() functions, or thresholds that eliminates this problem. The post-multiplication pipeline, on the other hand, works much better, although there is the expected and unfortunate darkening of the red cube. (The "wings" on the cubes are due to the use of per-slab masks - a different problem.)
I have trouble justifying post-multiplication, however. My pre-division
pipeline is carefully arranged to divide apples by apples, including taking a
sqrt (thereby converting variance into standard deviation) before dividing,
whereas the post-multiplication pipeline is applied after a nonlinear ramping
and thus throws this arrangement to the winds. See epi_back_var_reproject2 for
a tweak that alleviates the darkening of the red cube.
epi_perslab.tcl
Quick experiment comparing per-slab to summed-backprojection variance
computations.
The left half of the image shows an unmasked pipeline (using my resurrected
post-multiplication color equalization method) and the right half shows a
heavily masked pipeline. (The mask was a heavily blurred backprojection +
gradient mask, shown in cell h7.) Within each half, in the left column
variances are computed from summed backprojections, and in the right column(s)
variances and masks are computed per-slab. At the bottom are the product of
each of these masks with the (normally but not heavily blurred) backprojection
+ gradient masks from the first and second iteration of epi_causal (cells e7
and n7, also displayed). (These product masks are toastier (i.e. weaker) than
the masks in epi_causal because I use a more strongly nonlinear ramping on the
variance pipelines here.)
As expected, per-slab masks are more distinct but exhibit wings, while masks
from summed backprojections are weaker but without wings. Per-slab masks even
seem aliased, but this might be simply that they are so much more distinct that
they are "falling off the other end of the table", i.e. they are beginning to
break up. Note that either kind of mask suffices to clean up the noise
in the backprojection + gradient mask.
By the way, note the highly instructive per-slab variances in the masked case;
I have included an extra column of these images because they are so
neat-looking. I have always been computing such images, but color equalization
has made them look non-intuitive; in this pipeline, equalization is delayed
until after these images are computed.
Yikes, I have been computing masked variance wrong! See epi_newvariance.
epi_newvariance.tcl
Yikes, I have been computing masked variance wrong! Within the summation to
compute X^2, I should have been squaring color *before* multiplying by
visibility, not afterwards. Then, I should have been dividing the summed
backprojections and backprojected squares by total visibility. Only using this
algorithm do occluded rays *not* contribute to variance as; otherwise, they
contribute as black rays, leading to artificially high variance in occluded
areas and therefore poor masks. This error is evident in the backprojected
squares in cell l3 (and the occupancy mask in cell o3) of epi_perslab.
In epi_newvariance, the left half of the image shows masked variance using the
synthetic cross section (cell b5), while the right half uses a blurred
backprojection + gradient mask (cell e7). Within each half, the left column
shows a mask from summed backprojections, while the right column shows per-slab
masks. From top to bottom are the mask backprojections, standard deviations,
per-slab mask (for the per-slab case), and composite masks (both cases). For
visualization purposes only, Reg881 and cell s3 show the standard deviations
(e.g. cell p3) multiplied by the blurred color (e.g. cell q3, not shown), which
is usually used later in the pipeline, during color equalization (currently
done using post-multiplication). These visualizations correspond nicely to our
intuition of what a variance image should look like.
The important thing to observe about this image is that the top edge of the red
cube in cells p3 and r3 do not break up (as they do in cells l3 and o3 of
epi_perslab). This is directly attributable to the new variance pipeline.
Reg816 and Reg851, which employ the synthetic cross section, demonstrate a
perfect version of this desired behavior.
On the other hand, the bottom of the red cube is disappointingly weak in the
composite mask in cell r5. It is even weak in Reg876, which uses the synthetic
cross section for masking. This may be because it is only seen obliquely, thus
increasing the apparent frequency of its texture. This behavior was also
observed in the old pipeline (see cell o5 in epi_perslab).
In epi_newvariancea, the right half of the image is identical to
epi_newvariance, while the left half shows unmasked variance using the new
pipeline. The composite mask for the per-slab case (cell h5) is essentially
identical to cell f5 in epi_perslab, a good check that the new pipeline
performs reasonably in the unmasked case. Note that the top edge of the red
cube, which looks good in the masked case (cells p3 and r3) look poor in the
unmasked case (cells f3 and h3). This shows the benefit of masking to variance
pipelines more clearly than any previous image I've made.
The only anomaly here are the masks from summed backprojections. Cell m6, from
summed masked backprojections, has no wings but it exhibits strange bulges, and
cell e6, from summed unmasked backprojections, has a severe level problem.
Even Reg872 in epi_newvariance, from summed masked backprojections using the
synthetic cross section as a mask, has bulges. I'm not sure what's going on
here.
I should probably re-try all my variance -occupdate experiments,
after making the appropriate changes in backproject.c...
epi_back_var_reproject2.tcl
Second attempt to use both pipelines in an iteration.
In epi_back_var_reproject2, the left half of the image shows the first
iteration, and the second half shows the second iteration. Within each half,
the top row of cells shows the (unmasked or masked) backprojection, the
(unmasked or masked) standard deviation of the back slab, visualized as
described in epi_newvariance, and the derived occupancy mask. Then, down the
left side of each half is the unblurred and blurred backprojection + gradient
mask (e.g. cells f7 and e7), and down the right side are the unblurred and
blurred variance mask (e.g. cells h5 and g5). A small improvement has been
made to post-multiplication color equalization; I am equalizing using an
inverse power-ramped color image. This helps restore the dark red cube to full
brightness. Along the bottom are the product of the unblurred masks (e.g. cell
g6 is the product of cells f7 and h5) and of the blurred masks. The mask from
the first iteration that was used to mask the backprojections in the second
iteration is cell g6, the product of unblurred masks. (In another experiment
(not shown), I tried using the product of blurred masks (cell f6) in the second
iteration. It made little difference.)
This result is about as good as epi_back_var_reproject, but no better. The
variance masks are basically being used simply to remove noise in the
backprojection + gradient masks, and also most any decent mask would do the
same. On the other hand, even after one iteration, the variance mask is still
weak in the center, so the product mask is weaker in the center than the
backprojection + gradient mask alone. In another experiment (not shown),
I tried a third iteration. Everything began to weaken.
In epi_back_var_reproject3, I repeat the same experiment on the textured buddha
skirt strip. I deliberately use ramping parameters on the backprojection +
gradient mask that leave some noise in, and lo and behold, the variance mask
cleans it up. However, a different ramping might have done just as well. This
charade aside, the second iteration is a clear win, but the third iteration is
not. Unblurred masks are used throughout. This agrees with my (unshown)
experiments above with the standard scene. Cell r6 (the product mask from the
second iteration) is the nicest mask I have ever obtained for the buddha skirt
(except when I used two textures, which is unfair).
epi_back_var_reproject3a is identical except that I have added one more cell
(q7), which shows my best mask using a two-iteration backprojection + gradient
pipeline alone. Frankly, it looks almost as good as the dual-pipeline result
(cell r6), although not quite as smooth (i.e. antialiased) and clean
(i.e. noise-free).
epi_perslab
November 14, 1997
epi_perslab.sht
epi_newvariance,a
November 14, 1997
epi_newvariance.sht
epi_newvariancea.tcl
epi_newvariancea.sht
epi_back_var_reproject2,3,3a
November 14, 1997
epi_back_var_reproject2.sht
epi_back_var_reproject3.tcl
epi_back_var_reproject3.sht
epi_back_var_reproject3a.tcl
epi_back_var_reproject3a.sht
© 1997
Marc Levoy
Last update:
April 19, 2001 02:34:40 AM
levoy@cs.stanford.edu