# Patent

## Title
Critical alignment of parallax images for autostereoscopic display

## Abstract

A method is provided for generating an autostereoscopic display. The method includes acquiring a first parallax image and at least one other parallax image. At least a portion of the first parallax image may be aligned with a corresponding portion of the at least one other parallax image. Alternating views of the first parallax image and the at least one other parallax image may be displayed.

## Background
CROSS REFERENCE TO RELATED APPLICATIONS
This application is a continuation of U.S. patent spplication Ser. No. 14/593,495, filed Jan. 9, 2015, which is a continuation of U.S. patent application Ser. No. 13/298,824, filed on Nov. 17, 2011, which is a continuation of U.S. patent application Ser. No. 10/536,005, filed May 20, 2005, which is a national stage entry of International Patent Application No. PCT/US2003/037203, filed Nov. 20, 2003 which claims the benefit of priority from U.S. Provisional Patent Application No. 60/427,961, filed Nov. 21, 2002. The contents of all the foregoing applications are herein incorporated by reference in their entireties.


FIELD OF THE INVENTION
The present invention relates to the visual arts field and more particularly to autostereoscopic imaging methods for producing two-dimensional images that, upon display, can be perceived to be three-dimensional without the use of special viewing aids.
BACKGROUND
The production of two-dimensional images that can be displayed to provide a three-dimensional illusion has been a long-standing goal in the visual arts field. Methods and apparatus for producing such three-dimensional illusions have to some extent paralleled the increased understanding of the physiology of human depth perception, as well as, developments in image manipulation through analog/digital signal processing and computer imaging software.
Binocular (i.e., stereo) vision requires two eyes that look in the same direction, with overlapping visual fields. Each eye views a scene from a slightly different angle and focuses it onto the retina, a concave surface at the back of the eye lined with nerve cells, or neurons. The two-dimensional retinal images from each eye are transmitted along the optic nerves to the brain's visual cortex, where they are combined, in a process known as stereopsis, to form a perceived three-dimensional model of the scene.
Perception of three-dimensional space depends on various kinds of information in the scene being viewed including monocular cues and binocular cues, for example. Monocular cues, include elements such as relative size, linear perspective, interposition, light, and shadow. Binocular cues include retinal disparity, accommodation, convergence, and learned cues (e.g., familiarity with the subject matter). While all these factors may contribute to creating a perception of three-dimensional space in a scene, retinal disparity may provide one of the most important sources of information for creating the three-dimensional perception. Particularly, retinal disparity results in parallax information (i.e., an apparent change in the position, direction of motion, or other visual characteristics of an object caused by different observational positions) being supplied to the brain. Because each eye has a different observational position, each eye can provide a slightly different view of the same scene. The differences between the views represents parallax information that the brain can use to perceive three dimensional aspects of a scene.
Parallax information does not have to be presented to the brain simultaneously. For example, left and right eye depth information can be presented alternately to the left and right eyes, resulting in depth perception as long as the time interval does not exceed 100 msec. The brain can extract parallax information from a three-dimensional scene even when the eyes are alternately covered and uncovered for periods of up to 100 msec each. The brain can also accept and process parallax information presented to both eyes simultaneously if the parallax information is sequenced. For example, two or more views of the same scene taken from different observational viewpoints may be shown to both eyes in a sequence (e.g., each one of the views may be shown to both eyes for a short amount of time before showing the next view in the sequence).
Several three-dimensional image display methods have been proposed and/or implemented. These methods may be divided into two main categories of stereoscopic display methods and autostereoscopic display methods. Stereoscopic techniques including stereoscopes, polarization, anaglyphic, Pulfrich, and shuttering technologies require the viewer to wear a special viewing apparatus such as glasses, for example. Autostereoscopic techniques such as holography, lenticular screens, and parallax barriers produce images with a three-dimensional illusion without the use of special glasses, but these methods generally require the use of a special screen.
Other systems have been proposed, however, that require neither special glasses nor special viewing screens. These systems include autostereoscopic television and motion picture systems that utilize alternately displayed views of a scene recorded by two cameras from different points of view. For example, the devices described in U.S. Pat. No. 4,006,291 to Imsand; U.S. Pat. No. 4,303,316 to McElveen; U.S. Pat. No. 4,429,328 to Jones et al.; and U.S. Pat. No. 4,815,819 to Mayhew et al., all utilize two carefully aligned cameras to record horizontally, vertically, or a combination of horizontally and vertically displaced views of a scene. While these systems deal mainly with techniques of image acquisition for autostereoscopic display using standard screens the cameras must be carefully matched and aligned to capture appropriate images. Further, once the images from the cameras have been captured, the alignment of the images cannot be readjusted.
In yet another approach, U.S. Pat. No. 5,510,831 issued to Mayhew describes a method of autostereoscopic display of parallax images using a slit scanning technique. In this technique, two cameras are carefully aligned to capture stereoscopic images. These images may be displayed by providing a first image as a background image and overlaying a second image onto the first image in the form of a scanning slit.
While each of these described methods and systems can be used to capture images for three-dimensional image display, there are problems associated with each. For example, many of the methods require the use of at least two carefully aligned cameras to capture images having parallax information. Aligning multiple cameras at a common scene is cumbersome. Not only are there multiple cameras to carry and to position, but proper alignment and color/luminance matching of the cameras can be difficult. Even after alignment, the cameras still may not provide a desired degree of image alignment for later display. Further, many of the prior art methods require special camera or lens mechanisms, video switching equipment, special viewing glasses, and/or special screens to create the three-dimensional illusion. Also, none of these three-dimensional display methods are suitable for use with randomly acquired images or with images extracted from a conventional video image stream (e.g., sequence) or images with parallel views, for example.
The present invention is directed to overcoming one or more of the problems associated with the prior art three-dimensional image display systems and methods.
SUMMARY OF THE INVENTION
A first aspect of the invention includes a method for generating an autostereoscopic display. The method includes acquiring a first parallax image and at least one other parallax image. A portion of the first parallax image may be aligned with a corresponding portion of the at least one other parallax image. Alternating views of the first parallax image and the at least one other parallax image may be displayed.
A second aspect of the invention includes a system for generating a set of aligned parallax images. The system includes a computer and an application running on the computer. The application is configured to display alternating views of two or more parallax images at a desired viewing rate and to manipulate the two or more parallax images such that at least a portion of first one of the parallax images is aligned with at least a portion of a second one of the parallax images.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 illustrates exemplary camera positions for generating parallax images in accordance with an exemplary embodiment of the invention;
FIG. 2 provides a flowchart representing a method for critically aligning parallax images in accordance with an exemplary embodiment of the invention;
FIGS. 3a-3d illustrate a transformation process for aligning parallax images in accordance with an exemplary embodiment of the invention; and
FIGS. 4a-4d illustrate various sequence patterns for display of parallax images during and after alignment in accordance with an exemplary embodiment of the invention.



DETAILED DESCRIPTION
One exemplary embodiment of the present invention includes a method for creating an autostereoscopic display by manipulating parallax images to create a resultant moving image. The resultant moving image may provide an autostereoscopic display and may be viewed on a conventional screen (e.g., a TV, computer monitor, a projection screen, moving image display, or any other type of display on which a moving image may be shown) As discussed above, parallax images include two or more images with overlapping visual fields but different points of view. For example, as illustrated in FIG. 1, a camera 10 may capture a first set of images and a camera 12 may capture a second set of images of a common scene 14 while being displaced from one another. The resulting sets of images from cameras 10 and 12 will be parallax images. That is, the set of images from camera 10 and the set of images from camera 12 will include some duplicated visual information by virtue of the fact that cameras 10 and 12 capture images of the same scene 14. The sets of images from cameras 10 and 12, however, will also include some different visual information resulting from the different points of view. These parallax images may serve as a basis for generating an autostereoscopic display consistent with the present invention.
It should be noted that cameras 10 and 12 may capture parallax images simultaneously or alternatingly. Parallax images may even be generated by a single camera 10 that captures a first image of scene 14 before moving to a new position (e.g., the position of camera 12 in FIG. 1) and capturing a second image of scene 14. Further, any length of time may pass between capturing parallax images of scene 14. For example, after capturing a first image of scene 14, a second image from a different point of view may be captured at any later time (1 second, 1 hour, 1 day, 1 year, etc.). Additionally, cameras 10 and 12 need not be in any special alignment configuration to produce suitable parallax images for use with the present invention.
An exemplary method of the present invention may involve the steps of acquisition and selection of source images, critical alignment of the images, and display of the images. In one embodiment, as illustrated in FIG. 2, the method may include acquiring source images at step 20, loading source images into alignment software at step 22, adjusting alignment parameters at step 24, saving/storing aligned images at step 26, and viewing aligned images at step 28.
Acquisition and Selection
The parallax images used to generate the autostereoscopic display may be acquired from a variety of imaging sources such as digital still cameras, digital video cameras, conventional film cameras and conventional video cameras (followed by subsequent digitization), computer generated graphics sources, and any other suitable imaging source. Additionally, the parallax images may be taken from a single image stream or from multiple image streams. Multiple image streams could be the output of a video stereo camera pair, or more generally, any two or more image sources with overlapping views of the same scene, including overlapping image sequences with parallel points of view. The parallax images may also be generated by a computer (as with 3D rendered graphics) or false-color images produced by RADAR, SONAR, etc.
Critical Alignment
The alignment process includes displaying alternating views of parallax images, at a desired viewing rate (i.e., a frequency at which the parallax image views are changed), and then manipulating the alternating views to match alignment. While the alternating views may be displayed at any desired viewing rate, in one embodiment, the viewing rate may be from about 3 Hz to about 6 Hz. The term “match alignment” refers to a condition in which a region of interest in an image to be aligned (i.e., converged) is positioned such that it occupies the same location within the frame of the image to be aligned as the corresponding region in a reference image frame. The region of interest may be all or part of the image to be aligned.
The alignment matching process begins by selecting a reference image 30, as shown in FIG. 3a, from a set of parallax images. Once reference image 30 has been selected, other images 32, as shown in FIG. 3b, from the parallax image set can be aligned to reference image 30. While only a single unaligned image 32 is shown in FIG. 3b, unaligned image 32 may represent a plurality of N images. One or more of the plurality of N images may be selected and aligned with respect to reference image 30. In certain situations, the stability of an autostereoscopic display consistent with the present invention may increase as the number of parallax images with differing parallax positions increases.
Reference image 30 may include a region of interest 34. The same region of interest 34′, albeit as viewed from a different point of view, may appear in unaligned image 32. Unaligned image 32 may be manipulated, as shown in FIG. 3c, for example, until region 34′ matches alignment with region 34, as illustrated in FIG. 3d. The manipulation process may be represented by an affine transformation including translation, rotation, scaling, and/or any other desired transformation. In addition, the point about which unaligned image 32 is rotated can also be adjusted to a position other than the center of the image.
The critical alignment process may be performed by a computer. For example, a set of parallax images may be loaded into a software application that enables a user to select a reference image. For example the set of parallax images may be loaded into open graphics language (OGL) software or other software suitable for manipulating image data. The computer may then automatically perform alignment of one or more of the remaining parallax images in the set. Alternatively, however, the software may enable an operator to input transformation parameters for one or more of the remaining parallax images in the set.
In one exemplary embodiment, a user may select a convergence point in the reference image and in one or more of the unaligned images. A computer can perform appropriate translation(s) to align the convergence points in the images based on calculated differences between the selected convergence points in the images. The computer may further perform pattern matching or feature extraction algorithms to determine, (a) whether any significant rotational disparities exist among two or more selected images, (b) the degree of the rotational disparities, (c) a point or rotation about which one or more of the selected images can be rotated, and (d) what rotational translation(s) would be required to match alignment of regions of interest in the selected images at or near the selected convergence points. Thus, the computer may align the images based on the convergence points selected and rotate the images to match alignment.
In another embodiment, the computer may control an even greater portion of the alignment process. For example, either an operator or the computer may select a convergence point in reference image 30. Next, the computer may use pattern-matching algorithms to compute an estimate for a matching region in unaligned image 32 that corresponds to the region around the convergence point in reference image 30. Any appropriate pattern matching algorithm known in the art may be used to perform this calculation. For example, a block of pixels from each of images 30 and 32 may be chosen and compared for similarity. This process may be repeated until a best match is chosen. Repetition of this process with increasingly smaller displacements may be performed to refine the translation value (e.g., to provide transformation parameters of sub-pixel resolution). Rotation may also be handled, as described above.
In yet another embodiment, the computer may enable an operator to input transformation parameters for one or more parallax images. Thus, for each image to be aligned, a user may manually enter and vary transformation parameters to align the parallax images. The alignment software may include, for example, a graphical user interface (GUI) where the user may enter transformation parameters such as translation parameters, scaling parameters, rotation values, a rotational pivot point, and any other parameters associated with image transformations. Additional features may include alignment guides to assist in qualitatively identifying matching areas, the ability to zoom in/out, and the ability to mask off (i.e., obscure) parts of an image outside the region of interest.
Regardless of the degree of automation, the transformation parameters in each process may be continuously adjusted until critical alignment is achieved. Critical alignment corresponds to a condition where the degree of alignment s sufficient to achieve a stable autostereoscopic display. Stability of the whole image may not be required, as long as at least a particular region of interest in the autostereoscopic display is stable.
One of the key elements of the disclosed alignment process is the use of parallax image manipulations of sub-pixel resolution to achieve critical alignment. Specifically, the transformations for achieving critical alignment may proceed to a sub-pixel level where one image is moved with respect to another image by an amount less than an integral number of pixels. That is, the transformations may include displacements of an integral number of pixels plus or minus any fraction of one pixel dimension. These sub-pixel manipulations may help to maximize the stability of the autostereoscopic display. To achieve sub-pixel alignment, image interpolation methods such as bicubic resealing, bilinear resealing, or any other appropriate image interpolation method may be employed.
Display
The parallax images, and alternating views thereof, may be displayed before, during, or after critical alignment of the parallax images. Displaying alternating views of the parallax images during the critical alignment process may aid in determining when one or more images match alignment with a reference image. For example, as the alternating views of the parallax images are displayed, a user may intermittently enter transformation parameters, as described above, to align two or more parallax images. One advantage of displaying the parallax images during the alignment process is that the user may see, in real time, the effect that the entered transformation parameters have on the alignment of the images. In this way, a user may progress incrementally toward a match alignment condition by entering transformation parameters, observing the alignment condition of the parallax images, and reentering transformation parameters to refine the alignment condition of the parallax images.
Once the parallax images have been aligned, the aligned images may be stored as a set of image data. Storing image data in this manner may be useful for displaying the aligned parallax images in a stand-alone operation after alignment has been completed. For example, the aligned parallax images may be stored and later displayed in a video format. Further, the stored, aligned parallax images may be reloaded into the alignment software for viewing or further processing, including, for example, aligning the images with respect to a new region of interest.
Alternatively, a record of the transformations used to align the images (i.e., image alignment parameters) may be stored. In a later process, the stored transformations may be retrieved and reapplied to the set of parallax images to regenerate the match alignment condition of the images. In one embodiment, the image alignment parameters may be stored and used to align higher resolution versions of the same images. This process may be useful, for example, to speed processing of high resolution images. Rather than performing the critical alignment process on high resolution images, which may require significant processing resources and may slow or prevent real-time manipulation of the images, the manipulations may be performed on low resolution versions of the high resolution images. Then the alignment parameters determined for the low resolution images may be applied to the higher resolution versions of the images.
Unlike stereoscopic displays, the autostereoscopic images consistent with the invention can be viewed as a sequence of images on conventional two-dimensional displays (e.g., screens), such as a television, computer monitor, a projection screen, moving image display, or any other type of display on which a moving image may be displayed. A set of aligned images can be displayed in sequential order, a randomly selected order, or any other desired order. For example, FIG. 4a represents a set of six parallax images (e.g., three right-left pairs) in matched alignment. FIG. 4b illustrates a sequential playback pattern in which the aligned parallax images in the set are displayed serially in a repeating sequence. FIGS. 4c and 4d demonstrate two possible random playback sequences. As noted above, the frequency with which the views in the sequence are changed (i.e., the viewing rate) may be any desired frequency. In one embodiment, however, the viewing rate may be between about 3 Hz and about 6 Hz. Furthermore, the viewing rate need not be constant, but may be varied over time.
Analysis:
In addition to or instead of displaying the aligned parallax images, computational analysis may be performed on the images. For example, certain quantitative information may be extracted from the aligned parallax images. As a result of the parallax information contained in the images, an apparent shift of an object may exist between different views. The apparent shift refers to the distance a point in an image appears to move between images taken from different points of view. By measuring the amount of apparent shift of a point in two or more parallax images, quantitative position values may be computed for the point in relation to objects in the image if certain other information, such as the distance between the camera and a point in the image, is known. For example, by knowing the distance between the camera and the ground in an image captured from the air, and by measuring the apparent shift of the top edge of a building between two or more parallax images, the height and/or volume of the building may be calculated.
Additionally, quantitative positional information for scene points may be calculated based on known quantities appearing in the image. For example, if a certain model of automobile appears in the image and dimensional data is available for that automobile, then positional values may be calculated for other scene points by measuring the apparent shift of one or more points in the scene associated with the automobile.
Further, by determining position values for enough scene points in an image, a depth map for objects in the scene can be computed. This depth map can be used to create views corresponding to intermediate parallax angles. This allows for interpolation of views from the originally captured images.

## Claims

1. A method for aligning stereoscopic camera images on a display, comprising:
acquiring a first image of a first visual field and at least one second image of a second visual field that at least partially overlaps the first visual field, wherein differences between the first image and the second image include parallax information;
identifying a first region in the first image that corresponds with a second region in the at least one second image;
displaying alternating views of the first image and the second image on the display;
aligning the first region in the first image with the second region in the at least one second image such that the first region of the first image occupies the same location as the corresponding second region of the at least one second image to generate a set of aligned parallax images;
performing a computational analysis on at least two images from the set of aligned parallax images to extract quantitative information associated with the parallax information; and
generating an interpolated image of a third visual field using the extracted quantitative information.

2. The method of claim 1, wherein performing a computational analysis on at least two images from the set of aligned parallax images to extract quantitative information associated with the parallax information comprises:
measuring an apparent shift of a scene point in the at least two images from the set of aligned parallax images; and
computing at least one position value for the scene point based on the measured apparent shift.

3. The method of claim 2, wherein computing at least one position value for the scene point based on the measured apparent shift comprises:
computing the at least one position value for the scene point based on the measured apparent shift relative to at least one object in the set of aligned parallax images.

4. The method of claim 2, wherein computing at least one position value for the scene point based on the measured apparent shift comprises:
computing the at least one position value for the scene point based on the measured apparent shift and a known parameter in the set of aligned parallax images.

5. The method of claim 4, wherein the known parameter comprises known dimensional data in the set of aligned parallax images.

6. The method of claim 1, wherein displaying alternating views of the first image and the second image on the display comprises displaying alternating views of all of the first image and all of the second image.

7. The method of claim 1, wherein performing a computational analysis on at least two images from the set of aligned parallax images to extract quantitative information associated with the parallax information comprises:
measuring an apparent shift of a first scene point of an object in the at least two images from the set of aligned parallax images; and
computing at least one position value for a second scene point in the set of aligned parallax images based on the measured apparent shift of the first scene point.

8. The method of claim 7, wherein at least one parameter of the object is known.

9. The method of claim 1, wherein generating an interpolated image of a third visual field using the extracted quantitative information comprises:
computing at least one position value for a plurality of scene points in the at least two images from the set of aligned parallax images based on the extracted quantitative information;
computing a depth map for at least one object in the set of aligned parallax images; and
generating the interpolated image of the third visual field using the computed depth map.

10. The method of claim 1, wherein the interpolated image of the third visual field comprises an intermediate parallax angle different from the first image and the second image.

11. A system for aligning stereoscopic camera images on a display, comprising:
a display; and
a processor coupled to the display and configured with processor executable instructions to perform operations comprising:
acquiring a first image of a first visual field and at least one second image of a second visual field that at least partially overlaps the first visual field, wherein differences between the first image and the second image include parallax information;
identifying a first region in the first image that corresponds with a second region in the at least one second image;
displaying alternating views of the first image and the second image on the display;
aligning the first region in the first image with the second region in the at least one second image such that the first region of the first image occupies the same location as the corresponding second region of the at least one second image to generate a set of aligned parallax images;
performing a computational analysis on at least two images from the set of aligned parallax images to extract quantitative information associated with the parallax information; and
generating an interpolated image of a third visual field using the extracted quantitative information.

12. The system of claim 11, wherein the processor is configured with processor-executable instructions to perform operations such that performing a computational analysis on at least two images from the set of aligned parallax images to extract quantitative information associated with the parallax information comprises:
measuring an apparent shift of a scene point in the at least two images from the set of aligned parallax images; and
computing at least one position value for the scene point based on the measured apparent shift.

13. The system of claim 12, wherein the processor is configured with processor-executable instructions to perform operations such that computing at least one position value for the scene point based on the measured apparent shift comprises:
computing the at least one position value for the scene point based on the measured apparent shift relative to at least one object in the set of aligned parallax images.

14. The system of claim 12, wherein the processor is configured with processor-executable instructions to perform operations such that computing at least one position value for the scene point based on the measured apparent shift comprises:
computing the at least one position value for the scene point based on the measured apparent shift and a known parameter in the set of aligned parallax images.

15. The system of claim 14, wherein the known parameter comprises known dimensional data in the set of aligned parallax images.

16. The method of claim 11, wherein the processor is configured with processor-executable instructions to perform operations such that displaying alternating views of the first image and the second image on the display comprises displaying alternating views of all of the first image and all of the second image.

17. The system of claim 11, wherein the processor is configured with processor-executable instructions to perform operations such that performing a computational analysis on at least two images from the set of aligned parallax images to extract quantitative information associated with the parallax information comprises:
measuring an apparent shift of a first scene point of an object in the at least two images from the set of aligned parallax images; and
computing at least one position value for a second scene point in the set of aligned parallax images based on the measured apparent shift of the first scene point.

18. The system of claim 17, wherein the processor is configured with processor-executable instructions to perform operations such that at least parameter of the object is known.

19. The system of claim 11, wherein the processor is configured with processor-executable instructions to perform operations such that generating an interpolated image of a third visual field using the extracted quantitative information comprises:
computing at least one position value for a plurality of scene points in the at least two images from the set of aligned parallax images based on the extracted quantitative information;
computing a depth map for at least one object in the set of aligned parallax images; and
generating the interpolated image of the third visual field using the computed depth map.

20. The system of claim 11, wherein the processor is configured with processor-executable instructions to perform operations such that the interpolated image of the third visual field comprises an intermediate parallax angle different from the first image and the second image.