08-11-2016, 11:05 AM
1466589895-cadapaper48reformattedfinal.pdf (Size: 1.07 MB / Downloads: 15)
ABSTRACT
We present a method to extract the contour of geometric objects embedded in binary
digital imagesusing techniques in computational geometry. Rather than directly
dealing with pixels as in traditional contour extraction methods, we processon
objectpointsetextractedfrom the image.The proposed algorithm works in four
phases: point extraction, Euclidean graph construction, point linking and contour
simplification. In point extraction phase, all pixels that represent the object pattern
are extracted as a point set from the input image. We use the colorsegmentation to
distinguish the object pixels from the background pixels. In the second phase, a
geometric graph G=(V,E) is constructed, where V consists of the extracted object
point set and E consists of all possible edges whose Euclidean distance is less than a
threshold parameter, l ; which can be derived from the available information from
the point set. In point linking phase, all border points are connected to generate the
contour using the orientation information inferred from the clockwise turn angle at
each border point. Finally, the extracted contour is simplified using collinearity
check. Experiments on various standard binary images show that the algorithm is
capable of constructing contourswith high accuracy and achieves high compression
ratio in noisy and non-noisy binary images.
INTRODUCTION
The boundary lines of geometric objects embedded within an image is referred to as a contour [15]; see
Fig. 1.In computer vision, contour features are used to identify, localize and analyze objects in digital
images. So, contour extraction from images, particularly images with complex shapes and noise, is a
topic of interest to researchers in the field of computer vision, graphics and pattern recognition.
Contour extractionfinds many applications in different domains.For instance, in the development of
computer aided design (CAD) system for detecting breast cancers, region of interest (ROI)
segmentation is extremely important. In [21], a local binary image along with contour extraction has
been proposed for ROI segmentation from mammogram patches. In automated medical diagnosis,
anatomical abnormalities of internal organs due to tumors or particular syndromes can be determined
by matching the contours of corresponding infected and uninfected body parts (Please see Fig. 2).
Further, contours extracted from binary images of optical coherence tomography (OCT) images are
used for automated OCT segmentation in the clinical diagnosis of coronary arterial lumen [23].
Contours are widely applied in pattern analysis of digital images through feature extraction [14].
Contour consists of a small subset of the pixels representing the geometric objects in digital image and
also shares manyimportant features with the original object pattern. As a consequence,the
computation time will be considerably reduced if the feature extraction algorithms are applied on the
contour rather than on the original pattern [13, 14]. In machine vision, contour detection plays a
significant roleespecially when dealing with the inspection of manufactured parts. Contour extraction
along with matching can be applied in unsupervised inspection of machine parts for geometric irregularity
In applications such as tracking of earth resources, geographical mapping, weather forecasting,
prediction of agricultural crops etc., images transmitted by satellites or remote sensorsare often
contaminated by noisy components [12] (Fig.3 shows an example of satellite image before and after
transmission). Consequently, edge detection or contour extraction in such images poses a great
challenge as the noise can change the contrast along edges, and even lead to local contrast reversals.
Smoothening the image (e.g., with a Gaussian filter [6]) reduces the noise, but it may also weaken the
contrast across the edges and blend adjacent edges [1]. So, a perfect contour detection in a noisy image
using common edge detectors is extremely difficult. This is more evident from Fig.4, which shows the
result of Sobeledge detection [5] algorithm over noisy image. In this paper, we propose a geometrybasedcontour
extraction approach that works well with noisy binary images (seeFig. 4). Further, we
demonstrate the efficiency of the proposed algorithm through various experimental studies on noisy
and non-noisy images.Rest of this paper is organized as follows: In Section 2, wepresent some closely
related work. In Section 3, we discuss the contour extraction algorithm.Section 4 illustrates empirical
studies with results and discussions. Weconclude the paper in section 5.
2 RELATED WORK
Several computational models have been reported in the literature for contour or edge detection in
images. Some of the earlier works include Robert [20], Sobel [5] and Prewitt [17] edge detectors, all of
which use local derivative filters to do the boundary detection. D. Marr et.al [9] exploits intensity changes to detect the edges by finding zero values of Laplacianof Gaussian distribution. Canny edge
detector [4] is one of the well-known edge detection algorithmthat uses sharp discontinuities in the
brightness channel to detect edges.
Contours extracted by geometric algorithms are often found to have high compression ratio and
smooth representation compared to pixel based methods. Despite this fact, very few geometry/graph
based algorithms address contour extraction form digital images. One such algorithm is proposed by
Pedro J. et al. [15], which makes use of geometric techniques such as clustering, linking, and
simplification to find contours in O(n2
logn) time where n is the size of extracted feature points from
the image. Q. Zhu [24] describes a graph based approach for boundary detection in 2D image with
clutters which uses cycle tracing in the output of an external graph cut. There are also some methods
proposed to capture discontinuity in detected edges [19]. For example, X. Ren et al. [19] uses
constrained Delaunay triangulation over the set of contours detected by local edge detectors to remove
gaps and clutters present in the extracted edges.
In general, computational approaches proposed for contour extraction can be classified
depending on whether they do local, regional or global processing [6]. In local processing, adjacent
pixels in the neighbourhood are linked if they satisfy some criteria. Some examples of local contour
tracing algorithms are: square tracing algorithm, Moore-neighbourhood algorithm [22], radial sweep
and bug follower’s algorithm [13, 14, 16]. A recent local approach include multi scale version of Pb
detector[2], where a Pb detector [10] is an edge detection algorithm that predict the posterior
probability of a boundary with a particular orientation at each image pixels by measuring the local
image brightness, colour, and texture channels. In regional methods, starting from a seed point,
regions grow by adding pixels that are previously known to be a part of the same region or contour.
Global processing techniques try to find pixels which lie on curves of specific shapes. However, all
these three traditional methods possess some drawbacks: local methods ignore everything other than
those pixels within the neighbourhood and hence does not take into account the valuable global
information about the geometric proximity of pixels; regional methods needs some prior knowledge
about which pixels lie on which contour; and usage of global processing techniques such as Hough
transform are only applicable to some specific types of shapes [15]. As opposed to this, our approach
exploits the proximity and orientation of points inferred through a threshold length parameter and
turn angle at each boundary pixel, requires no prior knowledge on the regional belongings of pixels
and is not restricted to any specific shape.
3 ALGORITHM
A bi-level image (binary image) is a digital image in which each pixel can have one of 2 values: 0 or 1.
Pixel value 0 is used for denoting background pixels and 1 for denoting object pixels.Our algorithm is
designed to generate closed contours in binary images and uses some simple geometric techniques for
the contour construction. Approach consists of four phases:point extraction, graph construction, point
linking and contour simplification as shown in Fig. 5. In point extraction phases, a set of points that
represent the object pattern in the image, are extracted. Then a geometric graph is constructed on
these extracted points in the second phase. The boundary edges are linked together to construct the
contour in the third phase.Finally, the extracted contour is simplified using collinearity checking.We
use the following few notations while describing the algorithm. Letp1, p2 are two points having
coordinates (x1,y1) and (x2,y2) respectively,then (p1,p2) denotesthe edge connecting points ?1 and ?2 and
d(?1, ?2) denotes the Euclidean distance between points ?1and ?2.
Point Extraction
In image processing, thebasic processingunit is a pixel whereasthe basic processing unit in discrete
geometry is a point. In this step, the algorithm deals with the mapping and extraction of pixels that
represent the object pattern in the given digital image to its corresponding object point set for further
processing. Once the point set is extracted, the problem of contour detection can be reinterpreted as a
geometric problem that deals with theconstruction of the shape border for the pointset in 2D. Since
the inputs to the algorithm are binary digital images that have only two color components, the color
value at each pixel can be exploited to decide on whether it belongs to the object pattern or
background. We employ a color segmentation to extract the object pattern from the image. Let the
image I={F,G} where F={?1,?2,?3…,? } denotes the set of foreground pixels (or object pattern)with color
value c and B={?1,?2,…, ? } denotes the set of background pixels. For each pixel ?=(?, ?) in I, the
algorithm adds a point ?= (?, ?) to P, i.e. the point set P= {?1,?2,…,? } is constructed where ?=?,
0<i<n+1. Fig. 6 shows an example in which the foreground pixels are transformed into a set of points.
Geometric Graph Construction
3.2.1 Graph construction
This step constructs a geometricgraph G= (V, E) from the point setP, where V is the set of all points inP
and E is the set of all edges (?,? ) such that?,? in P and d(?,? ) <threshold value l. The threshold
parameter can be statically defined and provided to the algorithm and hence eliminates the hassles of
parameter tuning for the construction of a connected graph.Static value of threshold parameter can be
derived through a pixel grid based analysis of the image which is presented in Section 3.2.2. In order to
realize the graph, for each point ? in P,algorithm checks the length to all other ? in P, if it is less than
the threshold l, then it adds the edge (?,? ) to E.
Formally, from a point?1in P an edge is created to?, if ? belongs to the interior of a circle centered at
?1 with radius l. In Fig.7(a), an edge is created from ?1 to ?2 and ?3astheybelong to the interior of
circle.Fig. 8(a)and 8(b) show an example point set of bird and its corresponding geometric graph with
appropriate length parameter lrespectively.
(a) (b) ©
Fig.8. Left: Input point set, Middle: Corresponding geometric graph with appropriate value of l,
Right: Contour extracted by our algorithm.
3.2.2 Threshold parameter
Now we analyse the pixel grid of a portion of the image in order to derive the value for threshold
parameter. Consider the mask shown in Fig. 9 which gives the all possible neighbourhoods of a pixel at
position (x, y). Please note that distance between the centres of two adjacent pixels