Image Reconstruction from Zero-Crossings

1. INTRODUCTION

The goal of low level vision is to detect changes in the reflectance of object surfaces and in surface orientation, geometry and depth value. In computer vision or the computational human vision, changes in image intensity of different scales of resolution is the optimal indicator of such changes. It has been proposed that different scales are set by filtering the image with 2-dimensional Gaussian filters of different sizes [2]. Intensity changes of object surfaces are spatially localized at different scales.

In the spherical model, we could extend the Gaussian filter on the plane to a filter (probability distribution) of Gaussian type, such as Fisher and von Mises filters on the sphere. It is quite natural to consider the exponential family of distributions on the sphere, because of its relation to spherical harmonics . We may consider some characterizations of the Gaussian to set up analogous filters in the spherical model. Alternatively, we may use the correspondence between the image plane and

IMAGE RECONSTRUCTION FROM ZERO-CROSSINGS

Su-shing Chen

Department of Computer Science, University of North Carolina

Charlotte, NC 28223, U.S.A.

the image sphere (see next section) to transform filtered planar images to scaled images on the sphere. That is, we may do the filtering in the plane first and then transform the filtered image to an scaled image G*I on the sphere.

In both cases, zero-crossings are computed by finding the zero set of the spherical Laplace operator .1. on G*I. Detection of edges in an image is reduced to solving for zero-crossings. A key question is whether detected edges contain full information about the image. If we can reconstruct the image from detected edges, then the question is affirmatively answered. From the view point of visual information processing, we do not need to reconstruct the original image, but only to show that sufficiently enough information is provided.

An extension of B. Logan's theorem to the image sphere will be presented. Thus, the theory of Marr and Hildreth [2] will be supported by this paper. The sphere is parametrized by the elevation and azimuth angles e and 4>. Any square integrable function f(9,cp) may be . decomposed into a sum of spherical harmonics { Y km(9,cp)}. which are products of exponentials and Legendre functions (special functions), functions of two variables e and cp. As we have stated earlier, this framework will provide the appropriate extension of Logan's theorem to two variables. It will be shown that such a function f can be reconstructed from the zero-crossings data, provided that enough of them are available.

This extension of theoretical basis Logan's theorem is of zero-eros sings the and spatiotemporal interpolation. Spatiotemporal interpolation is proposed in [ 1] and other references quoted there. The positional accuracy in human vision, corresponding to a fraction of the spacing between adjacent photoreceptors in the fovea [1], implies the spatial interpolation. The perception of continuous motion requires spatiotemporal interpolation [1]. Our extension of Logan's theorem addresses both the problem of spatial interpolation and an extension to 9,q>,t-variables for spatiotemporal interpolation.

2. THE SPHERICAL MODEL

The two imaging models are not very different. The image sphere (or hemisphere) is replacing the image plane tangent to it at the north pole. The perspective projection is extended beyond the image plane to the spherical perspective projection onto the image sphere. In [5], a nonlinear transformation sets up the correspondence between points on the image plane and points on the image sphere. Image intensity is defined by this correspondence, under the Lambertian model. If we move the origin (viewer) of the spherical model to infinity, the limit is the orthographic model. There are other nice features of the spherical model. For instance, the vanishing points are finite points on the image sphere.

Like the Fourier descriptor method of expanding functions on [O,t] in exponentials, we expand an image intensity function 1(9,q>) in spherical harmonics (Yk m (9,q>), -kS:m S:k, k=O, t ,2, ... } which form a basis of all square integrable functions on the unit sphere. There are other orthonormal expansions of image intensity functions, such as SVD and Karhunen-Loeve expansions; however, all the nice properties of Fourier descriptors are lost. This spherical harmonics expansion carries the group invariance over and forms a natural setting in the group representation theory of modern physics [5].

Each spherical harmonic Ykm(9,q>) is the product exp(imq>)Pkm(9), -kS:mS:k, for each k. In fact, there is a vector space spanned by Y k m, for each k=0,1,2, ..... The Legendre function Pkm is presented in [5]. For any square integrable 1(9,q, ), we have

These coefficients can be calculated numerically and lookup tables are constructed to speed up numerical work involving with Legendre functions. In [5], a distance d(l1 ,I2) is defined for equivalent shape classes It and 12. Thus, object recognition is performed in a standard fashion. If I 1 and I2 have respectively Fourier coefficients (c(l)km} and (c(2)km}, then the minimum of the vector (c(l)km -RsSc(2)km), over all rotations R, symmetries s and scalings S, is the distance between It and I2.

3. ZERO-CROSSINGS

The first order differential operators on the sphere are given by three basis operators

Dt =exp(iq>)( lJ/ lJ9+icot9lJ I lJq>),

D2= exp( -iq>)( -lJI lJ9+icot9lJ/ lJq>),

and D3= -lJI lJq>.

The effect of these three differential operators on spherical harmonics (Ykm(9,q>)} is given by

Dt Ykm=v(k-m)(k+m+1) Yk(m+t)·

D3Ykm= kYkm.

The spherical Laplace operator t. is computed to act on Ykm by

t. Ykm= k(k+t)Ykm·

Thus, the Laplace operator t. is a scalar matrix when restricted to the subspace V k = ( Y k m I -kS:mS:k} for each k=0,1,2, .... This is a very nice feature of the spherical model.

The correspondence between Q(X,Y) on the image plane and S(9,q>) on the image sphere is given by the nonlinear transformation between the image plane at the north pole and the sphere. The image intensity function I(9,q>) is conveniently defined as the image intensity function I(X, Y) under this correspondence. This is a reasonable assumption near the fovea in human vision or near the optical axis in computer vision because the plane is tangent to the sphere. For peripheral views or wide viewing angles, problems arise and we need to rotate our eyeballs or cameras. This amounts to a rotation of the sphere and its tangent plane at the north pole.

Since the Gaussian filter (distribution function) in [2] is to set up different scales of resolution, it is quite reasonable to project the 2-dimensional Gaussian filter on the plane G(X,Y ,a)=(l/v (27t) a) exp(-(X2+ y2)/2a2) to a filter on the sphere

G(e,cp,a)=(l/v (27t) a) exp( -cot2e/2cr2). Now, we consider t.(G*I) = 0. The zero set is the zero-crossings of I in the spherical model. The blurred image G*I may be expanded in terms of spherical harmonics:

Thus, zero-crossings are given by solutions of the following nonlinear equation

'Ik=l oo 'Im=-kkckmk(k+ l)Y km(e,cp)=O. For each k and m, Ykm(e,cp)= exp(imcp)Pkm(e), -k~m~k. The Legendre functions Pkm (e) could be calculated by lookup tables over a sufficiently fine subdivision of (0,1t ). Let d k m (eo) be the value of Pk m at a particular point eo. In the cross section at eo. we have

'Ik=l 00 'Im=-kkckmk(k+ l)dkm<eo)exp(imcp)=O. For bandlimited functions, we have 'Ik=l N 'Im=-kkckmk(k+ l)dkm<eo)exp(imcp)=O.

By interchanging summation signs over k and

m, we factor out

em(eo)='Ik=1 Nckmk(k+1)dkm<eo) and the equation of zero-crossings in the cross section at eo becomes

Thus, we have successfully reduced the equation of zero-crossings at each cross section to the equation of B. Logan [1], [3]. Like [1], [3], we may assume that the fun~tion is bandpass with one octave bandwidth. The complex coefficients em (e0)'s may be determined by the 2N solutions of the equation as the solutions of

'I m=-NN em (eo)exp(im<P2N )=0 After the set {em (eo)} is determined, we solve the set of equations

'Ik=1Nckmk(k+1)dkm(eo)=em(eo).-N ~m ~N. for the unknowns {ck m}. For each m, there are N unknowns {ckml. k=1,2, ... ,N. We need to set up a system of N equations, for each m, and N cross-sections { e 1· ... ,eN}:

The samples { e 1 , e 2 , ... ,eN} may be taken from a suitable subdivision · of (0,1t) such that the lookup tables of dkm(ei)· together with k(k+1), form determinants of maximum rank. Consequently, the image intensity function I(e,cp) is recovered from the spherical harmonics expansion whose coefficients { ck m } are determined by the above 2N+1 systems of N equations.

THEOREM. Under suitable conditions, image intensity functions in the spherical model may be recovered up to multiplicative constants from their zero-crossings data.