A NEW ALGORITHM IMPLEMENTATION FOR IMAGE SEGMENTATION USING JAVA

A NEW ALGORITHM IMPLEMENTATION FOR IMAGE SEGMENTATION USING JAVA

A NEW ALGORITHM IMPLEMENTATION FOR IMAGE SEGMENTATION USING JAVA

Girisha GS1, Dr. K. Udaya Kumar2, Dr. P. Deepa Shenoy3

1Department of Information Science & Engineering,BNM Institute of Technology, Bangalore, India

2Principal, Adarsha Institute of Technology, Bengaluru, Karnataka, India

3Department of Computer Science & Engineering, UVCE, Karnataka, India

Abstract: Accurate Image segmentation has played an important role in computer vision and image analysis. Based on resonance theory an algorithm is proposed for color image segmentation [1]. The resonance algorithm is an unsupervised method to generate the region (feature space) from similar pixels (feature vectors) in an image. It tolerates gradual changes of texture to some extent for image segmentation. This paper presents the resonance algorithm analysis and implementation using java which is always the first step to control a real intelligent control system.

Keywords: Resonance algorithm, Image segmentation, Seed pixel

1 INTRODUCTION

For image analysis, image segmentation is needed, which means to partition an image into several regions that have homogeneous texture or similar feature. This process is usually approached by the region-based, boundary- based or edge- based method [2]. And from the viewpoint of clustering, these methods can be divided into the supervised or unsupervised texture segmentation.

An intelligent control system is difficult to know the feature in the image before recognition, e.g. how many types of textures exist in it. Thus the unsupervised segmentation algorithm is needed, although it is more difficult than the supervised method.

Many image segmentation methods are proposed based on the change of intensity [3, 4]. But they always fail to handle the wide-ranged gradations in intensity. It is usually difficult to give a suitable threshold for pixel-based image processing methods to deal with this gradation.

This paper proposes the image segmentation by the resonance algorithm and implementation. The outline of the paper is as follows. Section 2 is related work. Section 3 is the algorithm for image segmentation. Section 4 shows the architectural design. In Section 5 the experiment and result are given. Section 6 is the conclusion.

.

1. RELATED WORK

   1. Clustering methods

      The K-means algorithm is an iterative technique that is used to partition an image into K clusters. The basic algorithm is:

      1. Pick K cluster centers, either randomly or based on some heuristic

      2. Assign each pixel in the image to the cluster that minimizes the distance between the pixel and the cluster center

      3. Re-compute the cluster centers by averaging all of the pixels in the cluster

      4. Repeat steps 2 and 3 until convergence is attained (e.g. no pixels change clusters)

         In this case, distance is the squared or absolute difference between a pixel and a cluster center. The difference is typically based on pixel color, intensity, texture, and location, or a weighted combination of these factors. K can be selected manually, randomly, or by a heuristic.

         This algorithm is guaranteed to converge, but it may not return the optimal solution. The quality of the solution depends on the initial set of clusters and the value of K.

         In statistics and machine learning, the k-means algorithm is a clustering algorithm to partition n objects into k clusters, where k < n. It is similar to the expectation-maximization algorithm for mixtures of Gaussians in that they both attempt to find the centers of natural clusters in the data.

         The model requires that the object attributes correspond to elements of a vector space. The objective it tries to achieve is to minimize total intra-cluster variance, or, the squared error function. The k-means clustering was invented in 1956.

         The most common form of the algorithm uses an iterative refinement heuristic known as Lloyd's algorithm. Lloyd's algorithm starts by partitioning the input points into k initial sets, either at random or using some heuristic data.

         It then calculates the mean point, or centroid, of each set. It constructs a new partition by associating each point with the closest centroid. Then the centroids are recalculated for the new clusters, and algorithm repeated by alternate application of these two steps until convergence, which is obtained when the points no longer switch clusters (or alternatively centroids are no longer changed).

         Lloyd's algorithm and k-means are often used synonymously, but in reality Lloyd's algorithm is a heuristic for solving the k- means problem, as with certain combinations of starting points and centroids, Lloyd's algorithm can in fact converge to the wrong answer.

         Other variations exist, but Lloyd's algorithm has remained popular, because it converges extremely quickly in practice. In terms of performance the algorithm is not guaranteed to return a global optimum.

         The quality of the final solution depends largely on the initial set of clusters, and may, in practice, be much poorer than the global optimum. Since the algorithm is extremely fast, a common method is to run the algorithm several times and return the best clustering found.

         A drawback of the k-means algorithm is that the number of clusters k is an input parameter. An inappropriate choice of k may yield poor results. The algorithm also assumes that the variance is an appropriate measure of cluster scatter.

   2. Histogram-based methods

      Histogram-based methods are very efficient when compared to other image segmentation methods because they typically require only one pass through the pixels. In this technique, a histogram is computed from all of the pixels in the image, and the peaks and valleys in the histogram are used to locate the clusters in the image [1]. Color or intensity can be used as the measure.

      A refinement of this technique is to recursively apply the histogram-seeking method to clusters in the image in order to divide them into smaller clusters. This is repeated with smaller and smaller clusters until no more clusters are formed [1, 3].

      One disadvantage of the histogram-seeking method is that it may be difficult to identify significant peaks and valleys in the image. In this technique of image classification distance metric and integrated region matching are familiar.

      Histogram-based approaches can also be quickly adapted to occur over multiple frames, while maintaining their single pass efficiency. The histogram can be done in multiple fashions when multiple frames are considered.

      The same approach that is taken with one frame can be applied to multiple, and after the results are merged, peaks and valleys that were previously difficult to identify are more likely to be distinguishable.

      The histogram can also be applied on a per pixel basis where the information results are used to determine the most frequent color for the pixel location. This approach segments based on active objects and a static environment, resulting in a different type of segmentation useful in Video tracking.

   3. Image segmentation and primal sketch

   There have been numerous research works in this area, out of which a few have now reached a state where they can be applied either with interactive manual intervention (usually with application to medical imaging) or fully automatically.

   The following is a brief overview of some of the main research ideas that current approaches are based upon.

   The nesting structure that Witkin described is, however, specific for one-dimensional signals and does not trivially transfer to higher-dimensional images.

   Nevertheless, this general idea has inspired several other authors to investigate coarse-to-fine schemes for image segmentation. Koenderink proposed to study how iso-intensity contours evolve over scales and this approach was investigated in more detail by Lifshitz and Pizer.

   Unfortunately, however, the intensity of image features changes over scales, which implies that it is hard to trace coarse-scale image features to finer scales using iso-intensity information.

   Lindeberg studied the problem of linking local extrema and saddle points over scales, and proposed an image representation called the scale-space primal sketch which makes explicit the relations between structures at different scales, and also makes explicit which image features are stable over large ranges of scale including locally appropriate scales for those.

   Bergholm proposed to detect edges at coarse scales in scale- space and then trace them back to finer scales with manual choice of both the coarse detection scale and the fine localization scale.

   Gauch and Pizer studied the complementary problem of ridges and valleys at multiple scales and developed a tool for interactive image segmentation based on multi-scale watersheds.

   The use of multi-scale watershed with application to the gradient map has also been investigated by Olsen and Nielsen and been carried over to clinical use by Dam Vincken et al. proposed a hyperstack for defining probabilistic relations between image structures at different scales.

   The use of stable image structures over scales has been furthered by Ahuja and his co-workers into a fully automated system.

   A fully automatic brain segmentation algorithm based on closely related ideas of multi-scale watersheds has been presented by Undeman and Lindeberg and been extensively tested in brain databases.

   These ideas for multi-scale image segmentation by linking image structures over scales have also been picked up by Florack and Kuijper. Bijaoui and Rué associate structures detected in scale-space above a minimum noise threshold into an object tree which spans multiple scales and corresponds to a kind of feature in the original signal. Extracted features are accurately reconstructed using an iterative conjugate gradient matrix method.

2. RESONANCE ALGORITHM

   The resonance algorithm emphasizes the similarity between the adjacent points, not the threshold for the global usage. And the resonance can be spread from point to point. Thus the problem caused by gradation in intensity can be solved. Only the sudden change of features between adjacent points can be regarded as the boundary of different regions [1].

   The steps of the resonance algorithm for image segmentation are:

   1. Initialization. R (0).

   2. Segmentation. Find new region R (i).

   3. Termination after having searched all pixels.

   4. Result. R = R (i ) .

   By the resonance theory, the algorithm is driven by three controlling parameters [1]:

   1. One or several seed points,

   2. The features to determine the difference between points,

   3. The parameter of the threshold .

   Figure 3.1 gives the flow chart of the resonance algorithm for image segmentation

   Start

   Initialization and Feature extraction

   Segmentation is finished

   Have Y

   labelled all pixels

   N

   Select adjacent unlabelled pixel

   Belongs to a new region

   Distance Y

   >

   Belongs to current region

   N

   End

   Figure 4.1: Block diagram showing the segmentation procedure

   5. EXPERIMENTAL RESULTS

   The experiments have been implemented in java and a set of color image is taken to perform this experiment. Figure 5.1 shows the results of the algorithm for an image of an outdoor scene. In figures 5.1(a)-(d), we show four images, the image is divided into two parts. The sky is separated into part 1 and Part 2 is the region of hill.

   1. Input Image (b) Grey Scale image

      Figure 3.1: Resonance algorithm

3. IMPLEMENTATION

The block diagram in Figure 4.1 shows the step-by-step process of image segmentation process. We adopt the gray level as the feature. Color images are first converted in to gray color images. In the next step, the seed pixel is selected from the top-left corner of the image. Then segmentation procedure is performed & the result is the segmented image.

(c) Seed Pixel Image (d) Segmented Image

Figure 5.1: Segmentation results

6. CONCLUSION

In this paper, we have developed an unsupervised resonance algorithm for image segmentation, which has the feature to eliminate the influence of gradual changes of texture in intensity to some extent. In this paper, image segmentation is to

search the same or similar texture pixels so as to cluster them into one region: the resonance is spread among all the pixels within the image. The result shows that the resonance algorithm emphasizes the similarity among the adjacent pixels rather than the global threshold values, and the segmentation result is satisfied.

REFERENCES

1. Fengzhi Dai, Yutaka Fujihara Image Segmentation by Resonance Algorithm

2. K. R. Castleman, Digital Image Processing, Original edition published by Prentice Hall, Inc., a Simon & Schuster Company, Press of Tsinghua University, 1998.

3. T. Nakamura, T. Ogasawara, On-line visual learning method for color Image segmentation and object tracking, Proc. of the 1999 IEEE/RSJ International Conf. on Intelligent Robots and Systems, Vol. 1, pp. 222-228, 1999.

4. K. Deguchi, I. Takahashi, Image-based simultaneous control of robot and target object motion by direct-image-interpretation, Proc. of the 1999 IEEE/RSJ International Conf. of Intelligent Robot and System, Vol. 1, pp. 375-380, 1999.

5. Begininng J2EE 1.4 by James L Weaver, Kevin Mukhar and Jim Crume. High Performace MySql by baron Schwartz, Peter Zaitsev.

6. F. Dai, M. Sugisaka, Application of Resonance Algorithm for Image Segmentation, Proc. of the Eighth International Symposium on Artificial Life

   and Robotics, vol. 1, pp. 251-254, 2003.

7. Jähne, Digital Image Processing – Concepts, Algorithms, and Scientific Applications. The Third Edition, Springer-Verlag, 1995.

8. THE COMPLETE REFERENCE JAVA 7TH EDITION BY HERBERT SCHILDT