From MATLAB® and Simulink® to

Real Time with TI DSPs

Detecting Shapes in Images using

the Hough Transform

Content developed in partnership with

Tel-Aviv University

© 2007 Texas Instruments Inc,

0-1
Outline

• Detecting Straight Lines

• Detecting Straight Lanes

© 2007 Texas Instruments Inc, Slide 2

The Straight Line

(x1,y1)

(x2,y2)
y  m x b

• For each point (x,y) in the line the following equation applies:
y  m x b
• Therefore:
y1  m  x1  b
© 2007 Texas Instruments Inc,
y 2  m  x2  b
Slide 3
Multiple Lines over a single point

y=m2x+b2

y=m1x+b1

(x,y) y=m4x+b4

y=m3x+b3

• Each pair (m,b) defines a distinct straight line containing

the point (x,y)

© 2007 Texas Instruments Inc, Slide 4

The Parameter Plane

b =-mx1+y1
(x1,y1)

(x2,y2)
(x3,y3)

b =-mx3+y3
b =-mx2+y2
• Each point in the (x,y) space(image plane) is mapped to a
straight line in the (m.b) space (parameter plane).

• A straight line in the (x,y) space (image plane) is mapped to the

intersection point of the lines corresponding to its points, in the
(m.b) space (parameter plane).
© 2007 Texas Instruments Inc, Slide 5
Dealing with digital
pictures
Image Plane Parameter Plane
ls N lines
N pixe

M lines
M
pi
xe
ls

• A line formed by M (N) pixels in the image space will be mapped to the
intersection point of M (N) lines in the parameters space, where each
line corresponds to a pixel in the image space.

• The number of lines intersecting in a single point in the parameter

space represents the length of the original line in the image space.
© 2007 Texas Instruments Inc, Slide 6
 The Accumulator Concept
b • The (m.b) space (parameter
bmax plane) is subdivided in cells.

• Each pixel (x,y) in the original

image vote in the (m,b) space
for each line passing through
it.

b1 N
• The votes are summed in an
Accumulator

Corresponds to a straight line

y=m1x+b1
of N pixels length

bmin
mmin m1
© 2007 Texas Instruments Inc,
mmax m Slide 7
Using Polar Coordinates
• For each point (x,y) in the
r  x cos   y sin 
line the following equation
applies:
r  x cos   y sin 
(x1,y1) • In particular:

r  x1 cos   y1 sin 
(x2,y2)
r r  x2 cos   y2 sin 

© 2007 Texas Instruments Inc, Slide 8

The Motivation for Polar Coordinates

Vertical lines cannot be mapped to the

(m,b) space, since:
m
b?
Vertical lines can be described using
polar coordinates : x=r

x  r cos 0  r sin 0
xr

© 2007 Texas Instruments Inc, Slide 9

Hough Transform - The (r,θ) Space

r=x2cosθ+y2sinθ
r=x4cosθ+y4sinθ

(x1,y1)
r=x1cosθ+y1sinθ
(x3,y3)
(x2,y2)
(x4,y4)

r=x3cosθ+y3sinθ

• Hough Transform - Each point in the (x,y) space is mapped to a sinusoid in

the (r,θ) space.

• Sinusoids corresponding to collinear points in the (x,y) space intersect at

a common point in the (r,θ) space.

© 2007 Texas Instruments Inc, Slide 10

 Accumulators in the (r,θ) Plane

θ
θmax

Corresponds to the straight line

r1=xcosθ1+xsinθ1
of N pixels length

θ1 N

θmin
rmin r1
© 2007 Texas Instruments Inc,
rmax r Slide 11
The Region of Interest (ROI)

ymax r max

ymin
xmin xmax

• The ROI is the area in the original image, where lines need to be
detected. The ROI for the picture above is:

xmin  x  xmax   0  r  rmax

  rmax   xmax  xmin    ymax  ymin 
2 2

ymin  y  ymax  0    360
© 2007 Texas Instruments Inc, Slide 12
Longest Line Detection

Hough Algorithm
Input
Image
Edge
Detection
Hough
Transfom
Find
Max.
Draw Line
+ Output
Image

Binary
Image

The line is reconstructed using

the equation:
Accumulator Longest rm=xcosθm+ysinθm
Array Line
(rm,θm)
(Calculated for the values of
(x,y) that “voted” for the
accumulator cell (rm, θm).

© 2007 Texas Instruments Inc, Slide 13

Line Detection Model

© 2007 Texas Instruments Inc, Slide 14

The Hough Algorithm

© 2007 Texas Instruments Inc, Slide 15

Line Drawing & Image Construction

© 2007 Texas Instruments Inc, Slide 16

Line Detection - Hands-On

• Simulation

• Implementation using the DSK6416

© 2007 Texas Instruments Inc, Slide 17

Simulation

MATLAB® Display

Image File

Line
Detection

© 2007 Texas Instruments Inc, Slide 18

Real Time Implementation

MATLAB
Display
Image
Script
File
RGB
to
Grayscale

RTDX RTDX

Line
Detection
DSK6416
© 2007 Texas Instruments Inc, Slide 19
From Line to Lane

1. Find two longest lines in the

picture

2. Draw Polygon

© 2007 Texas Instruments Inc, Slide 20

Lane Detection
Hough Algorithm
Enhanced
Input
Image
Determine
ROI
Edge
Detection
Hough
Transfom
Find
2 Max.
(r,θ)
Correction
Draw
Lane + Output
Image

Binary
Image Two Longest Lines
Accumulator (rm,θm) / (rn,θn)
Array

Two lines are reconstructed using the

equation:
rm=xcosθm+ysinθm
(Calculated for the values of (x,y) that
“voted” for the two maximum values in
the accumulator cell.
A polygon is constructed connecting
those lines

© 2007 Texas Instruments Inc, Slide 21

Enhanced Edge Detection
An histogram-based thresholding edge detection method enables the identification of
areas where pixels change from light to dark or dark to light, which might indicate
lane edges.

Edge
Detection

Logical Binary
ROI
AND Image

≥
Histogram Based
Threshold

© 2007 Texas Instruments Inc, Slide 22

Why Enhanced Edge Detection?

Edge Detection Only

Edge Detection with Histogram Based Thresholding

© 2007 Texas Instruments Inc, Slide 23

The Need for (r,θ) Correction

No Correction Misdetection of the

longest lines

(r,θ) Correction

© 2007 Texas Instruments Inc, Slide 24

(r,θ) Correction
• If the lane position given by the Hough Transform block
changes abruptly with respect to its values in the previous
frame, the Rho Theta Correction subsystem discards the
current position and keeps the previous position. Maximum
allowable variation in E and F with respect to previous values
are:

rcurrent  rprevious  30 pixels

or
 current   previous  10 degrees

© 2007 Texas Instruments Inc, Slide 25

Lane Detection Model

© 2007 Texas Instruments Inc, Slide 26

Enhanced Edge Detection

© 2007 Texas Instruments Inc, Slide 27

The Hough Algorithm

© 2007 Texas Instruments Inc, Slide 28

Lane Drawing

© 2007 Texas Instruments Inc, Slide 29

Lane Detection - Hands-On

• Simulation

• Implementation using the DM6437 DVDP

© 2007 Texas Instruments Inc, Slide 30