Zhuo Wu, Xiaohua Wang, Yongwen Shen and Yueting Shi

(School of Information and Electronics, Beijing Institute of Technology, Beijing 100081, China)

Abstract: To segment high-resolution remote sensing images (RSIs) accurately on an object level and meet the precise boundary dividing requirement, an improved superpixel segmentation and region merging algorithm is proposed. Simple linear iterative clustering (SLIC) is widely used because of its advantages in performance and effect; however, it causes over-segmentation, which is very disadvantageous to information extraction. In this proposed method, SLIC is firstly adopted for initial superpixel partition. The second stage follows the iterative merging procedure, which uses a hierarchical clustering algorithm and introduces a local binary pattern (LBP) texture feature operator during the process of merging. The experimental results indicate that the proposed method achieved a good segmentation and region merging performance, and worked effectively on cloud detection preprocessing in high-resolution RSIs with cloud and snow overlap situations.

Key words: superpixel; remote sensing image; region merging; hierarchical clustering

With the rapid development of imaging technology, high-resolution remote sensing images have been widely applied in disaster detection, environmental protection, and resource exploration. However, the presence of clouds in remote sensing images (RSIs) greatly reduces data quality and availability[1]. Therefore, cloud detection is always a challenge in remote sensing image processing and analysis. As a preprocessing step of cloud detection, remote sensing image segmentation plays an indispensable role and has been in continuous development.

In the past few years, a number of discriminative segmentation algorithms have been developed, which can roughly be classified into pixel-based methods and object-based methods. Pixel-based methods extract information by using statistics of single pixels. They may lack accuracy for RSIs, due to their inability of extracting spatial, structural, and texture features of the same object type[2]. Object-based methods that use image objects as basic analysis units have a lot of benefits. They have better incorporation of spatial and contextual information, and are more capable of reducing the variability of within-class spectrum[3].

Currently, one of the popular object-based methods is superpixel algorithms. Superpixel algorithms are methods that group pixels into meaningful atomic regions of different shapes; most of these small regions retain effective information for further image segmentation and generally reserve the boundary information of the object in the image. Superpixel algorithms were first introduced by Ren and Malik[4]. They can be divided into graph-based methods and gradient-ascent-based methods. Representative superpixel segmentation algorithms based on graph theory include the graph-based algorithm[5], the normalized cut (Ncut) algorithm[6], the superpixel lattice algorithm[7], and the entropy rate based algorithm[8]. On the other hand, the gradient-ascent-based algorithms include the watersheds algorithm[9], the meanshift algorithm[10], the quick-shift algorithm[11], the turbopixels algorithm[12], and the simple linear iterative clustering (SLIC) algorithm[13-14].

SLIC, which generates superpixels by clustering color and distance features of pixels, is now the most widely used algorithm because of its attractive advantages, such as short calculation time, less parameter setting, accurate edge covering and compact structure. Nevertheless, there are also some problems when we apply the SLIC algorithm to cloud detection preprocessing in high-resolution remote sensing images. It is difficult to achieve excellent cloud extraction results with SLIC because of its over-segmentation.

As for image merging algorithms,region adjacency graph (RAG)[15]and nearest neighbor graph (NNG)[16]are two main methods to reduce the over-segmentation of SLIC. NNG only records the edges of the merged object and its most similar object, which is different from the RAG method, which needs to retain all its edges. However, it is not easy for them to find a suitable merging threshold because regional information may change a significant amount in an image. Hierarchical clustering[17]is another method, which is commonly used to reduce over-segmentation by iterating the merge of the most similar superpixels. This method is easy to define similarity, has fewer parameters to set, and can provide hierarchical information.

This paper proposes a method to improve the region merging algorithm by using the hierarchical clustering algorithm. On account of lacking texture information constraints during the merge process, local binary pattern(LBP) texture features are considered. Our improved algorithm benefits from simplicity because it has no need for a merging threshold, so it is easier to implement in the real world. A series of simulation experiments were conducted, and the results show that the F1-score of our proposed methods improved over 6%.

1 SLIC Superpixel Segmentation Algorithm

The SLIC algorithm, which generates superpixels by iterative clustering of color and distance features of pixels, was first proposed by Achanta et al. in 2010. Fig.1 is the result of segmentation with the SLIC algorithm. This algorithm has three basic processing steps.

Fig.1 Remote sensing image segmented into superpixels of (approximate) size 300 pixels

G(x,y)=‖I(x+1,y)-I(x-1,y)‖2+
‖I(x,y+1)-I(x,y-1)‖2

(1)

whereI(x,y) is the lab vector corresponding to the pixel at position (x,y), and ‖·‖ is the L2norm.

Second, superpixels are generated by dividing each pixel into its nearest cluster. Unlike the global search clustering algorithms, which calculate the distance between each pixel and all cluster centers, the SLIC algorithm only calculates the distance between cluster centers and pixels in a 2S×2Ssquare neighborhood around the cluster center. In the SLIC algorithm, the distance between the pixel point and the cluster center is defined as

(2)

(3)

(4)

wheredlabis the Euclidean distance in CIELAB color space which is perceptually meaningful for small distances.dxyis the Euclidean space distance.DSis the distance between the pixel and the cluster center,Sis the distance between center points, andmis another input parameter that can be used to control the ratio of the distance between the color distance and the spatial distance, usually taking the value of 10. After all the pixels are assigned to the best matching cluster center, the average labxy vector of all pixels in the superpixel is computed and set as the new center. The process of this step is then iterated until convergence. The cluster centerφof superpixel is re-computed as

(5)

whereGjis the superpixel produced by linear clustering;Njis the number of pixels in this superpixel;Ckis the labxy feature vector of pixelxkinGj.

Finally,the adjacent merging strategy is used to eliminate the isolated superpixels of smaller sizes, which ensures the connectivity and tightness of the final result.

The process of the SLIC algorithm

(1) Set the number of superpixels, initialize cluster centers and fine-tune the cluster centers to the lowest gradient position

(2) repeat

(3) for each cluster center

(4) Assign the best matching pixels from a 2S× 2Ssquare neighborhood around the cluster

center according to the distance measure

(5) end for

(6) Compute new cluster centers and residual errorE

(7) untilEthreshold

(8) Merge small isolated superpixels into the nearest large one

2 Improved Region Merge Algorithm

2.1 Hierarchical clustering algorithm

Fig.2 Process of the hierarchical clustering algorithm

Hierarchical clustering algorithms are a type of clustering algorithm that determines the similarity between data points of each category by calculating the distance between them and all data points. A small distance indicates high similarity. The two closest data points or categories are combined and the process is iterated repeatedly. Fig.2 is a diagram of the hierarchical clustering algorithm.

Fig.3 Segment hierarchy and segment tree

2.2 Improved region merging algorithm

In the region merging algorithms based on hierarchical clustering, there are different kinds of similarity measuring methods, such as color distance and Euclidean distance. When applied to some special scenarios, the hierarchical clustering algorithm fails to get good segmentation performance. As shown in Fig.4a, clouds and snow often overlap in remote sensing images. Since their colors are hard to distinguish from each other, they are often classified into the same category. However, this is not in line with our expected segmentation results. It can be clearly seen from Fig.4b that the measurement method of color distance cannot achieve good segmentation result for the parts of thin clouds and snow overlap. Therefore, an improved method of similarity measurement is proposed. In this method, LBP texture feature is introduced to the similarity measurement which improves the segmentation performance.

Fig.4 Remote sensing image after hierarchical clustering

Local binary pattern (LBP) is an operator originally proposed by T. Ojala, M. Pietikäinen and D. Harwood in 1994. It provides a more applicable way to describe the local texture features of an image. Rotation invariance and gray invariance are great advantages of the LBP operator. In this paper, the improved algorithm adopts the LBP equivalent mode to solve the over-segmentation problem in this application background, which means the cyclic binary number corresponding to an LBP varies from 0 to 1 or from 1 to 0 with at most two jumps. Moreover, the types of binary patterns are greatly reduced without losing any information by this mode, which reduces the dimension of eigenvectors and the impact of high-frequency noise.

In this paper, a simple and efficient histogram measure method, correlation measure, is used to calculate the texture similarity distance between two superpixels. The LBP distance of two superpixels is

(6)

(7)

whereHis the LBP histogram of the superpixel,nis the bins value of histogram, andiandjrepresent adjacent superpixels. The improved similarity measurement is as follows.

(8)

dlbp=d(Hi,Hj)

(9)

Dist=dc+γdlbp

(10)

The process of the improved region merging algorithm

(1) Initialize the number of superpixels and the number of superpixels to be merged

(2) Calculate the LBP characteristic matrix of the image

(3) Apply superpixel segmentation with SLIC algorithm

(4) repeat

(5) Calculate the adjacent superpixels for each superpixel

(6) Merge the two superpixels with the highest similarity, i.e. minimize distance

(7) until The number of superpixels merged reaches the preset value

(8) Enforce connectivity

3 Experimental Result and Analysis

In order to verify the proposed improved region merge algorithm, we conducted experiments on a group of high resolution remote sensing images and some representative test images are shown in Fig.5a. First, the SLIC algorithm is used to pre-segment the images. The initial number of superpixels is set to 300 and the segmentation results are shown in Fig.5b. It shows that the generated superpixels are uniform, compact in size, and clearly delineated in boundary. However, over-segmentation is very apparent, which can seriously affect the detection of clouds later.

For the purpose of comparing and measuring the performance of the improved region merge algorithm, on the basis of the above preliminary segmentation, the algorithm proposed in this paper is compared with the region merging algorithm based on hierarchical clustering. Two groups of different experimental results from merging the 267 regions are shown in Fig.5c and Fig.5d. It can be clearly seen from the experimental results that because the algorithm proposed in this paper introduced LBP texture information into the similarity measurement, clouds and snow with the same color features could be distinguished, and the final segmentation area obtained better reflected the contour of clouds, and the result was also more ideal in the detailed representation of image features.

Fig.5 Segmentation and region merging resultsfor different backgrounds

We use the classical performance evaluation indices recall and precision to evaluate the segmentation performance to further verify the effectiveness of the proposed algorithm. The definitions of recall and precision are

(11)

(12)

whereRis recall,Pis precision, TP is true positives, FN is false negatives, and FP is false positives.

The high recall and precision indicate a good segmentation effect. However, there is generally an inverse relationship between recall and precision, so these two measures can be combined together as a single F1-score, which is

(13)

whereFis F1-score,Ris recall,Pis precision,

The three segmentation indices of the image segmentation results are shown in Tab.1. The improved algorithm has a higher F1-score, which means the algorithm we proposed has better segmentation accuracy and precision.

Tab.1 Numerical evaluation measures of the segmentation results using different methods

4 Conclusion

In this paper, an improved region merging algorithm based on hierarchical clustering and SLIC is proposed. On account of lacking texture information constraints during the merge process, LBP texture features are considered. Our improved algorithm benefits from simplicity because it has no need for a merging threshold, so it is easier to implement in the real world. The experimental results show that the proposed method achieved good segmentation and region merging performance, and worked effectively on cloud detection preprocessing in the high-resolution remote sensing images with cloud and snow overlap situations.