| Image
Processing Articles
Index |
 |
| Why
Convex Hull? |
| Finding
the convex hull of
a set of points is
the most elementary
interesting problem
in computational geometry,
just as minimum spanning
tree is the most elementary
interesting problem
in graph algorithms.
It arises because
the hull quickly captures
a rough idea of the
shape or extent of
a data set. |
|
| Convex
hull also serves as
a first preprocessing
step to many, if not
most, geometric algorithms.
For example, consider
the problem of finding
the diameter of a
set of points, which
is the pair of points
a maximum distance
apart. The diameter
will always be the
distance between two
points on the convex
hull. The O(n \lg
n). algorithm for
computing diameter
proceeds by first
constructing the convex
hull, then for each
hull vertex finding
which other hull vertex
is farthest away from
it. This so-called
``rotating-calipers''
method can be used
to move efficiently
from one hull vertex
to another. |
|
  |
|
| INPUT
OUTPUT |
|
| What
is convex hull? What
is the convex hull
problem? |
For
a subset 
of  ,
the convex hull  is
defined as the smallest
convex set in containing. |
|
The
convex hull computation
means the ``determination''
of
for a given finite
set of 
points
in.
|
|
| The
usual way to determine
is to represent it
as the intersection
of halfspaces, or
more precisely, as
a set of solutions
to a minimal system
of linear inequalities.
|
|
This
amounts to output
a matrix 
and a vector 
for some 
such that  .
When
is full-dimensional,
each (non redundant)
inequality corresponds
to a facet of .
Thus the convex hull
problem is also known
as the facet enumeration
problem. |
|
Some
people define the
convex hull computation
as the determination
of extreme points
of
, or equivalently
that of redundant
points in
to determine .
This is much simpler
computation than our
convex hull problem.
In fact, this can
be done by solving
linear programs and
thus polynomially
solvable. |
|
| Guidelines
for Use |
| To
illustrate the convex
hull, we start with
a simple image containing
some distinct artificial
objects( specifically
text) |
|
| Now
we apply Grayscale
conversion to the
image to convert it
to Grayscale image. |
|
 |
|
| Now
we apply Grayscale
conversion to the
image to convert it
to Grayscale image. |
|
 |
|
| Now,
we will convert the
image into binary
so only two intensities
will be present in
the image..... Black
and white or in other
words 0 and 1. |
|
 |
|
| After
scanning this image
and labeling the distinct
pixels classes with
a different grayvalue,
we obtain the labeled
output image. |
|
 |
|
| C#
Sample Program: |
The
algorithm is coded
in C# using unsafe
so the quality and
speed of the program
may not be affected.
The class BitmapData
is used to read and
process the pixels
in the image. This
is the speicality
of C# to provide such
a speed even on image
processing applications.
There is a set of
modules that are designed
to implement the algorithm.
The program scans
the image to convert
the image into grayscale
Levels.Then it converts
the image into binary.This
binary image will
be subjected to spliting
it into components.Here
we can use 4-Connected
or 8-Connected Algorithm
but we used 8-Connected
Algorithm for finding
the Blobs in the image
as described above.
The final output is
a colored image showing
separate colors for
every blob.... An
array named objects
of Type Class Objects
contains the sizes
of each blob or object
being segmented and
the object also contains
the convex hulls of
the objects yet obtained... |
|
 |
|
| Please
refer to the article
"RTS Invariant
Moments" for
more information about
the class hierarchy
used here. Here we
discuss the other
used classes. |
|
| CDLL:
This is the doubly
linked list used to
organize the points.
So, the decision is
made whether the point
is included in the
convex hull or not.
Its functionality
is same as that of
the usual Linked lists. |
|
| Point:
A class similar to
the built in Point
class in C#. |
|
| Polysort:
The points are sorted
using this class.. |
|
| Output:
A word file containing
the Convex Hull of
each of the blob so
obtained. |
Download
Project Files
 |
|
| Image
Processing Articles
Index |
