International Journal of Scientific & Engineering Research, Volume 3, Issue 10, October-2012 1

ISSN 2229-5518

Image Classification Using Segmentation Graph


Athira Devi C P,Arya Venugopal

AbstractIntroducing a multiregion graph cut image partitioning through kernel mapping of the image data. The proposed func- tional contains two terms: an original kernel-induced term which evaluates the deviation of the mapped image data within each region from the piecewise constant model and a regularization term expressed as a function of the region indices. Using a com- mon kernel function, the objective functional minimization is carried out by iterations of two consecutive steps: 1) minimization with respect to the image segmentation by graph cuts 2) minimization with respect to the regions parameters via fixed point computation

Index TermsGraph cuts,Pixel label,Segmentation,Graph kernels,Pixel ratio,Optimization,Region parameters

—————————— ——————————


An image is an array, or a matrix, of square pixels (picture el- ements) arranged in columns and rows. In a (8-bit) grayscale image each picture element has an assigned intensity that ranges from 0 to 255. A grey scale image is what people nor- mally call a black and white image, but the name emphasizes that such an image will also include many shades of grey.
A normal grayscale image has 8 bit colour depth =
256 grayscales. A “true colour” image has 24 bit colour depth =
8 x 8 x 8 bits = 256 x 256 x 256 colours = ~16 million colours.
Some grayscale images have more grayscales, for instance 16 bit = 65536 grayscales. In principle three grayscale images can be combined to form an image with 281,474,976,710,656 gray- scales.
When you open the document, select “Page Layout”
from the “View” menu in the menu bar (View | Page Layout), which allows you to see the footnotes. Then type over sections of the document or cut and paste from another document and There are two general groups of ‘images’: vector graphics (or line art) and bitmaps (pixel-based or ‘images’). Some of the most common file formats are:
GIF — an 8-bit (256 colour), non-destructively compressed
bitmap format. Mostly used for web. Has several sub- standards one of which is the animated GIF.
JPEG — a very efficient (i.e. much information per byte) de- structively compressed 24 bit (16 million colours) bitmap for- mat. Widely used, especially for web and Internet (bandwidth-
PS — Postscript, a standard vector format. Has numerous sub- standards and can be difficult to transport across platforms and operating systems.
PSD – a dedicated Photoshop format that keeps all the infor- mation in an image including all the layers. For science com- munication, the two main colour spaces are RGB and CMYK. The RGB colour model relates very closely to the way we per- ceive colour with the r, g and b receptors in our retinas. RGB uses additive colour mixing and is the basic colour model used in television or any other medium that projects colour with light. It is the basic colour model used in computers and for web graphics, but it cannot be used for print production.
The secondary colours of RGB – cyan, magenta, and yellow – are formed by mixing two of the primary colours (red, green or blue) and excluding the third colour. Red and green com- bine to make yellow, green and blue to make cyan, and blue and red form magenta. The combination of red, green, and blue in full intensity makes white. In Photoshop using the “screen” mode for the different layers in an image will make the intensities mix together according to the additive colour mixing model. This is analogous to stacking slide images on top of each other and shining light through them.


TIFF — the standard 24 bit publication bitmap format. Com- presses non-destructively with, for instance, Lempel-Ziv-


Athira Devi C P is currently pursuing Mtech in computer science and engineering in Adi Shankara Institute of Engineering and Technology , Kalady,Kerala,India.PH-919562825960 E-mail:

Arya Venugopal is currently pursuing Mtech in computer science and engineering in Adi Shankara Institute of Engineering and Technology , Kalady,Kerala,India E-mail:

Welch (LZW) compression.
The 4-colour CMYK model used in printing lays down over- lapping layers of varying percentages of transparent cyan (C), magenta (M) and yellow (Y) inks. In addition a layer of black (K) ink can be added. The CMYK model uses the subtractive colour model.
The range, or gamut, of human colour perception is quite large. The two colour spaces discussed here span only a frac- tion of the colours we can see. Furthermore the two spaces do

IJSER © 2012

International Journal of Scientific & Engineering Research, Volume 3, Issue 10, October-2012 2

ISSN 2229-5518

not have the same gamut, meaning that converting from one
colour space to the other may cause problems for colours in the outer regions of the gamuts.
Astronomical images
Images of astronomical objects are usually taken with elec- tronic detectors such as a CCD (Charge Coupled Device). Sim- ilar detectors are found in normal digital cameras. Telescope images are nearly always grayscale, but nevertheless contain some colour information. An astronomical image may be tak- en through a colour filter. Different detectors and telescopes also usually have different sensitivities to different colours (wavelengths).
Filters can either be broad-band (Wide) or narrow-band (Nar- row). A broad-band filter lets a wide range of colours through, for instance the entire green or red area of the spectrum. A narrow-band filter typically only lets a small wavelength span through, thus effectively restricting the transmitted radiation to that coming from a given atomic transition, allowing as- tronomers to investigate individual atomic processes in the object.
Natural colour images
It is possible to create colour images that are close to “true- colour” if three wide band exposures exist, and if the filters are close to the r, g and b receptors in our eyes. Images that approximate what a fictitious space traveler would see if he or she actually travelled to the object are called “natural colour ” images. To make a natural colour image the order of the col- ours assigned to the different exposures should be in “chro- matic order”, i.e. the lowest wavelength should be given a blue hue, the middle wavelength a green hue and the highest wavelength should be red.
Representative colour images
If one or more of the images in a data set is taken through a
filter that allows radiation that lies outside the human vision span to pass i.e. it records radiation invisible to us, it is of course not possible to make a natural colour image. But it is still possible to make a colour image that shows important information about the object. This type of image is called a representative colour image. Normally one would assign col- ours to these exposures in chromatic order with blue assigned to the shortest wavelength, and red to the longest. In this way it is possible to make colour images from electromagnetic ra- diation far from the human vision area, for example x-rays.
Stretch function
One particularly important aspect of image processing is the choice of the best stretch function. A logarithmic representa-
tion of the pixel values tends to suppress the bright parts of
the image, i.e. the stars, and to enhance the fainter part, e.g. nebulosity. This can be desirable if the ‘faint stuff’ needs ‘a boost’, but a logarithmic stretch function can also reduce the contrast in an image, producing a lower dynamic range.

1.1 Problem Definition

The purpose of multiregional image segmentation is to divide an image into regions answering a given descrip- tion.Continuous formulations view images as continuous functions over a continuous domain.Unsupervised graph cut methods, which do not require user intervention, have used the piecewise model, or its Gaussian generalization, because the data term can be written in the form required by the graph cut algorithm.Graph cut image segmentation commonly stated as a maximum a posteriori (MAP) estimation problemIntro- duce the kernel-induced data term in the graph cut segmenta- tion functional. It also gives functional optimization equations and the ensuing algorithm.

1.2 Existing System

In existing system the parameter learning and the segmenta- tion process are only loosely coupled in the sense that they do not result from the objective function optimization. Interactive graph cut methods have used models more general than the Gaussian by adding a process to learn the region parameters at any step of the graph cut segmentation process. These pa- rameters become part of the data at each step. However, the parameter learning and the segmentation process are only loosely coupled in the sense that they do not result from the objective function optimization.

1.3 Drawbacks of Existing System

The idea of matching graphs for the purpose of image classifi- cation has a long history in computer vision. However, the general graph matching problem is especially hard as most of the simple operations which are simple on strings (such as matching and edit distances) are NP-hard for general undi- rected graphs. While exact graph matching is unrealistic in our context, inexact graph matching is NP-hard and sub graph matching is NP-complete. Hence most work so far has focused on finding ingenious approximate solutions to this challeng- ing problem. An interesting line of research consists in over- coming graph matching problems by projecting graphs on strings by the so-called seriation procedure, and then use string edit distance as a proxy to graph edit distance. So to avoid these hardness problems kernels can be used for image classification. In this paper tree walk kernels are used for seg- mentation.

1.4 Proposed System

Investigation of multiregional graph cut image segmentation in a kernel-induced space. The proposed method consists of minimizing a functional containing an original data term

IJSER © 2012

International Journal of Scientific & Engineering Research, Volume 3, Issue 10, October-2012 3

ISSN 2229-5518

which references the image data transformed via a kernel
function. The optimization algorithm iterated two consecutive steps: 1.graph cut optimization 2.fixed point iterations for up- dating the regions parameters. A quantitative and comparative performance study over a very large number of experiments on synthetic images illustrated the flexibility and effectiveness of the proposed method. The purpose of segmentation is to divide an image into regions answering a given description. Existing systems have focused on variational formulations because they result in the most effective algorithms. Variation- al formulations seek an image partition which minimizes an objective functional containing terms that embed descriptions of its regions and their boundaries. The literature abounds of both continuous and discrete formulations. Minimization by graph cuts of objective functionals with a piecewise constant data term produce nearly global optima and, therefore, are less sensitive to initialization. In our proposed system we aim the following two main steps,
1) Minimization with respect to the image segmentation by
graph cuts.
2) Minimization with respect to the regions parameters via fixed point computation.

1.5 Objective

Use a common kernel function, and to verify the effectiveness of the method by a quantitative and comparative performance evaluation over a large number of experiments on synthetic images and to improve the segmentation accuracy and flexibil- ity


Normalized Cuts and Image Segmentation [1] proposed a novel approach for solving the perceptual grouping problem in vision. Rather than focusing on local features and their con- sistencies in the image data, the approach aims at extracting the global impression of an image. Image segmentation is a graph partitioning problem and proposes a novel global crite- rion, the normalized cut, for segmenting the graph. The nor- malized cut criterion measures both the total dissimilarity be- tween the different groups as well as the total similarity within the groups. This shows an efficient computational technique based on a generalized eigenvalue problem that can be used to optimize this criterion. This approach is applied for segment- ing static images, as well as motion sequences, and found the results to be very encouraging.
A grouping algorithm based on the view that perceptual
grouping should be a process that aims to extract global im- pressions of a scene and provides a hierarchical description of it. By treating the grouping problem as a graph partitioning problem, here proposed the normalized cut criteria for seg- menting the graph. Normalized cut is an unbiased measure of disassociation between subgroups of a graph and it has the nice property that minimizing normalized cut leads directly to
maximizing the normalized association, which is an unbiased
measure for total association within the subgroups. In finding an efficient algorithm for computing the minimum normalized cut, a generalized eigenvalue system provides a real valued solution to the problem. A computational method based on this idea has been developed and applied to segmentation of brightness, color, and texture images. Results of experiments on real and synthetic images are very encouraging and illus- trate that the normalized cut criterion does indeed satisfy our initial goal of extracting the big picture of a scene.
Fast Approximate Minimization by energy efficient graph Cuts [2] Many tasks in computer vision involve assigning a label (such as disparity) to every pixel. A common constraint is that the labels should vary smoothly almost everywhere while preserving sharp discontinuities that may exist, e.g., at object boundaries. These tasks are naturally stated in terms of energy minimization. In this paper, a wide class of energies with vari- ous smoothness constraints is considered. Global minimiza- tion of these energy functions is NP-hard even in the simplest discontinuity-preserving case. Therefore, the focus is on effi- cient approximation algorithms. This presents two algorithms based on graph cuts that efficiently find a local minimum with respect to two types of large moves, namely expansion moves and swap moves. These moves can simultaneously change the labels of arbitrarily large sets of pixels. In contrast, many standard algorithms (including simulated annealing) use small moves where only one pixel changes its label at a time. The expansion algorithm finds a labeling within a known fac- tor of the global minimum, while the swap algorithm handles more general energy functions. Both of these algorithms allow important cases of discontinuity preserving energies. The ap- proach for image restoration, stereo and motion was effective and achieved about 98 percent accuracy.
Here considered a wide class of energy functions with various discontinuity preserving smoothness constraints. While it is NP-hard to compute the exact minimum, developed two algo- rithms based on graph cuts that efficiently find a local mini- mum with respect to two large moves, namely, -expansion moves and --swap moves. Our –expansion algorithm finds a labeling within a known factor of the global minimum, while our --swap algorithm handles more general energy functions. The combinatorial optimization techniques, such as graph cuts, will prove to be powerful tools for solving many com- puter vision problems.
An Experimental comparison of Min-cut /Max-Flow Algo-
rithms for Energy minimization in Vision [3] emerged as an increasingly useful tool for exact or approximate energy min- imization in low-level vision. The combinatorial optimization literature provides many min-cut/max-flow algorithms with different polynomial time complexity. Their practical efficien- cy, however, has to date been studied mainly outside the scope of computer vision. The goal of this paper is to provide an

IJSER © 2012

International Journal of Scientific & Engineering Research, Volume 3, Issue 10, October-2012 4

ISSN 2229-5518

experimental comparison of the efficiency of min-cut/max
flow algorithms for applications in vision. Here compared the running times of several standard algorithms, as well as a new algorithm that has been developed recently. The algorithm studied includes both Goldberg-Tarjan style “push-relabel” methods and algorithms based on Ford- Fulkerson style “augmenting paths.” We benchmark these algorithms on a number of typical graphs in the contexts of image restoration, stereo, and segmentation. In many cases, the new algorithm works several times faster than any of the other methods, making near real-time performance possible. An implementa- tion of our max-flow/min-cut algorithm is available upon re- quest for research purposes.
Here a test is done on reasonable sample of typical vision
graphs. In most examples, the new min-cut/max-flow algo- rithm worked 2-5 times faster than any of the other methods, including the push-relabel and the Dinic algorithms (which are known to outperform other min-cut/max-flow techniques). In some cases, the new algorithm made possible near real-time performance of the corresponding applications. More specifi- cally, it can be concluded that our algorithm is consistently several times faster (than the second best method) in all appli- cations where graphs are 2D grids.
Multiregion Level-Set segmentation of Synthetic Aperture Ra- dar Images[4] investigate Synthetic Aperture Radar (SAR) im- age segmentation into a given but arbitrary number of gamma homogeneous regions via active contours and level sets. The segmentation of SAR images is a difficult problem due to the presence of speckle which can be modeled as strong, multipli- cative noise. The proposed algorithm consists of evolving simple closed planar curves within an explicit correspondence between the interiors of curves and regions of segmentation to minimize a criterion containing a term of conformity of data to a speckle model of noise and a term of regularization. Results are shown on both synthetic and real images. Presented a curve evolution algorithm for segmenting synthetic aperture radar (SAR) image into a fixed but arbitrary number of Gam- ma-homogeneous regions. This algorithm consists in evolving curves in order to minimize a statistical criterion. This led to partitions of the image domain following an explicit corre- spondence between segmentation regions and regions en-
noise, blurred edges and topology changes and the advantages
of graph cuts vis-a-vis global optimization and speed. The main objective in this paper is to extend our previous ap- proach to segment n classes. The results show that our algo- rithm outperforms the multiphase image segmentation ap- proach and also the segmentation algorithm is very robust to noise and topology changes and it can detect triple junctions because it maintains all the advantages of the level set formu- lation. The algorithms also have the advantages of graph cut optimization, and hence it is very fast and insensitive to initial- ization.

3 Segmentation graph kernals

3.1 Implicit mapping of image data into high dimensional feature(kernel) space

map the image data to a predetermined very high- dimensional space via a kernel function

Find the hyper plane that maximizes the margin between the two regions

If data are not separable find the hyper plane that maximizes the margin.

3.2 Application of piecewise constant model

Find the regions and the constant values inside the re- gions for the segmentation. Set the constant values as minimi- zation variables. Solving image segmentation in a kernel- induced space with graph cuts consists of finding the labeling which minimizes the following function and measures kernel- induced non Euclidean distances between the observations and the regions parameters (1)

3.3 Evaluate the deviation of the mapped image data within each region from the piecewise constant model by an origi- nal kernel-induced term and express the regularization term as a function of the region indices.

Use the following kernel function, where “ .” is the dot
product in the feature space.
closed by evolving curves. The algorithm was illustrated on
both synthetic and real SAR images. The proposed technique

K(y,z)= ( y) T. ( z) ,

( y, z)  I 2 (2)

can be improved by introducing a way to estimate the number of regions and can be extended to other representations of SAR images such as vector valued polar metric SAR images.
Graph cut based active contour for multiphase image Segmen- tation [5] presents a unified framework that unifies two basic segmentation approaches; level set methods and graph cut algorithms. A bimodal image segmentation approach have the advantages of the level set methods such as robustness to
After substituting the kernel functions we got a non- Euclidean distance measure in the original data space corre- sponding to the squared norm in the feature space. Simplifica- tion yields kernel induced segmentation functional term.

3.4 Minimization of objective function by using a RBF ker- nel function

RBF kernel function is defined as

IJSER © 2012

International Journal of Scientific & Engineering Research, Volume 3, Issue 10, October-2012 5

ISSN 2229-5518


y z

2 2) (3)

The RBF kernel has been prevalent in pattern data clustering.
With this kernel, the necessary condition for a minimum of the segmentation functional, with respect to region parameter by the following fixed point equation

µKRkk)=0, k L (4)

3.5 Minimization with respect to the regions parameters via fixed point computation.

This step consists of fixing the labeling (or the image partition) and optimizing with respect to statistical regions parameters via fixed point computation.

3.6 Minimization with respect to the image segmentation by

graph cuts.

This step consists of finding the optimal label- ing/partition of the image, given region parameters provided by the previous step, via graph cut iterations. The algorithm iterates these two steps until convergence. A cut is a set of edges the removal of which separates the terminals into two induced subgraphs.This cut is minimal in the sense that none of its subsets separates the terminals into the same two sub graphs. The minimum cut problem consists of finding the cut, in a given graph, with the lowest cost.


4.1 Test data collection

Since the project deals with image classification, many standard images are used for preprocessing, kernalizing and for clustering. The images from Berkley Dataset are used for classification.

4.2 Testing Parameters:

 Segmentation time
 Pixel label
 Pixel count

5 Results

Fig:1 shows the results obtained on the basis of tree walk ker- nels. A maximum of 250 pixels can only be grouped

Fig 2:shows the pixel label and count along with the width and height of segmented image

IJSER © 2012

International Journal of Scientific & Engineering Research, Volume 3, Issue 10, October-2012 6

ISSN 2229-5518

segmentation via maximum-likelihood approximation and efficient multiphase level-sets,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 28, no. 9, pp.1493–1500, Sep. 2006.
[3] Y. G. Leclerc, “Constructing simple stable descriptions for
image partitioning,” Int. J. Comput. Vis., vol. 3, no. 1, pp. 73–102,


[4] M. Girolami, “Mercer kernel based clustering in feature space,” IEEE Trans. Neural Netw., vol. 13, no. 3, pp. 780–784, May


[5] P. Felzenszwalb and D. Huttenlocher, “Efficient graph- based image segmentation,” Int. J. Comput. Vis., vol. 59, pp.

167–181, 2004.

Fig 3:shows the results obtained through the proposed ap- proach. It classifies around 10,000 pixels by a single label


We can change the kernel function in such a way to improve the optimization process. Another new extension to this work would be to evaluate the improvement of using our segmenta- tion algorithm as a first step in medical analysis such as tumor detection

6 References

[1] Jianbo Shi and Jitendra Malik, “Normalized Cuts and Im- age Segmentation,” in IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 22, NO.
8, AUGUST 2000.
[2] Yuri Boykov,Olga Veksler and Ramin Zabih,” Fast Ap-
proximate Energy Minimization via Graph Cuts,” Computer Science Department Cornell University Ithaca, NY 14853. [3]Yuri Boykov and Vladimir Kolmogorov,” An Experimental Comparison of Min-Cut/Max-Flow Algorithms for Energy Minimization in Vision,” in IEEE Transactions on PAMI, Vol.
26, No. 9, pp. 1124-1137, Sept. 2004.

[4] Michael Ying Yang,” MULTIREGION LEVEL-SET SEG- MENTATION OF SYNTHETIC APERTURE RADAR IMAG- ES,” Department of Photogrammetry, University of Bonn,

53115 Bonn, Germany.

[5] El-Zehiry, N.Y. Univ. of Louisville, Louisville, KY Elma-

ghraby, A. ,”A graph cut based active contour for multiphase image segmentation,”
[1] Y. Boykov and M.-P. Jolly, “Interactive graph cuts for opti- mal boundary and region segmentation of objects in N-D im- ages,” in Proc. IEEE Int. Conf. Comput. Vis., 2001, pp. 105–112.
[2] I. B. Ayed, A. Mitiche, and Z. Belhadj, “Polarimetric image

IJSER © 2012