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

- corresponding unknown 3D points: 12#12
- all points moving with same but unknown velocity 13#13

15.2.2 Focus of Expansion and Contraction

known:

- 3D motion is translational
- one 2D projected point 2#2 has no motion: 14#14

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,

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

- 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,

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:

- minimum number of points to compute motion and shape
- what set of optic flow points violate rank assumption e.g. collinearity ...
- what's the accuracy of estimated motion from noisy optic flow?

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

- 113#113
- 114#114

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:

- optimal or nearly optimal at assumed noise distribution
- relatively small performance degradation with small number of outliers
- larger deviations from assumed distribution do not cause catastrophe

- 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

- 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

=====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

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

points in observer's direction of translation remain relatively unchanged

information available to a moving observer

=====Nalwa,

impart time dimension to image data

spatiotemporal image data block

=====Nalwa,

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,

motion field of pilot looking straight ahead in motion direction

zero image velocity: at approach point and at infinity (along horizon)

=====Nalwa,

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,

spatiotemporal image data acquired by a camera, --caption--

straight streaks at block top due to translating parallel to image plane

=====Nalwa,

B. K. P. Horn, *Robot Vision*, The MIT Press, Cambridge, MA, 1986.

Chapter 12 Motion Field & Optical Flow

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,

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,

first derivatives: estimated using first differences in 194#194 cube

=====Horn,

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,

estimated optical flow after 1, 4, 16, and 64 iterations

=====Horn,

(a) estimated optical flow after several more iterations

(b) computed motion field

=====Horn,

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