Chapter 15 Motion and Surface Structure from Time-Varying Image Sequences

15.1 Introduction
Motion analysis involves estimating the relative motion of objects with respect to each other and the camera, given two or more perspective projection images in a time sequence.
real-world applications:
industrial automation and inspection, robot assembly,
autonomous vehicle navigation, biomedical engineering,
remote sensing, general 3D-scene understanding
object motion and surface structure recovery from:

• observed optic flow
• point correspondences

15.2 The Fundamental Optic Flow Equation
1#1: 3D point on moving rigid body
2#2: perspective projection on the image plane
3#3: camera constant
4#4: velocity of the point 2#2

5#5

take time derivatives of both sides

6#6

yields the fundamental optic flow equation:

7#7

general solution: (8#8 is a free variable)

9#9

15.2.1 Translational Motion
known:

• 10#10-point optic flow field: 11#11
unknown:
• corresponding unknown 3D points: 12#12
• all points moving with same but unknown velocity 13#13
can be solved up to a multiplicative constant

15.2.2 Focus of Expansion and Contraction
known:

• 3D motion is translational
• one 2D projected point 2#2 has no motion: 14#14
thus, translational motion is in a direction along the ray of sight
focus of expansion (FOE): if 3D point field moving toward camera
FOE: motion-field vectors radiate outward from that point
focus of contraction (FOC): if 3D point field moving away from camera
FOC: vectors radiate inward toward diametrically opposite point
flow pattern of the motion field of a forward-moving observer
=====Nalwa, A Guided Tour of Computer Vision, Fig. 8.14=====

15.2.3 Moving Line Segment
known:

• fixed distance between two unknown 3D points 15#15
• translational motion with common velocity 13#13
• corresponding optic flow: 16#16
unknown:
• 15#15: two unknown 3D points
• common velocity: 13#13

15.2.4 Optic Flow Acceleration Invariant
since 17#17
differentiating general solution in Sec. 15.2 and solve for 18#18:

19#19

15.3 Rigid-Body Motion
rigid-body motion: no relative motion of points w.r.t. one another
rigid-body motion: points maintain fixed position relative to one another
rigid-body motion: all points move with the body as a whole
20#20: rotation matrix
21#21: translation vector
22#22: initial position of given point
23#23
24#24: position of given point at time 25#25
rigid-body motion in displacement vectors:

26#26

velocity vector: time derivative of its position:

27#27

since 28#28

29#29

(a) translational-motion field under projection onto hemispherical surface
only translational-component motion useful in determining scene structure
(b) rotational-motion field under projection onto hemispherical surface
rotational-motion field provides no information about scene structure
=====Nalwa, A Guided Tour of Computer Vision, Fig. 8. 15=====

we can describe rigid-body motion in instantaneous velocity by

30#30

31#31: angular velocities in three axes
32#32: translational velocities in three axes
from rigid-body-motion equation

33#33

and perspective projection equation

34#34

we can determine an expression for 35#35:

36#36

after simplification

37#37

image velocity: expressed as sum of translational field and rotational field

1#1: 3D coordinate before rigid-body motion in displacement vectors
38#38: 3D coordinate after rigid-body motion in displacement vectors
39#39: rotation angles in three axes
40#40: translation in three axes
rigid-body motion in displacement vectors:

41#41

42#42

motion in displacement vector and instantaneous velocity is different:
e.g. moon encircling earth
instantaneous velocity: first order approximation of displacement vector
first order approximation: when 43#43 small, 44#44
first order approximation: when time=1 thus 45#45
first order approximation: 46#46

47#47

=====Garfield 17:26=====

15.4 Linear Algorithms for Motion and Surface Structure from Optic Flow

15.4.1 The Planar Patch Case
48#48: arbitrary object point on planar patch at time 25#25
49#49: central projective coordinates of 24#24 onto image plane 50#50

51#51

52#52

53#53

54#54: instantaneous velocity of moving image point 49#49
55#55: optic flow image point
56#56: instantaneous rotational angular velocity
57#57: instantaneous translational velocity
unit vector 58#58: orthogonal to moving planar patch
rigid planar patch motion represented by rigid-motion constraint:

30#30

59#59

from above two equations:

60#60

let

61#61

62#62

rigid-motion constraint could be written as:

63#63

denote the 64#64 matrix 65#65 by 66#66 and its three row vectors by 67#67
66#66: called planar motion parameter matrix
68#68 since 69#69 skew symmetric
above equation can be written as:

70#70

from perspective projection equations:

71#71

taking time derivatives of these equations, we have

72#72

substitute equations into above equations:

73#73

from third row:

74#74

substitute 35#35 to obtain optical flow-planar motion equation:

75#75

we have 76#76 linear equations: 77#77:

78#78

optic flow-planar motion recovery: first solve 66#66, then find 79#79

15.4.2 General Case: Optic Flow-Motion Equation
1. set up optic flow-motion equation not involving depth information
2. solve it by using linear least-squares technique

15.4.3 A Linear Algorithm for Solving Optic Flow-Motion Equations

15.4.4 Mode of Motion, Direction of Translation, and Surface Structure
mode of motion: whether translation 80#80 or not
direction of translation: direction of 81#81
surface structure: relative depth when 82#82

15.4.5 Linear Optic Flow-Motion Algorithm and Simulation Results
motion and shape recovery algorithms should answer three questions:

1. minimum number of points to compute motion and shape
2. what set of optic flow points violate rank assumption e.g. collinearity ...
3. what's the accuracy of estimated motion from noisy optic flow?
=====Oldie 33:74=====

15.5 The Two View-Linear Motion Algorithm

15.5.1 Planar Patch Motion Recovery from Two Perspective Views: A Brief Review

Two View-Planar Motion Equation
imaging geometry for two view-planar motion
=====Fig. 15.1=====
rigid planar patch in motion in half-space 83#83
84#84: arbitrary object point before motion
85#85: same object point after motion
86#86: central projective coordinates of 87#87
3#3: camera constant

88#88

89#89

90#90: 64#64 rotational matrix, 91#91
92#92: 93#93 translational vector
94#94: 93#93 normal vector
rigid-body-motion equation relates 95#95 to 96#96 as follows:

97#97

planarity constrains 95#95 by

98#98

combining two equations produces planar rigid-body-motion-equation:

99#99

15.5.2 General Curved Patch Motion Recovery from Two Perspective Views: A Simplified Linear Algorithm
discard planar patch assumption, consider general curved patch

15.5.3 Determining Translational Orientation

15.5.4 Determining Mode of Motion and Relative Depths

15.5.5 A Simplified Two View-Motion Linear Algorithm

15.5.6 Discussion and Summary
when no noise appears: algorithm extremely accurate
when small noise appears: it works well except mode of motion incorrect

15.6 Linear Algorithm for Motion and Structure from Three Orthographic Views
Ullman (1979) showed that for the orthographic case four-point correspondences over three views are sufficient to determine the motion and structure of the four-point rigid configuration.
=====Shimon Ullman, The Interpretation of Visual Motion, =====
=====The MIT Press, Cambridge, MA, 1979 =====
to infer depth information: translation needed in perspective projection
to infer depth information: rotation useless in perspective projection
to infer depth information: rotation needed in orthographic projection
to infer depth information: translation useless in orthographic projection
=====depth from motion=====

15.6.1 Problem Formulation
image plane stationary, three orthographic views at time 100#100
1#1: object-space coordinates of point 101#101 at 102#102
38#38: object-space coordinates of point 101#101 at 103#103
104#104: object-space coordinates of point 101#101 at 105#105
2#2: image-space coordinates of 101#101 at 102#102
106#106: image-space coordinates of 101#101 at 103#103
107#107: image-space coordinates of 101#101 at 105#105
108#108: rotation matrix
109#109: translation vector

110#110

111#111

known:
• four image-point correspondences:
112#112
unknown:
• 113#113
• 114#114
note that with orthographic projections

115#115

116#116

117#117

therefore it is obvious that 118#118 can never be determined
we are trying to determine: 119#119

15.6.2 Determining 120#120

15.6.3 Solving a Unique Orthonormal Matrix 121#121

15.6.4 Linear Algorithm to Uniquely Solve 122#122

15.6.5 Summary
Given two orthographic views, one cannot finitely determine the motion and structure of a rigid body, no matter how many point correspondences are used, as shown by Huang.

15.7 Developing a Highly Robust Estimator for General Regression

15.7.1 Inability of the Classical Robust M-Estimator to Render High Robustness
classical robust estimator, such as M-, L-, or R-estimator:

1. optimal or nearly optimal at assumed noise distribution
2. relatively small performance degradation with small number of outliers
3. larger deviations from assumed distribution do not cause catastrophe
MF-estimator with new property much stronger than property 3
1. relatively small performance degradation with larger deviations from assumed distribution

15.7.2 Partially Modeling Log Likelihood Function by Using Heuristics
MF-estimator: combine Bayes statistical decision rule with heuristics
MF-estimator: robust regression 123#123 more appropriate model-fitting

15.7.3 Discussion
M-, L-, R-, and MF-estimator: all residual based

15.7.4 MF-Estimator

15.8 Optic Flow-Instantaneous Rigid-Motion Segmentation and Estimation
formulate optic flow-single rigid-motion estimation into general regression

15.8.1 Single Rigid Motion

15.8.2 Multiple Rigid Motions
=====joke=====

15.9 Experimental Protocol

15.9.1 Simplest Location Estimation

15.9.2 Optic Flow-Rigid-Motion Segmentation and Estimation

15.10 Motion and Surface Structure from Line Correspondences

15.10.1 Problem Formulation
Cartesian reference system-central projection
=====Fig. 15.8=====
124#124: line in 3D space
125#125: projection of the line on image plane 50#50
50#50: image plane
126#126: known plane line 125#125 is in; projective plane of 124#124
127#127: set of lines in 3D space
128#128: lines moved by rigid motion 129#129 at time 130#130
131#131: lines moved by rigid motion 132#132 at time 133#133
134#134: projections of lines
135#135; respective projective planes
known:

• 136#136 triples of line correspondences in three views
137#137
unknown:
• rotations and translations: 138#138
• 3D lines 139#139

15.10.2 Solving Rotation Matrices 140#140 and Translations 141#141

15.10.3 Solving Three-Dimensional Line Structure

15.11 Multiple Rigid Motions from Two Perspective Views

15.11.1 Problem Statement
imaging geometry for two-view-motion
=====Fig. 15.9=====
How many good point correspondences are needed in order to apply the nonlinear least-squares estimator?

15.11.2 Simulated Experiments

15.12 Rigid Motion from Three Orthographic Views

15.12.1 Problem Formulation and Algorithm
same as Sec. 15.6, instead of linear algorithms, formulate model-fitting problem

15.12.2 Simulated Experiments

15.12.3 Further Research on the MF-Estimator
two problems to be solved for MF-estimator to be practically useful:

• distance problem
• requirement for a good initial approximation
difficulty of motion and shape recovery: ambiguity of displacement field
=====Fuh, Ph.D. Thesis, Fig. 4.1=====

15.13 Literature Review

15.13.1 Inferring Motion and Surface Structure
classifications for methods of inferring 3D motion and shape

• use of individual sets of feature points
• use of local optic flow information about a single point
• use of the entire optic flow field
Despite all the results obtained over the years, almost none of these inference techniques have been successfully applied to feature-point correspondences calculated from real imagery.

15.13.2 Computing Optic Flow or Image-Point Correspondences
problem source contains abundant information

• occlusion boundaries
• specular points
• near a focus of expansion
• noise and digitization effects in image formation
motion parallax: apparent relative motion between objects and observer
points in observer's direction of translation remain relatively unchanged
information available to a moving observer
=====Nalwa, A Guided Tour of Computer Vision, Fig. 8.1=====
impart time dimension to image data
spatiotemporal image data block
=====Nalwa, A Guided Tour of Computer Vision, Fig. 8.2=====
motion field: assignment of vectors to image points representing motion
angular velocity of fixed scene: inversely proportional to distance
pilot in straight-ahead level flight on an overcast day
=====Nalwa, A Guided Tour of Computer Vision, Fig. 8.3=====
motion field of pilot looking straight ahead in motion direction
zero image velocity: at approach point and at infinity (along horizon)
=====Nalwa, A Guided Tour of Computer Vision, Fig. 8.5=====
motion field of pilot looking to the right in level flight
focus of expansion here: at infinity to the left
focus of contraction here: at infinity to the right of the figure
=====Nalwa, A Guided Tour of Computer Vision, Fig. 8.6=====
spatiotemporal image data acquired by a camera, --caption--
straight streaks at block top due to translating parallel to image plane
=====Nalwa, A Guided Tour of Computer Vision, Fig. 8.10=====

B. K. P. Horn, Robot Vision, The MIT Press, Cambridge, MA, 1986.
Chapter 12 Motion Field & Optical Flow

optic flow: apparent motion of brightness patterns during relative motion
arrows: represent angular velocities, which are zero directly ahead and behind
J. J. Gibson's example of flow induced by motion
=====Marr, Vision, Fig. 3-55=====

12.1 Motion Field
motion field: assigns velocity vector to each point in the image
142#142: some point on the surface of an object
143#143: corresponding point in the image
144#144: object point velocity relative to camera
145#145: motion in corresponding image point
146#146: distance between perspectivity center and image point
147#147: distance between perspectivity center and object point
148#148: camera constant
149#149: depth axis, optic axis
object point displacement causes corresponding image point displacement
=====Horn, Robot Vision, Fig. 12.1=====
velocities:

150#150

where 147#147 and 146#146 are related by

151#151

differentiation of this perspective projection equation yields

152#152

=====joke=====

12.2 Optical Flow
optical flow need not always correspond to the motion field
(a) perfectly uniform sphere rotating under constant illumination:
no optical flow, yet nonzero motion field
(b) fixed sphere illuminated by moving light source:
nonzero optical flow, yet zero motion field
=====Horn, Robot Vision, Fig. 12.2=====
apparent motion of brightness patterns: awkward concept
not easy to decide which 153#153 on contour 154#154 corresponds to 101#101 on 155#155
=====Horn, Robot Vision, Fig. 12.3=====
optical flow: not uniquely determined by local information in changing image
156#156: irradiance at time 25#25 at image point 157#157
158#158: 159#159 components of optical flow vector
assumption: irradiance the same at time 160#160 at point 161#161

162#162

fact: motion field continuous almost everywhere
expand above equation in Taylor series

163#163

164#164: second- and higher-order terms in 165#165
cancelling 156#156, dividing through by 166#166:

167#167

which is actually just the expansion of the equation

168#168

abbreviations:

169#169

170#170

we obtain optical flow constraint equation:

171#171

flow velocity 2#2: lies along straight line perpendicular to intensity gradient
=====Horn, Robot Vision, Fig. 12.4=====
rewrite constraint equation:

172#172

aperture problem: cannot determine optical flow along isobrightness contour

12.3 Smoothness of the Optical Flow
motion field: usually varies smoothly in most parts of image
try to minimize a measure of departure from smoothness

173#173

error in optical flow constraint equation should be small

174#174

overall, to minimize 175#175:

176#176

8#8: large if brightness measurements are accurate
8#8: small if brightness measurements are noisy

12.4 Filling in Optical Flow Information
regions of uniform brightness: optical flow velocity cannot be found locally
brightness corners: reliable information is available

12.5 Boundary Conditions
well-posed problem: solution exists and is unique
partial differential equation: infinite number of solution unless with boundary

12.6 The Discrete Case
first partial derivatives of 177#177: can be estimated using difference
=====Horn, Robot Vision, Fig. 12.5=====
measure of departure from smoothness:

178#178

error in optical flow constraint equation:

179#179

to seek set of values 180#180 that minimize

181#181

differentiating 164#164 with respect to 182#182:

183#183

184#184

where 185#185 are local average of 177#177 (9 neighbors?)
extremum occurs where the above derivatives of 164#164 are zero:

186#186

187#187

determinant of 188#188 coefficient matrix:

189#189

so that

190#190

191#191

suggests iterative scheme such as

192#192

193#193

new value of 2#2: average of surrounding values minus adjustment
=====Horn, Robot Vision, Fig. 12.6=====
first derivatives: estimated using first differences in 194#194 cube
=====Horn, Robot Vision, Fig. 12.7=====
consistent estimates of three first partial derivatives:

195#195

196#196

197#197

198#198

199#199

200#200

four successive synthetic images of rotating sphere
=====Horn, Robot Vision, Fig. 12.8=====
estimated optical flow after 1, 4, 16, and 64 iterations
=====Horn, Robot Vision, Fig. 12.9=====
(a) estimated optical flow after several more iterations
(b) computed motion field
=====Horn, Robot Vision, Fig. 12.10=====

12.7 Discontinuities in Optical Flow
discontinuities in optical flow: on silhouettes where occlusion occurs
=====joke=====

Project due April 26:
implementing Horn & Schunck optical flow estimation as above
synthetically translate lena.im one pixel to the right and downward
Try 8#8 of 0.1, 1, 10

2002-02-26