Advanced Topics – I (EENG 4010)

Computer Vision & Image Analysis

(EENG 5640)
 Introduction to Computer Vision

Image
Processing
System
Image Image

Computer Vision/ Image/

Image Analysis/ Image Scene
Understanding System Description
Image
Pattern Pattern
Pattern Vector (with
Recognition Classification
Image measurements
System Label
as components in the
current application)
Computer Vision generally involves pattern recognition
Typical Computer Vision
Applications

 Medical Imaging
 Automated Manufacturing (some experts
use Machine vision as the term to describe
Computer Vision for Industrial applications;
others use it as synonym for computer vision)
 Remote Sensing
 Character Recognition
 Robotics
Binary Image Analysis

 Grey scale to Binary transformation (Otsu’s

method)
 Counting holes
 Counting objects
 Connected Component Labeling Algorithms
– Recursive Algorithm
– Two Pass Row by Row Labeling Algorithm
Two-Pass Algorithm: Illustrative
Example

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2
1 1 1 1 1 1 2 2
1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2
1 1 1 1 1 1 2 2
2
1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 1 1 1 4 4 4 2 2 2
1 1 1 1 3 3 4 4 3
1 1 1 1 3 3 4 4
1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 3
4
1 1 1 1 1 1 1 1 1 1 1 3 3 3 3 3 3 3 3 3 3 3

1 2 3 4 -- Label
0 1 1 2
Parent
Binary Image analysis (Contd.)

 Morphological Processing
– Dilation, Erosion, Opening and Closing
Operations
– Example to Illustrate the effects of the operations
 Region Properties
– Area
– Perimeter
– Circularity
Medical Application of Morphology
Industrial Application of
Morphology
Grey Level Image Processing

 Image Enhancement Methods

– Histogram Equalization and Contrast Stretching
– Mitigation of Noise Effects
 Image Smoothing
 Median Filtering
 Frequency Domain Operations (Low Pass Filtering)
 Image Sharpening and Edge Detection
– High Pass Filtering
– Differencing Masks (Prewitt, Sobel, Roberts, Marr-
Hildreth operators)
– Canny Edge Detection and Linking
 Histogram Equalization- Original
Image
Histogram Equalization- Equalized
Image
Low Contrast Image
Contrast Stretching (Linear
Interpolation between 79-136)
Histogram Equalization
 Color Fundamentals

[0, 1, 1] [0, 1, 0] [1, 1, 0]

[0, 0, 1] Cyan Green yellow
Blue

[1, 0, 1] [1, 1, 1] [1, 1, 1]

Magenta White White
[0, 1, 1] [1, 0, 0]
Cyan Red
[0, 0, 0] [0, 1, 0]
Black Green

[1, 0, 0] [1, 0, 1]
Red [0, 0, 1] Magenta
[1, 1, 0] Blue
yellow
RGB and HSI (HSV) Systems
RGB-HSI Convesion
RGB to HSI Conversion- Final
Formulae
HIS-RGB Conversion

Method is given. You need to reason out why? Or explore web for answer.
YIQ and YUV Systems for TVs, etc.

YIQ system is used in TV Signals. Its components are:

Luminance Y = 0.30R + 0.59G + 0.11B
R-Cyan I = 0.60R - 0.28G - 0.32B
Magenta-Green Q = 0.21R - 0.52G + 0.31B

In some digital products and JPEG/MPEG Compression

algorithms, YUV System as follows is used:
Y = 0.30R + 0.59G + 0.11B
U = 0.493* (B – Y)
V = 0.877*(R – Y)

Advantage: Luminance and Chromaticity components can

be coded with different number of bits.
Optical Illusion - I
Optical Illusion - II
Optical Illusion - III
Texture

 Pattern caused by a regular spatial arrangement

of pixel colors or intensities.
 Two approaches
– Structural or Syntactic (usually used in case of
synthetic images by defining a grammar on texels).
– Statistical or quantitative (more useful in natural
texture analysis; can be used to identify texture
primitives (texels) in the image.
Quantitative Texture Measures

 Edge related
– Edginess (proportion of strong edges in a small
window around pixels.
– Edge direction histograms (the pattern vector
constituted by the proportion of the edgels in the
horizontal, vertical, and other quantized
directions among the total pixels in a chosen
window around a pixel (I,j) under consideration
 Co-occurrence matrix based
Co-occurrence matrix based
Measures

 Construction of Co-occurrence matrix Cd [i,j]

where d is the displacement of j from i (e.g.
(0,1), (1, 1), etc.
 Normalized and symmetric co-occurrence
matrices Nd [i,j] and Sd [i,j].
 Zucker and Terzopoulos’s Chi-square metric to
choose the best d (i.e. d with most structure).
 Numeric measures from Nd [i,j]
Choice of the Best Co-occurrence
Matrix and Computation of Features
Laws’ Texture Energy Measures

 Simple because masks are used

 2-D masks are created using 1-D masks:
– L5 (Level) = [ 1 4 6 4 1]
– E5 (Edge) = [-1 -2 0 2 1]
– S5 (Spot) = [-1 0 2 0 -1]
– W5 (Wave) = [-1 2 0 -2 1] (not in the text!)
– R5 (Ripple) = [ 1 – 4 6 -4 1]
(e.g. 5x5 matrix of L5E5 mask is obtained by
multiplying transpose of L5 by E5).
Laws’ Algorithm for Texture Energy
Pattern Vector Construction
Laws’ Texture Segmentation Results- I
Laws’ Texture Segmentation Results- II
Laws’ Texture Segmentation Results- III
Gabor Filter Based Texture
Analysis

Gabor Filter is mathematically represented by (refer

Wikipedia):

Where

and

θ  Orientation of the normal to parallel stripes

λ  Wavelength or inverse of the frequency of the cosine function

g  Spatial aspect ratio σ  Sigma of the Gaussian function

ψ  Phase offset of the cosine function

Image Segmentation

Image Segmentation

Contour-Based Methods Region-Based Methods

(e.g. Canny Edge
Detection and Linking)

Partitioning/Clustering (e.g. K-Means Region Growing

Clustering, Isodata clustering, (e.g. Haralick and
Ohlander’ et al.’s recursive histogram- Shapiro Method)
based technique)
Clustering Algorithms

 Clustering (partitioning) of pixels in the pattern space

 Each pixel is represented by a pattern vector of
properties. For example, in case of a colored image,
we could have
 could be of any dimensionality (even 1, i.e.
could be a scalar as in case of a grey level image).
 Depending upon the problem, may include other
measurements on texture, shading, etc. that
constitute additional dimensional components of the
pattern vector.
Note: i and j denote pixel row & columns.
K-Means Clustering algorithm
Isodata Clustering Algorithm

T
ISODATA Clustering Problem

 4   2 .8 
m1    m2    m3   
  .1 4  m3

m2
m1
g
1 0 1 0 3 1
1    2    3    r
 0 1   0 1  1 3
To which cluster does X belong to?

 2 If split threshold TS = 3.0 and Merge Threshold TM = 1.0,

X   what will be the new cluster configuration?
 2 Get new cluster means in case of a
Split.
Image Databases- Content-Based
Image Retrieval

Any Problem with Traditional Text (in Caption) Based Retrieval?

Typical SQL (Structured Query Language) Query:

SELECT * FROM IMAGEDB
WHERE CATEGORY = ‘GEMS’ AND SOURCE = ‘SMITHSONIAN’
AND (KEYWORD = ‘AMETHYST’ OR KEYWORD = ‘CRYSTAL’
OR KEYWORD = ‘PURPLE’)

This will retrieve the gem collection of the Smithsonian Institute from its
IMAGEDB database restricting its search based on the logical
combination of the keyword specified.

Looks like no problem here!

Limitations of the Key Word Based
Retrieval

 Human coding of key words is expensive; but

still some keywords by which one likes to
retrieve the image cannot be visualized and
hence may be left out. Key words may
sometimes retrieve unexpected images as
well!
 What kind of images do you expect with the
key word ‘pigs’?
Unexpected Retrieval- An Example
Content-Based Image Retrieval

 Uses Query-By-Example (QBE) Concept

 IBM’s QBIC (Query By Image Content) is the
first system
 In QBE systems, you specify an example
plus some constraints
 Typical example images for specification-
– A digital Photograph
– User painted drawing
– A line-drawing sketch
Matching- Image Distance
(Similarity Measures)

4 Major classes:
 Color Similarity
 Texture Similarity
 Shape Similarity
 Object and relationship similarity
Color Similarity Measures

 QBIC lets the user choose up to 5 colors

from the color table and specify their
percentages
 Color histograms (K-bin) can be used
Dhist ( I , Q)  (h( I )  h(Q)) A(h( I )  h(Q))
T

Here h(I) and h(Q) are K-bin histograms of

images I and Q, and A is (K x K) similarity
matrix.
Color-Layout-Based Similarity

 Distances between corresponding grid

squares of the database and example
images are found and summed up.
Dgridded _ color ( I , Q)   Dcolor (C I ( g ), C Q ( g ))
g
 Each grid square spans over multiple pixels.
Then how do you compare grid squares?
– Use Mean Color
– Use Mean and Standard Deviation
– Use Multi-bin Histogram
Texture-Based Similarity Measure

 Pick-and-Click distance
D pick _ and _ click ( I , Q)  min iI || T (i)  T (Q) || 2
 Grid based texture similarity can be found by
the same process as in the gridded color
case
Dgridded _ texture( I , Q)   Dtexture(T I ( g ), T Q ( g ))
g
Shape-Based Similarity Measures

 Histogram approach is difficult to apply

particularly when you want scale and rotation
invariance.
 Boundary Matching
 Granlund’s Fourier Descriptors for
Translation, Scale, starting point (for
boundary tracing), and rotation invariant
matching.
Boundary (Sketch) Matching

 Obtain a normalized image- reduce the original

image to a fixed size, e.g., (64x64) & median filter
 2 stage edge detection-global and local
thresholds.
 Perform linking and thinning.
 Find Correlation between line drawing (L)’s grid
square and various shifts (n) of the DB image A’s
grid square & sum up best correlations.
1
Dsketch ( I , Q) 
 max n[ Dcorrelation (shiftn ( AI ( g )), LQ ( g ))]
g
Line Sketch of a Horse
Retrieved Images of Paintings
 Granlund’s Fourier Descriptors

 Let be the points on the

boundary of the query shape.
 The k-th discrete Fourier coefficient is given by

 Leaving out and , we can compute

translation, rotation, starting-point and scale
invariant shape descriptors ) as follows:
Invariant Properties of Fourier
Descriptors

 Translation

 Rotation |.|
takes care of the problem because
 Scale By using
for scaling, we are eliminating c.
 Starting point- Once again |.| operation helps!
Relational Similarity

 Spatial Relationship- relational graphs indicating

inter-object relationships can be constructed.
Once objects are identified, relationships can be
matched, by graph matching techniques.
 Abstract Relationship- Happy face; it involves
separation and identification of a face region
first, and then checking whether it is a happy or
sad face.
Matching in 2D

 Transformation- Mapping from one coordinate

space to another.
– linear or nonlinear (called warps)
– one to one correspondence between points if linear
– Invertible or non-invertible
 Image Registration- Process of establishing
point by point correspondence between two
images of a scene.
Affine Transformation (Mapping)

 Wikipedia Definition: Affine (Latin affinis 

Connected with) mapping between two vector
(affine) spaces is a linear transformation followed
by translation.
 It preserves:
– Collinearity of points
– Ratios of distances along a line
Image Operations Represented by
Affine Transformation

 Can we write the affine transformation

Y = A.X + t (Can we absorb t into A)?
 For scaling and rotation, yes.
 For translation, does not seem to be
possible. What is the way out?
Homogeneous Coordinates

 Introduced by August Ferdinand Mobius (1790-

1868), a German mathematician and theoretical
astronomer.
 (x, y)  (w.x, w.y, w); (2.x, 2.y, 2) = (3.x, 3.y, 3)
 (x, y, z)  (w.x, w.y, w.z, w); Same concept an
be extended to any n-dimensional space.
 You can represent a point at infinity (how?)
Usage of Homogeneous Coordinates

 The rotation, scaling, and translation can be

modeled as matrix multiplication operations as
follows:

 If control (easily distinguishable) points of two

images are identified, and registered with an
affine mapping, it is easy to identify the presence
of the same object(s) in both- Recognition by
Alignment.
Shears and Reflections
(1, 1+ex)
(1, 1) (1+ey, 1)
(0, 1) (0, 1) (1, 1)
(ey, 1)
y

y
(1, ex)
(0, 0) (1, 0)
x (0, 0) (1, 0)
Horizontal Shear x
Vertical Shear

Reflections about x-axis (x, y)  (x, -y)

Reflections about y-axis (x, y)  (-x, y)
You can express these also as an affine transformations.
General Affine Transformation

 You may consolidate all the previous affine

transformations (translation, rotation, scale,
shear, and reflection) into the general affine
transformation as follows:
Best 2D Transformation with Least-
Squares Fitting

 Let (xj, yj), j = 1, n the control points in an image,

and (x’j, y’j) are the corresponding points in the
transformed image. Then the least-squares fit
method seeks to minimize the error:

 Setting the 6 partial derivatives of the form

corresponding to the 6 translation parameters to
zero, we get 6 equations for 6 unknowns.
2D-Object Recognition via Affine
Mapping- Local Feature Focus
Method

Local-Feature-Focus-Method F2 F3
G2
{ G1
For each pair of model and image F1 F4
G4 G3
features Model F
{ G8
Find the maximal subset of G5
G6 G7 E1 E4
matching neighboring features;

Find Best T; E2

E3
If enough features align, confirm
the presence of the model object; Image
Model E
}
}
2D-Object Recognition via Affine
Mapping- Pose Clustering Method

Pose-Clustering-Method (P, L)
{
// P is the set of image features
‘L’ Junction ‘Y’ Junction ‘T’ Junction
// L is the set of stored model features
For each pair (Pi, Pj) of image features
For each pair (Lm, Ln) of model features
of the same type
{ Arrow ‘X’ Junction
Compute the affine (RST) parameters a Junction
Each a will be a point in the parameter space Some Typical
} Model Features
Examine the parameter space for large cluster modes
return all ak ‘s corresponding to dominant modes
}
2D-Object Recognition via Affine
Mapping- Geometric Hashing
e10 Te01
• Useful when model database (DB) e01
is very large and an object in the x
Tx
image is known to be an affine
transform of one of the DB models e00 Te10
• If e00, e01, and e10 are any three non-collinear feature
Te00
points from the model feature point set M, any point x e
M can be represented as follows using the affine basis
set (coordinate set) constructed from these 3 points:
x = x(e10 – e00) + h(e01 – e00) + e00
• We use the property that under an affine transform,
the same relation holds:
Tx = x(Te10 – Te00) + h(Te01 – Te00) + Te00
Geometric Hashing Method (Contd.)

GH-Offline-Preprocessing (D, H)
{
//D- Database Model Set
// H- Initially empty hash table
for each model M in D
{
Extract feature set FM;
For each non-collinear triplet E of FM
For each other point x of FM
{
Calculate (x, h) for x with respect to E
Store (M, E) in the table H at index (x, h)
}
}
}
Geometric Hashing Method (Contd.)

GH-Online-Recognition (D, H)
{
//- Database Model Set; H- Hash table constructed in the offline processing
for each possible (M, E) tuple in the database
{
set Bin-Count (M, E) = 0;
}
Extract image feature set FI;
for each non-collinear triplet E of FI and for each other point x of IM
{
Calculate (x, h) for x with respect to E;
Retrieve (M, E) pairs in the table H at index (x, h);
Increment the Bin-Count of those (M, E) pairs;
}
Return (M, E) values with highest Bin-Count values.
}
Practical Problems in Geometric
Hashing

 Errors in feature point coordinates

 Missing and extra feature points
 Occlusions and multiple objects
 Unstable bases
 Weird affine transforms on subsets
(a) Image Points
points and consequent hypotheses
for presence of hallucinated
objects (This problem is present in (b) Hallucinated Object
pose clustering and focus feature
methods also).
General Framework for 2D-Object
Recognition via Relational Matching

 Consistent Labeling Problem is a 5-tuple

(P, L, RP, RL, f)
 P- Object Parts (found in the image)
 L- Object Labels (names of stored model features)
 RP – Set of Relationships between Parts;
 RL – Set of Constraint Relationships between Labels
 f is a mapping such that
if (pi, pj) e RP, then (f(pi), f(pj)) e RL
Brute Force Method for Consistent
Labeling - Interpretation Tree Search
Bool Interpretation-Tree-search(P, L, RP, RL, f)
C1 C2 C5 C6
{ H3 H4
p = first(P); H2
for each I in L { H1
f’ = f U {(p, I)};//add part-label to interpretationC4 C3
C7 C8
OK = true; (a) Labels P1
P2
for each N-tuple (p1, …, pN) in RP containing p {
if ( f ' ( p1 ),..., f ' ( pn ))  RL then OK = false; break; } P4 P5
if OK then { Nil P3
P’ = P – {p}; P4
if is-empty(P’) then output(f’); else P1 = H1 (b) Image
Interpretation-Tree-Search(P’, L, RP, RL, f’) } P1 = C1 Parts
} (c) Interpretation Tree
Discrete Relaxation Labeling
Discrete Relaxation Labeling(P, S, R)
{ // Pi , i = 1, …, D, is the set P of the detected image features
// S is the set of sets S(Pi ), i = 1, …, D, of initially compatible labels for Pis
// R = set of relationships over which compatibility is determined
repeat
{
for each (Pi, S(Pi))
{
for each label Lk e S(Pi)
for each relation R(Pi, Pj) over image parts
If there exists Lm e S(Pj) with R(Lk, Lm) in model
then keep Lk in S(Pi) else delete Lk from S(Pi)
}
} until no change in any S(Pi)
return (S)
}
Continuous (Probabilistic)
Relaxation

iter  0
pri0 (l )  pri (l )
Loop on i and iter until labels of all parts stabilize and become unique

qiiter l    ij  ij
C r (l , l ' ) pr iter
j (l ' )
{ j|( i , j )RP } l 'L j
compatibility values
iter
 iter
priiter1 l  
pri ( l )( 1 q i (l ))

 i
pr
l 'Li
iter
( l ' )(1  q iter
i (l ' ))
Extraction of 3D Information from 2D
Images- Shape from “X” Techniques

 Direct 3D perception- Range Imaging (Costly)

 How do human perceive depth/3D shape?
– Stereo
– Shading
– Monocular cues, e.g., Relative depth information
from occlusions of the background objects by
foreground objects, perspective view with farther
objects appearing smaller with distance
 Shape from X (X = binocular stereo/
photometric stereo/shading/texture/
boundary/motion
Binocular Stereo

P
x'

x’’ d x’/f = OP/(f + z)

x’’/f = (OP + d) / (f + z)
(x’’-x’)/f = d/(f + z)
z = f . d /(x’’ – x’) - f
f z

Depth can be inferred from the disparity (x’’-x’)

Only problem remains to be solved is the
correspondence problem.
Surface Orientation from
Reflectance Models

i = angle of incidence
z n ng
ns y e = angle of emittance
i g g = phase angle
e n, ng, and ns are unit vectors along
the surface normal, view direction,
and source direction, respectively.
x
For specular (smooth mirror-like) surfaces, maximum amount of light is
reflected in the direction of what is called specular angle, and it reduces
in the directions away from this one. An estimate of the cosine of the
difference between the specular and viewing angles is given by:
C = 2cos(i) cos(e) – cos (g). For dusty/matte (Lambertian) surfaces,
reflectivity in any direction is proportional to angle of incidence. A
general formula that includes both effects is:
L(i, e, g) = s Cn + (1 – s) cos (i) 0 <= s <= 1. Larger the
n, sharper the peaking in the specular direction.
Reflectance Map for Lambertian
Surfaces

q
R = r0 [Link] … (1)
The spatially varying reflectance
factor r0 is called albedo. For a
surface z = f(x, y), let
0.9 p = z/x and q = z/y
0.8
p z= (z/x).  x+ e  p.  x
z n y (x, 0, p.x )T || l to (1, 0, p)T = rx, say
0.7
(0, y, p.y)T || l to (0, 1, q)T = ry, say
n  rx x ry = (-p, -q, 1)T
x ns  (-ps, -qs, 1) r
x Putting in (1), we
get R(p, q)
Photometric Stereo

With 3 sources of light

Rk(x, y) = Ik(x, y) = ro(nk.n) k = 1, …, 3

I = r0 N. n where I = [I1(x, y), I2(x, y), I3(x, y) ]T and

q
R2(p, q) = 0.75
R1(p, q) = 0.9
ro = |N-1 I| Solution point
n = 1/ r0 . N-1 I p
R3(p, q) = 0.5
Shape from Shading

We know that (-p, -q, 1) is the vector in the direction of surface normal
and (-ps, -qs, 1) is the corresponding vector for source direction, the
reflectance (i.e. image intensity) for a Lambertian surface is given by:

At each pixel site (k, l) we need to find the best (pkl, qkl) pair that gives an
Rkl matching with the image intensity Ekl. In other words, we minimize

This may not have unique solution. Hence, we used in photometric stereo 3
images to resolve the ambiguity. Here we use surface continuity for the same:

Overall we minimize
We get the final solution by setting and
Shape from Shading- Ikeuchi’s
Relaxation Approach

Continuing from the previous slide by setting and , we get

and
Now, the equations for obtaining p and q iteratively by Ikeuchi’s relaxation
approach are:

Mask to compute
average p and q

Advantage: Relaxation method can enforce the boundary conditions and get
good solutions.
Limitation: In the current formulation, occluding boundary
with p and q at  causes a problem. How to solve this
problem?
 Photometric Stereo by Relaxation
Approach

Same relaxations equations can be extended to the photometric stereo

problem involving n (= 2 or more) images:

Here and represent the intensity at the pixel site in the image
captured with the th light source, and the corresponding reflectance map,
respectively.
Advantage: Relaxation method can enforce the boundary conditions and get
good solutions.
Limitation: In the current formulation, occluding boundary
with p and q at  causes a problem. How to solve this
problem? See the next slide!
Solution to the Problem of Infinite
Gradients at Occluding Boundary

Ikeuchi suggested to formulate the problem in polar coordinates and solve!

If P is a point on a surface patch, and OP is a unit normal, the x, y, and z
components of this vector are given by:
(sin . cos , sin . sin , cos ) … (1)
We can represent similarly the x, y, and z components of the unit vector in
the direction the light source with polar coordinates (s, s) as: z
(sin s. cos s, sin s. sin s, cos s) P
Since, for Lambertian surfaces, R = ro. cos i where i is the
angle between the two directions, we can rewrite R as the 
following function of  and : O y
R (,  ) = ro. (sin  sin s cos  cos s + 
sin  sin s sin  sin s + cos  cos s )
= ro. ( sin  sin s cos( - s ) + cos  cos s ). At the x
occluding boundary  = /2 and  = tan-1y/x. The same
equations as before hold with  and  replacing p and q.
From  and  to p and q may be done in the end using (1).
Needle Diagram (Display of Unit
Normal Vectors in the Image Space)

(a) Image of a resin Droplet on a (b) Needle diagram for the image in (a)
flower of a plant
Depth Construction from the (p, q)
tuples (Needle Diagram)
Since p = z/x and q = z/y,

Because of imperfect (p, q) values, this integral may not yield correct values.
The values may be sensitive to the path chosen for integration. Integral
around a close loop of pixels may not vanish. Hence, better approach is to
choose p and q that minimizes:
. From the calculus of variations, an integral

of the form can be minimized by solving the Euler equation:

. For our problem, the Euler equation would yield:

 Z-map Construction Algorithm
1. Convolve the p and q maps with horizontal and vertical Prewitt/Sobel
masks to get px and qy maps and add them up to get s= px+qy map.
2. Start with a random configuration of z-values on the image grid. Or,
preferably obtain a crude z-map by starting with z (0, 0) = 0 and
applying the integral for computing z from p and q values by visiting the
cell sites in raster scan fashion.
3. Convolve the z-image with horizontal Prewitt/Sobel mask to get z/x -
image. Convolve again the resultant image with same mask to get
2z/x2. Convolve again the z-image with vertical Prewitt/Sobel mask to
get z/y -image. Convolve again the resultant image with same mask
to get 2z/y2. Add the two resultant images to get 2z-image.
4. For all (i, j), update zij by zij + e.(2zIj – sij) where e is a small constant.
5. If none of the updated zij s change significantly, stop.
Otherwise, go to step 3.
Moving Objects- Optical Flow
Constraint line
Whether the observer or the scene objects are moving, the relative Ixu+Iyv+It = 0
motion gives a lot of information about depth because the points v
closer to the observer seem to be moving faster. Motion stereo is
the name of phenomenon (or body of techniques) for depth (Ix,Iy)
perception based on motion information.
Brightness patterns in the image move as the objects that
give rise to them move. Optical flow is the apparent motion of the u
brightness pattern. Ix= I/x
Basic optical flow equation: Iy= I/y
Expanding the left hand side by Taylor series and equating terms, It= I/t
we get -

Velocity in the direction of brightness gradient

is given by We can’t determine flow in the iso-

brightness (right angles) direction. This is called aperture problem.

 Optical Flow Estimation- Horn and
Sjoberg’s Relaxation Method
As before, we need to minimize conjointly two constraints:

It Computation

(i, j) (i, j) (i, j) (i, j) (i, j) (i, j)

(i+1, j+1) (i+1, j+1) (i+1, j+1) (i+1, j+1) (i+1, j+1) (i+1, j+1)
Frame t Frame t+1 Frame t Frame t+1 Frame t Frame t+1

Ix Computation Iy Computation
Shape/Structure from Motion

Now, equating each component of , we get:

If are the image point corresponding to the 3-D

object point P, we have from perspective projection:
and (assuming f = 1, and Z >> f). z
v vx, wy, wzT
P = (X, Y, Z)T
Now, the optical flow components and are:
O
and y

Now, using (1), we can get expressions for x

and in terms of Z and 6 motion parameters.
 Shape from Motion- Pure
Translation Case
From the imaging geometry, the (x, y) coordinates of the image points
corresponding to the 3D-Object point (X, Y, Z) are given by:

Now, if we ignore terms related to rotation from the equations of u and v

on the previous slide, we get

In order to match the estimated (u, v) values with computed values, we

need to minimize the function:
Shape/Object Representation and
Recognition

Objects/Shapes

2-D (Planar) 3-D

Representation of closed Surface based
boundaries (Recognition Volumetric/binary voxel
representations(e.g.
Sensitive to Noise and representation (e.g. for 3-D
Coon’s surface
Occlusions) e.g., Fourier medical image constructed
patches represented
Descriptors from 2D-slices)
by 2-D polynomials,
generalized cylinders )
Noise and Occlusion-tolerant Representation of parts
and their interrelationships (e.g., Connectivity,
adjacency). Parts could be regular shaped objects
such as circles, squares, triangles recognizable by
Hough transform, or curve segments represented
using polynomial forms (B-Splines)
Reconstruction Imaging- Computer
Aided Tomography (CAT) Scans

g(x, y)

X-ray source