Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-07-19
2003-05-13
Vo, Cliff N. (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
Reexamination Certificate
active
06563499
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to the area of 3-dimensional (3D) image processing and more particularly relates to methods and systems for generating a 3D region from a surrounding imagery.
2. Description of the Related Art
Three-dimensional (3D) models of objects can provide information useful for a variety of applications such as generating computer aided design models from physical objects in product designs, outlining biological structures or organs in medical research and generating digital characters for computer games. Nevertheless, the creation of the 3D models has in the past required highly skilled professionals, extensive artistic knowledge, expensive modeling equipment and laborious efforts.
With the popularity of personal computers and the rapid emergence of the Internet and the World Wide Web (WWW), there are increasing demands from non-professionals for 3D modeling systems that require no extensive knowledge to operate. For example, a business may need to generate 3D models of its products and present them on its www site to attain its e-commerce presence. A game developer may need to create a 3D model of a physical object to use as a realistic character in a computer game. A child may want to generate a 3D image of one of his/her favorite new toys to share by the Internet with a relative living remotely. The various applications and demands have proclaimed features of such 3D modeling systems that must be low in cost and easy in operation.
One of the commonly used 3D modeling systems is a triangulation system projecting beams of laser light onto an object. Ordinarily, the reflected light bounces off the object at an angle relative to the light source. The system employing an imaging system collects the reflection information from a different location relative to the light source and then determines the coordinates of the point or points of reflection by triangulation. A single dot system projects a single beam of light which, when reflected, produces a single dot of reflection. A scanning line system sends a plane of light against the object, the plane of light is reflected as a curvilinear-shaped set of points describing one contour line of the object. The location of each point in that curvilinear set of points can be determined by triangulation. The accuracy of the systems may be high but the systems are costly. The triangulation in the systems requires a precise configuration between the light source and the imaging system. Further the digitizing speed is usually slow when the object is large in size and limited by the mechanics of the scanning system.
Another commonly used 3D modeling approach is a stereoscopic system employing one or more imaging systems located at known locations or distances from each other to take multiple images of a 3D object. The captured images are processed with a pattern recognition system that corresponds the various points of the object in the multiple images and triangulates to extract depth information of these points, thereby obtaining the shape/contour information of the 3D object.
The above systems are either costly or require substantial knowledge to operate and not applicable in many applications that can not afford the cost and complexity. It is therefore a great need for a 3D modeling system that is easy to set up, virtually anywhere within minutes, and operated together with a personal computer, to scan and measure a 3D object and electronically replicate a fully-textured 3D model of the object.
In scanning the 3D object, there are generated images that are typically taken respectively around the object. Each of the images is a corresponding projection of the 3D object. Thus, there is a further need to develop a solution that can automatically and efficiently generate from those images a 3D region representing a volume bounding the object in a 3D space and used in subsequent processing for generating the full-textured model of the object.
SUMMARY OF THE INVENTION
The present invention has been made in consideration of the above described problems and needs and has particular applications for an image-based 3D modeling system that can be used to generate fully-textured models of objects. According to one aspect of the present invention, a surrounding imagery comprising a sequence of side view images taken respectively at a known position around an object. The images are preprocessed to generate corresponding sequence of silhouette or mask images. To accelerate the subsequent space carving process, each of the mask images is encoded uniquely using what is called herein a Maximal Area Encoding (MAE) scheme. In the space carving process, volumetric cells or cubes representing the object are recursively subdivided to gradually fit the object by “carving” away those cubes that are not occupied by any of the object. All cubes are encoded and indexed using a tree structure, such as an octree.
The invention can be implemented in numerous ways, including a method, a system and a computer readable medium containing program code for automatically generating a 3D region from a surrounding imagery. The advantages of the invention are numerous. Different embodiments or implementations may yield one or more of the following advantages.
One of the advantages is the encoding of the mask images using the unique MAE scheme. Each of the encoded values or pixels in one of the encoded images represents a squared area of a mask image that has a same color and is created by incrementing from a neighboring encoded values, resulting in an efficient encoding scheme. Another advantage of the present invention is that the process of deciding the status of each of the cubes (i.e. occupied, unoccupied or partially unoccupied by the object) is performed with respect to the encoded mask images rather than the original mask images, which makes the space carving process independent of the size of the mask images.
Other advantages, objects and features of the present invention, together with the foregoing, are attained in the exercise of the invention in the following description and resulting in the embodiment illustrated in the accompanying drawings.
REFERENCES:
patent: 5760882 (1998-06-01), Gulick, Jr. et al.
Bandari Esfandiar
Waupotitsch Roman
Geometrix, Inc.
Vo Cliff N.
Zheng Joe
LandOfFree
Method and apparatus for generating a 3D region from a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for generating a 3D region from a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for generating a 3D region from a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3015523