INTRODUCTION

As the use of digital image information grew rapidly in recent years, it became more important to manage these images efficiently. The need of analysis, retrieval, classifications and knowledge mining from larger numbers of images based their contents, is shared by many groups, including engineers, journalists, librarians, teachers, artists and historians. However, the content in one image is described by its contained objects in different forms under special scenes. So, it is usually necessary to extract objects from background or separate the image into several meaningful regions. Thus, the segmentation of images has always been a key problem in image analysis based contents.

The straightforward segmentation methods are those based expectation maximization (Fwu and Djuric, 1997), k-means methods (Chen et al., 1998) and threshold-based approaches (Xue and Gupta, 1993). However, when these approaches could not achieve accuracy segmentation regions. In recent literatures (Jianbo and Malik, 2000; Comaniciu and Meer, 2002; Chunming et al., 2005; Edward, 1993; Felzenszwalb and Huttenlocher, 2004; Larrabide et al., 2006; Montoya et al., 1999), some more accuracy image segmentation methods have been proposed, i.e., the methods based normalized cuts (Jianbo and Malik, 2000), mean shift clustering (Comaniciu and Meer, 2002), level set (Chunming et al., 2005), watershed (Edward, 1993), graph (Felzenszwalb and Huttenlocher, 2004), topological derivative (Larrabide et al., 2006), region growing (Montoya et al., 1999) and so on. In order to segment the complex images with large numbers of small objects, these image segmentation algorithms will consume much time, which should be avoided as these segmentation results may be unuseful to image content analysis or retrieval. Although the complex images occupy only one small part of image databases, it is essential to avoid segmenting these images. These complex images will be analyzed or retrieved as a whole rather than the segmented regions. Therefore, how to measure the necessity of image segmentation is one problem met in recently research works.

This problem was described by Dai et al. (2006) and Luo et al. (2001), respectively. The complexity of one image is used as the metric of segmentations. Actually, the segmentation complexity of images could be measured by that of any suitable descriptors (Shao et al., 2007), such as color, energy, orientation or phase. Thus, Dai et al. (2006) adopted the wavelet modulus maxima-based complexity indicator (WMMCI) as the metric of image complexity, which is defined as the ratio of the total number of wavelet modulus maxima points to the total number of pixels in one image. The number of wavelet modulus maxima points is essentially the measure of image edge information or acute points and only reveals how much the edge information is in the image as a whole. However, the edge information could not explicitly indicate the implicit regions to be disclosed by image segmentation, as some implicit regions may not contain acute points, e.g., the flat regions. As another image segmentation complexity measure, the Cluster Connectivity Index (CCI) was detailed in literature. On the basis of initial image segmentation by histogram based-multi-threshold approaches, its evaluation is conducted by averaging the connectivity of every pixel according its details in Luo et al. (2001). Nevertheless, just like the WMMCI, the CCI is only the measure of image segmentation complexity as a whole, which could not indicate the necessity of image segmentation. It is the size of implicit regions in one image that also determines the necessity of image segmentation, as we generally use those regions whose sizes in certain size ranges.

So, the necessity of segmentation should be evaluated according to image complexity together with the implicit region sizes. In this paper, we give one Segmentation Necessity Index (SNI) as the metric of segmentation necessity, which is defined as the couple of image complexity and its region sizes. According to the proposed metric, one image is determined to be further segmented if its SNI was lower than the given threshold. It is determined by the minimum implicit object sizes along with the image analysis time requirements. Thus, the RI-based necessity of images can roundly reflect the object analysis requirements and its complexity limitations, while the WMMCI and CCI-based approaches only disclose the complexity of segmentations, which could not avoid those unuseful segmentation results.

When the segmented regions of one image are meaningless to image analysis or one image is essentially indiscriptable, image segmentations should be avoided to save much computation overhead. In Fig. 1, we list 8 images to which image segmentation should be avoided and these images are taken in our school except the one containing peoples. Then their segmentation results are also presented in Fig. 2, where the Graph-based segmentation method as showed in literature (Felzenszwalb and Huttenlocher, 2004) is used to conduct image segmentations. As showed Fig. 2, there are two different representations i.e., one simple dominant region and larger numbers of small regions.

Though the more details of objects in images are disclosed explicitly, the regions from correspondent segmentations may be meaningless to image retrieval or classification. According to the contents of these images, they should not be segmented as they only confer one semantic object and should be dealt with as a whole rather than those segmented meaningless regions. Thus, this puzzle also presents us one challenge to detect those images that refuse to segmentation.

Fig. 1:	Example images to be avoided with segmentation

Fig. 2:	The correspondent segmentation results of those images in Fig. 1

As we known, there are no dedicated literatures to address the question about image segmentation and the problem were only partially involved in references where the segmentation necessity is determined by the given WMMCI or CCI according to their predefined thresholds, respectively. But, the selection of thresholds was not detailed in the two literatures. So, there are still many disclosed problems about segmentation necessity metrics to be worked out. Here, for the sake of preliminary information, we give some simple introductions to the WMMCI and CCI, which one can find more details in literatures by Dai et al. (2006) and Luo et al. (2001), respectively.

Wavelet modulus maxima points: Mallat and Hwang (1992) have proposed the use of wavelet transform modulus maxima for characterization of regularity of signals. By examining the wavelet modulus maxima, they could measure the local Lipschitz exponents of a signal. This turned out to be an effective way to locate the singularity or edges of an image. The points having local maximum of wavelet transform modulus are corresponding to the abrupt change locations in one image and the gradual changes are set to zero. The wavelet modulus maxima can represent the sharply focused edges and the inner texture details of the interest regions in image. Therefore, the wavelet maxima point density of the image is in proportion to the visual complexity of the whole image.

Define the ratio of the total number of wavelet modulus maxima points to the total number of pixels as the complexity indictor C_w of the image. Then, the low threshold C_w-low and high threshold C_w-high are specified to determine the segmentation necessity. If C_w < C_w-low, it shows that the image content is so consistent as not to be segmented, the whole image can be looked as region of interest. If C_w > C_w-high, it shows that the image has too many details to be segmented, the whole image can be looked as region of interest too.

For the example images refused to segmentation in Fig. 1, their corresponding wavelet modulus maxima images are showed in Fig. 3. The crowd image and flowers image having abundant texture details, their wavelet modulus maxima point densities are larger than C_w-high. But for sky images, the densities are smaller than C_w-low, it is difficult to know which region is interest region or background. If these four images were segmented, some meaningful regions would be lost.

Connectivity index: The image complexity is actually related to the cluster connectivity of image pixels according to their color values, so the cluster connectivity is used as the metric of image segmentation in literature by Luo et al. (2001). Thus, the cluster connectivity approaches are based on the pixel cluster of images.

According to the results of reference Luo et al. (2001), a hue histogram based multi-threshold approach is used for image segmentation. It is the most simple way and effective way in many cases, because different objects in practical world usually have different colors. Then, the cluster connectivity index N_k can be defined as:

(1)

Fig. 3:	The wavelet modulus maxima point images of the images in Fig. 1

where, N is the image size and k is the size of the neighborhood area, V_k(x) is the ratio of the same labeled pixels number as the x-th pixel in the neighborhood one considers.

By calculating the connectivity index one can classify the images into different groups according to their complexity. The N_k is bigger if the complexity of the image is low. Then, two thresholds are specified, i.e., N_k-low and N_k-high. We assume that if N_k < N_k-low, the image is too complex for segmentation; if N_k-low < N_k < N_k-high, assume the complexity of the image is average and we do clustering for subsequent image analysis; if N_k > N_k-high, we assume that the image is simple. Thus, the too complex or simple images will be avoided for segmentation.

The two approaches mentioned earlier ignore the implicit region sizes, which could only disclose those regions with acute changes rather than those flat regions. So, we propose another segmentation necessity metric, i.e., the Segmentation Necessity Index (SNI), which can synthetically reflect both the image complexity and the implicit region sizes. The segmentation complexity is actually consistent with the number of implicit regions, while the segmentation necessity is related to the dominant region sizes. Subsequently, we give the definition of SNI with general consideration of image complexity and region sizes.

Definition: Assume the initial segmentation regions can be denoted as {R(i) | iε{1,2,...,K}}, where K is the total region number in one image and the {N(i), iε{1,2,...,K}} is the correspondent region size in terms of pixels. Then, the segmentation regions are sorted in descending order according their sizes and {R(n,i) | n = 1,2,..., K, iε{1,2,...,K}}are the sorted regions, where the size of R(n,i) is larger than that of R(n+1,i). Given a specified region size N(0), the entropy for those regions whose sizes smaller than N(0) is firstly evaluated and then its scaled version by their total percentage in the image is defined as the segmentation necessity index of the image, i.e.,

(2)

where, S_N(0) (K₀) and H_N(0) (K₀) are denoted as the entropy for those regions whose sizes smaller than N(0) and their total percentage in the image, respectively. They are given as followings, i.e.,

(3)

In the formula (2), the parameter N is used to normalize the product of S_N(0) (K₀) and H_N(0) (K₀) according to the image size. The terms of S_N(0) (K₀) and H_N(0) (K₀) actually reflect the significance and the number of those small regions, respectively. As the percentage of every small region is much smaller than one, this results in the strong relations between the value of H_N(0) (K₀) and the number of small regions. The more the number of small regions, the larger the value of H_N(0) (K₀) is and the more segmentation complexity for the image. However, if the small regions only occupy one small part of the image with small S_N(0) (K₀), the value P_s of SNI is shrunk and the image should be further segmentation. Otherwise, the image should refuse to segmentation. Thus, the proposed metric for image segmentation necessity can reflect the requirement of region sizes and complexity.

Threshold: As the WMMCI and CCI, one specified threshold for the SNI must be given in advance to determine segmentation necessity. According to the SNI definition, the threshold is related with the requirement region size N(0), which is the smallest region size that should be retrieved or classification.

In order to give the threshold, let us consider the case, where N(0) is the largest region size in one image segmentation and all other regions are a little smaller than the given largest regions. Thus, the largest region and all other regions are almost equal to each other and the value of (2) can be considered as the critical value to determine whether the given image should refuse to segmentation, i.e., the threshold P_s(N(0)) for segmentation. So, the P_s(N(0)) is evaluated as:

(4)

In the case that N(0) is much smaller than the image size N, the (4) can be approximated as:

(5)

Implementation: In the color image, the Hue-Saturation-Intensity (HSI) color space represents the human concept of color well and it is more suitable for the analysis of color images. Usually, in the HSI color space, intensity is used for texture analysis and the other two components are used to extract the color feature. Here, the saturation can be considered as the importance index of the weight of color information. The higher the saturation, the more reliable the color information is. The perception of color of human eyes mainly comes from the hue component.

For a given color image, one hue histogram based multi-threshold (Xue and Gupta, 1993) is adopted for initial image segmentation to evaluate its segmentation necessity index. The multi-threshold method is the most simple way and effective way in many cases as different objects in practical world usually have different colors. The scheme to determine the segmentation necessity of images could be implemented as showed in Fig. 4. The label regions are conducted by the method given in reference of Haralick and Shapiro (1992), while the multi-threshold of hue-histogram multi-threshold segmentation approaches (Xue and Gupta, 1993) are achieved by detecting the maximum points of hue-histogram after smoothed by Gaussian functions.

Fig. 4:	The flowchart of segmentation necessity

In order to validate the accuracy of image segmentation necessity, an image database with 121 images is constructed, which includes many categories of images, such as flower, sky, horse, dog, vegetable, leafs, grass, automobile, crowd, individual and buildings. According to the semantic content or complexity of images, each image in the database is flagged to indicate whether refuse to segmentation. Then, the proposed segmentation necessity and other approaches are used to check each image whether worthy of segmentation and their evaluated results are compared with the pre-flagged indicators to achieve their verdict accuracies.

Here, the WTMM point density (Mallat and Hwang, 1992), the connectivity index (Dai et al., 2006), the intensity variance based methods and the region size-based schemes (Shao et al., 2007) are used to evaluate the segmentation necessity together with the proposed scheme. The critical thresholds of WTMM point density, intensity variance and connectivity index based approaches, consist of high and low thresholds which are achieved by averaging the corresponding segmentation necessity metrics of 20 typical images that refuse to segmentations. So does the threshold of the region size-based scheme and the thresholds of the proposed scheme for different region sizes are worked out according to formula (5). The Table 1 shows their verdict accuracies, respectively for different approaches, which as the ratio of verdict results consist with the pre-flagged indicators to the total number of images in database. As indicated the numerical results, with different region sizes, the proposed scheme can achieve good accuracy than other schemes and the requirement region sizes has small effect on its accuracy.

Fig. 5:	The curve of segmentation necessity metrics for all the images in the database

Table 1:	The verdict accuracies for different segmentation necessity schemes

Table 2:	Three typical images with low, medium and high values of segmentation necessity metrics

Subsequently, the curve of segmentation necessity metric for all the images in the database is showed in Fig. 5, where the horizontal axis indicates the serial number of images in the database. In order to show the internal relation with the curve in Fig. 5, we check the several typical values with corresponding images in the followings. For the different size values of images with corresponding serial numbers are given in Table 2, where the given region size is 300 pixels. Several images with low, medium and high values of segmentation necessity metrics are also presented in Fig. 6, where the corresponding serial numbers are showed under these images. According to the results indicated in Table 2 and Fig. 6, the SNI values of these images are obviously consistent with their contents in terms of implicit meaningful regions. By this token, the values of curve in Fig. 3 at different location indicate the segmentation necessity of corresponding images and the proposed can describe the segmentation necessity accurately.

When the WTMM point density (Mallat and Hwang, 1992), the connectivity index (Dai et al., 2006), the intensity variance-based methods (Shao et al., 2007) and the region size-based schemes (Shao et al., 2007) are used to verdict the segmentation necessity of image 24 as showed in Fig. 6, their values are 0.27936, 0.84944, 0.21332 and 2243.5, respectively. According to their threshold in Table 2, the image 24 refuses to segmentation. However, its SNI values with 50, 100 region sizes are 5.86 and 6.3439, respectively and the image should avoid segmentation at region size 50 and further be segmented at region size 100. This case displays the adaptation of the proposed scheme with the requirement region sizes.

Fig. 6:	The typical images with different segmentation necessity metrics, where the first, medium and last rows are the those with low, medium and high values, respectively

In order to figure out those images that refuse to segmentation in image analysis, several image complexity metrics were proposed in recent literatures, but they ignore the requirements of implicit region sizes in terms of meaningful region objects. So, a novel segmentation necessity metric is given in this study. As the pretreatment of content-based image analysis, the metric can describe the division degree of images in terms of semantic regions or complexity. According to the values, we could exclude those images with great complexity or without non-implicit regions and a great deal of computation and storage are saved. An image database with many categories is constructed to test the proposed segmentation necessity metric and other common approaches. Experiment results verify that the proposed scheme can achieve more verdict accuracy than other schemes and its results can keep consistent with the semantic segmentation of corresponding images.