United States Patent [19]
`Gullichsen et al.
`
`11111111~~~ 111111111111111111111111111111111111~111111~ 111111111111
`5,796,426
`Aug. 18, 1998
`
`US005796426A
`[11] Patent Number:
`[451 Date of Patent:
`
`[54) WIDE-ANGLE IMAGE DEWARPING
`METHOD AND APPARATUS
`
`[75]
`
`Inventors: Eric GnUichsen: Susan Wyshynski.
`both of Sausalito. Calif.
`
`OTHER PUBLICATIONS
`
`"Image Distorsion from Zoom Lenses: modeling and digital
`correction", by Rebiai et al. me 1992. p.: 438-441. lEE
`London. UK. Jul. 1992.
`
`[73] Assignee: Warp, Ltd.
`
`[21] Appl. No.: 250,594
`
`May 27, 1994
`
`[51]
`[52)
`[58]
`
`[22] Filed:
`Int. Cl.6
`..................................................... H04N 5/225
`U.S. Cl ............................ 348/207; 348/147: 382/293
`Field or Search ..................................... 348/207. 335,
`348/36. 25. 20. 143. 147; 359/618. 623;
`382/293. 294. 300. 285: 395/127. 125.
`130. 136; H04N 5/225
`
`[56]
`
`References Cited
`
`U.S. PxrENT DOCUMENTS
`6/1988 Hadley ...................................... 382/44
`6/1988 Kishi et al .............................. 395/127
`9/1988 Tuck ......................................... 358/87
`6/1991 McCutchen ............................. 358/231
`9/1991 Tararine et al ......................... 382/300
`1111991 Juday et al ............................. 358/160
`12/1992 Blackham et al ......................... 382/44
`12/1992 Sayre ...................................... 195/133
`2/1993 Zimmennann .......................... 348/207
`111995 Martin et al ............................ 348/207
`6/1995 Yamada ................................... 395/127
`
`4,751,660
`4,754,269
`4.772,942
`5.023,725
`5,048,102
`5,067.019
`5,173,948
`5,175,808
`5,185,667
`5,384,588
`5,422,987
`
`Primary Examiner-Andrew Faile
`Assistant Examiner-Than V. Ho
`Attome}~ Agent, or Firm-James E. Eakin
`
`[57]
`
`ABSTRACT
`
`A method and apparatus for transforming wide angle video
`into perspective corrected viewing zones which either a
`single user or multiple users may select. orient and magnify.
`The present invention first captures a wide angle digital
`video input by any suitable means. The captured image is
`then stored in a suitable memory means so portions of the
`image may be selected at a later time. When a portion of the
`stored video is selected for viewing. a plurality of discrete
`viewing vectors in three dimensional space are chosen on
`the video input and transformed to a plurality of control
`points in a two dimensional plane or any other suitable
`surface. The area between these points which is still warped
`from the original wide angle image capture is then trans(cid:173)
`formed to a perspective corrected field of view. The per(cid:173)
`spective corrected field of view is then displayed on a
`suitable displaying apparatus, such as a monitor or head
`mounted display.
`
`16 Claims, 9 Drawing Sheets
`
`Real
`\.torld
`22
`
`10
`
`20
`
`24
`
`\ , Fro.Me
`
`30
`v
`
`40
`
`v
`
`/Grabber
`
`\
`/ MeMory
`
`CPU
`
`/
`
`"
`"so
`
`Input
`Port
`
`/"-
`
`1-100
`
`90~ Input
`Device
`
`L_D
`
`Texture
`)'w'arp
`
`/70
`
`Video
`Output
`
`150
`
`ASIC ~
`'
`
`'.k'_
`
`Display v
`
`80
`
`

`

`Figure 1
`
`24
`
`Cj
`00 •
`~ ~
`~ = ~
`
`Reo.t
`'w'orld
`22
`
`10
`
`\
`f
`
`I
`1
`
`20
`
`\
`
`--"'
`
`/
`
`30
`
`/
`
`FroMe
`Grubber
`
`) MeMory
`
`40
`
`------
`
`Lo
`Texture
`' 'w'urp
`/ ASIC
`
`150
`
`CPU
`
`/. -
`v
`r"
`
`"'50
`
`Input
`Port
`
`/ 1"-
`
`r----.100
`
`90'----
`
`Input
`Device
`
`' / /70
`
`Video
`Output
`
`' ]/
`Displu.y v
`
`iC oe
`
`> = ~ -!?J -iC
`~ a -0
`"""= ""
`
`~
`
`til
`~
`
`\C "" ~
`N ""
`
`

`

`U.S. Patent
`
`Aug. 18, 1998
`
`Sheet 2 of 9
`
`5,796,426
`
`0
`..........
`ru
`
`X
`
`(l)
`c
`c:S
`o_
`
`(l)
`CJ)
`0
`£:
`.__...
`
`0
`(l)
`0..
`<..._
`0
`:3
`
`(\J
`
`(l)
`<..._
`::3
`(J)
`L
`
`0
`(\J
`
`>,
`
`N
`
`C)
`C)
`(\J
`
`(l)
`0
`::3
`lfl c
`())
`OJ
`E_j
`OJ OJ
`<..._~
`-t->0)
`X c
`W<:r::
`
`

`

`U.S. Patent
`
`Aug. 18, 1998
`
`Sheet 3 of 9
`
`5,796,426
`
`Figure 3A
`
`Bilineo.r Mo.p
`
`Recto.ngle
`
`Arbitro.ry
`Qund
`
`Figure 3B
`
`BiQuo.dro. tic
`Mo.p
`
`Recto.ngle
`
`Edges nre Po.ro.bolic,
`Ench Defined by 0
`Qundro. tic Equo. tion.
`
`

`

`U.S. Patent
`
`Aug. 18, 1998
`
`Sheet 4 of 9
`
`5,796,426
`
`c
`Q;
`Q;
`lfl
`
`OJ
`u c
`d 0
`Q_
`lfl ~
`>(::')
`:::s Q;
`
`I
`
`:::5
`
`I
`
`"<t
`
`Q;
`~
`:::5
`(])
`
`~
`
`>
`
`I - -
`>~
`
`(lJ
`(::5
`:3 lfl
`c
`Q; OJ
`E_i
`OJ OJ
`~~
`+-'
`(])
`X c
`W<[
`
`~
`0
`+-'
`u
`Q;
`>
`(])
`c
`3:
`OJ
`>
`N
`>..
`X
`
`CD
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 18, 1998
`Aug. 13, 1998
`
`Sheet 5 0f 9
`Sheet 5 of 9
`
`5,796,426
`5,796,426
`
`~
`0
`+>
`u
`(l)
`>
`CJ)
`c
`3::
`(l)
`
`>
`
`
`
`gowum>9:35\CGECQNirax
`
`
`
`>,
`~
`0
`£
`~
`Q_
`
`N
`I
`>-
`I
`X
`
`0
`u
`+>
`r....
`OJ
`>
`?i
`OJ
`>
`4-
`0 >
`I
`(J >
`OJ 0
`4-
`4-
`
`EUPLm;£63m0EEC
`
`n>|>omv
`
`+>
`c
`0
`Q_
`3::
`OJ
`>
`
`PEOQ39>
`
`~ rr
`é?
`
`Buncomiog1/?,3
`
`0
`+>
`3:: c
`,.......,
`(l) 0
`.£
`-- N
`I
`('5 > -- >
`~ ~ 0
`-~<+-04-
`4-0..£
`
`Asu>O¢V
`
`m930C
`
`GOOGLE EXHIBIT 1010, Page 6 of 16
`
`
`

`

`t;ons
`Ins true
`
`l
`Contra
`Pixel
`Coordin
`1tes
`
`"-.!
`
`1 260
`,1
`
`Forwnrd
`" Mopping
`/ Solution
`240
`
`Control
`
`Oij
`bij
`Coefficients
`
`"
`
`/
`
`230
`
`I
`~
`
`!Ant~ I
`~Llins;ng _j
`290
`
`Interpolo. t;on
`So.Mpler
`
`~-~
`Source
`-----jj Prefilter ~
`Pixels
`(Unwo.rp
`270
`ed)
`L _ _j
`
`"
`
`/
`
`250
`
`Destino tion
`Pixel
`Coordino. tes
`
`Figure 6
`Ho.rdwo.re Texturing Engine
`
`Destinn tion
`Pixels
`(IJorped)
`
`Video
`FroMe
`Buffer
`
`280
`
`"
`
`/
`
`"
`
`/
`
`~ • 00. .
`~ = ~
`~ = ~
`
`;...
`= ~
`.....
`~
`.....
`~
`00
`
`r.J':J =(cid:173)
`
`l'!)
`
`l'!) -="
`
`~
`\C
`
`01
`~
`\0
`Q\
`,..
`~
`N
`Q\
`
`

`

`U.S. Patent
`
`Aug. 18, 1998
`
`Sheet 7 of 9
`
`5,796,426
`
`U-V Plane
`Source Texture
`
`bounding
`box
`u5v5
`u2v2r-------- ~~---==
`I
`I
`I
`I
`I
`I
`u1v1L---
`u1 v1
`:
`I
`I
`I
`I
`I
`
`Figure 7
`
`I
`I
`I
`I
`I
`I
`\~/
`
`x2y2
`t'...._
`\
`
`........ _
`
`\
`\
`\
`\
`\
`I
`I
`
`~~
`
`---
`
`x2y2
`
`x1 y1
`
`' ' I
`I , __
`~- ---
`xtytr
`r
`I
`I
`I
`I
`I
`I
`I
`I
`I
`I
`L - -
`x0y0
`
`xOyO
`
`-
`
`--
`
`-----
`
`screen boundaries
`
`X-Y Plane
`Destination Texture
`----.---
`1 x5y5
`I
`I x5y5
`I
`I
`I
`x4y41
`----r- ------- --
`' ' ' I
`
`----
`
`~~
`
`x8y8
`
`I
`I
`
`x4y4
`
`x7y7
`
`\
`\
`\ x3y3
`\
`- _ ,_ - - -
`
`x3y3
`
`x6y6
`----
`
`-
`
`-I
`
`x8y8
`
`....-
`
`/1
`I
`,;,;
`I
`I
`I
`I
`I
`I
`
`I
`I
`
`I ,
`I ,
`
`---...t x7y7
`\
`\
`I
`\
`\
`\
`\
`\
`\
`------.l
`x6y6
`
`

`

`U.S. Patent
`US. Patent
`
`Aug. 13, 1998
`Aug. 18, 1998
`
`Sheet 8 of 9
`Sheet 8 of 9
`
`5,796,426
`5,796,426
`
`CXJ
`
`
`
`GOOGLE EXHIBIT 1010, Page 9 of 16
`
`

`

`U.S. Patent
`
`Aug. 18, 1998
`
`Sheet 9 of 9
`
`5,796,426
`
`F igure 9
`
`Define Fixecl \Jo.rped
`],.lOge Po.rar1eters
`
`400
`
`~
`
`Initialize Vario.ble
`Dewarpecl !Mage
`Paro.Meters
`
`410
`
`~
`
`Load PrecoMpute:>d
`Inverse:> Mo. trix
`Values
`
`420
`
`l
`
`... ..
`
`Input Video Signo.l
`
`430
`
`l
`
`User Selection of
`Viewing Vector
`
`440
`
`l
`
`Control Point
`Trans for Mo. tion
`
`450
`
`l
`
`Dewarp Region
`Defined by Control
`Points
`
`460
`
`l
`
`Output to Video
`Buffer
`
`470
`
`

`

`5.796.426
`
`1
`WIDE-ANGLE IMAGE DEWARPING
`METHOD AND APPARATUS
`
`F1ELD OF THE INVENTION
`The present invention relates to a method and apparatus
`for displaying a perspective corrected field of view from
`wide angle video sources. and more particularly relates to
`permitting the user of an orientation sensing means to view
`a selected portion of stored or real time video encoded from
`a wide angle source and transforming that portion to a
`perspective-corrected field of view.
`
`BACKGROUND OF THE INVENTION
`"Virtual reality" and "telepresence" have become
`extremely popular for use in research. industrial and enter(cid:173)
`tainment applications. In "virtual reality " . or VR. a user is
`permitted to view a computer-generated graphical represen(cid:173)
`tation of a selected environment. Depending on the sophis(cid:173)
`tication of the hardware and software used to generate the
`virtual reality environment. the user may be treated to a three
`dimensional view of the simulated environment. In
`"telepresence," a user is permitted to view a real-world. live
`or recorded environment from a three dimensional perspec(cid:173)
`tive.
`In addition. in some higher end systems the user is
`permitted to see different portions of the VR and telepres(cid:173)
`ence environments simply by moving or orienting his head
`in one or more degrees of freedom. This permits the user to
`obtain the sensation that he is immersed in the computer(cid:173)
`generated/real-world environment. High end devices detect
`pan. roll and tilt motions by the user and cause the envi(cid:173)
`ronment to change accordingly. The pan\tilt\roll motions
`may be inputted by many types of input devices. such as
`joysticks. buttons or head orientation sensors (which may be
`connected to head mounted displays).
`In VR applications. a continuing problem is how to render
`a three dimensional environment of the quality and speed
`users want while offering the product at a price they can
`afford. To make a realistic environment. such as in a three 40
`dimensional video game. many three dimensional polygons
`need to be rendered. This rendering requires prolubitively
`expensive hardware which greatly restricts the commercial
`value of such a system.
`In relation to telepresence applications. a continuing prob- 45
`lem with the prior art is how to encode sufficient data that a
`viewer may arbitrarily move his viewing perspective within
`the telepresence environment and not look beyond the field
`of view. One relatively simple solution. where the telepres(cid:173)
`ence environment is based on a real three dimensional 50
`environment. is to simply use the head orientation sensors to
`cause a camera to track the orientation of the viewer. This
`has obvious limitations in that only one viewer can be in the
`telepresence environment at a time (since the camera can
`only track one viewer, and the other viewers will not 55
`typically be able to follow the head motions of the control(cid:173)
`ling viewer) and. also, prerecorded data cannot be used.
`Further. there is an inherent delay between a change in user
`viewing perspective and the time that it takes to realign the
`corresponding camera. These limitations greatly restrict the 60
`value of such systems.
`One method for overcoming each of these limitations is to
`encode. either in real time or by pre-recording. a field of
`view largely equivalent to the entire range of motion vision
`of a viewer-that is. what the viewer would see if he moved 65
`his head in each permitted direction throughout the entire
`permissible range. For example. encoding substantially a
`
`2
`full hemisphere of visual information would permit a plu(cid:173)
`rality of viewers a reasonable degree of freedom to interac(cid:173)
`tively look in a range of directions within the telepresence
`environment.
`The difficulty with this approach is that most means for
`encoding such information distort. or warp. the visual data.
`so that the information must be corrected. or "de-warped"
`before a viewer can readily assimilate it. For example. a
`typical approach for encoding substantially a full hemi-
`10 sphere of information involves using a fish-eye lens. Fish(cid:173)
`eye lenses. by their nature. convert a three dimensional
`scene to a two-dimensional representation by compressing
`the data at the periphery of the field of view. For the
`information to be viewed comfortably by a viewer in the VR
`15 environment. the visual data must be decompressed. or
`dewarped. so that it is presented in normal perspective as a
`two dimensional representation.
`One solution to the distortion problem is proposed in U.S.
`Pat. 5.185.667 issued to Steven Zimmerman. The '667
`20 patent describes an apparatus which effects camera control
`for pan. tilt. rotate and zoom while having no moving parts.
`Through the use of a fisheye lens and a complicated trigo(cid:173)
`nometric technique. portions of the video images can be
`dewarped. However. the solution proposed by the '667
`25 patent is impractical because it is insufficiently flexible to
`accommodate the use of other lenses besides a theoretically
`perfect hemispherical fisheye lens without the introduction
`of mathematical errors due to the misfit between the theo(cid:173)
`retical and the actual lens characteristics. This solution also
`30 introduces undesirable trigonometric complexity which
`slows down the transformation and is overly expensive to
`implement. This solution further maps each individual pixel
`through the complex trigonometric mapping formula further
`reducing the speed of the transformation from one coordi-
`35 nate system to another.
`As a result. there has been a substantial need for a method
`and apparatus which can dewa.rp encoded wide angle visual
`data with sufficient speed and accuracy to permit a viewer to
`immerse himself in a VR or telepresence environment and
`look around within the environment while at the same time
`permitting other viewers concurrently to independently
`engage in the same activity on the same broadcast video
`signal. There has also been a need for a method and
`apparatus capable of providing such dewarping on a general
`purpose high speed computer.
`
`SUMMARY OF THE INVENTION
`The present invention overcomes the limitations of the
`prior art. In particular. the present invention transforms a
`plurality of viewing vectors within a selected portion of the
`wide angle. three dimensional video input into two dimen(cid:173)
`sional control points and uses a comparatively simple
`method to transform the image between the control points to
`create a perspective-corrected field of view.
`More specifically. the present invention is drawn to a
`method and apparatus which provides perspective corrected
`views of live. prerecorded or simulated wide angle environ(cid:173)
`ments. The present invention first captures a wide angle
`digital video input by any suitable means. such as through
`the combination of a high resolution video camera. hemi(cid:173)
`spherical fisheye lens and real time digital image capture
`board. The captured image is then stored in a suitable
`memory means so portions of the image may be selected at
`a later time.
`When a portion of the stored video is selected. a plurality
`of discrete viewing vectors in three dimensional space are
`
`

`

`5.796.426
`
`3
`chosen and transformed into a plurality of control points in
`a corresponding two dimensional plane. The area bet.w~en
`the control points. which is still warped from t~e ongmal
`wide angle image capture. is then transformed mto a per(cid:173)
`spective corrected field of view through a biquadratic poly(cid:173)
`nomial mapping technique. The perspective corrected field
`of view is then displayed on a suitable displaying apparatus.
`such as a monitor or head mounted display. The present
`invention further has the ability to sense an inputted
`selection. orientation and magnification of a new portion of
`the stored video for transformation.
`In comparison with the prior art. the present invention
`provides a dependable. low cost, faster and mor~ eleg~ntly
`simple solution to dewarping wide angle three dimensiOnal
`images. The present invention also allows for simultaneous.
`dynamic transformation of wide angle video to multiple
`viewers and provides each user with the ability to access and
`manipulate the same or different portions of the video input.
`In VR applications. the present invention also allows the
`computer generated three dimensional polygons to be ren(cid:173)
`dered in advance; thus. users may view the environments
`from any orientation quickly and without expensive render(cid:173)
`ing hardware.
`It is therefore one object of the present invention to
`provide a method and apparatus for dewarping wide angle
`video to a perspective corrected field of view which can then
`be displayed.
`It is another object of the present invention to provide a
`method and apparatus which can simultaneously transform
`the same or different portions of wide angle video input for
`different users.
`It is yet another object of the present invention to provide
`a method and apparatus which allows selection and orien(cid:173)
`tation of any portion of the video input.
`It is still another object of the present invention to provide
`a method and apparatus for magnification of the video input.
`It is still another object of the present invention to provide
`a method and apparatus which performs all of the foregoing
`objects while having no moving parts.
`These and other objects of the invention will be better
`understood from the following Detailed Description of the
`Invention. taken together with the attached Figures.
`THE FIGURES
`FIG. 1 shows a functional block diagram of one embodi(cid:173)
`ment of the present invention.
`FIG. 2 diagrams the geometry between three dimensional
`(X-Y-Z) space and its corresponding two dimensional (U-V)
`plane.
`FIG. 3a shows a bilinear mapping of a warped image.
`FIG. 3b shows a biquadratic mapping of a warped image.
`FIG. 4 shows a side view of a viewing vector from a three
`dimensional (X-Y-Z) wide angle lens as it is seen on a two
`dimensional (U-V) plane.
`FIG. 5 shows a three dimensional field of view along with
`a plurality of viewing vectors according to the present
`invention.
`FIG. 6 shows a block diagram of the elements of a
`forward texture mapping ASIC according to the present
`invention.
`FIG. 7 shows an example of a U-V source texture
`transformed into a X-Y plane destination texture according
`to the present invention.
`FIG. 8 is one embodiment of how to obtain a 360 degree
`view using six hemispherical fisheye lenses according to the
`present invention.
`
`5
`
`4
`FIG. 9 is a functional flow chart of one embodiment of the
`present invention.
`DErAILED DESCRIPTION OF THE INVENTION
`Referring now to FIG. 1. an embodiment of the present
`invention for processing wide angle video information in
`real time is shown. A high resolution video camera 10
`having a wide angle lens 20. such as a hemispherical fisheye
`lens. is directed to a real world scene 22. The output 24 of
`the camera 10 is provided to a real time image digitizing
`10 board 30. commonly referred to as a "frame grabber."
`located in or operatively connected to a conventional high
`speed computer indicated generally at 150. The camera 10
`may be any camera which is capable of using a wide angle
`lens and providing suitable resolution. In most instances the
`15 camera will be a video camera. although in some instances
`it may be desirable to use a still frame camera. One suitable
`fish eye lens is the Nikkor Auto 1: 1.8 f=8mm fish eye lens
`which can be adapted to a standard high resolution broadcast
`video camera with a Nikon FW-Eng TMW-Bl converter.
`20 The computer 150 is any computer capable of receiving and
`processing video information at an acceptable rate and may.
`for example. be an 80486-based or Pentium ThCbased system.
`or other computer platform such as are made by Silicon
`Graphics. Sun Micro Systems. Apple Computer. or similar
`25 other computer manufacturers.
`The fish eye lens 20 causes the video output signal 24 from
`the camera 10 to be optically warped in a non-linear manner.
`Before the image can be comfortably viewed by a user.
`perspective-correcting measures must be taken. The. d!~i-
`30 tized video signal 24 is thus transferred through the digitiz(cid:173)
`ing board 30 (typically but not necessarily operating at 30
`frames per second) into memory 40 of the computer 150 so
`that portions of the video picture can be randomly accessed
`by a microprocessor 50. also within the computer 150. at any
`time.
`The dewarping software is also stored in memory 40 and
`is applied to the video signal 24 by the microprocessor 50.
`The stored video signal is then transmitted from memory 40
`40 to a special purpose ASIC 60 capable of biquadratic or
`higher order polynomial transformations for texture warping
`and interpolation. Alternatively, the texture warping ASIC
`60 may be omitted and its functionality may be performed
`by software. Phantom lines have been used to show the
`45 optional nature of ASIC 60. The perspective corrected video
`signal is next transmitted to a video output stage 70. such as
`a standard VGA card. and from there displayed on a suitable
`monitor. head mounted display or the like 80. An input
`device 90, such as a joystick or headtracker (which senses
`50 the head movements of a user wearing a headmounted
`display). transmits position information through a suitable
`input port 100. such as a standard serial, paralle~ or game
`port. to the microprocessor 50 to control the port10n of the
`stored video that is selected, dewarped and displayed. The
`55 input device 90 also transmits roll/pitch/yaw information to
`the microprocessor 50 so that a user may control the
`orientation of the dewarped video signal. Further. one skilled
`in the art will appreciate that a magnification option could be
`added to the input device 90 to allow the user to magnify the
`60 selected portion of video input, constrained only by the
`resolution of the camera 10.
`FIG. 2 shows a real world three dimensional environment
`200 which has been imaged by the wide angle lens 20. This
`environment is defined by the Cartesian coordinate system
`65 in X. Y and z with the viewpoint defined to be the origin of
`the coordinate system. The viewing direction of the user. as
`defined by the input device 90. is given as a viewing vector
`
`35
`
`

`

`5.796.426
`
`5
`in the X-Y-Z coordinate system. The image plane 210
`containing the warped wide angle image is defined by a two
`dimensional coordinate system in U and V. with the origin
`of the coordinate system coincident with the origin of the
`X-Y-Z coordinate system. If the field of view of the lens 20
`is sufficient. and the lens is rotationally symmetric about the
`viewing axis. the digitized warped image will be roughly
`circular in the U-V plane.
`The first generation of ASICs. developed for low-cost
`texture mapping of three dimensional graphics. mapped 10
`video images through a bilinear technique. such as is shown
`in FIG. 3(a). These chips were able to apply linear interpo(cid:173)
`lation to texture pixels in both the X and Y directions and
`could thereby stretch rectangular source textures to any two
`dimensional quadrilateral shape. An example of a chip of 15
`this type is the Artist Graphics 3GA chip. These bilinear
`chips do. however. introduce texture errors for polygons
`whose vertices have been subject to significant amounts of
`perspective. and further are not capable of sufficiently high
`order texture distortion to adequately flatten extreme wide 20
`angle views, such as with hemispherical fisheye lenses.
`FIG. 3b shows an example of a biquadratic technique.
`such as is now coming onto the market. The preferred
`embodiment of the present invention uses an ASIC chip
`which implements a texture warping technique of at least 25
`second polynomial order. The present invention is of suffi(cid:173)
`cient simplicity that this technique could also be imple(cid:173)
`mented in software on a general purpose high speed
`computer, such as a Silicon Graphics Indigo™ computer or
`a Pentium ™ based computer.
`The warped image in the U-V plane. shown in FIG. 2. has
`a radius 220 equal to RADIUS pixels with an origin at
`UORIGIN and VORIGIN. For any rotationally symmetric
`lens. the warping effect of the lens can be described by a
`single lens equation. r=f(S). where the function f(S) maps 35
`any incident ray at angle e from the axis of viewing to a
`radial displacement in pixels. r. from the center of the U-V
`plane. as shown in FIG. 4.
`For any given viewing direction in three dimensional
`X-Y-Z space, we then have:
`
`30
`
`40
`
`s= \lx2+y2
`
`e =arctan..!.. z
`
`r =J(9)
`
`rx
`u=(cid:173)
`s
`
`v=.!2
`s
`
`(1)
`
`45
`
`50
`
`6
`v from the primary viewing vector. as shown in FIG. 5. Each
`of these nine vectors are then projected from three dimen(cid:173)
`sional X-Y-Z space to the two dimensional U-V plane by
`equations (1). The result is a 3x3 grid of control points in the
`U-V plane. with the edges of the grid curving mathemati(cid:173)
`cally to conform with the curvature induced by the warping
`effect of the wide angle lens.
`The global bivariate polynomial transformation:
`
`(3)
`
`N N-i
`v= ;~};n bqxiyl
`
`with x and y now referring to the pixel coordinates in
`the output device
`
`is then found to describe the geometric correction necessary
`to transform the region within the warped 3x3 grid in the
`U-V plane into a perspective corrected field of view. A
`biquadratic polynomial transformation. N=2 in the above
`equations. has been selected because a second order poly(cid:173)
`nomial approximates the warping characteristics of most
`lenses to an adequately high degree of precision and because
`there is existing hardware to perform the resulting biqua(cid:173)
`dratic transformation. However. it will be appreciated by one
`skilled in the art that other polynomial transformations of
`higher degree could be used to increase the precision of the
`transformation.
`Expanding the above equations (3):
`
`(4)
`
`I XJ Y! Xl)l! xi Xt2
`
`I X2 Y2 X2Y2 ~ X22
`I XJ Y3 X3Y3 4 XJ
`I X< Y• X<Y4 ~xi
`
`2
`
`1 xs Y5 X5Y5 ~ xs2
`
`1X6Y6X6Y6xi~
`
`,..,Y7Xm~xr
`
`aoo
`
`a10
`
`llOl
`
`au
`
`Q2()
`
`ll02
`
`UJ
`
`U2
`
`UJ
`
`"•
`us
`
`U6
`
`U7
`
`U$
`
`ug
`
`I xs Ys X8Ys ,.Z. xs2
`1 xg Y9 xgyg 4 xg2
`The values for v and bii. can be similarly found. In matrix
`form. the expanded equations (4) can be written as:
`
`U=WA
`
`V=WB
`
`(5)
`
`In the case of an ideal hemispheric fisheye lens. f(S)=
`(RADIUS)(sin(S)) and the lens equation which results is:
`
`r
`
`(RADIUS)(s)
`
`(RADIDS)~
`
`z~1+.:t
`
`z2
`
`z~l+x2+f
`
`z2
`
`(2)
`
`To discover a,i and bii • according to the method of the
`present invention. a pseudoinverse technique is used.
`55 However. one skilled in the art will appreciate that there are
`methods to solve equations (5) other than by a pseudo
`inverse technique. i.e. a least squares technique. The pseudo(cid:173)
`inverse solutions for A and B in the above equation (5) are:
`
`60
`
`A=(W"' W)-' W"'U
`
`Equations (1) convert an inputted X-Y-Z three dimensional
`viewing vector into a corresponding control point in the U-V
`plane.
`To dewarp a rectangular portion of the wide angle video
`input for a given viewing direction (x.y.z). eight other 65
`viewing vectors. which surround the primary viewing
`vector. are computed at the field of view angles fovh and fov
`
`(6)
`
`Therefore. for a target display of a given pixel resolution
`NxM. W and its pseudoinverse (W7Wr 1
`WT can be calcu(cid:173)
`lated a priori. The values for a,J and bij are then found by
`mapping the points in the U-V plane for the 3x3 grid of
`control points using the above equations ( 6). The biquadratic
`
`

`

`5.796.426
`
`8
`mapped to the input (U-V). In the case where a forward
`texture mapping ASIC is used. the coordinates for the
`destination control points in X-Y must be supplied so that
`the rectilinear source texture region can be mapped from the
`5 U-V plane. as provided by the inverse texture mapping
`software solution above. to the X-Y plane. An example of a
`forward texture mapping ASIC is the NV-I chip sold by
`N-Vidia Corporation. FIG. 6 gives another example of an
`ASIC chip 230 which accepts control pixel coordinates at a
`forward mapping solution stage 240. Four pixel coordinates
`will be accepted for a bilinear mapping. nine in the case of
`quadratic mapping. 16 in the case of cubic mapping. etc.
`These control pixels are produced in the host CPU according
`to the equations (7). below. As shown in Fig. 7. the coor(cid:173)
`dinates of a rectangular bounding box are determined to
`15 enclose an exemplary 3x3 grid of control points uy, in the
`U-V plane. The corners of the bounding box are found from
`the u,v, extrema. Using the same technique described in
`equations (3). aii and b,1 for N=2 can be solved with the
`equations (7) for enclosing the region to be warped to the
`20 corners of the display screen.
`
`10
`
`7
`polynomial transformations of the equations (3) are then
`used to transform the area between the control points. In this
`embodiment. the determination of the coordinates of each
`pixel in the U-V plane takes a total of thirteen multiplication
`and ten addition operations. Additionally. three of the
`required multiplication operations per pixel may be obviated
`by storing a table of xy. x 2 and y 2 values for each xy
`coordinate pair in the dewarped destination image. In
`another embodiment. the "x" values which do not vary as
`"y" changes (i.e. a 1 *x+a4 *x 2 and b 1 *x+b4 *x2
`) may also be
`precomputed and stored. Likewise. the "y" values which do
`not vary as "x" changes may be precomputed and stored.
`These further optimizations reduce the operations needed to
`determine the coordinates of each pixel in the U-V plane to
`two multiplication and four addition operations.
`It will be appreciated by one skilled in the art that the
`accuracy of the dewarping transformation will increase as
`the number of transformed viewing vectors increases. i.e. a
`4x4 grid of control points will produce a more accurate
`transformation than a 3x3 grid of control points. However.
`the amount of increase in accuracy quickly draws near an
`asymptote as the number of control points is increased. One
`skilled in the art will recognize. therefore. that there is little
`reason in increasing the number of viewing vectors to more
`than half of the total number of pixels in the displayed 25
`region.
`It will be further appreciated by one skilled in the art that
`the selection of a rectangular shape of the video input could
`be changed to another shape and still be within the scope of
`the invention. Further. the number of control points could be 30
`increased or decreased to correspondingly increase or
`decrease the accuracy of the transformation of control points
`may be between five and half of the number of pixels in the
`output image. Further still. an image filtering stage could be
`applied during the inverse texture mapping without deviat- 35
`ing from the present invention.
`FIG. 9 shows a functional flow chart of the major ele(cid:173)
`ments of one embodiment of the present invention. First. the
`fixed warped image parameters (step 400) are defined, such
`as the size of the input image. the input image radius. and the 40
`input image center in U-V coordinates typically measured in
`pixels. The next step 410 is to initialize the variable dew(cid:173)
`arped image parameters. such as the size of the dewarped
`image area. the horizontal and vertical field of views
`(generally shown in degrees). the creation of an untrans- 45
`formed view cone centered in this embodiment on the +Z
`axis and the initialization of the layout and number control
`points used therewith. Typically. the next step is to load the
`precomputed inner-loop matrix values as well as the "xy"
`product terms, as shown in step 420. to ensure that the so
`transformation is accomplished as quickly and efficiently as
`possible. In step 430. the video signal is input to the system
`in any suitable form. i.e. live or pre-recorded real-time
`digitized video or computer synthesized video environ(cid:173)
`ments. The system then allows the user to select the viewing 55
`vector (step 440) which in turn determines the portion of
`video which is to be transformed. The control points are next
`transformed from the selected viewing vectors (step 450)
`and the region defined by the control points is dewarped
`(step 460). The signal is then sent to the video buffer and to 60
`an appropriate viewing apparatus (step 470). There is a
`recursive loop from step 470 to step 430 to allow the video
`signal to be refreshed. as is needed with live motion video.
`The loop also allows the user to make on-the-fly selections
`of alternate portions of the incoming video.
`The foregoing description describes an inverse texture
`mapping technique whereby the biquadratic output (X-Y) is
`
`N N-i
`x= l:
`l: a··u'vi
`i=Oj=O •
`
`N N-i
`y = l:
`l: b··u'vi
`i=Oj=O •
`
`(7)
`
`Thus. the same control points for the U-V plane map to
`the corners of the display screen in the X-Y plane. The
`warped regions outside the bounding box may be clipped by
`hardware or software so that they are not visible on the
`display screen.
`The source pixel coordinates. which are fed from the host
`CPU, are converted to a;1 and b;1 coordinates for forward
`mapping in the forward mapping solution stage 240. again
`using techniques mathematically equivalent to those of the
`equations (7). A series of instructions is further sent from the
`host CPU to the chip 230 and received by a control unit 260.
`The control unit 260 sequences and controls the operation of
`the other functional stages within the chip 230. The host
`CPU also directs a linear sequence of source pixels. which
`are to be warped. to an interpolation sampler stage 250
`wit