Robot Vision (contd.

PROF. (DR.) DILIP KUMAR PRATIHAR

MECHANICAL ENGINEERING DEPARTMENT, IIT KHARAGPUR

1
 Methods of Pre-
Processing
a. Masking

𝑷 ( 𝒙 ,𝒚 )=𝑶 [ 𝒇 ( 𝒙 , 𝒚 )]
Pre-processed Input
intensity operator intensity

2
 f(x,y) : Light intensity value at y
pixel Q
x
f(x-1,y-1) f(x-1,y) f(x-1,y+1)
f(x,y-1) Q: f(x,y) f(x,y+1)
f(x+1,y-1) f(x+1,y) f(x+1,y+1
)
Let us consider the pixel Q having the coordinates (x,y).
It has two horizontal and two vertical and four diagonal
neighbors.

3
Let us consider a 3x3 mask with coefficients W1, W2, W3,
W4, W5, W6, W7, W8,and W9.

W1 W2 W3 -1 -1 -1
W4 W5 W6 -1 +8 -1
W7 W8 W9 -1 -1 -1
Example of a 3x3 mask

4
𝑷 ( 𝒙 ,𝒚 )=𝑶 [ 𝒇 ( 𝒙 , 𝒚 )]

5
b. Neighborhood Averaging

Here, p(x,y) is calculated by averaging the intensity

values of the pixels contained in a pre-defined
neighborhood of f(x,y).

Where, S is the set of pixels lying in the neighbourhood

of (x,y) including itself and R is the total number of
neighbourhood pixels including itself.

6
c. Median Filtering

To determine pre-processed light intensity value of a pixel Q,

we consider light intensity values of all its neighboring pixels
including itself. We sort light intensity values in the ascending
order say, and then determine the median value. This median
value is going to replace the intensity value at Q.

7
Step 5: Thresholding
• To get clear distinction between objects and the
background, let T be the threshold intensity
0 0 0 0 0 0 Y
0 0 1 1 1 0
0 0 1 1 0 0
For the black background and white0 0 1 1 0 0
object, 1 corresponds to object and 0 0 1 0 0 0
0 indicates the background.
X

8
Step 6: Edge detection

• To detect the edge of an object

• Gradient operator

9
Masks used for Gradient operator

-1 -2 -1 -1 0 1
0 0 0 -2 0 2
1 2 1 -1 0 1

𝑮𝒙 𝑮𝒚

10
• Laplace operator

0 1 0
1 -4 1
0 1 0

11
Edge Detection
(contd.)
• Light object on dark
background

12
 Boundary
Chain Codes –Descriptors
used to represent the boundary of an
object by a set of straight line segments of specified
length and direction.

4-directional chain code 8-directional chain code

13
Example:

Chain code: 11030010332222

14
 Signatur
• e representation of a boundary
One dimensional functional

Examples:

15
Note: To identify multiple objects present in an image,
we consider Compactness = (perimeter2/ area)

16
Topic 8: Robot Motion Planning

PROF. (DR.) DILIP KUMAR PRATIHAR

MECHANICAL ENGINEERING DEPARTMENT, IIT KHARAGPUR

17
Aim

To determine the course of action/path while moving

from an initial position to a final position.

18
 Robot Motion
Planning

Gross motion planning / Fine motion planning /

Free space motion Compliant motion
planning planning
Manipulati Navigation
on

19
20
Sequence of Robotic Action

Task Motion
Kinematics
identification Planning

Trajectory
planning

Control
Motor action Dynamics
scheme

21
 Structured
environment
Environment
Un-structured
environment

22
 Motion Planning Approaches

Global Approach/ Act-After- Local Approach/ Act-

Thinking process/ Off-line While-Thinking
planning (motion planning process/ On-line
with complete information) planning (motion
planning with
incomplete
information)

23
 Motion Planning Schemes

Traditional schemes/ Algorithmic Approaches Non-Traditional schemes

(using soft computing)
(i) Fuzzy logic – based
(ii) Neural networks –
Graph-based methods Analytical Approaches based approaches
(i) Visibility graph (i) Potential Field Approach
(ii) Voronoi diagram (ii) Path Velocity Decomposition
(iii) Cell decomposition (iii) Incremental Planning
(iv) Tangent graph (iv) Probabilistic Approach
(v) Accessibility graph (v) Relative Velocity Approach
(vi) Reactive Control Strategies
(Behavior-Based Robotics)

24
 Visibility Graph (Nilsson 1969)
 It connects those vertices of obstacles, which are
visible from one another.

25
 Voronoi Diagram (Dunlaing et al., 1986)
 Represents the locus of points those are equidistant
from at least two of the boundaries (obstacle).

26
Cell Decomposition (Lozano Perez, 1983)
Configuration space (C-space)

27
 Cell Decomposition (contd.)
 Robot’s free area is divided into a number of small
regions called cells. A connectivity graph is then
constructed and searched.

28
 Tangent Graph (Liu & Arimoto 1991)

 Tangents are drawn from the starting point to the

visible obstacle and then from one obstacle to
another
 A path comprises of tangents and circular arcs
 Complexity: O (N2), where N is the number of control
points

29
 G

O3

O2

O1
S

30
 Approaches to Solve Moving Obstacle
Problems
Path Velocity Decomposition (Kant and
Zucker, 1984)

This problem is decomposed into two sub-problems as

follows:
(i) Path planning problem (PPP) – to plan a path to
avoid collision with static obstacles
(ii) Velocity planning problem (VPP) – to plan the
velocity of the robot along the above planned path
to avoid collision with moving obstacles
31
Drawbacks

 The path may not be always good, particularly

when there are many obstacles

 As there is a sudden change of velocity of the

robot, it will have jerky motion, which is not
desirable.

32
 Accessibility Graph (Fujimura and samet,
1988)

 Generalization of the visibility graph

 At a particular instant of time, motion planning

problem in dynamic environment is converted into
find-path problem, which is solved using visibility
graph
 In dynamic environment, visibility graph will go on
changing.

33
Incremental Planning Scheme (Slack & Miller,
1987)
Plan a collision – free path based
on predicted position of
obstacles
Follow the path until it becomes
invalid (validity is checked based
on the data collected using
sensor(s) / camera(s)

Adjust the predictions & plan a

new collision – free path

34
Follow the path until it becomes
invalid

Continue until the robot

reaches its destination

35
Relative Velocity Scheme

 Consider relative velocity of the robot with respect

to obstacles

 Dynamic motion planning problem is converted into

several static problems

36
 Several static problems are then converted into a
single problem by means of a vector transformation

 Set of velocity vectors are then computed, so that

the robot avoids collision with all the moving
obstacles

37
Potential Field Approach (Khatib, 1986)

38
 Speed of the robot α Fres

 Direction of movement of the robot is along the

direction of resultant force

39
Attractive Potential
1 2
U att ( R)   d goal ( R), if parabolic
2
 d goal ( R ), if conic-well

R
dgoal (R)

40
Repulsive Potential

U rep ( R) 0

41
 1 1 1 2
  (  ) , if P(R)<Po
U rep ( R )  2 P( R) Po
0, if P(R)  P
 o

42
Drawbacks
 Solution depends on the chosen potential function
 Chance of local minima problem – when the
attractive force is balanced by the repulsive force

43
 When the robot travels in a narrow corridor, it
experiences repulsive forces simultaneously
from the opposite sides, and consequently the
motion becomes unstable

 Unable to find a path among closely spaced

obstacles

44
Reactive Control Strategy (Brooks, 1986)
 Robotic action is decomposed into some
independent primitive behaviours like move-to-
goal, avoid-obstacle, etc.
 Basic behaviours are controlled at different
layers of control architecture
 Basic behaviours are coordinated by a central
mechanism (Behaviour-Based Robotics)

45
Drawbacks
 The behaviours are hard-wired, thus it is unable to
handle behaviours which the programmer did not
foresee beforehand

 The number of layers increases with the complexity

of the problem. It requires a large amount of
computer memory

46
Computational Complexity

 Canny and Reif (1987) –

Motion planning for a point robot among moving
obstacles in 2D plane with bounded velocity is
NP-hard.

47
 Reif and Sharir (1985) –

a) Motion planning among moving obstacles in

3-D space without velocity bound is NP-hard

b) Motion planning among moving obstacles in

3-D space with velocity bound is PSPACE-hard

48
Drawbacks of the Traditional Methods of Motion
Planning

 Traditional methods are computationally

expensive even for a simple problem
 No versatile algorithm, which is applicable to all
the problems
 As most of the algorithms do not have an
optimization module, the generated path may
not be optimal in any sense.

49
So, there is still a need for the development of an
efficient, versatile and computationally tractable
algorithm for solving the motion planning problems
of robots.

50