CS 664 Machine Vision Lecture # 14 OFCE, Probability & Statistics Lecturer: Professor Ramin Zabih Scribe: JenYee Hui 10/23/01 0 Announcements: PS # 1 handed back Quiz # 3 on Thursday 10/25/01 MD guest Lecture Tuesday 10/30/01 ~1:15-3:00pm 1 Review: Optical Flow Constraint Equation ∇I • [u v] = -It Ixu + Iyv + It = 0 (Assumes constant brightness) where the intensity gradient, ∇I and It is measurable and image flow (u, v) needs to be derived. The intensity gradient, ∇I, always points in the direction of maximum increase of intensity, while the vector (u , v) lies somewhere along a line perpendicular to the intensity gradient. Since there are two unknowns in one equation, solutions to OFCE are non-unique and problem is ill posed. Note: How much motion there is depends on the local intensity component and It. If It is large, then there is big motion.2 Aperture problem Given the OFCE, it is only possible to perceive motion along a single line. This is analogous to viewing through a porthole. If image is getting darker, then we know that object is moving to the right. One can only detect the horizontal motion component, no vertical motion component. Thus, this problem is ill posed and has an ambiguous solution. First find the normal flow then use spatial coherence: Solution: 1. Solve for normal flow components {(u, v) of OFCE} 2. Smoothing application 3. Application of choice (i.e. FOE- focus of expansion) 3 Direct Method This is a class of methods that are badly named and skips the smoothing function step. Should use only if expected error is small. 4 Two Major Assumptions: 1. When computing the normal flow, constant brightness is assumed. Thus, the constant brightness of a point does not change with motion. 2. Framework used to derive OFCE equation is done in continuous math although images are discrete. Thus, must be careful when applying continuous math. 5 Energy Functional: E(u,v) = Edata(u , v) + λ Esmooth(u , v) ∂x ∂y Calculus of Variations: Used to find extreme values of functionals. The basic tool is use Euler-Lagrange Equations to find minima, which holds the position of the extrema as well as other positions Å local minima in weak sense. E(f) = argmin E(f’) where f’ is near f A small change in local value f does not change the value of E by much. -> gradient descent. Paper by Horn & Schunk (~1977) proposed a measure for the correlation between calculated optical flow and the true motion field. Their normal flow and optical flow equation with standard smoothing on vector field measures how rapidly coordinates are changing with no notion of discontinuity. Esmooth = |∇ u |2 + |∇ v |2 Edata = Ix u + Iy v + ItIssue arises in local approach for stereo motion - When individual value does not matter causing pixels to be weighted at center. Depending on lambda, pixel either moves a little or all the way. Lambda determines how important it is for pixel to be spatially coherent. For example, a small lambda would result in smooth output with little sense of borders or other detail. If neighbors have different intensity gradients, but are doing same things, will eventually intersect using least squares fitting. Another important variant of the LSF, the Lucas-Kanade Algorithm, which is a differential technique, gives terrible answers at discontinuities. If there appears to be two intersections, thus two clusters, the Lucas-Kanade Algorithm would give an answer in between the two intersections Å garbage in center. These normal flow algorithms can also be used in other applications such as Parametric Motion Models for model fitting. (will go back in detail later) Solution - Use robust Statistics.3.0 Applying Statistics To Computer Vision Many problems in computer vision involve statistical estimation. 3.1 Relationship between Probability and Statistic Probability uses theorems to derive the chances of occurrence on a sample based on the population. Meanwhile, statistics uses justified guess (hypothesis) to infer chances of occurrence on population based on sample data. Thus, probability is a branch in mathematics and statistics is a branch in science. Population Sample Probability Å Statistics Ä 3.2 Probability Terms Ω - an exhaustive set of outcomes samples (also called events, outcomes) – elements of Ω Event space F contains all subsets of Ω closed under various operations: if Ω is finite, then event space F is usually the power set (all subsets of Ω) Å 2Ω if Ω is not finite, then event space F has a continuous power set (hard) Example. Flip 2 coins Ω = {TH HH TT HT} Ω is finite, thus event space F is all subsets: F = { φ , Ω, {TH, TT}, {HT, HH}} {Tail first}, {Head first} Events obey some trivial Laws such as commutative, distributive laws and uses Venn Diagrams to show intersections. 3.3 Probability Functions Probability function P is an unit interval function P: FÅ[0,1] * must be an event P(φ) = 0 P(Ω) = 1 P(A∪B) = P(A) + P(B) - P(A∩ B) Where P(A) measures the size of event A relative to Ω. If Ω is non-finite, then use measure theory (not covered) for continuous probability. (Ω, F, P) is the probability space. 3.4 Conditional Probability: The probability of event B when event A has already occurred. P(B/A) ≡ P(A ∩ B) where P(A) ≠ 0 P(A) Can also be written as P’(X) =