17-12-2012, 05:43 PM
APPLICATIONS OF BEAMLETS TO DETECTION AND EXTRACTION OF LINES, CURVES AND OBJECTS IN VERY NOISY IMAGES
1 Two-scale Relationship.pdf (Size: 90.74 KB / Downloads: 36)
ABSTRACT
Beamlets are a special dyadically organized collection of line segments,
exhibiting a range of lengths, positions and orientations.
This collection is relatively compact: there are O(n2 log2(n))
beamlets, compared to O(n4) line segments. This collection is
relatively expressive: up to a certain tolerance, it does not take
more than O(log2(n)) beamlets to approximate a single line segment.
Because of these two properties, chains of a relatively few
beamlets can build quite general curves. The beamlet pyramid is
a multiscale data structure which stores all the line integrals of the
image over all beamlets. By summing a relatively few coefficients
from the beamlet pyramid, one can obtain integrals of the image
along quite general polygonal curves.
We consider the beamlet pyramid a natural platform on which
to build new methods for detecting linear and curvilinear features
in very noisy data. The general approach is to solve such problems
by adaptively constructing chains of beamlets which extremize
certain integrals over the image. We give examples in the problems
of detecting the presence of line segments in very noisy data;
detecting curves in noisy data; and in the problem of extracting objects
in very noisy data. We are able, in examples, to detect objects
which seem practically invisible to the unaided eye.
INTRODUCTION
Identifying linear and curvilinear image features is a common problem
in applications of image processing. There is an overwhelmingly
large literature on methods of detecting such features, for example
under the name ‘edge detection’, so a comprehensive summary
is beyond hope, but it is possible to make a few generalizations.
Classical ‘edge detectors’ seem to work well when the noise
is nonexistent or weak.
Classical detectors work only at the finest scale of the image
– detecting edges based on behavior of the image in a
sliding window a few pixels wide.
We are interested in a situation where an underlying linear or
curvilinear feature is embedded in a very noisy image. In fact,
we are interested in settings where the pixel signal-to-noise ratio,
computed in a pixel centered on the feature, is very small.
BEAMLETS, A PRIMER
Beamlets provide us an organizational tool which is very useful in
searching for linear and curvilinear structures in image data. There
are five interrelated concepts to: beamlet dictionary, beamlet transform,
beamlet pyramid, fast beamlet transform, and beamlet graph.
Some of these ideas, or near relatives, have appeared before, without
special names or under other names. We mention some prior
literature.
Beamlet Dictionary
Beamlets make up a special subcollection of line segments associated
with an n by n image. They are generated following
three steps: (1) exhaustive dyadic recursive partitioning of the
unit square, (2) marking equispaced vertices along the boundary
of every resulting dyadic subsquare, and (3) connecting all pairs
of vertices within each square by a line segment. A description,
together with a graphical illustration can be found in [5], compare
also [7], where the same collection appeared by a different name.
The line segments that result are called beamlets and the collection
of all such beamlets is the beamlet dictionary. Although there
are O(n4) line segments associated with vertices on an n by n
grid, there are only O(n2 log(n)) beamlets. Nevertheless, it takes
only O(log(n)) beamlets to build an approximation to any line
segment, valid to within one pixel.
Beamlet Transform
The beamlet transform is, loosely speaking, the collection of all
line integrals of the image defined by line segments in the beamlet
dictionary.
More precisely, given a digital image, we first perform a piecewiseconstant
interpolation, creating a function on the continuum which
is constant on each pixel. Then we associate to each given beamlet
a beamlet coefficient defined by integration of the interpolated
function along this beamlet. The beamlet pyramid is the data structure
comprising all such beamlet coefficients.
Two-scale Relationship
Beamlet dictionary obeys a certain 2-scale relationship: each beamlet
at a coarser scale is approximately the union of at most three
beamlets at the next finer scale.
More precisely, consider a dyadic square, the parent, and its
four dyadic children; and consider a beamlet associated with the
parent. We can see by inspection that this coarse-scale beamlet
can be broken into 1, 2, or 3 disjoint line segments associated
to the child dyadic squares which are traversed by the line segment.
Those shorter segments can all be approximated to within
one pixel distance by beamlets associated to the children squares.
Fast Algorithms & Hough Transform
The 2-scale relation we have just mentioned has been discovered
and applied within the context of fast algorithms for Hough transforms
and Radon transforms, see [9, 4, 3]. For example, Goetze
and Druckmiller [9] defined essentially the same data structure
as beamlets (without the beamlet name, and with other applications
in mind) and used a bottom-up recursive algorithm based on
the two scale relationship to approximately calculate all integrals
over lines traversing the image from one boundary pixel corner to
another, in O(n2 log(n)) time. During the execution of this algorithm,
beamlet coefficients are calculated at intermediate steps.
Brandt and Dym [4], without defining specifically the beamlet dictionary,
also pointed out a two scale relationship to calculate approximate
multiscale line integrals of an image over an extensive
collection of line segments in the image.
CURVE DETECTION
In Figure 2, we summarize an experiment in a beamlet-based curve
detection. We embed a very weak signal in a very strong noise.
The signal should be the indicator function of a filament and should
be so weak that, roughly speaking, it is indetectable to the unaided
eye. As one can see, the algorithm we develop is able to recover a
surprisingly accurate reconstruction of the filament.
CONCLUSION
Beamlets provide a conceptual and software toolbox which is wellsuited
to detect linear features in very noisy pictures. We demonstrated
some experiments in the detection of lines, curves, and objects
with regular boundary. We were able to obtain success at
extremely low signal-to-noise ratios. At the conference we hope
to present detailed performance comparisons with existing techniques.