# Patent

## Title
Image processing method and system

## Abstract

The government may have certain rights to this invention under NSF grant number ASC 892019.

## Background
The present invention describes a system for correcting perceptual distortion in an image of a three-dimensional object, especially a wide angle image. More specifically, the present invention defines a correction system formed by an image-changing object such as a processor or a lens, which corrects for distortion in a wide angle image.

Cameras operate by converting light reflected from a three dimensional object into a two dimensional image. The conversion between different numbers of dimensions uses a "projection" to transform between the multiple dimensions. Conceptually, camera-type devices, including lens-operated cameras, CCD arrays, and photosensitive elements and the like, all operate in the same way.

FIG. 1 shows an object 100 producing light reflections 101 input to a lens system 110. The angle .theta. of the lens limits the amount of the object 100 which can be seen at one time. This angle .THETA., therefore, defines the maximum amount of the object which can be imaged. Therefore, for lens 110 with angle .theta., the part of the object between area 102 and 104 can be simultaneously imaged. A wider angle lens can image more of the object.

The rays of light are focused by the lens 110 onto an image receiving surface 120, which in a camera is embodied by a photoplate.

The lens can alter the light in various ways for various conditions. A conventional pinhole camera allows a single ray of light from each point on the object to impinge therethrough. Therefore, light from the point A on the object 100 is received at point B on the image receiving surface 120. If the object 100 is at the focal length distance 130 from the lens 110, then the dimension B can be related to the dimension A by any desired transformation amount, where the axis 132 is the central axis of the device. For example, lenses are known wherein B=A; B=sin A, B=Fourier transform (A) and other relations.

The inventors, however, recognized that linear perspective images may become distorted, especially as the angle of the lens increases. For a 180.degree. lens, the photoplate would need to become theoretically infinite. Techniques such as "fisheye lens", described in U.S. Pat. Nos. 4,412,726; 4,647,161; 4,464,029 are used to avoid the necessity for an infinite photoplate.

FIG. 1A shows a direct view transformation of a scene, and FIG. 1B shows a linear perspective view of that scene. Notice how the circles/spheres in FIG. 1A have become distorted in FIG. 1B. The straight lines in FIG. 1B, however, have become curved in FIG. 1A.

It is known that we can apply a conformal or angle-preserving transformation to an image, in a way that preserves the amount of direct view distortion. The curvature distortion can be further reduced by choosing an appropriate conformal transformation T and interpolating between T(DP(r)) and r.

It is an object of the present invention to correct for the geometric perceptual distortion which occurs in such pictures. This is done according to a first aspect of the present invention by transforming the images using a tradeoff between two competing transforms, to maximize the amount of distortion compensation. This can be done either via an optical correction mechanism or by an electronic correction.

These and other aspects of the invention will now be described in detail with reference to the accompanying drawings, wherein:

FIG. 1 shows a schematic of operation of a normal lens system;

FIGS. 1A and 1B show linear perspective and direct view transformations;

FIG. 2 shows a linear perspective transformation;

FIG. 3A shows how multiple flat-backed cameras can obtain a wide angle image of an object;

FIG. 3B shows how a single flat-backed camera cannot obtain that image;

FIG. 4 shows a concept of a direct view transformation;

FIG. 5 shows the conceptual projection effected according to the present invention;

FIG. 6 shows the geometry of the transformation;

FIG. 7 shows an image processing system according to the present invention;

FIG. 7A shows an analog image processing system;

FIG. 8 shows a flowchart used by the image processing system of the present invention;

FIG. 8A shows how the images are re-mapped according to the present invention;

FIG. 9 shows a first lens embodiment of the present invention; and

FIG. 10 shows a second lens embodiment according to the present invention.

In order to describe the preferred embodiment, we must first consider the basis from which the present inventors realized the concepts of the present invention. Realistic image synthesis is based on modelling the physics of light propagations into three dimensional environments. The geometry of the three dimensional space must be projected onto the picture plane. The inventors realized that this transformation can cause distortion, especially when linear perspective is used.

The inventors of the present invention also noticed that distortions which occur in images can be classified as one of two main types:

I. Zero Curvature Condition--straight lines in the object space should be represented by straight lines in the image. The first kind of distortion changes the shape of straight lines.

II. Direct View Condition--All objects should look as if we were looking directly at them. The three dimensional object which we know as a sphere should look like a circle when we are looking directly at its two-dimensional rendering. The direct view distortion changes the look of a circle.

The inventors have determined a technique for obviating this problem. First, a brief description of the analysis.

Theoretically, a proper two dimensional image will produce the same image on the retina of an eye that the actual object would have produced. Assume a plane in the path between the object and the eye. Paint each point on that plane with the color of the ray of light going into the plane. When the eye then looks at the image on that plane, it should ideally see an image which coincides precisely with the image that it would have seen looking at the object. This only works, however, if the observer is looking only with one eye, or is far enough away that both eyes receive the same image. The user must also be far enough away such that looking at the picture, the position of the eye coincides with the position of the eye or camera. This is where the distinctions between real objects and pictures begin to become more apparent. We can look at a picture from various distances and directions with both eyes without our perception of the image changing at all. While almost all cameras use linear perspective, the inventors found that deviations from linear perspective can improve the look of an image.

The inventors have found that the direct view condition and zero curvature conditions cannot both be exactly satisfied simultaneously. Accordingly, according to the present invention, a technique is established for devising a tradeoff between the two types of distortions. The structure defined according to the present invention obviates this problem by defining a tradeoff between the two. The inventors have found that the zero curvature condition can be satisfied by the transformation:

The direct view condition can be satisfied by: ##EQU1##

The inventors prefer to blend these two equations into the following transformations:

and .phi.=.o slashed.. ##EQU2##

Where .rho. and .phi. are the transformed polar coordinates corresponding to the original polar coordinates r and .o slashed., .lambda. is the transformation ratio defining the amount of each transform to be used, and R is the size of the new image. So, each point on the original image at position r, .THETA. is transformed to the point .rho., .phi.. The transformation ratio A is used to weight the straightness of lines transformation. Its compliment, 1-.lambda., is used to weight the direct view condition transformation.

The transformation leaves a new image on the screen with image elements at new positions represented by the equation above. Interpolation between pixels may be necessary because of the stretching and compressing caused by the transformation.

To explain this more conceptually, the linear perspective transformation is shown in FIG. 2. The rays of light 200 and 202 from object 100 are input through pinhole 204 to impinge on the rear photographic plate 206 of camera 208. The straightness of the lines can be preserved by mapping the image that is originally formed on surface 206 onto a new surface 210. This flat transformed surface effects a linear perspective transformation by the amount r/R.

Now, consider the situation of looking at an object 100 with a wide view as shown in FIG. 3A. Cameras 300, 301, and 302, all "look" directly at the object. The light rays 303, 304, and 305 arrive relatively straight. This situation assumes the hypothetical situation where all the cameras face the object 100, i.e., each faces in a different direction. FIG. 3B shows what would happen if all the cameras faced the same way. Camera 310 receives rays 312 and 314 which are skewed with respect to one another since the camera back 316 is parallel to the camera back 306 of camera 311. This would be the case for the usual camera which has a flat back--all imaging surfaces of the camera back are parallel. However, camera 310 is receiving rays from object 100 at an angle which distorts those rays.

Accordingly, the inventors found that in order to obtain an image which is undistorted in the direct view sense, each image point must appear to point directly towards the image. That is, the plurality of cameras which are effectively used to obtain the image in FIG. 3 must have what amounts to a spherical image obtaining surface.

FIG. 4 shows the direct view transformation which preserves the shape and direction of objects. This essentially forms a projection of images 100, 150 to a spherical image obtaining surface 400 in a way such that each image object is directly viewed.

In the real world, however, cameras do not have spherical image receiving surfaces. Accordingly, the real world transformation used according to the present invention first obtains the image on a flat image receiving surface 500 as done by standard cameras. The image on the flat image receiving surface 500 is then mapped to sphere 510. The projection to the sphere 510 essentially maintains the direct view condition of the image. Now, the image on the sphere 510 needs to be mapped back to a flat surface which is done according to the present invention by projecting the image from the sphere 510 back to a flat surface 520.

The ray 502 then hits the initial image receiving surface 500 at point 504, which is located at a position r, .THETA. in polar coordinates. This point r, .THETA. is mapped onto the sphere 510, and then to the flat image receiving surface 520. The position of mapping onto the flat receiving surface 520 is referred to herein as .rho., .phi.. Assuming the sphere is of radius 1, ##EQU3##

FIG. 6 shows the overall relationship. Calling the radius of the circle R.sub.0, the original image on the photographic plate deriving from the object would be at the point r. The transformed image is at the point .rho.. As seen from the diagram of FIG. 6, assuming R.sub.0 =1;

where ##EQU4##

As described above, .lambda. can either be constant, or variable. .lambda. may change depending on (.rho. and .phi. the viewing angle of the object). The preferred case balances between direct view compensation and zero curvature compensation to compensate for different directions of view at the object. For example, in the case of FIG. 3, views from the direction of camera 300 might be optimized for zero curvature conditions, but those views from cameras could be optimized for direct view.

For a lens-embodied system, the system would be optimized based on the position of the lens. For the operation described herein using electronic image processing, this can be done on a pixel-by-pixel basis.

Therefore, using the above information, .lambda.=1 is a complete linear projection, while .lambda.=0 is a projection which maintains the direct view transformation.

Another embodiment of the invention replaces the constant .lambda. by a function of r and .THETA. in polar coordinates to use .lambda.(r,.THETA.) to allow different trade-offs between different types of distortion for different parts of the picture. When there are few long lines parallel to the edges of a wide angle picture, and a large number of objects of simple familiar shape, .lambda. should be small. An image with a lot of long straight edges would be better compensated if .lambda. is high.

The first embodiment of the invention uses these techniques to provide a system which corrects distortion in images using the techniques described above. Camera 700 obtains a visual image of a scene 702. Camera 700 can be any camera which is capable of obtaining an image of a scene, including a photographic-type camera, an electronic camera or the like. The output is produced as 703 which is coupled to an image processing computer 704, with associated image memory 706, which processes the received information and displays it on output unit 710.

An alternate embodiment effects this by functionals. A functional F is an equation which returns a numerical indication of proper fit. Then minimization of these functionals allows determination of an error functional which is a numerical expression for the perceptual error for each type of distortion and simultaneously minimize these functionals. ##EQU5##

If we set K(T.sub.plane, x,y)=0, we can see that all the second derivatives of .eta. and .xi. should be equal to zero, therefore, T.sub.plane should be a linear transformation. This coincides with the fundamental theorem of affine geometry which says that the only transformations of the plane which map lines into lines are linear transformations.

Direct view error function. In order to formalize the direct view condition we consider mappings which are locally equivalent to direct projection as defined in Section 3. We can observe that the projection onto the sphere is locally a direct projection. Therefore, if we use the decomposition P=T.sub.sphere o II.sub.sphere we have to construct the mapping T.sub.sphere which is locally is as close to a similarity mapping as possible. Formally, it means that the differential of the mapping T.sub.sphere, which maps the tangent plane of the sphere at each point x to the plane T.sub..function.(x) R.sup.2 =R.sup.2 coinciding with the picture plane vat the point .function.(x), should be close to a similarity mapping. The differential DT.sub..function.(x) can be represented by the Jacobian matrix J of the mapping T.sub.sphere at the point x. A nondegenerate linear transformation J is a similarity transformation if and only if .vertline.Jw.vertline./.vertline.w.vertline. doesn't depend on w.

If this ratio depends on w, then we define the direct view error function to be ##EQU6## can be used as the measure of "non-directness" of the transformation at the point 9for more detailed discussion see [Aur95].)

It can be shown that ##EQU7## where .EPSILON.=(.eta..sub.u).sup.2 +(.xi..sub.u).sup.2, F+.eta..sub.u .eta..sub.v +.xi..sub.u .xi..sub.v, G=.eta..sub.v.sup.2 +.xi..sub.v.sup.2.

Additional constraints can be imposed on the acceptable transformation. For example, it is possible to design transformations that preserve vertical and/or horizontal straight lines in an image. The analytical form of these transformations can be different from DP (r) or any other expression in the patent, or might be exist (some transformations can be computed only numerically.)

In particular, it is feasible to make corrective transformations only in one coordinate, preserving the other. If the horizontal coordinate is preserved, vertical lines remain vertical.

The image altering device of the present invention can be any kind of image changing element including a lens, a microprocessor or DSP based image processor, or an analog image processor. The digital image processor device operates as follows The image processor operates according to the flowchart of FIG. 8. At step 800, the image is acquired. The image can be acquired by any known technique, but is preferably acquired using either a photographic camera with a photographic plate or an electronic camera such as a video camera or CCD device. The information must be converted into a form where it can be processed. The preferred embodiment of this invention converts the image into an electrical signal 702. Electrical signal 702 is coupled to image processor 704, which determines the content and kind of distortions in the picture at step 802. This can be done in many ways. One simple way of doing this is to manually observe the image relative to the original, and manually ascertain the kind and quality of distortions therein.

This can also be done automatically using software which is appropriately programmed to determine the amount and kind of lines and spheres in the image. Different parts of the image may include different kinds of distortions.

At step 804, the different distortions in the different parts of the images are correlated against the correction value. As discussed above, this system corrects these distortions using a higher value of .lambda. for linear perspective distortion so that the linear perspective distortion can be expressed according to the equations above, with .lambda.(r,.THETA.). A smaller value of .lambda. makes the correction closer to the second half of the equation thus better preserving the shape of the objects. Based on this analysis, a parameter .lambda. is assigned as a function of R and .THETA.. .lambda. can be constant for areas of said image, or can be a continuously varying function.

At step 806 the pixels are remapped according to .rho.,.THETA.. Examples of this mapping operation are shown in FIG. 8A. The original image 850 is shown with pixel areas A, B, C and D; each of which can be single pixels or blocks of pixels. The mapping operation is shown in FIG. 8A where each of the pixel areas from (r, .THETA.) are mapped to locations (.rho., .psi.) to form the new corrected image 860.

Pixels A and B are mapped in the new image closer to one another than they were in the original image. The pixels include a hatched overlap area 862 therebetween. This means that extra pixels are formed between the pixel areas A and B. These extra pixels are interpolated at step 808. The area 862 is interpolated using the combination of the pixels from A and B which form the overlap area. Such interpolation is well known in the art.

The pixels C and D show precisely the opposite situation. The pixels C and D in the new image are further spaced from one another than they were in the original image. This space area 864 is interpolated at step 808 to provide appropriate missing pixels between the pixels C and D.

Both of these operations can be analogized to images on putty which are being stretched or compressed. The AB to AB transformation corresponds to compression of the image on the putty. The CD to CD information corresponds to a stretching on that same hypothetical image.

Once the missing and extra pixels have been interpolated at step 808, the new image is stored at step 810. The storage of the new image is preferably in an image type memory, but can also be effected through a charge coupled device array or on a photographic plate or on a photosensitive surface such as a drum of a copying machine or laser printer.

Step 812 shows "display" of the image which generically refers to herein as displaying it on a screen, on a photographic plate or paper or on a printer. The new image which is displayed at step 812 has corrected for the content and kind of distortions therein by the techniques described above.

The system can also be carried out as shown in FIG. 7A. There, the camera output 703 is coupled to analog circuit 740 which has circuitry to calculate the function (1) or (2) above. For example, circuit 740 can be effected in components (e.g. transistors, capacitors, resistors, etc.) or in analog VISI.

An alternate embodiment of the present invention is shown in FIGS. 9 and 10 which show a lens system constructed according to the teachings of the present invention. FIG. 9 shows the lens effected by a barrel lens device 900 including lens elements 902 and 904. More generally, however, any number of lens elements could be used. Parameters of lenses in the barrel 902 and 904 are variable with respect to one another. Those having ordinary skill in the lens forming art well understand how to alter lens characteristics to make a lens system having any desired transfer function. The lens system in FIG. 9 is variable such that the overall output of the lens varies between tangent .beta. and tangent of .beta./2, where .beta. is the input ray direction and as defined above. The field of view of the lens can also be changed as in a "zoom" lens. The alternate embodiment shown in FIG. 10 provides a lens which has different kinds of transfer characteristics for different impinging rays. The ray 1010 has a transfer characteristic of tangent .beta.. The ray 1012 has a transfer characteristic of tangent .beta./2. More generally, this lens provides different transfer characteristics between tangent p and tangent .beta./2 for incoming rays coming from different directions.

The simplest single lens system is shown in FIG. 11. In this figure, the incoming rays are transformed with a transfer characteristic which is between but not equal to, either of tangent .beta. or tangent .beta./2. More generally, this lens has a transfer characteristic of tangent .beta./k, where k is greater than or equal to 1 and less than or equal to 2.

An alternate embodiment uses an additional constraint which preserves vertical straight lines, under this additional limitation, the following transformation can be shown to satisfy direct view condition: coordinates in the new image and w is the width of the ##EQU8## image. We assume x to be the horizontal coordinate and y to be the vertical coordinate.

This transformation can be used instead of the direct view projection in all the constructions given above. The parametric family of transformations linearly interpolating between linear perspective projection and the projection above can be written as ##EQU9## If we exchange x and y and .eta. and .xi. in the form above, the resulting transformation will preserve horizontal straight lines instead of vertical.

Although only a few embodiments have been described in detail above, those having ordinary skill in the art will certainly understand that many modifications are possible in the preferred embodiment without departing from the teachings thereof.

All such modifications are intended to be encompassed within the following claims.

## Claims

1. A method of correcting an image, comprising: different locations in the image; first transformation parameter being a transformation for preserving straightness of lines, and said second transformation parameter being a transformation minimizing distortion of shapes; and correcting of at least one of said components being based on both said first transformation parameter and said second transformation parameter.

2. A system for processing images, comprising: image; determine kinds of information in the image, and to obtain first and second transformation parameters for the image, said first transformation parameter correcting for a first straightness of lines distortion in the image, and said second transformation parameter correcting for a second distortion of shape distortion in the image and to correct said image by moving its components to different locations based on both said first transformation parameter and said second transformation parameter at the same time, in addition to a transformation ratio that sets a ratio between said first and second transformation parameters.

3. A method of correcting an image, comprising: different locations in the image; first transformation parameter being a transformation for preserving straightness of lines, and said second transformation parameter being a transformation minimizing distortion of shapes; and correcting of at least one of said components being based on both said first transformation parameter and said second transformation parameter, wherein said first transformation corrects as .rho.=r/R, where r is the polar coordinate of an initial image, and R is a dimension of the photographic plate, and said second transformation corrects as ##EQU10## where .rho. and .phi. are transformed polar coordinates corresponding to original polar coordinates r and .o slashed., .lambda. is a transformation ratio defining the amount of each transform to be used, and R is the size of an image; and ##EQU11## .

4. A method of correcting an image, comprising: different locations in the image; first transformation parameter being a transformation for preserving straightness of lines, and said second transformation parameter being a transformation minimizing distortion of shapes; and correcting of at least one of said components being based on both said first transformation parameter and said second transformation parameter, further comprising: first transformation ratio between said straightness of lines transformation and said distortions of shape transformation which will appropriately correct for said distortion in said first part of said image; second transformation ratio, different than said first transformation ratio, between said straightness of lines transformation and said distortions of shape transformation which will appropriately correct for said distortion in said second part of said image; and transformation ratio and correcting distortion in said second part of said image using said second part of said image using said second transformation ratio.

5. A method as in claim 3 wherein said transformation ratio .lambda. is a function of coordinates of the image.

6. A method as in claim 4 wherein said obtaining an image obtains an image on a photographic plate.

7. A method as in claim 4 wherein said obtaining an image comprises obtaining an electronic view of the image.

8. A method of obtaining a distortion-free image, comprising: projected onto a flat image plane; image from said first flat image plane into an image projected onto a second, curved image plane; and image from said second image plane to a third, flat image plane, wherein said projections are carried out such that ##EQU12## and .phi.=.o slashed.where .rho. and .phi. are transformed polar coordinates corresponding to the original polar coordinates r and .o slashed., .lambda. is a transformation ratio defining the amount of each transform to be used, and R is the size of the image.

9. A method of correcting an image, comprising: image, and classifying said distortions based on whether they will be more easily corrected by a linear transformation or by a direct view transformation; image; transformation and direct view transformation as weighted by said first and second transformation ratio respectively and a compliment of said transformation ratio respectively, wherein said correcting is carried out such that ##EQU13## and .phi.=.o slashed., where .rho. and .phi. are the transformed polar coordinates corresponding to the original polar coordinates r and .o slashed., .lambda. is the transformation ratio defining the amount of each transform to be used with .lambda.1 being used for said first area, and .lambda.2 being used for said second area, and R is the size of the new image.

10. A method as in claim 8 where .lambda. is a function of coordinates of the image on the screen.

11. A method as in claim 8 wherein said first and second transformations are carried out by a computer which computes new pixel locations for pixels of the image.

12. A method as in claim 8 wherein said transformations are carried out by a lens.

13. A method of correcting an image, comprising: image, and classifying said distortions based on whether they will be more easily corrected by a linear transformation or by a direct view transformation; setting a first transformation ratio .lambda.1 for a first area of the image; image; transformation and direct view transformation as weighted by said first and second transformation ratio respectively and a compliment of said transformation ratio respectively.

14. A method of correcting distortion in images, comprising: therein, using a transformation ratio which is greater than zero, and less than one, to balance linear transformation and direct view transformations and to use both linear transformation and direct view transformations at the same time, wherein said transformation ratio is different for different parts of the image.

15. A method as in claim 14 wherein said transformation ratio is different for different parts of the image.

16. A method as in claim 14 wherein said transformation ratio is a function of position in the image.

17. A method as in claim 13 wherein said transformation causes some of the areas of the transformed image to be closer together than the original, and causes some areas of the transformed image to be further apart than the original, and further comprising