Chapter 11 Arc Extraction and Segmentation

11.1 Introduction

edge detection: labels each pixel as edge or no edge

additional properties of edge: direction, gradient magnitude, contrast

edge grouping: edge pixels in same region boundary grouped together

edge detector: typically produces short linear disjointed edge segments

each edge segment: has an orientation and a position

edge segments: of little use until aggregated into extended edges

global edge aggregation: upon proximity, relative orientation, contrast, ...

local edge aggregation: extends edges by seeking compatible neighbor edges

global methods: can incorporate domain knowledge into cost functions

global methods: more robust to noisy edge data

global methods: bought at expense of relatively high computational cost

aggregation into extended edges and parametric description: new research area

extended edges: like other curves, can be described at multiple scales

Fig. 3.18(a) 1#1 image of an industrial part

Fig. 3.18(b) edges of (a), large dot: edge center, medium dot: edge extension

Fig. 3.18(c) thinning of (b) leads to the minimally connected graph

Fig. 3.18(d) simple contour following based on orientation compatibility

Fig. 3.18(e) polygonal approximation with vertices highlighted

Fig. 3.18(f) tangent versus arc-length plot

Fig. 3.18(g) same as (d), except letters indicating initial knots

Fig. 3.18(h) fitted straight lines and conics and final set of knots

=====Nalwa, *A Guided Tour of Computer Vision*, Fig. 3.18=====

11.2 Extracting Boundary Pixels from a Segmented Image

after segmentation/connected components: region boundary may be extracted

border algorithm: to extract all region boundaries in left-right, top-bottom

11.2.1 Concepts and Data Structures

input image: symbolic image whose pixel values denote region labels

current regions: borders partially scanned but not yet output

past regions: completely scanned and their borders output

future regions: not yet been reached by the scan

at most
2#2 region labels may be active at a time

hash table: used to allow rapid access to chains of a region

each chain: linked list of pixel positions grow-able from beginning to end

11.2.2 Border-Tracking Algorithm

symbolic image and its output from the border procedure

=====Fig. 11.1=====

11.3 Linking One-Pixel-Wide Edges or Lines

segments: may consist of line, endpoint, corner, junctions

symbolic edge image containing junction (3,3) and potential corner (5,3)

=====Fig. 11.2=====

algorithm to track segments like these has to be concerned with

- starting a new segment
- adding an interior pixel to a segment
- ending a segment
- finding a junction
- finding a corner

pixeltype: isolated, starting, interior, ending, junction, corner

output of the edge-track procedure on the image of Fig. 11.2

=====Fig. 11.3=====

11.4 Edge and Line Linking Using Directional Information

edge linking: labeled pixels with similar enough directions form chains

edge linking: chains identified as arc segment with good fit to curvelike line

=====Garfield 17:11=====

11.5 Segmentation of Arcs into Simple Segments

extracted digital arc: sequence of row-column pairs 4-neighbor or 8-neighbor

arc segmentation: partitions extracted digital arc to fit straight/curved line

endpoints of subsequences: corner points or dominant points

basis for partitioning process: identification of all locations with

- sufficiently high curvature (high change in tangent angle to length)
- enclosed by subsequences fitting different straight lines or curves

techniques: from iterative endpoint fitting, splitting to using tangent angle

deflection, prominence, or high curvature as basis of segmentation

11.5.1 Iterative Endpoint Fit and Split

one distance threshold 3#3

pixel with farthest distance to line 4#4 is 5#5 and distance 6#6 then split

=====Fig. 11.4=====

11.5.2 Tangential Angle Deflection

another approach: identify locations where two line segments meet

exterior angle between two line segments: change in angular orientation

=====Fig. 11.5=====

caution: spatial quantization at small distances can completely mask direction

11.5.3 Uniform Bounded-Error Approximation

segment arc sequence into maximal pieces whose points deviate 7#7 given amount

optimal algorithms: excessive computational complexity

caption of Fig. 11.6 explains Tomek's segmentation technique

=====Fig. 11.6=====

11.5.4 Breakpoint Optimization

after initial segmentation: shift breakpoints to produce better segmentation

first: shift odd final point i.e. even beginning point

then: shift even final point i.e. odd beginning point

11.5.5 Split and Merge

first: split arc into segments with error sufficiently small

then: merge successive segments if resulting segment sufficiently small error

third: try to adjust breakpoints to obtain better segmentation

repeat: until all three steps produce no further change

11.5.6 Isodata Segmentation

iterative isodata line-fit clustering procedure: determines line-fit parameter

then: each point assigned to cluster whose line fit closest to the point

11.5.7 Curvature

geometry of circular arc segment defined by 8#8 and
9#9

=====Fig. 11.7=====

10#10: curve represented parametrically, 11#11

12#12: arc length going from 13#13 to 10#10

14#14

15#15

: unit length tangent vector at 10#10 measured clockwise from column axis

16#16

67#67: unit normal vector at 10#10

17#17

For a planar curve, the curvature at a point on the curve is the limit, as arc length change goes to zero, of the change in tangent angle divided by the change in arc length.

18#18: curvature defined at point of arc length 32#32 along curve

19#19: change of arc length

20#20: change in tangent angle

21#21

natural curve breaks: curvature maxima and minima

curvature passes through zero: local shape changes from convex to concave

surface elliptic: when limb in line drawing is convex

surface hyperbolic: when its limb is concave

surface parabolic: wherever curvature of limb zero

cusp singularities of projection: occur only within hyperbolic surface

=====Nalwa,

11.6 Hough Transform

Hough transform: method for detecting straight lines and curves on images

Hough transform: template matching

11.6.1 Hough Transform Technique

The Hough transform algorithm requires an accumulator array whose dimension
corresponds to the number of unknown parameters in the equation of the family
of curves being sought.

Finding Straight-Line Segments

22#22: for straight lines does not work for vertical lines

23#23: slope, 23#23: intercept

24#24: where row (31#31) and column (48#48) used

25#25: perpendicular distance from the line to the origin

118#118: the angle the perpendicular makes with the 26#26-axis

=====Fig. 11.8=====

use
27#27 and
28#28 to determine
if point falls into cell

an accumulator array quantized in this fashion

=====Fig. 11.9=====

Fig. 7.18(a) image with five labeled points

Fig. 7.18(b) each point mapped onto 29#29 plane as a curved line

Fig. 7.18(c) A: intersection of points 1,3,5; B: intersection of points 2,3,4

Fig. 7.18(d)
30#30 since 31#31 change sign at
32#32

=====Gonzalez and Woods, *Digital Image Processing*, Fig. 7.18=====

Fig. 7.19(a) infrared image containing two hangars and a runway

Fig. 7.19(b) thresholded gradient image using Sobel operators

Fig. 7.19(c) linear Hough transform of (b)

Fig. 7.19(d) three accumulator cells with highest count, no gaps 33#33 pixels

=====Gonzalez and Woods, *Digital Image Processing*, Fig. 7.19=====

Finding Circles

31#31: row

48#48: column

34#34: row-coordinate of the center

35#35: column-coordinate of the center

25#25: radius

36#36: implicit equation for a circle

circles represented by equations:

37#37

38#38

direction of the gradient at the boundary points of a circle

inward pointing gradients will accumulate evidence for the circle center

=====Fig. 11.11=====

Extensions

generalized Hough transform: to arbitrary shapes specified by boundary points

Variations

Burns line finder: to find straight lines in complex images of outdoor scenes

Burns line finder: uses Hough transform and connected components algorithm

11.6.2 A Bayesian Approach to the Hough Transform

39#39: some fixed number related to function of resolution cell size

set of pixels potentially participating in line
40#40:

41#41

=====joke=====

11.7 Line Fitting

procedure for least-squares fitting of line to observed noisy values

8#8: unknown values before noise perturbation

42#42: noisy observed values

43#43: line where points 8#8 lie

model for
42#42:

44#44

45#45

46#46: independent and identically distributed with mean 0 and variance 6#6

47#47

48#48

49#49

50#50

51#51

11.7.1 Variance of the Fitted Parameters

randomness of observed data points in noise: leads to parameter randomness

11.7.2 Principal-Axis Curve Fit

principal-axis curve fit: generalization of line-fitting idea

11.8 Region-of-Support Determination

region of support too large: fine features smoothed out

region of support too small: many corner points or dominant points produced

11.9 Robust Line Fitting

robust line fitting: fit insensitive to a few outlier points

least-squares formulation first, then modify it to make it robust

11.10 Least-Squares Curve Fitting

different approaches and solving methods as follows

11.10.1 Gradient Descent

11.10.2 Newton Method

11.10.3 Second-Order Approximation to Curve Fitting

oblique view of a torus exhibiting folds, cusps, and T-junctions

folds, cusps, and T-junctions: canonical singularities of surface projections

=====Nalwa, *A Guided Tour of Computer Vision*, Fig. 4.15=====

11.10.4 Fitting to a Circle

31#31: row

48#48: column

52#52: center of circle

53#53: radius

circle represented by:

54#54

11.10.5 Variance of the Fitted Parameters

11.10.6 Fitting to a Conic

conic sections: by intersecting a cone with a plane

conic sections: can be circle, ellipse, parabola, hyperbola

=====Jain, *Machine Vision,* Fig. 6.8=====

31#31: row

48#48: column

55#55: coefficients

conic represented by:

56#56

11.10.7 Fitting to an Ellipse

the most common conic fitting: fit to an ellipse

11.10.8 Bayesian Fitting

equal-weight least-squares fit: suitable when all observed points noisy

Bayesian fitting: some observed data points not noisy

11.10.9 Uniform Error Estimation

uniform error estimation appropriate: if all points in observed arc reliable

edge detection purpose: encode and describe information in economical form

=====Nalwa, *A Guided Tour of Computer Vision*, Fig. 3.1=====

=====joke=====

2001-09-19 Counter:

FastCounter by bCentral