A Review on Graph Based Segmentation <s> A. Regular pyramids <s> Abstract Picture segmentation is expressed as a sequence of decision problems with the framework of a split-and-merge algorithm. First regions of an arbitrary initial segmentation are tested for uniformity and if not uniform they are subdivided into smaller regions, or set aside if their size is below a given threshold. Next regions classified as uniform are subject to a cluster analysis to identify similar types which are merged. At this point there exist reliable estimates of the parameters of the random field of each type of region and they are used to classify some of the remaining small regions. Any regions remaining after this step are considered part of a boundary ambiguity zone. The location of the boundary is estimated then by interpolation between the existing uniform regions. Experimental results on artificial pictures are also included. <s> BIB001 </s> A Review on Graph Based Segmentation <s> A. Regular pyramids <s> The task of segmenting an image and that of estimating properties of image regions may be highly interdependent. The goal of segmentation is to partition the image into regions with more or less homogeneous properties; but the processes which estimate these properties should be confined within individual regions. A cooperative, iterative approach to segmentation and property estimation is defined; the results of each process at a given iteration are used to adjust the other process at the next iteration. A linked pyramid structure provides a framework for this process iteration. This hierarchical structure ensures rapid convergence even with strictly local communication between pyramid nodes. <s> BIB002 </s> A Review on Graph Based Segmentation <s> A. Regular pyramids <s> Abstract Although pyramid segmentation algorithms have been reported to be successful in a large number of fields, some of their basic properties have not been systematically investigated. They were especially used in applications involving compact objects, in which moreover the connectivity of the final segments was of no great importance. We will show that most pyramid segmentation algorithms are shift-, rotation- and scale-variant and hence that the results of a pyramid segmentation are very data-dependent and not reproducible. We will demonstrate that the fundamental reason for this shortcoming is the subsampling introduced in the higher levels of the pyramid. We will also discuss why multi-resolution algorithms in general have a fundamental and inherent difficulty in analyzing elongated objects and ensuring connectivity. Finally, we will discuss the way in which a new pyramid algorithm using irregular tessellations, reduces some of those problems but introduces some new ones. <s> BIB003 </s> A Review on Graph Based Segmentation <s> A. Regular pyramids <s> Pyramid-based image segmentation is a kind of very precise, universal and efficient method. A new image segmentation approach based on this idea is presented. A new way to build a pyramid of an image and a new strategy of identifying the root nodes are developed. In this approach: (1) the Gaussian filter function with changeable filter scales is used to build a pyramid, so as to decrease the loss of the original image information; (2) the relationship among the pixels which are in both level-in and level-between is used to determine the root nodes. The new approach need not know the image information in advance. A satisfactory result can be obtained even in a low signal-to-noise ratio image. <s> BIB004 </s> A Review on Graph Based Segmentation <s> A. Regular pyramids <s> As image segmentation is one of the first steps in image processing, little knowledge about the image content is available. The modified pyramidal linking approach presented here is intended as a low-level process for segmentation without any a priori information or user-defined thresholds. The process works with multiple features which are weighted according to their information content. The number of extracted regions is automatically determined by the process itself. <s> BIB005
In regular pyramids, spatial relationships and the reduction factor, which is defined as the ratio between the number of vertices at level L and the number of vertices at level L+1, are constant and fixed, hence, the size and the layout of the structure of the pyramids are predicable. The first segmentation method based on regular pyramids was proposed by Chen and Pavlidis BIB001 . Ping et al. BIB004 utilized a pyramid built using a Gaussian filter function having adjustable filter scales. Burt et al. BIB002 proposed a pyramid linking approach to attain image segmentation. But the accuracy of this method is sensitive to the right selection of the working level. To overcome this drawback, a modified pyramid linking approach which particularly uses two scaling rules was suggested by Ziliani and Jensen BIB005 . Though this method attempted to improve the pyramid linkage approach, a few drawbacks remain in common to both these approaches. They are: elongated regions are not properly segmented, and the structure of the pyramid varies even due to small rotations, shifts and scales of the input image BIB003 .