Method and apparatus for automatic keystone correction

[0002] This application claims the benefit of U. S. Provisional Application Serial No. 60/172,051 filed Dec. 23, 1999.

[0003] 1. Field of the Invention

[0004] The present invention relates generally to distortion correction systems and, in particular, to the automatic correction of distorted computer projection display images.

[0005] 2. Description of the Prior Art

[0006] Unless a projector is carefully aligned to the projection surface (screen), the resulting image on the screen appears distorted, or “keystoned”. In prior art, “keystone” refers specifically to a symmetric, trapezoidal distortion caused by projector pitch misalignment. In this application, the term “keystone” refers to the broader class of distortions caused by any misalignments in projector position or orientation.

[0007] Keystoning is undesirable, not only because viewers find this warping to be distracting, but also because the distortion can significantly affect the interpretation of visual information such as graphs, bar charts and technical drawings. This keystoning can be prevented by aligning the projection system's optical axis so that it is perpendicular to the screen and ensuring that the image is not rotated with respect to the screen.

[0008] Unfortunately, in many situations, these constraints (particularly the former) create a projected image that is either too small (when the projector is too close to the screen) or badly placed (when the projected image is too close to the floor). In view of these constraints, keystoning is often unavoidable.

[0009] Some sophisticated LCD projectors offer manual keystone correction.

[0010] Using manual controls, a user is able to adjust the projection system to eliminate distortions caused by vertical misalignment. The prior art only addresses symmetric vertical keystoning caused by projector pitch (where a rectangular source image projects to a trapezoid on the screen). In typical projectors, a pitch of up to ±12° may be rectified and the best systems can correct a pitch up to ±20°. More importantly, the prior art cannot rectify distortions caused by any other misalignments, such as projector yaw or roll.

[0011] The prior art requires the user to manually adjust the projection system to eliminate keystoning. This can be time consuming and requires the user to have access to the projector. Manual controls would be particularly limiting if the projector were capable of rectifying a broad class of distortions since the user would be required to simultaneously optimize several parameters.

[0012] It is, therefore, an object of the present invention to exceed the prior art limitations of pitch correction. It is another object of the present invention to allow rectification of any distortions due to projector placement and enable users to mount projectors anywhere in the room. It is a further object of the present invention to enable fully automatic adjustment of all parameters. However, if the user wishes to manually refine the process, the present invention also offers an intuitive interactive interface.

[0013] The method of the present invention entails determining a mapping between points in the source image frame and the corresponding points in the viewer image frame; identifying boundaries of the projected image frame within the viewer image frame; computing a possible mapping between the projected image frame and the viewer image frame; inferring a possible mapping from the source image frame to the projected image frame based upon the mappings computed in the previous two steps; determining an optimal placement for the corrected application image within the projected image frame (this is the largest rectangle that is completely contained within the projection of the computer display, i.e., the keystoned quadrilateral); computing a pre-warping transformation based on the previous two steps; pre-warping each application image to correct for keystoning based on the pre-warping transformation; and continuously recalibrating the system if desired (assuming that computational resources are available).

[0014] Further, the present invention includes an apparatus that is capable of performing the above-described methodology. In this application, the more general problem of aligning the corrected image to a physical projector screen is discussed. The simpler problem of aligning the corrected image to the camera image can be solved by equating the camera image to the physical screen.

[0015] FIG. 1 is, a block diagram of one embodiment of the apparatus according to the present invention;

[0016] FIG. 2 is a flow diagram illustrating the general method according to the present invention;

[0017] FIG. 3 is a side-by-side comparative view of results from the present invention with typical distortion;

[0018] FIG. 4 is an illustration of the relationships between the three frames of reference according to the present invention; and

[0019] FIG. 5 is an illustration of an appropriately distorted application image using mapping according to the present invention.

[0020] According to the present invention, there is provided a method and apparatus for automatically correcting distorted projected images. Referring to FIG. 1, the apparatus includes a computer 10 having a source image frame, a projector 12 in communication with the computer 10 resulting in an application image 14, a projection surface 16 having a projected image frame and a camera 18 having a viewer image frame. Further, as seen in FIGS. 4 and 5, the computer 10 provides a means for determining a mapping T between points in the source image frame and the corresponding points in the viewer image frame, means for identifying the boundaries of the projected image frame within the viewer image frame, means for computing a possible mapping C between the projected image frame and the viewer image frame, means for inferring a possible mapping P from the source image frame to the projected image frame, resulting in a corrected application image 20, means for determining an optimal placement mapping S for the corrected application image 20 within the projected image frame, and means for computing a pre-warping transformation W. The computer 10 may also have a local connected components algorithm as well as standard computer vision algorithms.

[0021] As shown in FIG. 2, automatic keystone correction of the present invention is achieved through the steps of: determining the mapping T between points in the source image frame and the corresponding points in a viewer image frame (projector-camera system calibration step 22); identifying the boundaries (typically a quadrilateral) of the projected image frame within the viewer image frame (identifying projector screen boundaries step 24); computing a possible mapping C between the projected image frame and the viewer image frame (derive mapping (C) step 26); inferring a possible mapping P from the results of the source image frame to the projected image frame, based upon steps 24 and 26 (infer mapping (P) step 28), resulting in a corrected application image 20; determining an optimal placement mapping S for the corrected application image 20 within the projected image frame (determine optimal placement step 30); computing a pre-warping transformation W (compute pre-warped transformation (W) step 32), based on P and S, determined in steps 28 and 30; and pre-warping the application image (image warping step 34) based on the pre-warping transformation computed in step 32. In addition, this method may be continuously or periodically repeated (automatic online recalibration step 36).

[0022] The two key concepts of the present invention are: (1) the uncalibrated camera 18 is used to observe the display of the computer 10; and (2) the image to be displayed is then pre-warped so that the distortions induced by the projection system will exactly undo the keystone distortion. The result is that the arbitrarily mounted projector 12 (in an unknown orientation) still displays a perfectly aligned and rectilinear image. The projected image may be aligned either with respect to the camera 18 (optimized for a viewer at the camera's location) or with respect to the projection surface 16 that is visible to the camera 18, as shown in FIG. 1. In either case, the method of the present invention process is fully automatic.

[0023] The human visual system unconsciously accounts for naturally occurring perspective distortions. Therefore, the juxtaposition of a precisely rectangular image (keystone corrected for a particular viewpoint) on the naturally distorted projection surface seems unnatural. Furthermore, it is impossible to perform keystone correction such that audience members seated in different locations of the room all perceive a perfectly rectangular image (since each location induces a different perspective distortion). While the technical challenges of the latter approach are greater (since the boundaries of the projection surface 16 must be detected in a darkened room), a keystone correction process that aligns images with the projection surface 16 is universally preferred. Therefore, the preferred embodiment of the present invention focuses on the second approach.

[0024] The typical hardware requirements for this invention are modest: (1) a standard computer (a prototype was implemented on a Dell Inspiron 7000 laptop); (2) a low-resolution digital camera (e.g., Logitech QuickCam); and (3) a standard LCD projector. The projector 12 can be mounted anywhere as long as the image falls entirely within the projection surface 16 area (e.g., the projector 12 could be placed near the edge of the room, even at an angle). The camera 18 must be mounted such that the projection surface 16 is within its field of view, but the camera 18 can be placed anywhere in a room and need not be level.

[0025] After the apparatus is assembled as described above, the method of the present invention is utilized. The effective results of the present invention are presented in FIG. 3. A rectangular source image (top left) appears distorted when projected from an off-center projector (middle and bottom left). Using the present method, the source image is pre-warped (top right). The resulting projected image is rectilinear and perfectly aligned to the projection screen (middle and bottom right). The middle row of images was captured with a low-quality camera used in the apparatus, and the bottom row of images was captured with a high-quality camera to illustrate how the presentation would appear to an audience member in the room. Each step of the method is described in greater detail below.

[0026] As illustrated in FIG. 4, the goal of the projector-camera system calibration step 22 is to determine a mapping between points in an image frame 38 and the corresponding points in a viewer image frame 40 camera image. Calibration of the projector-camera system may be manual, semi-automatic or fully automatic. For manual calibration, the camera 18 and projector 12 are mounted in a known position and orientation, and the internal optical parameters of the components are specified. For semi-automatic calibration, the computer 10 projects an image depicting several calibration regions, and the user manually identifies the locations of these regions in the camera image. From these correspondences, the system automatically computes the above mapping. For the fully automatic calibration, the calibration can be performed without any user interaction. The mapping computed by the calibration process is termed T in the remainder of this document (see FIG. 4).

[0027] Next, the identify projector screen boundaries step 24 is performed. The general problem of keystone correction requires pre-warping a source image such that, when projected, its edges will be aligned parallel to the boundaries of the projection surface 16. In a typical case, in which the projection surface 16 is rectangular, the corrected image 20 will also be rectangular. More precisely, the edges of the corrected image 20 should converge toward the same vanishing points as the corresponding edges of the physical screen. To do this, the boundaries of the physical projection surface 16, which is a challenging computer-vision task, must be located. The light from the LCD projector 12 is typically the sole source of illumination, and the screen edges are often difficult to extract under such conditions.

[0028] The present invention preferably uses a local connected-components algorithm in which two adjacent pixels are merged if the ratio of their intensities is close to one. Subsequently, all components containing a pixel within a specified distance from the projected source image frame 38 (i.e., the inner quadrilateral 46 in FIG. 4) are merged. The corners of the resulting component (i.e., the outer quadrilateral 48 in FIG. 4) are then extracted with sub-pixel precision using combinations of standard computer vision algorithms. The human user can be offered the opportunity to examine the extracted points and to manually refine the positions if desired. While user feedback is typically unnecessary, the option of user refinement improves reliability in challenging conditions.

[0029] Turning to the derive mapping (C) step 26, from the corners found in step 24, and an assumption that the physical surface 16 is rectangular, a mapping C is derived, using standard computer vision techniques, transforming points from a projected image frame 42 to the viewer image frame 40 (within a scale factor). The present invention heuristically estimates the aspect ratio of the physical surface; alternatively, this information may be supplied to the system.

[0030] Next, the present invention includes the infer mapping (P) step 28. As shown in FIG. 4, the mapping P from the source image frame 38 to the projected image frame 42 may be computed from the two known mappings T and C, derived above, by composing T with the inverse of C:P=C⁻¹T. In this system, P models the configuration of the projector 14 setup that is directly responsible for the keystoning distortion. The task is, therefore, to pre-warp the application image 14 so that it is rectilinear after being mapped through P, creating pre-warped application image 44.

[0031] The next step in the method is the determine optimal placement step 30, where the optimal placement of the corrected image is completed. The computer display (source image frame 38) projects to an arbitrary quadrilateral (projected computer display) in the projected image frame 42, as shown in FIG. 5. Since the pre-warped application image 44 can only be displayed within the bounds of the computer 10 display, the corrected image 20 must lie within the bounds of this quadrilateral and (for best viewing) should be as large as possible. This is equivalent to finding the largest rectangle with appropriate aspect ratio within the projected computer display (since it is assumed that the application image is a rectangle). Again, the present invention employs a heuristic optimization that yields satisfactory results.

[0032] The next step is the compute pre-warped transformation (W) step 32. Given the desired size and location of the corrected image 20, standard computer vision techniques are used to compute a mapping S that scales and shifts the application image 14 to lie within this area. The necessary pre-warping transformation W is computed from the two known transformations S and P:W=P⁻¹S (see FIG. 5).

[0033] Next, the image warping step 34 is performed. The pre-warped image 44 (suitable for projection through an off-center projector 12) is created from the application image 14 using the transformation W calculated above. For each pixel in the pre-warped image 44, the corresponding point in the application image 14 is found by applying the inverse mapping W⁻¹. Since the computed point is real valued, it will not typically correspond to a single (integer) pixel in the application image 14. Therefore, several points or pixels in the application image 14 closest to the identified point are blended. In this example, the four pixels in the application image 14 that are closest to this point are blended using bilinear interpolation (a standard computer graphics technique). The application image 14 is embedded in a virtual region of black pixels to ensure that only pixels within the corrected image 20 are illuminated. The image warping computations are well suited to exploit the accelerated 3-D graphics hardware available in typical computers.

[0034] The present invention is not limited to digital pre-warping of the application image 14. If the position, location or optical characteristics of the projector can be computer controlled, then the mapping W can be translated into commands to adjust these directly. Similarly, the present invention could also provide instructions to a user for manually adjusting such parameters. A combination of manual and automatic hardware and software distortion correction may result in optimal performance. For instance, the present invention could perform automatic focusing through the hardware interface, followed by fully automatic keystone correction in software and interactive placement of the final corrected image 20.

[0035] The final step is the automatic online recalibration step 36. If the application images are suitable for calibration (i.e., either they have several significant point features or have sufficient texture to support an area-based correlation algorithm), and if sufficient computational resources are available on the user's computer during the course of a presentation, then the keystone correction system could perform automatic online recalibration. This would have important benefits. For instance, if the camera 18 or projector 12 were accidentally moved during the course of the presentation, the system would automatically detect the disturbance by observing the discrepancy between expected and observed camera images. The pre-warp transformation W would then be automatically adjusted so that the projected image could remain steady in spite of the motion. In an extreme scenario, one could even envision mounting the camera 18 and/or projector 12 on a moving platform (e.g., such as the user's body) with no adverse effect in the projected image.

[0036] Several minor modifications to the general keystone correction method described above are noteworthy. If the apparatus is built such that the camera 18 and projector 12 optics are shared (i.e., the lens is simultaneously used to project and acquire images), the mapping T is simply a known similarity mapping, regardless of the position and orientation of the apparatus with respect to the projection screen 16. Such an apparatus requires no projector-camera system calibration.

[0037] If the goal is to correct for keystoning in the camera 18 image (i.e., align the application image to the borders of the viewer image frame 40), one can simply consider the camera image frame 40 to be the projected image frame 42. In other words, C can be the identity mapping and the rest of the method is unchanged. The present invention is also applicable to a setup where the camera 18 observes an undistorted computer 10 display, such as a monitor or LCD screen, and the goal is to correct for the distortions caused by the misaligned camera 18. Further, the present invention may also be used to induce desired keystoning (e.g., for special effects). Given a description of the target quadrilateral (in either projected image or camera image coordinates), one can pre-warp the source image to produce the appropriate effect.

[0038] In this manner, the present invention exceeds the prior art limitations of pitch correction. In addition, the above-described apparatus and method of the present invention allow the correction of distortions due to projector placement and allows users to arbitrarily mount projectors anywhere in the room. Further, the present invention is a fully automatic keystone correction system which enables the automatic adjustment of all parameters. Still further, the present invention offers an intuitive interactive interface for manual refinements and adjustments to the process.

[0039] The invention itself, both as to its construction and its method of operation, together with the additional objects and advantages thereof, will best be understood from the previous description of specific embodiments when read in connection with the accompanying drawings. Although the specific description of the herein disclosed invention has been described in detail above, it may be appreciated that those skilled in the art may make other modifications and changes in the invention disclosed above without departing from the spirit and scope thereof.