Source: http://www.google.com/patents/US5475422
Timestamp: 2013-12-05 17:30:26
Document Index: 438124754

Matched Legal Cases: ['art 10', 'art 20', 'art 10', 'art 23', 'art 21', 'art 25', 'art 26', 'art 27', 'art 29', 'art 29']

Patent US5475422 - Method and apparatus for reconstructing three-dimensional objects - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Advanced Patent Search | Sign inAdvanced Patent SearchPatentsOne of the images of an object captured by at least three cameras is defined as a basic image, and a basic backprojection line is defined which passes through a feature point in the basic image corresponding to a noted three-dimensional feature point on the object and the optical center of the camera...http://www.google.com/patents/US5475422?utm_source=gb-gplus-sharePatent US5475422 - Method and apparatus for reconstructing three-dimensional objectsPublication numberUS5475422 APublication typeGrantApplication numberUS 08/262,541Publication dateDec 12, 1995Filing dateJun 20, 1994Priority dateJun 21, 1993Fee statusPaidAlso published asDE69430153D1, DE69430153T2, EP0631250A2, EP0631250A3, EP0631250B1Publication number08262541, 262541, US 5475422 A, US 5475422A, US-A-5475422, US5475422 A, US5475422AInventorsTakeaki Mori, Satoshi Suzuki, Takayuki YasunoOriginal AssigneeNippon Telegraph And Telephone CorporationPatent Citations (4), Referenced by (44), Classifications (22), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetMethod and apparatus for reconstructing three-dimensional objectsUS 5475422 AAbstract One of the images of an object captured by at least three cameras is defined as a basic image, and a basic backprojection line is defined which passes through a feature point in the basic image corresponding to a noted three-dimensional feature point on the object and the optical center of the camera that captured the basic image. Reference backprojection lines are defined with respect to respective feature points on an epipolar line, obtained by projecting the basic backprojection line onto the image by each of the other cameras, and the optical center of said each camera. The coordinates of intersection points of the basic backprojection line and the reference backprojection lines are calculated and the number of the reference backprojection lines intersecting at each intersection point on the basic backprojection line is counted. The point having the maximum number of intersections is determined to be the position of the noted three-dimensional feature point. Similar processing is performed for all of the feature points in the basic image, by which the positions of corresponding three-dimensional feature points of the object are determined.
What is claimed is: 1. A method of obtaining three-dimensional information of an object by capturing images of said object by a plurality of cameras and making three-dimensional feature points on said object to correspond to feature points in said images, said method comprising the steps:(a) imaging said object by n cameras to obtain n frames of images and outputting said images as image data, said n being an integer equal to or greater than 3; (b) receiving said image data and extracting feature points of said object on said n frames of images respectively; (c) defining one of said n cameras as a basic camera, defining the image picked up by said basic camera as a basic image, defining the other remaining cameras as reference cameras, defining the images captured by said reference cameras as reference images, and defining a backprojection line, which passes through the optical center of said basic camera and a feature point in said basic image chosen in correspondence to a noted three-dimensional feature point on said object, as a basic backprojection line; (d) projecting said basic backprojection line onto said reference images to define thereon epipolar lines, respectively; (e) defining backprojection lines, which pass through said feature points on said epipolar lines on said reference images and optical centers of said reference cameras, as reference backprojection lines; (f) calculating the coordinates of intersection points of said basic backprojection line and said reference backprojection lines, counting the numbers of intersections of said basic backprojection line and said reference backprojection lines at their respective intersection points, and determining the intersection point of the maximum count value to be the position of said noted three-dimensional feature point; and (g) repeating said steps (c) through (f) for each of said feature points on said basic image to obtain the positions of said three-dimensional feature points on said object as its three-dimensional information. 2. A method of obtaining three-dimensional information of an object by capturing images of said object by a plurality of cameras and making three-dimensional feature points on said object to correspond to feature points in said images, said method comprising the steps:(a) imaging said object by n cameras to obtain n frames of images and outputting said images as image data, said n being an integer equal to or greater than 3; (b) receiving said image data and extracting feature points of said object on said n frames of images, respectively; (c) defining one of said n cameras as a basic camera, defining the other remaining cameras as reference cameras, defining the images captured by said reference cameras as reference images, and defining a backprojection line, which passes through the optical center of said basic camera and a feature point in said basic image chosen in correspondence to a noted three-dimensional feature point on said object, as a basic backprojection line; (d) projecting said basic backprojection line onto said reference images to define thereon epipolar lines, respectively; (e) defining backprojection lines, which pass through said feature points on said epipolar lines on said reference images and optical centers of said reference cameras, as reference backprojection lines; (f) calculating the coordinates of intersection points of said basic backprojection line and said reference backprojection lines, filtering the distribution of said intersection points along said basic backprojection line by convolution to emphasize the concentration of said distribution of said intersection points, and determining the position where said filtered distribution of the intersection points is maximum to be the position of said noted three-dimensional feature point; and (g) repeating said steps (c) through (f) for each of said feature points on said basic image to obtain the positions of said three-dimensional feature points on said object as its three-dimensional information. 3. The method of claim 1 or 2, wherein a position on said basic backprojection line is defined every predetermined unit length of said basic backprojection line lengthwise thereof and the number of intersections at each of said intersection points is the number of intersections in said unit length at the position on said basic backprojection line through which said reference backprojection lines pass.
BACKGROUND OF THE INVENTION The present invention relates to measurements of the position, shape and movement of a three-dimensional moving object and, more particularly, to a three-dimensional information reconstruction or recovery method and apparatus which can be used in the fields of three-dimensional information reconstruction, recognition and description (CG) of moving objects.
SUMMARY OF THE INVENTION It is therefore an object of the present invention to provide a method and apparatus which permit the acquisition or recovery of three-dimensional information of an object from its images taken by a small number of cameras.
BRIEF DESCRIPTION OF THE DRAWINGS FIG. 1 is a block diagram illustrating the configuration of an embodiment of the three-dimensional information reconstructing apparatus according to the present invention;
DESCRIPTION OF THE PREFERRED EMBODIMENTS In FIG. 1 there is shown in block form an embodiment of the three-dimensional information reconstructing apparatus according to the present invention. The illustrated apparatus is made up of an image input part 10 and an image information processing part 20. The image input part 10 is composed of n (n being an integer equal to or greater than 3) image capturing parts (for example, TV cameras, hereinafter referred to simply as cameras) 111 through 11n, A/D converters 121 through 12n, frame memories 131 through 13n, a camera controller 14, a movable table 15A, a driver 15B and a movement controller 16. The cameras 111 through 11n are mounted on the common moving table 15A at different heights. The moving table 15A is designed to be movable three-dimensionally by the driver 15A formed by a robot arm under the control of the movement controller 16.
By the feature extracting part, feature points on each image 32 (for example, isosbestic points and regions in an image, contour lines and regions in a differential image and isothermal points and regions in a thermal image) are extracted. In this example, edges of the image are extracted feature points by a Canny filter (Canny J. F.:"A computational approach to edge detection," IEEE Trans. PAMI, Vol. 8, No. 6, pp. 679-698, 1986). Next, the basic backprojection generating part 23 selects an image 32 of an arbitrary one of the n frames as a basic image 32s and calculates a backprojection line 34s which passes through one noted feature point on the basic image 32s and the optical center 31s of the camera (that is, the basic camera) corresponding to the image 32s which is inputted from the camera information input part 21. The coordinates (x.sub.b, y.sub.b, z.sub.b) of an arbitrary point on the backprojection line 34s satisfy the following equation: ##EQU1## where (x.sub.p y.sub.p, z.sub.p) and (x.sub.c, y.sub.c, z.sub.c) are coordinates of the noted feature point on the image 32s and the optical center 31s of the basic camera, respectively. Such a backprojection line 34s will hereinafter be referred to as a basic backprojection line. An arbitrary point E=(x.sub.e, y.sub.e) on an epipolar line, which is obtained by projecting the basic backprojection line onto each reference image, has such relations as shown below. ##EQU2## where R.sup.T' and T' are a two-dimensional expression of a transposed version of a matrix which defines the rotation of the camera optical axis with respect to the coordinate system and a two-dimensional expression of a vector which defines the translation of the camera optical axis with respect to the coordinate system, respectively, and B'=(X.sub.b, y.sub.b).sup.T is a two-dimensional expression of an arbitrary point on the backprojection line. As is evident from FIG. 3, the basic backprojection line 34s is present in a plane containing the optical center 31 of every reference camera and the epipolar line 35 by the reference camera. This plane will hereinafter be called an epipolar plane by the reference camera. Three-dimensional feature points on the object 19 present in an extension plane of the epipolar plane of each camera are all projected onto the epipolar line 35 of the camera. Next, the reference backprojection line generating part 25 detects all feature points 33 on the above-mentioned epipolar line 35. One of these feature points 33e on the epipolar line 35 corresponds to the noted feature point 33s. In practice, however, there are cases where these feature points are not on the epipolar line because of an image quantization error. Accordingly, feature points within a fixed distance from the epipolar line 35 are also regarded as its feature points 33e. This is followed by obtaining backprojection lines 34 which pass through the feature points 33e on the epipolar line 35 in the image 32 by each reference camera and the optical center 31 of the reference camera. These backprojection lines 34 will hereinafter be referred to as reference backprojection lines.
Next, the intersection extracting part 26 calculates the coordinates of intersections of the basic backprojection line 34s and the reference backprojection lines 34. Owing to the presence of an feature extraction error on each image 32 and an error in the optical center of each camera, the situation occasionally arises where the basic backprojection line 34s and the reference backprojection lines 34 do not intersect in the three-dimensional space. In this embodiment, the shortest distance between the basic backprojection line 34s and each reference backprojection line 34 is calculated and if this shortest distance is smaller than a fixed threshold value, the basic backprojection line 34s and the reference backprojection line 34 concerned are regarded as intersecting each other. That is, if the rank of the following matrix with two arbitrary points B.sub.b1 =(X.sub.b1, y.sub.b1, z.sub.b1).sup.T and B.sub.b2 =(x.sub.b2, y.sub.b2, z.sub.b2) on the basic backprojection line 34s and two arbitrary points B.sub.r1 =(x.sub.r1, y.sub.r1, z.sub.r1) and B.sub.r2 =(x.sub.r2, y.sub.r2, z.sub.r2) on the reference backprojection line 34 is 1, these two lines do not extend parallel to each other. ##EQU3## In this instance, two points (x.sub.bs, y.sub.bs, z.sub.bs).sup.T and (x.sub.rs, y.sub.rs, z.sub.rs).sup.T, which stay on the basic backprojection line 34s and the reference backprojection line 34, respectively, and provide the shortest distance between the two lines, are given as follows: ##EQU4## where: K.sub.b =(G.sub.r H-F.sub.r G.sub.b)/(F.sub.b F.sub.r =-H.sup.2)
K.sub.r =(F.sub.b G.sub.r -G.sub.b H)/(F.sub.b F.sub.r -H.sup.2)
F.sub.b =(x.sub.b2 -x.sub.b1).sup.2 +(y.sub.b2-y.sub.b1).sup.2 +(z.sub.b2 -z.sub.b1).sup.2
F.sub.r =(x.sub.r2 -x.sub.r1).sup.2 +(y.sub.r2 -y.sub.r1).sup.2 +(z.sub.r2 -z.sub.r1).sup.2
G.sub.b =(x.sub.b2 -x.sub.b1)(x.sub.b1 -x.sub.r1)+(y.sub.b2 -y.sub.b1)(y.sub.b1 -y.sub.r1)+(z.sub.b2 -z.sub.b1)(z.sub.b1 -z.sub.r1)
G.sub.r =(x.sub.r2 -x.sub.r1)(x.sub.r1 -x.sub.b1)+(y.sub.r2 -y.sub.r1)(y.sub.r1 -y.sub.b1)+(z.sub.r2 -z.sub.r1)(z.sub.r1 -z.sub.b1)
H=(x.sub.b2 -x.sub.b1) (x.sub.r1 -x.sub.r2)+(y.sub.b2 -y.sub.b1)(y.sub.r1 -y.sub.r2)+(z.sub.b2 -z.sub.b1)(z.sub.r1 -z.sub.r2)
d={(x.sub.bs -x.sub.rs).sup.2 +(y.sub.bs -y.sub.rs).sup.2 +(z.sub.bs z.sub.rs).sup.2 }.sup.1/2 &amp;lt;&#955;                       (6)
x=(x.sub.bs +x.sub.rs)/2
y=(y.sub.bs +y.sub.rs)/2
z=(z.sub.bs +z.sub.rs)/2 (7)
In the interests of clarity, let the number of feature points on the epipolar line of each reference camera obtained by projecting the basic backprojection line 34s onto each reference image be represented by M. Only one or none of the M feature points on the epipolar line on the image by each camera correspond to the noted feature point. Now, assume that one of the M feature point on each epipolar line corresponds to the noted feature point. Accordingly, one reference camera provides M reference backprojection lines and the probability that any one of the M intersections of M reference backprojection lines and the basic backprojection line corresponds to a noted feature point is β=1/M. The same goes for the other reference cameras. Hence, the probability a that one of the reference backprojection lines from every reference camera intersects the basic backprojection line 34s at any intersection thereon is α=β.sup.n-1. When only one feature point is present on the epipolar line of the reference camera (that is, when M=1), that feature point corresponds to the noted feature point and the reference backprojection line intersects the noted feature point; in this case, no problem arises. It is when the number M of reference backprojection lines from each reference camera is 2 or more that matters. Therefore, discussion will be made below on the case where β=1/M is in the range of between 0 to 0.5.
FIG. 4 is a graph showing the probability α that (n=1) reference backprojection lines from (n-1) reference cameras intersect at one point on the basic backprojection line when the value β is in the range of 0&lt;β≦0.5. As is evident from the graph, even in the case where β=0.5, if the number n of all cameras (i.e. the number of viewing points) is equal to or larger than 6, the probability α of five reference backprojection lines from reference cameras intersecting at one point on the basic backprojection line is as negligibly small as (0.5).sup.5 =0.03. Also when n=5 (the number of reference cameras is four), the value α is as small as 0.06. That is, the possibility that a plurality of reference backprojection lines from respective reference cameras happen to intersect at the noted feature point decreases rapidly as the number n of cameras increases. Conversely speaking, when the number of reference backprojection lines which actually intersect at a certain point on the basic backprojection line is plural (four or more, for instance), it implies that the intersection is very likely to be a noted feature point. Then, it is possible to uniquely determine or locate the position of the noted three-dimensional feature point by counting in the intersection counting part 27 the number of reference backprojection lines intersecting at each point on the basic backprojection line 34s (hereinafter referred to simply as the intersection number) and then detecting in the three-dimensional feature point extracting part 29 the position providing the maximum intersection number, as described previously. In this way, any given three-dimensional feature point on the object 19 can be made to correspond to a unique intersection on the basic backprojection line.
P'(s)=&#8747;P(s-t)
where P(s) and P'(s) are the distributions of backprojection line intersection counts before and after the convolution of the function f(t), respectively, and s is the position along the basic backprojection line 34s. The filter function f(t) can be obtained with such various filters as mentioned above. In this embodiment, a Laplacian-Gaussian filter (commonly called a ∇.sup.2 G filter) 52, which has such a characteristic as shown in FIG. 6B, is used to perform the convolution with the distribution of the intersection counts 51 along the basic backprojection line 34s. Since the ∇.sup.2 G filter has a property of emphasizing peaks of a continuous waveform while suppressing high-frequency discrete noise, the convolution suppresses discrete intersection counts and emphasizes peaks of highly concentrated intersection counts as shown in FIG. 6C. Thus, the extraction of a false three-dimensional feature point can be prevented by detecting peaks 51p of the intersection counts on the basic backprojection line 34s in the three-dimensional feature extracting part 29 and then determining that the intersection closest to the peak position concerned is the position of the noted three-dimensional feature point.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4062045 *Feb 24, 1976Dec 6, 1977The President Of Hokkaido UniversityThree-dimensional television systemUS4541007 *Aug 15, 1981Sep 10, 1985Kiyoshi NagataStereoscopic color television systemUS4956705 *Mar 10, 1989Sep 11, 1990Dimensional Visions GroupElectronic method and apparatus for stereoscopic photographyUS5049987 *Oct 11, 1989Sep 17, 1991Reuben HoppensteinMethod and apparatus for creating three-dimensional television or other multi-dimensional images* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS5644651 *Mar 31, 1995Jul 1, 1997Nec Research Institute, Inc.Method for the estimation of rotation between two frames via epipolar search for use in a three-dimensional representationUS5687249 *Sep 1, 1994Nov 11, 1997Nippon Telephone And TelegraphMethod and apparatus for extracting features of moving objectsUS5710875 *Mar 8, 1995Jan 20, 1998Fujitsu LimitedMethod and apparatus for processing 3-D multiple view images formed of a group of images obtained by viewing a 3-D object from a plurality of positionsUS5818959 *Oct 4, 1995Oct 6, 1998Visual Interface, Inc.Method of producing a three-dimensional image from two-dimensional imagesUS5999187 *Jun 27, 1997Dec 7, 1999Resolution Technologies, Inc.Fly-through computer aided design method and apparatusUS6072903 *Dec 31, 1997Jun 6, 2000Kabushiki Kaisha ToshibaImage processing apparatus and image processing methodUS6104425 *Feb 25, 1997Aug 15, 2000Matsushita Electric Industrial Co., Ltd.Method and apparatus for transmitting television signals, method and apparatus for receiving television signals, and method and apparatus for transmitting/receiving television signalsUS6118475 *Jun 1, 1995Sep 12, 2000Canon Kabushiki KaishaMulti-eye image pickup apparatus, and method and apparatus for measuring or recognizing three-dimensional shapeUS6141440 *Jun 4, 1998Oct 31, 2000Canon Kabushiki KaishaDisparity measurement with variably sized interrogation regionsUS6160909 *Apr 1, 1998Dec 12, 2000Canon Kabushiki KaishaDepth control for stereoscopic imagesUS6205241Jun 1, 1998Mar 20, 2001Canon Kabushiki KaishaCompression of stereoscopic imagesUS6320979Oct 6, 1998Nov 20, 2001Canon Kabushiki KaishaDepth of field enhancementUS6553138Dec 30, 1998Apr 22, 2003New York UniversityMethod and apparatus for generating three-dimensional representations of objectsUS6661914 *Nov 20, 2001Dec 9, 2003Koninklijke Philips Electronics N.V.Method of reconstruction of tridimensional scenes and corresponding reconstruction device and decoding systemUS6674431 *May 30, 2000Jan 6, 2004Minolta Co., Ltd.Method for processing data expressing three-dimensional shapeUS6744914 *Apr 28, 2000Jun 1, 2004Orametrix, Inc.Method and system for generating a three-dimensional objectUS6760488 *Jul 12, 2000Jul 6, 2004Carnegie Mellon UniversitySystem and method for generating a three-dimensional model from a two-dimensional image sequenceUS6834119 *Apr 3, 2001Dec 21, 2004Stmicroelectronics, Inc.Methods and apparatus for matching multiple imagesUS6834163 *Jan 14, 2003Dec 21, 2004Z/I Imaging GmbhCamera system having at least two first cameras and two second camerasUS7149345 *Oct 3, 2002Dec 12, 2006Minolta Co., Ltd.Evaluating method, generating method and apparatus for three-dimensional shape modelUS7167738 *Jul 31, 2001Jan 23, 2007Stryker Leibinger Gmbh & Co., KgMethod for navigating in the interior of the body using three-dimensionally visualized structuresUS7196719Jul 16, 2004Mar 27, 2007Vision Robotics CorporationAngled axis machine vision system and methodUS7272306 *Apr 18, 2005Sep 18, 2007Xiaolin ZhangBionic automatic vision and line of sight control system and methodUS7310154 *Aug 3, 2001Dec 18, 2007Ricoh Company, Ltd.Shape measurement systemUS7898522 *Jun 1, 2007Mar 1, 2011Gesturetek, Inc.Video-based image control systemUS7898569Feb 15, 2007Mar 1, 2011Vision Robotics CorporationAngled axis machine vision system and methodUS8027531Jul 21, 2005Sep 27, 2011The Board Of Trustees Of The Leland Stanford Junior UniversityApparatus and method for capturing a scene using staggered triggering of dense camera arraysUS8059888Oct 30, 2007Nov 15, 2011Microsoft CorporationSemi-automatic plane extrusion for 3D modelingUS8126273 *Mar 10, 2008Feb 28, 2012Siemens CorporationMethod for reconstructing three-dimensional images from two-dimensional image dataUS8139110Nov 1, 2007Mar 20, 2012Northrop Grumman Systems CorporationCalibration of a gesture recognition interface systemUS8180114Jun 5, 2008May 15, 2012Northrop Grumman Systems CorporationGesture recognition interface system with vertical displayUS8234578Jul 25, 2006Jul 31, 2012Northrop Grumman Systems CorporatiomNetworked gesture collaboration systemUS8253847Feb 28, 2011Aug 28, 2012Nikon CorporationDigital camera having an automatic focusUS8274535Aug 17, 2007Sep 25, 2012Qualcomm IncorporatedVideo-based image control systemUS8345920Jun 20, 2008Jan 1, 2013Northrop Grumman Systems CorporationGesture recognition interface system with a light-diffusive screenUS8427545 *Nov 20, 2007Apr 23, 2013Sony Europe LimitedMethod and an apparatus for generating image contentUS8432448Aug 10, 2006Apr 30, 2013Northrop Grumman Systems CorporationStereo camera intrusion detection systemUS8547374Oct 9, 2009Oct 1, 2013Lockheed Martin CorporationDetection and reconstruction of 3D objects with passive imaging sensorsUS20100318467 *Nov 20, 2007Dec 16, 2010Sony United Kingdom Limitedmethod and an apparatus for generating image contentUS20110128393 *Dec 1, 2009Jun 2, 2011Nokia CorporationDigital imagingCN1079182C *Feb 28, 1997Feb 13, 2002松下电器产业株式会社Television signal transmitting, receiving method, device and transmitting/receiving method and deviceCN100414249CMay 26, 2005Aug 27, 2008上海交通大学Computer automatic measuring visual system for stock ground measuringCN100427876CMay 26, 2005Oct 22, 2008上海交通大学Automatic measuring method of computer visual system for stock ground measuringWO1998039739A1 *Mar 3, 1998Sep 11, 1998Josefsson ThorleifData processing* Cited by examinerClassifications U.S. Classification348/48, 348/E13.8, 348/E13.15, 348/E13.25International ClassificationH04N13/02, G06T11/00, H04N13/00, G06T7/00Cooperative ClassificationG06T7/0065, H04N13/0221, G06T2207/10012, H04N13/0242, H04N2013/0081, G06T11/006, G06K9/209, H04N13/0055, H04N13/0296European ClassificationH04N13/02Y, H04N13/02A3, G06T11/00T3, G06T7/00R7, G06K9/20SLegal EventsDateCodeEventDescriptionMay 29, 2007FPAYFee paymentYear of fee payment: 12Jun 9, 2003FPAYFee paymentYear of fee payment: 8Apr 13, 1999FPAYFee paymentYear of fee payment: 4Jun 20, 1994ASAssignmentOwner name: NIPPON TELEGRAPH AND TELEPHONE CORPORATION, JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:MORI, TAKEAKI;SUZUKI, SATOSHI;YASUNO, TAKAYUKI;REEL/FRAME:007044/0932Effective date: 19940607Jun 20, 1994AS02Assignment of assignor's interestOwner name: MORI, TAKEAKIEffective date: 19940607Owner name: NIPPON TELEGRAPH AND TELEPHONE CORPORATION 1-6, UCOwner name: SUZUKI, SATOSHIOwner name: YASUNO, TAKAYUKIRotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google