Abstract: In MRF based unsupervised segmentation, the MRF model parameters are typically estimated. Those global statistics are far from accurate for local areas if the image is highly non-stationary and hence will generate false boundaries. This study mainly deals with an image segmentation using Hough transformation method. The proposed method is an improvement of building a hierarchical representation of the image content and allows various region features and even domain knowledge to be incorporated in the segmentation process. The algorithm has been successfully tested on several artificial images.

INTRODUCTION

Image segmentation is the process of segmenting an image into several disjoint regions whose characteristics such as intensity, color and texture, etc. are similar. It is a key step in early vision problem and it has been widely investigated in the field of image processing. A large number of segmentation techniques are available in the literature. But there does not exist a general algorithm that can excellently perform the segmentation task even for all light intensity images which is the most common type.

Available segmentation techniques include thresholding, region growing, clustering, classifier, neural network-based approaches, deformable models, MRF model based a1 pproaches. Thresholding does not take into account the spatial characters of an image. This makes it sensitive to noise. The primary disadvantage of region growing is that it requires manual interaction to obtain the seed point. Clustering algorithms do not require training data but they do require an initial segmentation. Classifier methods are pattern recognition techniques to partition a feature space derived from the image using data with known labels.

The methodology of using MRF models to the problem of segmentation has emerged later and has created a lot of interest. Markov random fields have been and are increasing being used to model a prior beliefs about the continuity of image features such as region labels, textures, edges and so on (Lu and Jiang, 2001). The main disadvantage of MRF-based methods is that the objective function associated with most nontrivial MRF problems is extremely non-convex and as such the minimization problem is computationally very taxing. To reduce the computational burden, some approaches based on multi resolution techniques have been reported (Sarkar et al., 2000). The essence of MRF frame work on multi-resolution is that it starts processing images at a coarse resolution and then progressively refines them to finer resolution.

In this study, the researchers use Hough transformation method which is an improvement over the other techniques. The existing method was used for improved image segmentation. Segmentations of images having larger floe sizes are also investigated. However, such a tendency is not obvious for other methods as those pixel-based methods typically locate local minima and are less sensitive to the correctness of the prior model. The existing method is deterministic and the merging step is not reversible. Fast speed is achieved at the expense of accuracy. More accurate results may be obtained with the incorporation of a region splitting process.

Review of basic system: The image segmentation method is characterized by two aspects. First, it uses Graduated Increased Edge Penalty (GIEP) functions within the traditional Markov Random Field (MRF) context model in formulating the objective functions. Second, Hough transform technique in searching for the solutions to these objective functions.

More generally, the MRF can be defined on irregular graphs rather than the regular image lattice. This allows the image segmentation problem to be based on a set of interconnected groups of pixels (referred to here as regions) with the MRF spatial context model based on a Region Adjacency Graph (RAG) (Boykov et al., 2001). Here, the labeling is not on single pixels but on regions where the regions are commonly obtained by a deliberate over segmentation. Each node in the RAG represents aregion and a link between the nodes represents the existence of a common boundary between the regions. Defined on the RAG, the MRF models the behaviors of the regions in a similar way as for pixel.

Graduated Increased Edge Penalty (GIEP): This study focuses on one aspect of the proposed method using a sequence of edge penalty functions to approximate the MRF spatial context model. This aspect alone provides a basis for a novel segmentation method and it will be referred to as the Graduated Increase Edge Penalty (GIEP). The GIEP has two attractive features. First, it utilizes edge information to improve the segmentation on non-stationary situations. Second, it provides a simple and elegant method of simultaneously estimating model parameters and searching solutions for the MRF-based formulation.

The MRF spatial context model functions as a penalty for the existence of boundary site pairs. Instead of penalizing equally for all boundary site pairs, a greater penalty can be applied to weak edge and a lesser penalty to strong edge so that local statistic such as edge strength can be incorporated. Therefore, the penalty term can be replaced with some monotonically decreasing function g (.) of the strength of the edge between the two neighboring sites astride the boundary.

The edge penalty function g (.) can be any monotonically decreasing function so that the greater the edge strength is the smaller the penalty. Suppose the edge strength for ∇_st any boundary site pair s and t has been normalized to (0, 1). Then, the penalty function can be formulated as:

(1)

The parameter K defines how fast the edge penalty decays with the increase of edge strength. As K increases, the penalty difference between weak and strong edges decreases. When K approaches infinity, all edge penalties are equally 1.

Hough transformation: In this study, the researchers extend the GIEP method in a hierarchical manner, leading to the proposed method. Many researchers have applied the MRF model on a hierarchical structure of pixels instead of single pixels (Bouman and Shapiro, 1994; Kato et al., 1996; Laferte et al., 2000; Wilson and Li, 2002) since, pixel-based methods are either easily trapped in local minima or extremely slow in convergence. However, the fixed hierarchical structure in those approaches does not allow efficient descriptions of the underlying image contents and may produce undesirable artifacts. There are a number of studys that construct data-adaptive structures using graph cuts (Barbu and Zhu, 2005; Boykov et al., 2001) or region growing (Wesolkowski and Fieguth, 2004) techniques. The sequence of objective functions described in the preceding section are introduced naturally as the merging criteria corresponding to various scales and here, a simple region growing technique is used to construct the hierarchical data-adaptive structures of the image for optimization purposes.

MATERIALS AND MATHODS

The limit of the multiple-seed approach is to let every pixel be a seed. If two adjacent pixels are similar, merge them into a single region. If two adjacent regions are collectively similar enough, merge them likewise. This collective similarity is usually based on comparing the statistics of each region. Eventually, this method will converge when no further such merging are possible.

Parameter space algorithm: Consider n points in an image and we want to find out the subsets of each point and that lie on a straight line. Consider a point (x, y) that lie in a straight line, the slope intercept form y = ax+b. By varying the values of a and b this equation can also be written as b = -xa+y. The ab plane yields the equation of a single line. Likewise an another point (x’, y’) that also lie in the plane (a’, b’) where a’ is the slope and b’ is the intercept point of both the lines (Fig. 1). If the entire region is coherent (i.e., if all pixels in the region have sufficient similarity), leave it unmodified. If the region is not sufficiently coherent, split it into four quadrants and recursively apply these steps to each new region.

Fig. 1:	Parameter space

Parameter plane: For the calculation of Hough transform the parameter space is divided in to cells. The cell at co-ordinates (i, j) with the value A (i, j) corresponds to the square associated with the parameter space co-ordinates (a_i, b_j). Initially these cells are set at zero.Then for every point in the image plane, the parameter a subdivided in to values according to the equation b = -xa+y. The a axis is subdivided in to k values with n image points this method involves nk computations. A problem with using the equation y = ax+b to represent this line the slope approaches infinity and the line approaches the vertical. So the image is merged into a single block and which blocks can be split into smaller blocks based on the difference between the maximum and minimum intensities in each block. If the max-min difference of a block is close to the max-min difference of its neighbors (i.e., difference between blocks is within the threshold) then the blocks are merged into a single block. A block is split in half if the max-min difference of the block exceeds the threshold. The general algorithm for Hough transform is as follows (Fig. 2):

Basic Algorithm for Hough transformation
Algorithm:

Fig. 2:	Parameter plane

Algorithm for Hough transformation concept
Algorithm:

The Hough transformation algorithm allows us to modify only regions form a partition of a domain to be segmented. Thus avoiding modification of the regions created by previous segmentation algorithms. Hough transformation is done by examining properties of each block and merging them with adjacent blocks that satisfy some criteria. We used one of two criteria. One criteria is to look at the max-min difference and combine adjacent regions whose max-min difference is within a tolerance of the seed block’s. The new region is now the seed and the process is repeated, examining adjacent regions, comparing max-min differences and adding blocks that are within the tolerance specified by user. This tolerance does not have to be the same as the threshold used in the Hough transform algorithm. Alternatively, the mean values of the blocks can be used to determine which blocks should be merged.

RESULTS AND DISCUSSION

The existing region growing method that was used gave good results in segmentation. Yet, it has some disadvantages such as algorithmic speed and the accuracy that matters a lot. Hence the results of the Hough transformation are being done. In which the latter gave good results in the accuracy of the segmentation. The comparison is being done by varying the threshold values and then comparing them. The compared results are as shown below among which proposed approach gave a better result when compared to that of the existing approach. Figure 3-5 shows the segmentation of the image using Hough transform. The threshold is being varied every time. The images are being tested with the threshold values 2, 8, 16. We have achieved better results in segmentation, each time as the threshold value is increased.

Fig. 3:	Hough transformation with threshold = 2

Fig. 4:	Hough transformation with threshold = 8

Fig. 5:	Hough transformation results with threshold = 16

Figure 6 shows the image segmentation using the Hough transformation method here the threshold value is being kept as 16. When compared with the existing method gave better and accurate results. The segmentation results are of the images are analyzed and compared. The segmentation done using the Hough transform gave good result.

Fig. 6:	Hough transformation with threshold = 16

CONCLUSION

The Hough transformation algorithm due to its use of criteria based on the difference between the maximum and minimum pixel values within the region tends to act like an edge detection algorithm. In smooth (no noise or textures) and low gradient images, edges are the only areas where large differences in pixel values tend to occur. As a result near edges, the algorithm tends to split blocks down to individual pixels. Larger merged blocks appear in the interiors. So for this class of images, Hough transformation is an effective first stage in segmentation and region growing can take place faster.

For images with complex sub regions, fine detail, patterns and gradients such as the plane with a max-min criteria does not buy you that much. Too low threshold creates too many small pixel size regions. Too high threshold creates too many large blocky regions. Unfortunately it also results in blocking of the final image. On the other hand, Hough transformation generated images with blurry edges.