Chapter 2 Binary Machine Vision:

Thresholding and Segmentation

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=====

Project due Oct. 16:

Write a program to generate

a. a binary image (threshold at 128)

b. a histogram

c. connected components (regions with + at centroid, bounding box)

2001-09-19 Counter:

FastCounter by bCentral