Digital Image Processing
Lecture # 6
Hough Transform - Image Segmentation
1
2
3
4
7
8
9
13
Hough Transform
Implementation steps:
• Initially the accumulator cells are set to zero.
• Then for every point (xk,yk) in the image, a is varied over the
allowed subdivision values and the corresponding b values are
calculated using b = -xka + yk.
• The resulting b are then rounded off to the allowed values of b.
• If a value of ap results in solution bq, we let the corresponding
accumulator value A(p,q) = A(p,q) +1.
• In the end the value of Q in A(i,j) corresponds to Q points on the
line y = -aix + bj.
Note: The number of subdivisions in the ab plane determines the
accuracy of the colinearity of these points.
14
Hough Transform Implementation -3 -2 -1 0 1 2 3 -3 -2 -1 0 1 2 3
1 0 0 0 0 0 0 -3 0 0 0 0 0 0 0 -3 0 0 0 1 0 0 0
0 1 0 0 0 0 0 -2 0 0 0 0 0 0 0 -2 0 0 0 1 0 0 0
0 0 1 0 0 0 0 -1 0 0 0 0 0 0 0 -1 0 0 0 1 0 0 0
0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
1 1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
2 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
3 3
-3 -2 -1 0 1 2 3 -3 -2 -1 0 1 2 3 -3 -2 -1 0 1 2 3
-3 0 0 0 1 0 0 0 -3 0 0 0 1 0 0 0 -3 0 0 0 1 0 0 0
-2 0 0 0 1 0 0 1 -2 0 0 0 1 0 0 1 -2 0 0 0 1 0 0 1
-1 0 0 0 1 0 1 0 -1 0 0 0 1 0 1 0 -1 0 0 0 1 0 1 0
0 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 …. 0 0 0 0 1 1 1 2
0 0 0 2 0 0 0 0 0 0 3 0 0 0 0 0 1 5 0 0 0
1 1 1
0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 0 0 0
2 2 2
0 1 0 1 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 0
3 3 3
Parameters a and b can take values between –infinity to +infinity 15
Hough Transform
• Limitation in using yi = a xi + b, as the representation of
straight line is that slope approaches to infinity as the line
approaches to be vertical.
• Therefore usually Hough Transform is implemented using the
polar equation of straight line, i.e. x c o s q y s in q r
and instead of ab-plane rq-plane is used.
• Every point in image gives a sinusoidal curve in the rq-plane.
17
See Example on You Tube:
https://www.youtube.com/watch?v=4zHbI-fFIlI
Hough Transform
19
Hough Transform
Implementation of the Hough transform
• Construct an array representing q, r
• For each point, render the curve (q, r) into this array, adding one
at each cell
• Difficulties
– how big should the cells be? (too big, and we cannot
distinguish between quite different lines; too small, and noise
causes lines to be missed)
• How many lines?
– count the peaks in the Hough array
• This method can be extended to other type of curves also by
using the equation for the desired curve, e.g. circle:
( x c1 ) ( y c 2 ) c
2 2 2
3
22
Image Segmentation
Image Segmentation
Group similar components (such as, pixels in an
image, image frames in a video)
Applications: Finding tumors, veins, etc. in medical
images, finding targets in satellite/aerial images,
finding people in surveillance images, summarizing
video, etc.
12/7/2020 Image Segmentation 24
Image Segmentation
Segmentation algorithms are based on one of two basic
properties of gray-scale values:
Discontinuity
Partition an image based on abrupt changes in gray-scale levels.
Detection of isolated points, lines, and edges in an image.
Similarity
Thresholding, region growing, and region splitting/merging.
12/7/2020 Image Segmentation 25
Thresholding
Segmentation into two classes/groups
Foreground (Objects)
Background
12/7/2020 Image Segmentation 26
Thresholding
1 if f ( x, y ) T
g ( x, y )
0 if f ( x, y ) T
Objects & Background
Global Thresholding
Local/Adaptive Thresholding
12/7/2020 Image Segmentation 27
Global Thresholding
Single threshold value for entire image
Fixed ?
Automatic
Intensity histogram
12/7/2020 Image Segmentation 28
Global Thresholding
Single threshold value for entire image
Fixed ?
Automatic
Intensity histogram
12/7/2020 Image Segmentation 29
Global Thresholding
Estimate an initial T
Segment Image using T: Two groups of pixels G1 and G2
Compute average gray values m1 and m2 of two groups
Compute new threshold value T=1/2(m1+m2)
Repeat steps 2 to 4 until: abs(Ti – Ti-1)<epsilon
12/7/2020 Image Segmentation 30
Global Thresholding
Multilevel thresholding
12/7/2020 Image Segmentation 32
Thresholding
Non-uniform illumination:
12/7/2020 Image Segmentation 33
Global Thresholding
12/7/2020 Image Segmentation 34
Adaptive Thresholding
12/7/2020 Image Segmentation 35
Adaptive Thresholding
Threshold: function of neighboring pixels
T mean
T median
max min
T
2
12/7/2020 Image Segmentation 36
Adaptive Thresholding
Original Image Global Thresholding
12/7/2020 Image Segmentation 37
Adaptive Thresholding
T=mean, neighborhood=7x7 T=mean-Const., neighborhood=7x7
12/7/2020 Image Segmentation 38
Adaptive Thresholding
Niblack Algorithm
T mks
m mean
s standard deviations
k Niblack constant
Neighborhood size???
12/7/2020 Image Segmentation 39
Document Binarization
• Local Thresholding – Examples
Original Niblack Sauvola
Wolf Feng NICK
40
Region-Based Segmentation
Divide the image into regions
R1,R2,…,RN
Following properties must hold:
(For adjacent regions)
12/7/2020 Image Segmentation 44
Region-Based Segmentation
Region Growing
Region growing: groups pixels or subregions into larger
regions.
Pixel aggregation: starts with a set of “seed” points and from
these grows regions by appending to each seed points those
neighboring pixels that have similar properties (such as gray
level).
1. Choose the seed pixel(s).
2. Check the neighboring pixels and add them to the region if they are
similar to the seed
3. Repeat step 2 for each of the newly added pixels; stop if no more
pixels can be added
Predicate: for example abs(zj - seed) < Epsilon
12/7/2020 Image Segmentation 45
Region-Based Segmentation
Example
12/7/2020 Image Segmentation 46
Region-Based Segmentation
Region Splitting
Region Growing: Starts from a set of seed points.
Region Splitting: Starts with the whole image as a single
region and subdivide the regions that do not satisfy a
condition.
Image = One Region R
Select a predicate P (gray values etc.)
Successively divide each region into smaller and smaller
quadrant regions so that:
P( Ri ) true
12/7/2020 Image Segmentation 47
Region-Based Segmentation
Region Splitting
Problem? Adjacent regions could be same
Solution? Allow Merge
12/7/2020 Image Segmentation 48
Region-Based Segmentation
Region Merging
Region merging is the opposite of region splitting.
Merge adjacent regions Ri and Rj for which:
P( Ri R j ) True
Region Splitting/Merging
Stop when no further split or merge is possible
12/7/2020 Image Segmentation 49
Region-Based Segmentation
Example
1. Split into four disjointed quadrants any region Ri where P(Ri)=False
2. Merge any adjacent regions Rj and Rk for which P(Rj U Rk)=True
3. Stop when no further merging or splitting is possible
12/7/2020 Image Segmentation
51
Acknowledgements
Digital Image Processing”, Rafael C. Gonzalez & Richard E. Woods, Addison-Wesley, 2002
Computer Vision for Computer Graphics, Mark Borg
Material in these slides has been taken from, the following resources
Computer Vision A modern Approach by Frosyth
CSCI 1430: Introduction to Computer Vision by James Tompkin
52
