 

 

MSU

LIBRARIES
“

 

 

RETURNING MATERIALS:
Place in book drop to
remove this checkout from
your record. FINES will
be charged if book is
returned after the date
stamped below.

 

 

 

 

 

 

 

RELATIVE SENSITIVITY OF A FAMILY OF
CLOSEST-POINT GRAPHS IN VISION APPLICATIONS

By

Terrence L. C horzempa

A THESIS

Submitted to
Michigan State University
in partial fulﬁllment of the requirements
for the degree of

MASTER OF SCIENCE

Department of Computer Science

1988

ABSTRACT

RELATIVE SENSITIVITY OF A FAMILY OF
CLOSEST-POINT GRAPHS IN VISION APPLICATIONS

By

Terrence L. C horzempa

Detecting structure in images is one of the important tasks performed
early in a vision system. A common technique for structure detection
involves graphs and the neighborhoods they create. The goals of this work
are twofold. One is to measure the sensitivity of the Delaunay Triangula-
tion, the Gabriel Graph, the Relative Neighborhood Graph and the
Minimum Spanning Tree in locating dotted structures embedded in a uni-
formly distributed random dot pattern. The second goal is to measure the

effect of dot position perturbations on each graph’s structure.

Structure detection experiments are performed where linear structures
with varying degrees of spacing, longitudinal and transverse variation are
placed in a noisy background and then detected using the Hough transform.
Global structures detected by the Hough transform are then reﬁned using
the neighborhood information provided by the graphs. Graph performance
is measured by the amount of structure fragmentation resulting from the

interference caused by the background points.

Terrence L. C horzempa

Graph stability experiments are performed where one dot of a uni-
formly distributed random dot pattern is subjected to random direction per-
turbations. Graph performance is measured by the highest order neighbor

whose vertex adjacencies have been effected.

Results indicate that the Delaunay triangulation is the least sensitive to

background interference and dot perturbations.

Acknowledgements

I would like to thank my advisor, Dr. Mihran Tuceryan, for all his
valuable assistance in preparing this thesis.

I also wish to thank my parents, Vincent and Mary, for their unending
support and patience.

iv

Table of Contents

List of Tables ........................................................................................ vii
List of Figures ...................................................................................... viii
Chapter 1 Introduction ......................................................................
1.1 Motivation ........................................................................
1.2 Thesis Problem Statement ................................................ 19
1.3 Thesis Outline .................................................................. 20
Chapter 2 Structure Detection .......................................................... 21
2.1 Background ...................................................................... 21
Chapter 3 Methodology ..................................................................... 24
3.1 Problem to Study .............................................................. 24
3.2 Procedure .......................................................................... 29
3.2.1 Generation of Structure Detection Images .................... 29
3.2.2 Detection of Global Structure ....................................... 33
3.2.3 Localizing the Structure using Graphs .......................... 37
3.2.4 Generation of Graph Stability Images ........................... 37
3.2.5 Identiﬁcation of Altered Neighbors .............................. 38
3.3 Measures of Sensitivity .................................................... 40
3.4 Experiments ...................................................................... 41

Chapter 4 Results and Discussion ..................................................... 45
4.1 Experiment 1 - Spacing (20) ............................................ 45
4.2 Experiment 2 - Spacing, Transverse (20) ......................... 55
4.3 Experiment 3 - Spacing, Longitudinal, Transverse (20).. 59
4.4 Experiment 4 - Spacing, Longitudinal, Transverse (16).. 63

4.5 Experiment 5 - Perturbation (20) ..................................... 67
4.6 Experiment 6 - Perturbation (16) ..................................... 70
Chapter 5 Conclusions ....................................................................... 73
5.1 Summary and Conclusions ............................................... 73
5.2 Future Work ..................................................................... 75
Bibliography ........................................................................................ 77

vi

List of Tables

Table 4-1 Experiment 5, Signiﬁcance of the Average Neighbor Orders ....... 69
Table 4-2 Experiment 6, Signiﬁcance of the Average Neighbor Orders ....... 72

vii

List of Figures

Figure 1-1 A Dotted Line ..................................................................... 3
Figure 1-2 A Dotted Line Surrounded by Noise .................................. 4
Figure 1-3 A Random Dot Pattem ....................................................... 7
Figure 1-4 Voronoi Tessellation for Figure 1-3 ................................... 8
Figure 1-5 Delaunay Triangulation for Figure 1-3 ............................... 9
Figure 1-6 GG Circles of Inﬂuence ...................................................... 11
Figure 1-7 RNG Lunes of Inﬂuence ..................................................... 12
Figure 1-8 Gabriel Graph for Figure 1-3 .............................................. 13
Figure 1-9 Relative Neighborhood Graph for Figure 1-3 .................... 14
Figure 1-10 Minimum Spanning Tree for Figure 1-3 .......................... 16
Figure 3-1 MST of a Dotted Line ......................................................... 26
Figure 3-2 MST of a Dotted Line Surrounded by Noise ...................... 27
Figure 3-3 Spacing, Longitudinal and Transverse Variations .............. 32
Figure 3-4 Hough Parameters of a Line ............................................... 35
Figure 3-5 Points of a Hough Detected Line ........................................ 36
Figure 3-6 First, Second and Third Order DT Neighbors .................... 39
Figure 4-1 Experiment 1, Small Dotted Line Perturbations ................. 48
Figure 4-2 Experiment 1, Average Figure Signiﬁcance Results .......... 49
Figure 4-3 Experiment 1, MST of Small Dotted Line Perturbations 50
Figure 4-4 Experiment 1, DT of Small Dotted Line Perturbations ...... 51
Figure 4-5 Experiment 1, Large Dotted Line Perturbations ................. 52
Figure 4-6 Experiment 1, MST of Large Dotted Line Perturbations 53
Figure 4-7 Experiment 1, DT of Large Dotted Line Perturbations ...... 54
Figure 4-8 Experiment 2, Small Dotted Line Perturbations ................. 56
Figure 4-9 Experiment 2, Average Figure Signiﬁcance Results .......... 57
Figure 4-10 Experiment 2, Large Dotted Line Perturbations ............... 58

viii

Figure 4-11 Experiment 3, Small Dotted Line Perturbations ............... 60

Figure 4-12 Experiment 3, Large Dotted Line Perturbations ............... 61
Figure 4-13 Experiment 3, Average Figure Signiﬁcance Results ........ 62
Figure 4-14 Experiment 4, Average Figure Signiﬁcance Results ........ 64
Figure 4-15 Experiment 4, Small Dotted Line Perturbations ............... 65
Figure 4-16 Experiment 4, Large Dotted Line Perturbations ............... 66
Figure 4-17 Experiment 5, Average Neighbor Order Results .............. 68
Figure 4-18 Experiment 6, Average Neighbor Order Results .............. 71

ix

Chapter 1

Introduction

 

This thesis examines the suitability of a set of related closest-point
graphs in the detection of structure and explores the graph’s structural sta-
bility in random dot patterns. One objective is to determine the portion of
the structure retained by a particular graph when controlled amounts of dis-
tortion are introduced. The second objective is to ascertain the stability of
each graph when an image point is subjected to controlled amounts of per-
turbation. Each one of these graphs has been shown to possess favorable
characteristics as discussed in Chapter Two. In the following section, per-
ceptual grouping is discussed. The remaining sections of Chapter One con-

tain the thesis problem statement and goals followed by the thesis outline.

1.1 Motivation

Structural grouping using graph theoretic techniques is very prevalent
[AHU 82] [FAI 83] [JAR 73] [MAT 80] [TOU SOB] [URQ 82] [ZAH 71].
There are several reasons why this is so. One reason is that there exists a

large body of theoretical knowledge on graphs to draw upon. Speciﬁcally,

2

many efﬁcient graph algorithms [WAR 62] [KRU 56] [PR1 57] can be used
to ease the computational burden of computer vision tasks. Another reason
is that graphs can be used to easily express spatial relationships between
entities in an image; for example, the perception of Gestalt groupings
[KOF 35] [WER 38]. The Gestalt laws of perceptual grouping are used by
a vision system to organize image entities without a priori knowledge of
what is contained in the image. The basis for this low level processing lies
in the fact that regularity in the image plane almost always results from
regularities in the physical world. The primitive structural information
provided by this grouping procedure is used in more complex processes
such as the perception of depth and object recognition. This view of per-
ceptual organization allows an interpretation of vision processes in terms
closely related to the characteristics of human vision. Gestalt rules include
proximity, smoothness, closure and symmetry. The dots in Figure 1-1 are
perceived as a line using the proximity criteria. With the addition of noise
points in Figure 1-2, the line is no longer perceivable. It is the ability to
capture the interactions among the image points by the graph neighbor

relation that is under study in this thesis.

 

 

 

- Figure 1-1 A Dotted Line

 

 

 

.“ .0 ' . 6 0 C O o o
o .0. 'g .0 'g ' o
O 0 a. . . O .
' . . o o. o . . ‘0 . ' ." 3 ' '
'0’ o. o . o " O: 9 .' ' ' .
. ‘ .’ 9. . .0 $3 . o .
o o o
. . Q . O . .. . .... . O .. .g.
I O . .0 . .0 .. . . o . . o I
. . O O O .. .. .
' o, . c . . - 0 .
o ' o .‘. ' : 3' . o o o
. 0 g . . . O O
I o O . . . . I . . . O. .
D. . ... 0 . g . O Q
g. . o. . 0 o o '
O . .. .O . . . . g . ..
' O C . ’
.. .. .‘ .0 o. .. ..I.O:‘ . : ..E . o
' o”. o o o ' 0 O. O . .
o o o
. . . . ‘.. O O . . O . Q ..0 . .
:0 o .. I ' . . ' . . 0' .0 .
O . . .. . ‘ . ..:. . .:.
o . ‘ 0'. I. o
.. o. .0 ' . . . . o .
:0 ° ' a 0' . q- "
’ g C. 0 g 0 . . . . . . . C 0'
O I
: o '0 '0.0.0. o. O o O .
. O . ... . . : . . : ..’ . . :0 :
' . C . C . .. .0. . .0 . . ..... .
.. . . . .: O. O . . .
. .. .. . o g. o o .0 " .‘ o . ’
.0 . . . O I . .0. o
.u . . . .. O . g . O
O. .. . . u .. . Q
’ o o . ' ’ 00 . ." . o ‘ o
. ' . o .. . .0 .' a ' o
.. .... . . .C... . O . . .C‘ . . .
a o F’ .0 o o g 0 .0 '. ' .
! I -‘ . '0 A C. O . O . O . .

 

Figure 1-2 A Dotted Line Surrounded by Noise

 

In this thesis, the data consists of binary images. The black pixels in
the image deﬁne a uniformly distributed random dot pattern. With the
closest-point graphs studied here, every dot of the random dot pattern is a
node (vertex) of a graph and the edges connecting the adjacent nodes are
drawn based on the Euclidean distance separating the nodes. According to
Gestalt rules of organization [KOF 35] [WER 38], one way the human
vision system extracts structure is by grouping objects that are within close
proximity to one another. In this case, the proximity criteria is expressed
by the vertex adjacency relation of a particular graph and a metric on the

edges.

The closest-point graphs under study in this work are the Delaunay
Triangulation (DT), the Gabriel Graph (GG), the Relative Neighborhood
Graph (RNG) and the Minimum Spanning Tree (MST). These graphs were
chosen for evaluation because all have been suggested as valuable tools in
structure identiﬁcation [AHU 82] [TOU 80B] [URQ 82] [ZAH 71]. These
proposals are based on the idea that each graph induces a neighbor relation
on the set of image dots that can be used in applying one or more of the
Gestalt laws of perceptual grouping. Another property of these graphs that

contributed to their selection is that they form the hierarchy given below.
MSTgRNG gGG gDT

This hierarchical relationship is important for two reasons. First, the
hierarchy reﬂects the stringency of the graph neighbor requirements with
the MST being the most stringent and the DT being the least. Secondly,
with only minor modifications to the algorithm for computing the DT, any

one of the other graphs can be easily obtained.

6

As noted earlier, the DT is a superset of all the other graphs, therefore,
the GG, RNG and MST can be easily deﬁned in terms of the DT. First of
all, the DT is the dual of the Voronoi tessellation. Let S be a set of three or
more points in the Euclidean plane. Assume that these points are not all
collinear and that no four points are cocircular. Consider an arbitrary pair
of points P and Q. The bisector of the line joining P and Q is the locus of
points equidistant from both P and Q and divides the plane into two halves.
The half plane Hg (H5) is the locus of points closer to P (Q) than to Q
(P). For any given point P, a set of such half planes is obtained for various

. . . n
chorces of Q. The mtersectron Qes, Qﬂ, Hg deﬁnes a convex polygonal

region consisting of points closer to P than any other point. Such a region
is called the Voronoi polygon [VOR 08] associated with the point P. The
set of complete polygons is called the Voronoi diagram of S [SHA 75]
[AHU 82]. The Voronoi diagram together with the incomplete polygons in
the convex hull deﬁne a Voronoi tessellation of the entire plane. The Voro-
noi tessellation for the points in Figure 1-3 is shown in Figure 1-4. Two
points are Voronoi neighbors if the Voronoi polygons enclosing them share
a common edge. Connecting all pairs of Voronoi neighbors gives the DT.

Figure 1-5 is the DT computed from Figure 1-4.

 

 

 

Figure 1-3 A Random Dot Pattem

 

 

 

 

 

Figure 1-4 Voronoi Tessellation for Figure 1-3

 

 

 

 

Au - L
ﬁn,
(A?

ll

 

 

 

 

 

 

10

The GG can be obtained from the DT by constructing a circle of
inﬂuence for each DT edge. For each circle, the DT edge constitutes the
diameter. Figure 1-6 gives two circles of inﬂuence used in obtaining the
GG for Figure 1-3. If any dot falls within a circle of inﬂuence then the DT
edge is removed, otherwise the DT edge is kept. In Figure 1-6, the large
circle contains point PGG therefore, the dotted DT edge AB deﬁning the
diameter is eliminated from the GG. The dashed DT edge CD deﬁning the
diameter of the small circle in Figure 1-6 is an edge of the GG because no
image point falls within the circle of inﬂuence. To form the RNG, two cir-
cles are drawn for each DT edge with the centers at the endpoints and the
radii deﬁned by the length of the DT edge. The intersection of the two cir-
cles (lune) is the region of inﬂuence for the RNG. Figure 1-7 gives two
lunes used to construct the RNG for Figure 1-3. If a lune contains no dots
then the DT edge is retained, otherwise the DT edge is deleted. In Figure
1-7, the large lune is free of dots so the dashed DT edge GH remains part
of the RNG. With the small lune of Figure 1-7, the point PRNG causes the
dotted DT edge EF to be eliminated from the RNG. The GG and RNG

derived from Figure 1-5 are presented in Figures 1-8 and 1-9 respectively.

 

 

 

 

 

 

 

<
/
l

 

Figure 1-7 RN G Lunes of Inﬂuence. The dotted DT edge EF is deleted from the RNG be-
cause the point Pam; is inside the lune created by the intersection of the two circles centered at E and F
whose radii are deﬁned by ET. The dashed DT edge GH remains part of the RNG because no point ne-
sides in the lune created by the intersection of the two circles centered at G and H with radii speciﬁed by
CH.

14

 

 

V
O

 

 

Figure 1-9 Relative Neighborhood Graph for Figure 1-3

 

15

The MST of a set of dots is formed by joining pairs of dots creating a
tree that spans all dots such that the sum of the edge lengths is the
minimum of all trees spanning the dot set. The MST is used in many ﬁelds
and two classic MST algorithms are given in [KRU 56] and [PR1 57].
Since the MST is a subset of the DT, it can also be computed by only con-
sidering the edges of the DT [PRE 85]. Figure 1-10 is a MST of the dots in
Figure 1-3.

l6

 

 

 

Figure 1-10 Minimum Spanning Tree for Figure 1-3

 

17

The reason for studying the DT, GG, RNG and MST is to assess the
usefulness of each graph’s neighbor relation in detecting structure in the
presence of noise. The structure to be detected is linear and constructed of
dots. This linear structure is embedded in a uniformly distributed random
dot pattern which tests how robust the neighborhood of each graph is.
When a graph is computed for the entire image, the noise points disrupt the
graph edges that would join the dots of the line if no noise were present.
To further test the stability of each graph’s neighborhood deﬁnition, the
dotted line is subjected to various types of perturbations. At some high
level of distortion, none of the four graphs are expected to maintain the

neighbors of the dotted line when surrounded by noise.

The type of dotted structure studied in this thesis is linear. The dotted
line detection ability of each graph is determined by the fraction of the dot-
ted line retained after it is embedded in a noisy background. In the case of
the MST, a noise point in the vicinity of a dot which forms part of the line
to be detected can cause a MST edge joining two dots on the line to disap-
pear. This characteristic tends to make the MST sensitive to noise. With
the less sensitive DT, it is more difﬁcult to break an edge because a node of
the DT has a less restrictive neighborhood deﬁnition than a node of the
MST. In order to capture each graph’s ability to retain the neighbors of the
original structure in the presence of noise, a quantitative measure is
needed. This measure must penalize a graph for allowing a line point to
become isolated by losing neighbors belonging to the line and gaining
neighbors that are considered part of the background. This process causes
segments of the line to disappear. The measure must also allow noise

points to strengthen the structure without any penalty assessed to the graph.

18

This situation arises when a noise dot falls on a graph edge joining two
points of the line. Various combinations of line point perturbations are
used in order to determine when a particular graph may completely break

down and fail to retain the neighbor relations of the structure.

An important aspect of structure detection is how stable the graph
neighbor information is. For instance, if two images of the same scene
differ by small changes in the background then the differences in the
neighbor information given by the graph should be proportional to the
severity of the change. With the more global nature of the MST, it is
expected that a small perturbation in the position of a dot will generate a
disproportionately large change in the MST of the entire image. The DT
vertex however has its neighbors deﬁned as those points whose Voronoi
polygons share an edge, therefore if a vertex is moved slightly then the DT
is expected to change very little when compared to the MST.

In order to evaluate each graph’s structural stability, one dot of a ran-
dom dot pattern is perturbed. The perturbed dot is always the centerrnost
dot of the image. Graph stability is measured by the highest order neighbor
that has its vertex adjacencies modiﬁed. The order of a vertex that is a
neighbor of a point is the minimum number of graph edges that connect the
point and the neighbor. Directions of the perturbations are randomly
selected. It is desirable that the graph’s structure be well behaved for the

neighbor information to be considered stable.

19

A major concern in using geometric methods is the time and space
complexity of their calculation. Fortunately, efﬁcient algorithms exist and
can be easily implemented [GRE 78] [PRE 85] [FRI 57] [URQ 82]. Tous-
saint [TOU 80A] provides a fairly complete survey of available algorithms.

1.2 Thesis Problem Statement
In this thesis, the DT, GG, RNG and MST will be employed to detect

dotted linear structures which have been placed in unifomly distributed
random dot patterns. A quantitative measure will be developed that reﬂects
the degree of the dotted line remaining after the structure has been
detected. The graphs will be ranked according to this quantitative measure.
The emphasis will be on measuring each graph’s behavior when controlled
amounts of perturbation are applied to the structure dots. Only small
amounts of variation will be examined. The types of perturbation are res-
tricted to interdot spacing of the line, longitudinal variation from a dot’s

equally spaced position and transverse variation perpendicular to the line.

This thesis will also subject random dot patterns to perturbations of the
centermost dot to determine the structural sensitivity of the DT, GG, RNG
and MST. The highest order neighbor that has its vertex adjacencies
altered will be recorded. The graphs will be ordered according to this
neighbor order. The emphasis will be on measuring each graph’s behavior
when controlled amounts of distortion are applied to the centermost dot.
Only small amounts of variation will be studied with the direction selected

randomly.

20

1.3 Thesis Outline

Chapter Two reviews geometric applications to pattern recognition.
Chapter Three outlines the methodology of this thesis and the quantitative
measures computed. Chapter Four presents the results along with analyses.
Finally, Chapter Five summarizes the thesis and gives suggestions for

future work.

Chapter 2

Structure Detection

 

Computer vision and structural grouping have a very short history. As
noted by Toussaint [TOU 80A], in the brief existence of pattern recogni-
tion few problems have been attacked using geometric structures despite
their natural applicability. This chapter reviews some of the work already

completed.

2.1 Background

The earliest attempt at deﬁning the rules used in the perception of
structure was reported by Gestalt psychologists [KOF 35] [WER 38].
They observed that the human vision system uses rules such as proximity,
similarity, continuity, 'closure and symmetry in analyzing images. These
criteria are helpful in explaining the perceptions of various images. Unfor-
tunately, the Gestalt laws of perceptual grouping are only explanatory and

do not shed light on the mechanisms that implement these rules.

Work concerning the implementation of the Gestalt laws in computer

vision systems was scarce for a long period of time after the Gestalt laws

21

22

ﬁrst appeared. Zahn’s classic clustering paper [ZAH 71] had a major
impact on the application of Gestalt laws to problems encountered by
vision researchers. Zahn proposed using the MST to embody the principle
of proximity in cluster detection problems and demonstrated that the MST
performed well in clustering arbitrary point sets. In one instance the perfor-
mance of the MST was analyzed in the presence of small amounts of noise
widely and randomly spread over the image. This thesis will explore the

effects of noise on graph behavior more systematically.

Since the appearance of Zahn’s paper, studies using various graphs in
image analysis have become more frequent. Toussaint [TOU 80A] surveys
many geometric structures that have been used in solving a variety of pat-
tern recognition problems. In another paper, Toussaint [TOU 80B] intro-
duces the RNG and espouses its usefulness in extracting perceptually
meaningful structure from a set of points. Both papers presented no perfor-
mance analysis of the geometric structures and offered numerous direc-

tions for future research.

A proposal for applying another type of geometric structure to pattern
recognition problems is given by Ahuja [AHU 82]. Here he argues that the
Voronoi tessellation gives a better deﬁnition of a point’s neighborhood
than methods using parameters that need to be tuned according to the input
point pattern. As in Zahn’s work, Ahuja goes on to deﬁne the Voronoi
tessellation along with its attributes and presents numerous instances where
the Voronoi neighborhood works well. Later, Ahuja’s ideas were expanded
upon in [TUC 86].

Another example of geometric applications to pattern recognition is

presented by Urquhart [URQ 82]. Urquhart gives a general family of

23

graphs deﬁned by using a region of inﬂuence which includes the GG and
RNG. He presents point patterns where these region of inﬂuence graphs do
well in locating clusters. Urquhart does provide some comparative results
of the MST, GG and RNG to show their viability but the analysis is not
extensive.

Numerous other instances of complex pattern recognition problems
addressed by geometric methods can be found. A good survey of results is

given by [TOU 87] accompanied by an extensive bibliography.

Chapter 3

Methodology

 

The objective of this thesis is to determine the relative performance of
the DT, GG, RNG and MST in two areas of computer vision. One concern
is the effect of interdot spacing, longitudinal variation and transverse varia-
tion on each graph’s line detection capability. Also of concern is each
graph’s structural sensitivity to single point perturbations. This chapter
describes the methodology employed and the experiments performed.

Section 3.1 presents the problem under study. Section 3.2 elaborates
on the procedure and Section 3.3 gives the performance measures. Finally,

Section 3.4 speciﬁes the parameters studied in each of the six experiments.

3.1 Problem to Study

As implied earlier, the rationale behind using graphs for structure
detection is based on the neighbor relationship they induce on the image
entities. Figures 1-5, 1-8, 1-9 and 1-10 show how graph edges between
dots are eliminated from the DT to the MST based on the changing neigh-

borhood deﬁnitions. For instance, the MST with its strict constraints on

24

25

node adjacencies (relative to the DT), groups nodes together that are within
close proximity to one another. In a vision setting, image points can be
separated into ﬁgure points and noise points based on their surrounding
environment. Figure 3-1 displays a dotted structure and its MST. In the
absence of background noise all the points of the structure are MST neigh-
bors. Figure 3-2 adds uniformly distributed noise to Figure 3-1. When the
MST of Figure 3-2 is computed, only a small subset of the points of the
original structure are MST neighbors. The presence of noise in Figure 3-2
causes the original MST neighbors of the line in Figure 3-1 to be modiﬁed

resulting in a deterioration of the line into segments.

26

 

 

 

Figure 3-1 MST of a Dotted Line

 

27

 

 

 

Figure 3-2 MST of a Dotted Line Surrounded by Noise

 

28

More speciﬁcally, one problem under consideration is the detrimental
effect that dot perturbations have upon a graph’s ability to maintain the
node adjacencies of a structure in a noisy environment. The structures
under consideration here are simple and consist of dotted lines. Three
types of perturbations are explored: interdot spacing, longitudinal variation
and transverse variation. By varying the spacing of the dots comprising a
structure, the dots once perceived as part of the structure are now con-
sidered part of the background. In the case of interdot spacing, a closely
spaced dotted line is capable of blending into the background as the inter-
dot spacing of the line nears the interdot spacing of the surrounding
environment. For human visual perception, this was shown experimentally
by Vistnes [V18 87]. Figure 1-2 contains a structure whose interdot spac-
ing is larger than the average interdot distance of the background. A meas-
ure is employed to quantify how well a graph resists this structure disap-
pearance by retaining the connections between the dots of the original

structure.

The second problem under consideration is the effect of single dot per-
turbations on the structure of the DT, GG, RNG and MST. The dot pertur-
bations consist of varying the position of the centermost dot in a random
direction and identifying the vertices of the graph that have their vertex
adjacencies altered. The order of the vertex that has its neighbors changed
is used to quantify how stable the graph’s structure is. To be considered
stable, the graph should limit the effect of the change and reﬂect the magni-

tude of the change in a proportional manner.

29

3.2 Procedure

The structure detection procedure employed in this thesis consists of
three stages, (i) image generation with controlled structure variations, (ii)
Hough transformation which detects global structures present in the image,
and (iii) identiﬁcation of local structures by imposing graph adjacency rela-
tionships on the global structures obtained by the Hough transform. The
graph stability procedure consists of two stages, (i) image generation and
(ii) identiﬁcation of the highest order neighbor effected by the image dot
perturbations.

3.2.1 Generation of Structure Detection Images

This step generates a uniformly distributed random dot pattern accord-
ing to an average interdot distance parameter and then randomly places a
dotted line within this uniform background. The dotted line is of random
position and orientation and possesses speciﬁc interdot spacing and varia-
tion characteristics. The background noise dots are generated in the same
manner as in [V18 87] with the number of background noise dots described
by one parameter, an average interdot distance D. A Poisson distribution of
noise dots is approximated by a normal distribution N with the mean equal

to the variance. The mean number of noise dots used for N is computed by

_A_
D2
where A is the area of the image.
The normally distributed random numbers of N used to approximate
the Poisson distribution of the background dots are produced using the
polar coordinate method [BOX 58] [MAR 62]. First, two unifome

30

distributed random numbers between 0 and 1 are converted into two uni-
formly distributed random numbers between -1 and +1. Let U1 and U 2

represent the two uniformly distributed random numbers between -1 and
+1 and set V = [1% + U%. If V 2 1 then the procedure is restarted. Other-

wise, the normally distributed random numbers of N are obtained by

evaluating the expression below.

 

N=U1\/(—21nV)/V

Dot placement within the image is uniform. The x and y coordinates of
each dot are generated by multiplying a unifome distributed random

number between 0 and 1 by the length of an image boundary.

The uniform random number generator used is the lagged Fibonacci
(17,5,-) [GEB 67] generator. The lagged Fibonacci generator is ﬁrst
seeded by 17 uniformly distributed random numbers from a linear
congruential random number generator which is itself seeded by one prime
number. Uniformly distributed random numbers between 0 and 1 are now
produced by X,- =X,-_17 -Xi_5 fori = 18, 19, 20,... .

The dotted line parameters are interdot spacing, longitudinal variation
and transverse variation. Figure 33 deﬁnes these three parameters where S
is the interdot spacing, L is the longitudinal variation and T is the
transverse variation. Note that the range of L is from (—O.5)S to (+0.5)S.
Systematic variation of these parameters allows the study of each graph’s
sensitivity in detecting structure that has not been explored in previous
work. The L and T dot perturbations are determined by two uniformly dis-
tributed random numbers from the lagged Fibonacci generator. The ﬁrst

random number selects the perturbation direction. One direction is

31

designated by numbers between 0.0 and 0.5 inclusive and the other direc-
tion is designated by numbers greater than 0.5. The amount of the perturba-
tion is calculated by multiplying the second random number by the pertur-
bation parameter. In the case of L, the second random number is halved

before the multiplication.

32

 

 

 

 

 

Figure 3-3 Spacing, Longitudinal and Transverse Variations. Dots comprising
the line to be detected are perturbed in three ways. Spacing dictates the interdot distance of the line and
Longitudinal perturbation alters the location of a dot along the line with respect to the dot’s equally
spaced position. Finally, Transverse perturbation moves a dot in a direction perpendicular to the line.

33

3.2.2 Detection of Global Structure

The Hough transformation [HOU 62] has been studied extensively
[BAL 81] [BRO 83] [CA8 87] [DUD 72] [ILL 87] [MAI 86] [SHA 79]
[SKL 78] [VAN 81] and is a well known global technique for detecting
structures in images. In stage two, the Hough transform is used to locate
linear structures in the image. The parameterization proposed by Duda and
Hart [DUD 72] is implemented here to avoid difﬁculties with inﬁnite slope.
Basically, the Hough transform performs a mapping of lines from the
image space to the parameter space. The equation of a line I can be given

as
p=xcos0+ysin0 (1)

where p and 0 are the parameters deﬁning l as shown in Figure 3—4. For a
ﬁxed point (x,y), equation (1) deﬁnes all the lines that pass through the
point and creates a sinusoid in the (p,0) space. So, given the (x,y) coordi-
nate pair of an image dot, 0 is varied from 0 to 360 degrees producing a
series of (p,0) Hough cell coordinates specifying the Hough cells to be
incremented. In essence, the (x,y) coordinate pair votes for a number of
lines, each represented by the (p,0) Hough cell coordinates. After this vot-
ing process is completed for all the image dots, the Hough cell with the
highest count has the (p,0) coordinates that determine the line in the image
space having the largest number of dots. Since the line points can be per-
turbed transversely, a band surrounding the line [MAI 86] is used to deter-
mine the ﬁgure and noise points representing the detected line. Figure 3-5
shows the points of a typical image that fall within such a band around a
detected line. The points of the detected line are then used to decrement

the Hough cells in a manner analogous to incrementing the Hough cells.

34

That is, the (x,y) coordinate pair of every image dot on the detected line is
applied to equation (1) and the (p,0) coordinates of the Hough cells to
decrement are given by varying 0 from 0 to 360 degrees. When the decre-
menting procedure is completed for all the line dots, a new maximum
Hough cell emerges resulting in the next detected line. This process is
repeated until the maximum Hough cell count equals two. Lines made up
of two points need not be considered because any two points constitute a

line. Note that there is no thresholding to eliminate noise lines.

35

 

 

 

 

 

 

 

Figure 3-4 Hough Parameters of a Line. The line i is deﬁned by the equation
p = it cos 0 + y sin 0 with parameters p and 0. The length of the normal from the origin to I having (x,y)
as a point is the radius p. The angle the normal forms with respect to the x axis is 0.

36

 

S o
o
o. o .'
9 o
0 I
o O '
o ’ O
. .'.
. C
I. . '
o. .

     

 

o
' oo
4 o

A

 

I
'1

 

Figure 3-5 POil'ltS Of a Hough Detected Line. After identifying the Hough cell with the

highest count, a band surrounding the line speciﬁed by the (p,6) Hough cell coordinates is used to locate
the image dots belonging to the line.

37

3.2.3 Localizing the Structure using Graphs

The third and ﬁnal stage of the structure detection procedure involves
determining which points of the structure detected by the Hough transform
method are neighbors. This neighbor relation is deﬁned by the four dif-
ferent graphs. Step three shows how the different graph neighbor relations
effect the graph’s structure detection capability. For example, a MST
neighbor is a point that is the closest whereas a DT neighbor has no such

requirement.

For each line detected by the Hough method, a two dimensional neigh-
bor matrix is formed where the rows and columns represent the points of
the line. An entry in the matrix is made if two line points are neighbors of
one of the four graphs computed for the entire random dot pattern. The
reﬂexive, symmetric and transitive closure of this dot neighbor matrix is
then obtained using Warshall’s algorithm [WAR 62]. This computation
produces groups of points that form connected components. The points of
every connected component are now intersected with the points of the ori-
ginal dotted line. The resulting connected components made up of the ori-
ginal line points are ﬁnally compared to the original structure in order to

determine the portion of the line that is retained by each graph.

3.2.4 Generation of Graph Stability Images

Images used for determining each graph’s structural stability are pro-
duced in the same fashion as the images used for determining each graph’s
structure detection ability. The only difference is that no dotted line is
implanted. The dot perturbation parameter speciﬁes the variation amount

that is added to the x and y coordinates of the centermost dot. The direction

38

of the x and y variation is dependent on two unifome distributed random
numbers from the lagged Fibonacci generator. A number between 0.0 and
0.5 inclusive represents a positive direction and a number greater than 0.5
represents a negative direction. Systematically varying the perturbation
amount allows the study of how well each of the graphs respond to the

change.

3.2.5 Identiﬁcation of Altered Neighbors

The last stage of the graph stability procedure involves determining the
highest order neighbor whose vertex adjacencies have changed due to the
movement of the centermost dot. This step shows the graph’s structural

reaction to small changes in the position of image entities.

First, the DT, GG, RNG and MST are computed for the entire image.
After the centermost dot is perturbed, the DT, GG, RNG and MST are then
recomputed using the perturbed image. The original graph and the per-
turbed graph are now compared, edge by edge starting from the centermost
dot, to locate any differences. When a difference is found then the neighbor
order is recorded. The order of a vertex that is a neighbor of the center-
most dot is the minimum number of graph edges that connect the center-
most dot and the neighbor. Figure 3-6 is an example of the ﬁrst, second
and third order DT neighbors of the centermost dot in a unifome distri-

buted random dot pattern.

39

 

 

 

 

 

Figure 3-6 First, Second and Third Order DT Neighbors. The set of points on
curve A are the ﬁrst order DT neighbors of the centermost point P. The points on curve B are the second
order DT neighbors of P and the points on curve C are the third order DT neighbors of P.

40

3.3 Measures of Sensitivity

One measure, a ﬁgure signiﬁcance, is computed to rank each graph’s
relative performance in the linear structure detection task. The ﬁgure
signiﬁcance is the fraction of the structure’s total retained MST length in
the presence of noise compared to the structure’s total MST length in the
absence of noise. Let PL be the set of points of the original line and let PG
be the set of points of a connected graph G. Let G,- for i = l, 2, 3,..., m be
the set of all connected components remaining at the end of the structure
detection procedure. Now deﬁning L(P) as the total length of the MST for
the point set P, the ﬁgure signiﬁcance measure is computed by the follow-
ing equation.

2L(PGinPL)

i=1

 

Fi ure Si ni cance =
g g ﬁ L (PL)

Therefore, a ﬁgure signiﬁcance of 1.00 is the maximum and corresponds to
all points on the structure being neighbors according to a particular graph
neighbor relation. At the other extreme, a ﬁgure signiﬁcance of 0.00 is the
minimum and corresponds to every point of the structure having no graph

neighbors.

The measure used to determine each graph’s relative structural stabil-
ity is the highest order of the neighbors whose adjacencies have changed
due to the perturbation of the centermost dot. This vertex order is an indi-

cation of the severity of the change in the graph’s structure.

41

3.4 Experiments

Four experiments were performed to evaluate each graph’s structure
detection sensitivity. All experiments were run with a 512 by 512 square
grid. Each experiment consisted of ﬁve prime numbers to initialize the
random number generator and produced ﬁve distinct images with identical
control parameters from which the ﬁgure signiﬁcance measurements were
obtained then averaged. Within each of the ﬁve images, one randomly
generated dotted line is embedded with varying degrees of perturbation
under the control of the three variation parameters (interdot spacing, longi-
tudinal variation and transverse variation). Limits on the line spacing were
imposed based on the Vistnes ratio [V18 87]. This ratio compares the
interdot spacing of the ﬁgure to the average interdot distance of the back-
ground. Vistnes has shown that a ratio of 1.10 is the point where the ﬁgure
is no longer perceivable by humans due to the background interference.
Transverse variation was also limited to avoid creating bars (two dimen-
sional objects) instead of lines. Finally, experimental measurements were
discarded when the Hough transformation did not locate the embedded
structure. That is, if the Hough transform detected a line whose position
and orientation did not match the target line then the ﬁgure signiﬁcance of

such a failure is ignored when computing the averages.

Two experiments were performed to evaluate each graph’s structural
stability to single dot perturbations. Both experiments were run with a 512
by 512 square grid. Each experiment consisted of 100 prime numbers to
initialize the random number generator and produced 100 distinct images
with identical control parameters. With each of the 100 images, the center-

most dot is perturbed in a random direction and in increasing amounts. The

42

maximum perturbation amount is again limited by the Vistnes ratio
[V18 87] of 1.10. For each perturbation, the highest order of the neighbors

effected is averaged over the 100 unifome distributed random dot images.

For the graph stability experiments, a measurement signiﬁcance Z is

computed using a conﬁdence coefﬁcient of 0.95 and the following formula.

(Ni-N2)

2 2 —1—
61 62]2

 

—+_

N1 N2

 

Here til, it; represent the sample means, 0%, 6% signify the sample vari-
ances and N], N 2 give the number of samples taken from the two popula-
tions. AI ZI > 1.96 indicates the difference between the sample means til
and [.12 is signiﬁcant with a conﬁdence level of 95%. The measurement
signiﬁcance is computed using the average neighbor order of the DT and
every other graph. Therefore, til, 0% and N 1 are the mean, variance and
number of samples respectively for the DT at each perturbation amount

and [12, 0% and N 2 are the same quantities for one of the other graphs
under the same perturbation parameter.
Experiment 1 - Spacingj20)

A set of images are generated each of which contains one evenly
spaced dotted line of random position and orientation embedded in a back-
ground of uniformly distributed random dots. The average interdot dis-
tance of the background noise is 20 pixels. Line spacing is varied from 10
pixels (one half the average interdot distance of the background) to 22 pix-
els (1.10 times the average interdot distance of the background) in incre-

ments of three pixels. For each line spacing, ﬁve random dot images are

43

generated and the ﬁgure signiﬁcance measurements are averaged over
these ﬁve images. It is expected that as the line spacing increases, the

graphs will detect less of the dotted line.
Experiment 2 - Spacing, Transverse (20)

In this experiment, transverse variation as well as line spacing is
varied. Line spacing is varied from 10 pixels to 22 pixels in increments of
three pixels. For the transverse variation, a dot on the line is randomly per-
turbed from plus or minus two pixels to plus or minus four pixels. For
each set of perturbation values, ﬁve random dot images are generated and
the ﬁgure signiﬁcance measurements are averaged over these ﬁve images.
Again, the additional distortion is expected to hamper the graph’s structure
detection capability and increase the interference caused by the background

noise.
Experiment 3 - Spacing, Longitudinal, Transverse (20)

This experiment introduces every possible dot variation combination.
For each combination, there are ﬁve random dot images generated contain-
ing one dotted line of random position and orientation. Line spacing is
varied from 10 pixels to 22 pixels in steps of three pixels. A dot is ran-
domly perturbed longitudinally from its evenly spaced position, either for-
ward or backward, up to a maximum of one half of the interdot spacing of
the line. Experiment 3 explores longitudinal variations of plus or minus
three, six and nine pixels. The dots are then subjected to transverse varia-
tions of plus or minus two, three and four pixels with the perpendicular

direction selected randomly. Experiment 3 should provide a rigorous test

44

of each graph’s structure detection potential.
Experiment 4 - Spacing, LonghudinaL Transverse Q6)

The parameters in this experiment are exactly the same as Experiment
3 except that the background noise has been increased by decreasing the
average interdot distance from 20 pixels to 16 pixels. Because of the
decrease in the average interdot distance of the background, the maximum
line spacing need only be 19 pixels instead of 22 pixels. Results of Experi-

ment 4 should mirror the results of Experiment 3.
Experiment 5 — Perturbation (20)

Experiment 5 contains 100 images with the average interdot distance
equal to 20 pixels. The position of the centermost dot is altered in steps of
three pixels starting from 3 pixels to a maximum of 21 pixels. The direc-
tion of the variation is randomly selected. For each perturbation amount,
the highest order of the neighbors effected is averaged over the 100 ran-
dom dot images. Experiment 5 is expected to show increasing average

neighbor orders as the dot perturbation amount gets large.
Experiment 6 - Perturbation (16)

The parameters in this experiment are exactly the same as Experiment
5 except that the dot density of the image has been increased by decreasing
the average interdot distance from 20 pixels to 16 pixels. Due to the
decrease in the average interdot distance of the image, the maximum dot
variation need only be 18 pixels instead of 21 pixels. The results of Exper-

iment 6 should replicate those of Experiment 5.

Chapter 4

Results and Discussion

 

The results of the six experiments are presented in this chapter. The
ﬁrst four experiments involve the analysis of the effect of various perturba-
tions on a graph’s structure detection ability in the presence of noise. The
last two experiments involve the analysis of single dot perturbations on a
graph’s structural stability. Results are presented graphically along with a
discussion and some example images. Note that the curves depicting the
outcome of Experiments 1, 2, 5 and 6 do not represent continuous func-
tions but related measurements joined by line segments to emphasize their
behavior.

4.1 Experiment 1 - Spacing (20)

In this ﬁrst structure detection experiment, the simplest type of varia-
tion is tested. As Figure 4-1 illustrates, it is very easy to perceive the
embedded structure. The line is immediately obvious because the dot spac-
ing of the structure is one half the average interdot distance of the back-

ground. This fact is responsible for the corresponding high average ﬁgure

45

46

signiﬁcance values of Figure 4-2 at a line spacing of 10 pixels. All four
graphs perform well at this spacing, connecting the closely spaced dots and
detecting the associated structure direction suggested in [ROS 73]. Figure
4-3 and Figure 44 give the MST and DT neighbors of the structure in Fig-
ure 4-1 and reﬂect the high average ﬁgure signiﬁcance measurements by
maintaining the majority of connections between the structure dots. Refer-
ring again to Figure 4-2, graph structure detection performance begins to
decline as the interdot spacing of the line increases. Note the gap between
the DT and the MST at the line spacing of 19 pixels indicating that the
MST is more strongly affected by the widely spaced structure points. The
insensitivity of the DT is present throughout the range of line spacings. An
important point in interpreting the experimental results is that the purpose
of Experiments 1 through 4 is to ascertain trends in the graph’s structure
detection capability under the parameters tested by each experiment. Fig-
ure 4-5 shows the same line as Figure 4-1 but with a spacing just shy of the
average interdot distance of the background. The increased difﬁculty in
perceiving the dotted line of Figure 4-5 is reﬂected by the MST’s inability
to locate the complete line and is illustrated in Figure 4-6. Figure 4-7 gives
the DT of the line in Figure 4-5 and still maintains the neighbors of the
dots that make up the line. The lower than expected average ﬁgure
signiﬁcance values of Experiment 1 can be attributed to the band used in
determining the image points of the Hough detected line. Here the band
surrounding the line is of a ﬁxed width and the line is located in the center.
In Experiments 2, 3 and 4, the band is of the same ﬁxed width but due to
the transverse variation of the dots comprising the line, the band surrounds

the line in a manner that results in the detection of the largest number of

47

points. Therefore, the results plotted in Figure 4-2 and Figures 4-9, 4-13

and 4-14 cannot be compared.

48

 

 

90 0 0 0
0 00 0 90 .9
.0 09 0 9o. :. ' :0 . 9 9 0 9
0... . . .0. . . .0 . ..0 . .0 .
9 . 0 .. 09. . 9 . 0
.. 0 ' . 0. 0 . 0 0
0 .:.. 0 . ..0 . . . ~ .
. O . . O .0 . g
. .. . i . 0 . .... . .. 00
. 0. 0 0 9. 00 0 0 0
O . . .0 . . . {.Q . .
0 “0‘ 0 . .. . .9
'00 9 0 . 0. .9 0
p 0 ’ 0
0 . 00‘ 9 ’0 . . . '0'. ~ 0
Q C O . . C
.0 0 I ~ 0 .
. 0.0 :. . 0 . 0 9
. ' 00 . .0 ' .
9 0 ' 0‘ .9 0 . . 0
0 . .'o ' . 9. ' 9 0 0
0 9 0 ... . . . 0
. 9 .' 9 0 .9. .9. .. .‘9 . 0 0. '
:0 0 . . . . ..: .9. - 9 9O , . .0 C
O . O
O . Q Q ... . 0’ .0. ‘ e ‘ 0.. .
' .. O. .. . .. .0 .0 g . .
g 0 0 0.9 0 0.
-. . . 0 0 . 0 . .:0 ‘0 . . 00 . .0
0
. O... . ‘ . O .. .. . . .. .2. .
. 0 . 0. 9 .0 ‘ 0 ' O ... . . .0 . .
0 .$ . ' Q 0 g 9
9 0 '. . 0‘ '0 . .1... . .. 0
.. . 0 I . . g .. O . O
.0 0. 0. 0. 0 . .. 9 .9
0 g .. . .. 0 . . . .0
0 . . 9 . 0 9 9' .0 . 0 0
0
0 0 ... 0 9. .
. O . : . . . . ...OO ’0. Q
.- . Q. . O. . .t :A O. . ~‘ ..

 

Figure 4-1 Experiment 1, Small Dotted Line Perturbations

 

49

 

Ave
Fig 0.5 -—
Sig

0.1 —

 

l

 

 

 

11111111 1111
10111213141516171819202122

Line Spacing (pixels)

Figure 4-2 Experiment 1, Average Figure Signiﬁcance Results

50

 

 

 

 

 

Figure 4-3 Experiment 1, MST of Small Dotted Line Perturbations .

51

 

 

 

 

 

Figure 4-4 Experiment 1, DT of Small Dotted Line Perturbations

 

52

 

‘0 90 0 O 9
0.
9 9 09 9 0.. 8. 9 g 9 0 0 .9 9. 0 9 9
.0909 : .9 9 9 99 9 0 9 .9
0 0 . g 0 0 0 0 .
. . 0 . 00 0 0 ..0 . . .0 . 0 .
.. : . ' . O. I .. Q . O .. O T
. 9 . .O . . ~ . ..
9 0 9 0 . 9 0 99 .0 9 09 0 9 9
' . O. 9 O
9. 9 0 9 0 9.: 0.. 00 o 9 .9 . .9.
C .. . .0 . . . .{.. . C
0 0-0 9 99 .9 .9 9 99 0
0 . 0. ’ .9 0
. 00 99’ 90 0 . . 9. 0o 9 9 a
0 . . 0 9 0 . 0 .9 0
0O .0 0 ‘ 9 O . .
9 9 0. 0 :... 9 9. 0 9
0 9 9 0 ..0‘ . ..O.09. 0. .0 0 ~
0 . 0 . . 0.9. . 9 . . 9 0 0 .
0 O
. 9 . . 9 0. . . 9 0 0 0 0 ... . 9.. . 09 . t .
0 9 Q 9 O
'0 . . O . . .0 ‘.O , g . : .
. 0O 0.. . . 09 . . .0 90 . .0 Q
9 9 9 90 90 g 0
90 00 9.. . .9 9.. 0 9 9 ’9’. 9 9 9 0..
0 9 0 9 9 0 0 0 9 o .0 9 90
9 . . . . 9 9 0 9 .099. 9 . .000 0 9.
0 §
0 :0... 9 9 9 9 9 9 9. 9 9 9 9 .0. 9 0 0.
. C ‘ C .. .C.
0 . 0 . . .. . 0 . . 0 0 .
9 0 9‘ 9 9 D . “0 9 9
. 0 . .9 0 .$ .. . . .. I .. . 0%
O .' 9 0.. . . O 9. O .
0. .0. . .0 .. .. 0 0 .0 a. .
0 00 O a. .9 .0 .9 9 9 9 9 9. ‘ 9
0 0 0 0 0
. 0 0 9 . 9 . 0 ... I g 9 .9 9 9 0
9 0 . O 0 . . 0 . 9 000 :9 9
0 9 g 0 ..9 0 .ﬂ :9: . :1999 .0

 

Figure 4-5 Experiment 1, Large Dotted Line Perturbations

 

53

 

 

 

 

 

Figure 4-6 Experiment 1, MST of Large Dotted Line Perturbations

54

 

 

 

 

 

Figure 4-7 Experiment 1, DT of Large Dotted Line Perturbations

55

4.2 Experiment 2 - Spacing, Transverse (20)

Figure 4-8 is an example of the additional level of structure perturba-
tion in Experiment 2. In this test, transverse variation has been introduced
in increments of one pixel beginning with plus or minus two pixels and
ending with plus or minus four pixels. Since Figure 4-8 does not contain
large amounts of perturbation, it is still easy to perceive the line. The rela-
tively high average ﬁgure signiﬁcance measurements of the DT depicted in
Figure 4-2 are again evident in Figure 4-9 with all four graphs performing
well in the cases where the structure to background interdot distance ratio
is small. Like Experiment 1, as the interdot spacing and transverse varia-
tion increase, all the graphs retain less of the line with the MST retaining
the least and having the highest rate of disintegration regardless of the
transverse perturbation amount. The sharp decline between the line spac—
ings of 19 and 22 pixels is due to the small number of valid ﬁgure
signiﬁcance measurements used for the average. As pointed out earlier,
ﬁgure signiﬁcance measurements are discarded if the Hough transform
fails to detect the target line. Figure 4-10 shows the same line as in Figure
4-8 except that the structure interdot spacing is nearly doubled. A decrease
in the average ﬁgure signiﬁcance measurements of Figure 4-9 accompanies

the increased perturbation depicted in Figure 4-10.

 

56

 

"—1-. v- 90 O 9
9 9 90 09 9 99 O 0 9 99 99 9 9
0 9 :9 0 9 9 0 9
.. O .' 0 ~ 3 Q,
. . . . g .0 .0 . . 0 . .0 . .
. . . 9 0 0 0 g .
0 9 09 Q 99 0 0 999 9 9 9 9 0 9 9 9'
.. . . . 0 . 0 9 0.
O. O Q .. . . ~ 0 O
C Q . . . .. .
O O 9 .0 9 .. Q 0 9
. 0. O 0. ... .. 00 . 0 .
0 0 9 9 9 999 00 9 9 9 90
0 9 . .0 9 . 9 9 0 . 09
9 0 9 9 0 g 0999
9 9999 99 90 O0 9 9 9 09 0
.. O 9 ' 9 0
I0 0 I 9 9 0 90 ~ .
9 g 0 9 9 09 0 99 9 9
0| .0. 9 ~ 9 9 o 90
. 9 9 0 0 ::.0 9 9 9. . a
O . . . Q .. ﬂ .
. . 0 . ¢;:.....9 .. :0 .. u
0 9 0 0 g 9 0
0 .0 0 . 00.. . . . .0 '
9‘ Q .. O 9 O . O. . O. O. 9.. 9 . .9 .
" : O 9 9 O O ‘0- 9 Q : Q
. 9. 9 0 99 0 . .9 99 $ .0 Q
0 . 9 9 900 . 9.9 909 $ ﬁ 9 0. 0 .
9 99 .0 0 .0 9 9. 9 9 09
p . ' . . . . .. . .. . . . . .
. . . . O . . ..’.. . . ...
f 9 9 0" 0 9 0 9 0 9 9 9 9 90 9 99 0 9 0
. 090. 9 . 9909 9 9 .099 g 0
I'D 0 . 0 .9 .ﬁg9. 0.90 0 099.99
. 0‘ 9 0 9. 009 0 0
O 9 9 99 9 Q‘ 9Q C 9’ 9 O. 9%
P: 99 9 9.9 . 9 9 9 90 99 990 9 9
9 .0. .0 .0 90 :g . 0 ..9 09 99 .
. ... . . . 0 .0. 0 . . . 0. 0 .. 0
9 9 0 9 0 9 9 0 99 99 9
9 .00 9
9 9 9 0 9 : 9 9 9 9 9 900 9909 9 0
9 9. 9: 9 00 9 09: 9.9 99; 9 91999 9

 

Figure 4-8 Experiment 2, Small Dotted Line Perturbations

 

0.9
0.8
0.7
0.6
Ave
Fig 0.5
Sig
0.4
0.3
0.2

0.1

57

 

 

 

 

_ - <99

a \\

E]

F— nag

— DT “
— ---- GG
........ RNG
—- —— MST

1 1 l l 1 4 l 1 1 1 1 u 1

10 11 12 13 14 15 16 17 18 19 20 21 22

Line Spacing (pixels)

i2(*), i3(A), i403) Transverse Variations (pixels)

Figure 4-9 Experiment 2, Average Figure Signiﬁcance Results

 

58

 

 

 

w
: I . ’0 o. ' .. . . . O . " ~ . o
0 Q .
I o o . o
o '0' . ~ 3 o a o a
.. . . C . . .
' ' o O '0 o o . 'g . .
C C . .. .0 . C . . C
O .. .0. . . .. . C . . ...O I
o ' 0 .0 . . . Q. .0
C . C . . . . .C .. . .. .. .
’ o ’ o o ’0'... .’ ..o .'.
o o I o
. o '0 o 0' . o . u ‘0' o. '. .
. .C .. .0 . C. . ..
o 0 0
an “a .~.o. .. ' . 0' . 0 ~ . . .
. ... . ‘ . O: . ‘ : I. . .. O
.. 0.0 o o o. ' '
. ‘ ' o a a... ' . o '
o . o . . $.‘. .0...¢I : 0.. ~
. o . ' 5.. . . o . . . o
. O . . . 0 g . . .0
O . .0 . . . . O ' '
$ 0 . . ' o . '0 ' Co . 0
'0. o . 0 .CI' . o . :0 '
. .05.... 00' '.. .ﬁ .0 00,. .ou
o o
.0 o. .0. . ... .Q' .0 ..‘ ’0. ‘ ...o ."
D O ' . . . . . .... . .... .0
o o
’ . Q. .C. . . .0 ...... ‘. . 0.... O. .
0'... .‘. . ..... . ' 0" on
o o
:0. . o . a. ' .0 ‘ O '0 o ’ :.o..
c
o '2'. ‘ .. ‘ o .000 ' . ’0‘
' o O 00
.: .. o ... . O. . 0 .. .0 O o .
'| .0 o o. O. a. ' ' .' 0'
. ' o. o o. ' . o O 0. ‘ o .
. ...:. . . .. . o . .8 . .0 a.
. . . ... O . .’o O .
. ' ' 0 ' o o
- ~.' ' -:- ' ' - .1 :5; . '-

 

Figure 4-10 Experiment 2, Large Dotted Line Perturbations

59

4.3 Experiment 3 - Spacing, Longitudinal, Transverse (20)

Figures 4-11 and 4-12 contain all possible line perturbations. The line
in Figure 4-11 is immediately obvious while the line in Figure 4-12 is not.
Figure 4-12 emphasizes the effect of the background absorbing the struc-
ture when the structure to background interdot distance ratio approaches
1.10. Average ﬁgure signiﬁcance measurements plotted for Experiment 3
do not distinguish between the combinations of the longitudinal and
transverse variation amounts used. The only distinction made is of the
graph type. Also, no points are joined by line segments because the
number of points possible at a line spacing of 10 pixels is not equal to the
number of points possible at a line spacing of 13 pixels. This is due to the
dependency of the longitudinal variation range on the structure spacing and
is shown in Figure 3—3. The DT structure detection results of Figure 4-13
agree with those of Figure 4-2 and Figure 4-9. Figure 4-13 gives an indica-
tion of how the graphs separate into four groups with some overlap of the
neighbors in the graph hierarchy. This overlap is caused by extremes in
the perturbation parameter values. For example, for a given line spacing,
the DT of a line having plus or minus nine dots longitudinal and plus or
minus four dots transverse variation can produce a ﬁgure signiﬁcance value
similar to the CG of a line having plus or minus three dots longitudinal and
plus or minus two dots transverse variation. At a line spacing of 22 pixels,
the most challenging, it is clear that the DT gives the best performance of

all the graphs.

 

6O

 

 

Figure 4-11 Experiment 3, Small Dotted Line Perturbations

61

 

 

 

." .0 0
' 0’ . 0.. g 0 0 . . . .. O. .
00’ O '0 8 ' . . ' .
0 0 . 0 . . 8 .. . .
. . . g C. . .. C O. . .. . a.
: :0 ' z. '0 O .' . . . . . ..
O . . .. Q . .0 . ... .
. . . . . . O. . ~ ..
. . . ’ .0 . Q. C C .
. . . C.... .. ... O . C
. .. .0 . . O. O Q . '
0 0.0 . 0 .. ' i.. . .. .
. .‘. . I . 0 C .0 . ..
0 00 .~ . . ' I .
' O O
.. . ‘ . . . . 0. g 0 O o
00 . s ' ~ ' . .
I C .0. g : . .. . .
0 0 ... . . . .
. O 0 0.0‘ :0 0.. . . 0
0 0 .. . o '0 ' . " ' '. o o ‘
0 . 0 . O . 00 O 0 . . .
$ 0 0 ' .' 0 ... . . . . ’
0'0 ' . . . .. . .
0 ﬂ '0 0 '. . 0. ' ' '0'- . . '
. . .0 O0 , . :.
0. 0 . '00 .0 .0 . .. ~
00 .0 0 .0 0 . ‘ I: $ ... .
P .0 ' 0 ' ’ . 0 ' 0 :. ' ' . ..
P C a .. 0 0 . . 0 . 0.0.. . . .. .0.
0 0 0‘ I 0 ° . ‘ . ... . .
I. . '. . .. . ° . 0 ..O .
0
0 . ' . 0.: ‘0‘. ‘ . . .. . . :.0 ... . .
0
. . .0 . .‘ . . ‘ 0 '0'. I . .0
0:. " . '0. g ' .. . .0 .. ' .. . ‘
0 00 I . ' 0 00 ' O 0 " .
0'00 ’. 0 ' ’ . O . O
O. . .. .0. t . .. . .
I C o . . .
D O . 03' 00. . . . . ' ...:. 1.. . .
0J OJ 0, 0 :00 .

 

Figure 4-12 Experiment 3, Large Dotted Line Perturbations

62

 

1 _ :1: :1:
s :1: i
0.9 _ ° *
e g * $
0.8 _ g A g ., :
m as
A * i
0.7 — 1:1 3 3
8 x
i A 8
0.6 —- 0 8 0
Ave @ A
Fi 0.5 L- A
g e? a Q1
0 4 — D m D
O 3 — D E
0.2 1— D
* DT
0.1 — 0 GO
A RNG
O - D MST

 

 

 

1 1 1 1 1 1 1 1 1 1 1 1 1
10 11 12 13 14 15 16 17 18 19 20 21 22
Line Spacing (pixels)

i3, i6, :9 Longitudinal and i2, i3, :4 Transverse Variations (pixels)

Figure 4-13 Experiment 3, Average Figure Signiﬁcance Results

63

4.4 Experiment 4 - Spacing, Longitudinal, Transverse (16)

Experiment 4 is exactly the same as Experiment 3 except for the
decrease in the average interdot distance of the background (higher dot
density). The superior structure detection capability of the DT exhibited in
Experiment 4 supports the ﬁndings of Experiment 3 and are plotted in a
similar fashion in Figure 4-14. Figures 4-15 and 4-16 show examples of the
increased background noise and different degrees of line distortion. Note
that in Figure 4-14 at a line spacing of 19 pixels, the four graphs group into

a well deﬁned hierarchy.

64

 

1 _ * =1: * :1:
E i ,.
0.9 _ A § 3 3
o “5 if
m 0
0.8 — 1:] A o
A o g
D a A O
0.7 — Q A 8
0.6 _ 1:1 A 2
Ave g A
[:1
Fig 0.5 _ g A
. 1:1 4
Srg A
0.4 — E
CI
0.3 —- a
0.2 ~
* DT
0.1 - 0 CG
A RNG
O - D MST
l

 

 

 

1 1 1 1 1 1 1 1 1 1
10 11 12 13 14 15 16 17 18 19 20
Line Spacing (pixels)

:3, i6, i9 Longitudinal and i2, i3, :4 Transverse Variations (pixels)

Figure 4-14 Experiment 4, Average Figure Signiﬁcance Results

65

 

 

 

 

.0
.c' . '6‘ " .-
0. 0. 0 O .0 : ... 0 .' .‘T? j .
. U
I. .. .’. . ... . 0.0: O . ' 0 0 0 .O§ . 0.. ' ’. . 0
. . . . ‘ . . .. .. . .0: . . 0' . 0' 0. .0
0 ..
0 0 O 00. : 00. - $ "0.. ' . ' :..' ... . . .
I g g. . : . O .. .. .. .
. . . “* . . . .‘.. . .0 t. 00'. 0 " 00:0
. . ‘ . . .0 O 00 0 g 00 C I
8 .. . .' . . 0 0 0 O. 0
O. . . ‘ .0 . 0 O . ‘. .. .
.11. a. s. .|- up. '- " '..
. . .... . :* . . . .C ’ . . . Q Q
0 ‘. 0 f '0. ' 0 .‘.0 '. ' 0 0. ' 0. . ’ n .0.
0 O 0 0 ' . . ' .
:0'. 000. . ' 0‘: “.0 .. . : .00.$.O. " :
O .. Q 0' '0'. . O . . . ?.. . . . ’.. . .. .
.9 . . .. ..,. . . 0 I 0 0 0
O. : C Q . . . . O . ’0 . . . .
O .. 0 0 0 0 . 0‘ . 0'0 . . . . ~ .. ; ‘-
0 .0 ' O. ':0 0 ' . ‘0 .‘.000 . ... .....
0 . 0 .0 0 0 0 . 0 . O. ' 0. . ﬁ .. ..
0 00. 0 0. 0 0 .0 0 0 9000'... .
.. ’. . .. ...O . . ‘0 0.. .0 . . ... ..o
I: . .. . . .... O. . ﬂ . 0 . O . .
0 ' . Q 0. . 0 . a . . . .
0 O0 .. O I . ' . . . ‘ . .
b :0 ‘....',0l '0 ~ C 0! . . O0 0 0
:.....:.0 O . : .0 . : 0. . . C. ’ .0 ...
00 . . o 0' . ' : ' g. 0.. : ‘ .
0 . .
P . ... . .~ . .. . . . . . . .. . . .. .. .. .'
0.. 0 . O 0 t. . .. a .
.0 ' .0 00 . ' . .. . 0 . .
0
0 ° .0 0.0.’ '. 0'00 . ’1 .. ....
.. . . . . . .O. .0 O. . . . . . .
0 0 0 000 ' . . . .~ .
0 0 . u . . .
.1 0.. 0 0 ' 0 0. I o . 0 \' 1. . . . .
.. . “.3. . ‘ ‘ z. 0. u. 0 ' 0.
0 .. a 00. . . .
_l: r ' 4? 0: ‘ 1.," 1

 

 

Figure 4 15
- Ex '
penment 4, Small Dotted Line Pert b
ur ations

66

 

 

 

.v . .. .. .0 .0 “—7. v . ..0. 0
. .t . .0 I .' . . ’0'. 0 .0§ . '00 00. .. 0.
0 0 0 0
0 O 0 0 ' 0
C. C. . . .. . . . . C C
P .0 .I. 0 .. ..0 ..0' . 0: 0.. '30 0' 0 .
. .‘.. .'0 0"“ . . ... 00 00.0
0 g 0 0.. Q ... - . .0 .0 . . 0‘ . .. ‘
0 ' . g .. 0'0 . 0.. {D 2.0 . . . .
'. 0. ‘ ' 0 . 0 ‘ '0 0 0 .
.. '- . 00“ . . I . ".0.. ... . 0 .00 . .' .
‘ C. CC. . O k . . C . .
' ' ' . . c ‘ . . .‘ .. 0 0 '0 0'
0 0 0
O .‘ . . :0. . .. . ..‘ . 0 00. . ' .'
‘ 0
. 0 0 . 0 . 0 0 0
. 0.00 .0 0: ‘50 .' .0 0 1. $ 0..."...
. ~. . - - . . 3' - : - - -' - .
.0. 0 .... . .30 .
0 ' ' . o . . 0 . . 0
.' 0.0. . 0 . . . 0 t . : . g... . .. 00 0'.'0$.
. '.. .0' 00' .0 . Q 0 0’0 . . 0. 0.0 '.
0 0 O 0 0
IV.. . . . 0 .. 0 . :0. :0....' g. 0..
‘ . CC. . C . . C C
0 0 . . . . y 0 .00 . . 0. 0 '
0 . 0: . ° '0 ‘ O ‘ 0 ' .
" . - " ' u" 0 J.’ ' o ' ' '
0 " 0 .0 . . . . . . . . .
' . ’~ 00. 0 . 0 ' . . h 0 ' 0 ‘ . O0 0 : .
. C ' . .C .
’0 . 0 . . . 0 .f 0 ’ .. 0.0.
0 O0 0 0
.. 0 :‘i... 0 . 0‘0 .. . . 0. .: 0 : ‘
0 ’0. O . O Q .0 O . 0 . ~0 0 . . 0
“C 00' 0. . 0 O ... .
’. . ' ‘ 0 0’0. ' '. I 0 O . 0
. . 0 ' .. 0 '.. ' 0. . 0 ' '0 0 .00
, . ... 0.0$ 0. . .. . . . 0 0‘. .0 0
'0 O . 0 00 ' ' 0
0O 0. 0 0 .. 0 O .' . 0 '~.
0 . 0 I O. .' '.. '0 .. '3" . . .. .I
.. . '. 0 ' 0 . . . 0"“ '0. .0 . o
0. 0 0 0. . 0 .30. ‘ ‘ .0 Nil .0. ~
- ~' 0'.“ 0. . . 0 0 f ' :4: "'. - ‘

 

 

 

Figure 4-16 Experiment 4, Large Dotted Line Perturbations

67

4.5 Experiment 5 - Perturbation (20)

In this experiment and the one following, a single dot has been per-
turbed and the highest order neighbor with altered vertex adjacencies is
determined. The average of the highest neighbor orders effected by each
dot perturbation is given in Figure 4-17. The trend exhibited by the data
shows that the average neighbor order effected by the dot perturbations is
larger for the GG, RNG and MST than the DT. The values of the measure-
ment signiﬁcance Z computed using the average neighbor orders are given
in Table 4-1 where an absolute value of Z greater than 1.96 indicates that
the difference between the average neighbor orders is signiﬁcant. Table
4—1 indicates that a signiﬁcant difference exists between the average neigh-
bor order of the DT and any other graph at dot perturbations greater than or
equal to 9 pixels. The only other signiﬁcant difference between the aver-
age neighbor order measurements exists at a dot perturbation of 6 pixels
between the DT and the MST. Note the high variances of the MST over the

entire dot perturbation range.

 

4.5

3.5

Ave
Ngh 2.5
0rd

68

 

 

 

 

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
6 7 8 9101112131415161718192021
Dot Perturbation (pixels)

Figure 4-17 Experiment 5, Average Neighbor Order Results

 

 

69

Table 4-1 Experiment 5, Signiﬁcance of the Average Neighbor Orders. The

difference in the average neighbor order measurements (11) between the DT and any other graph are

signiﬁcant if I ll > 1.96. These values of 2 have been marked with an asterisk (*). The variances (02)
used in computing Z are also listed.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Dot Perturbation Graphs

or GG RNG MST

11 1.18 1.15 1.17 1.05

3 0'2 1.33 1.25 2.10 4.13
z -019 -005 -0.56

11 1.72 1.98 2.04 2.35

6 02 1.16 1.04 2.24 7.63
z 1.75 1.74 2.13*

p 2.13 2.39 2.56 2.90

9 67- 0.73 0.72 2.15 7.41
z 2.16* 253* 270*

11 2.46 2.70 3.09 3.48

12 02 0.43 0.59 2.08 7.75
z 238* 398* 357*

u 2.63 2.95 3.43 3.44

15 0’2 0.45 0.63 2.03 4.99
z 308* 5.08* 347*

11 2.91 3.15 3.97 4.24

18 02 0.30 0.69 2.81 7.76
z 241* 601* 468*

0 3.14 3.43 4.06 4.34

21 62 0.36 0.89 . 2.46 8.84
z 260* 5.31* 3.96*

 

 

 

70

4.6 Experiment 6 - Perturbation (l6)

Experiment 6 is a duplicate of Experiment 5 in every way except that
the dot density is increased. The high relative stability of the DT’s structure
indicated by the results of Experiment 6 are in agreement with those of
Experiment 5 and are shown in Figure 4-18. The values for the measure-
ment signiﬁcance Z in Table 4-2 show that the difference between the aver-
age neighbor orders is signiﬁcant for all dot perturbations greater than or
equal to 9 pixels. In this experiment however, the signiﬁcant differences
generally occur between the DT and every other graph except the GG. The
only signiﬁcant difference between the average neighbor order of the DT
and the CO is at perturbations of 12 and 18 pixels. Again note the high

variances of the MST across all dot perturbation amounts.

4.5

3.5

Ave
Ngh 2.5
0rd

71

 

 

 

 

——MST
......... RNG
..... GG
— DT
AJJIIJIIIJJIIIIJLJIIII
O 1 2 3 4 5 6 7 8 9101112131415161718192021

Dot Perturbation (pixels)

Figure 4-18 Experiment 6, Average Neighbor Order Results

 

 

72

Table 4-2 Experiment 6, Signiﬁcance of the Average Neighbor Orders. The
difference in the average neighbor order measurements (11) between the DT and any other graph are
signiﬁcant if I Z | > 1.96. These values of Z have been marked with an asterisk (*). The variances (0'2)

 

 

 

 

 

 

 

 

 

used in computing 2 are also listed.
Dot Perturbation Graphs

DT GG RNG MST

11 1.52 1.46 1.53 1.78

3 0’2 1.09 1.51 2.03 4.95
z -037 0.06 1.06

11 2.20 2.25 2.33 2.40

6 0'2 0.52 0.91 2.02 5.70
z 0.42 0.82 0.80

11 2.51 2.69 2.87 3.03

9 02 0.49 0.79 2.19 5.61
z 1.59 220* 211*

11 2.80 3.04 3.42 3.36

12 0'2 0.46 0.94 2.38 5.03
z 203* 368* 239*

u 3.07 3.27 3.92 4.14

15 0’2 0.53 0.94 3.21 7.28
z 1.65 440* 383*

11 3.24 3.59 4.53 4.44

18 0'2 0.44 1.04 4.09 8.11
z 287* 606* 410*

 

 

 

 

 

 

 

Chapter 5

Conclusions

 

Various graphs have been suggested as tools for detecting structure in
random dot patterns. The DT, GG, RNG and MST have been evaluated to
determine their relative potential in this area. Additionally, the DT, GG,
RNG and MST have been evaluated to determine their relative stability in
deﬁning a neighbor relation on image entities. Results have been presented
in previous chapters. This chapter draws conclusions from the performance

measurements and gives suggestions for future work.

5.1 Summary and Conclusions

The DT, GG, RNG and MST have been examined to determine their
relative performance in detecting linear structures implanted in uniformly
distributed random dot patterns. Four structure detection experiments have
been performed focusing on the detrimental effects that structure dot per-
turbation has on the graph’s ability to retain the neighbor relations among
the dots comprising the structure. The types of structure perturbation

employed were interdot spacing, longitudinal variation and transverse

73

74

variation. The performance of the graphs was quantiﬁed by one measure, a

ﬁgure signiﬁcance.

The DT, GG, RNG and MST have also been examined to determine
their relative structural stability. Two graph stability experiments have
been performed focusing on the range of the effect a single dot perturba-
tion has on the graph neighbors. The dot perturbation amount was sys-
tematically varied with the direction selected randomly. The stability of the
graphs was quantiﬁed by the highest order of the neighbors effected by the

change.

It is not surprising that all the graphs performed well in the easy cases
of the structure detection experiments. All these cases included a dotted
line with an interdot spacing much smaller than the average interdot dis-
tance of the background. These instances are given in Experiment 1, in
Experiment 2 with transverse variations and in Experiments 3 and 4 with a
combination of longitudinal and transverse variations. In these situations,
the graph neighbor relations of the DT, GG, RNG and MST maintained the
connections between the image points that were in close proximity to one

another.

Across all structure detection experiments, the general trend is that the
performance of each ,graph degrades when the amount of perturbation
increases. This trend holds whether there exists a single type of perturba-
tion or a combination of perturbations. Furthermore, the results exhibit the
general tendency of the performance of the DT to degrade slower than the
performance of any other graph. Since the neighborhood deﬁnition of the
DT allows a node to have a greater number of neighbors than any other

graph then the DT should suffer the least drop in structure detection

75

performance. This outcome is most apparent in Figure 4-9 portraying the

results of Experiment 2.

Turning to the two graph stability experiments, the pattern that
emerges is that when the dot perturbation increases, all the graphs have a
higher order neighbor effected. The experimental results indicate that the
DT is the best at localizing the effect of single dot perturbations and the
MST is the worst. The difference in the sensitivity between the MST and
the DT is signiﬁcant and can be attributed to the global versus local nature

of their graph neighborhood deﬁnitions.

The major contribution of this thesis lies in the systematic examination
of the sensitivity of a family of closest-point graphs. A minor contribution
was the development of a measure to quantify the structure detection per-
formance of the DT, GG, RNG and MST. The new results from this study
indicate that the DT has the greatest ability to locate dotted linear structures
when a relatively high amount of interference is present and is the most

structurally stable under single dot perturbations.

5.2 Future Work

The structure detection performance evaluation in this thesis concen-
trated on the simplest of all dotted structures, the line. The linear case is
just one of the many possible structures that need examination. Another
form is the circle. The circular case is important because a circle, or one of

its relatives, is encountered very frequently in image processing tasks.

Another area of further study would be an investigation concerning the
interaction of multiple lines and curves during structure detection. Every

image in computer vision is comprised of many straight and curved lines

 

76

contributing to the overall shape of each object.

An extension of the graph stability experiments would be to study the
effects of multiple dot perturbations on the graph’s structure. The graph
with the most stable neighbor relation would be very useful in providing
information where small distortions are present in multiple images of the

same scene.

With the results from this thesis and the areas of future work sug-
gested, the development of a formal algorithm to detect linear structures in
arbitrary images using graph neighbor information can be attempted. This
algorithm would have to deal with eliminating noise lines whose points are
all graph neighbors. One possible solution would be to calculate the ﬁgure
signiﬁcance and multiply it by a measure that would be able to distinguish
if the dots of the candidate structure are from the same population as the
surrounding environment. If the dots of the structure are of the same popu-
lation as the background, then the measurement should be low and when
multiplied by the ﬁgure signiﬁcance would produce a low overall value
thereby eliminating the noise line from further consideration. Otherwise,
the measurement should be high giving a high overall rank after multiplica-

tion and labeling the line as a valid structure.

The DT may not be practical for all situations where linear structure
needs to be located. If the magnitude of the variations are known to be lim-
ited to the range where the MST does well then the MST is the better
choice. However, if nothing is known about the linear structure perturba-
tions present in an image or if the range of the perturbations is unrestricted
then the DT is a worthy candidate for providing reliable graph neighbor

information in linear structure detection tasks.

 

Bibliography

 

[AHU 82] Ahuja N., "Dot Pattern Processing using Voronoi Neighbor-
hoods", IEEE PAMI, V4, 1982, pp. 336-343.

[BAL 81] Ballard D. H., "Generalizing the Hough Transform to Detect
Arbitrary Shapes", Pattern Recognition, V13, 1981, pp. 111-
122.

[BOX 58] Box G. E. P., Muller M. E., "A Note on Generation of Normal
Deviates", Annals of Mathematical Statistics, V28, 1958, pp.
610-61 1.

[BRO 83] Brown C. M., "Inherent Bias and Noise in the Hough
Transform", IEEE PAM], V5, 1983, pp. 493-505.

[CAS 87] Casasent D., Krishnapuram R., "Curved Object Location by
Hough Transformations and Inversions", Pattern Recognition,
V20, 1987, PP. 181-188.

[DUD 72] Duda R. 0., Hart P. E., "Use of the Hough Transformation to
Detect Lines and Curves in Pictures", CACM, V15, 1972, pp.
1 1-15.

[FAI 83] Fairﬁeld J., "Segmenting Dot Patterns by Voronoi Diagram
Concavity", IEEE PAMI, V5, 1983, pp. 104-110.

77

Wyn-1:: age-mp

78

[GEB 67] Gebhardt F., "Generating Pseudo-Random Numbers by

[GRE 78]

[HOU 62]

[ILL 87]

[JAR 73]

[KOF 35]

[KRU 56]

[MAI 86]

Shufﬁing a Fibonacci Sequence", Mathematics of Computation,
V21, 1967, pp. 708-709.

Green P. J ., Sibson R., "Computing Dirichlet Tessellations in
the Plane", Computer Journal, V21, 1978, pp. 168-173.

Hough P. V. C., "Method and Means for Recognizing Complex
Patterns", U. S. Patent 3069654, 1962.

Illingworth J., Kittler J., "The Adaptive Hough Transform",
IEEE PAM], V9, 1987, PP. 690-698.

Jarvis R. A., Patrick E. A., "Clustering using a Similarity Meas-
ure Based on Shared Near Neighbors", IEEE C, V22, 1973, pp.
1025-1034.

Koffka K., Principles of Gestalt Psychology. Harcourt Brace
and Jovanovich, 1935.

Kruskal J. B. Jr., "On the Shortest Spanning Subtree of a Graph
and the Traveling Salesman Problem", Proceedings of the
American Mathematical Society, V7, 1956, pp. 48-50.

Maitre H., "Contribution to the Prediction of Performances of
the Hough Transform", IEEE PAM], V8, 1986, pp. 669-674.

[MAR 62] Marsaglia G., "Random Variables and Computers", Transac-

tions of the Third Prague Conference on Information Theory,
Statistical Decision Functions, Random Processes, Czechoslo-
vak Academy of Sciences, 1962, pp. 499-510.

[MAT 80] Matula D. W., Sokal R. R., "Properties of Gabriel Graphs

[PRE 85]

Relevant to Geographic Variation Research and the Clustering
of Points in the Plain", Geographical Analysis, V12, 1980, pp.
205-222.

Preparata F. P., Shamos M. 1., Computational Geometry, An
Introduction, Springer-Verlag, 1985.

 

79

[PRI 57] Prim R. C., "Shortest Connection Networks and Some General-
izations", Bell Systems Technical Journal, V36, 1957, pp.
1389-1401.

[ROS 73] Rosenberg B., Langridge D. J., "A Computational View of Per-
ception", Perception, V2, 1973, pp. 415-424.

[SHA 75] Shamos M. I., Hoey D., "Closest-Point Problems", Proceedings
of the Annual Symposium on the Foundations of Computer Sci-
ence, 1975, pp. 131-162.

[SHA 79] Shapiro S. D., Iannino A., "Geometric Constructions for
Predicting Hough Transform Performance", IEEE PAM], V1,
1979, PP. 310-317.

[SKL 78] Sklansky J., "On the Hough Technique for Curve Detection",
IEEE C, V27, 1978, PP. 923-926.

[TOU 80A]Toussaint G. T., "Pattern Recognition and Geometrical Com-
plexity", Proceedings of the IEEE International Conference on
Pattern Recognition, 1980, pp. 1324-1347.

[TOU 80B]Toussaint G. T., "The Relative Neighbourhood Graph of a Fin-
ite Planar Set", Pattern Recognition, V12, 1980, pp. 261-268.

[TOU 87] Toussaint G. T., "Computational Geometry: Recent Results
Relevant to Pattern Recognition", NATO Advanced Study Insti-

tute on Pattern Recognition Theory and Applications, V30,
1987, PP. 295-305.

[TUC 86] Tuceryan M., "Extraction of Perceptual Structure in Dot Pat-
tems", PhD. Thesis, University of Illinois at Urbana-
Champaign, 1986.

[URQ 82] Urquhart R., "Graph Theoretical Clustering Based on Limited
Neighbourhood Sets", Pattern Recognition, V15, 1982, pp.
173-187.

[VAN 81] van Veen T. M., Groen F. C. A., "Discretization Errors in the
Hough Transform", Pattern Recognition, V14, 1981, pp. 137-
145.

80

[V18 87] Vistnes R. "Detecting Dotted Lines and Curves in Random-Dot
Patterns", Proceedings of the DARPA Image Understanding
Workshop, V2, 1987, pp. 849-861.

[VOR 08] Voronoi M. G., "Nouvelles Applications des Parametres Con-
tinus a la Theorie des Forrnes Quadratiques. Deuxieme
Memoire. Recherches sur 1es Parallelloedres Primitifs.", Jour-
ncgzlgﬁtg die Reine und Angewandte Mathematik, V134, 1908, pp.
1 -2 7.

[WAR 62] Warshall S., "A Theorem on Boolean Matrices", JACM, V9,
1962, pp. 11-12.

[WER 38] Wertheirner M., Laws of Organization in Perceptual Forms
from a Source Book of Gestalt Psychology, Harcourt Brace and
Jovanovich, 1938.

[ZAH 71] Zahn C. T., "Graph-Theoretical Methods for Detecting and
Describing Gestalt Clusters", IEEE C, V20, 1971, pp. 68-86.