Lucas-Kanade Method | Optical Flow

we have seen thus far that the optical flow estimation problem is an under constrained problem the lucas canada method uses the assumption that the optical flow in a very small neighborhood in the scene is the same for all points within that neighborhood and uses that assumption to then solve for the optical flow so let's take a look at how that works we're going to assume that for each pixel the motion field and hence the optical flow is constant within a small neighborhood around that pixel neighborhood we'll call that w so let's say that we have a patch here in the image a small patch smaller the better small patch right here we're going to assume that all the points within this patch are moving the same way in this in the image in other words they produce the same motion field and hence the same optical flow in the image so if that's the case for each point within this window let's say we take the point kl we have the derivative of the intensity in the x direction times u plus the derivative of the intensity in the y direction times v plus the derivative in the time direction is equal to zero and so that's one constraint that we have for the point kl but since we have many points inside here we're going to get a system of equations you're going to get a large system of equations where the number of equations is going to be equal to the number of points inside the window w now one of the interesting questions is is why does this work well it works because all of these equations we hope are not linearly dependent on each other and the reason they tend not to be is because if you have a patch that has interesting enough texture the derivatives i x and and i y will most likely be different from pixel to pixel so these are the equations that you get and you can stack them up and then write it in matrix form as follows and here you have this known matrix a which is n squared the window we said is n by n so it's n squared by 2. that's this matrix you have your unknown vector here u this is what we're trying to find for the window that's optical flow and then you have your known vector on the right hand side which is again n squared by 1. so you have n squared equations and you have two unknowns we know how to solve this problem it's the least square solution so let's take a look at that we have a u equal to b we take a transpose a times u equal to a transpose b and we know how to do this we simply find the inverse of this so this is the same written in matrix form right here with all the elements and we take the inverse of a transpose a and we can find a solution for u this is very easy very fast particularly because a transpose a is a two by two matrix and here are the elements within a transpose a these are uh all functions of the spatial derivatives that's interesting i x and i y you don't have the time derivative in this matrix right here the time derivative shows up in b the vector on the right hand side so this is a very simple thing to do and the question to ask is when does this not work when do we have problems but we know that it's not going to work when a transpose a is not invertible another way to think about it is that a transpose a is not well conditioned so what does that really mean what is a well-conditioned system let's say you have some system which has an input and an output a well-conditioned system is one where you have a significant enough change in the output for a change in the input when that is the case you can take changes in the output you can take the output and estimate the input well enough if you change the input and nothing happens in the output then that's not a well-conditioned system so even when you have a a simple a system such as this a u equal to b in this particular case it is going to be a well conditioned if the matrix a transpose a is well conditioned then you're going to have a good robust reliable solution for the optical flow u and when is a transpose a well conditioned when the eigenvalues remember this is a two by two matrix the two eigenvalues lambda one and lambda two both are significant enough neither one is close to zero and you can have one greater than the other which will often happen but it one cannot be significantly larger than the other one so let's sort of visually take a look at how this manifests in real images and what what's really going on here in terms of this matrix a transpose a well let's take a look at this scenario here where you have um basically a textureless patch in the scene and we want to compute the optical flow right here well this is what the patch looks like and if you look at the spatial gradients i x and i y and you simply plot them that is you're taking two images but you take the first image and compute the spatial gradients these are the spatial gradients right here they're all close to zero as expected because there's not much texture in this window right here and so the way to visualize the condition number and how good the matrix a transpose a is is that you take all of these points in ix iyy space and imagine fitting an ellipse to it and that is the best fit ellipse that you see here happens to be close to a circle in this case the semi-major axis and semi-minor axis of this ellipse that you fit correspond to the eigenvalues lambda 1 and lambda 2 of the matrix a transpose a so if lambda 1 and lambda 2 are really small which is the way it's turning out in this case because all the gradients are very small then you're not going to be able to compute optical flow reliably this should not surprise you when you have no texture to hang on to your derivatives are all small clearly estimating optical flow is going to be small very difficult that applies to us as well if i show you a scene or a surface patch which has no texture and i move it well it looks pretty much the same even after the motion any local patch within it so it cannot be estimated reliably so that's what i would call a bad region there's another type of bad region where you have an edge so an edge of course has a very clear visual feature but when you look at the gradients in this case you have strong gradients in one direction but you have weak gradients in the other direction so the problem really here is that if you have this edge it's very hard to know whether the edge actually moved this way or it's actually moving diagonally this way even faster so both of them will produce the same apparent changes in the brightness in the two different images and so this is again badly conditioned because in this particular case one eigenvalue is significantly larger than the other one again cannot be computed optical flow cannot be computed reliably this corresponds to the aperture problem we talked about earlier so the the sort of good case for us is when you have rich texture when you have texture that looks like this we have lots of different brightness values or changes in brightness in both the directions then you can imagine that when you find the spatial derivatives i x and i y they're going to be scattered and you're going to get large eigenvalues and therefore the matrix a transpose a is well conditioned and the optical flow that you end up computing is going to be reliable you

Channel: First Principles of Computer Vision

Views: 3,366

Rating: 5 out of 5

Keywords: Least squares solution, pseudo inverse, optical flow, flow estimation, condition number, eigenvalues, textureless, texture, Shree Nayar, First principles, computer vision, computational imaging, computational photography, Columbia Vision Laboratory, CAVE Laboratory, Computer Science, Columbia Engineering, School of Engineering and Applied Sciences, Columbia University

Id: 6wMoHgpVUn8

Length: 9min 10sec (550 seconds)

Published: Sun May 02 2021