Panoramic movies which simulate movement through multidimensional space

Description of equivalent WO 9959026 A2

PANORAMIC MOVIES WHICH SIMULATE MOVEMENT THROUGH MULTIDIMENSIONAL SPACE

Field of the Invention: The present invention relates to photography, digital image processing and to computer graphics. More particularly the present invention relates to a method and system for providing a viewer with a multidimensional view which simulates movement through space or time.

Copyright Notice: A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document; however, otherwise the copyright owner reserves all rights whatsoever.

Background of the invention: Motion is usually simulated by means of single view movies. Single view movies consist of a series of single photographs which are sequentially projected on a screen. At any time, a single photograph is entirely projected on the screen. Some movie theaters have screens which partially surround the viewer, so that a viewer can turn and look at a different portion of the screen as the movie progresses However, irrespective of where the viewer's attention is focused, in fact the entire image is being projected on the screen. With some equipment single view movies can be stopped and reversed; however, again at a particular time a selected frame is entirely displayed. In summary, traditional movies do not allow a viewer to control the portion of the image which is projected on the screen. Stated differently, with traditional movies a viewer can not control the "view window" through which each image is viewed.

It should be noted that as used herein the term "screen" refers to either a traditional screen onto which an image is projected or an electronic display which projects or displays an image in such a manner that the image can be seen by a viewer.

The technology for producing panoramic images and photographs is well known. Panoramic images are images which represent the visual surroundings from a single location (or view point) of a particular 3D environment. Panoramic images can be photographic, computer-generated (CG), or a composite of photo and CG imagery. Equipment is available which seams together a series of two dimensional conventional images to form a panoramic image. Panoramic images may consist of any field of view such as a full sphere full cylinder, semi-sphere, etc. however, full sphere views are generally preferred. Panoramic images may be in any of the known projection formats, such as equi-rectangular, Mercator, Peters, fisheye, cube, or hemicube, etc. If the field of view is wide enough to warrant, perspective correction may be applied to the portion of a panoramic image displayed in order to remove projection distortions from the given view of the user. Computer programs and systems which allow one to view a selected portion of, to pan, to rotate, etc a panoramic image or photograph in response to the movement of a computer mouse, joystick, keyboard, etc. are commercially available.

Panoramic image (or photographic image) viewing systems are available which provide a number of panoramas (for example views of adjacent rooms in a building) and which allow a user who is viewing one of the rooms to "click" on a door and to thus bring up the panorama of the next room, thereby, in some sense simulating movement into the next room. However, each of the panoramic views in such systems is static and some explicit action on the part of the viewer is required to move on to a different panorama.

U.S. Patents 5,023,925 and 5,703,604 describe, and Dodeca LL.C. located in Portland Oregon commercially markets, a system for capturing images using a multi lens camera, for seaming the images into panoramas, and for viewing selected portions of the panoramic images.

Other panoramic image or photographic viewing systems are available which initiate a conventional single view motion picture when a user "clicks" on a spot such as a door in a first panoramic view. The single view movie simulates movement into a different location and at the end of the movie, the user is presented with a second panoramic view.

A company named "Warp" located in the Kingdom of Tonga has demonstrated a system wherein a video sequence is captured using a video camera with a fisheye lens which is pointed in the vertical or "up" direction (see, VTV Software Development Kit Reference Manual 2.01 Win95 1996). This approach provides a hemispheric movie in which the user may "pan around" while the movie is playing. In the system demonstrated by Warp, the user views the movie "in sequence", meaning that each frame of the movie is played according to the temporal sequence in which the hemispheric movie was captured. The system demonstrated by Warp was limited to sub-spherical panorama dimensions and the camera was located at a fixed position.

Realistic simulation of movement from one location to another can be provided by three dimensional computer modeling systems, such as those used in some flight simulators. However, such systems are very computationally intensive

Summary of the present invention: The present invention simulates movement through multi-dimensional space using a series of panoramic images which are projected or displayed in sequence. The user's direction of view, that is the selected view window, is maintained as the series of images is projected or displayed. Motion in directions other than forward or reverse is simulated by utilizing "branch" points in the sequence. Each path from a branch point can simulate motion in a different direction. Branch points are generally indicated to a viewer by visual indicators called "hot spots"; however, branch points may also be hidden and activated in response to the viewer's selected direction of view. If a branch point is indicated by a visual indicator, a user can select motion in a desired direction by "clicking" on a "hot spot".

In order to conserve storage space, the image representing each panorama can be stored in a compressed format. If the images are stored in compressed format, in order to conserve time and processing power, when an image is displayed, only the portion of the panorama necessary to create a "view window" that is, the portion of the image displayed in response to the user's direction of view, is decompressed. Furthermore, the images are stored in a format that does not utilize inter-image compression (such as that used by the MPEG format). Since the images are stored in a format that does not utilize inter-image compression, it is possible to simulate motion in both the forward and backward direction without operating on a series of decompressed images. An index methodology is used to store the panoramic images. Use of the indexing methodology allows the images to be retrieved in both the forward and backward direction to simulate movement in either direction.

Sound is provided in a special format, so that special effects can be provided based on the user's point of view and dependent upon the direction of motion selected by the user.

Brief Description of the Figures: Figure 1 illustrates a key frame (that is, panoramic image) with a view window and associated sound tracks.

Figure 2 is a block diagram showing the major components in the preferred embodiment.

Figures 3A to 3D shows the sequence of operations performed by the various components in the system shown in Figure 2.

Figure 4A illustrates a sequence of frames which constitute a panoramic movie.

Figure 4B illustrates the sound track associated with the frames of a panoramic movie.

Figure 5A is a perspective view of the multi lens hand held unit that captures a series of panoramic images.

Figure 5B is top view of the multi lens hand held unit shown in Figure 5A.

Figure 6 is a block diagram of the electronic components in the hand held unit shown in Figures 5A and 5B.

Figure. 7 is a diagram of a file containing a pan movie. Figure 7 shows a series of panoramas stored as a series of compressed key-frames and a file index for sequencing playback of the key-frames. Figure 8 is a block diagram of a program for inserting hot spots in a pan movie.

Figure 9A is a block diagram of a system for playback of a 3-D panoramic movie according to the invention.

Figure 9B is a block diagram of a real time viewing unit.

Figure 10 is a flowchart of the program for viewing a 3-D movie containing a sequence of panoramas according to the invention.

Figure 1 1 is a diagram illustrating the audio information associated with each key frame.

Figure 12A, 12B and 12C are a spatial sequence of perspectively correct views illustrating movement past a billboard displaying an advertisement which has been superimposed into a scene as a hot spot.

Description of Appendices: Appendix A is a print out of computer code for retrieving images and correcting the perspective of images in a pan movie. Appendix B is a sample of link control file for a pan movie. Appendix C is a print out of computer pseudocode for linking sequences of images to form a pan movie.

Description of a preferred embodiment: In order to simulate movement through multi-dimensional space, one must first capture a series of panoramic images, the panoramic images must be stored as frames and then the appropriate view window from selected frames must be displayed in an appropriate sequence.

A panoramic image provides data concerning what is visible in any direction from a particular point in space. At any particular time a viewer or user can only look in one direction. The direction or point of view of a viewer or user determines the "view window", that is, the part of a panoramic image which is projected on a screen at a particular time Figure 1 shows a key frame (i e a panoramic image) or a panorama 3a Panorama 3a has a view window 3b which corresponds to a portion of panorama 3a Panorama 3a also has associated therewith a number of sound tracks 3c It is noted that for ease and clarity of illustration, no attempt has been made to illustrate in Figure 3 the well know fact that there is a difference in perspective between what is displayed in a view window and what is stored in a flat section of a rectilinear spherical panorama

Figure 2 is an overall diagram of a preferred embodiment of the invention A camera unit 10 captures images The images are sent to a computer 20 which stores the images Computer 20 also controls camera unit 10 If desired the images can be viewed by a real time viewer 30 The images are transferred from computer 20 to off line computer 21 Computer 21 seams the images into panoramas, transforms the images to equirectangular format, adds other information to the images, compresses the panoramas, and links the panoramas into a pan movie Finally the pan movie is viewed on viewer 22

The operations performed by the units in Figure 2 are shown in Figures 3A, 3B, 3C and 3D As shown in Figure 3A, block 11 a, camera unit 10 captures a number of single view images As indicated by block 1 1 b these images are compressed and sent to a computer 20 Computer 20 activates camera 10 to capture the images as indicated by block 20a It then accepts the images as indicated by block 20b and stores them

The stored images are manually transferred to off line computer 21 which is programmed to perform the operations shown in Figure 3C First the images are decompresses as indicated by block 20a so that they can be manipulated Next the single view images are seamed into a panorama and transformed to equirectangular format as indicated by block 21 b Hot spots which indicate break points in a sequence of images and sound tracks are added next as indicated by block 21 c Finally the images are compressed as indicated by block 21 d and stored with an index file as indicated by block 21 e Each panorama is termed a "key frame" A series of key frames (or more precisely a sequence of view windows) projected in sequence is a pan movie A viewer program in viewer computer 22 is used to view the pan movies The viewer 22 displays in sequence a series of images, that is, a series of key frames For each key frame displayed the viewer 22 determines an appropriate view window as indicated by block 22a The portion of the key frame which corresponds to the view window is then de-compressed and displayed as indicated by block 22b As indicated by block 22c, sound is played if appropriate

It is noted that the operations indicated by blocks 20a, 20b, 21 a to 21 e, 22a, 22b, and 22c are implemented by means of computer programs which perform the functions shown Computer programs are given in appendices A, B, C, and D

Figure 4A represents or illustrates a sequence or series of panoramic images in a pan movie Each arrow in Figure 4A represents one key frame At any particular time, only a part (i e the view window) from one key frame is visible to a user or observer The direction of each arrow indicates the direction of view, that is, the view window or part of the key frame that is projected on a screen for observation The arrows in Figure 4A are meant to represent a particular "view window" from each key frame As indicated by the change in direction of the arrows in the area of Figure 4A designated by the letter E, a viewer can change his direction of view as the pan movie progresses It is noted that when a user is viewing a panorama, a user can point toward the top or bottom of the screen and thus can view images located in a 360 degree circle from top to bottom in addition to the horizontal directions illustrated by the arrows shown in Figure 4A

The sequence of images begins at the point or at the key frame indicated by the letter A and the sequence proceeds to the point or key frame indicated by the letter B At this point the viewer can select to either go toward point C or toward point D The selection may be made by "clicking" on a designated "hot spot" in the panorama designated B or it may be made depending on some other criteria or action by the user An important point is that at the branch point B, the direction of view (indicated by the direction of the arrows) remains the same irrespective of which path of travel is chosen The view from the first frame after the branch point will be almost identical in both paths As time progresses and the viewer moves further from the branch point, the view will gradually change This is the effect that a person experiences when one arrives at a dividing point in a path When a person takes the first step on a branching path, the persons field of view remains practically identical

It is noted that at branch point B, the arrows are not pointing in the direction of the path leading to point D Normally, a viewer would be looking in the direction of a branch point when the viewer selects to travel in the direction of the branch point Thus, a viewer looking in the direction of the arrows shown in Figure 4A would normally continue to point C rather than selecting the path to point D

Sequences of key frames can either be joined at branch points such as branch point B or alternatively a branch point may be located at the end of a sequence of key frames That is, a branch point may be located at the terminal frame of a sequence of key frames Such a branch point could have two alternative sequences, one of which can be selected by a user by clicking on one of two hot spots Alternatively at the end of a sequence of key frames, there can be an implicit branch point At such an implicit branch point a new sequence of frames would be selected by the system without any action by the user

There is a one to one ratio of key frames to possible user positions Hence, there exists a correlation between frame rate and user motion speed If the user is moving through the environment, every frame displayed is a new key frame The faster the frame rate for a given frame spacing, the faster the user travels Given a fixed frame rate, the user's travel speed may be dictated by the relative spacing of key frames The closer the key frames are, the slower the user will travel For example, for a travel speed of approximately 5 mph and a playback frame rate of 15 fps, individual panoramic frames should be captured at about 6 inch increments The math is as follows (5 miles/hour * 63,360 inches/mile)/ (3600 sec/hour * 15 frames/sec) = 6 inches per frame When the movie is being displayed, speed of travel can be increased by skipping some of the frames (for example if every other frame is skipped the speed of travel is doubled) Skipping frames reduces the rate at which frames need be sent to the viewer and thus reduces the bandwidth required

In addition to the spacing of key frames to achieve different travel speeds, the orientation of individual key frames may be adjusted in order to achieve a desired motion effect, such as gate, slumber, waddle, crawl, skip, etc The orientation of a key frame is defined to be the default view (or point of focus) of the user within the panoramic image if no other point of view is specifically selected

Sound can accompany the visual effect provided by pan movies Figure 4B indicates that each key frame can have one or more associated digital sound tracks The digital sound tracks are indicated in Figure 4B by the dotted line which is associated with each of the arrows As shown in Figure 11 and described later, there can be several different sound tracks associated with each key frame

Figure 5A is a perspective view of the six lens camera unit 10 which is used to digitally capture panoramic images, that is, key frames Figure 5B is a top view of camera 10 which is included to show that the unit has six lenses 41 a to 41f Each lens 41 a to 41f has a 1 10 degree field of view The images captured by lenses 41 a to 41f are transmitted to computer 20 through a serial connection Computer 21 "seams" the individual images from lenses 41 a to 41 f into panoramic images or key frames, compresses the key frames and stores them for future display Additionally, a real time viewer can 30 can be used to view the images as they are being captured and seamed

In the preferred embodiment the connection from camera unit 10 to computer 20 and from computer 20 to real time viewer 30 is a "HOTIink" serial bus Such connections are commercially available from suppliers such a Cypress Semiconductor Corp or from Dataforth Corporation which is a division of Burr-Brow Company Alternatively other types of high speed connections could be used For example the connection could be a standard SCSI connection

Figure 6 shows the electronic components in camera 20 The components associated with each lens 41 a to 41f are substantially identical to the components in commercially available digital cameras The internal operation of the camera 20 is controlled by a conventional embedded programmed computer 45 which, for example, may be a model 29000 computer available from Advanced Micro Devices Corporation Many different suitable embedded processors are commercially available Embedded computer 45 receives commands from computer 20 which has IO units which allow an operator to enter commands For example computer 20 sends commands to computer 45 which set the aperture of the lenses 41 a to 41 f and which starts and stops the operation of the camera. While computer 20 sends general commands to computer 45 such as set aperture, start, stop, etc., computer 45 sends to detailed commands which control CCD arrays 43a to 43f and which control compression chips 44a to 44f. Such commands are conventional.

Each of the lenses 41 b to 41 f has a set of associated components similar to the components associated with lens 41 a.. The following will discuss the components associated with lens 41 a. It should be understood that the other lenses 41 b to 41f have a similar sets of components.

The image from lens 41 a is focused on a CCD (Charge Coupled Device) array 43a. CCD array 43a captures the image from lens 41 a and send this image to embedded computer 45. CCD arrays 43a is controlled and operated by embedded computer 45. By resetting and reading the CCD array 43a in a particular time period, the embedded computer 45 in effect controls or provides an electronic shutter for lens 41 a. The electronic shutters associated with each of the lenses 40a to 40f open and close simultaneously. Each CCD array 43a to 43f captures 30 images per second under normal operation.

The output of CCD array 43a is fed into a JPEG data compression chip 44a. Chip 44a compresses the image from lens 41 a so that the image can be more easily transmitted to computer 40. The output from compression chip 41 a fed to an embedded controller 45 which transmits signals to computer 40 on a serial time slice basis.

The lenses 41 and the CCD arrays 43, and are similar to the components found in commercially available digital cameras. JPEG compression chips 44 and embedded computer 45 are also commercially available components. For example such components are available from suppliers such as Zoran Corporation or Atmel Corporation.

The electronic shutters associated with lenses 41 operate at 30 cycles per second and hence computer 21 receives six images (one from each lens) each 1/30th of a second. The six images received each 1/30th of a second must be seamed and transformed to equirectangular format to form one panorama as indicated by step 21 b in Figure 2.

While the specific embodiment of the invention shown herein utilizes a digital camera to take the initial single view images which are compressed and sent to computer 20 for storage, it should be understood that one could use a variety of other types of cameras to take these initial images. For example the images simultaneously taken from a number of lenses could be recorded on tape for later processing by off line computer 21.

The seaming operation is done by the program in computer 21. In general the seaming operation connects the individual images into a panoramic image by finding the best possible fit between the various individual images. The process of seaming images into a panoramic image is known. For example U.S. patent 5,694,531 describes seaming polygons into a panorama which has a low root-mean-square error.

After the seaming operation is complete each seamed image is a panoramic image (called a panorama) and each panorama is a frame of a pan movie. Prior to storage the seamed images are compressed so as that the file size will be manageable. A commercially available compression program known as "Indeo" is used to compress the images. The Indeo program was developed by and is marketed by the Intel Corporation. The Indeo compression program provides a mode of operation which does not utilize any inter-frame compression. The no inter-frame compression mode of the Indeo program is used with the present embodiment of the invention. Since there is no inter frame compression, the key frames can be accessed and viewed in either the forward or the reverse direction. Furthermore, only the portion of a panorama required for a particular view window is decompressed, thereby saving time and computational resources.

The compressed panoramic images are stored in files on computer disks, tape or compact discs (CDs). Each file includes a header and an index as shown in Figure 7. The header includes information such as the following: File Type Tag: File Size: (total bytes used by the file)

- π - Index Size (Number of entries in frame Index) Max Frame Size (total bytes used by largest compressed frame) Codec (Codec used to compress frames After the file header, a frame index is provided (see Figure 7) Each frame index points to the location of the associated frame as indicated by the arrows in Figure 7 Thus, individual frames can be read in any order by obtaining their location from the frame index

The indexing mechanism would not be necessary if the key frames were always going to be used in frame order However, in the present embodiment, the system can play the key frames which comprise the pan movie in either forward or backward direction Hence the system must be able to locate individual frames quickly in any order Furthermore, it is desirable that the system be able to locate a key frame with only a single disk access Consider the situation were the user is moving "backward" (in the opposite direction of the key frame disk storage) at a fast travel speed (to increase speed of movement some key-frames are skipped) Without a key frame directory, the disk would have to be searched in a "reverse-linear" manner in order to find and load the next appropriate key frame With a key frame directory, the next key frame location is located immediately, and loaded with a single disk access (given the directory itself is stored in RAM memory)

As indicated in Figure 4A, a viewer can branch from one sequence of images to another sequence of images This is indicated by branch point B in Figure 4A By branching a user in effect changes the direction of the simulated travel A user indicates a desire to change direction by "clicking" on a visible "hot spot" or by otherwise activating a hidden hot spot A visible hot spot can be indicated by any type of visible symbol that is visible in a view window For example a hot spot may be indicated by a bright red dot in the view window Alternatively, a hot spot may be indicated by the fact that the cursor changes to a different shape when the cursor is over a hot spot

It is noted that not all visually apparent alternate paths visible in any panorama are actually available as a pan movie branch For example, at a street intersection, branches may not be provided to all visible streets Care must be taken to insure that a viewer is given an indication of the branch points that are actually available to the viewer.

At a playback rate of 30 frames per second a user would have to be very "fast" (i.e. it would in fact be practically impossible) for a viewer to see and click on a hot spot that appears on a single frame. Without advanced notice, the viewer would have great difficulty actually taking a specific action to activate a branch during a specific single frame since in normal operation a particular frame is only displayed for about 1/30th of a second. In order to be effective and user friendly a user must be given an early indication of a upcoming branch opportunity that requires user action. A hot spot in a pan movie must be visible by a viewer in a relatively large number of key frames. For example a hot spot might be visible in the thirty key frames that precede (or follow for reverse operation) a branch point.

Hot spots are inserted into a pan movie in the manner illustrated in Figure 8. The hot spots are inserted into the key frames by computer 21 before the frames are compressed as indicated by blocks 21 c and 21 d in Figure 3C. It is noted that hot spots may be inserted into a pan movie by altering the original panoramic image so that it includes the hot spot or alternately by providing a overlay image which contains the hot spot image. If an overlay is used, the overlay image needs be projected at the same time as the original image. As indicated by block 87a one must first determine how much in advance one wants to warn the user. If a hot spot is to have a particular size at the time action is needed, when viewed in advance (i.e. from a distance) the hot spot will be much smaller. As indicated by block 87b, in order to insert hot spots in a pan movie, one must select the region where the hot spot is to be located. In general this will be in a view looking toward the direction where the branch will take place. The hot spot is then inserted into the panorama by modifying the images. The hot spot may be indicated by a light colored outline superimposed over the region. The area within the outline may be slightly darkened or lightened. The object is to highlight the region without obscuring the image itself. Various other alternative indications can also be used.

The process repeats as indicated by blocks 87d and 87e until the key frame at the branch point is reached. Finally the process is repeated from the opposite direction from the branch point so that the branch point will be visible if the pan movie is shown in the reverse direction.

The changes to the individual key frames may be made manually with a conventional image editor, or the process can be automated by a program designed just for this purpose.

In order to avoid unnecessary user intervention, "hidden" hot spots may be added to connect multiple pan movies. A hidden hotspot is one that does not need to be manually selected by the user. With a hidden hot spot, if the user "travels" into a particular key frame which has a hidden hot spot, and the user is "looking" in the hot spot's general direction, then the system will react based upon the user's implicit selection of the hotspot and the user will be sent along the path directed by the hot spot.

Figure 9A is a block diagram of the viewer 22 which plays or displays pan movies. The main components of the viewer 22 are a CD disk reader 80, a computer 81 , a display 82, a keyboard 84 and a mouse 85. Computer 81 reads key frames from disk 80 and displays the view widow from each key frame on display 82. The operator or user utilizes mouse 85 to indicate a view direction. The view direction determines the view window which is displayed on display 82 by computer 81. A program which implements blocks 22a to 22c (shown in Figure 3D) is stored in and executed by computer 81.

Figure 9B is a block diagram of the real time viewer 30. As an option, the images captured by camera 10 can be viewed in real time. Images are transferred from computer 21 to viewer 22 in real time. The transfer is by means of a HOTIink bus to HOTIink card 86a. The images go from card 86a to RAM memory 86b and then to decompression card 86c which does the de-compression. From the de-compression board 86c the images go back to memory and then to CPU 86d which combines i.e. seams the images as necessary and transfers them to video card 86e which displays them on monitor 86f. Viewer 30 is controlled via a conventional mouse 86m and keyboard 86k. Figure 10 is block diagram of a program for displaying pan movies. The program shown in block diagram in Figure 10 is executed by the computer 81 in Figure 9A. The process begins at block 91 with user input. The user must indicate a start location (at the beginning of the process this would normally be the first frame in the movie). The user must also specify direction of motion, speed and direction of view. As indicated by blocks 92, 92a, 92b and 92c the system determines and then reads the appropriate pan frame data. As indicated by block 96 and 96a, the system determines the portion of the pan frame that is in the selected view window and that portion of the frame is decompressed. As indicated by blocks 97 and 97a, the image is re-projected to obtain a perspective view. If the hot spots have not been placed on the actual key frames but are contained in a separate file, the hot spot imagery is overlaid on the image. Finally, as indicated by block 98, the part of the image which constitutes the view window is projected on the screen.

As a user travels, the next required key frame is determined by the current user position and direction of travel. The location of this key frame within the file of images is determined via the file index directory; and the key frame is loaded into RAM memory, decompressed, and displayed. To increase performance, only the view window (depending on current user view) portions of the key frame need be loaded into RAM. If for ease of programming the entire key frame is loaded into memory, only view window portions of the key frame need be decompressed. If the entire key frame is compressed as a whole, then a de-compressor supporting "local decompression" is more efficient, e.g., Intel Indeo. To determine the portion of the panorama needed to display a particular view, each of the corner coordinates of the perspective view plane (display window) is converted to panorama coordinates. The resulting panorama coordinates do not necessarily represent a rectangle, therefore the bounding rectangle of these panorama data is needed to derive a perspective view at a given view orientation.

Once the corners of the desired bounding rectangle are determined the Indeo de compression program is instructed to decompress only that portion of the key frame needed for the particular view window. In order to do this, the program must call the Video For Windows function ICSetState prior to decompressing the frame. The C code to accomplish this follows. #include "windows. h" #include "vfw.h" #include "vfw_spec.h"

extern HIC hie; // Opened CODEC (IV41); extern RECT *viewRect; // Determined elsewhere static R4_DEC_FRAME_DATA Statelnfo;

void SetRectState ( HIC hie; // Opened CODEC (IV41); RECT *viewRect; // Local Rectangle of interest ) { R4_DEC_FRAME_DATA Statelnfo;

memset(&Statelnfo,0,sizeof(R4_DEC_FRAME_DATA)); Statelnfo.dwSize = sizeof(R4_DEC_FRAME_DATA); Statelnfo.dwFourCC = mmioStringToFOURCC("IV41 ",0); // Intel Video 4.1 Statelnfo.dwVersion = SPECIFIC_INTERFACE_VERSION; Statelnfo.mtType = MT_DECODE_FRAME_VALUE; Statelnfo.oeEnvironment = OE_32; Statelnfo.dwFlags = DECFRAME_VALID | DECFRAME_DECODE_RECT;

Statelnfo. rDecodeRect.dwX = min(viewRect->left,viewRect->right); Statelnfo. rDecodeRect.dwY = min(viewRect->top,viewRect->bottom); Statelnfo. rDecodeRect.dwWidth = abs((viewRect->right-viewRect->left)+1 ); Statelnfo. rDecodeRect.dwHeight = abs((viewRect->bottom-viewRect- >top)+1 );

ICSetState(hic,&Statelnfo,sizeof(R4JDEC_FRAME_DATA)); } If the projection used to store the pan-frame is such that there exists a discontinuity in pixels with respect to the spherical coordinates they represent, then the local region required may be the combination of multiple continuous regions. For a full cylinder/sphere equirectangular projection (centered about 0 degrees), the left pixel edge represents -180 degrees and the right pixel edge represents 180 degrees. In spherical coordinates, -180 degrees is the same as 180 degrees. Therefore, the discontinuous left/right pixels represent a continuous "wrap-around" in spherical coordinates.

The math to determine the portion of the source key-frame panorama needed for a particular view window depends on the projection used to store the panorama. Optionally, the viewer may predict the next key-frame to be loaded (depending on user travel direction and speed), and pre-load it in order to increase performance. For an equirectangular projection of a full sphere panorama frame, the equations for determining the required portion are as follows: where:

Sealer variables are lower case, vectors are bold lower case, and matrices are bold upper case.

Panorama point (s,t) is derived from any perspective plane point (u.v).

The perspective plane has a focal length I from the center of projection.

In addition, the perspective plane can be arbitrarily rotated through a given view orientation, namely heading, pitch, and bank (h,p,b).

Any point in the perspective plane is specified by the 3D vector: w = <u, v, l>

The rotations are applied by using a standard matrix-vector product. The three matrices accounting for Heading, Pitch and Bank are as follows: I cos(h) 0 sin(h)

H = | θ 1 0

| -sin(h)0 cos(h)

1 0 0

P = 0 cos(p) -sin(p)

0 sin(p) cos(p)

cos(b) sin(b) 0

B = -sin(b) cos(b) 0 The vector w is rotated using the above matrices to attain w' like such" w' = H*P*B*w The final step is converting from rectangular to spherical coordinates. Denoting the 3 components of the vector w" as x, y, z, then the conversion is: s = atan2(x, z) t = atan2(y, sqrt(x*x + z*z)) Note: atan2(a, b) is a standard C-function very similar to atan(a/b), but atan2 correctly handles the different cases that arise if a or b is negative or if b is 0.

Optionally, the viewer may predict the next key-frame to be loaded (depending on user travel direction and speed), and pre-load this key frame in order to increase performance.

Due to the one to one ratio of key frames to possible user positions, there exists an exact correlation between frame rate and user motion speed. If the user is currently moving through the environment, every frame displayed is a new key frame, thus the faster the frame rate, the faster the user travels. For this reason, the frame rate is "capped" during user travel to eliminate the problem of excessive user travel speed. In order to retain smooth motion, the frame rate is not decreased to below standard video frame rates (15 frames/sec.) The frame rate is not increased in order to keep the relative spacing of key frames to a manageable distance; the faster the frame rate, the closer the key frames must be to achieve the same user travel speed. The viewer may optionally skip key-frames in order to increase the user's travel speed through the environment. The more key-frames skipped, the faster the user will travel; if no key-frames are skipped, the user will travel at the slowest possible rate (given a constant frame rate.)

The system can link pan movie segments so as to permit branching and thereby follow a path selected by a user. Multiple linear (one dimensional) pan movies may be linked together to create a "graph" of pan movies (see appendix B). For each pan movie, the end of one segment may be associated with the start of a "next" pan movie. This association (in conjunction with the length of the individual pan movies) is the basis for the graph shape. In order to achieve smooth transitions, the "last" frame in the "first" pan movie must be the same as (or one frame off from) the "first" frame of the "next" pan movie. In addition to positional correctness, the relative view orientations of the joining frames must be known. For example, if the "last" frame of the "first" pan movie faces "north", and the "first" frame of the "next" Pan Movie faces "east", then the viewing software must be alerted to this orientation change. Without this information, there would be a 90 degree "snap" in the transition between the two Pan Movies. All this graph information may be stored in a separate file (text or binary form.)

The audio information associated with each frame of a pan movie must take into account the fact that a viewer of a pan movie has a great deal of control over what is presented on the screen. In addition to the ability to select branch points a user may choose to change the direction of view or to stop and backup. The audio information associated with each key frame must accommodate this flexibility.

As illustrated in Figure 11 , the audio information stored with each key frame includes five audio tracks designated A, B, C, D, E and control information. Figure 1 1 shows eight key frames Fa to Fi each of which has five associated audio tracks and a control field. Audio track A is the track that is played if the pan movie is moving forward in the normal direction at the normal rate of thirty frames per second. Audio track B is the track that is played if the pan movie is being displayed in reverse direction. Audio track C is the audio track that is played if the movie is moving forward at half speed. Audio track D is the track that is played if the movie is being played in the reverse direction at one half speed. Finally audio track E is the track that is repeatedly played if the movie has stopped at one frame. Naturally a variety of other audio tracks could be added for use in a number of other situations. For example, tracks can point to audio clips or to other audio tracks.

The control information that is recorded with each frame controls certain special effects. For example the control information on one frame can tell the program to continue playing the audio tracks from the following frame even if the user has stopped the movie at one particular frame. As the sound track on each frame is played, the control information on that frame is interrogated to determine what to do next. What sound is played at any particular time is determined by a combination of the control information on the particular frame being viewed and the action being taken by the viewer at that time. From a programming point of view, the commands associated with each rack are de-compressed and read when the view window for the associated frame is de-compressed and read. As a particular view window is being displayed (or slightly before) the commands stored in the control field are read and executed so that the appropriate sound can be de-compressed and played when the view window is displayed.

For example the control information could provide the following types of commands: Stop this audio track if user stops pan movie here (typical setting). If this is not set the audio will continue playing in same direction until audio for this track ends

Start or continue to play this audio track if user is viewing pan movie in forward direction (typical setting)

Start or continue to play this audio track backwards if user if viewing pan move in a backwards direction, (note if the same audio information is played is reverse it may be distorted)

Start this audio track when image frames are in motion and being played in a reverse direction. This allows high quality audio to be played while reverse viewing

Continue audio track from / on other file structure (branch most likely has occurred) modify volume This is used to fade out an audio track that may have played ahead earlier

Stop all audio tracks

Stop this audio track if user slows pan movie playback

Start audio file X: where X is a conventional audio file that is separate from the pan movie. A wide variety of other commands may be implements as desired by the designer of a particular movie.

The audio information can be recorded with a normal recorder when the initial images are recorded or it can be recorded separately. The audio data is merged with the key frames by computer 21. This can be done manually on a frame by frame basis or the process can be automated. When the sound is merged with the key frames the appropriate control information is added.

Figures 12A, 12B and 12C illustrate another aspect of the present invention. A hot spot on a key frame can contain and display information that is independent from, and in addition to the information in the base images which are used to form the panoramas. For example, as a pan movie simulates movement past a billboard, a "regular" motion picture (which might for example be an advertisement for a product) can be displayed on the billboard. The motion picture on the billboard would be integrated with the various key frames in the same manner as hot spots are added to key frames. As illustrated in Figure 12A, 12B and 12C, such images displayed on a billboard passed which motion is simulated must be corrected for the fact that the viewer is not directly viewing the image when he is approaching it. The image is only rectangular when the viewer is adjacent the image as shown in Figure 12C. As the viewer is approaching the image it is distorted as illustrated in Figures 12A and 12B.

The attached appendices provide computer programs which implement various aspects of the present invention. These programs are designed to run under a conventional operating system such as the "Windows" operating system marketed by the Microsoft Corporation.

The program given in Appendix A will retrieve frames for a move, correct the perspective in accordance with known equations and then display the images of the movie in sequence.

Appendix B is an example of a link control file for the frames of a pan movie. Appendix C is pseudocode showing how sequences of images are linked to form a pan movie. It is noted that in a pan movie the frames do not all have to have the same resolution. Some frames may be of a higher resolution. For example, at the most interesting places in the Pan Movie may have a higher resolution.

Many alternative embodiments of the invention are possible. For example, the initial capture process could record the images on video tape rather than recording the images digitally. Electronic cameras could be used which include image capture devices other than CCD arrays to capture images. Branching can provide three or more optional paths rather than just two pats as shown in Figure 4; and branching can provide for going left or right at an intersection.

It is noted that in alternative embodiments, compression schemes or techniques other than Intel Indio can be used. Furthermore, alternative embodiments could use no compression at all if enough storage and bandwidth were available.

While in the embodiment shown the images files are manually transferred between some of the units in the embodiment shown, in alternative embodiments these files could be transferred between units by electronic connections between the units.

While in the embodiment described above the camera has six lenses which record all six sides of the cube, in alternative embodiments the camera could record less than an entire sphere. For example the lens pointing down could be eliminated in some embodiments. Still other alternative embodiments could use lenses with wider or narrower fields of view. For example less lenses each with a wider field of view could be used. Furthermore, while the embodiment described above utilizes spherical panorama, other types of panoramas could be used. Various types of projections such as cubic could be used instead of equi-rectangular.

The embodiment shown includes a number of sound tracks with each key frame and control information which indicates which sound track should be played when the key frame is displayed depending on whether or not certain special conditions exist. Alternatively, there could be a single sound track associated with each frame. In such an embodiment the single sound track on each key frame could be the sounds recorded when the images is the particular frame were recorded. In other alternatively embodiments, there could be no sound tracks and in such case the images would be displayed without accompanying sound.

Having described and illustrated the principles of the invention in various embodiments thereof, it should be apparent that the invention can be modified in arrangement and detail without departing from the principles of the invention. We claim all modifications and variation coming within the spirit and scope of the following claims.

APPENDIX A FRAME RETRIEVAL CODE

#ιnclude "windows h" #ιnclude "mmsystem h" #ιnclude "vfw h" #ιnclude "vfw_spec h" #defιne S_BMIH sιzeof(BITMAPINFOHEADER) // Externally declared (and allocated) variables extern UINT currentFrameNumber, // Current Pan Movie file frame number (user position) extern HANDLE hFile, // Open file handle of Pan Movie file extern HIC hie, // Open IC handle (installed compressor) extern DWORD Index, // Pan Movie Frame Index (read from file at load extern LPBITMAPINFOHEADER viewFrame, // Buffer large enough to hold image the size of the display window extern LPBITMAPINFOHEADER panFrame, // Buffer large enough to hold largest uncompressed frame extern LPBITMAPINFOHEADER compressedFrame, // Buffer large enough to hold largest compressed frame // Function prototypes extern void VιewToPan(ιnt viewWidth.int viewHeightint panWidth.int panHeight.float heading, float pitch, float bank,float zoom, POINT ^*poιnt), static LPBITMAPINFOHEADER RetπevePanFrame(ιnt frameNumber.RECT ^*vιewRect), // // This function generates a <img file="EP1099343A2_D0001.tif" /> correct bitmap image given a user view orientation and travel speed // static LPBITMAPINFOHEADER RetπeveVιewFrame(float userHeading.float userPitch, float userBank, float userZoom.int userTravelSpeed) { // Determine Decode BoundingBox POINT point, RECT localDecompressionRect, // Upper left corner of viewFrame point x = 0, point y = 0, VιewToPan(vιewFrame-&gt;bιWιdth,vιewFrame-&gt;bιHeιght,panFrame-&gt;bιWιdth,panFrame-&gt;bιHeι ghtuserHeadmg.userPitch, userBank, userZoom.&amp;point), localDecompressionRect top = point y, localDecompressionRect left = point x, // Upper right corner of viewFrame point x = vιewFrame-&gt;bιWιdth-1 , point y = 0, VιewToPan(vιewFrame-&gt;bιWιdth,vιewFrame-&gt;bιHeιght,panFram^p-&gt;bιWιdth,panFrame-&gt;bιHeι ght,userHeadιng,userPιtch, userBank, userZoom.&amp;point), localDecompressionRect top = mιn(localDecompressιonRect top, point y), localDecompressionRect right = point x, // Lower left corner of viewFrame point x = 0, point y = vιewFrame-&gt;bιHeιght-1 , VιewToPan(vιewFrame-&gt;bιWιdth,vιewFrame-&gt;bιHeιght,panFrame-&gt;bιWιdth,panFrame-&gt;bιHeι ght,userHeadιng,userPιtch,userBank,userZoom,&amp;poιnt), localDecompressionRect bottom= point y, localDecompressionRect left = mιn(localDecompressιonRect left.point x), // Lower right corner of viewFrame point x = vιewFrame-&gt;bιWιdth-1 , point y = vιewFrame-&gt;bιHeιght-1 , VιewToPan(vιewFrame-&gt;bιWιdth,vιewFrame-&gt;bιHeιght,panFrame-&gt;bιWιdth,panFrame-&gt;bιHeι ght,userHeadιng,userPιtch,userBank,userZoom,&amp;poιnt), localDecompressionRect bottom= max(localDecompressιonRect bottom, point y), localDecompressionRect right = max(localDecompressιonRect πghtpoint x), // Get Pan Frame (or "userDecompressionRect" portion thereof) currentFrameNumber += userTravelSpeed, // userTravelSpeed is negative if traveling backwards LPBITMAPINFOHEADER pFrame = RetπevePanFrame(currentFrameNumber,&amp;localDecompressιonRect), ιf(ρFrame == NULL) { currentFrameNumber -= userTravelSpeed, return NULL, } // A very slow warping routine (assumes 24-bιt pixels) LPBYTE srcPixels = ((LPBYTE)pFrame) + S_BMIH, LPBYTE dstPixels = ((LPBYTE)vιewFrame) + S_BMIH, for(ιnt y = 0, y &lt; vιewFrame-&gt;bιHeιght, y++) { for(ιnt x = 0, x &lt; vιewFrame-&gt;bιHeιght, x++) { point y = y, point x = x, VιewToPan(vιewFrame-&gt;bιWιdth,vιewFrame-&gt;bιHeιght,pFrame-&gt;bιWιdth,pFrame-&gt;bιHeιght,u serHeadιng,userPιtch,userBank,userZoom,&amp;poιnt), memcpy(&amp;dstPιxels[3^*(x + y^*vιewFrame-&gt;bιWιdth)],&amp;srcPιxels[3^*(poιnt x + point y*pFrame-&gt;bιWιdth)],3), // supports 24-Bιt Pixels only } } return viewFrame, } // // This function reads and decompresses a Pan Frame bitmap image from a Pan Movie file // static LPBITMAPINFOHEADER RetπevePanFrame(ιnt frameNumber,RECT ^*vιewRect) { DWORD d, UINT frameSιze= lndex[frameNumber+1]-lndex[frameNumber], // Set the file pointer to the start of the requested frame and read in the bitmap header SetFιlePoιnter(hFιle,lndex[frameNumber],NULL,FILE_BEGIN), ReadFιle(hFιle,panFrame,S_BMIH,&amp;d,NULL), ιf(panFrame-&gt;bιCompressιon == 0) { // Uncompressed frame (read rest of frame and return) ReadFιle(hFιle,((BYTE*)panFrame)+S_BMIH,frameSιze-S_BMIH,&amp;d,NULL), return panFrame, } // Read the remainder of the compressed frame *compressedFrame = ^*panFrame, ReadFιle(hFιle,((BYTE^*)compressedFrame)+S_BMIH,frameSιze-S_BMIH,&amp;d,NULL), // Set up decompressed bitmap header panFrame-&gt;bιCompressιon = 0, panFrame-&gt;bιSιzelmage = 0, panFrame-&gt;bιBιtCount = 24, panFrame-&gt;bιClrUsed = 0, LPBITMAPINFOHEADER biSrc = compressedFrame, LPBITMAPINFOHEADER biDst = panFrame, LPBYTE srcPixels = (BYTE*)bιSrc + S_BMIH, LPBYTE dstPixels = (BYTE*)bιDst + S_BMIH, // If the frame is compressed with Intel Indeo 4 and a local rect was requested, then perform local decompression ιf(vιewRect &amp;&amp; bιSrc-&gt;bιCompressιon == mmιoFOURCC(Y,V,'4', )) { // Intel Indeo 4 1 R4_DEC_FRAME_DATA Statelnfo, memset(&amp;Statelnfo,0,sιzeof(R4_DEC_FRAME_DATA)), Statelnfo dwSize = sιzeof(R4_DEC_FRAME_DATA), Statelnfo dwFourCC = bιSrc-&gt;bιCompressιon, Statelnfo dwVersion = SPECIFIC_INTERFACE_VERSION, Statelnfo mtType = MT_DECODE_FRAME_VALUE, Statelnfo oeEnvironment = OE_32, Statelnfo dwFlags = DECFRAME_VALID | DECFRAME_DECODE_RECT, Statelnfo rDecodeRect dwX = mιn(vιewRect-&gt;left,vιewRect-&gt;πght), Statelnfo rDecodeRect dwY = mιn(vιewRect-&gt;top,vιewRect-&gt;bottom), Statelnfo rDecodeRect dwWidth = abs((vιewRect-&gt;πght-vιewRect-&gt;left))+1 , Statelnfo rDecodeRect dwHeιght= abs((vιewRect-&gt;bottom-vιewRect-&gt;top))+1 , ICSetState(hιc,&amp;Statelnfo,sιzeof(R4_DEC_FRAME_DATA)),

ιf(ICDecompressEx(hιc,0,bιSrc,srcPιxels,0,0,bιSrc-&gt;bι\Λ/ιdth,bιSrc-&gt;bιHeιght,bιDst,dstPιxels,0, 0,bιDst-&gt;bιWιdth,bιDst-&gt;bιHeιght) 1= ICERR_OK ) return NULL, } else { // Decompress entire frame ιf(ICDecompressEx(hιc,0,bιSrc,srcPιxels,0,0,bιSrc-&gt;bιWιdth,bιSrc-&gt;bιHeιght,bιDst,dstPιxels,0, 0,bιDst-&gt;bιWιdth,bιDst-&gt;bιHeιght) ι= ICERRJ3K ) return NULL, } return panFrame, }

© Infinite Pictures 1998

APPENDIX B SAMPLE PAN MOVIE LINK CONTROL FILE &lt; &gt; &lt;- C I B -&gt; I I I I A I I [Segment-A (start)] Fιle= "A pan" North= 0 [Segment-A (end)] Fιle= "A pan" North= 0 Link 90= "Segment-B (start)" Link 270= "Segment-C (start)" [Segment-B (start)] Fιle= "B pan" North= 90 Link 90= "Segment-A (end)" Link 180= "Segment-C (start)" [Segment-B (end)] Fιle= "B pan" North= 90 [Segment-C (start)] Fιle= "C pan" North= 270 Link 270= "Segment-A (end)" Link 180= "Segment-B (start)" [Segment-C (end)] Fιle= "C pan" North= 270 © Infinite Pictures 1998

APPENDIX C PSEUDOCODE FOR LINKED PAN MOVIES (VIA CONTROL FILE)

GLOBAL FILE controlFile // Control file GLOBAL STRING currentSegment // The name of the current pan movie segment GLOBAL INTEGER currentFrameNumber // The current frame number of the current Pan Movie GLOBAL INTEGER currentHeadmg // The current user view horizontal pan orientation // // This function will read the control file and determine which linked segment is closest // to the current user heading orientation // It will also determine the new frame number of the new segment // BOOLEAN RetrιeveLιnk() { INTEGER mmAngle STRING nextSegment if currentFrameNumber == 0 currentSegment = currentSegment + (start) else currentSegment = currentSegment + (end) if no links in section currentSegment of controlFile return FALSE mmAngle = link angle closest to currentHeadmg nextSegment = GetStπng(mιnAngle) if AngleDιfference(currentHeadιng, MmAngle) &gt; 45 degrees return FALSE, INTEGER nextNorth = GetNorth(nextSegment) INTEGER currentNorth = GetNorth(currentSegment) currentHeadmg = currentHeadmg + (nextNorth - currentNorth) currentSegment = nextSegment if stπngFιnd(currentSegment,"(end)") currentFrameNumber = -1 else currentFrameNumber = 0 return TRUE }

© Infinite Pictures 1998