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

segments: lists of edge points representing straight or curved lines
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

simple arc segment: straight-line or curved-arc segment
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, A Guided Tour of Computer Vision, Fig. 4.14=====




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