United States Patent (19)
`Meijers
`
`USOO5929859A
`Patent Number:
`11
`(45) Date of Patent:
`
`5,929,859
`Jul. 27, 1999
`
`54 PARALLACTIC DEPTH-DEPENDENT PIXEL
`SHIFTS
`
`75 Inventor: Patrick F. P. Meijers, Eindhoven,
`Netherlands
`
`73 Assignee: U.S. Philips Corporation, New York,
`N.Y.
`
`21 Appl. No.: 08/768,484
`22 Filed:
`Dec. 18, 1996
`30
`Foreign Application Priority Data
`Dec. 19, 1995 EP European Pat. Off. .............. 952O3553
`Jul. 1, 1996 EP European Pat. Off. .............. 962O1823
`(51) Int. Cl." ..................................................... G06T 17/00
`52 U.S. Cl. .............................................................. 345/419
`58 Field of Search ..................................... 345/418, 419,
`345/420, 421, 422, 423, 424, 433
`
`56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`1/1995 Komma et al. ......................... 395/119
`5,379,369
`5,502,798 3/1996 Ito et al. .......
`... 345/422
`5,537,520 7/1996 Doi et al...
`... 345/422
`5,542,025
`7/1996 Brown ..................................... 345/422
`
`5,671,157 9/1997 Saito ....................................... 345/419
`5,671,344 9/1997 Stark ....................................... 345/419
`OTHER PUBLICATIONS
`IEEE Computer graphics & Applications, Tutorial: Time
`Multiplexed Stereoscopic Computer Graphics, Mar., 1992.
`Primary Examiner Phu K. Nguyen
`ASSistant Examiner-Cliff N. Vo
`Attorney, Agent, or Firm-Gregory L. Thorne
`57
`ABSTRACT
`An output image is created through a parallactic transfor
`mation of an input image. Pixels of the input image are
`Supplied as a color value and a depth value. A depth
`converter 520 converts the depth value into a depth
`dependent pixel shift, which is stored in a memory 510
`together with the color value. A processor 530 generates the
`output image from the Stored input image for on the fly
`Supply to a Stereoscopic display System by Shifting the input
`pixels. A 3D-rendering proceSS may be used to generate one
`input image for a pair of Stereoscopic output images, or
`occasionally for moving images, whereas the depth
`dependent shifts are used to create the parallactic image
`effects. Artifacts Such as undesired holes or overlapS result
`ing from the shifts are avoided.
`
`17 Claims, 7 Drawing Sheets
`
`
`
`PXL
`
`IPR2018-01045
`Sony EX1007 Page 1
`
`

`

`U.S. Patent
`
`Jul. 27, 1999
`
`Sheet 1 of 7
`
`5,929,859
`
`
`
`IPR2018-01045
`Sony EX1007 Page 2
`
`

`

`U.S. Patent
`
`Jul. 27, 1999
`
`Sheet 2 of 7
`
`5,929,859
`
`
`
`IPR2018-01045
`Sony EX1007 Page 3
`
`

`

`U.S. Patent
`
`Jul. 27, 1999
`
`Sheet 3 of 7
`
`5,929,859
`
`
`
`FIG. 3B
`
`IPR2018-01045
`Sony EX1007 Page 4
`
`

`

`U.S. Patent
`
`Jul. 27, 1999
`
`Sheet 4 of 7
`
`5,929,859
`
`
`
`FIG. 4B
`
`IPR2018-01045
`Sony EX1007 Page 5
`
`

`

`U.S. Patent
`
`Jul. 27, 1999
`
`Sheet 5 of 7
`
`5,929,859
`
`
`
`DE-COMP
`
`FIG.5
`
`IPR2018-01045
`Sony EX1007 Page 6
`
`

`

`U.S. Patent
`
`Jul. 27, 1999
`
`Sheet 6 of 7
`
`5,929,859
`
`
`
`
`
`al al
`
`IPR2018-01045
`Sony EX1007 Page 7
`
`

`

`U.S. Patent
`
`Jul. 27, 1999
`
`Sheet 7 of 7
`
`5,929,859
`
`
`
`
`
`ah anNYBs
`
`
`
`
`
`
`IPR2018-01045
`Sony EX1007 Page 8
`
`IPR2018-01045
`Sony EX1007 Page 8
`
`

`

`1
`PARALLACTIC DEPTH-DEPENDENT PXEL
`SHIFTS
`
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`The invention relates to an image processing System for
`generating at least one output image related to an input
`image through a parallactic transformation; the image pro
`cessing System comprising input means, output means, a
`memory and a processor; the input means comprising means
`for receiving a respective input pixel value and input pixel
`depth of input pixels of the input image and for Storing
`received input pixel values in the memory; the processor
`being operative to create output pixels of the output image
`by deriving for the output pixel a respective output pixel
`value from the input pixel value of at least one input pixel,
`which is parallactically related to the output pixel; the
`parallactic relationship being a function of the respective
`input pixel depth; the output means comprising means for
`outputting the output pixel values.
`The invention further relates to a processor for parallac
`tically transforming an input image into at least one output
`image; the processor comprising an input for receiving a
`respective input pixel value of input pixels of the input
`image and an output for Outputting a respective output pixel
`value for output pixels of the output image; the processor
`being operative to create the output pixel by deriving a
`respective output pixel value from the input pixel value of at
`least one input pixel, which is parallactically related to the
`output pixel.
`2. Description of Related Art
`The interest in providing a depth sensation when display
`ing an image on a 2D display is growing rapidly, notably in
`Virtual reality applications and computer games. Various
`forms of providing depth cues, Such as influencing the
`brightneSS level or the Size of an object, are known.
`Particularly, Stereopsis, or Stereoscopic Vision, receives
`much attention as a technique for providing depth Sensation.
`Stereopsis is evoked by presenting to a person two 2D
`images of the same Scene as observed from two positions a
`little way apart. One of the images is presented to the left
`eye, the other one is presented to the right eye. The two
`images are parallactically related. The term "parallax” refers
`to the apparent displacement or the difference in apparent
`direction of an object as Seen from two different points not
`on a Straight line with the object. Parallax allows a person to
`perceive the depth of objects in a Scenery.
`It is known from U.S. Pat. No. 5,379,369 to generate from
`one 2D input image Separate output images for each of the
`eyes. In the known System, the 2D input image represents
`objects observed from a point corresponding to a middle
`point in between both eyes. The left eye image is a 2D
`representation of the objects observed from a point corre
`sponding to the Visual point of the left eye. The right eye
`image is a 2D representation of the objects observed from a
`point corresponding to the Visual point of the right eye.
`Typically, the 2D input image is given in the form of an array
`of pixels. It may, for instance, have been obtained using a
`camera or computer graphics. For each of the pixels of the
`input image additional depth information is available. In the
`known system, depth information is derived from the 2D
`input image itself, for instance based on brightness levels of
`pixels of the 2D input image. Based on the parallax when
`observing the same object from the visual point of the eyes
`and from the middle point in between the eyes, the pixels of
`the left eye image and the right eye image are derived from
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,929,859
`
`2
`the pixels of the input image by shifting the pixels. By
`choosing the horizontal axis of the co-ordinate System as
`being parallel to the line connecting both eyes, only a
`horizontal shift occurs. The amount of shift of a pixel
`depends on the depth information. Typically, a graphical
`processing System Suitable for generating parallactically
`related images from an input image comprises a memory,
`Such as a graphics memory, for Storing the 2D input image
`with the additional depth information. The 2D input image
`and the depth information are usually Supplied by an appli
`cation program. Typically, a copy of the 2D input image and
`the depth information is also stored in a memory for use by
`an image processing System. The image processing System
`generates one or more 2D output images from the 2D input
`image and the depth information. The output images are
`parallactically related to the input image. The generation is
`achieved by performing a depth dependent shift of the pixels
`of the 2D input image. The 2D output images are Stored in
`a graphics memory. Using a D/A converter the 2D output
`images are displayed using a Suitable Stereoscopic display
`System. Many display techniques for displaying Stereoscopic
`images are known. Using a time-parallel technique, both
`output images are presented Simultaneously to one or two
`displayS. For example, both images may be filtered with
`complementary colours and Superimposed on one display.
`The observer wears glasses with filters that match the
`projection filters. Alternatively, both images may be dis
`played alongside on one display and viewed using a viewer
`which directs each image to the correct eye. AS another
`example, two displayS may be used to present two differ
`ently polarised pictures, which are viewed through corre
`spondingly polarised glasses. Alternatively, both images
`may be presented using a head-mounted device with sepa
`rate displays for each eye. Also time-multiplexed techniques
`may be used, where the left and right images are alternat
`ingly displayed on one display. AS an example, one image is
`written to the even Scan lines of a monitor and the other
`image to the odd Scan lines. A shutter System is used to
`occlude the left eye when the right-eye image is displayed
`and to occlude the right eye when the left-eye image is
`displayed. The Shutter System may be mounted in glasses
`worn by the observer. Alternatively, a shutter with a con
`trollable polariser is placed in front of the display and the
`observer wears a head-mounted device with polarised
`glasses.
`The known image processing System is relatively costly
`for use in consumer products, Such as game computers and
`PCs. Moreover, only moderate quality can be achieved.
`
`OBJECTS AND SUMMARY OF THE
`INVENTION
`It is an object of the invention to provide a fast and
`cost-effective system of the kind set forth, which enables the
`generation of parallactically related images of a high quality.
`To achieve this object, the System according to the inven
`tion is characterised in that the input means comprises a
`depth converter for converting the input pixel depth into an
`input pixel shift and for Storing a representation of the input
`pixel shift in the memory; and in that the processor is
`conceived to determine the parallactic relationship between
`an output pixel and an input pixel based on the Stored input
`pixel Shift representation corresponding to the input pixel.
`The pixel shift range is typically less than the pixel depth
`range. By Storing the pixel shift, instead of the pixel depth,
`the Storage requirements may be reduced. Additionally or
`alternatively, the pixel depth range may be increased allow
`
`IPR2018-01045
`Sony EX1007 Page 9
`
`

`

`3
`ing for a more discriminative shifting of pixels while the
`Storage requirements do not increase. As an example, for a
`System using a 16-bit pixel depth it may be Sufficient to Store
`only 4 to 6 bits of pixel shift information. Furthermore, the
`pre-processing performed by the depth converter reduces the
`load on the processor, allowing a cost-effective processor to
`be used for deriving the output image on the fly from the
`input image. Preferably, the depth converter converts and
`Stores a plurality of Successive pixels before the processor
`processes the pixels. Advantageously, Such plurality
`includes all pixels of the image, all pixels of a line of the
`image or an amount of pixels corresponding to a maximum
`pixel shift (e.g. if a pixel can be shifted over a maximum of
`16 pixel positions, at least 16 pixels are processed by the
`depth converter, before being processed by the processor).
`An embodiment of the System, according to the invention
`wherein the pixel Shift is limited to a predetermined maxi
`mum of N pixel positions, is characterised in that the
`processor comprises a sliding buffer with at least N locations
`for Storing pixel values and in that the processor is operative
`to proceSS Successive input pixels; Said processing compris
`ing:
`copying the respective input pixel value from the memory
`into the sliding buffer at a location with an offset depending
`on the corresponding input pixel shift,
`outputting an output pixel value by reading a pixel value
`from an output location in the sliding buffer, and
`shifting the sliding buffer.
`The pixels of the output image are created using only a Small
`Sliding buffer without requiring to Store the output image.
`This also simplifies the operation of the processor, contrib
`uting to a fast and cost-effective implementation of the
`processor.
`An embodiment of the system, according to the invention
`wherein the processor is operative to, if a foreground and a
`background input pixel are parallactically related to a same
`output pixel, Select the foreground input pixel for further
`processing, is characterised in that the processor comprises
`an indicator for indicating whether the Sliding buffer loca
`tions are occupied; in that the processor is operative to
`perform the Selection by only copying an input pixel value
`into a location of the sliding buffer if the indicator indicates
`that the location is not occupied.
`An input pixel may be shifted in either direction, depend
`ing on whether the object represented by the pixel is located
`in front or behind the focus plane. Moreover, the amount of
`pixel positions being shifted depends on the depth of the
`object. Consequently, more than one input pixel may be
`shifted to the same output pixel. This can be visualised by
`considering that from an observation point matching the
`input image certain objects at different depths may not
`overlap (or overlap only partially), whereas from the obser
`Vation point matching the output image the objects do
`overlap (or overlap more). In the known System, each time
`an input pixel is shifted to an output pixel location, to which
`already another input pixel has been copied, the correspond
`ing depth information of both input pixels involved is used
`to ensure that the foreground input pixel is Selected. The
`insight of the inventor is that by using a buffer with the
`indicator, the desired input pixel can be Selected by merely
`checking whether the buffer location of the output pixel is
`already occupied. No depth information is required any
`OC.
`An embodiment of the System, according to the invention
`wherein the processor is operative to, if a foreground and a
`background input pixel are parallactically related to a same
`output pixel, Select the foreground input pixel for further
`processing, is characterised:
`
`1O
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`5,929,859
`
`4
`in that the processor comprises an indicator for indicating
`whether the sliding buffer locations are occupied;
`in that the processor is conceived to process input pixels
`of a row of the input image in a given processing direction;
`in that the processor comprises a Selector for Selectively
`copying an input pixel value into a location of the sliding
`buffer, in dependence of a relative position of an output
`observation point matching the output image compared to an
`input observation point matching the input image; the Selec
`tor being operative to:
`if the direction from the input observation point to the
`output observation point is the Same as the processing
`direction, copy the input pixel value irrespective of the
`location being occupied, and
`if the direction from the input observation point to the
`output observation point is opposite to the processing
`direction, copy the input pixel value if the indicator indicates
`that the location is not occupied. The insight of the inventor
`is that, if the direction from the input observation point to the
`output observation point is the Same as the processing
`direction, then automatically the foreground input pixel is
`Selected. If both directions are opposite, then the desired
`input pixel can be Selected by merely checking whether the
`buffer location of the output pixel is already occupied. The
`Selector allows the processor to effectively Select the appro
`priate input pixel in dependence of the relative position of
`the input and output observation points.
`An embodiment of the System, according to the invention
`wherein the processor comprises a duplicator for, if none of
`the input pixels is parallactically related to a given output
`pixel, creating a respective output pixel value of the output
`pixel by reproducing an input pixel value, is characterised in
`that the proceSSor comprises an indicator for indicating
`whether the Sliding buffer locations are occupied; and in that
`the duplicator is operative to reproduce a pixel value which
`was output previously from the sliding buffer if the indicator
`indicates that the predetermined output location of the
`Sliding buffer is not occupied.
`In contrast to input pixels being shifted to the same output
`pixel, it may also occur that no input pixel is shifted to a
`certain output pixel location. This can be visualised by
`considering that, from an observation point matching the
`input image, objects at different depths may partially
`overlap, whereas from the observation point matching the
`output image the objects overlap less (a larger Section of a
`partially obscured background object is visible). The holes
`which may occur in this way, are filled by duplicating the
`previously output pixel. Preferably, the direction from the
`output observation point to the input observation point is the
`Same as the processing direction. In this way, typically, a
`background input pixel is reproduced, representing the
`emerged part of the background object.
`An embodiment of the System, according to the invention
`is characterised in that the input pixel Shift comprises a
`Sub-pixel shift indicative of a shift of the corresponding
`input pixel to a position in between pixel positions of the
`output image; and in that the processor comprises a mixer
`for blending pixel values of neighbouring pixels, where
`weighting factors of the blending depend on the Sub-pixel
`shift of the neighbouring pixels. By using the Sub-pixel shift
`for blending neighbouring pixels, a high quality output can
`be achieved wherein no clearly noticeable depth-related
`jumps in Shift occur, which would otherwise have given the
`impression of a Series of shifted, parallel planes.
`An embodiment of the System, according to the invention
`is characterised in that the depth converter comprises a table
`for converting the input pixel depth into the input pixel shift.
`
`IPR2018-01045
`Sony EX1007 Page 10
`
`

`

`5,929,859
`
`15
`
`25
`
`35
`
`40
`
`S
`Using a table is an effective way of transforming the pixel
`depth, which may, for instance, be represented using 16 bits,
`into the pixel shift, which may, for instance, be four to Six
`bits.
`An embodiment of the System, according to the invention
`is characterised in that the depth converter comprises com
`pression means for compressing the input pixel shift of at
`least one input pixel into the input pixel shift representation,
`and in that the processor comprises decompression means
`for decompressing the input pixel Shift representation into
`the input pixel shift of the corresponding input pixel(s). By
`compressing the pixel Shifts the Storage requirements are
`reduced even further.
`An embodiment of the System, according to the invention
`wherein the processor is operative to generate at least two
`output images, which are related to the same input image
`through a parallactic transformation, is characterised in that
`the input image constitutes one of the output images. By
`presenting one of the output images as the input image, one
`leSS image needs to be generated. For conventional Stereo
`Vision with two output images, derived from one input
`image, either the left or right image may be presented to the
`System as the input image. The other output image is derived
`from the input image through the parallactic translation.
`An embodiment of the System, according to the invention
`wherein the processor is operative to generate at least two
`output imageS which are related to the same input image
`through a parallactic transformation, is characterised in that
`an input observation point matching the input image is not
`horizontally in between output observation points matching
`each of the output images.
`In this way the same processing can be used to derive each
`output image from the input image.
`An embodiment of the system, according to the invention
`is characterised in that the direction from the input obser
`Vation point to the output observation point is opposite to the
`direction in which the processor processes the input pixels of
`a row of the input image. In this way the processing is
`Simplified.
`An embodiment of the System, according to the invention
`wherein the System comprises a display System for display
`ing the output image on a display, is characterised in that the
`processor is directly connected to the display System for
`Supplying the output pixels. This avoids the use of additional
`graphics memory for Storing the output from the processor.
`To achieve the object of the invention, the processor is
`characterised:
`in that the processor comprises an input for receiving a
`representation of a respective input pixel shift of the input
`pixel; the input pixel shift being limited to a predetermined
`maximum of N pixel positions,
`in that the processor comprises a sliding buffer with at
`least N locations for Storing pixel values, and
`in that the processor is operative to process Successive
`input pixels; Said processing comprising:
`copying the respective input pixel value from the memory
`into the sliding buffer at a location with an offset depending
`on the corresponding input pixel shift,
`outputting an output pixel value by reading a pixel value
`from an output location in the sliding buffer, and
`shifting the sliding buffer.
`BRIEF DESCRIPTION OF THE DRAWINGS
`These and other aspects of the invention will be apparent
`from and elucidated with reference to the embodiments
`shown in the drawings.
`FIG. 1 shows a block diagram of a conventional System
`incorporating an image processing System,
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`FIGS. 2A-2C show a perspective projection,
`FIGS. 3A-3B illustrate increased overlapping of objects
`when observed from a different position,
`FIGS. 4A-4B illustrate the appearance of a hole when
`objects are observed from a different position,
`FIG. 5 shows a block diagram of an image processing
`System according to the invention,
`FIG. 6 illustrates an embodiment of the image processing
`System according to the invention,
`FIG. 7A-7B illustrate relative shifts of objects, and
`FIG. 8 illustrates shifts to sub-pixel locations.
`DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`FIG. 1 shows a block diagram of a conventional System
`in which the image processing System according to the
`invention may advantageously be used. The conventional
`System comprises a memory 100, Such as a graphics
`memory, for Storing a 2D input image 110. The input image
`110 is comprised of an array of pixels divided in rows and
`columns. For each pixel a pixel value is given. Various ways
`of representing a pixel value are well known, Such as an
`RGB (Red, Green, Blue) or YUV coding. The pixel value
`may be Stored in full, e.g. using 16 or 24 bits per pixel.
`Alternatively, a Colour Look-Up Table (CLUT) scheme may
`be used to code the pixel value usingleSS bits, e.g. 8 bits. In
`addition to the pixel value, for each pixel a depth value is
`stored in the memory 100 as the input depth 120. The depth
`value may, for instance, be stored using 16 bits per pixel. If
`required, a separate memory may be used for Storing the
`input depth 120. On a game computer or personal computer
`the input image 110 and the input depth 120 are usually
`generated by a 3D-rendering process 130 which derives the
`information from a 3D model 140 stored in a memory 150.
`Typically, the memory 150 is part of the main memory of the
`computer. The memory 150 may be formed by any suitable
`Storage means, Such as RAM, ROM, magnetic or optical
`background Storage. The 3D-rendering process 130 is typi
`cally executed using the main CPU of the computer or by
`means of a graphics processor or accelerator. It will be
`appreciated that the input image 110 and the input depth 120
`may also be Supplied or generated in other ways. AS an
`example, communication means, Such a telecommunication
`means, audio/video broadcasting or a cable network, may be
`used to supply the input image 110 and the input depth 120.
`As an alternative to the 3D-rendering process 130, other
`means may be used to generate an image and depth infor
`mation. As an example, two cameras located at different
`positions may be used, preferably each representing a dif
`ferent eye. From the two 2D-images obtained by the
`cameras, one image plus depth information can be formed.
`The depth information can then be Supplied in addition to
`and, preferably, compatible with the conventional Supply of
`only one 2D image, allowing the Scene to be observed using
`either a conventional 2D display System or a Stereoscopic
`display System.
`A processor 160 uses the input image 110 and the input
`depth 120 to generate at least one output image. In the
`example shown in FIG. 1, a left image 170 and a right image
`180 are generated. The left image 170 represents a 2D
`representation of the 3D scene as observed from an obser
`Vation point coinciding with the left eye of an observer.
`Similarly, the right image 180 represents a 2D representation
`of the 3D scene as observed from an observation point
`coinciding with the right eye of an observer. Typically, the
`processor 160 builds the output images in a memory 190,
`
`IPR2018-01045
`Sony EX1007 Page 11
`
`

`

`5,929,859
`
`7
`such as a graphics memory. Usually a D/A converter 200
`presents the output images on a Suitable display 210, Such as
`a Stereoscopic display. In order to allow the processor 160 to
`operate on the input image and input depth without being
`time-synchronised at pixel level to the Supply of this
`information, typically a memory 210 is used for Storing an
`input image 220 and input depth 230, being a respective
`copy of the input image 110 and input depth 120. The
`processor 160 then operates on the input image 220 and
`input depth 230, independent from the 3D-rendering process
`130 supplying the input image 110 and input depth 120. At
`Suitable moments, e.g. when a complete new image has been
`created, the input image 110 and the input depth 120 are
`copied to the respective input image 220 and input depth
`230. In a situation where the memory 100 and the memory
`210 are physically combined in one memory block, the
`copying may be performed without physically copying the
`data, for instance by reassigning pointer registers.
`The parallactic transformation of the input image into the
`output image is associated with displacements of 3D objects
`relative to each other. The displacements occur as a conse
`quence of, e.g., a change in the location of the observer
`relative to the Scene, a change in the orientation of the
`observer relative to the Scene, changing positions of the
`objects relative to each other due to their relative Velocities,
`or a combination of these changes.
`FIG. 2A shows a perspective projection. Shown is a
`3D-co-ordinate system with an X-axis 200, y-axis 210 and a
`Z-axis 220. A 2D image is comprised of an array of discrete
`pixels arranged in rows and columns. Pixels in this context
`are the Smallest entities considered by the image processing
`according to the invention. Each respective pixel of a
`Specific row in the image can assume only a respective one
`of a Series of discrete positions. Each row of pixels in an
`image runs parallel to the x-axis 200, so that individual
`pixels in a row are discriminated on the basis of their
`respective X-coordinates. Each column of pixels runs paral
`lel to the y-axis 210 that points in a direction perpendicular
`to the x-axis 200. The depth of the scene is measured along
`the Z-axis 220, which runs perpendicular to both the x-axis
`200 and the y-axis 210. A respective Z-value is assigned to
`each particular pixel in order to represent the depth of the
`Scenery for that particular pixel. For explaining the paral
`lactic shifting of pixels, the origin O=(0, 0, 0) and the
`orientation of the co-ordinate System are chosen Such that a
`3D-object, represented by the point P=(x, y, z) is observed
`from the observation point O =(D, 0, 0). The plane z=z, is
`chosen to be the focus plane 240 (the plane on which the
`eyes of the observer focus). Usually, the plane of the display
`is chosen to coincide with the focus plane. The 2D image
`observed from the observation point O is formed by a
`projection of the 3D objects on the focus plane, which is also
`referred to as the projection plane. The point P is projected
`onto P=(x, y, z).
`FIG. 2B shows a projection of FIG. 2A onto the plane
`y=0. P is projected onto P'=(x, 0, z); P"=(D, 0, Z). From the
`triangle O, P, P" it follows that: Z/Z=(x-D)/(x-D), giving
`x=D+(x-D).Z/Z.
`FIG. 2C shows a projection of FIG. 2A onto the plane
`x=D. P is projected onto P'=(D, y, z); P"=(D, 0, Z). From the
`triangle O, P, P" it follows that: Z/Z=y/y, giving y=y.Z/Z.
`This gives that P=(D+(x-D).Z/Z, y.Z/Z, Z). Similarly,
`P=(-D+(x+D).ZZ, y.Z/Z, Z). Similar formulas are given in
`IEEE Computer graphics & Applications, Tutorial: Time
`Multiplexed Stereoscopic Computer Graphics, March
`1992). From the formulas, it follows that by choosing the
`
`5
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`X-axis to be parallel to the line through the observation
`points, they coordinates of P and P are the same. So, when
`deriving an image observed from O2 from the image
`observed from O, no vertical parallax occurs. In general, by
`choosing the X-axis in this way the calculation of the
`parallax is simplified. The pixels of the output image can be
`derived from the input image. ASSuming that the input image
`corresponds with the image as observed from O and the
`output image corresponds with the image as observed from
`O. ASSuming further that for input pixel p=(x, y) the pixel
`value is given, as well as the depth Z, of the 3D point P(x,
`y, z) from which p is derived. The corresponding output
`pixel p=(x, y), with y=y is related to the same 3D point
`P(x, y, z). This gives:
`
`This implies that X can be derived from X, in the following
`way: X=x-2D+2D.Z/Z-X,+2D(Z/Z-1).
`The output image can, therefore, be derived from the input
`image by performing a horizontal shift d (only in the
`X-direction) of:
`(1).
`d=2D(2/2-1).
`From this formula it can be observed that the shift is
`proportional to the inverse of the depth. In the formula, 2D
`corresponds to the offset between the observation points O,
`and O. This also corresponds to the parallax in the furthest
`allowed point (Z=OO). Usually, the maximum parallax is
`restricted to being less than the offset between the observa
`tion points. This can be achieved by choosing a Smaller
`value for 2D. For a conventional 17" display good results
`have been achieved by choosing 2D to be 8 pixels. It should
`be noted that since the eyes converge in the plane of Z. no
`parallax occurs for objects in this plane. Objects with the
`maximum allowed depth have a shift of 2D. Objects with a
`depth of 2.Z, have a shift of -2D (in a direction opposite to
`the parallax of the objects with maximum depth). Preferably,
`the minimum depth is restricted to %.Z., resulting in the
`maximum shift in either direction being the same. The depth
`Z may be represented in various ways. For instance, a 16-bit
`encoding on a linear Scale may be used, where the depth of
`an object with minimum allowed depth is encoded as 0000H
`(hexadecimal) and the depth of an object with maximum
`allowed depth is encoded as FFFFH. Persons skilled in the
`art will be able to Select appropriate other representations, if
`So desired.
`AS described above, the absolute direction of a shift is
`influenced by an object being in front or behind the focus
`plane. It should also be noted that the absolute direction of
`the shift is also determined by the relative horizontal posi
`tions of the observation points of the images. In the example
`given above, the observation point O of the output image is
`to the left of the observation point O of the input image. If
`the observation points are Swapped, the shift is in opposite
`direction (replacing D by -D in the formulas). In Such a
`case, objects with the maximum allowed depth have a shift
`of -2D and objects with a depth of 2.z, have a shift of 2D.
`By choosing 2D to correspond to 8 pixels, an 8-pixel shift
`can occur in either horizontal direction. AS Such, 4 bits are
`required for Storing the shift.
`FIG. 3A shows a scene observed fr