Methods, systems, and computer-readable storage media for generating three-dimensional (3D) images of a scene

CROSS REFERENCE TO RELATED APPLICATIONS

0001This application is a continuation application of pending U.S. utility patent application Ser. No. 15/193,623, filed Jun. 27, 2016, which is a continuation application of U.S. utility patent application Ser. No. 13/115,459 (now U.S. Pat. No. 9,380,292), filed May 25, 2011, which is a continuation-in-part application of U.S. utility patent application Ser. No. 12/842,084 (now U.S. Pat. No. 8,508,580), filed Jul. 23, 2010, which claims the benefit of U.S. provisional patent application Ser. No. 61/230,131, filed Jul. 31, 2009; the disclosures of which are incorporated herein by reference in their entireties; said U.S. utility patent application Ser. No. 13/115,459 (now U.S. Pat. No. 9,380,292), filed May 25, 2011, is a continuation-in-part application of U.S. utility patent application Ser. No. 12/842,171 (now U.S. Pat. No. 8,436,893), filed Jul. 23, 2010, which claims the benefit of U.S. provisional patent application Ser. No. 61/230,133, filed Jul. 31, 2009; the disclosures of which are incorporated herein by reference in their entireties.

TECHNICAL FIELD

0002The subject matter disclosed herein relates to generating an image of a scene. In particular, the subject matter disclosed herein relates to methods, systems, and computer-readable storage media for generating three-dimensional images of a scene.

BACKGROUND

0003Stereoscopic, or three-dimensional, imagery is based on the principle of human vision. Two separate detectors detect the same object or objects in a scene from slightly different positions and/or angles and project them onto two planes. The resulting images are transferred to a processor which combines them and gives the perception of the third dimension, i.e. depth, to a scene.

0004Many techniques of viewing stereoscopic images have been developed and include the use of colored or polarizing filters to separate the two images, temporal selection by successive transmission of images using a shutter arrangement, or physical separation of the images in the viewer and projecting them separately to each eye. In addition, display devices have been developed recently that are well-suited for displaying stereoscopic images. For example, such display devices include digital still cameras, personal computers, digital picture frames, set-top boxes, high-definition televisions (HDTVs), and the like.

0005The use of digital image capture devices, such as digital still cameras, digital camcorders (or video cameras), and phones with built-in cameras, for use in capturing digital images has become widespread and popular. Because images captured using these devices are in a digital format, the images can be easily distributed and edited. For example, the digital images can be easily distributed over networks, such as the Internet. In addition, the digital images can be edited by use of suitable software on the image capture device or a personal computer.

0006Digital images captured using conventional image capture devices are two-dimensional. It is desirable to provide methods and systems for using conventional devices for generating three-dimensional images. In addition, it is desirable to provide methods and systems for aiding users of image capture devices to select appropriate image capture positions for capturing two-dimensional images for use in generating three-dimensional images. Further, it is desirable to provide methods and systems for altering the depth perceived in three-dimensional images.

SUMMARY

0007This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description of Illustrative Embodiments. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

0008Disclosed herein are methods, systems, and computer-readable storage media for generating three-dimensional (3D) images of a scene. According to an aspect, a method includes using at least one processor and at least one image capture device for capturing a real-time image and a first still image of a scene. Further, the method includes displaying the real-time image of the scene on a display. The method also can include determining one of an image sensor property, optical property, focal property, and viewing property of the captured images. The method also includes calculating one of camera positional offset and pixel offset indicia in a real-time display of the scene to indicate a target camera positional offset with respect to the first still image based on the captured images and potentially one of the image sensor property, optical property, focal property, and viewing property of the captured images. Further, the method includes determining that the at least one capture device is in a position of the target camera positional offset. The method also includes capturing a second still image. Further, the method includes correcting the captured first and second still images to compensate for at least one of camera vertical shift, vertical tilt, horizontal tilt, and rotation. The method also includes generating the three-dimensional image based on the corrected first and second still images.

0009According to another aspect, a method for generating a three-dimensional image includes using at least one processor for receiving, from an image capture device, a plurality of images of a scene from different positions from an image capture device. The method also includes determining attributes of the images. Further, the method includes generating, based on the attributes, a pair of images from the plurality of images for use in generating a three-dimensional image. The method also includes correcting the pair of images to compensate for one of camera vertical shift, vertical tilt, horizontal tilt, and rotation. Further, the method includes generating a three-dimensional image based on the corrected pair of images.

BRIEF DESCRIPTION OF THE DRAWINGS

0010The foregoing summary, as well as the following detailed description of preferred embodiments, is better understood when read in conjunction with the appended drawings. For the purposes of illustration, there is shown in the drawings exemplary embodiments; however, the presently disclosed subject matter is not limited to the specific methods and instrumentalities disclosed. In the drawings:

0011<figref idref="DRAWINGS">FIG. 1</figref> is a block diagram of an exemplary device for generating three-dimensional images of a scene according to embodiments of the presently disclosed subject matter;

0012<figref idref="DRAWINGS">FIG. 2</figref> is a flow chart of an exemplary method for generating a three-dimensional image of a scene using the device shown in <figref idref="DRAWINGS">FIG. 1</figref>, alone or together with any other suitable device, in accordance with embodiments of the present disclosure;

0013<figref idref="DRAWINGS">FIGS. 3A-3D</figref> illustrate a flow chart of an exemplary method for generating a three-dimensional image of a scene in accordance with embodiments of the present subject matter;

0014<figref idref="DRAWINGS">FIG. 4A</figref> is a front view of a user moving between positions for capturing different images using a camera in accordance with embodiments of the present subject matter;

0015<figref idref="DRAWINGS">FIG. 4B</figref> is a front view of a user moving between positions for capturing images using a camera in accordance with embodiments of the present subject matter;

0016<figref idref="DRAWINGS">FIG. 5</figref> is a flow chart of an exemplary method for a preliminary, quick analysis to pre-screen whether an image pair may be a valid stereoscopic pair in accordance with embodiments of the present subject matter;

0017<figref idref="DRAWINGS">FIGS. 6A-6C</figref> are a flow chart of an exemplary method for edge-based analytics and matching for image correspondence, determination of right/left image, and camera toe-in/parallel plane configuration according to embodiments of the present disclosure;

0018<figref idref="DRAWINGS">FIG. 7</figref> is a graphical depiction of an edge detection example in accordance with embodiments of the present subject matter;

0019<figref idref="DRAWINGS">FIGS. 8A and 8B</figref> illustrate a flow chart of an exemplary method for determining whether an image pair is a valid stereoscopic pair and which image is left and right according to embodiments of the present disclosure;

0020<figref idref="DRAWINGS">FIG. 9</figref> is a diagram depicting a technique for identifying corresponding points in left and right view images in accordance with embodiments of the present disclosure;

0021<figref idref="DRAWINGS">FIG. 10</figref> is a flow chart of an exemplary method for determining pixel disparities according to embodiments of the present subject matter;

0022<figref idref="DRAWINGS">FIG. 11</figref> is a flow chart of an exemplary method for adjusting parallax of segmented, moving objects according to embodiments of the present subject matter;

0023<figref idref="DRAWINGS">FIG. 12</figref> is an exemplary diagram of a method for adjusting parallax of moving, segmented objects according to embodiments of the present subject matter;

0024<figref idref="DRAWINGS">FIGS. 13A, 13B, and 13C</figref> illustrate an exemplary process for disparity interpolation according to embodiments of the present subject matter;

0025<figref idref="DRAWINGS">FIG. 14</figref> is a flow chart of an exemplary method for adding/removing objects from a single image according to embodiments of the present subject matter;

0026<figref idref="DRAWINGS">FIG. 15</figref> is an exemplary diagram of a process for adding/removing objects from a single image according to embodiments of the present disclosure;

0027<figref idref="DRAWINGS">FIG. 16</figref> illustrates an exemplary process for creating three-dimensional still images from a standard two-dimensional video sequence by identifying stereoscopic pairs in accordance with embodiments of the present disclosure;

0028<figref idref="DRAWINGS">FIG. 17</figref> illustrates an exemplary process for creating three-dimensional video from a standard two-dimensional video sequence according to embodiments of the present disclosure;

0029<figref idref="DRAWINGS">FIG. 18</figref> illustrates an exemplary process of creating three-dimensional video with changing parallax and no translational motion from a standard two-dimensional video sequence in accordance with an embodiment of the subject matter disclosed herein;

0030<figref idref="DRAWINGS">FIG. 19</figref> is a flow chart of an exemplary method for generating a three-dimensional image of a scene using the device shown in <figref idref="DRAWINGS">FIG. 1</figref>, alone or together with any other suitable device, in accordance with embodiments of the present disclosure;

0031<figref idref="DRAWINGS">FIGS. 20A and 20B</figref> illustrate a flow chart of an exemplary method for generating a three-dimensional image of a scene in accordance with embodiments of the present disclosure;

0032<figref idref="DRAWINGS">FIG. 21</figref> is a diagram of an exemplary image capture technique for facilitating subsequent conversion to three-dimensional images in accordance with embodiments of the present disclosure;

0033<figref idref="DRAWINGS">FIG. 22</figref> is a flow chart of an exemplary method for assisting a user to capture images for use in a process to yield high-quality, three-dimensional images in accordance with embodiments of the present disclosure;

0034<figref idref="DRAWINGS">FIGS. 23A and 23B</figref> depict diagrams of examples of close and medium-distance convergence points, respectively, in accordance with embodiments of the present disclosure;

0035<figref idref="DRAWINGS">FIG. 24</figref> illustrates an exemplary process of horizontal alignment assistance in accordance with embodiments of the present disclosure;

0036<figref idref="DRAWINGS">FIG. 25</figref> illustrates an example of Hough transform lines superimposed for stereo capture according to embodiments of the present disclosure;

0037<figref idref="DRAWINGS">FIG. 26</figref> is a schematic diagram illustrating translational offset determination according to embodiments of the present disclosure;

0038<figref idref="DRAWINGS">FIG. 27</figref> is another exemplary process of “alignment guide” determination according to embodiments of the present disclosure;

0039<figref idref="DRAWINGS">FIG. 28</figref> is a schematic diagram of an exemplary camera-positioning mechanism for automating the camera-assisted image capture procedure according to embodiments of the present disclosure;

0040<figref idref="DRAWINGS">FIG. 29</figref> illustrates an exemplary method of camera-assisted image capture using the automatic camera-positioning mechanism <b>1500</b> shown in <figref idref="DRAWINGS">FIG. 28</figref> according to embodiments of the present disclosure; and

0041<figref idref="DRAWINGS">FIG. 30</figref> illustrates an exemplary environment for implementing various aspects of the subject matter disclosed herein.

DETAILED DESCRIPTION

0042The presently disclosed subject matter is described with specificity to meet statutory requirements. However, the description itself is not intended to limit the scope of this patent. Rather, the inventors have contemplated that the claimed subject matter might also be embodied in other ways, to include different steps or elements similar to the ones described in this document, in conjunction with other present or future technologies. Moreover, although the term “step” may be used herein to connote different aspects of methods employed, the term should not be interpreted as implying any particular order among or between various steps herein disclosed unless and except when the order of individual steps is explicitly described.

0043Embodiments of the presently disclosed subject matter are based on technology that allows a user to capture a plurality of different images of the same object within a scene and to generate one or more stereoscopic images using the different images. Particularly, methods in accordance with the present subject matter provide assistance to camera users in capturing pictures that can be subsequently converted into high-quality three-dimensional images. The functions disclosed herein can be implemented in hardware and/or software that can be executed within, for example, but not limited to, a digital still camera, a video camera (or camcorder), a personal computer, a digital picture frame, a set-top box, an HDTV, a phone, or the like. A mechanism to automate the image capture procedure is also described herein.

0044Methods, systems, and computer program products for selecting an image capture position to generate a three-dimensional image in accordance with embodiments of the present subject matter are disclosed herein. According to one or more embodiments of the present subject matter, a method includes determining a plurality of first guides associated with a first still image of a scene. The method can also include displaying a real-time image of the scene on a display. Further, the method can include determining a plurality of second guides associated with the real-time image. The method can also include displaying the first and second guides on the display for guiding selection of a position of an image capture device to automatically or manually capture a second still image of the scene, as well as any images in between in case the image capture device is set in a continuous image capturing mode, for pairing any of the captured images as a stereoscopic pair of a three-dimensional image. Such three-dimensional images can be viewed or displayed on a suitable stereoscopic display.

0045The functions and methods described herein can be implemented on a device capable of capturing still images, displaying three-dimensional images, and executing computer executable instructions on a processor. The device may be, for example, a digital still camera, a video camera (or camcorder), a personal computer, a digital picture frame, a set-top box, an HDTV, a phone, or the like. The functions of the device may include methods for rectifying and registering at least two images, matching the color and edges of the images, identifying moving objects, removing or adding moving objects from or to the images to equalize them, altering the perceived depth of objects, and any final display-specific transformation to generate a single, high-quality three-dimensional image. The techniques described herein may be applied to still-captured images and video images, which can be thought of as a series of images; hence for the purpose of generalization the majority of the description herein is limited to still-captured image processing.

0046Methods, systems, and computer program products for generating one or more three-dimensional images of a scene are disclosed herein. The three-dimensional images can be viewed or displayed on a stereoscopic display. The three-dimensional images may also be viewed or displayed on any other display capable of presenting three-dimensional images to a person using other suitable equipment, such as, but not limited to, three-dimensional glasses. In addition, the functions and methods described herein may be implemented on a device capable of capturing still images, displaying three-dimensional images, and executing computer executable instructions on a processor. The device may be, for example, a digital still camera, a video camera (or camcorder), a personal computer, a digital picture frame, a set-top box, an HDTV, a phone, or the like. Such devices may be capable of presenting three-dimensional images to a person without additional equipment, or if used in combination with other suitable equipment such as three-dimensional glasses. The functions of the device may include methods for rectifying and registering at least two images, matching the color and edges of the images, identifying moving objects, removing or adding moving objects from or to the images to equalize them, altering a perceived depth of objects, and any final display-specific transformation to generate a single, high-quality three-dimensional image. The techniques described herein may be applied to still-captured images and video images, which can be thought of as a series of images; hence for the purpose of generalization the majority of the description herein is limited to still-captured image processing.

0047In accordance with embodiments, systems and methods disclosed herein can generate and/or alter a depth map for an image using a digital still camera or other suitable device. Using the depth map for the image, a stereoscopic image pair and its associated depth map may be rendered. These processes may be implemented by a device such as a digital camera or any other suitable image processing device.

0048It should be noted that any of the processes and steps described herein may be implemented in an automated fashion. For example, any of the methods and techniques described herein may be automatically implemented without user input after the capture of a plurality of images.

0049<figref idref="DRAWINGS">FIG. 1</figref> illustrates a block diagram of an exemplary image capture device <b>100</b> for generating three-dimensional images of a scene according to embodiments of the presently disclosed subject matter. In this example, device <b>100</b> is a digital camera capable of capturing several consecutive, still digital images of a scene. In another example, the device <b>100</b> may be a video camera capable of capturing a video sequence including multiple still images of a scene. A user of the device <b>100</b> may position the camera in different positions for capturing images of different perspective views of a scene. The captured images may be suitably stored, analyzed and processed for generating three-dimensional images as described herein. For example, subsequent to capturing the images of the different perspective views of the scene, the device <b>100</b>, alone or in combination with a computer, may use the images for generating a three-dimensional image of the scene and for displaying the three-dimensional image to the user.

0050Referring to <figref idref="DRAWINGS">FIG. 1</figref>, the device <b>100</b> may include a sensor array <b>102</b> of charge coupled device (CCD) or CMOS sensors which may be exposed to a scene through a lens and exposure control mechanism as understood by those of skill in the art. The device <b>100</b> may also include analog and digital circuitry such as, but not limited to, a memory <b>104</b> for storing program instruction sequences that control the device <b>100</b>, together with a CPU <b>106</b>, in accordance with embodiments of the presently disclosed subject matter. The CPU <b>106</b> executes the program instruction sequences so as to cause the device <b>100</b> to expose the sensor array <b>102</b> to a scene and derive a digital image corresponding to the scene. The digital image may be captured and stored in the memory <b>104</b>. All or a portion of the memory <b>104</b> may be removable, so as to facilitate transfer of the digital image to other devices such as a computer <b>108</b>. Further, the device <b>100</b> may be provided with an input/output (I/O) interface <b>110</b> so as to facilitate transfer of digital image even if the memory <b>104</b> is not removable. The device <b>100</b> may also include a display <b>112</b> controllable by the CPU <b>106</b> and operable to display the captured images in real-time for real-time viewing by a user.

0051The memory <b>104</b> and the CPU <b>106</b> may be operable together to implement an image generator function <b>114</b> for generating three-dimensional images in accordance with embodiments of the presently disclosed subject matter. The image generator function <b>114</b> may generate a three-dimensional image of a scene using two or more images of the scene captured by the device <b>100</b>. <figref idref="DRAWINGS">FIG. 2</figref> illustrates a flow chart of an exemplary method for generating a three-dimensional image of a scene using the device <b>100</b>, alone or together with any other suitable device, in accordance with embodiments of the present disclosure. Referring to <figref idref="DRAWINGS">FIG. 2</figref>, the method includes receiving <b>200</b> a plurality of images of a scene. For example, the device <b>100</b> may capture one or more real-time images. Further, for example, a user of the device <b>100</b> may use the input features of the device and move the device to different positions for capturing multiple images of a scene to which the sensor array <b>102</b> is exposed. The different images can include images of different perspective views of the scene. The CPU <b>106</b> may then implement instructions stored in the memory <b>104</b> for storing the captured images in the memory <b>104</b>.

0052The method of <figref idref="DRAWINGS">FIG. 2</figref> includes determining <b>202</b> attributes of the plurality of images. For example, attributes of an image captured by an image capture device may include, but are not limited to, analysis of color(s), including mean, standard deviation, histogram correlation, cross correlation, edges, junctions, identified objects, size, orientation, and timestamps of images. For each captured image, the image generator function <b>114</b> can determine one or more attributes. Additional exemplary details of determining attributes of images are provided herein.

0053The method of <figref idref="DRAWINGS">FIG. 2</figref> also includes generating <b>204</b>, based on the attributes, two or more images from among the plurality of images for use in generating a three-dimensional image. For example, the image generator function <b>114</b> may compare the measured value of an attribute of one image to the measured value of an attribute of another image for determining a difference of the measured values. The image generator function <b>114</b> may then determine whether the difference meets a threshold value level. If the threshold criterion is met, the image generator function <b>114</b> determines that the images may be selected for use in generating a three-dimensional image. This process may be used for preliminarily and efficiently determining whether images are candidates for pairing as a three-dimensional image as described in further detail herein.

0054The generated two or more images may also be suitably processed <b>206</b>. For example, the images may be corrected and adjusted for display as described herein.

0055The method of <figref idref="DRAWINGS">FIG. 2</figref> includes displaying <b>206</b> the three-dimensional image. For example, the three-dimensional image may be displayed on the display <b>112</b>. In another example, the three-dimensional image may be communicated to and displayed on another device such as, but not limited to, a computer, video camera, digital picture frame, a set-top box, and a high-definition television.

0056Although the above examples are described for use with a device capable of capturing images, embodiments of the present subject matter described herein are not so limited. Particularly, the methods described herein for generating a three-dimensional image of a scene may for example be implemented in any suitable system including a memory and computer processor. The memory may have stored therein computer-executable instructions. The computer processor may execute the computer-executable instructions. The memory and computer processor may be configured for implementing methods in accordance with embodiments of the subject matter described herein.

0057<figref idref="DRAWINGS">FIGS. 3A-3D</figref> illustrate a flow chart of an exemplary method for generating a three-dimensional image of a scene in accordance with embodiments of the present subject matter. The method can convert a plurality of images to a three-dimensional image that can be viewed on a stereoscopic display. Referring to <figref idref="DRAWINGS">FIGS. 3A-3D</figref>, the method can begin with receiving <b>300</b> a plurality of images of a scene. For example, the images can be captured by a standard digital video or still camera, or a plurality of different cameras of the same type or different type. A camera user may capture an initial image. Next, the camera user may capture subsequent image(s) at positions to the left or right of the position at which the initial image was captured. These images may be captured as still images or as a video sequence of images. The images may be captured using a device such as the device <b>100</b> shown in <figref idref="DRAWINGS">FIG. 1</figref>. The images may be stored in a memory such as the memory <b>104</b> shown in <figref idref="DRAWINGS">FIG. 1</figref>. In another example, the images may be received at a device after they have been captured by a different device.

0058Images suitable for use as a three-dimensional image may be captured by a user using any suitable technique. For example, <figref idref="DRAWINGS">FIG. 4A</figref> illustrates a front view of a user <b>400</b> moving between positions for capturing different images using a camera <b>402</b> in accordance with embodiments of the present subject matter. Referring to <figref idref="DRAWINGS">FIG. 4A</figref>, the user <b>400</b> is shown in solid lines in one position for capturing an image using the camera <b>402</b>. The user <b>400</b> is shown in broken lines in another position for capturing another image using the camera <b>402</b>. The camera <b>402</b> is also at different positions for capturing images offering different perspective views of a scene. In this example, the user <b>400</b> stands with his or her feet separated by a desired binocular distance, then captures the first image while aligning the camera over his or her right foot (the position of the user <b>400</b> shown in solid lines). Then the user captures the second image, and possibly other images in between, while aligning the camera <b>402</b> over his or her left foot (the position of the user <b>400</b> shown in broken lines). The captured images may be used for generating a three-dimensional image in accordance with embodiments of the present subject matter.

0059In another example, <figref idref="DRAWINGS">FIG. 4B</figref> illustrates a front view of a user <b>410</b> moving between positions for capturing different images of a scene using a camera <b>412</b> in accordance with embodiments of the present subject matter. Referring to <figref idref="DRAWINGS">FIG. 4B</figref>, the user <b>410</b> stands with his or her feet together and uses the camera <b>412</b> to capture the first image while maintaining a centered pose (the position of the user <b>410</b> shown in solid lines). Then the user moves one of his or her feet away from the other by twice the desired binocular distance while maintaining a centered pose and uses the camera <b>412</b> to capture the second image, and possibly other images in between (the position of the user <b>410</b> shown in broken lines). The captured images may be used for generating a three-dimensional image in accordance with embodiments of the present subject matter. The previously described two methods are just examples, and a user can capture the images by standing still and just moving the camera left or right to capture multiple images of the scene just looking at the live view images on the display <b>112</b>.

0060The distance between positions at which images are captured (the stereo baseline) for generating a three-dimensional image can affect the quality of the three-dimensional image. The optimal stereo baseline between the camera positions can vary anywhere between 3 centimeters (cm) and several feet, dependent upon a variety of factors, including the distance of the closest objects in frame, the lens focal length or other optics properties of the camera, the camera crop factor (dependent on sensor size), the size and resolution of the display on which the images will be viewed, and the distance from the display at which viewers will view the images. A general recommendation is that the stereo baseline should not exceed the distance defined by the following equation:

0061<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mrow><mrow><mi>B</mi><mo>=</mo><mfrac><mrow><mn>12</mn><mo>⁢</mo><mi>D</mi></mrow><mrow><mn>30</mn><mo>⁢</mo><mrow><mi>FC</mi><mo>/</mo><mn>50</mn></mrow></mrow></mfrac></mrow><mo>,</mo></mrow></math></maths><br /> where B is the stereo baseline separation in inches, D is the distance in feet to the nearest object in frame, F is the focal length of the lens in millimeters (mm), and C is the camera crop factor relative to a full frame (36×24 square mm.) digital sensor (which approximates the capture of a 35 mm analog camera). In the examples provided herein, it is assumed that at least two images have been captured, at least two of which can be interpreted as a stereoscopic pair.

0062The identification of stereo pairs in <b>302</b> is bypassed in the cases where the user has manually selected the image pair for 3D image registration. This bypass can also be triggered if a 3D-enabled capture device is used that identifies the paired images prior to the registration process. Returning to <figref idref="DRAWINGS">FIGS. 3A-3D</figref>, the method includes selecting <b>302</b> two images among the plurality of captured images for use as a stereoscopic pair. For example, the image generator function <b>114</b> shown in <figref idref="DRAWINGS">FIG. 1</figref> may be used for selecting captured images for use as a stereoscopic pair. One or more metrics can be defined for measuring one or more attributes of the plurality of images for selecting a stereoscopic pair. For example, a buffer of M consecutive images may be maintained, or stored in the memory <b>104</b>. The attributes of image with index m are compared with the corresponding attributes of image m+1. If there is no match between those two images, image m+1 is compared with imagem+2. If images are determined to be sufficiently matched so as to be stereoscopic, and after those images have been processed as described below to generate a three-dimensional image, the m and m+2 images are compared to also identify a possible stereoscopic pair. The process may continue for all or a portion of the images in the buffer.

0063A preliminary, quick analysis may be utilized for determining whether images among the plurality of captured images are similar enough to warrant a more detailed analysis. This analysis may be performed by, for example, the image generator function <b>114</b> shown in <figref idref="DRAWINGS">FIG. 1</figref>. <figref idref="DRAWINGS">FIG. 5</figref> illustrates a flow chart of an exemplary method for a preliminary, quick analysis to pre-screen whether an image pair may be a valid stereoscopic pair in accordance with embodiments of the present subject matter. Referring now to <figref idref="DRAWINGS">FIG. 5</figref>, the method includes defining <b>500</b> a candidate stereoscopic pair. For example, the image generator function <b>114</b> may define the image with index m and the image m+1 as a candidate stereoscopic pair.

0064The method of <figref idref="DRAWINGS">FIG. 5</figref> includes performing <b>502</b> a series of measurements of the candidate stereoscopic image pair. The measurements may be of attributes of the image pair. For example, for each color, the image generator function <b>114</b> may measure or calculate the following values: <ul id="ul0001" list-style="none"><li id="ul0001-0001" num="0000"><ul id="ul0002" list-style="none"><li id="ul0002-0001" num="0065">Average image value</li></ul></li></ul>

0066<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mrow><mi>AV</mi><mo>=</mo><mrow><mrow><mo>(</mo><mfrac><mn>1</mn><mi>image_size</mi></mfrac><mo>)</mo></mrow><mo>⁢</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>image_size</mi></munderover><mo>⁢</mo><mi>Ii</mi></mrow></mrow></mrow></math></maths><ul id="ul0003" list-style="none"><li id="ul0003-0001" num="0000"><ul id="ul0004" list-style="none"><li id="ul0004-0001" num="0067">Segmented average image value: Divide image in k segments and take the average of those segments</li><li id="ul0004-0002" num="0068">Minimum pixel value for each color of the image (MIN)</li><li id="ul0004-0003" num="0069">Maximum pixel value for each color of the image (MAX)</li></ul></li></ul>

0070The method of <figref idref="DRAWINGS">FIG. 5</figref> includes applying <b>504</b> criteria to the measurements. For example, the image function generator <b>114</b> shown in <figref idref="DRAWINGS">FIG. 1</figref> may apply several criteria for determining if the images are a possible stereoscopic pair. Exemplary equations defining the application of these criteria to the image m and image m+1 follow: <br />Image pair is not stereoscopic=ABS(AV_m−AV_m+1)>ThresholdAV<br />OR<br />For all k, ABS(SAV_k,m−SAV_k,m+1)>ThresholdSAV<br />OR<br />ABS(MAX_m−MAX_m+1)>ThresholdMAX<br />OR<br />ABS(MIN_m−MIN_m+1)>ThresholdMIN<br /> ThresholdAV, ThresholdSAV, ThresholdMAX, and ThresholdMIN are threshold value levels for the average, segmented average, maximum and minimum, respectively. These equations can be applied to all or at least some of the colors.

0071The method of <figref idref="DRAWINGS">FIG. 5</figref> includes determining <b>506</b> whether any of the criteria are met. The image generator function <b>114</b> may determine whether any of the criteria are met. If the differences between the values for each image are less than a defined threshold, analysis can continue using more complex techniques for determining whether the images are a suitable stereoscopic pair. For example, the method of <figref idref="DRAWINGS">FIGS. 6A-6C</figref>, described below, can be applied for determining whether the images are a suitable stereoscopic pair <b>508</b>. Otherwise, if all the differences are greater than the defined threshold, the images are rejected as a stereoscopic pair <b>510</b>.

0072Referring again to <figref idref="DRAWINGS">FIGS. 3A-3D</figref>, after images are determined to be a potential stereoscopic pair, the method includes applying <b>304</b> rudimentary color adjustment to the images. For example, the image generator function <b>114</b> shown in <figref idref="DRAWINGS">FIG. 1</figref> may apply color adjustment to the images. This optional color adjustment can be a normalized adjustment or DC-correction applied to a single image to allow luminance-based techniques to work better. In addition, several additional criteria may typically be applied to the luminance planes (or optionally to all color planes), including, but not limited to, a Hough transform analysis <b>306</b>, segmentation <b>308</b>, edge detection <b>310</b>, and the like. For example, segmented objects or blocks with high information content can be compared between the two image views using motion estimation techniques, based on differential error measures, such as, but not limited to, sum of absolute difference (SAD) or sum of squared errors (SSE), or correlation based measures, such as phase correlation or cross correlation. Rotational changes between the two images may be considered and identified during this procedure. Segmented objects that are in one view only are indicative of occlusion, and having a significant number of occluded regions is indicative of a poor image pair for stereoscopy. Regions of occlusion identified during this process are recorded for use in later parts of the conversion process. Similarly, motion vector displacement between matching objects may be recorded or stored for further use.

0073Using the results of the motion estimation process used for object similarity evaluation, vertical displacement can be assessed. Vertical motion vector components are indicative of vertical parallax between the images, which when large can indicate a poor image pair. Vertical parallax must be corrected via rectification and registration to allow for comfortable viewing, and this correction will reduce the size of the overlapping region of the image in proportion to the original amount of vertical parallax.

0074Using the motion vectors from the similarity of objects check, color data may be compared to search for large changes between images. Such large changes can represent a color difference between the images regardless of similar luminance.

0075The method of <figref idref="DRAWINGS">FIGS. 3A-3D</figref> includes performing <b>312</b> edge-based analytics and matching for determining whether camera planes are parallel <b>313</b>. For example, <figref idref="DRAWINGS">FIGS. 6A-6C</figref> illustrate a flow chart of an exemplary method for edge-based analytics and matching for image correspondence, determination of right/left image, and camera toe-in/parallel plane configuration according to embodiments of the present subject matter. This method may be implemented by the image generator function <b>114</b> shown in <figref idref="DRAWINGS">FIG. 1</figref>. Referring to <figref idref="DRAWINGS">FIGS. 6A-6C</figref>, two images are provided <b>600</b>. Edge detection, when applied to both images, can be the foundation for image analysis and correspondence. In an example, the image generator function <b>114</b> shown in <figref idref="DRAWINGS">FIG. 1</figref> may apply <b>602</b> numerous edge operators for this analysis. The edge operators may include, but are not limited to, zero-cross or gradient-based operations. Following the application of edge operators, the image generator function <b>114</b> may apply <b>604</b> a slice-based horizontal and vertical edge locator function for extracting edges from the binary images.

0076Referring to <figref idref="DRAWINGS">FIGS. 6A-6C</figref>, the image generator function <b>114</b> may also determine whether enough edges have been found <b>606</b>. This stage (<b>606</b>) involves a comparison of the edges found from the two pictures to make sure that they meet a predefined minimum edge count. This stage also confirms the similarity of the two pictures by comparing the edge count of the two images to assure they are within a predefined percentage of each other. If enough edges have not been found, techniques alternative to edge-based processing techniques may be used <b>608</b>. These techniques include motion-estimation-based image matching and quadrant-based or full-image based cross correlation of the input images. Edge extensions from slice boundaries can be generated <b>610</b> if enough edges have been found. This scheme simplifies the overall amount of calculation to determine the edges within the images by first considering edge segments that span a slice and then growing these edge segments to determine the exact edge size and endpoints. Next, the method of <figref idref="DRAWINGS">FIGS. 6A-6C</figref> includes comparing and correlating <b>612</b> the lengths, slope, curvature, midpoints/offset position, boundaries, and primary points of the resulting edges within the two images as an additional check of potential correspondence. Block <b>614</b> tests each edge to see if it intersects with a single image boundary (i.e., top, bottom, left or right boundary of image). In the event of an edge intersecting a single image boundary, block <b>616</b> classifies its primary point as the endpoint which is not on the boundary. Otherwise, block <b>618</b> classifies its primary point as the midpoint of the edge. Block <b>620</b> involves solving a minimization problem via vertical edge matching in order to determine the optimal selection for the vertical shift between the two images. In an example for block <b>620</b>, the following equation may be used:

0077<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mrow><msubsup><mi>min</mi><mrow><msub><mi>δ</mi><mi>γ</mi></msub><mo>=</mo><mrow><mo>-</mo><msub><mi>ɛ</mi><mi>γ</mi></msub></mrow></mrow><msub><mi>ɛ</mi><mi>γ</mi></msub></msubsup><mo>⁢</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>M</mi></munderover><mo>⁢</mo><mrow><msubsup><mi>min</mi><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></msubsup><mo>⁢</mo><mrow><mo>(</mo><mrow><mi>min</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mo></mo><mrow><mrow><msub><mi>P</mi><mi>i</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>x</mi><mo>,</mo><mrow><mi>y</mi><mo>+</mo><msub><mi>δ</mi><mi>γ</mi></msub></mrow></mrow><mo>)</mo></mrow></mrow><mo>-</mo><mrow><msub><mi>Q</mi><mi>j</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>x</mi><mo>,</mo><mi>y</mi></mrow><mo>)</mo></mrow></mrow></mrow><mo></mo></mrow><mo>,</mo><mrow><msub><mi>ɛ</mi><mi>x</mi></msub><mo>+</mo><msub><mi>ɛ</mi><mi>y</mi></msub></mrow></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></mrow></math></maths><br /> For each vertical edge in one image, determine the closest edge in the other image, subject to meeting criteria for length, slope and curvature. For distance, use the distance between the primary points. If this distance is larger than ε, it is deemed that no edge matches, and this edge contributes ε to the cost function. The end result of the optimization is the determination of <b>6</b>, the optimal shift between the two images based on this vertical edge matching. In box <b>622</b>, the same optimization process from box <b>620</b> is repeated; this time, however, is for horizontal edge matching, and utilizes the vertical δ already determined from box <b>620</b>.

0078In an example for block <b>622</b>, the following equation may be used:

0079<maths id="MATH-US-00004" num="00004"><math overflow="scroll"><mrow><msubsup><mi>min</mi><mrow><msub><mi>δ</mi><mi>x</mi></msub><mo>=</mo><mrow><mo>-</mo><msub><mi>ɛ</mi><mi>x</mi></msub></mrow></mrow><msub><mi>ɛ</mi><mi>x</mi></msub></msubsup><mo>⁢</mo><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>M</mi></munderover><mo>⁢</mo><mrow><msubsup><mi>min</mi><mrow><mi>j</mi><mo>=</mo><mn>1</mn></mrow><mi>N</mi></msubsup><mo>⁢</mo><mrow><mi>min</mi><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mo></mo><mrow><mrow><msub><mi>P</mi><mi>i</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mrow><mi>x</mi><mo>+</mo><msub><mi>δ</mi><mi>y</mi></msub></mrow><mo>,</mo><mrow><mi>y</mi><mo>+</mo><msub><mi>δ</mi><mi>y</mi></msub></mrow></mrow><mo>)</mo></mrow></mrow><mo>-</mo><mrow><msub><mi>Q</mi><mi>j</mi></msub><mo>⁡</mo><mrow><mo>(</mo><mrow><mi>x</mi><mo>,</mo><mi>y</mi></mrow><mo>)</mo></mrow></mrow></mrow><mo></mo></mrow><mo>,</mo><mrow><msub><mi>ɛ</mi><mi>x</mi></msub><mo>+</mo><msub><mi>ɛ</mi><mi>y</mi></msub></mrow></mrow><mo>)</mo></mrow></mrow></mrow></mrow></mrow></math></maths><br /> Block <b>624</b> then uses the calculated horizontal and vertical δ's to match each edge with its closest edge that meets the length, slope and curvature criteria. In an example for block <b>624</b>, the following equation may be used:

0080<maths id="MATH-US-00005" num="00005"><math overflow="scroll"><mrow><msub><mi>C</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>=</mo><mrow><mo>{</mo><mtable><mtr><mtd><mn>1</mn></mtd><mtd><mrow><mi>if</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><msub><mi>P</mi><mi>i</mi></msub><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>matches</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><msub><mi>Q</mi><mi>j</mi></msub></mrow></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mi>otherwise</mi></mtd></mtr></mtable></mrow></mrow></math></maths><br /> The output of this stage is the matrix C, which has 1 in location i,j if edge i and j are matching edges and otherwise 0. This matrix is then pruned in Box <b>626</b> so that no edge is matched with multiple other edges. In the event of multiple matches, the edge match with minimal distance is used. Finally, in Box <b>628</b>, the edge matches are broken down into regions of the image. The set of matching edges within each region are then characterized by the mean shift, and this mean shift is then the characteristic shift of the region. By examining the direction of the shifts of each subregion, it is thus possible to determine which picture is left and which is right. It is also possible to determine whether the second captured picture was captured with a focal axis parallel to the first picture. If not, there is some amount of toe-in or toe-out which can be characterized by the directional shifts of the subregions.

0081Referring to <figref idref="DRAWINGS">FIGS. 6A-6C</figref>, the extracted edge sets from the two input images can be compared as part of a minimal optimization, in order to solve for the optimal delta translation between images. This 6 value allows for determination of which image is left and right, as well as whether the cameras were in parallel configuration. When the cameras focal axes are parallel (or near parallel), the algorithm (from <figref idref="DRAWINGS">FIGS. 3A-3D</figref>) can proceed to the image registration without performing image rectification.

0082<figref idref="DRAWINGS">FIG. 7</figref> is a graphical depiction of an edge detection example in accordance with embodiments of the present subject matter. The example of <figref idref="DRAWINGS">FIG. 7</figref> shows the edge detection map when edge detection is applied to a captured image, and demonstrates that the extracted images can be a representation of image composition.

0083A Hough transform can be applied <b>306</b> to identify lines in the two images of the potential stereoscopic pair. Lines that are non-horizontal, non-vertical, and hence indicate some perspective in the image can be compared between the two images to search for perspective changes between the two views that may indicate a perspective change or excessive toe-in during capture of the pair.

0084The aforementioned criteria may be applied to scaled versions of the original images for reducing computational requirements. The results of each measurement may be gathered, weighted, and combined to make a final decision regarding the probable quality of a given image pair as a stereoscopic image pair.

0085The method of <figref idref="DRAWINGS">FIGS. 3A-3D</figref> includes identifying <b>314</b> a valid stereoscopic pair. For example, <figref idref="DRAWINGS">FIGS. 8A and 8B</figref> illustrate a flow chart of an exemplary method for determining whether an image pair is a valid stereoscopic pair and which image is left and right according to embodiments of the present disclosure. This method may be implemented, for example, by the image generator function <b>114</b> shown in <figref idref="DRAWINGS">FIG. 1</figref>. Referring to <figref idref="DRAWINGS">FIGS. 8A and 8B</figref>, the method includes defining <b>800</b> a candidate stereoscopic image pair. In this example, two images with indices m and m+1 are examined. The method includes performing <b>802</b> a quick analysis to identify stereoscopic pairs.

0086At step <b>804</b>, color segmentation is performed on the objects. At step <b>806</b>, the bounding box of 8×8 blocks for each object in each image may be identified. At step <b>810</b>, images may be partitioned into N×N blocks. At step <b>812</b>, blocks with high information content may be selected. At step <b>813</b>, the method includes performing motion estimation on blocks in L relative to R image (accumulate motion vectors for L/R determination. These steps may be considered Techniques <b>1</b>, <b>2</b>, and <b>3</b>.

0087At step <b>814</b>, edge detection may be performed on left/right images. Next, at step <b>816</b>, vertical and horizontal lines in left/right images may be identified and may be classified by length, location, and slope. At step <b>818</b>, a Hough transform may be performed on the left/right images. Next, at step <b>820</b>, the method includes analyzing Hough line slope for left/right images and identifying non-vertical and non-horizontal lines.

0088Referring to <figref idref="DRAWINGS">FIGS. 8A and 8B</figref>, LDIAG represents the set of lines that have been identified as non-vertical or non-horizontal using the Hough transform. LHV represents lines that have been classified as either vertical or horizontal. MVY are the luminance motion vectors, and MVCRB the chrominance motion vectors, for each segmented object or N×N block. Similarly, MVYM is the mean luminance motion vector measurement, and MYCRBM the mean chrominance motion vectors. BMAD is the mean accumulated best match difference. ORG is the measurement of how well origins of horizontal/vertical lines match. LEN is the measurement of how well lengths of horizontal/vertical lines match. SLP is the measurement of how well slopes of horizontal/vertical lines match. TIN is the measurement of how well slopes of diagonal lines match.

0089At step <b>822</b>, the following calculations may be performed for all objects or blocks of interest and lines:

0090<maths id="MATH-US-00006" num="00006"><math overflow="scroll"><mrow><mrow><mi>MVYM</mi><mo>=</mo><mrow><munder><mo>∑</mo><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></munder><mo>⁢</mo><msub><mi>MVY</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi><mo>,</mo><mi>m</mi></mrow></msub></mrow></mrow><mo>,</mo><mstyle><mtext></mtext></mstyle><mo>⁢</mo><mrow><mi>where</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>i</mi><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>object</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>ID</mi></mrow><mo>,</mo><mrow><mi>j</mi><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>motion</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>vector</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>ID</mi></mrow><mo>,</mo><mrow><mi>m</mi><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>image</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>ID</mi></mrow></mrow></math></maths><maths id="MATH-US-00006-2" num="00006.2"><math overflow="scroll"><mrow><mrow><mi>BMAD</mi><mo>=</mo><mrow><munder><mo>∑</mo><mi>i</mi></munder><mo>⁢</mo><mrow><mi>abs</mi><mo>⁡</mo><mrow><mo>[</mo><mrow><msub><mi>block</mi><mrow><mn>0</mn><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi><mo>,</mo><mi>m</mi></mrow></msub><mo>-</mo><msub><mi>block</mi><mrow><mi>mv</mi><mo>,</mo><mi>i</mi><mo>,</mo><mi>j</mi><mo>,</mo><mrow><mi>m</mi><mo>+</mo><mn>1</mn></mrow></mrow></msub></mrow><mo>]</mo></mrow></mrow></mrow></mrow><mo>,</mo><mstyle><mtext></mtext></mstyle><mo>⁢</mo><mrow><mi>where</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>i</mi><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>object</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>ID</mi></mrow><mo>,</mo><mrow><mi>j</mi><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>motion</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>vector</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>ID</mi></mrow><mo>,</mo><mrow><mi>m</mi><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>image</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>ID</mi></mrow><mo>,</mo><mstyle><mtext></mtext></mstyle><mo>⁢</mo><mrow><mi>mv</mi><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>best</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>match</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>vector</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>for</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>block</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>j</mi></mrow></mrow></math></maths><maths id="MATH-US-00006-3" num="00006.3"><math overflow="scroll"><mrow><msub><mi>MVCRBM</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>=</mo><mrow><mo>∑</mo><msub><mi>MVCRB</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi><mo>,</mo><mi>m</mi></mrow></msub></mrow></mrow></math></maths><maths id="MATH-US-00006-4" num="00006.4"><math overflow="scroll"><mrow><mi>ORG</mi><mo>=</mo><mrow><munder><mo>∑</mo><mi>i</mi></munder><mo>⁢</mo><mrow><mi>abs</mi><mo>⁡</mo><mrow><mo>[</mo><mrow><mrow><mi>origin</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>LHV</mi><mrow><mi>i</mi><mo>,</mo><mi>m</mi></mrow></msub><mo>)</mo></mrow></mrow><mo>-</mo><mrow><mi>origin</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>LHV</mi><mrow><mi>i</mi><mo>,</mo><mrow><mi>m</mi><mo>+</mo><mn>1</mn></mrow></mrow></msub><mo>)</mo></mrow></mrow></mrow><mo>]</mo></mrow></mrow></mrow></mrow></math></maths><maths id="MATH-US-00006-5" num="00006.5"><math overflow="scroll"><mrow><mi>LEN</mi><mo>=</mo><mrow><munder><mo>∑</mo><mi>i</mi></munder><mo>⁢</mo><mrow><mi>abs</mi><mo>⁡</mo><mrow><mo>[</mo><mrow><mrow><mi>length</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>LHV</mi><mrow><mi>i</mi><mo>,</mo><mi>m</mi></mrow></msub><mo>)</mo></mrow></mrow><mo>-</mo><mrow><mi>length</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>LHV</mi><mrow><mi>i</mi><mo>,</mo><mrow><mi>m</mi><mo>+</mo><mn>1</mn></mrow></mrow></msub><mo>)</mo></mrow></mrow></mrow><mo>]</mo></mrow></mrow></mrow></mrow></math></maths><maths id="MATH-US-00006-6" num="00006.6"><math overflow="scroll"><mrow><mi>SLP</mi><mo>=</mo><mrow><munder><mo>∑</mo><mi>i</mi></munder><mo>⁢</mo><mrow><mi>abs</mi><mo>⁡</mo><mrow><mo>[</mo><mrow><mrow><mi>slope</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>LHV</mi><mrow><mi>i</mi><mo>,</mo><mi>m</mi></mrow></msub><mo>)</mo></mrow></mrow><mo>-</mo><mrow><mi>slope</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>LHV</mi><mrow><mi>i</mi><mo>,</mo><mrow><mi>m</mi><mo>+</mo><mn>1</mn></mrow></mrow></msub><mo>)</mo></mrow></mrow></mrow><mo>]</mo></mrow></mrow></mrow></mrow></math></maths><maths id="MATH-US-00006-7" num="00006.7"><math overflow="scroll"><mrow><mi>TIN</mi><mo>=</mo><mrow><munder><mo>∑</mo><mi>i</mi></munder><mo>⁢</mo><mrow><mi>abs</mi><mo>⁡</mo><mrow><mo>[</mo><mrow><mrow><mi>slope</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>LDIAG</mi><mrow><mi>i</mi><mo>,</mo><mi>m</mi></mrow></msub><mo>)</mo></mrow></mrow><mo>-</mo><mrow><mi>slope</mi><mo>⁡</mo><mrow><mo>(</mo><msub><mi>LDIAG</mi><mrow><mi>i</mi><mo>,</mo><mrow><mi>m</mi><mo>+</mo><mn>1</mn></mrow></mrow></msub><mo>)</mo></mrow></mrow></mrow><mo>]</mo></mrow></mrow></mrow></mrow></math></maths>

0091At step <b>824</b>, a weighted average of the above measures may be performed to determine whether images are a pair or not. Next, at step <b>826</b>, average motion vector direction may be used to determine left/right images.

0092Referring again to <figref idref="DRAWINGS">FIGS. 3A-3D</figref>, the method can next include determining which image of the stereoscopic pair represents the left view image and which image represents the right view image. This aspect can be important in many applications since, for example, a user can capture a plurality of images moving to the left or right. First, image segmentation <b>308</b> can be performed to identify objects within the two captured views. The motion estimation step that has been defined before saves the motion vectors of each object or block with high information content. If the general motion of segmented objects is to the right for one view relative to the other, it is indicative of a left view image, and vice versa. Since the process of motion estimation of segmented objects is also used in stereoscopic pair evaluation, left/right image determination can be performed in parallel.

0093For a stereo pair of left and right view images, the method of <figref idref="DRAWINGS">FIGS. 3A-3D</figref> includes rectification point selection <b>316</b>, rectification <b>318</b>, and region of interest identification <b>320</b>. For example, interest points for stereo correspondence, rectification and registration can be identified. According to embodiments of the present subject matter, the left view image, sized N×M, is broken into a number, N, of smaller n×m sub-images. Each sub-image can be filtered to find junction points, or interest points, within and between objects in view. Interest points can be identified, for example, by performing horizontal and vertical edge detection, filtering for strong edges of a minimum length, and identifying crossing points of these edges. Interest point determination can be assisted by Hough transform line analysis when determining the dominant edges in a scene. Interest points may not be selected from areas identified as occluded in the initial analysis of a stereo pair. Interest points can span the full image.

0094For a stereo pair of left and right view images with a set of identified interest points, rectification <b>318</b> may be performed on the stereo pair of images. Using the interest point set for the left view image, motion estimation techniques (as described in stereo pair identification above) and edge matching techniques are applied to find the corresponding points in the right view image. <figref idref="DRAWINGS">FIG. 9</figref> depicts an example of applying this technique. Referring to <figref idref="DRAWINGS">FIG. 9</figref>, the N corresponding points in the left and right view images are made into a 3×N set of point values, for example:

0095<maths id="MATH-US-00007" num="00007"><math overflow="scroll"><mrow><msub><mi>right</mi><mi>pts</mi></msub><mo>=</mo><mrow><mrow><mo>{</mo><mtable><mtr><mtd><mrow><mi>x</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mn>1</mn><mi>r</mi></msub></mrow></mtd><mtd><mrow><mi>x</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mn>2</mn><mi>r</mi></msub></mrow></mtd><mtd><mrow><mi>x</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mn>3</mn><mi>r</mi></msub></mrow></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd></mtr><mtr><mtd><mrow><mi>y</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mn>1</mn><mi>r</mi></msub></mrow></mtd><mtd><mrow><mi>y</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mn>2</mn><mi>r</mi></msub></mrow></mtd><mtd><mrow><mi>y</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mn>3</mn><mi>r</mi></msub></mrow></mtd><mtd><mi>…</mi></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd></mtr></mtable><mo>}</mo></mrow><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>and</mi></mrow></mrow></math></maths><maths id="MATH-US-00007-2" num="00007.2"><math overflow="scroll"><mrow><mrow><msub><mi>left</mi><mi>pts</mi></msub><mo>=</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><mi>x</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mn>1</mn><mi>l</mi></msub></mrow></mtd><mtd><mrow><mi>x</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mn>2</mn><mi>l</mi></msub></mrow></mtd><mtd><mrow><mi>x</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mn>3</mn><mi>l</mi></msub></mrow></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd></mtr><mtr><mtd><mrow><mi>y</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mn>1</mn><mi>l</mi></msub></mrow></mtd><mtd><mrow><mi>y</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mn>2</mn><mi>l</mi></msub></mrow></mtd><mtd><mrow><mi>y</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mn>3</mn><mi>l</mi></msub></mrow></mtd><mtd><mi>…</mi></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd></mtr></mtable><mo>}</mo></mrow></mrow><mo>,</mo></mrow></math></maths><br /> and the fundamental matrix equation <br />right_pts^T<i>*F</i>*left_pts=0<br /> is solved or approximated to determine the 3×3 fundamental matrix, F, and epipoles, e1 and e2. The camera epipoles are used with the interest point set to generate a pair of rectifying homographies. It can be assumed that the camera properties are consistent between the two captured images. The respective homographies are then applied to the right and left images, generating the rectified images. The overlapping rectangular region of the two rectified images is then identified, the images are cropped to this rectangle, and the images are resized to their original dimensions, generating the rectified image pair, right_r and left_r. The rectified image pair can be defined by the following equations: <br />right_<i>r</i>=cropped(<i>F</i>*right)<br />left_<i>r</i>=cropped(<i>F</i>*left)<br /> For the stereo pair of “left_r” and “right_r” images, registration is next performed on the stereo pair. A set of interest points is required, and the interest point set selected for rectification (or a subset thereof) may be translated to positions relative to the output of the rectification process by applying the homography of the rectification step to the points. Optionally, a second set of interest points may be identified for the left_r image, and motion estimation and edge matching techniques may be applied to find the corresponding points in the right_r image. The interest point selection process for the registration operation is the same as that for rectification. Again, the N corresponding interest points are made into a 3×N set of point values as set forth in the following equations:

0096<maths id="MATH-US-00008" num="00008"><math overflow="scroll"><mrow><msub><mi>right_r</mi><mi>pts</mi></msub><mo>=</mo><mrow><mrow><mo>{</mo><mtable><mtr><mtd><mrow><msup><mi>x</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>1</mn><mi>r</mi></msub></mrow></mtd><mtd><mrow><msup><mi>x</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>2</mn><mi>r</mi></msub></mrow></mtd><mtd><mrow><msup><mi>x</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>3</mn><mi>r</mi></msub></mrow></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd></mtr><mtr><mtd><mrow><msup><mi>y</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>1</mn><mi>r</mi></msub></mrow></mtd><mtd><mrow><msup><mi>y</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>2</mn><mi>r</mi></msub></mrow></mtd><mtd><mrow><msup><mi>y</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>3</mn><mi>r</mi></msub></mrow></mtd><mtd><mi>…</mi></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd></mtr></mtable><mo>}</mo></mrow><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>and</mi></mrow></mrow></math></maths><maths id="MATH-US-00008-2" num="00008.2"><math overflow="scroll"><mrow><mrow><msub><mi>left_r</mi><mi>pts</mi></msub><mo>=</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><msup><mi>x</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>1</mn><mi>l</mi></msub></mrow></mtd><mtd><mrow><msup><mi>x</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>2</mn><mi>l</mi></msub></mrow></mtd><mtd><mrow><msup><mi>x</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>3</mn><mi>l</mi></msub></mrow></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd></mtr><mtr><mtd><mrow><msup><mi>y</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>1</mn><mi>l</mi></msub></mrow></mtd><mtd><mrow><msup><mi>y</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>2</mn><mi>l</mi></msub></mrow></mtd><mtd><mrow><msup><mi>y</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>3</mn><mi>l</mi></msub></mrow></mtd><mtd><mi>…</mi></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd></mtr></mtable><mo>}</mo></mrow></mrow><mo>,</mo></mrow></math></maths><br /> and the following matrix equation <br />left_<i>r</i>_pts<i>=Tr</i>*right_<i>r</i>_pts<br /> is approximated for a 3×3 linear conformal transformation, Tr, which may incorporate both translation on the X and Y axes and rotation in the X/Y plane. The transform Tr is applied to the right_r image to generate the image “Right′” as defined by the following equation: <br />Right′=<i>Tr</i>*right_<i>r, </i><br /> where right_r is organized as a 3×N set of points (xi_r, yi_r, 1) for i=1 to image_rows*image cols.

0097Finally, the second set of interest points for the left_r image may be used to find correspondence in the Right′ image, the set of points as set forth in the following equations:

0098<maths id="MATH-US-00009" num="00009"><math overflow="scroll"><mrow><msubsup><mi>Right</mi><mi>pts</mi><mi>′</mi></msubsup><mo>=</mo><mrow><mrow><mo>{</mo><mtable><mtr><mtd><mrow><msup><mi>x</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>1</mn><mi>r</mi></msub></mrow></mtd><mtd><mrow><msup><mi>x</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>2</mn><mi>r</mi></msub></mrow></mtd><mtd><mrow><msup><mi>x</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>3</mn><mi>r</mi></msub></mrow></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd></mtr><mtr><mtd><mrow><msup><mi>y</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>1</mn><mi>r</mi></msub></mrow></mtd><mtd><mrow><msup><mi>y</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>2</mn><mi>r</mi></msub></mrow></mtd><mtd><mrow><msup><mi>y</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>3</mn><mi>r</mi></msub></mrow></mtd><mtd><mi>…</mi></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd></mtr></mtable><mo>}</mo></mrow><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>and</mi></mrow></mrow></math></maths><maths id="MATH-US-00009-2" num="00009.2"><math overflow="scroll"><mrow><mrow><msub><mi>left_r</mi><mi>pts</mi></msub><mo>=</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><msup><mi>x</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>1</mn><mi>l</mi></msub></mrow></mtd><mtd><mrow><msup><mi>x</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>2</mn><mi>l</mi></msub></mrow></mtd><mtd><mrow><msup><mi>x</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>3</mn><mi>l</mi></msub></mrow></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd></mtr><mtr><mtd><mrow><msup><mi>y</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>1</mn><mi>l</mi></msub></mrow></mtd><mtd><mrow><msup><mi>y</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>2</mn><mi>l</mi></msub></mrow></mtd><mtd><mrow><msup><mi>y</mi><mi>′</mi></msup><mo>⁢</mo><msub><mn>3</mn><mi>l</mi></msub></mrow></mtd><mtd><mi>…</mi></mtd></mtr><mtr><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mn>1</mn></mtd><mtd><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle></mtd></mtr></mtable><mo>}</mo></mrow></mrow><mo>,</mo></mrow></math></maths><br /> is identified and composed, and the equation <br />Right′_pts<i>=Tl</i>*left_<i>r</i>_pts<br /> is approximated for a second linear conformal transformation, Tl. The transform Tl is applied to the left_r image to generate the image “Left′”, as defined by the following equation: <br />Left′=<i>Tl</i>*left_<i>r </i><br /> “Right′” and “Left′” images represent a rectified, registered stereoscopic pair.

0099The method of <figref idref="DRAWINGS">FIGS. 3A-3D</figref> includes an overall parallax, or disparity, calculation <b>332</b>. According to embodiments of the present subject matter, for a stereoscopic pair of registered “Left′” and “Right′” images, a pixel-by-pixel parallax, or disparity, map is created. This can be performed, for example, by using a hierarchical motion estimation operation between the Left′ and Right′ images, starting with blocks sized N×N and refining as necessary to smaller block sizes. During the estimation process, only horizontal displacement may be considered, limiting the search range. After each iteration of the process, the best match position is considered for pixel-by-pixel differences, and the next refinement step, if needed, is assigned by noting the size of the individual pixel differences that are greater than a threshold, Tp. Regions of the image previously identified as occluded in one image are assigned the average parallax value of the pixels in the surrounding neighborhood. Regions of an image that are not known to be occluded from previous steps in the process, and for which an appropriate motion match cannot be found (pixel differences are never &lt;Tp) are assigned to the maximum possible parallax value to allow for simple identification in later steps of the stereo composition process. In the example of <figref idref="DRAWINGS">FIGS. 3A-3D</figref>, the method includes correspondence point selection <b>322</b>, correspondence <b>324</b> and registration transform to generate the Right′ image <b>326</b>. In addition, the method includes correspondence <b>328</b> and registration transform to generate the Left′ image <b>330</b>.

0100<figref idref="DRAWINGS">FIG. 10</figref> illustrates a flow chart of an exemplary method for determining pixel disparities according to embodiments of the present subject matter. The method may be implemented, for example, by the image generator function <b>114</b> shown in <figref idref="DRAWINGS">FIG. 1</figref>. Referring to <figref idref="DRAWINGS">FIG. 10</figref>, the method includes receiving <b>1000</b> a transformed stereoscopic image pair, including a left and right image. The method includes dividing <b>1002</b> the images into blocks of N×N pixels. For every block, the method includes performing <b>1004</b> motion estimation between left and right to determine a best match vector. Next, for every pixel in each block, the method includes calculating <b>1006</b> the differences between left and right for the best match vector.

0101The method of <figref idref="DRAWINGS">FIG. 10</figref> includes determining <b>1008</b> whether the best match difference is less than the threshold Tp. If the best match difference is less than the threshold Tp, the disparity of the pixel is set equal to the best match vector <b>1010</b>. Otherwise, if the best match difference is not less than the threshold Tp, the method includes determining <b>1012</b> whether the pixel is occluded. If the pixel is determined to be occluded, the disparity of the pixel is set equal to the best match vector <b>1010</b>. If the pixel is determined not to be occluded, the method includes grouping pixels in an M×M block and performing a new analysis with M×M refinement <b>1014</b>.

0102After steps <b>1010</b> and <b>1014</b> of <figref idref="DRAWINGS">FIG. 10</figref>, the method includes determining <b>1016</b> whether there are more pixels in the current block being processed. If there are more pixels, the method returns to step <b>1006</b>. Otherwise, the method determines <b>1018</b> whether there are more blocks to be processed. If not, the method exits <b>1020</b>. If there are more blocks, the method returns to step <b>1004</b>.

0103Returning now to <figref idref="DRAWINGS">FIGS. 3A-3D</figref>, the method includes applying <b>334</b> a parallax analysis. For example, for a stereoscopic pair of registered “Left′” and “Right′” images, the maximum and minimum pixel parallax values can be analyzed to decide whether the maximum or minimum parallax is within the ability of a viewer to resolve a three-dimensional image. If it is determined that the parallax is within the ability of a viewer to resolve the three-dimensional image, the method proceeds to step <b>342</b>. If not, the method proceeds to step <b>336</b>. Occluded regions and pixels with “infinite” parallax are not considered in this exemplary method.

0104For a stereoscopic pair of registered “Left′” and “Right′” images, the screen plane of the stereoscopic image can be altered <b>336</b>, or relocated, to account for disparities measured as greater than a viewer can resolve. This is performed by scaling the translational portion of transforms that created the registered image views by a percent offset and re-applying the transforms to the original images. For example, if the initial left image transform is as follows:

0105<maths id="MATH-US-00010" num="00010"><math overflow="scroll"><mrow><mi>Tl</mi><mo>=</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><mi>S</mi><mo>*</mo><mi>cos</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>θ</mi></mrow></mtd><mtd><mrow><mi>S</mi><mo>*</mo><mi>sin</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>θ</mi></mrow></mtd><mtd><mi>Tx</mi></mtd></mtr><mtr><mtd><mrow><mrow><mo>-</mo><mi>S</mi></mrow><mo>*</mo><mi>sin</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>θ</mi></mrow></mtd><mtd><mrow><mi>S</mi><mo>*</mo><mi>cos</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>θ</mi></mrow></mtd><mtd><mi>Ty</mi></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable><mo>}</mo></mrow></mrow></math></maths><br /> for scaling factor S, X/Y rotation angle θ, and translational offsets Tx and Ty, the adjustment transform becomes

0106<maths id="MATH-US-00011" num="00011"><math overflow="scroll"><mrow><msub><mi>Tl</mi><mi>alt</mi></msub><mo>=</mo><mrow><mo>{</mo><mtable><mtr><mtd><mrow><mi>S</mi><mo>*</mo><mi>cos</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>θ</mi></mrow></mtd><mtd><mrow><mi>S</mi><mo>*</mo><mi>sin</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>θ</mi></mrow></mtd><mtd><mrow><mi>Tx</mi><mo>*</mo><mi>Xscale</mi></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mo>-</mo><mi>S</mi></mrow><mo>*</mo><mi>sin</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>θ</mi></mrow></mtd><mtd><mrow><mi>S</mi><mo>*</mo><mi>cos</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>θ</mi></mrow></mtd><mtd><mrow><mi>Ty</mi><mo>*</mo><mi>Yscale</mi></mrow></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>1</mn></mtd></mtr></mtable><mo>}</mo></mrow></mrow></math></maths><br /> where Xscale and Yscale are determined by the desired pixel adjustment relative to the initial transform adjustment, i.e.,

0107<maths id="MATH-US-00012" num="00012"><math overflow="scroll"><mrow><mi>Xscale</mi><mo>=</mo><mrow><mn>1</mn><mo>+</mo><mrow><mfrac><mrow><mo>(</mo><mrow><mi>desired_pixel</mi><mo>⁢</mo><mi>_adjustment</mi></mrow><mo>)</mo></mrow><mi>Tx</mi></mfrac><mo>.</mo></mrow></mrow></mrow></math></maths><br /> Only in rare occurrences will Yscale be other than zero, and only then as a corrective measure for any noted vertical parallax. Using the altered transform, a new registered image view is created, e.g. the following: <br />Left′=<i>Tl</i>_alt*left_<i>r </i><br /> Such scaling effectively adds to or subtracts from the parallax for each pixel, effectively moving the point of now parallax forward or backward in the scene. The appropriate scaling is determined by the translational portion of the transform and the required adjustment.

0108At step <b>338</b> of <figref idref="DRAWINGS">FIGS. 3A-3D</figref>, it is determined whether the parallax is within the ability of a viewer to resolve the three-dimensional image. If it is determined that the parallax is within the ability of a viewer to resolve the three-dimensional image, the method proceeds to step <b>342</b>. If not, the method proceeds to step <b>340</b>. For a stereoscopic pair of registered “Left′” and “Right′” images, the pixel-by-pixel parallax for pixels of segmented objects may also be adjusted <b>340</b>, or altered, which effectively performs a pseudo-decrease (or increase) in the parallax of individual segmented objects for objects that still cannot be resolved after the screen adjustments above. This process involves the same type of manipulation and re-application of a transform, but specific to a given region of the picture, corresponding to the objects in question.

0109Since moving an object region in the image may result in a final image that has undefined pixel values, a pixel-fill process is required to ensure that all areas of the resultant image have defined pixel values after object movement. An exemplary procedure for this is described below. Other processes, both more or less complex, may be applied.

0110<figref idref="DRAWINGS">FIG. 11</figref> illustrates a flow chart of an exemplary method for adjusting parallax of segmented, moving objects according to embodiments of the present subject matter. Further, <figref idref="DRAWINGS">FIG. 12</figref> illustrates an exemplary diagram of a method for adjusting parallax of moving, segmented objects according to embodiments of the present subject matter. The method may be implemented, for example, by the image generator function <b>114</b> shown in <figref idref="DRAWINGS">FIG. 1</figref>. Referring now to <figref idref="DRAWINGS">FIG. 11</figref>, the method includes identifying <b>1100</b> a segmented object in an image I to relocate. The method of <figref idref="DRAWINGS">FIG. 11</figref> also includes defining a bounding rectangle R around the object and defining left/right bounds of a region M for left/right motion <b>1102</b>. In an example of defining the bounding rectangle R, the segmented region to be moved may be identified as a rectangular region of pixels, R, in the left_r or right_r image (whichever is to be altered), sized X columns by Y rows with the following coordinates:

0111R_ul=(x_l,y_u); the upper left coordinate

0112R_ll=(x_l,y_l); the lower left coordinate

0113R_ur=(x_r,y_u); the upper right coordinate

0114R_lr=(x_r,y_l); the lower right coordinate

0000For a large or complex object, multiple rectangular regions may need to be defined and moved, but the process executes identically for each region.

0115In an example of defining left/right bounds of a region M for left/right motion, the region M is the region to which the altered transform can be applied. This process first assesses the direction of movement to occur and defines one side of region M. If the intended movement is to the right, then the right bounding edge of region M is defined by the following coordinate pair in the appropriate left_r or right_r image (whichever is to be adjusted): <br /><i>M</i>_ur=(<i>x</i>_r<i>+P,y</i>_u); upper right<br /><i>M</i>_lr=(<i>x</i>_r<i>+P,y</i>_l); lower right<br /> If movement is to the left, the left bounding edge of region M is defined as: <br /><i>M</i>_ul=(<i>x</i>_l<i>−P,y</i>_u); upper left<br /><i>M</i>_ll=(<i>x</i>_l<i>−P,y</i>_l); lower left<br /> P is an extra number of pixels for blending purposes. The scaled version of the registration transform matrix T_altis provided <b>1104</b>. The inverse of the altered transform (assumed already calculated as above for movement of the screen plane for the whole image) may then be applied <b>1106</b> to the opposite edge of the region R to get the other edge of region M. For the sake of example, assume that the movement of R is intended to be to the right, and that the left image is to be altered (meaning Tl_althas been created for the intended movement). Since the right side of M is already known, the other side can now be determined as: <br /><i>M</i>_ul<i>=Tl</i>_alt⁻¹<i>*R</i>_ul+(<i>P,</i>0); upper right<br /><i>M</i>_ll<i>=Tl</i>_alt⁻¹<i>*R</i>_u+(<i>P,</i>0); lower right<br /> Again, P is an extra number of pixels for blending, and Tl_alt⁻¹is the inverse transform of Tl_alt. Note that P is added after the transform application, and only to the X coordinates. The region to be moved is now defined as the pixels within the rectangle defined by M.

0116The method also includes applying <b>1108</b> the inverse transform of Tl_altto the image to be transformed for blocks in the region M. For example, from this point, one of two operations can be used, depending on a measurement of the uniformity (texture) or the area defined by the coordinates M_ul, M_llR_ul, and R_ll(remembering again that the region would be using other coordinates for a movement to the left). Uniformity is measured by performing a histogram analysis on the RGB values for the pixels in this area. If the pixel variation is within a threshold, the area is deemed uniform, and the movement of the region is affected by applying the following equation: Left′=Tl_alt*left_r, for left_r ϵM. This is the process shown in the example method of <figref idref="DRAWINGS">FIG. 12</figref>. Alternatively, if the area is not uniform, movement of the object is applied to the smaller area:

0117Left′=Tl_alt*left_r, for the left_r region defined by R_ul, R_ll, M_ur, and M_lr.

0000The method of <figref idref="DRAWINGS">FIG. 11</figref> includes overwriting 1110 pixels within the defined rectangle in the transformed image with the newly transformed pixels.

0118The method of <figref idref="DRAWINGS">FIG. 11</figref> includes interpolating the outer P pixels on each side of the area with existing data. For example, the area in Left′ defined by the coordinates M_ul, M_ll, R_ur, and R_lrwill be empty, but is filled with a linear gradient fill between points on each horizontal line in the region. The fill-in process first determines the following distance d: <br /><i>d=R</i>_ul(<i>x</i>)−<i>M</i>_ul(<i>x</i>)<br /> for the x-coordinates of R_uland M_ul, and then proceeds to determine an interpolated gradient between the two pixel positions to fill in the missing values. For simplicity of implementation, the interpolation is always performed on a power of two, meaning that the interpolation will produce one of 1, 2, 4, 8, 16, etc. pixels as needed between the two defined pixels. Pixel regions that are not a power of two are mapped to the closest power of two, and either pixel repetition or truncation of the sequence is applied to fit. As an example, if R_ul(x)=13 and M_ul(x)=6, then d=7, and the following intermediate pixel gradient is calculated for a given row, j, in the region: <br /><i>p</i>1=7/8*(<i>x</i>₆<i>,y</i>)+1/8*(<i>x</i>₁₃<i>,y</i>)<br /><i>p</i>2=6/8*(<i>x</i>₆<i>,y</i>)+2/8*(<i>x</i>₁₃<i>,y</i>)<br /><i>p</i>3=5/8*(<i>x</i>₆<i>,y</i>)+3/8*(<i>x</i>₁₃<i>,y</i>)<br /><i>p</i>4=4/8*(<i>x</i>₆<i>,y</i>)+4/8*(<i>x</i>₁₃<i>,y</i>)<br /><i>p</i>5=3/8*(<i>x</i>₆<i>,y</i>)+5/8*(<i>x</i>₁₃<i>,y</i>)<br /><i>p</i>6=2/8*(<i>x</i>₆<i>,y</i>)+6/8*(<i>x</i>₁₃<i>,y</i>)<br /><i>p</i>7=1/8*(<i>x</i>₆<i>,y</i>)+7/8*(<i>x</i>₁₃<i>,y</i>)<br /> p8=(x₁₃, y) <br /> Since only 7 values are needed, p8 would go unused in this case, such that the following assignments would be made:

0119(x₆,y_j)=p1

0120(x₇,y_j)=p2

0121(x₈,y_j)=p3

0122(x₉,y_j)=p4

0123(x₁₀,y_j)=p5

0124(x₁₁,y_j)=p6

0125(x₁₂,y_j)=p7

0000This process can repeat for each row in the empty region.

0126A weighted averaging the outer P “extra” pixels on each side of the rectangle with the pixel data currently in those positions is performed to blend the edges.

0127As an alternative to the procedure of applying movement and pixel blending to alter the parallax of an object, the disparity map calculated using the two views, “Left′” and “Right′,” can be altered for the region M to reduce the disparity values in that region, and then applied to one of the “Left′” or “Right′” single image views to create a new view (e.g., “Left_disparity”). The result of this process is a new stereo pair (e.g., “Left′” and “Left_disparity”) that recreates the depth of the original pair, but with lesser parallax for the objects within the region M. Once created in this manner, the “disparity” view becomes the new opposite image to the original, or for example, a created “Left_disparity” image becomes the new “Right′” image.

0128Returning to <figref idref="DRAWINGS">FIGS. 3A-3D</figref>, the method includes performing <b>342</b> depth enhancements. For example, for a stereoscopic pair of registered “Left′” and “Right′” images, the screen plane of the stereoscopic image may be relocated to allow a viewer to emphasize or de-emphasize object depth in the three-dimensional image. This relocation may be implemented to enhance the subjective quality of the displayed image or to create three-dimensional effects that involve changing object depth over time to simulate motion. The process for this uses the same procedures as for general readjustment of the screen plane, and for segmented object specific adjustments, but is performed voluntarily for effect, rather than necessarily for correction.

0129The method of <figref idref="DRAWINGS">FIGS. 3A-3D</figref> includes removing <b>344</b> moving objects. For example, for a stereoscopic pair of registered “Left′” and “Right′” images, disparity differences can be identified which indicate object motion within, into, or out of the image frame for one image. These areas can be identifiable as those which have “infinite” parallax assignments from the disparity map step of the process. Areas indicating such motion are replicated or removed using data from the other image view and/or other views captured between the “Left” and “Right” images. Without any loss of generality, we will assume that first picture taken is the leftmost, and the last picture taken is the rightmost. In actuality, the opposite can occur. In the following description the following definitions apply: <ul id="ul0005" list-style="none"><li id="ul0005-0001" num="0000"><ul id="ul0006" list-style="none"><li id="ul0006-0001" num="0130">First picture: the first picture captured in the sequence (1)</li><li id="ul0006-0002" num="0131">Last picture: the last picture captured in the sequence (N)</li><li id="ul0006-0003" num="0132">Leftmost pictures: any set of pictures from 1^stto N−1</li><li id="ul0006-0004" num="0133">Rightmost pictures: any set of pictures from 2^ndto Nth</li><li id="ul0006-0005" num="0134">Left target picture: any of the leftmost pictures or a modified version of all captured pictures that will be used during the 3D generation process as left picture</li><li id="ul0006-0006" num="0135">Right target picture: any of the rightmost pictures or a modified picture that will be used during the 3D generation process as right picture <br /> The method of identifying and compensating for moving objects consists of the following steps. For a given sequence of pictures captured between two positions, divide each picture into smaller areas and calculate motion vectors between all pictures in all areas. Calculate by a windowed moving average the global motion that results from the panning of the camera. Then subtract the area motion vector from the global motion to identify the relative motion vectors of each area in each picture. If the motion of each area is below a certain threshold, the picture is static and the first and last picture, or any other set with the desired binocular distance, can be used as left and right target pictures to form a valid stereoscopic pair that will be used for registration, rectification, and generation of a 3D picture. If the motion of any area is above an empirical threshold, then identify all other areas that have zero motion vectors and copy those areas from any of the leftmost pictures to the target left picture and any of the rightmost pictures to the target right picture. </li></ul></li></ul>

0136For objects where motion is indicated and where the motion of an object is below the acceptable disparity threshold, identify the most suitable image to copy the object from, copy the object to the left and right target images and adjust the disparities as shown in the attached figure. The more frames that are captured, the less estimation is needed to determine the rightmost pixel of the right view. Most of occluded pixels can be extracted from the leftmost images. For an object that is moving in and out of the scene between the first and last picture, identify the object and completely remove it from the first picture if there is enough data in the captured sequence of images to fill in the missing pixels.

0137For objects where motion is indicated and where the motion is above the acceptable disparity, identify the most suitable picture from which to extract the target object and extrapolate the proper disparity information from the remaining captured pictures.

0138The actual object removal process involves identifying N×N blocks, with N empirically determined, to make up a bounding region for the region of “infinite” parallax, plus an additional P pixels (for blending purposes), determining the corresponding position of those blocks in the other images using the parallax values of the surrounding P pixels that have a similar gradient value (meaning that high gradient areas are extrapolated from similar edge areas and low gradient areas are extrapolated from similar surrounding flat areas), copying the blocks/pixels from the opposite locations to the intended new location, and performing a weighted averaging of the outer P “extra” pixels with the pixel data currently in those positions to blend the edges. If it is determined to remove an object, fill-in data is generated <b>346</b>. Otherwise, the method proceeds to step <b>348</b>.

0139<figref idref="DRAWINGS">FIGS. 13A, 13B, and 13C</figref> illustrate an exemplary process for disparity interpolation according to embodiments of the present subject matter. Referring to <figref idref="DRAWINGS">FIGS. 13A, 13B, and 13C</figref>, positions <b>1300</b> and <b>1302</b> are positions of a camera (not shown) when capturing images of object <b>1304</b> at different times. The image captured at position <b>1300</b> was captured prior to the image captured at position <b>1302</b>. A view of the object <b>1304</b> from position <b>1300</b> is indicated by lines <b>1306</b>, and a view of the object <b>1304</b> from position <b>1302</b> is indicated by lines <b>1308</b>. As shown by direction arrow <b>1310</b> in <figref idref="DRAWINGS">FIG. 13B</figref>, the object <b>1304</b> is moving from left to right across the camera's view. Between the image capture times, the object <b>1304</b> has moved from a position <b>1304</b>A (shown in a broken line) to the position <b>1304</b> shown in <figref idref="DRAWINGS">FIG. 13B</figref>) as shown in <figref idref="DRAWINGS">FIG. 13B</figref>.

0140The movement of the object <b>1304</b> is such that the disparity is unacceptable and should be corrected. In this example, the image obtained from position <b>1300</b> can be utilized for creating a three-dimensional image, and the image obtained from position <b>1302</b> can be altered for use together with the other image in creating the three-dimensional image. To correct, the object <b>1304</b> may be moved to the left (as indicated by direction arrow <b>1312</b> in <figref idref="DRAWINGS">FIG. 13C</figref>) in the image captured from position <b>1302</b>. The object <b>1304</b> may be moved to the left to a position of a desired left view (i.e., the positioning of the object <b>1304</b> within the view from position <b>1302</b> as indicated by lines <b>1314</b> shown in <figref idref="DRAWINGS">FIG. 13C</figref>. The desired left image for the three-dimensional image may be composed by reducing visibility of the left-most pixel from RLa to RLd; and by increasing visibility of the right-most pixel by interpolating the [RRd, RRa] area from pixels found in the right-most of RRa.

0141Another example of a process for adding/removing objects from a single image is illustrated in <figref idref="DRAWINGS">FIGS. 14 and 15</figref>. <figref idref="DRAWINGS">FIG. 14</figref> illustrates a flow chart of an exemplary method for adding/removing objects from a single image according to embodiments of the present subject matter. Referring to <figref idref="DRAWINGS">FIG. 14</figref>, the method includes creating parallax maps for stereoscopic images I<b>1</b> and I<b>2</b> and defining the area of image I<b>1</b> to change (step <b>1400</b>). The method of <figref idref="DRAWINGS">FIG. 13</figref> also includes defining <b>1402</b> 8×8 blocks in image I<b>1</b> to cover the intended area plus P pixels. Using the parallax map, the corresponding data in image I<b>2</b> is found (step <b>1404</b>). The corresponding data is copied from image I<b>2</b> to image I<b>1</b> (step <b>1406</b>). Next, the method includes applying a weighted average of the outer P pixels of the copy (step <b>1408</b>).

0142Referring to <figref idref="DRAWINGS">FIG. 15</figref>, the figure is a diagram of an exemplary method for adding/removing objects from a single image according to embodiments of the present subject matter. An original “Left′” image <b>1500</b> and an original “Right′” image <b>1502</b> are provided. The images may be paired to form a three-dimensional image in accordance with embodiments of the subject matter described herein. The images <b>1500</b> and <b>1502</b> both show objects, which are designated <b>1504</b>L and <b>1506</b>L, respectively, in the “Left′” image <b>1500</b>, and designated <b>1504</b>R and <b>1506</b>R, respectively, in the “Right′” image <b>1502</b>. The parallax of these objects is such that three-dimensional display of these objects in the three-dimensional image <b>1504</b> would be satisfactory to a viewer.

0143Referring to <figref idref="DRAWINGS">FIG. 15</figref>, the images of another object (designated <b>1508</b>L in the “Left′” image <b>1500</b>, and designated <b>1508</b>R in the “Right′” image <b>1502</b>) were captured while the object was moving at such a speed such that the parallax disparity of the object in the “Left′” image <b>1500</b> and the “Right” image <b>1502</b> makes viewing the three-dimensional image <b>1504</b> of the object unsatisfactory to a viewer. For this reason, the moving object may be removed from the “Left′” image <b>1500</b> and the “Right” image <b>1502</b>. A new “Left′” image <b>1510</b> without the moving object may be generated by bounding a region <b>1512</b>L to be corrected in the original “Left′” image <b>1500</b> for removing the moving object (i.e., an area including the moving object in the “Left′” image <b>1500</b>). A corresponding area in the original “Right′” image <b>1502</b> may be copied and used for replacing the bounded region <b>1512</b>L in the original “Left′” image <b>1500</b> to render the new “Left′” image <b>1510</b>. In a similar manner, a new “Right′” image <b>1514</b> without the moving object can be rendered. The new “Left′” image <b>1510</b> and the new “Right′” image <b>1514</b> can then be paired for rendering a new three-dimensional image <b>1516</b> without the moving object.

0144As an alternative to the procedure of identifying bounding regions of 8×8 blocks around objects to be added or removed in a view, the disparity map calculated using multiple views, “Left”, “Right”, and/or the images in between, can be applied to one of the “Left” or “Right” single image views to create a new view (e.g., “Left_disparity”). The result of this process is a new stereo pair (e.g., “Left′” and “Left_disparity”) that effectively recreates the depth of the original pair, but without object occlusions, movement, additions, or removals. Once created in this manner, the “disparity” view becomes the new opposite image to the original, or for example, a created “Left_disparity” image becomes the new “Right′” image. Effectively, this procedure mimics segmented object removal and/or addition, but on a full image scale.

0145Returning to <figref idref="DRAWINGS">FIGS. 3A-3D</figref>, the method includes applying <b>348</b> color correction to the images. For example, for a plurality of images, a pixel-by-pixel color comparison may be performed to correct lighting changes between image captures. This is performed by using the parallax map to match pixels from Left′ to Right′ and comparing the luminance and chrominance values of those pixels. Pixels with both large luminance and chrominance discrepancies are ignored, assuming occlusion. Pixels with similar luminance and variable chrominance are altered to average their chrominance levels to be the same. Pixels with similar chrominance and variable luminance are altered to average their luminance values to account for lighting and reflection changes.

0146For a finalized, color corrected, motion corrected stereoscopic image pair, the “Left′” and “Right′” images are ordered and rendered to a display as a stereoscopic image. The format is based on the display parameters. Rendering can require interlacing, anamorphic compression, pixel alternating, and the like.

0147For a finalized, color corrected, motion corrected stereoscopic image pair, the “Left′” view may be compressed as the base image and the “Right′” image may be compressed as the disparity difference from the “Left′” using a standard video codec, differential JPEG, or the like.

0148The method of <figref idref="DRAWINGS">FIGS. 3A-3D</figref> includes displaying <b>350</b> the three-dimensional image on a stereoscopic display. For example, the three-dimensional image may be displayed on the display <b>112</b> of the device <b>100</b> or a display of the computer <b>108</b>. Alternatively, the three-dimensional image may be suitably communicated to another device for display.

0149When a video sequence is captured with lateral camera motion as described above, stereoscopic pairs can be found within the sequence of resulting images. Stereoscopic pairs are identified based on their distance from one another determined by motion analysis (e.g., motion estimation techniques). Each pair represents a three-dimensional picture or image, which can be viewed on a suitable stereoscopic display. If the camera does not have a stereoscopic display, the video sequence can be analyzed and processed on any suitable display device. If the video sequence is suitable for creating three-dimensional content (e.g., one or more three-dimensional images), it is likely that there are many potential stereoscopic pairs, as an image captured at a given position may form a pair with images captured at several other positions. The image pairs can be used to create three-dimensional still images or re-sequenced to create a three-dimensional video.

0150When creating three-dimensional still images, the user can select which images to use from the potential pairs, thereby adjusting both the perspective and parallax of the resulting images to achieve the desired orientation and depth. <figref idref="DRAWINGS">FIG. 16</figref> illustrates an exemplary process for generating three-dimensional still images from a standard two-dimensional video sequence by identifying stereoscopic pairs in accordance with embodiments of the present subject matter. Referring to <figref idref="DRAWINGS">FIG. 16</figref>, this process can be used to create content for multi-view stereoscopic displays by creating a set of three-dimensional images of a subject with the same parallax but captured from slightly different positions. A three-dimensional video sequence can be created using one of the following methods. The first method is to select stereoscopic pairs with a constant positional offset, and sequence them in the same relative order in which they were captured. The user can select the offset to achieve the desired depth. During playback this method creates the effect of camera motion the same as occurred during capture, while the depth of the scene remains constant due to the fixed parallax. <figref idref="DRAWINGS">FIG. 17</figref> illustrates an exemplary process for generating three-dimensional video from a standard two-dimensional video sequence according to embodiments of the present subject matter.

0151Another method of creating a three-dimensional sequence includes creating stereoscopic pairs by grouping the first and last images in the sequence, followed by the second and next-to-last images, and so on until all images have been used. During playback this creates the effect of the camera remaining still while the depth of the scene decreases over time due to decreasing parallax. The three-dimensional images can also be sequenced in the opposite order so that the depth of the scene increases over time. <figref idref="DRAWINGS">FIG. 18</figref> illustrates an exemplary process of generating three-dimensional video with changing parallax and no translational motion from a standard two-dimensional video sequence in accordance with an embodiment of the subject matter disclosed herein. The camera or other display device can store a representation of the resulting three-dimensional still images or video in an appropriate compressed format. For more efficient storage of still images, one of the images in the stereoscopic pair can be compressed directly, while the other image is represented by its differences with the first image. For video sequences, the first stereoscopic pair in the sequence can be stored as described above for still images, while all images in other pairs are represented by their differences with the first image.

0152The generation and presentation, such as display, of three-dimensional images of a scene in accordance with embodiments of the present subject matter may be implemented by a single device or combination of devices. In one or more embodiments of the present subject matter, images may be captured by a camera such as, but not limited to, a digital camera. The camera may be connected to a personal computer for communication of the captured images to the personal computer. The personal computer may then generate one or more three-dimensional images in accordance with embodiments of the present subject matter. After generation of the three-dimensional images, the personal computer may communicate the three-dimensional images to the camera for display on a suitable three-dimensional display. The camera may include a suitable three-dimensional display. Also, the camera may be in suitable electronic communication with a high-definition television for display of the three-dimensional images on the television. The communication of the three-dimensional images may be, for example, via an HDMI connection.

0153In one or more other embodiments of the present subject matter, three-dimensional images may be generated by a camera and displayed by a separate suitable display. For example, the camera may capture conventional two-dimensional images and then use the captured images to generate three-dimensional images. The camera may be in suitable electronic communication with a high-definition television for display of the three-dimensional images on the television. The communication of the three-dimensional images may be, for example, via an HDMI connection.

0154In accordance with embodiments of the presently disclosed subject matter, the memory <b>104</b> and the CPU <b>106</b> shown in <figref idref="DRAWINGS">FIG. 1</figref> may be operable together to implement an image generator function <b>114</b> for generating three-dimensional images. The image generator function <b>114</b> may generate a three-dimensional image of a scene using two or more images of the scene captured by the device <b>100</b>. <figref idref="DRAWINGS">FIG. 19</figref> illustrates a flow chart of an exemplary method for generating a three-dimensional image of a scene using the device <b>100</b>, alone or together with any other suitable device, in accordance with embodiments of the present disclosure. In this example, the device <b>100</b> may be operating in a “stereoscopic mode” for assisting the camera user in generating high-quality, three-dimensional images of a scene. Referring to <figref idref="DRAWINGS">FIG. 19</figref>, the method includes receiving <b>1900</b> a first still image of a scene to which the sensor array <b>102</b> is exposed. For example, the sensor array <b>102</b> may be used for capturing a still image of the scene. The still image and settings of the device <b>100</b> during capture of the image may be stored in memory <b>104</b>. The CPU <b>106</b> may implement instructions stored in the memory <b>104</b> for storing the captured image in the memory <b>104</b>.

0155The method of <figref idref="DRAWINGS">FIG. 19</figref> includes determining <b>1902</b> a plurality of first guides associated with the first still image. For example, depth detection and edge and feature point extraction may be performed on the first still image to identify a set of interest points (IP) for use in assisting the user to move the camera for capturing a second still image to be used for generating a three-dimensional image. Additional details of this technique are described in further detail herein.

0156The method of <figref idref="DRAWINGS">FIG. 19</figref> includes displaying a real-time image of the scene on a display. For example, the device <b>100</b> may enter a live-view mode in which the user may direct the device <b>100</b> such that the sensor array <b>102</b> is exposed to a scene, and in this mode an image of the scene is displayed on the display <b>112</b> in real-time as understood by those of skill in the art. As the device <b>100</b> is moved, the real-time image displayed on the display <b>112</b> also moves in accordance with the movement of the device <b>100</b>.

0157The method of <figref idref="DRAWINGS">FIG. 19</figref> includes determining <b>1906</b> a plurality of second guides associated with the real-time image. For example, one or more of the image sensor data, an image sensor property, optical property, focal property, and viewing property of the captured images may be determined. In addition for example, the method may include calculating one of camera positional offset and pixel offset indicia in a real-time display of the scene to indicate a target camera positional offset with respect to one captured image and potentially, one of the image sensor property, optical property, focal property, and viewing property of the captured images. Further, for example, for vertical and perspective alignment, a Hough or any other transform for line identification may be applied, and the dominant horizontal and perspective lines in the two images (alternately colored) may be superimposed over the displayed real-time image in the live-view mode to assist the user in aligning the second picture vertically and for perspective. Further, a procedure to calculate required horizontal displacement, as described in more detail herein, may use the interest point set (IP) of the first image for performing a point correspondence operation to find similar points in the displayed real-time image as guidance for the capture of a second image.

0158The method of <figref idref="DRAWINGS">FIG. 19</figref> includes displaying <b>1908</b> the first and second guides on the display for guiding selection of a position of an image capture device to capture a second still image of the scene for pairing the first and second still images as a stereoscopic pair of a three-dimensional image. For example, an “alignment guide” may be displayed on the display <b>112</b>, as described in more detail herein, for assisting a user to position the device <b>100</b> for capturing a second image of the scene that would be suitable to use with the first captured image for generation of a three-dimensional image. Once the device <b>100</b> is positioned in suitable alignment for capturing the second image, the image generator <b>114</b> can determine such condition and take the second image automatically, or the user may then operate the device <b>100</b> for capturing the second image, such as, but not limited to, depressing an image capture button on the device <b>100</b>. After the second image is captured, the first and second captured images may be suitably processed in accordance with embodiments of the present disclosure for creating a three-dimensional image as shown in step <b>1910</b>. Particularly, two of the captured still images can be corrected to compensate for one or more of camera vertical shift, vertical tilt, horizontal tilt, and rotation. Other images may also be automatically captured between the time the first and second images are captured, and may also be used for generating a three-dimensional image based on the corrected still images. The method of <figref idref="DRAWINGS">FIG. 19</figref> may include displaying <b>210</b> the three-dimensional image. For example, the image may be displayed on the display <b>112</b> or any other suitable display.

0159Although the above examples are described for use with a device capable of capturing images, embodiments described herein are not so limited. Particularly, the methods described herein for assisting a camera user to generate a three-dimensional image of a scene may, for example, be implemented in any suitable system including a memory and computer processor. The memory may have stored therein computer-executable instructions. The computer processor may execute the computer-executable instructions. The memory and computer processor may be configured for implementing methods in accordance with embodiments of the present disclosure.

0160<figref idref="DRAWINGS">FIGS. 20A and 20B</figref> illustrate a flow chart of an exemplary method for generating a three-dimensional image of a scene in accordance with embodiments of the present disclosure. The method can convert a plurality of images to a three-dimensional image that can be viewed on a stereoscopic display. Referring to <figref idref="DRAWINGS">FIG. 20A</figref>, the method can begin with receiving <b>2000</b> a plurality of images of a scene. For example, the images can be captured by a standard digital video or still camera, or a plurality of different cameras of the same type or different types. A camera user may use the camera to capture an initial image. Next, the camera user may capture subsequent image(s) at positions to the left or right of the position at which the initial image was captured. These images may be captured as still images or as a video sequence of images. The images may be captured using a device such as the device <b>100</b> shown in <figref idref="DRAWINGS">FIG. 1</figref>. The images may be stored in a memory such as the memory <b>104</b> shown in <figref idref="DRAWINGS">FIG. 1</figref>. In another example, the images may be received at a device after they have been captured by a different device.

0161In accordance with embodiments of the present disclosure, a user may create high-quality, three-dimensional content using a standard digital still, video camera (or cameras), other digital camera equipment or devices (e.g., a camera-equipped mobile phone), or the like. In order to generate a good three-dimensional picture or image, a plurality of images of the same object can be captured from varied positions. In an example, in order to generate three-dimensional images, a standard digital still or video camera (or cameras) can be used to capture a plurality of pictures with the following guidelines. The user uses the camera to capture an image, and then captures subsequent pictures after moving the camera left or right from its original location. These pictures may be captured as still images or as a video sequence.

0162<figref idref="DRAWINGS">FIG. 21</figref> illustrates a diagram of an exemplary image capture technique for facilitating subsequent conversion to three-dimensional images in accordance with embodiments of the present disclosure. Referring to <figref idref="DRAWINGS">FIG. 21</figref>, a camera <b>2100</b> is used for capturing N images (i.e., images 1, 2, 3, . . . N−1, N) of an object of interest <b>2102</b> within a scene. The camera <b>2100</b> and the object <b>2102</b> are positioned approximately D feet apart as each image is captured. The distance between positions at which images are captured (the stereo baseline) for generating a three-dimensional image can affect the quality of the three-dimensional image. The optimal stereo baseline between the camera positions can vary anywhere between 3 centimeters (cm) and several feet, dependent upon a variety of factors, including the distance of the closest objects in frame, the lens focal length or other optics properties of the camera, the camera crop factor (dependent on sensor size), the size and resolution of the display on which the images will be viewed, and the distance from the display at which viewers will view the images. A general recommendation is that the stereo baseline should not exceed the distance defined by the following equation:

0163<maths id="MATH-US-00013" num="00013"><math overflow="scroll"><mrow><mrow><mi>B</mi><mo>=</mo><mfrac><mrow><mn>12</mn><mo>⁢</mo><mi>D</mi></mrow><mrow><mn>30</mn><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mrow><mi>FC</mi><mo>/</mo><mn>50</mn></mrow></mrow></mfrac></mrow><mo>,</mo></mrow></math></maths><br /> where B is the stereo baseline separation in inches, D is the distance in feet to the nearest object in frame, F is the focal length of the lens in millimeters (mm), and C is the camera crop factor relative to a full frame (36×24 square mm) digital sensor (which approximates the capture of a 35 mm analog camera). In the examples provided herein, it is assumed that at least two images have been captured, at least two of which can be interpreted as a stereoscopic pair.

0164Embodiments of the present disclosure define a “stereoscopic mode,” which may be used in conjunction with a standard digital still camera, standard video camera, other digital camera, or the like to assist the camera user in performing the function of capturing images that ultimately yield high-quality, three-dimensional images. <figref idref="DRAWINGS">FIG. 22</figref> illustrates a flow chart of an exemplary method for assisting a user to capture images for use in a process to yield high-quality, three-dimensional images in accordance with embodiments of the present disclosure. The image generator function <b>114</b> shown in <figref idref="DRAWINGS">FIG. 1</figref> may be used for implementing the steps of the method of <figref idref="DRAWINGS">FIG. 22</figref>. Referring to <figref idref="DRAWINGS">FIG. 22</figref>, the method includes entering <b>2200</b> a stereoscopic mode. After entering the stereoscopic mode, the method includes capturing <b>2202</b> the first image of the object or scene of interest. The camera stores <b>2204</b> its settings, including, but not limited to, aperture, focus point, focus algorithm, focal length, ISO, exposure, and the like, for use in capturing other images of the object or scene, to ensure consistent image quality. According to an aspect, the only camera variable that may be allowed to change between image captures of a pair is shutter speed, and then, only in the context of maintaining a constant exposure (to suitable tolerances).

0165The method of <figref idref="DRAWINGS">FIG. 22</figref> includes determining <b>2206</b> a position offset for a next image to be captured. For example, in the stereoscopic mode, upon capture of the first image of a pair, the camera may use the information relating to optics, focus, and depth of field (Circle of Confusion), in combination with measurable qualities of the capture image, to approximate the depth of the closest focused object in the frame. For a given combination of image (camera) format circle of confusion (c), f-stop (aperture) (A), and focal length (F), the hyperfocal distance (the nearest distance at which the far end depth of field extends to infinity) of the combination can be approximated using the following equation:

0166<maths id="MATH-US-00014" num="00014"><math overflow="scroll"><mrow><mi>H</mi><mo>≈</mo><mrow><mfrac><msup><mi>F</mi><mn>2</mn></msup><mrow><mi>A</mi><mo>*</mo><mi>c</mi></mrow></mfrac><mo>.</mo></mrow></mrow></math></maths><br /> In turn, the near field depth of field (D_n) for an image can be approximated for a given focus distance (d) using the following equation:

0167<maths id="MATH-US-00015" num="00015"><math overflow="scroll"><mrow><msub><mi>D</mi><mi>n</mi></msub><mo>≈</mo><mfrac><mrow><mi>H</mi><mo>*</mo><mi>d</mi></mrow><mrow><mo>(</mo><mrow><mi>H</mi><mo>+</mo><mi>d</mi></mrow><mo>)</mo></mrow></mfrac></mrow></math></maths><br /> (for moderate to large d), and the far field DOF (D_f) as

0168<maths id="MATH-US-00016" num="00016"><math overflow="scroll"><mrow><msub><mi>D</mi><mi>f</mi></msub><mo>≈</mo><mfrac><mrow><mi>H</mi><mo>*</mo><mi>d</mi></mrow><mrow><mo>(</mo><mrow><mi>H</mi><mo>-</mo><mi>d</mi></mrow><mo>)</mo></mrow></mfrac></mrow></math></maths><br /> for d<H. For values of d>=H, the far field DOF is infinite. <br /> Since the focus distance, focal length, and aperture are recorded at the time of capture, and the circle of confusion value is known for a given camera sensor format, the closest focused object can be assumed to be at the distance D_n, while the furthest focused pixels are at D_f.

0169In addition to this depth calculation, edge and feature point extraction may be performed on the image to identify interest points for later use. To reduce the complexity of this evaluation, the image may be down-scaled to a reduced resolution before subsequent processing. An edge detection operation is performed on the resultant image, and a threshold operation is applied to identify the most highly defined edges at a given focus distance. Finally, edge crossing points are identified. This point set, IP, represents primary interest points at the focused depth(s) of the image.

0170The stereoscopic camera assist method then uses the depth values D_nand D_fto determine the ideal distance to move right or left between the first and subsequent image captures. The distance to move right or left between the first and subsequent image captures is the position offset. It is assumed that the optimal screen plane is some percentage, P, behind the nearest sharp object in the depth of field, or at <br /><i>D</i>_s=(<i>D</i>_n*(1+<i>P/</i>100)),<br /> where P is a defined percentage that may be camera and/or lens dependent. At the central point of this plane, an assumed point of eye convergence, there will be zero parallax for two registered stereoscopic images. Objects in front of and behind the screen plane will have increasing amounts of disparity as the distance from the screen increases (negative parallax for objects in front of the screen, positive parallax for object behind the screen). <figref idref="DRAWINGS">FIGS. 23A and 23B</figref> depict diagrams of examples of close and medium-distance convergence points, respectively, in accordance with embodiments of the present disclosure. Referring to the examples of <figref idref="DRAWINGS">FIGS. 23A and 23B</figref>, this central point of the overlapping field of view on the screen plane (zero parallax depth) of the two eyes in stereoscopic viewing defines a circle that passes through each eye with a radius, R, equal to the distance to the convergence point. Still referring to <figref idref="DRAWINGS">FIGS. 23A and 23B</figref>, the angle, θ, between the vectors from the central point on the screen plane to each of the two eyes is typically between 1° and 6°. A default of 2° is applied, with a user option to increase or decrease the angle for effect. Medium distance convergence gives a relatively small angular change, while close convergence gives a relatively large angular change.

0171The value D_sgives the value of R. Hence, the binocular distance indicated to the user to move before the second/last capture is estimated as <br /><i>B=</i>2*<i>D</i>_ssin θ/2.<br /> or for default θ=2°, and

0172<maths id="MATH-US-00017" num="00017"><math overflow="scroll"><mrow><mi>B</mi><mo>=</mo><mfrac><msub><mi>D</mi><mi>s</mi></msub><mn>29</mn></mfrac></mrow></math></maths><br /> for B and D_smeasured in inches (or centimeters, or any consistent unit).

0173The method of <figref idref="DRAWINGS">FIG. 22</figref> includes identifying a bounding box for the set of focused points, IP, defined above, and superimposing the boundaries of this region with proper translational offset, S, on a display (or viewfinder) as a guide for taking the second picture <b>2210</b>. In addition to the binocular distance calculation, a feedback mechanism may assist the user with camera alignment for the second/last capture <b>2208</b>. One exemplary process for this is to apply a Hough transform for line detection to the first image, and superimpose the dominant horizontal and perspective lines in the two images (alternately colored) over the live-view mode or electronic viewfinder to assist the user in aligning the second/last picture vertically and for perspective. It should be noted that the Hough step is optional. For example, these guide lines may be displayed on the display <b>112</b> shown in <figref idref="DRAWINGS">FIG. 1</figref>. At step <b>2212</b>, a user moves the image capture device to a new location, aligning the translation region and any other guides on the display with those of the first captured image.

0174The value S is calculated using the value D_s(converted to mm) and the angle of view (V) for the capture. The angle of view (V) is given by the equation

0175<maths id="MATH-US-00018" num="00018"><math overflow="scroll"><mrow><mi>V</mi><mo>=</mo><mrow><mn>2</mn><mo>*</mo><msup><mi>tan</mi><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⁢</mo><mfrac><mi>W</mi><mrow><mn>2</mn><mo>*</mo><mi>F</mi></mrow></mfrac></mrow></mrow></math></maths><br /> for the width of the image sensor (W) and the focal length (F). Knowing V and D_s, the width of the field of view (WoV) can be calculated as <br /><i>WoV=</i>2*<i>D</i>_s*tan(<i>V/</i>2)=<i>D</i>_s<i>*W/F. </i><br /> The width of view for the right eye capture is the same. Hence, if the right eye capture at the camera is to be offset by the binocular distance B, and the central point of convergence is modeled as B/<b>2</b>, the position of the central point of convergence in each of WoV₁and WoV₂(the width of view of images 1 and 2, respectively) can be calculated. Within WoV₁, the central point of convergence will lie at a position

0176<maths id="MATH-US-00019" num="00019"><math overflow="scroll"><mrow><mrow><mi>C</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mn>1</mn></mrow><mo>=</mo><mrow><mfrac><mi>WoV</mi><mn>2</mn></mfrac><mo>+</mo><mrow><mfrac><mi>B</mi><mn>2</mn></mfrac><mo>.</mo></mrow></mrow></mrow></math></maths><br /> Conversely, within WoV₂, the central point of convergence will lie at a position

0177<maths id="MATH-US-00020" num="00020"><math overflow="scroll"><mrow><mrow><mi>C</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mn>2</mn></mrow><mo>=</mo><mrow><mfrac><mi>WoV</mi><mn>2</mn></mfrac><mo>-</mo><mrow><mfrac><mi>B</mi><mn>2</mn></mfrac><mo>.</mo></mrow></mrow></mrow></math></maths>

0178<figref idref="DRAWINGS">FIG. 26</figref> is a schematic diagram illustrating translational offset determination according to embodiments of the present disclosure. If X1 is the X-coordinate in the left image that corresponds to C<b>1</b>, X1 is calculated as

0179<maths id="MATH-US-00021" num="00021"><math overflow="scroll"><mrow><mrow><mrow><mi>X</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mn>1</mn></mrow><mo>=</mo><mrow><mfrac><msub><mi>P</mi><mi>w</mi></msub><mi>WoV</mi></mfrac><mo>*</mo><mi>C</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mn>1</mn></mrow></mrow><mo>,</mo></mrow></math></maths><br /> and X2 is the similar coordinate for the right image to be captured, calculated as

0180<maths id="MATH-US-00022" num="00022"><math overflow="scroll"><mrow><mrow><mrow><mi>X</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mn>2</mn></mrow><mo>=</mo><mrow><mfrac><msub><mi>P</mi><mi>w</mi></msub><mi>WoV</mi></mfrac><mo>*</mo><mi>C</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mn>2</mn></mrow></mrow><mo>,</mo></mrow></math></maths><br /> where P_wis the image width in pixels. Finally, S is calculated as

0181<maths id="MATH-US-00023" num="00023"><math overflow="scroll"><mrow><mi>S</mi><mo>=</mo><mrow><mrow><mrow><mi>X</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mn>1</mn></mrow><mo>-</mo><mrow><mi>X</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mn>2</mn></mrow></mrow><mo>=</mo><mrow><mrow><mfrac><msub><mi>P</mi><mi>W</mi></msub><mi>WoV</mi></mfrac><mo>*</mo><mi>B</mi></mrow><mo>=</mo><mrow><mfrac><mrow><mn>2</mn><mo>*</mo><msub><mi>P</mi><mi>w</mi></msub></mrow><mfrac><mi>W</mi><mi>F</mi></mfrac></mfrac><mo>*</mo><mi>sin</mi><mo>⁢</mo><mrow><mfrac><mi>θ</mi><mn>2</mn></mfrac><mo>.</mo></mrow></mrow></mrow></mrow></mrow></math></maths><br /> Since W, F, and P_Ware camera-specific quantities, the only specified quantity is the modeled convergence angle, θ, as noted typically 1-2 degrees. The value S may need to be scaled for use with a given display, due to the potentially different resolution of the display and the camera sensor.

0182<figref idref="DRAWINGS">FIG. 24</figref> illustrates an exemplary process of horizontal alignment assistance in accordance with embodiments of the present disclosure. For proper translation and vertical alignment, the guide region from this process should be aligned as precisely as possible. Referring to <figref idref="DRAWINGS">FIG. 24</figref>, objects <b>2400</b> and <b>2402</b> are within an interest point set (IP) (area of the image within the broken lines <b>2404</b>) in a captured left image <b>2406</b>. In the right image <b>2408</b> being shown in a live view on a camera display, the left image IP set <b>2404</b> is matched to the objects <b>2400</b> and <b>2402</b>. Also, in the live view of the right image <b>2408</b>, a desired right image IP set <b>2410</b> is displayed. The IP sets <b>2404</b> and <b>2410</b> serve as alignment guides. When the IP sets <b>2404</b> and <b>2410</b> are aligned exactly or sufficiently closely, the IP sets are suitably matched and the user knows that the subsequent image may be captured. <figref idref="DRAWINGS">FIG. 24</figref> presents an example of the guides. In general, the current and target positions can be represented in various graphic forms. The current position can be represented by any set of guides and the target location by a different set of guides. A guide can be any collection of pixels shown on the display <b>112</b>.

0183In the case where guides beyond displacement and vertical alignment are generated (assisting with perspective alignment, rotation prevention, and the prevention of camera toe-in), <figref idref="DRAWINGS">FIG. 25</figref> illustrates an example of Hough transform lines superimposed for stereo capture according to embodiments of the present disclosure. Three lines are superimposed on the live view or EVF window that are indicative of vertical alignment and perspective alignment, and three alternately colored lines are similarly superimposed at points on the live view or EVF window at the same distance, S, to the left (assuming left eye capture first) of where the IP region was captured in the first image. The guide region to be shown on the live view screen may be described by the following. Initially, the x-coordinate values of the left and right boundaries of the area defined by the interest point set of the captured left image (IP) are recorded as X_1land X_1r. The value S is calculated as described, and from this, the target offset coordinates for the right image capture are calculated as X_2land X_2r. Vertical lines may be superimposed at these coordinates in the live view screen as the “target lines,” or another guide mechanism, such as a transparent overlay, may be used. The second guide that is superimposed is the “alignment guide,” which represents the position of the left and right boundaries of the region of interest point set area as it is viewed in the live view window.

0184<figref idref="DRAWINGS">FIG. 27</figref> is another exemplary process of “alignment guide” determination according to embodiments of the present disclosure. Referring to <figref idref="DRAWINGS">FIG. 27</figref>, a position and shape of a first alignment guide <b>2714</b> and a second alignment guide <b>2716</b> may be calculated by the device based on key points found within the scene being viewed. The guides <b>2714</b> and <b>2716</b> may or may not have an obvious relationship to objects within the scene. When the camera moves, the key points and alignment guides <b>2714</b> and <b>2716</b> associated with those points move accordingly. The device displays the alignment guides <b>2714</b> and <b>2716</b> at the desired location and the user then moves the camera so the first (live-view) alignment guides <b>2714</b> align with the second (target) alignment guides <b>2716</b>.

0185In accordance with other embodiments of user alignment assistance, one or more windows <b>2718</b> may be displayed which contain different alignment guides <b>2720</b> to assist the user in moving the camera for capturing the second image. The windows <b>2718</b> may include live views of the scene and alignment guides <b>2720</b> that are calculated based on various objects <b>2722</b> in the image. A feature may also be available which allows the user to control the zoom factor of one or more windows <b>2724</b> in order to improve viewing of the enclosed objects <b>2726</b> and alignment guides <b>2728</b>, thus facilitating camera alignment in accordance with embodiments of the presently disclosed disclosure.

0186Note that although the convergent point at a distance D_sshould have zero parallax, the individual image captures do not capture the convergent center as the center of their image. To obtain the convergent view, registration of the image pair after capture must be performed.

0187Referring to <figref idref="DRAWINGS">FIG. 22</figref>, image generator function <b>114</b> determines whether a camera monitoring feature is activated (step <b>2214</b>). A user of the device <b>100</b> may select to activate the camera monitoring feature. If the camera monitoring feature is not activated, the user may input commands for capturing a second image with settings controlled by the camera to provide the same exposure as when the first image was captured (step <b>2216</b>). When the user is comfortable with the camera alignment, the second image can be captured automatically or the camera can stop capturing images when it is set in a continuous image capture mode. After capture, pairs of the captured images are combined to form a stereoscopic pair (or pairs) that is (are) suitable for three-dimensional registration and compression or rendering.

0188If the camera monitoring feature is activated, the device <b>100</b> may analyze the currently viewed image (step <b>2218</b>). For example, in this mode, the device <b>100</b> continues to monitor the capture window as the user moves the camera in different positions to capture the second/last picture. The device <b>100</b> analyzes the image and determines if an ideal location has been reached and the camera is aligned (step <b>2220</b>). If the ideal location has not been reached and the camera is not aligned, the device <b>100</b> may adjust directional feedback relative to its current camera position (step <b>2222</b>). If the ideal location has not been reached and the camera is not aligned, the second image may be captured automatically when the calculated binocular distance is reached as indicated by proper alignment of the region of interest with the current live view data, and any assistance lines, such as those generated by Hough transform (step <b>2224</b>).

0189Although the camera may be moved manually, a mechanism may automate the movement process. For example, <figref idref="DRAWINGS">FIG. 28</figref> is a schematic diagram of an exemplary camera-positioning mechanism <b>2800</b> for automating the camera-assisted image capture procedure according to embodiments of the present disclosure. Referring to <figref idref="DRAWINGS">FIG. 28</figref>, the mechanism <b>2800</b> may include a motorized mounting bracket <b>2802</b> which moves a camera <b>2804</b> as the camera <b>2804</b> calculates when in stereoscopic mode. The mounting bracket <b>2802</b> may connect to the camera <b>2804</b> via a suitable mount, such as, but not limited to a tripod-type mount. The bracket may rest on a tripod base <b>2808</b> or another type of base, such as a shoulder mount or handle, to be held by the user. The bracket may include a set of rails <b>2806</b> which allow the camera <b>2804</b> to move over it, but constrains the camera so that it can only move in a straight line in the horizontal direction (the direction indicated by direction arrow <b>2810</b>). The camera <b>2804</b> connects to the motor controller via a digital communication interface such as USB or any other external interface. The camera <b>2804</b> may use this connection to communicate feedback information about the movement needed for the second/last image to be captured. In addition, the motor controller may control a suitable mechanism for rotating the camera <b>2804</b> in a direction indicated by direction arrow <b>2812</b>.

0190<figref idref="DRAWINGS">FIG. 29</figref> illustrates an exemplary method of camera-assisted image capture using the automatic camera-positioning mechanism <b>1500</b> shown in <figref idref="DRAWINGS">FIG. 28</figref> according to embodiments of the present disclosure. Referring to <figref idref="DRAWINGS">FIG. 29</figref>, when the mechanism <b>2800</b> is to be used for the first time, the user may provide input to the camera <b>2804</b> for instructing the motor <b>2802</b> to move the camera <b>2804</b> to the “home” position (step <b>2900</b>). The home position may be the farthest point of one end of the rails <b>2806</b>, with the camera viewing angle perpendicular to the path of the rails <b>2806</b>. The user can then adjust the camera settings and the orientation of the bracket and take a first image (step <b>2902</b>). The settings used for capturing the first image (e.g., aperture and the like) may be stored for use in capturing subsequent images (step <b>2904</b>).

0191At step <b>2906</b>, the camera <b>2804</b> may use optics, focus, depth of field information, user parallax preference, and/or the like to determine position offset for the next image. For example, after the first image is captured, the camera <b>2804</b> may communicate feedback information about the movement needed for the second/last shot to the motor controller. The motor <b>2802</b> may then move the camera <b>2804</b> to a new location along the rails <b>2806</b> according to the specified distance (step <b>2908</b>). When the calculated camera position is reached, the last image may be captured automatically with settings to provide the same exposure as the first image (step <b>2910</b>). The camera <b>2804</b> may then be moved back to the home position (step <b>2912</b>). Any of the captured images may be used to form stereoscopic pairs used to create three-dimensional images. All of the calculations required to determine the required camera movement distance are the same as those above for manual movement, although the process simplifies since the mount removes the possibility of an incorrect perspective change (due to camera toe-in) that would otherwise have to be analyzed.

0192The subject matter disclosed herein may be implemented by a digital still camera, a video camera, a mobile phone, a smart phone, phone, tablet, notebook, laptop, personal computer, computer server, and the like. In order to provide additional context for various aspects of the disclosed subject matter, <figref idref="DRAWINGS">FIG. 30</figref> and the following discussion are intended to provide a brief, general description of a suitable operating environment <b>3000</b> in which various aspects of the disclosed subject matter may be implemented. While the presently disclosed subject matter is described in the general context of computer-executable instructions, such as program modules, executed by one or more computers or other devices, those skilled in the art will recognize that the disclosed subject matter can also be implemented in combination with other program modules and/or as a combination of hardware and software.

0193Generally, however, program modules include routines, programs, objects, components, data structures, etc. that perform particular tasks or implement particular data types. The operating environment <b>3000</b> is only one example of a suitable operating environment and is not intended to suggest any limitation as to the scope of use or functionality of the subject matter disclosed herein. Other well-known computer systems, environments, and/or configurations that may be suitable for use with the presently disclosed subject matter include but are not limited to, personal computers, hand-held or laptop devices, multiprocessor systems, microprocessor-based systems, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include the above systems or devices, and the like.

0194With reference to <figref idref="DRAWINGS">FIG. 30</figref>, an exemplary environment <b>3000</b> for implementing various aspects of the subject matter disclosed herein includes a computer <b>3002</b>. The computer <b>3002</b> includes a processing unit <b>3004</b>, a system memory <b>3006</b>, and a system bus <b>3008</b>. The system bus <b>3008</b> couples system components including, but not limited to, the system memory <b>3006</b> to the processing unit <b>3004</b>. The processing unit <b>3004</b> can be any of various available processors. Dual microprocessors and other multiprocessor architectures also can be employed as the processing unit <b>3004</b>.

0195The system bus <b>3008</b> can be any of several types of bus structure(s) including the memory bus or memory controller, a peripheral bus or external bus, and/or a local bus using any variety of available bus architectures including, but not limited to, 11-bit bus, Industrial Standard Architecture (ISA), Micro-Channel Architecture (MCA), Extended ISA (EISA), Intelligent Drive Electronics (IDE), VESA Local Bus (VLB), Peripheral Component Interconnect (PCI), Universal Serial Bus (USB), Advanced Graphics Port (AGP), Personal Computer Memory Card International Association bus (PCMCIA), and Small Computer Systems Interface (SCSI).

0196The system memory <b>3006</b> includes volatile memory <b>3010</b> and nonvolatile memory <b>3012</b>. The basic input/output system (BIOS), containing the basic routines to transfer information between elements within the computer <b>3002</b>, such as during start-up, is stored in nonvolatile memory <b>3012</b>. By way of illustration, and not limitation, nonvolatile memory <b>3012</b> can include read only memory (ROM), programmable ROM (PROM), electrically programmable ROM (EPROM), electrically erasable ROM (EEPROM), or flash memory. Volatile memory <b>3010</b> includes random access memory (RAM), which acts as external cache memory. By way of illustration and not limitation, RAM is available in many forms such as synchronous RAM (SRAM), dynamic RAM (DRAM), synchronous DRAM (SDRAM), double data rate SDRAM (DDR SDRAM), enhanced SDRAM (ESDRAM), Synchlink DRAM (SLDRAM), and direct Rambus RAM (DRRAM).

0197Computer <b>3002</b> also includes removable/nonremovable, volatile/nonvolatile computer storage media. <figref idref="DRAWINGS">FIG. 30</figref> illustrates, for example, disk storage <b>3014</b>. Disk storage <b>3014</b> includes, but is not limited to, devices like a magnetic disk drive, floppy disk drive, tape drive, Jaz drive, Zip drive, LS-100 drive, flash memory card, or memory stick. In addition, disk storage <b>1024</b> can include storage media separately or in combination with other storage media including, but not limited to, an optical disk drive such as a compact disk ROM device (CD-ROM), CD recordable drive (CD-R Drive), CD rewritable drive (CD-RW Drive) or a digital versatile disk ROM drive (DVD-ROM). To facilitate connection of the disk storage devices <b>3014</b> to the system bus <b>3008</b>, a removable or non-removable interface is typically used such as interface <b>3016</b>.

0198It is to be appreciated that <figref idref="DRAWINGS">FIG. 30</figref> describes software that acts as an intermediary between users and the basic computer resources described in suitable operating environment <b>3000</b>. Such software includes an operating system <b>3018</b>. Operating system <b>3018</b>, which can be stored on disk storage <b>3014</b>, acts to control and allocate resources of the computer system <b>3002</b>. System applications <b>3020</b> take advantage of the management of resources by operating system <b>3018</b> through program modules <b>3022</b> and program data <b>3024</b> stored either in system memory <b>3006</b> or on disk storage <b>3014</b>. It is to be appreciated that the subject matter disclosed herein can be implemented with various operating systems or combinations of operating systems.

0199A user enters commands or information into the computer <b>3002</b> through input device(s) <b>3026</b>. Input devices <b>3026</b> include, but are not limited to, a pointing device such as a mouse, trackball, stylus, touch pad, keyboard, microphone, joystick, game pad, satellite dish, scanner, TV tuner card, digital camera, digital video camera, web camera, and the like. These and other input devices connect to the processing unit <b>3004</b> through the system bus <b>3008</b> via interface port(s) <b>3028</b>. Interface port(s) <b>3028</b> include, for example, a serial port, a parallel port, a game port, and a universal serial bus (USB). Output device(s) <b>3030</b> use some of the same type of ports as input device(s) <b>3026</b>. Thus, for example, a USB port may be used to provide input to computer <b>3002</b> and to output information from computer <b>3002</b> to an output device <b>3030</b>. Output adapter <b>3032</b> is provided to illustrate that there are some output devices <b>3030</b> like monitors, speakers, and printers among other output devices <b>3030</b> that require special adapters. The output adapters <b>3032</b> include, by way of illustration and not limitation, video and sound cards that provide a means of connection between the output device <b>3030</b> and the system bus <b>3008</b>. It should be noted that other devices and/or systems of devices provide both input and output capabilities such as remote computer(s) <b>3034</b>.

0200Computer <b>3002</b> can operate in a networked environment using logical connections to one or more remote computers, such as remote computer(s) <b>3034</b>. The remote computer(s) <b>3034</b> can be a personal computer, a server, a router, a network PC, a workstation, a microprocessor based appliance, a peer device or other common network node and the like, and typically includes many or all of the elements described relative to computer <b>3002</b>. For purposes of brevity, only a memory storage device <b>3036</b> is illustrated with remote computer(s) <b>3034</b>. Remote computer(s) <b>3034</b> is logically connected to computer <b>3002</b> through a network interface <b>3038</b> and then physically connected via communication connection <b>3040</b>. Network interface <b>3038</b> encompasses communication networks such as local-area networks (LAN) and wide-area networks (WAN). LAN technologies include Fiber Distributed Data Interface (FDDI), Copper Distributed Data Interface (CDDI), Ethernet/IEEE 1102.3, Token Ring/IEEE 1102.5 and the like. WAN technologies include, but are not limited to, point-to-point links, circuit switching networks like Integrated Services Digital Networks (ISDN) and variations thereon, packet switching networks, and Digital Subscriber Lines (DSL).

0201Communication connection(s) <b>3040</b> refers to the hardware/software employed to connect the network interface <b>3038</b> to the bus <b>3008</b>. While communication connection <b>3040</b> is shown for illustrative clarity inside computer <b>3002</b>, it can also be external to computer <b>3002</b>. The hardware/software necessary for connection to the network interface <b>3038</b> includes, for exemplary purposes only, internal and external technologies such as, modems including regular telephone grade modems, cable modems and DSL modems, ISDN adapters, and Ethernet cards.

0202The various techniques described herein may be implemented with hardware or software or, where appropriate, with a combination of both. Thus, the methods and apparatus of the disclosed embodiments, or certain aspects or portions thereof, may take the form of program code (i.e., instructions) embodied in tangible media, such as floppy diskettes, CD-ROMs, hard drives, or any other machine-readable storage medium, wherein, when the program code is loaded into and executed by a machine, such as a computer, the machine becomes an apparatus for practicing the presently disclosed subject matter. In the case of program code execution on programmable computers, the computer will generally include a processor, a storage medium readable by the processor (including volatile and non-volatile memory and/or storage elements), at least one input device and at least one output device. One or more programs are preferably implemented in a high level procedural or object oriented programming language to communicate with a computer system. However, the program(s) can be implemented in assembly or machine language, if desired. In any case, the language may be a compiled or interpreted language, and combined with hardware implementations.

0203The described methods and apparatus may also be embodied in the form of program code that is transmitted over some transmission medium, such as over electrical wiring or cabling, through fiber optics, or via any other form of transmission, wherein, when the program code is received and loaded into and executed by a machine, such as an EPROM, a gate array, a programmable logic device (PLD), a client computer, a video recorder or the like, the machine becomes an apparatus for practicing the presently disclosed subject matter. When implemented on a general-purpose processor, the program code combines with the processor to provide a unique apparatus that operates to perform the processing of the presently disclosed subject matter.

0204While the embodiments have been described in connection with the preferred embodiments of the various figures, it is to be understood that other similar embodiments may be used or modifications and additions may be made to the described embodiment for performing the same function without deviating therefrom. Therefore, the disclosed embodiments should not be limited to any single embodiment, but rather should be construed in breadth and scope in accordance with the appended claims.