JP2009536499A - System and method for reconstructing a three-dimensional object from a two-dimensional image - Google Patents

Abstract

Systems and methods for three-dimensional (3D) acquisition and modeling of scenes using two-dimensional (2D) images are provided. The system and method obtains first and second images of a scene and applies a smoothing function to the first image (202) to further determine object feature points such as object corners and edges in the scene. Visible and applied to the first image with at least two feature detection functions, detects feature points of the object in the first image (204, 208), and combines the outputs of the at least two feature detection functions Select feature points of the object to be tracked (210), apply a smoothing function to the second image (206), and apply a tracking function to the second image to track the feature points of the selected object Then, the three-dimensional model of the scene is reconstructed from the output of the tracking function (218).

Description

The present invention relates generally to 3D object modeling, and more particularly to a system and method for obtaining 3D (3D) information from 2D (2D) images using hybrid feature detection and tracking including smoothing functions. .
This application claims the benefit of 35U.SC §119 of provisional application 60/798087 filed in the United States on May 5, 2006.

  When the scene is filmed, the resulting video sequence contains implicit information about the three-dimensional (3D) shape of the scene. While this implicit information is sufficient for proper human perception, the exact shape of the 3D scene is required for many applications. One category of these applications is when sophisticated data processing techniques are used, for example, in the generation of new scene views or 3D shape reconstruction for industrial inspection applications.

  The recovery of 3D information has been an active research area for some time. Numerous techniques in the literature to capture 3D information directly, for example using a laser range finder, or to recover 3D information from one or more two-dimensional (2D) images such as stereo or structure from motion techniques Exists. In general, 3D acquisition techniques can be classified as active and passive approaches, single-view and multi-view approaches, and geometric and luminosity methods.

  The passive approach acquires 3D shapes from images or videos taken under normal lighting conditions. The 3D shape is calculated using geometric shapes or optical features extracted from images and videos. Active approaches use special light sources such as lasers, structured illumination or infrared illumination. The active approach calculates the shape based on the response of the object and scene to the special light projected onto the object and scene surface.

  The single view approach uses a large number of images taken from a single camera viewpoint to recover the 3D shape. Examples include structure from motion and depth from defocus.

  The multi-view approach recovers the 3D shape from multiple camera viewpoints obtained from object motion or from multiple images taken at different light source positions. Stereo matching is an example of multi-view 3D recovery by matching pixels in the left and right images in a stereo pair to obtain pixel depth information.

  Geometric methods recover 3D shapes by detecting geometric features such as corners, edges, lines or contours in one or more images. Special relationships between extracted corners, edges, lines or contours are used to infer the 3D coordinates of the pixels in the image. SFM (Structure From Motion) is a technology that attempts to reconstruct the 3D structure of a scene and moving objects from a series of images taken from a moving camera or a stationary camera in the scene. Many agree that SFM is basically a non-linear problem, but there have been some attempts to represent non-linearity that provide mathematical elegance as well as direct solution methods. On the other hand, linear techniques, non-linear techniques require iterative optimization and need to deal with local minima. However, they compromise good numerical accuracy and flexibility. The advantage of SFM over stereo matching is that one camera is required. The feature-based approach is made even more effective by tracking techniques that use the past history of feature motion to predict discrepancies in the next frame.

  Second, because of the same space and time difference between two consecutive frames, the corresponding problem is positioned as a problem of predicting the apparent movement of the image brightness pattern, called the optical pattern. There are several algorithms that use SFM, most of which are based on the reconstruction of 3D shapes from 2D images. Some assume known corresponding values, others use a statistical approach to reconstruct without a correspondence.

  The methods described above have been extensively studied for decades. However, a single technique does not perform well in all situations, and most of the past methods focus on 3D reconstruction relatively easily under laboratory conditions. For real world scenes, the subject is moving, the lighting is complex, and the depth range is large. It is difficult to deal with these real-world conditions for previously identified technologies.

  This disclosure provides systems and methods for three-dimensional (3D) acquisition and modeling of scenes using two-dimensional (2D) images. The system and method of this disclosure includes the steps of acquiring at least two images of a scene, performing a smoothing function that makes the features more visible, for feature selection and tracking for 3D information recovery. Followed by a hybrid scheme. First, a smoothing function is applied to the image and is followed by feature point selection to find features in the image. At least two feature point detection functions are utilized to cover a wide range of good feature points in the first image, and then a smoothing function is applied to the second image and detected in the second image. Followed by the tracking function to track the feature points. Feature detection / selection and tracking results are combined to obtain a complete 3D model. One target application for this function is 3D reconstruction of film sets. The resulting 3D model is used for visualization or post-processing during film shooting. Other applications will benefit from this approach, including but not limited to gaming and 3DTV.

  According to one aspect of this disclosure, a three-dimensional acquisition process is provided. Obtaining first and second images of the scene; applying at least two feature detection functions to the first image to detect object feature points in the image; Combining the output of at least two feature detection functions for selection, applying a tracking function to the second image to track the feature points of the selected object, and 3 of the scene from the output of the tracking function Reconstructing the dimensional model. This process further applies a smoothing function to the first image before applying at least two feature detection functions to make the feature points of the object in the first image more visible. A point is a corner, edge or line of an object in the image.

  In another aspect of this disclosure, a system for obtaining three-dimensional (3D) information from a two-dimensional (2D) image is provided. The system includes a post-processing device configured to reconstruct a 3D model of a scene from at least two images, the post-processing device being configured to detect feature points in the image. A point detector, which includes at least two feature detection functions. At least two feature detection functions are applied to a first image of at least two images. The system also generates a feature point tracking means configured to track selected feature points between at least two images, and a depth map between the at least two images from the tracked feature points. A depth map generator configured for the purpose. The post-processing device generates a 3D model from the depth map. The post-processing device further includes a smoothing function filter configured to make the feature points of the object in the first image more visible.

  In a further aspect of this disclosure, a computer-readable program storage that implements a program comprising computer-executable instructions to perform method steps for modeling a three-dimensional (3D) scene from a two-dimensional (2D) image. A device is provided, the method comprising: obtaining a first and second image of a scene; applying a smoothing function to the first image; and smoothing at least two feature detection functions Applying to the image of the image, detecting a feature point of the object in the image, combining the outputs of at least two feature detection functions to select the feature point of the object to be tracked, a second smoothing function Applying to the second image, tracing to the second image to track the feature points of the selected object Applying a king function, and a step of reconstructing a 3-dimensional model of a scene from an output of the tracking function.

  These aspects, features and advantages of the present invention, as well as other aspects, features and advantages will be set forth and will be apparent from the following detailed description of the preferred embodiments, read in conjunction with the accompanying drawings.

  In the drawings, like reference numerals designate like elements throughout the drawings. The drawings are for purposes of illustrating the concepts of the invention and are not necessarily the only possible configuration for illustrating the invention.

  It will be appreciated that the elements shown may be implemented in various forms of hardware, software or combinations thereof. Preferably, these elements are implemented in a combination of hardware and software on one or more appropriately programmed general purpose devices including a processor, memory and input / output interfaces.

  This description illustrates the principles of the invention. Those skilled in the art will appreciate that although not explicitly described or illustrated herein, the principles of the invention may be implemented and various arrangements may be devised which fall within the spirit and scope of the invention. .

  All examples and conditional languages cited herein are intended for educational purposes to assist the reader in understanding the principles of the invention and the concepts contributed by the inventor, and are specifically cited as such. Should not be construed as having any limitations on the examples and conditions.

  Moreover, all references to principles, aspects and embodiments of the invention are intended to cover structurally and functionally equivalent configurations of the invention, as well as specific examples thereof. Furthermore, such equivalent configurations include both equivalent configurations that will be developed in the future as well as currently known equivalent configurations, ie, both developed elements that perform the same function regardless of the structure.

  Thus, for example, it will be appreciated by those skilled in the art that the block diagrams presented herein represent a conceptual view of an exemplary circuit that implements the principles of the invention. Similarly, any flowcharts, flow diagrams, state transition diagrams, pseudocodes, etc. may be substantially represented by computer-readable media, whether or not the computer or processor is explicitly shown. Represents the various processes so represented.

  The functionality of the various elements shown is provided through the use of dedicated hardware as well as hardware capable of executing software in conjunction with appropriate software. When provided by a processor, the functionality is provided by a single dedicated processor, a single shared processor, or multiple individual processors, some of which are shared. Furthermore, the explicit use of the terms “processor” or “controller” should not be construed to indicate exclusively hardware capable of executing software, but without limitation, digital signal processors (DSPs). Implicitly includes hardware, read only memory (ROM) for storing software, random access memory (RAM) and non-volatile storage.

  Other hardware, conventional and / or custom may be included. Similarly, any switches shown are conceptual. Those functions can be performed through program logic, through dedicated logic, through program control and dedicated logic iterations, or manually, and specific techniques can be selected by the implementor to be understood in more detail from the context. It is.

  In the claims of the present invention, an element expressed as a means for performing a particular function is a) a combination of circuit elements that perform that function, or b) suitable software that executes that software to perform that function. It is intended to encompass any method of performing that function, including any form of software including firmware, microcode, etc. coupled with the circuit. The invention defined by such claims resides in the fact that the functions provided by the various cited means are combined and combined with each other in the way the claims require. It is thus regarded that any means that can provide those functionalities are equivalent to those shown herein.

  The technique disclosed in the present invention addresses the problem of recovering the 3D shape of objects and scenes. Restoring the shape of a real-world scene is challenging due to object movement, large depth discontinuities between the foreground and background, and complex lighting and brightness conditions It is a problem. Current methods used in feature point selection and tracking to predict a depth map of an image or to reconstruct a 3D representation are not performed very well by themselves. Although 3D reconstruction from 2D images is used, the results are limited and the depth map is not very accurate. Some techniques for 3D acquisition, such as laser scanning, are not acceptable in many situations, for example due to the presence of human objects.

  Systems and methods are provided for recovering the three-dimensional (3D) shape of objects and scenes. The system and method of the present invention provides an SFM (Structure From Motion) enhancement approach using a hybrid approach to recover 3D features. This technology is motivated by the lack of a single method that can reliably place features for large environments. The technique of the present invention begins by applying different smoothing functions, such as Poisson or Laplacian transforms, to the image prior to feature point detection / selection and tracking. This type of smoothing filter serves to make it more visible to detect features in the image than commonly used Gaussian functions. A number of feature detectors are then applied to one image to obtain good features. After using two feature detectors, good features are obtained and then easily tracked through several images using a tracking method.

Referring now to the drawings, exemplary system components according to embodiments of this disclosure are shown in FIG. The scanning device 103 can be used to print a film print 104 such as a camera-original film negative, for example, a Cineon format or SMPTE (Society of Motion Picture and Television).
Provided for scanning to digital formats such as Engineers' DXP (Digital Picture Exchange) files.

Scanning device 103 includes, for example, telecine, or any device that produces video output from film such as ArriLocPro ^™ with video output. Alternatively, a file from a post-production process or digital cinema 106 (eg, a file that already exists in a computer-readable format) can be used directly. Potential sources of computer readable files are AVID ^™ editors, DPX files, D5 tapes, etc.

  The scanned film print is input to a post-processing device 102 such as a computer. The computer may include one or more central processing units (CPU), memory 110 such as random access memory (RAM) and / or read only memory (ROM), as well as keyboards, cursor control devices (eg, mouse or joystick) and display devices. It may be implemented on various known computer platforms having hardware such as an input / output (I / O) user interface 112. The computer platform includes an operating system and microinstruction code. The various processes and functions described in the present specification are a part of microinstruction code or a part (or combination thereof) of a software application program executed via an operating system. In one embodiment, the software application program is implemented on a program storage device and uploaded to a suitable computer such as the post-processing device 102 for execution. In addition, various other peripheral devices are connected to the computer platform by various interfaces and bus structures such as a parallel port, serial port or universal serial bus (USB). Other peripheral devices include a further storage device 124 and a printer 128. The printer 128 is utilized to print a revised version of the film 126, and the scene is changed or replaced using 3D modeled objects as a result of the technique described.

  Alternatively, file / film prints that are already in computer readable form 106 (eg, digital cinema stored on external hard drive 124) are input directly to computer 102. Note that the term “film” used in this specification may indicate either film print or digital cinema.

  The software program includes a three-dimensional (3D) reconstruction module stored in the memory 110. The 3D reconstruction module 114 includes a smoothing function filter 116 that is further visible to detect object features in the image. The 3D reconstruction module 114 includes feature point detection means 118 for detecting feature points in the image. The feature point detector 118 includes at least two different feature point detection functions, such as an algorithm, for detecting or selecting feature points. A feature point tracking means 120 is provided for tracking selected feature points through a plurality of consecutive images via a tracking function or algorithm. A depth map generator 122 is provided for generating a depth map from the tracked feature points.

  FIG. 2 is a flow diagram of an exemplary method for reconstructing a three-dimensional (3D) object from a two-dimensional (2D) image according to an aspect of the present invention.

  Referring to FIG. 2, post-processing device 102 obtains a digital master video file in a computer-readable format. A digital video file is obtained by capturing a sequence of temporal video images with a digital video camera. Alternatively, the video sequence may be captured by a conventional film type camera. In this scenario, the film is scanned via scanning device 103 and the process proceeds to step 202. The camera acquires a 2D image while either an object or camera in the scene moves. The camera acquires multiple viewpoints of the scene.

Regardless of whether the film is scanned or is already in digital format, the digital file of the film contains instructions or information regarding the position of the frame (eg, time code, frame number, time from the start of the film, etc.). Each frame of the digital video is, for example, I ₁ , I ₂ ,. . . Including one image such I _n.

In step 202, the smoothing function filter 116 is applied to the image I ₁ . Preferably, the smoothing function filter 116 is a Poisson or Laplacian transformation to make it more visible to detect the function of the object in the image than a Gaussian function commonly used in the art. Useful. It should be understood that other smoothing function filters may be employed.

The image I ₁ is then processed by the first feature point detector at step 204. Feature points are salient features of the image such as corners, edges, lines, etc., where there is a large amount of image intensity contrast. Feature points are selected and tracked robustly to be easily identifiable. The feature point detection means 118 may use the Kitchen-Rosenfeld corner detection operator C, as is well known in the art. This operator is used to evaluate the degree of “cornerness” of an image at a given pixel location. A “corner” is a feature of an image characterized by the intersection of two directions of the maximum value of the intensity gradient of the image at an angle of 90 degrees, for example. In order to extract feature points, the Kitchen-Rosenfeld operator is applied at each valid pixel position in the image I ₁ . When the value of the operator C increases for a specific pixel, the degree of cornerness increases, and the operator C at the pixel position (x, y) in the image I ₁ is another pixel in the vicinity of (x, y). The position (x, y) is a feature point if it is greater than The neighborhood is a 5 × 5 matrix centered at the pixel location (x, y). In order to ensure robustness, the selected feature points have a degree of cornerness greater than a threshold, such as T _c = 10. The output from the feature point detector 118 is a set of feature points {F _1} in the image I _1, each of F ₁ corresponds to the position of the pixel of the "features" of the image I _1. Many other feature point detectors are used, including but not limited to SIFT (Scale Invariant Feature Transform), SUSAN (Smallest Univalue Segment Assimilating Nucleus), Sobel edge operator and Canny edge detector .

In step 206, the image I ₁ is input to the smoothing function filter 116, and a second different feature point detector is applied to the image (step 208). The feature points detected in step 204 and step 208 are then combined and the selected feature points of the duplicate are removed (step 210). The smoothing function filter applied in step 206 is the same filter applied in step 202, but in other embodiments, a different smoothing function filter is used in each of steps 202 and 206. Please understand that there are cases.

  It should be understood that a large number of feature points can be detected by employing a hybrid approach for feature point detection. FIG. 3A illustrates a scene with detected feature points represented by small rectangles. The scene in FIG. 3A is processed with one feature point detector. In contrast, the scene in FIG. 3B is processed with the hybrid point detector approach of the present invention to detect a significant number of feature points.

After the detected feature points are selected, the second image I ₂ is smoothed using the same smoothing function filter used in the first image I ₁ (step 212). Good feature points selected in the first image I ₁ are tracked in the second image I ₂ (step 214). Given a set of feature points in image I ₁ , feature point tracking means 120 tracks the feature points in the next image I ₂ of the scene shot by finding their closest match.

  As described above, in other embodiments, the smoothing function filter applied in step 212 is different from the filter applied in steps 202 and 206. Further, although steps 202-212 are described sequentially, in certain embodiments, smoothing function filters may be applied simultaneously via parallel processing or hardware.

Once the feature points are tracked, mismatch information is calculated for each tracked feature as the difference between the pixel positions l ₁ and l ₂ in the horizontal direction. The discrepancy is inversely related to depth by a scaling factor associated with the camera calibration parameters. At step 216, camera calibration parameters are obtained and utilized by the depth map generator 122 to generate a depth map of the object or scene between the two images. Camera parameters include, but are not limited to, the focal length of the camera and the distance between the two camera shots. Camera parameters are manually entered into the system 100 via the user interface 112 or estimated from a camera calibration algorithm. Using camera parameters, depth is predicted at feature points. The resulting depth map is sparse with depth values only at the detected features. A depth map is a two-dimensional array of values for mathematically representing a surface in space, where the rows and columns of the array correspond to the x and y positions of the surface, and the array element is given by A measure of depth or distance from a point or camera position to the surface. The depth map can be viewed as a grayscale image of the object, and the depth information replaces intensity information or pixels at each point on the surface of the object. Thus, surface points are also referred to as pixels in 3D graphical construction techniques, and the two terms are used interchangeably in this disclosure. Because the discrepancy information is inversely proportional to the depth multiplied by the scaling factor, it can be used directly to build a 3D scene model for most applications. This eliminates the need for camera parameter calculation and simplifies the calculation.

From the set of feature points present in the image pairs I ₁ and I ₂ and the estimated depth values at each feature point and so that the feature points are located relatively close to each other and span the entire image If a feature point is selected, the depth map generating means 122 forms a 3D mesh structure by connecting the feature points to each other, where the feature points are the vertices of the formed polygon. It is in. When the feature points are close to each other, the resulting 3D mesh structure has a higher density. Since the depth at each vertex of the 3D structure is known, the depth at the point in each polygon is estimated. In this way, the depths at the pixel positions of all the images are estimated. This may be done by planar interpolation. A robust and fast method for generating 3D mesh structures is Delaunay triangulation. The feature points are connected to form a set of triangles whose vertices are at the location of the feature points. Using the depth associated with each feature point and its corresponding vertex, the “depth plane” is fitted to each individual triangle, and from each individual triangle, the depth of each point within the triangle is It is determined.

The complete 3D model of the object can be reconstructed by combining the triangular mesh obtained from the Delaunay algorithm with the texture information from image I ₁ (step 218). The texture information is a 2D intensity image. A complete 3D model includes depth and intensity values at the pixels of the image. The resulting combined image is visualized using conventional visualization tools such as the ScanAlyze software developed at Stanford University, Stanford, California.

  A reconstructed 3D model of a particular object or scene is rendered for viewing on a display device or stored in a digital file 130 away from the file containing the image. The 3D reconstructed digital file 130 is stored in the storage device 124 for later retrieval, for example, during a film editing stage where the modeled object is inserted into a scene where the object did not previously exist. Is done.

  The system and method of the present invention utilizes multiple feature point detectors to combine the results of multiple feature point detectors to improve the number and quality of detected and feature points. Combining different feature point detectors as opposed to a single feature detector improves the finding of good feature points to track. After obtaining “good” results from multiple feature point detectors (ie, using more than one feature point detector), the feature points in the second image are easy to track, Compared to using a single feature point detector to obtain a depth map result, it is easier to produce a good depth map result.

  While embodiments incorporating the teachings of the present invention have been shown and described in detail herein, those skilled in the art will readily devise many other varied embodiments that incorporate these teachings. Can do. While a preferred embodiment of a three-dimensional (3D) acquisition and modeling system and method of a scene (which is intended to be exemplary and not limiting) has been described, modifications and variations in light of the above teachings Made by those skilled in the art. Accordingly, it is to be understood that the particular embodiments of the disclosed invention may be practiced within the scope and spirit of the invention as outlined in the claims. Although the invention has been described in detail and as required by patent law, the desired concepts claimed and protected by patent law are set forth in the following claims.

1 is an exemplary description of a system for obtaining three-dimensional (3D) information according to an aspect of the present invention. 4 is a flowchart of an exemplary method for reconstructing a three-dimensional (3D) object from a two-dimensional (2D) image according to an aspect of the present invention. It is a figure which illustrates the scene processed with one feature point detection function. It is a figure which illustrates the scene shown by FIG. 3A processed with a hybrid detection function.

Claims (21)

Obtaining a first image and a second image of a scene;
Applying at least two feature detection functions to the first image to detect feature points of the object in the first image;
Combining the outputs of the at least two feature detection functions to select feature points of the object to be tracked;
Applying a tracking function to the second image to track feature points of the selected object;
Reconstructing a three-dimensional model of the scene from the output of the tracking function;
A three-dimensional acquisition process. Applying a smoothing function to the first image prior to applying the at least two feature detection functions to further make object feature points in the first image more visible. ,
The three-dimensional acquisition process according to claim 1. The feature points are corners, edges or lines of objects in the image,
The three-dimensional acquisition process according to claim 2. Prior to applying the tracking function, further comprising applying the same smoothing function to the second image;
The three-dimensional acquisition process according to claim 2. Applying a first smoothing function to the first image before applying a first feature detection function of the at least two feature detection functions; and Applying a second smoothing function to the first image before applying the second feature detection function;
The first and second smoothing functions make the feature points of the object in the first image more visible;
The three-dimensional acquisition process according to claim 1. The combining step further includes the step of removing duplicate feature points detected by the at least two feature detection functions;
The three-dimensional acquisition process according to claim 1. The reconstructing step further includes generating a depth map of feature points of an object selected between the first image and the second image.
The three-dimensional acquisition process according to claim 1. The reconstructing step further includes generating a three-dimensional mesh structure from the feature points of the selected object and the depth map.
The three-dimensional acquisition process according to claim 7. The step of generating the three-dimensional mesh structure is performed by a triangulation function.
The three-dimensional acquisition process according to claim 8. Reconstructing further comprises combining the mesh structure with texture information from the first image to complete a three-dimensional model;
The three-dimensional acquisition process according to claim 8. A system for obtaining three-dimensional (3D) information from a two-dimensional image,
The system has a post-processing device configured to reconstruct a three-dimensional model of the scene from at least two images,
The post-processing device includes:
A feature point detector configured to detect feature points in an image and including at least two feature detection functions, and the at least two feature detection functions are applied to a first image of the at least two images. ,
Feature point tracking means configured to track selected feature points between the at least two images;
Depth map generating means configured to generate a depth map between at least two images from the tracked feature points;
The post-processing device generates the 3D model from the depth map;
A system characterized by that. The post-processing device further includes a smoothing function filter configured to make object feature points in the first image more visible.
The system of claim 11. The smoothing function filter is a Poisson transform or a Laplacian transform.
The system of claim 12. The feature point detection means is configured to combine the feature points detected from the at least two feature detection functions to remove the detected feature points of replication.
The system of claim 12. The post-processing device is further configured to generate a three-dimensional mesh structure from the selected feature points and the depth map.
The system of claim 12. The post-processing device is further configured to combine the mesh structure with texture information from the first image to complete a 3D model.
The system of claim 15. A display device for rendering the 3D model;
The system of claim 16. A computer-readable recording medium for realizing a program comprising instructions executable by a computer to execute a method of modeling a three-dimensional scene from a two-dimensional image,
The method is
Obtaining a first image and a second image of a scene;
Applying a smoothing function to the first image;
Applying at least two feature detection functions to the smoothed first image to detect feature points of the object in the first image;
Combining the outputs of the at least two feature detection functions to select feature points of the object to be tracked;
Applying a smoothing function to the second image;
Applying a tracking function to the second image to track feature points of the selected object;
Reconstructing a three-dimensional model of the scene from the output of the tracking function;
A recording medium comprising: The reconstruction step further includes generating a depth map of feature points of the selected object between the first image and the second image.
The recording medium according to claim 18. The reconstructing step further includes generating a three-dimensional mesh structure from the feature points of the selected object and the depth map.
The recording medium according to claim 19. The reconstruction step further comprises the step of combining the mesh structure with texture information from the first image to complete the three-dimensional model.
The recording medium according to claim 20.

Images