Gravel Image Auto-Segmentation Based on an Improved Normalized Cuts Algorithm ()
1. Introduction
Sedimentology requires standardization of the size and shape of gravel. Whether the size of gravel can be effectively identified is closely related to the efficiency of grain-size distribution research. Establishment of outdoor laboratory consumes manpower and material resources [1] - [7] . Grain-size measurement methods based on photographic images have been proposed by many researchers [2] [3] [4] [6] [8] [9] [10] . These methods have greatly improved the efficiency of grain-size measurement. However, lack of the accuracy of measurement is also the question of many methods.
In recent years, many effective methods have been proposed. To circumvent the problem of the more laborious fieldwork, a refined automated grain sizing method is proposed for automatic extraction of grain-size distribution based on digital photographs taken from a river-bed [11] [12] . In succession, a new automated image-processing algorithm can identify sand grains in digital images acquired with a standard digital camera without any extra hardware attached to it [13] .
The normalized cuts of digital image method have high accuracy in image segmentation [14] . The idea of the method is to treat a picture as a graph, calculate the weighted graph, and divide it into regions with the same characteristics (texture, color, lightness, etc.) [15] . The main focus of this study is to apply normalized cuts to extract the grain-size data and improve it. An automated normalized cuts method is proposed to extract the grain-size data from gravel-bed.
2. Methodology
2.1. The Normalized Cuts Framework
Normalized cut criterion is an unsupervised image segmentation technique proposed by Shi and Malik. It does not need initialization and has three main characteristics [15] : 1) it transforms the problem of image segmentation into the problem of graph partition; 2) it is a global criterion; 3) it maximizes the dissimilarity between different groups and similarity within the same group.
A weighted undirected graph,
, can be divided into two unconnected point sets A and B by deleting some edges, so that
,
. The degree of dissimilarity between the two parts can be defined as the sum of the weights of all edges that were deleted from the original edges two parts. In graph theory, it is called
[15] :
(1)
where
is the weight of the edges of connection point
and point
, and it represents the degree of similarity between the two points.
The optimal dichotomy of a graph is to minimize the value of
. To overcome this disadvantage, Shi and Malik proposed a new measure of dissimilarity between different groups, i.e. normalized cut:
(2)
where
is the total connection from nodes in A to all the nodes in the graph, likewise
.
can be rewritten as:
(3)
Let
,
is a symmetric matrix of
, and
. The global optimal value problem can be simplified to:
(4)
And
Since
is a real vector, the above equation is optimized by solving the generalized eigenvalue system:
(5)
It was proved that the second smallest eigenvector of this system is the real valued solution to the normalized cuts problem. The solutions based on higher eigenvectors become unreliable. One key problem of the application of the presented method is the feature selection and the computation of weights for graph setting. As it was mentioned earlier, color/intensity and texture features can be used for evaluating the image regions. Intensities, color, spatial proximity and DOG (Difference of Gaussians) were suggested for texture characterization. In this work we derive texture features from the orientation histograms of each scale level. The weights of the graph are obtained by taking into account those obtained at higher scale levels.
2.2. The Weights Defining
We define the edge weight
between node
and
as the product of a feature similarity term and spatial location term.
(6)
where
is the spatial location of node
, and here
is the feature vector based on color at that node defined as:
(7)
where
,
,
are the HSV values, and the color parameters in this model are: hue (H), saturation (S), Value (V).
2.3. The Normalized Cuts for Gravel Segmentation
According to the characteristics of gravel image, we can estimate the number of gravels in the image. Getting a line from the gravel image, let
be the gray
value of a line and
be the position,
is the rate of change of
and
indicates the acceleration of the change of pixel value, shown as Equation (2) and Equation (3). A specific example is shown in Figure 1.
(8)
(9)
Figure 1. The distribution regular of pixel ((a) gray image, (b) pixel value of gray image, (c) the rate of change of pixel value, (d) the acceleration of change of pixel value)).
For the image of the compactly distributed gravel, the gray value of the edge of the gravel changes faster as shown in Figure 2(d). Remarkable edge features of gravel facilitate accurate statistics of the length of gravel intercepted.
The algorithm may intercept any position of the gravel. It may be an edge part, its length close to zero. It may be a positive center and its length can represent the length of the gravel. The interception length obtained by statistics is related to the longest length of gravel measurement, but they cannot be equated. Let
be the interception length obtained by statistics,
be the number of statistics and
be the estimated value of grain-size,
can be obtained by
, as
(10)
where
is the correlation coefficient between
and the mean of
.
Traditional normalized cuts need to manually adjust the related parameters. To get better initial segmentation effect, it automatically calculates related parameters through the size of the grain-size estimated by previous work. The following steps are described for the specific implementation of automatic Ncut:
1) Consider image as an undirected graph
and construct a Pixel Similarity Matrix (PSM). As stated before, each element of the PSM is the weight of edge
and is calculated by Equation (6).
2) Solve Equation (5) for the Eigenvectors with the smallest Eigen values.
3) Use the Eigen vector with the second smallest Eigen value to bipartition the image by finding the splitting points such that its Ncut value is minimized.
4) Recursively re-partition the segments (go to step i).
5) Exit, if Ncut value for segment is over some specified threshold
.
In this process, we can determine
by the estimated particle size:
where
is the width of the gravel image,
is the height of the gravel image,
is the shape coefficient of the gravel and
is the estimated value of grain-size.
3. Experimental Results and Analysis
In order to verify the effectiveness of the improved Ncut algorithm proposed in this paper. MATLAB software is used to simulate, and the size of the image in the simulation is 512 × 384. Images of gravel in different environments were captured and used in experiments to demonstrate the effectiveness of our algorithm. Compared with other algorithms, a class of gravel image is selected for processing.
3.1. The Results of Processing Different Kinds of Gravel Images
To show the effectiveness of our method, six types of gravel images are used in experiments, as shown in Figure 2. The corresponding results are shown in Figure 3. Without debugging of corresponding parameters, the effect of image segmentation is remarkable. The gravel image with clear edge texture and simple structure obtains pretty good results that segmentation close to the edge of gravel and there is few over-segmentation (Figures 3(a)-(d)). Even for complex gravel images, the effect is not bad that segmentation is not comprehensive and there is some over-segmentation (Figure 3(e) and Figure 3(f)).
3.2. The Results of Different Methods
In order to verify the effectiveness of the proposed method, we do experiments on a large number of different types of gravel images. It’s compared with Marker Controlled Watershed (MCW) [16] , Grain size measurement based on edge image (GSME) [13] and SLIC [17] in this paper. We chose an image for experiment and comparison (Figure 4). The experimental results as shown in Figure 5.
Figure 3. The segmentation results of gravel images by using our method.
Figure 5. The segmentation results by using different methods, (a) MCW, (b) GSME, (c) SLIC, (d) our method.
We should be clear that the edge is not accurate in the result of MCW, as shown in Figure 5(a). GSME can only get the edges that are not closed. It is difficult to measure. The result of SLIC looks good. However, there are some cases of over-segmentation and under-segmentation in the results. It is not difficult to find that our method performs well in this respect. The cases of over-segmentation and under-segmentation decreased so much.
4. Conclusion
Image segmentation plays an important role in quantitative research on the grain size distributions which is of great significance to geology, hydraulics and ecology. Some of the current methods have great improvement in saving time and measurement which moves one step toward the efficiency and automation of various research fields. The study in this paper has made great improvements in many respects, especially in accuracy of edge segmentation and automation. However, when the Ncut algorithm is used to solve the matrix, the computational complexity is complex. Many ways can be used to solve this problem. Combining Mean-Shift and Ncut, it shortens the processing time. Tradeoff between accuracy and time consumption is a problem we need to be concerned about.
Acknowledgements
We are grateful to anonymous reviewers for their constructive reviews on the manuscript, and the editors for carefully revising the manuscript. This research is financially supported by Hubei Provincial Department of Education (No. Q20181310) and Open Fund of Key Laboratory of Exploration Technologies for Oil and Gas Resources (Yangtze University), Ministry of Education (No. K2018-21). The supports are gratefully acknowledged.