Chapter 2 Binary Machine Vision:
Thresholding and Segmentation

2.1 Introduction
binary value 1: considered part of object
binary value 0: background pixel
binary machine vision: generation and analysis of binary image

2.2 Thresholding
if
if
: row, : column
: grayscale intensity, : binary intensity
: intensity threshold
original gray scale image: no numbers means value 0
=====Fig. 2.1=====
thresholded gray scale image: threshold 0
=====Fig. 2.2=====
=====lena.bin.128=====

histogram
spans each gray level value e.g.
: operator counts the number of elements in a set
image of a metal part
=====Fig. 2.3=====
histogram of the image of Fig. 2.3: two dominant modes
=====Fig. 2.4=====
metal-part image thresholded at gray level 148
=====Fig. 2.5=====
=====lena.histogram=====
BNC T-connector against a dark background
=====Fig. 2.6=====
histogram of the BNC T-connector image
=====Fig. 2.7=====
image of the BNC T-connector thresholded at: 110, 130, 150, 170
=====Fig. 2.8=====

2.2.1 Minimizing Within-Group Variance
: histogram probabilities of gray values

: the spatial domain of the image
within-group variance : weighted sum of group variances

: variance for the group with values
: variance for the group with values
: probability for the group with values
: probability for the group with values

find which minimizes
binary image produced by thresholding T-connector with Otsu threshold
=====Fig. 2.9=====
=====New 3:9=====

2.2.2 Minimizing Kullback Information Distance
minimize the Kullback directed divergence

mixture distribution of the two Gaussians in histogram:

binary image produced by thresholding with Kittler-Illingworth threshold
=====Fig. 2.10=====
T-connector histogram with Otsu (left) and Kittler-Illingworth (right) thr.
=====Fig. 2.11=====
mixture of two Gaussians
=====Fig. 2.12=====

2.3 Connected Components Labeling
Connected components analysis of a binary image consists of the connected components labeling of the binary-1 pixels followed by property measurement of the component regions and decision making.

All pixels that have value binary 1 and are connected to each other by a path of pixels all with value binary 1 are given the same identifying label.
label: unique name or index of the region
label: identifier for a potential object region
connected components labeling: a grouping operation
pixel property: position, gray level or brightness level
region property: shape, bounding box, position, intensity statistics

2.3.1 Connected Components Operators
Two 1-pixels and belong to the same connected component if there is a sequence of 1-pixels of where , and is a neighbor of for
4-connected: north, south, east, west
8-connected: north, south, east, west, northeast,
northwest, southeast, southwest
border: subset of 1-pixels also adjacent to 0-pixels
(a) 4-connected (b) 8-connected
=====Fig. 2.13=====
(a) original image (b) connected components
=====Fig. 2.14=====

Rosenfeld has shown that if is a component of 1s and is an adjacent component of 0s, and if 4-connectedness is used for 1-pixels and 8-connectedness is used for 0-pixels then either surrounds ( is a hole in ) or surrounds ( is a hole in ).
true when 8-connectedness for 1-pixels, 4-connectedness for 0-pixels
common to use one type of connectedness for 1-pixels and other for 0-pixels
phenomenon associated with using 4- and 8-adjacency
=====Fig. 2.15=====

2.3.2 Connected Components Algorithms
All the algorithms process a row of the image at a time
All the algorithms assign new labels to the first pixel of each component
attempt to propagate the label of a pixel to right or below neighbors
This process continues until the pixel marked in row 4 encountered
propagation process
=====Fig. 2.16=====
The differences among the algorithms of three types:
1. What label should be assigned to pixel ?
2. How to keep track of the equivalence of two (or more) labels?
3. How to use the equivalence information to complete processing?

2.3.3 An Iterative Algorithm
1. Initialization of each 1-pixel to a unique label
2. Iteration of top-down followed by bottom-up passes until no change
iterative algorithm for connected components labeling
=====Fig. 2.17=====
=====Oldie 34:13=====

2.3.4 The Classical Algorithm
makes two passes but requires a large global table for equivalences
1. performs label propagation as above
2. when two different labels propagate to the same pixel,
the smaller label propagates and equivalence entered into table
3. equivalence classes are found by transitive closure
4. second pass performs a translation
classical connected components labeling algorithm
=====Fig. 2.18 (a)=====Fig. 2.18(b)=====
main problem: global equivalence table may be too large for memory

2.3.5 A Space-Efficient Two-Pass Algorithm That Uses a Local Equivalence Table
small table stores only equivalences from current and preceding lines
maximum number of equivalences = image width
relabel each line with equivalence labels when equivalence detected
results after the top-down pass of local table method
=====Fig. 2.19=====

2.3.6 An Efficient Run-Length Implementation of the Local Table Method
run-length encoding: transmits lengths of runs of zeros and ones

(a) binary image (b), (c) run-length encoding
=====Fig. 2.20=====
data structures used for keeping track of equivalence classes
=====Fig. 2.21=====
diagram showing the bottom-up pass (8-connected)
=====Fig. 2.22=====

2.4 Signature Segmentation and Analysis
signature: histogram of the nonzero pixels of the resulting masked image
signature: a projection
projections can be vertical, horizontal, diagonal, circular, radial ...
=====Fig. 2.23: diagonal projection=====

vertical projection of a segment: column between
horizontal projection: row between
vertical and horizontal projection define a rectangle :

horizontal and vertical projection
=====Fig. 2.25=====
binary image segmented into regions based on initial projections
=====Fig. 2.27=====
binary image further segmented
=====Fig. 2.28=====
1. segment the vertical and horizontal projections
2. treat each rectangular subimage as the image
=====check=====

Diagonal projections:
: from upper left to lower right
: from upper right to lower left
diagonal projections and
=====Fig. 2.29=====
object area: sum of all the projection values in the segment

2.5 Summary
when components spaced away and relatively few, use signature segmentation
=====joke=====

2001-09-19
Counter:

FastCounter by bCentral