MVA2000 IAPR Workshop on Machine Vision Applications, Nov. 28-30,2000, The University of Tokyo, Japan 12-1 Self-Calibration from Optical Flow and Its Reliability Evaluation Department of Kenichi K a n a t a n i * Computer Science, Gunma University Abstract An algorithm is presented for 3-D reconstruction from optical flow observed by an uncalibrated camera. We show that by incorporating a statistical model of image noise, we can not only compute a statistically optimal shape but also evaluate its reliability in quantitative terms. We show real-image experiments and discuss the effect of the "gauge" on the uncertainty description. 1. Introduction 3-D reconstruction from optical flow has been studied by many researchers [4, 5, 131, but most have assumed that the camera is calibrated. Recently, the self-calibration approach using an uncalibrated camera was formulated by ViCville et al. [16] and Brooks et al. [2]. The self-calibration procedure consists of the following steps: 1. We detect optical flow from an image sequence. 2. We compute the flow fundamental matrices from the detected flow. 3. We decompose the computed flow fundamental matrices into the motion parameters. 4. We compute the 3-D shape of the scene. In this paper, we show that by incorporating a statistical model of image noise, we can not only compute a statistically optimal shape but also evaluate its reliability in quantitative terms. We show real-image experiments and discuss the effect of the gauge on the uncertainty description. 2. Optical Flow Detection The conventional method for optical flow detection is based on what is known as the gradient constraint [ l l , 121. However, the resulting flow does not have sufficient accuracy for 3-D reconstruction. Here, we assume that a limited number of salient feature points are traced by template matching and other means with high accuracy. 3. Fundamental Matrices Let {(x,,~,)) and {(xk,yk)), a = 1, ..., N , be image coordinates of two sets of points on two different images. We define the "flow" and the "midpoint" of the a t h point as 'Address: Kiryu, Gunma 376-8515 Japan. E-mail: kanataniocs .gunma-u. ac .jp where fo is an appropriate scale factor (e.g., the image size). If noise does not exist, the following epipolar equation is satisfied: [2, 5, 6, 13, 161 (throughout this paper, the inner product of the vectors a and b is denoted by ( a , b ) ) : (xa,W x a ) + (x,, Cx,) = 0. (2) Here, W is an antisymmetric matrix, and C is a symmetric matrix. They play the same role as the fundamental matrix for finite motion images, so we call them the flow fundamental matrices. The matrices W and C are not independent of each other. The following relationship holds [2]: We call this the decomposability condition1. From {x,, x,), a = 1, ..., N , the flow fundamental matrices W and C are computed by a technique called renormalization [6, 91. The program is implemented in C++ and is publicly available2. It outputs the estimates w and c of the flow fundamental (+) matrices along with their standard deviations W , , c(+), and c(-'. If, say, w(+)and w(-)ccincide up to three significant digits, the estimate w is likely to have accuracy up to approximately three significant digits. w(-) 4. Motion Parameters We assume that the camera is freely moving and freely changing its focal length. Other camera parameters such as the principal point, the aspect ratio, and the skew angle, which usually do not change in the course of camera motion, are assumed to be 'This corresponds to the constraint that the fundamental matrix for finite motion should have rank 2. 2http://vvv.ail.cs .gunma-u.ac. jp/'kanatani/e. e且1ibratedbefbrehand．FIenee．theunknownparam− 鴨匝】＝diag〔1・川）／2†Wh椚di昭ト1由nof郡代hモ etersarethetrans玉ationvelocityv．therot且tionYe− locity叫thefb亡a11engthf．aJlditヨChangeratlef・ BTOOksetal・［2】showedthattheBePar乱TneteT5Can diagona）matril：Withdiagona）element芳…1nthat order． becomp山ed抑叫血callyfromⅣ＝〔町j）and亡ご ＝〔Cij）．lmttheireomputatiorlinvolvesratheTCOm− pli亡atedalgebrai亡manip111ations・打ere，WepTeSent aneleg弧t叩叩一触口柁t加古♪m亡e血門derivedbyex− PreSBlngquaJltitiesintermsofi7Te血cLbEerepresen一 InthepreseTICeOfTlOise．thedata丘≡andⅡmay notne亡eSSaTilysati叫eq．榊hrthe亡nmputed恥w h皿da爪ent且ユmatrice5CaTldW・So，WPOptima11y COrr配f．磨andD：tOenforceeq．〔2）．Thisi日dorwas 肘lowst6】＝ 品＝丘・刷町 拍如即Orthegroupロー2−Drotaもions古口（2）【3】． htⅧ＝〔叫）be七bev既tOTde扇nedi¶eqB・（3）， 且nddothe払1low）ngeOmPutatioTl＝ 立＝∬一発抑Ⅳ尭＋2恥ー叫 A＝C‖＋Cコ才，磨＝（C‖−C22）＋2fC12、（4） e＝2〔C．3十盲C23）， Here．wedeGme 上）＝C33， 問 且（よ，正）＝t恋．1V削＋（訂、CⅡ：）， 血＝叫巾ひ望， 血∫＝， 山i＝呵叫， ￠三 正・ ， 桝 瑚咄lV虎＋封コ瑚鴨E虎丁（Ⅳ蓋十割コ瑚T Ⅴ（よ，可 （161 ．︺ l l ．■■■■．＼ l WI Utp 鴨【司＝叫Ⅱ】 l′ りふ J＝J′九 r﹁ 叫＝∫一山墓， tlち匝】Ⅳ瑚叫歳】W可丁 Ⅴ〔丘，可 l ノ′＝イ軸】， l纏】＝鴨匝卜 ︺ O t−＝・＼−【 and丘aregh唱ma日払l】0Ⅶ・S【6ト ︵ J＝J′九 2PU3 丁（チープ′2叫山′ 匝，刺’ T 叫＝J′山主， The covarian亡e matrices ofthe resulting values立 一4＋〔血封） ロ 叫＝輌】， 可Ⅵ√よ＋2C正．鴨t輔Ⅳ塵＋把叫＝151 山妄＝坤拙 U3 ＝￣ J∫＝ 竹島可＝（Ⅳ訂．相国l町可 乱丁 Weassumf？thatcrroFSiTl嚢and工rarq5tati写tjea勒 imdepend印t，bt】tt・he仁0汀eCtPdvalues丘and虔have 〕ト〔13） 〔 げ〃抽叫 thetbllowingcoTre】a†・ion＝一軒 Here．iis theimaglnaryunit．Thequantitieswith tildesare・巳Dmplexnumbers：呵・］aLnd9［・ldenote therealandimaglnaryPaTrtB．reSpeCtively．Wedefine the“inneT PrOduct”ofcomp［exnumbers z＝J＋ OPerationNt・】designate3nOrmalizationLntO孔unit lノ右脚Ⅳ去十2仇：）（叫可Ⅳ正）T l−け、訂） （lTJ 6．Foc且1LengthAdj11如ment After the focallen郎hJ鋸Idits change rate have been computed，We tranSform鐘aTldコ亡 v眈tOr：叫瓜］＝山川榔 ．√Jd n 軸且nd苫′＝エ′＋材by（ヱ1Z′）＝エご十抑r・The l封蓋，可＝ Intheaboveprocedure，LL，3i畠亡OmPl血dbyeq，（即 LheiT亡0V乱丁i射1CPmatTi亡e5郎fo11帥唱〔wede6nef，k aTldbythe鮎stofeqs．（10）intwDW町S．Thedecom− ＝diag（1，1，0”： posabilitycondition桝requiresthatthetwovaIues 亡Dim亡ide． However．adeglmerate亡On軸urationhlWhichthe abovecomputat丘onfailsoc亡ur占Whenthecameraop− 壷←紳予k車←dia埠字柵 ticalaxismoveswithintheplanespannedbyitand thetranslationvelocityv，e，g．．WllenthecameTaun− dergoe5apuretranSlationorthecameTaOpticalaxis 哺←巽〔埴卜芋鞘恥芸叫 PaSSeSthroughafixedpointinthes亡ene・ 柵句←帥帥一書叫 欄←担叶 5．Corrモ亡t呈0ⅡOrFlow Let鴨匝】ar）dl／L［塵］bethe亡OVarian仁ematricesof 七hepo5itionこE and the鮎w丘defined uptos亡a）e， They亡an be deteTmined fTOm the He55ian ofthe （1即 Then，We⊂ZulViewtheimaginggeometrya占ifusing TeSidualsu一触：e Oftemplate matehing ofgr邑y Zev− aper叩e亡tivec訂−1eTaWithunit加由1en軒h・ f南［14，1叶IfれOpriorin氏｝rmationisav由1able，We 丁∴m叩thC8mput乱tion mayusethedぬultvalueslち［可＝2diag（1，l，叫and 444 The depth Z of the point x is given as follows [6]: Z=- (v, Sxv) (v, S,(X w X x ) ) ' + (19) Here, we define Figure 1: Real images of an indoor scene. . 3-D position of this point is and k = (O,O, I ) ~ The given by r = ZX. (21) At this point, we need to check the sign of the depth. This is because the signs of W and C are indeterminate as implied by eq. (2). Let 2, be the depth associated with x,. We replace the sign of each 2, N if sgn[za] < 0, where sgn[.] is the signature function that takes 1, 0, and -1 for x > 0, x = 0, and x < 0, respectively. Em=, 8. Reliability Evaluation From eq. (21), the covariance matrix of the reconstructed position i is given up to scale as follows: . . The matrix Vo[x] is given in eqs. (18). From eqs. (19), the matrices Y[z] and v~[z, x] are given as follows: Here, tr denotes trace, and we define However, this analysis is based on the computed flow fundamental matrices c and W . They are computed from the data {x,, x,), cr = 1, ..., N, and hence are not exact. It follows that the values f , f , v and w are not exact. However, it is difficult to analyze the error propagation precisely. Here, we adopt the following approximation. We reconstruct two 3D positions r(*)for x from the standard deviations c(*) and w(') and regard ( r ( + ) - i ) ( r ( + ) - i)T as the covariance matrix of r due to the errors in c and W . The total covariance matrix of F is given by Figure 2: 3-D reconstruction and uncertainty ellipsoids (stereogram). where Z2 is the absolute noise magnitude, which can be estimated in the process of com.puting c and w [6, 91. 9. Real Image Experiment We reconstructed the 3-D shape from the two images shown in Fig. 1, using the feature points marked in the images. Fig. 2 is a side view of the reconstructed points (stereogram); wireframes are shown for some points. On each reconstructed point is centered the uncertainty ellipsoid defined by the covariance matrix given by eq. (25). All ellipsoids look like thin needles, indicating that the uncertainty is large along the depth orientation. This description is deceptive, however. This uncertainty description is based on a particular gauge, i.e., a choice of normalization: the world coordinate system is identified with the camera frame and the translation velocity is normalized to unit length [8, 101. This gauge hides the fact that the uncertainty is mostly due to that of the translation velocity. In fact, what is uncertain is the depth of the object as a whole, not the object shape. For example, if we take the centroid of the polyhedral object as the coordinate origin and normalize the root-mean-square distance t o the vertices from the centroid to unit length, we obtain the description shown in Fig. 3(a). By construction, the uncertainty is almost symmetric with respect to the centroid, and the object shape has very little uncertainty. Fig. 3(b) is the uncertainty description for yet another gauge: one of the object vert,ex is taken to be the coordinate origin, another is taken to be (1,1,0), and a third one is on the XY plane. By definition, the first two points have no uncertainty. It follows that uncertainty of individual quantities has no absolute meaning. In other words, the discrepancy of the reconstructed quantities from their Figure 4 malization based o n t h r e e vertices. computed value true value predicted standard deviation ratio 1.02 1.00 0.08 ., angle (deg) 95.1 90.0 17.0 Table 1: Reliability of gauge invariants. true values is not a meaningful measure of accuracy if artificial normalizations are involved. Let us call the description changes due to choosing different gauges (i.e., normalizations) gauge transformations. Absolute meaning can be given only to gauge invariants [8], i.e., quantities invariant to gauge transformations. Typical gauge invariants for Euclidean reconstruction are ratios of lengths and angles of lines. Table 1 lists the ratio of two sides of the polyhedral object and the angle they make along with their true values and their standard deviations derived by the covariance matrices of the vertices. Fig. 4 shows two real images of a car. Fig. 5 shows its 3-D shape computed from the feature points marked in these images. We defined a wireframe with triangular meshes from the reconstructed points and mapped the texture onto it. A fairly accurate 3-D shape is created even though only two views are used. 10. Concluding Remarks An algorithm has been presented for 3-D reconstruction from optical flow observed by an uncalibrated camera. We have shown that by incorporating a statistical model of image noise, we can not only compute a statistically optimal shape but also evaluate its reliability in quantitative terms, although the accuracy is not as high as that using the fundamental matrix (1, 71. We have shown realimage experiments and discussed the effect of the gauge on the uncertainty description. Acknowledgments: T h i s work was in p a r t s u p p o r t e d by t h e Ministry of Education, Science, S p o r t s a n d Cult u r e , J a p a n under a G r a n t i n Aid for Scientific Research C(2) (No. 11680377). T h e a u t h o r t h a n k s Mike Brooks of t h e University of Adelaide a n d his colleagues for collaboration in this research. H e also t h a n k s Naoya O h t a of G u n m a University a n d Yoshiyuki Shimizu of S h a r p L t d . for their assistance in doing real image experiments. images of a car I Figure 5: Reconstructed 3-D s h a p e References [I] L . Baumela, L. Agapito, P. Bustos and I. Reid, Motion estimation using the differential epipolar equation, Proc. 15th Int. Conf. Patt. Recogn., September 2000, Barcelona, Spain, Vo1.3, pp. 848-851. [2] M. J . Brooks, W. Chojnacki and L. Baumera, Determining the egomotion of an uncalibrated camera from instantaneous optical flow, J. Opt. Soc. Am., A, 14-10 (1997), 2670-2677. [3] K. Kanatani, Group-Theoretical Methods in Image Understanding, Springer, Berlin, 1990, (41 K. Kanatani, 3-D interpretation of optical flow by renormalization, Int. J. Comput. Vision, 11-3 (1993), 267282. [5] K. Kanatani, Geometric Computation for Machine Vision, Oxford University Press, Oxford, 1993. (61 K. Kanatani, Statistical Optimization for Geometric Computation: Theory and Practice, Elsevier, Amsterdam, 1996. [7] K. Kanatani, Gauge-based reliability analysis of 3-Dreconstruction from two uncalibrated perspective views, Proc. 15th Int. Conf. Patt. Recogn, September 2000, Barcelona, Spain, Vol.1, pp. 76-79. [8] K. Kanatani and D. D. Morris, Gauges and gauge transformations in 3D reconstruction from a sequence of images, Proc. 4th Asian Conf. Computer Vision, January 2000, Taipei, Taiwan, pp. 1046 - 1051. (91 K. Kanatani, Y . Shimizu, N . Ohta, M. J . Brooks, W . Chojnacki and A. van den Hengel, Fundamental matrix from optical flow: Optimal computation and reliability evaluation, J. Electronic Imaging, 9-2 (2000), 194-202. [lo] D. D. Morris, K. Kanatani and T . Kanade, Uncertainty modeling for optimal structure from motion, IEEE Workshop on Vision Algorithm: Theory and Practice, September 1999, Corfu, Greece, pp. 33-40. [ l l ] N. Ohta, Image movement detection with reliability indices, IEICE 7'mns., E79-10 (1991), 3379-3388. [12] N. Ohta, Optical flow detection using a general noise model, IEICE Trans. Inf. 0 Syst., E79-D-7 (1996), 951957. [13] N . Ohta and K. Kanatani, Optimal structure-from-motion algorithm for optical flow, IEICE %ns. Inf. d Sys., E78-D-12 (1995), 1559-1566. [14] J . Shi and C. Tomasi, "Good features t o track," in Proc. IEEE Conf. Comput. Vision Patt. Rewgn., June 1994, Seattle, WA, U.S.A., pp. 593-600. [15] A. Singh, "An estimation-theoretic framework for imageflow computation," in Proc. 3rd Int. Conf. Comput. Vision, December, 1990, Osaka, Japan, pp. 168-177. (161 T. Vibville and 0. D. Faugeras, The first order expansion of motion equations in the uncalibrated case, Comput. Vision Image Understanding, 64-1 ( 1 996), 128-146.

© Copyright 2016 ExploreDoc