The purpose of the research is to use the modified Ward's method in high-speed processing of full-HD images of the remote sensing of the Earth. The classical Ward's method is modified by dividing the computational process into three successive stages. The first stage quickly builds a coarse hierarchy of approximations. The second stage performs a quality improvement of the specified partition for a fixed number of colors (clusters). The third stage is the clustering of the superpixels using the Ward's method. The software-algorithmic toolkit consists of four operations on clusters of pixels and image segments: merge operation joins together two clusters; divide operation reversibly disjoins the selected cluster into two; split operation extracts the part of the cluster into individual cluster; correct operation reclassifies pixels by extracting from one cluster and inserting into another cluster. The quality is assessed by the total squared error. The quality improvement is provided by iterative execution of a combination of merge and divide operations of pixel clusters, in particular image segments. One of the clusters (segments) is divided in two and a pair of other mismatched with it is combined into one according to the criterion of the minimum increment of the total squared error. The proposed modified Ward's method is appropriate in processing of fullHD images of the remote sensing of the Earth. The results of processing in pure segmentation and clustering modes are compared. The proposed pixel clustering model is appropriate in high-speed processing of the full-HD images. The pixel clustering in comparison with image segmentation allows to define in more detail both the contours of objects of interest and their internal structure.
The segmentation task refers to the stage of preliminary processing of the images. It
consists in dividing the image into disjoint areas based on the uniformity of
characteristics (brightness or color of pixels). The segmentation is applicable in many practical
? Publication is supported by RFBR grant 19-07-00844
areas, including remote sensing of the Earth. One of the common approaches to
segmentation of satellite images is based on the use of data clustering algorithms. The paper
[
Image segmentation (pixel clustering in general) consists in dividing the original image into embedded images of “objects” for the purpose of further analysis of attributes and recognition. Filling each embedded image with the same pixels with an average brightness value converts the original image to its approximation. The quality of the partition and the corresponding approximation of an image of N pixels is estimated by the standard deviation of the approximation pixels from the image pixels or the total square error E = 3N 2, where coefficient 3 takes into account the number of color components in the image. At the segmentation, the pixels of each embedded image constitute a single connected segment. At clustering pixels, it is assumed that the embedded image may consist of several or many non-adjacent segments of the original image. The partition and approximation for a given number of pixel clusters, in particular image segments, is considered to be optimal if it corresponds to the minimum possible value of the total squared error E or standard deviation . Then the objects are defined as clusters or segments of the optimal image approximation.
Present paper is devoted to the application of the modification [
The Ward’s [
The Application of the Model of High-Speed Pixel Clustering... 3
presents a classification of threshold image segmentation methods. The complexity of
the Mumford-Shah model is overcome in [
In [
Despite the fact that the Ward’s method returns results of acceptable quality by the total squared error, it is limited in used in image processing due to the high computational complexity.
The following challenging requirements are applied for the modern algorithms of
image segmentation [
2) The presence of the established quality criterion allowing to evaluate the obtained image partition into clusters/segments.
3) The possibility of segmenting the image into each number of colors/clusters from 1 to N , where N is the total number of pixels in the considered image. 4) The real-time processing.
5) The adequacy of the results, consisting in correspondence of the selected segments/clusters to the boundaries and areas of objects in the image.
Most of the above requirements are met by a group of cluster methods. The most
common are Ward’s method [
The difference of the considered cluster methods reveals in the way the image is divided into clusters of pixels or segments. The K-means method divides image pixels into an earlier predetermined and fixed number of clusters. The Otsu method, the Mumford-Shah segmentation model and the Ward’s method generate a set of partitions of the original image from 1 to N , where N is the total number of pixels in the original image. In contrast to Ward’s method that considers all the combinations of pixel clusters, the Mumford-Shah segmentation model considers only pairs of adjacent segments of the image.
The compared methods have different computational complexity and, consequently, possess different possibility of processing images in real time. If the classical Otsu method takes linear time to split pixels into two clusters, then in the general case its computational complexity grows exponentially with an increase of considered number of thresholds. The time taken by the K-means method for the division an image into a fixed number of clusters depends quadratically on the preset value of the number of clusters. The Mumford-Shah model segments the image in nearly real time. The computational complexity of the classical Ward’s method increases quadratically with the rise of the number of the considered clusters of pixels that makes it difficult to apply the method directly to the image processing.
The Ward’s method and the Mumford-Shah segmentation model support a hierarchical data structure. It stores information about the sequence of merges of pixel clusters or image segments, the values of total square errors, the values of the number of pixels and the average intensities for each newly formed pixel cluster or image segment. The hierarchical data structure allows both to perform a “rollback” operation into the past state, as well as to find a new partition characterized by a smaller value of the total squared error.
The classical Ward’s method satisfies most of listed requirements applicable to challenging image segmentation algorithms. But the high computational complexity significantly limits its application in image processing. The considered in further section modification of the classical Ward’s method allows to process images in image segmentation and pixel clustering tasks by means of dividing whole process into three successive stages. 3
Among the methods of cluster analysis applicable in image processing, the classical Ward’s method takes special place. It processes color images and returns adequate results, but the high computational complexity characteristic of the method significantly limits its application. Shown in Fig. 1, the scheme for the high-speed clustering of image pixels overcomes this drawback by dividing the processing process into three typical stages.
The first stage “a” quickly builds a rough hierarchy of connected segments, the
generation of which is available in two different variants. The first variant is to use the
Mumford-Shah model [
The second stage “b” forms N sp superpixels, in fact, performing an improvement
in the quality of a given partition with a fixed number of colors (clusters). For this task,
two basic algorithms have been developed: SI-method (Segmentation Improvement)
[
At the third stage “c”, superpixels are clustered by the Ward’s method [
The Application of the Model of High-Speed Pixel Clustering... 5
The basis of the software and algorithmic toolkit for the high-speed pixel clustering
scheme [
“correct” operation of reclassification of pixels by extraction them from one cluster and assigning them to another cluster
Ecorrect =
kn2 n2 + k kI k kI where I is the average value of reclassified k pixels, and I1, I2 are the average values of pixels of clusters 1 and 2. Criteria for the (5) operation is:
Ecorrect = min < 0:
The first two operations (1), (3) are used to build the hierarchy. A pair of other operations (4), (5) is used in hierarchy transformations.
The combination of “merge÷” operations (1), (3) improves image quality
in the SI-method by dividing one of the segments (numbered 1) and merging the other
two mismatched (numbered 2 and 3). SI-method is executed by the criterion [
At each iteration, a triple of segments is selected that provide the maximum drop in the total squared error, and the process of combined merging/dividion of the adjacent segments continues until three segments are found that satisfy the condition. Otherwise, the processing ends. For applications of the SI-method, it is important that the number of segments in the resulting approximation coincides with the number of segments in the original approximation.
Using the above operations (1), (3), (4), (5) and their combinations [
The application of the high-speed pixel clustering scheme is demonstrated by processing Earth remote sensing images taken from the Signal and Image Processing Institute of the University of Southern California (USC SIPI) database. In Fig. 2 the original image of the planet Earth is shown.
Series of Fig. 3 6 and Fig. 7 10 illustrate pixel clustering and image segmentation. The number of clusters/segments into which the original image is divided, as well as the value of the total squared error characterizing the quality of this partition is noted under each figure. The smaller value of total squared error, the better the quality of the partition. Note that pixel clustering gives a significantly more drop in the value of approximation error than the segmentation procedure. This can be noticed by comparing each subsequent partition of the image.
Fig. 11 shows grayscale aerospace image of the Pentagon. In the series of Fig. 12 15 the details of the building appear more clearly with each subsequent splitting, than in a similar series of segmentations of Fig. 16 19.
The Application of the Model of High-Speed Pixel Clustering... 7
The Table 1 shows the time costs for processing the images presented in the work in various modes: pixel clustering and image segmentation. The first column shows the name of the standard test image from the open USC-SIPI database. The second column indicates the size of the image sides in pixels. All images are square. The third column sets the N sp number of superpixels - the detail parameter, which takes values in the
Pixel clustering, N sp=1000
range from 1 to N the number of pixels in the image in total. When N sp = 1, the
program operates in pure segmentation mode, considering only pairs of adjacent pixels as
in the modified Mumford-Shah model [
The peculiarity of the modified Ward’s method is the bypass of the computational complexity by dividing the process into three sequential stages. It allows to implement the idea of Ward’s method in pixel clustering and image segmentation tasks.
It was established, that pixel clustering in comparison with image segmentation makes it possible to define both the contours of objects of interest and their internal structure in more detail. The time spent on image processing in the clustering mode with a compromise value of the input parameter of the number of superpixels N sp=1000 is close to the time required for image processing in the pure segmentation mode with N sp=1.
The statistical data of image processing is summarized in Table 1.