| Summary: | Optical flow is the apparent motion of the brightness patterns in an image. The pyramidal form of the Lucas-Kanade (<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>LK</mi></semantics></math></inline-formula>) method is frequently used for its computation but experiments have shown that the method has deficiencies. Problems arise because of numerical issues in the least squares (<inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>LS</mi></semantics></math></inline-formula>) problem <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo movablelimits="true" form="prefix">min</mo><msubsup><mfenced separators="" open="∥" close="∥"><mi>A</mi><mi>x</mi><mo>−</mo><mi>b</mi></mfenced><mn>2</mn><mn>2</mn></msubsup></mrow></semantics></math></inline-formula>, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>A</mi><mo>∈</mo><msup><mi mathvariant="double-struck">R</mi><mrow><mi>m</mi><mo>×</mo><mn>2</mn></mrow></msup></mrow></semantics></math></inline-formula> and <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>m</mi><mo>≫</mo><mn>2</mn></mrow></semantics></math></inline-formula>, which must be solved many times. Numerical properties of the solution <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>x</mi><mn>0</mn></msub><mo>=</mo><msup><mi>A</mi><mo>†</mo></msup><mi>b</mi></mrow></semantics></math></inline-formula> = <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msup><mrow><mo>(</mo><msup><mi>A</mi><mi>T</mi></msup><mi>A</mi><mo>)</mo></mrow><mrow><mo>−</mo><mn>1</mn></mrow></msup><msup><mi>A</mi><mi>T</mi></msup><mi>b</mi></mrow></semantics></math></inline-formula> of the <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>LS</mi></semantics></math></inline-formula> problem are considered and it is shown that the property <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>m</mi><mo>≫</mo><mn>2</mn></mrow></semantics></math></inline-formula> has implications for the error and stability of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>x</mi><mn>0</mn></msub></semantics></math></inline-formula>. In particular, it can be assumed that <i>b</i> has components that lie in the column space (range) <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">R</mi><mo>(</mo><mi>A</mi><mo>)</mo></mrow></semantics></math></inline-formula> of <i>A</i>, and the space that is orthogonal to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">R</mi><mo>(</mo><mi>A</mi><mo>)</mo></mrow></semantics></math></inline-formula>, from which it follows that the upper bound of the condition number of <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>x</mi><mn>0</mn></msub></semantics></math></inline-formula> is inversely proportional to <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo form="prefix">cos</mo><mi>θ</mi></mrow></semantics></math></inline-formula>, where <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>θ</mi></semantics></math></inline-formula> is the angle between <i>b</i> and its component that lies in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi mathvariant="script">R</mi><mo>(</mo><mi>A</mi><mo>)</mo></mrow></semantics></math></inline-formula>. It is shown that the maximum values of this condition number, other condition numbers and the errors in the solutions of the <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>LS</mi></semantics></math></inline-formula> problems increase as the pyramid is descended from the top level (coarsest image) to the base (finest image), such that the optical flow computed at the base of the pyramid may be computationally unreliable. The extension of these results to the problem of total least squares is addressed by considering the stability of the optical flow vectors when there are errors in <i>A</i> and <i>b</i>. Examples of the computation of the optical flow demonstrate the theoretical results, and the implications of these results for extended forms of the <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi>LK</mi></semantics></math></inline-formula> method are discussed.
|
|---|