Image analysis – Image compression or coding – Transform coding
Reexamination Certificate
2000-08-31
2004-06-29
Couso, Jose L. (Department: 2621)
Image analysis
Image compression or coding
Transform coding
Reexamination Certificate
active
06757441
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to an image data encoding/decoding method and apparatus and, more particularly, to an encoding/decoding method and apparatus which can decode encoded image data in units of pixels.
BACKGROUND OF THE INVENTION
As a conventional method of generating a three-dimensional image at an arbitrary viewpoint position, a method of expressing a three-dimensional object by a plurality of small triangular planes (polygons), and computing the luminance values of respective polygons on the basis of a given viewpoint is well known.
However, as the shape of a three-dimensional object becomes complicated, it becomes harder to express the object using polygons. In such case, even when smaller polygons are used, visual disturbance cannot be eliminated. As polygons becomes smaller, the data volume for expressing the object and the computation volume required for generating a three-dimensional image at an arbitrary viewpoint increase.
On the other hand, as a method of generating a three-dimensional image, in which the data volume does not depend on the object shape, a method using a ray space is known. This method is one of methods for generating and displaying an image at an arbitrary viewpoint position using a group of images actually captured at a plurality of viewpoint positions, and is based on the ray space concept that defines a three-dimensional object as a set of light rays propagating in a three-dimensional space.
According to this concept, since an image of a three-dimensional object viewed from an arbitrary viewpoint is generated by computing the luminance values of pixels that form a visible area of the three-dimensional object, the computation volume upon expressing the object depends only on the number of pixels that express the visible area and does not depend on its shape. Since the shape can be expressed by pixels, an image of even an object with a complicated shape can be accurately reconstructed. In addition, since actually captured images are used, a virtual space with high reality, which cannot be obtained by a method based on three-dimensional geometric models can be expressed.
The concept of a ray space will be further explained below. In a three-dimensional space, light rays coming from a light source, light rays reflected by objects, and the like exist. A light ray that passes through a given point in the three-dimensional space is uniquely defined by five variables that express its position (x, y, z) and direction (&thgr;, &phgr;). If a function that represents the light intensity of this light ray is defined as f, light ray group data in the three-dimensional space can be expressed by f(x, y, z, &thgr;, &phgr;). Furthermore, if a change over time in light ray group data is taken into consideration, that group data is expressed by f(x, y, z, &thgr;, &phgr;, t), i.e., the light ray group in the three-dimensional space is described as a six-dimensional space. This space is called a “ray space”.
A light ray group that passes through a plane (reference plane) Z=0 for t=0 will be examined. If a horizontal plane (X-Z plane) perpendicular to the Y-axis is considered, and disparity in the vertical direction is ignored (y=0), a real space is expressed as shown in
FIG. 13
for respective values of &phgr;. A light ray group coming from the reference plane is described by f(x, &thgr;) using two variables, i.e., position x and angle &thgr;. Therefore, a light ray group that passes a given point P(X,
0
, Z) in the real space satisfies for each &phgr;:
X=x+Z
tan &thgr; (1)
If a variable u=tan&thgr; is defined, equation (1) is rewritten as:
X=x+uZ
(2)
Therefore, in the ray space, a single light ray in the real space is mapped onto one point, and the light intensity, i.e., color information, is recorded there. Also, as can be seen from equation (2), a light ray group that passes through a certain point in the real space is mapped onto a straight line in the x-u space.
FIG. 14
shows the state wherein light rays observed at a viewpoint position P(X,
0
, Z) in the real space, and light rays observed from other viewpoint positions are mapped in the x-u space. Note that the x-u space forms a partial space of the aforementioned five-dimensional ray space. In this manner, when an image is captured from a sufficiently large number of viewpoints, the x-u space can be densely filled with data.
In order to accurately reconstruct an image at an arbitrary viewpoint position from this ray space, the y-axis direction, i.e., a dimension in the vertical direction, is required. However, in this case, ray space data must form at least a four-dimensional space x-y-&thgr;-&phgr;, and has a very large data size. Hence, conventionally, only the x-u space as a partial space of the ray space is considered. Furthermore, it is very redundant to provide color information to the entire coordinate system of the ray space. Because, even when only the x-u space is considered, pixel information in the y-axis direction is required to reconstruct an image, a three-dimensional ray space must be formed, and the light intensity of each light ray must be recorded there. To overcome this problem, a method of obtaining luminance values from multi-viewpoint images (images captured from a plurality of different viewpoint positions) loaded onto a memory by making ray space computations for all pixels of the image to be reconstructed is proposed. Note that the ray space computation is a computation made based on equation (2) in the x-u space to reconstruct an image at an arbitrary viewpoint position on the basis of multi-viewpoint images.
However, in the prior art, since the x-u space considers only disparity in the x-axis direction (horizontal direction), an identical ray space computation must be repeated for all scan lines in the y-axis direction. In order to generate and display an image at an arbitrary viewpoint position in real time in correspondence with motions of the operator, high-speed ray space computations are required. In order to implement such computations, operations for randomly accessing multi-viewpoint images and reading pixel data must be done. That is, high-speed random access to multi-viewpoint images is required. Hence, in the aforementioned example, the x-u space and multi-viewpoint images are loaded onto the memory in advance.
In this fashion, conventionally, upon generating and displaying an image at an arbitrary viewpoint position, an identical ray space computation must be repeated, and a work memory having a very large size must be used. A large number of times of computations required for obtaining pixel data often impair real-time motions. Also, when ray space data that describes an object have a huge data size and all such data must be loaded onto the memory, the number of objects that can be expressed in a three-dimensional virtual environment using the ray space is limited. In order to display an image in real time, repetitive computations must be avoided, and in order to lay out many objects described using ray space data in a three-dimensional virtual environment, the work memory size occupied by the ray space data must be minimized.
For this reason, as described in, e.g., Japanese Patent Laid-Open No. 10-111951, a method of encoding multi-viewpoint data, which are captured to generate an arbitrary viewpoint image of a given three-dimensional object, to reduce its data size has been proposed.
In order to generate three-dimensional object image data at an arbitrary viewpoint using the ray space theory, multi-viewpoint image data obtained by sensing that object through 360° are required. For example, a three-dimensional object is placed on a turntable, and its image is captured every time the object is rotated a predetermined angle in the horizontal direction, thus preparing multi-viewpoint image data for 360°. In order to generate data when the object is viewed from the above and below, multi-viewpoint images are captured by rotating the object also in the vertical d
Katayama Akihiro
Kotake Daisuke
Sakagawa Yukio
Canon Kabushiki Kaisha
Couso Jose L.
LandOfFree
Image data encoding/decoding method and apparatus does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image data encoding/decoding method and apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image data encoding/decoding method and apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3347246