Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
2000-04-20
2003-02-04
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C345S427000
Reexamination Certificate
active
06515658
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a 3D shape generation apparatus. More particularly, the present invention relates to a device for generating an objected captured in a camera image as a 3D shape on a display, based on camera images taken from a plurality of directions.
2. Description of the Prior Art
The increasing performance of computer systems in recent years and the progress in multimedia technology have led to a steadily improving environment for high-quality 3D computer graphics (referred to as “CG” in the following), even for use in personal computers. The question how a real object can be efficiently converted into 3D image data for a computer is an important problem for the structuring of systems, such as for electronic shopping, electronic libraries, etc., recreating objects realistically on a computer screen with 3D computer graphics technology.
The simplest method of generating data of a 3D object for a computer is to capture the 3D object from several directions to generate 2D image data, and to display the captured 2D image taken from the direction that is closest to the direction of the user on a display for reproduction. However, with this method, there is the problem that images of the 3D object from directions other than the directions from which the object has been captured cannot be displayed. Moreover, the images are 2D images after all, so that it is difficult to combine them with images of other 3D objects generated as 3D computer graphics data. To make it possible to display a captured 3D object from any direction, it is important to restore a 3D shape of the object as 3D image data, based on the 2D image data capturing the object from a plurality of directions, so that a projection image of the 3D shape can be generated and displayed for any direction.
Several methods have been proposed for restoring the 3D shape of an object as 3D image data from captured 2D image data. A prominent example is the method based on feature points. The generation of 3D image data with this method includes the following operations, illustrated by the flowchart in FIG.
14
.
FIG. 15
illustrates the conventional principle of 3D image data generation based on feature points.
First of all, a captured image is read in, from which feature points are derived (operation
1401
). For the derivation of these feature points, it is preferable that points where the brightness of the captured 2D image changes are selected as feature points. The feature points can be derived automatically by a computer searching for brightness changes, or they can be specified by hand. An example of a derivation of feature points is shown in FIG.
15
. In this example, the four feature points shown in
FIG. 15B
are derived from the captured image in FIG.
15
A.
Then, the correspondence of the derived feature points among the captured images is established (operation
1402
). If the positional relation between the captured images, similarities among the images, and the positional relation between the derived feature points are utilized for establishing the correspondence among the feature points, operation
1402
can be processed automatically with a computer. Of course, the feature points also can be specified by hand. In the example in
FIG. 15
, the correspondence of the feature points
1
to
4
has been established as shown in FIG.
15
C.
Then, the 3D coordinates of the feature points are determined by the principle of stereoscopy from the correspondence relation of the feature points (operation
1403
), whereby each feature point is expressed as a point in 3D space.
Then, faces are assigned to the feature points arranged in 3D space, and a polyhedron is formed (operation
1404
). Here, combinations of feature points defining a face are not arbitrary combinations, but have to be selected so as to form the outer surface of the object to be reproduced. In the example of
FIG. 15
, the faces are assigned as shown in
FIG. 15D
, forming a tetrahedron.
Then, textures are generated for the faces (operation
1405
). For the generation of textures, it is possible to compute textures referring to the patterns on the captured images, and map them onto the faces.
With these operations S
1401
to S
1405
, 3D image data can be generated from captured images. In the example of
FIG. 15
, 3D image data can be generated from the original 3D object, as shown in FIG.
15
E.
On the other hand, the reproduction of the 3D object on a computer screen, using the generated 3D image data, includes the following operations, illustrated by the flowchart in FIG.
16
.
First of all, the position of the user with respect to the object is specified. That is, the direction and distance with respect to the object are specified (operation
1601
).
Then, the position of each feature point on a projection plane corresponding to the direction and distance of the specified viewpoint with respect to the object is calculated, and a projection image is obtained (operation
1602
). At this stage, texture mapping has not yet been performed.
Then, a texture is mapped on each face of the projection image (operation
1603
). For the mapping of the texture, the texture is adjusted calculating the size, shape and direction of each projected face.
Finally, after applying the necessary special effects, such as lighting, tracing and shading, the 3D shape is displayed on a computer screen (operation
1604
).
With these operations S
1601
to S
1605
, a 3D object can be displayed from any direction on a computer screen, using the generated 3D image data.
Of the conventional 3D shape generation processing operations, the following methods are known for assigning faces to restore a 3D shape based on the feature point correspondences, shown as operation
1404
in FIG.
14
. However, each of these methods poses problems, also described below.
A first conventional method for assigning faces is the projection of 3D feature points onto a surface of a known shape. This method projects the 3D feature points onto a developable surface with a known shape, such as a conical surface or a cylindrical surface, and uses the connections among the vertices, which have been determined before. This processing method is simple and can be regarded as an effective technique.
However, in this first processing method the 3D shape must be already known, or the projection center for the projection towards the developable surface, has to be determined in a manner that there is no pair of faces where the projection overlaps in the projection processing from the center point onto the developable surface. In other words, there is the problem that this method cannot be used for the case where there are complex 3D shapes of unknown shape including dents.
A second conventional method for assigning faces is to determine the direction of the normal on the faces using brightness information, and to assign faces so that this direction is the normal. With irradiation from the direction of a light source during the time of the projection, the brightness at the feature points on the faces of the 3D shape correlate to the direction of the normal of those faces, so that using brightness information, the directions of the normal on the faces at the 3D feature points can be determined, and the faces can be assigned.
However, this second processing method can be used only when the 3D shape is comparatively not complex, and it has no bumps or dents. That is to say, near bumps or dents, the brightness information changes abruptly, so that often the direction of the normal cannot be determined, or a wrong direction is determined for the normal, and there is the problem that this method cannot be used for those cases.
A third conventional method for assigning faces is to display the derived feature points on a display screen, and to specify some of those feature points by hand to determine the faces of the 3D shape. If the user specifies the feature points correctly, the 3D shape can be restored and generated without error.
However, in this thir
Fujitsu Limited
Staas & Halsey , LLP
Vo Cliff N.
LandOfFree
3D shape generation 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 3D shape generation apparatus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 3D shape generation apparatus will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3158736