Iss.bu.edu

c 2001 EURASIP. Personal use of this material is permitted. However, In Proc. Int. Conf. on Augmented, Virtual En- permission to reprint/republish this material for advertising or promotional vironments and Three-Dimensional Imaging, purposes or for creating new collective works for resale or redistribution to ICAV3D-2001, May 30 -June 1, 2001, Mykonos, servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the EURASIP.
POCS reconstruction of stereoscopic views to signals defined over irregular sampling grids.
In such cases, Shannon’s theory is not applica- This paper presents an application of POCS (pro- ble and alternative methods must be found to jection onto convex sets) methodology to the re- reconstruct or approximate the original contin- construction of intermediate stereoscopic views.
The basic problem in such a reconstruction, re- Although some results on the reconstruction sulting from disparity compensation, is that of of band-limited functions from irregularly-spaced the recovery of a regularly-sampled image from samples are available (e.g., [1]), their practical its irregularly-spaced samples. This problem also usefulness is limited; theoretical constraints on arises in other image processing and coding ap- the maximum spacing of irregular samples under plications. The results reported here improve the perfect reconstruction condition cannot be our previous POCS-based reconstruction method satisfied by arbitrarily-distributed image sam- by locally adapting the algorithm to the density ples after disparity or motion compensation. By of image samples. We also extend the method relaxing the perfect reconstruction condition, al- to color images by implementing the method in ternative methods have been proposed such as the luminance-chrominance (Y -U -V ) space.
the polynomial interpolation or iterative recon-struction [2].
In this paper, we extend a reconstruction method based on projections onto convex sets In order to compute intermediate views in a (POCS) [3] proposed by us earlier [4]. We im- stereoscopic or multiview representation of a 3- prove the convergence of reconstruction by lo- D scene, the usual problem is that of recovering cally adapting the algorithm to the density of regularly-spaced images samples (intensity and image samples. We also extend the method to color) based on irregularly-spaced samples. This color images by implementing it in the luminance- is due to disparity compensation and is similar to motion compensation used for temporal in-terpolation of image sequences.
The interpolation of either regularly- or irre- gularly-spaced samples based on the knowledgeof a regularly-sampled image has been exten- Let g = {g(x), x = (x, y)T ∈ R2} be a con- sively treated in the literature and has found tinuous 2-D projection of the 3-D world onto numerous practical applications in image pro- an image plane and let gΛ = {g(x), x ∈ Λ} be cessing and coding. The case of computation of a discrete image obtained from g by sampling regularly-spaced samples based on regular ones over a lattice Λ [5]. Let’s assume that g is band- has been explored to a lesser degree. The pri- limited, i.e., G(f ) = F{g}=0 for f ∈ Ω where mary reason for this are difficulties associated F is the Fourier transform, f = (f1, f2)T is a with the extension of Shannon’s sampling theory frequency vector and Ω ⊂ R2 is the spectralsupport of g. If the lattice Λ satisfies the multi- This work was carried out with partial support from dimensional Nyquist criterion [5], the Shannon the Natural Sciences and Engineering Research Councilof Canada under Strategic Grant STR224122 while the sampling theory allows to perfectly reconstruct g from gΛ. However, in the case of irregular sam- pling the theory is not applicable. Therefore, there is little flexibility in shaping the spectrum the general goal is to develop a method for the of gk ; any practical lowpass filtering on Λ must reconstruction of g from an irregular set of sam- suppress high frequencies since a slow roll-off ples gΨ = {g(xi), xi ∈ Ψ ⊂ R2, i = 1, ., K}, transition band must be used to minimize ring- where Ψ is an irregular sampling grid.
ing on sharp luminance/color transitions. Sec-ondly, the interpolation operator IΨ/Λ, espe- cially the one based on triangulation (better per-formance), is involved computationally.
We use the POCS methodology [3] to recon- In our earlier work [4] an alternative imple- struct image g. This methodology involves a mentation of the algorithm (1) has been pro- set theoretic formulation, i.e., finding a solution posed. Since our goal is the reconstruction of as an intersection of property sets rather than image samples obtained from motion or dispar- by a minimization of a cost function. We use ity compensation, a 1/2-, 1/4- or 1/8-pixel pre- cision of motion or disparity vectors is usually sufficient. Therefore, it has been proposed to 0 - set of all images g such that at xi ∈ Ψ, i = 1, ., K (irregular sampling grid) implement (1) on an oversampled grid matching • A1 - set of all band-limited images g, i.e., where B is implemented on ΛP , that is a P ×P - If the membership in A0 can be assured by a times denser (oversampled) lattice than Λ, and sample replacement operator R (to enforce proper P equals 2, 4, or 8 depending on motion/disparity image values on Ψ), and the membership in A1 vector precision. Clearly, Λ is a sub-grid of ΛP , – by suitable bandwidth limitation (low-pass fil- i.e., x ∈ Λ ⇒ x ∈ ΛP . gΨ/Λ is the nearest- tering) B, then the iterative reconstruction al- neighbor interpolation of gΨ on ΛP , defined at where gk is the reconstructed image after k it- the nearest-neighbor sampling, i.e., sampling on tracts image values (luminance/color) on the ir- regular grid Ψ. Note that equation (1), pro- words, the implementation (3) is performed on a posed in [6], results in an approximation rather lar samples from Ψ are quantized to the nearest low-pass filtering. In order to implement equa- tion (1) on a computer, a suitable discretization must to be applied. In [6], equation (1) was im- tion that a suitable value of P is selected.
2.2. Adaptation of the relaxation coeffi-cient where the lowpass filtering B is implementedover Λ and α is a parameter that allows control The choice of the relaxation coefficient α in equa- of convergence and stability of the algorithm.
tion (3) has a direct impact on the convergence The symbol gk denotes a bilinearly-interpolated properties of the algorithm; the greater the α, image gk needed to recover image samples on Ψ.
the faster the convergence, but only up to some Also, note that an interpolation function IΨ/Λ αmax above which the algorithm becomes unsta- replaces the sampling operator SΨ. This func- ble. Experiments have shown that the value of tion interpolates image samples (gΨ − ˜ max in (3) is closely related to the properties of fined on Ψ in order to recover samples on Λ.
the irregular sampling grid. Namely, the algo- Sauer and Allebach have studied three interpo- rithm has been most prone to instability in im- lators IΨ/Λ: one derived from bilinear interpola- age regions where irregular sampling grid is the tion and two based on triangulation with planar densest. Clearly, when increasing α above αmax, facets [6]. The implementation (2) of the re- the algorithm starts to diverge in those image re- construction algorithm (1) suffers from two de- gions where the number of irregular samples per ficiencies. First, by processing all images on Λ area is the highest. That is why it is proposed to introduce an additional α-correcting term in Ω, the fewer the samples of Ek(f ) thatneed to be computed. This allows signif- Ψ are samples of a function describing lo- cal density of irregular grid. We expect that al- gorithm implementations based on (4) will allow vergence than those based on formulation (3).
tion by zeroing parts of the spectrum leads in spatial domain to oscillations at sharp only marginally dependent on the degree of vari- luminance/color transitions. In [4], a de- ation in the local densities of irregular grids.
tailed discussion of the design of lowpass To be a good descriptor of local grid den- filters that minimize these effects can be sity, the function d should equal 1 where the grid is regular, should be greater than 1 in areas where there are more samples of irregular gridthan those of regular one, and less than 1 when converse is true. Experiments show that the ac-tual definition of the function is not critical; var- This operation can be very efficiently im- ious functions d seem to work almost equally well. It has been decided that the d function is computed by counting occurrences of irregularsamples in a 1 × 1 square neighborhood of each node of the regular grid, and then by filteringthe results by a 5 × 5 separable smoothing fil- The proposed reconstruction algorithm has been ter. We obtain in this way a regularly-sampled tested experimentally on images with various ir- function d; as samples on the irregular grid d regular sampling grids Ψ. In our previous work the nearest-neighbor samples of d (on the regu- [4], we presented results for both synthetic and natural disparity fields. Since the local sampledensity is less predictable in the case of natu-ral disparity fields here we are comparing the new algorithm with the previous, non-adaptive The implementation of equation (4) would, in one on natural data only. The disparities were general, require more memory and be less effi- computed from an ITU-R 601 stereopair Flow- cient than that of equation (2), however we opt erpot using an optical flow-type algorithm [8], for an implementation in the frequency domain and subsequently used in disparity compensa- in order to reduce the computational complex- tion to obtain the irregular grid Ψ. Then, the luminance and color of gΨ were computed us-ing bicubic interpolation [9]. Using gΨ, gΛ was reconstructed and compared with the original be the reconstruction error defined on Λ image. We tested the algorithm for P =4, 8 and by the inverse of the irregular grid density func- 16 and various α’s. We used lowpass filters pro- tion. Then, each iteration of the reconstruction posed earlier in [4] since they give a good com- promise between detail loss and aliasing.
Fig. 1(a) shows the PSNR evolution for lumi- 1. Fourier transform of the error ek sampled nance reconstruction error with fixed and adap- tive α. Note that the experimentally optimizedfixed α (highest stable value) for the luminance component was 0.4 for P =4, 0.3 for P =8 and 0.2 for P =16, while it was 0.7 for all P ’s in the adaptive case. Clearly, the convergence in the adaptive case is faster and the steady-statePSNR is higher; the benefits of α adaptation are chrominance errors. Note that similarly to the luminance case the higher the P , the better the performance of the algorithm, although the higherthe computational complexity due to the higheroversampling rate. While the increase of over- sampling from P =4 to P =8 shows up to a 1dB PSNR gain, a similar increase from P =8 to P =16 Subjectively, the reconstructed images were of very high quality. This suggests the viabil- ity of the proposed algorithm for various high- quality reconstructions in image processing and ory and practice of irregular sampling,”in Wavelet: Mathematics and Applications, J. Benedetto and M. Frazier, Eds., chapter 8,pp. 305–363. CRC Press, Boca Raton FL, [2] A. Sharaf and F. Marvasti, “Motion com- pensation using spatial transformations with forward mapping,” Signal Process., ImageCommun., vol. 14, pp. 209–227, 1999.
[3] P. Combettes, “The foundations of set the- oretic estimation,” Proc. IEEE, vol. 81, no.
based image reconstruction from irregularly- spaced samples,” in Proc. IEEE Int. Conf.
Image Processing, Sept. 2000, vol. II, pp.
[5] E. Dubois, “The sampling and reconstruc- tion of time-varying imagery with applica- tion in video systems,” Proc. IEEE, vol. 73,no. 4, pp. 502–522, Apr. 1985.
reconstruction of band-limited images fromnonuniformly spaced samples,” IEEE Trans.
Circuits Syst., vol. 34, no. 12, pp. 1497–1506,Dec. 1987.
proach,” in Signal Process. III: Theories and Applications (Proc. Third European Signal Process. Conf.), 1986, pp. 267–270.
[8] R. March, “Computation of stereo dispar- ity using regularization,” Pattern Recognit.
Lett., vol. 8, pp. 181–187, Oct. 1988.
[9] R.G. Keys, “Cubic convolution interpolation for digital image processing,” IEEE Trans.
Acoust. Speech Signal Process., vol. 29, no.
Figure 1: Evolution of PSNR of the reconstruc-

Source: http://iss.bu.edu/data/jkonrad/cpapers/Stas01icav3d.pdf