The present invention relates to a method of storing a virtual image from space data generated based on actually captured data, a method of rendering a virtual space on the basis of stored space data, and apparatuses therefor and, more particularly, to progressive storage and rendering of the space data.
The present invention also relates to a virtual image rendering method that downloads large-size image data such as ray space data (to be abbreviated as RS data hereinafter), and presents the downloaded data to the user, and a rendering apparatus.
Many schemes that describe and express a virtual space on the basis of actually captured images in place of a description based on three-dimensional geometric models have been proposed. Such schemes are called Image Based Rendering (to be abbreviated as IBR hereinafter), and are characterized in that they can express a virtual space with high reality, which cannot be obtained by a scheme based on three-dimensional geometric models, since these schemes are based on actually captured images.
Attempts to describe a virtual space on the basis of a ray space theory as one of IBR schemes have been proposed. See, for example, xe2x80x9cImplementation of Virtual Environment by Mixing CG model and Ray Space Dataxe2x80x9d, IEICE Journal D-11, Vol. J80-D-11 No. 11, pp. 3048-3057, November 1997, or xe2x80x9cMutual Conversion between Hologram and Ray Space Aiming at 3D Integrated Image Communicationxe2x80x9d, 3D Image Conference, and the like.
The ray space theory will be explained below.
As shown in FIG. 1, a coordinate system 0-X-Y-Z is defined in a real space. A light ray that passes through a reference plane P (Z=z) perpendicular to the Z-axis is defined by a position (x, y) where the light ray crosses P, and variables xcex8 and xcfx86 that indicate the direction of the light ray. More specifically, a single light ray is uniquely defined by five variables (x, y, z, xcex8, xcfx86). If a function that represents the light intensity of this light ray is defined as f, light ray group data in this space can be expressed by f(x, y, z, xcex8, xcfx86). This five-dimensional space is called a xe2x80x9cray spacexe2x80x9d. Generally, a time variation t is also used in some cases, but is omitted here.
If the reference plane P is set at z=0, and disparity information of a light ray in the vertical direction, i.e., the degree of freedom in the xcfx86 direction is omitted, the degree of freedom of the light ray can be regenerated to two dimensions (x, xcex8). This x-xcex8 two-dimensional space is a partial space of the ray space. As shown in FIG. 3, if u=tan xcex8, a light ray (FIG. 2) which passes through a point (X, Z) in the real space is mapped onto a line in the x-u space, which line is given by:
X=x+uxc2x7Zxe2x80x83xe2x80x83(1)
Image sensing by a camera reduces to receiving light rays that pass through the lens focal point of the camera by an image sensing surface, and converting their brightness levels and colors into an image. In other words, a light ray group which passes through one point, i.e., the focal point position, in the real space is captured as an image in correspondence with the number of pixels. In this way, since the degree of freedom in the xcfx86 direction is omitted, and the behavior of a light ray is examined in only the X-Z plane, only pixels on a line segment that intersects a plane perpendicular to the Y-axis need only be considered. In this manner, by sensing an image, light rays that pass through one point can be collected, and data on a single line segment in the x-u space can be captured by single image sensing.
When this image sensing is done a large number of times by changing the viewpoint position (in this specification, the viewpoint position includes both the position of the viewpoint and the line-of-sight direction unless otherwise specified), light ray groups which pass through a large number of points can be captured. When the real space is captured using N cameras, as shown in FIG. 4, data on a line given by:
x+Znu=Xnxe2x80x83xe2x80x83(2)
can be input in correspondence with a focal point position (Xn, Zn) of the n-th camera (n=1, 2, . . . , N), as shown in FIG. 5. In this way, when an image is captured from a sufficiently large number of viewpoints, the x-u space can be densely filled with data.
Conversely, an observation image from a new arbitrary viewpoint position can be generated (FIG. 7) from the data of the x-u space (FIG. 6). As shown in FIG. 7, an observation image from a new viewpoint position E(X, Z) indicated by an eye mark can be generated by reading out data on a line given by equation (1) from the x-u space.
However, the above prior art makes arithmetic operations for converting all pixels of an actually captured image into ray space groups. That is, if there are E actually captured images each having mxc3x97n pixels, the pixels are converted into light ray groups via Exc3x97mxc3x97n computations, resulting in a very large computation volume. Especially, when a ray space group is mapped in the ray space to maintain the resolution of an input image and the RS data is quantized, the quantized data size also becomes huge.
It is an object of the present invention to provide a RS data storage method and apparatus, which allow progressive display of RS data of a target object.
It is another object of the present invention to provide a method and apparatus for displaying progressively stored space data.
Actually captured image data like the aforementioned RS data is compressed and stored in an external storage device or the like for each unit (e.g., for each object). Therefore, in order to render such space data in a virtual space, the data must be downloaded onto a main storage device, decoded, and rendered on the main storage device. On the other hand, the user can recognize a given virtual space only after virtual images of all virtual objects to be rendered in that virtual space are displayed. Therefore, when there are a plurality of objects to be rendered, the user cannot recognize such virtual objects until space data of all these objects are downloaded, decoded, and rendered. That is, when the user wants to walk through such virtual space, a rendering apparatus with poor response is provided.
This is the second problem of the prior art upon handling space data such as RS data.
The third problem of the prior art results from the fact that actually captured image data such as RS data or the like contain a large volume of data. It is a common practice to store such data at a location separated from an image processing apparatus in the form of a database. For this reason, when the image processing apparatus maps a virtual image in a virtual space, a large volume of space data must be downloaded into the image processing apparatus in advance. Owing to the huge size of actually captured image data, the turn around time from when space data is requested until that space data is ready to be rendered in the image processing time is not so short, although the communication speed is improving recently. Under these circumstances, the user must be prevented from being bored during the wait time until actually captured image data is ready for use in such system that presents a virtual space to him or her. That is, during this wait time, a billboard image (a single image) with a short download time is displayed instead, although a scene from an arbitrary viewpoint position cannot be obtained.
The fourth problem of the prior art occurs when a walk-through system which allows the user to freely walk through a virtual space using actually captured image data such as RS data has a limited memory size. That is, in order to combat the aforementioned second problem, a technique for segmenting a virtual space into a plurality of subspaces (e.g., in case of a virtual art museum, each exhibition room forms one subspace) can be proposed.
More specifically, when it is detected that the user is about to approach a given exhibition room, space data of that exhibition room is prefetched to shorten the time required for transfer prior to rendering. Furthermore, when the user is about to leave that exhibition room (subspace A), space data for the next subspace (e.g., exhibition room B) must be overwritten and stored on the memory area that stored space data of exhibition room A so far. In this manner, virtual subspaces of exhibition rooms can be reproduced in turn in nearly real time even by a relatively small memory size.
This prefetch start timing is determined depending on whether or not the viewpoint position of the user approaches a target subspace. However, since the user""s viewpoint position moves using a mouse or the like without any high-precision route guide, the user may often be guided to a wrong route. That is, when it is erroneously detected that the user""s viewpoint position which does not reach a prefetch start zone has reached that zone, the system starts prefetch. Especially, when the user""s viewpoint position moves near the prefetch start zone, such operation error readily occurs. For example, as shown in FIG. 32, when the viewpoint position moves from the exhibition room space into the prefetch start zone and returns to the exhibition room space again, if the aforementioned wrong prefetch starts, large-size space data for the exhibition room space is purged (deleted), and the system must re-transfer the data of the exhibition room space to xe2x80x9creturnxe2x80x9d to the exhibition room space (since this situation takes place due to a detection error of the viewpoint position, the user has no actual sense of returning), resulting in time-consuming operation.
The present invention is directed to solving the third problem.
It is still another object of the present invention to provide an image rendering method and apparatus, which can render space data stored in an internal memory, as needed, under the condition that space data in an external memory is rendered using at least two space data, one of which is stored in the external memory, and the other of which is stored in the internal memory.
In order to achieve the above objects, an image storage method for storing space data which includes real image data of an actually captured image in association with a predetermined space different from a real image space, comprises:
the first layer dividing step of hierarchically dividing the real image data into layers in accordance with resolutions;
the second layer dividing step of hierarchically dividing a map that represents correspondence between the real image space and the predetermined space into layers in accordance with resolutions, the resolutions of the divided layers corresponding to resolutions of the layers divided in the first layer dividing step; and
the step of storing obtained hierarchical image data from the first layer dividing step and hierarchical map data from the second layer dividing step in a storage device as the space data.
According to claim 2 as a preferred aspect of the present invention, the space data is RS data.
According to claim 3 as a preferred aspect of the present invention, the layers and resolutions are set in ascending or descending order.
According to claim 4 as a preferred aspect of the present invention, each of the first and second layer dividing steps includes the step of performing a data decimation process.
According to claim 5 as a preferred aspect of the present invention, the second layer dividing step includes the block segmentation step of segmenting the map data into a plurality of blocks in correspondence with a block having a size set in correspondence with the number of divided layers.
The map of space data includes address information. In the process of dividing map data into layers, this address information must also be appropriately converted. Hence, according to claim 6 as a preferred aspect of the present invention, the second layer dividing step uses converted address ni given by:
ni=[njxe2x88x921/2pxe2x88x92i]
where p is the number of divided layers, i is a layer to be processed, and nj is the storage address of map data of the i-th layer.
According to a preferred aspect of the present invention, if the block size is Nxc3x97N, the block segmentation step sets:
N=2pxe2x88x921 
where p is the number of divided layers. By satisfying this condition, hierarchization is simplified.
Hierarchical space data stored by the method of the present invention are effective in terms of progressive display at the time of rendering. Hence, according to a preferred aspect of the present invention, an image rendering method for rendering hierarchical in a virtual space, comprises:
the step of reading hierarchical space data of respective layers in ascending order of resolution; and
the rendering step of rendering a virtual image in the order the hierarchical space data is read.
According to a preferred aspect of the present invention, the method further comprises the detection step of detecting a user""s viewpoint position, and the rendering step includes the step of rendering a virtual image on the basis of the detected viewpoint position.
In order to render a virtual image still faster, objects to be rendered can be limited. Hence, according to another method of the present invention, the reading step includes the step of reading hierarchical space data of a space near the detected viewpoint position.
The above objects are also achieved by providing a storage medium that stores a program for implementing the aforementioned storage or rendering method on a computer.
According to a preferred aspect of the present invention, the present invention is a computer that mounts a storage medium.
Furthermore, the above objects are achieved by an image storage apparatus or image processing apparatus.
The above objects are also achieved by a image downloading method for downloading space data which is formed based on image data of an actually captured image in association with a predetermined space different from a real image space. That is, this method comprises:
the first layer dividing step of hierarchically dividing real image data in the space data into layers in accordance with resolutions; and
the downloading step of downloading obtained hierarchical image data, and a map that represents correspondence between the real image space and the predetermined space to an external apparatus.
According to a preferred aspect of the present invention, the method further comprises the second layer dividing step of hierarchically dividing the map into layers in accordance with resolutions, and
the downloading step includes the step of downloading the obtained hierarchical image data and hierarchical map data.
According to a preferred aspect of the present invention, the resolutions of the respective layers of the map are set in correspondence with resolutions of the respective layers divided in the first layer dividing step.
According to a preferred aspect of the present invention, the resolutions increase in an order the data are downloaded.
According to a preferred aspect of the present invention, the first layer dividing step includes the step of dividing the image data to make hierarchical image data of a first layer include real image data at a pixel position common to the respective layers, and hierarchical data of a second layer as a layer higher than the first layer not include the real image data at the common pixel position.
According to a preferred aspect of the present invention, the external apparatus merges the hierarchical image data of the first and second layers.
According to a preferred aspect of the present invention, the actually captured image data and space data are stored in an image database, which executes the first layer dividing step in response to a downloading request from the external apparatus.
The above objects are also achieved by the following image processing method. That is, this method comprises:
the step of converting input image data into space data that pertains to a predetermined space coordinate system different from an image space coordinate system of the input image data;
the first layer dividing step of hierarchically dividing the space data into layers in accordance with resolutions;
the step of generating a map that represents correspondence between image data in the image space coordinate system and space data in the predetermined space;
the second layer dividing step of hierarchically dividing the map into layers in accordance with resolutions;
the step of storing obtained hierarchical space data and hierarchical map data in a storage device; and
the image generation step of generating an image on the basis of the hierarchical space data and hierarchical map data.
According to a preferred aspect of the present invention, the resolutions of the respective layers divided by the second layer dividing step are set to correspond to the resolutions of the respective layers divided in the first layer dividing step.
According to a preferred aspect of the present invention, the layers and resolutions are set in ascending or descending order.
According to a preferred aspect of the present invention, each of the first and second layer dividing steps includes the step of performing a data decimation process.
According to a preferred aspect of the present invention, the second layer dividing step includes the block segmentation step of segmenting the map data into a plurality of blocks in correspondence with a block having a size set in correspondence with the number of divided layers.
The map of space data includes address information. In the process of dividing map data into layers, this address information must also be appropriately converted. Hence, the second layer dividing step uses converted address ni given by:
xe2x80x83ni=[njxe2x88x921/2pxe2x88x92i]
where p is the number of divided layers, i is a layer to be processed, and nj is the storage address of map data of the i-th layer.
According to a preferred aspect of the present invention, if the block size is Nxc3x97N, the block segmentation step sets:
N=2pxe2x88x921 
where p is the number of divided layers. By satisfying this condition, hierarchization is simplified.
According to a preferred aspect of the present invention, the method further comprises:
the step of reading hierarchical space data of respective layers in ascending order of resolution; and
the rendering step of rendering a virtual image in the order the hierarchical space data is read.
According to a preferred aspect of the present invention, the method further comprises the detection step of detecting a user""s viewpoint position, and the rendering step includes the step of rendering a virtual image on the basis of the detected viewpoint position.
In order to render a virtual image still faster, objects to be rendered can be limited. Hence, according to another method of the present invention, the reading step includes the step of reading hierarchical space data of a space near the detected viewpoint position.
The above objects are also achieved by providing a storage medium that stores a program for implementing the aforementioned processing method on a computer.
Furthermore, the above objects are also achieved by the following image processing apparatus. That is, this apparatus comprises:
means for converting input image data into space data that pertains to a predetermined space coordinate system different from an image space coordinate system of the input image data;
first layer dividing means for hierarchically dividing the space data into layers in accordance with resolutions;
means for generating a map that represents correspondence between image data in the image space coordinate system and space data in the predetermined space;
second layer dividing means for hierarchically dividing the map into layers in accordance with resolutions;
means for storing obtained hierarchical space data and hierarchical map data in a storage device; and
image generation means for generating an image on the basis of the hierarchical space data and hierarchical map data.
According to a preferred aspect of the present invention, the resolutions of the respective layers divided by the second layer dividing means are set to correspond to the resolutions of the respective layers divided by the first layer dividing means.
According to a preferred aspect of the present invention, the layers and resolutions are set in ascending or descending order.
According to a preferred aspect of the present invention, each of the first and second layer dividing means performs a data decimation process.
According to a preferred aspect of the present invention, the second layer dividing means includes block segmentation means for segmenting the map data into a plurality of blocks in correspondence with a block having a size set in correspondence with the number of divided layers.
The map of space data includes address information. In the process of dividing map data into layers, this address information must also be appropriately converted. Hence, according to a preferred aspect of the present invention, the second layer dividing means uses converted address ni given by:
ni=[njxe2x88x921/2pxe2x88x92i]
where p is the number of divided layers, i is a layer to be processed, and nj is the storage address of map data of the i-th layer.
According to a preferred aspect of the present invention, if the block size is Nxc3x97N, the block segmentation means sets:
N=2pxe2x88x921 
where p is the number of divided layers. By satisfying this condition, hierarchization is simplified.
According to a preferred aspect of the present invention, the apparatus further comprises:
means for reading hierarchical space data of respective layers in ascending order of resolution; and
rendering means for rendering a virtual image in the order the hierarchical space data is read.
According to a preferred aspect of the present invention, the apparatus further comprises detection means for detecting a user""s viewpoint position, and the rendering means renders a virtual image on the basis of the detected viewpoint position.
In order to render a virtual image still faster, objects to be rendered can be limited. Hence, according to the apparatus of the present invention, the reading means reads hierarchical space data of a space near the detected viewpoint position.
According to the present invention, an rendering method for rendering a virtual image viewed from an arbitrary viewpoint position in a virtual space, comprises the steps of:
storing first space data in a first format at a first viewpoint position in an internal memory;
storing second space data in a second format at the first viewpoint position in an external memory;
downloading the second space data from the external memory to generate a virtual image at an arbitrary viewpoint position; and
rendering the virtual image at the arbitrary viewpoint position on the basis of the first space data in the internal memory before downloading is completed, and on the basis of the second space data downloaded into the internal memory after downloading is completed.
The second space data that must be downloaded is huge space data and may often be difficult to reside on the internal memory. Before such second space data is downloaded, a virtual image is rendered on the basis of the first space data in the internal memory, thus preventing the user from being disturbed by an image non-display period, and efficiently using an expensive internal memory.
Note that the first space data is space data which is optimal to form a billboard image.
On the other hand, the first space data is VRML space data which has a small size but is inferior to the second space data in terms of precision and resolution, and the second space data is RS data which requires a large size but is superior to the first space data in terms of precision and resolution.
According to a preferred aspect of the present invention, this rendering method provides a virtual walk-through environment to a user in the virtual space.
The first space data also requires a relatively large size. It is preferable to store such first space data in the external memory. Hence, according to a preferred aspect of the present invention, the first space data is stored in the external memory, and downloading of the first space data to the internal memory is completed before downloading of the second space data.
For example, in the walk-through environment, a virtual space is made up of a plurality of subspaces. That is, the second space data is comprised of a plurality of units of space data.
Hence, according to a preferred embodiment of the present invention, the method further comprises steps of:
storing space data of a plurality of images captured in advance from a plurality of different viewpoint positions in the external memory as the second space data;
detecting a user""s viewpoint position which moves; and
executing a rendering process of an image at a viewpoint position after movement, and a download process of the second space data as parallel processes. In this specification, this method is implemented by the first example of the second embodiment.
On the other hand, in another embodiment, the method further comprises the steps of:
storing space data of a plurality of images captured in advance from a plurality of different viewpoint positions in the external memory as the second space data;
detecting a user""s viewpoint position which moves;
downloading space data corresponding to a viewpoint position after movement from the external memory; and
rendering a virtual image on the basis of the first space data in the internal memory before downloading is completed, and on the basis of the second space data which has been downloaded into the internal memory and corresponds to the viewpoint position after movement after downloading is completed. In this specification, this method is implemented by the second example of the second embodiment.
According to a preferred aspect of the present invention, the internal memory has a capacity for storing at least the first and second space data.
Note that the objects of the present invention can also be achieved by a rendering apparatus described in claim 60 and the like.
Furthermore, the objects of the present invention can also be achieved by a rendering method for rendering a virtual image at an arbitrary viewpoint position in a virtual space, according to the present invention, comprising the steps of:
rendering first space data in a first data format and second space data in a second data format at an arbitrary viewpoint position as virtual images; and
mapping the virtual image based on the first space data in the virtual space when rendering of the virtual image based on the second space data does not end in time before mapping in the virtual space.
Other features and advantages of the present invention will be apparent from the following description taken in conjunction with the accompanying drawings, in which like reference characters designate the same or similar parts throughout the figures thereof.