Accelerated multi-hillshade hierarchic clustering for automatic lineament extraction

A lineament is a mappable, simple, or composite linear feature of a surface whose parts are aligned in a rectilinear or slightly curvilinear relationship and which differs distinctly from the patterns of adjacent features and presumably reflects a subsurface phenomenon. Discontinuity in a geological structure, a mountain ridge, rock boundaries, sedimentary layers, wetness, vegetation changes, and many more can form a lineament (see O’Leary et al. 1976). In the field of lineament extraction from digital images, the lineament is seen as a line or a linear formation that is in strong contrast to background pixels (Soto-Pinto et al. 2013; Hashim et al. 2013). The lineaments are beneficial for both application and research areas. The landslide hazard assessment, monitoring of seismic and volcanic activities, and natural resource exploration are examples of application use (Ramli et al. 2010; Mallast et al. 2011). Geological faults comprise an exciting and important subject of study in geosciences; therefore, identifying the linear patterns of geological fault structures becomes an important task (Panagiotakis and Kokinou 2014). In geomorphological research, lineaments can be considered as an expression of morphotectonic fields, which allows for studying temporal changes of tectonic actions on land surface (Minár and Sládek 2009) or understanding of the genetic and spatial relationships of fracture systems (Seleem 2013).

Lineament extraction is a method producing line segments as results. Due to the fuzzy character of lineaments, the input data are usually multiple line segments with some inaccuracy which generally means that several similar line segments represent one lineament. The human eye easily recognizes these objects, but computer identification is not trivial (see Fig. 1).

The extraction of lineaments is often done manually. The disadvantage of the manual approach is its subjectivity—the user’s opinion influences the result. What is more, manual extraction is time-consuming. Therefore, semi-automatic and automatic approaches have been developed. A step often used in non-manual solutions is the spatial clustering of line segments. It is a method that groups line segments based on their length, slope, and position similarity. A representative line segment of each cluster is picked as a lineament. The spatial clustering enables more data input files to process, thus providing results of higher quality; however, time consumption might be too high.

An automatic representative method of this type is the multi-hillshade hierarchic clustering (MHHC) (Silhavy et al. 2016), which is artifact-resistant, robust, and provides similar results as manual extraction; however, it is relatively slow. Incorporating a more sophisticated computer science approach may bring a substantial acceleration while keeping good properties of the original method. And this is the main focus of this paper. We concentrate on the clustering step, incorporating a facility-location-based approach. The resulting algorithm, accelerated multi-hillshade hierarchic clustering for automatic lineament extraction (AMHHC), is faster than the original while keeping its required lineament-extraction behavior.

The paper is structured as follows. Section 2 covers state of the art. Sections 3 and 4 are devoted to the facility location problem and the original multi-hillshade hierarchic clustering algorithm, which are fundamentals for the proposed solution. The description of the newly developed approach follows in Sect. 5. Results, experiments, and comparison are in Sect. 6. Section 7 concludes the paper.

Clustering is a widely used principle in computer science (see Dubes and Jain 1980 for a survey). It is a process of grouping similar elements into so-called clusters, while elements from different clusters must be as dissimilar as possible (Likas et al. 2003). The input data to be clustered are usually spatial points, but images, patterns, or geometrical objects are also possible. Their suitable representation for clustering is the points in \(D\)-dimensional space, represented by its \(D\) spatial coordinates. The definition of similarity is crucial and is measured with a distance function, a metric. In the simplest case, the Euclidean distance is used. Many metrics (or quasi-metrics) for special clustering tasks have been developed, such as Mahalanobis metrics for detecting hyper-ellipsoidal clusters (Mao and Jain 1996), Itakura-Saito distance for vector quantization in speech processing (Linde et al. 1980), L1 distance for pattern recognition (Kashima et al. 2008) or Bregman distances used in machine learning (Banerjee et al. 2005).

The clustering problem is classified as NP-hard, so the algorithms produce only approximate results. The quality of the approximation is counterbalanced with the time of computation. Clustering techniques are applied in many areas, such as data analyses (Dubes and Jain 1980), pattern recognition (Baraldi and Blonda 1999), image processing (Jain and Flynn 1996), information retrieval (Rasmussen 1992), marketing (Russell and Lodwick 1999) or biology (Legendre and Legendre 2012).

Clustering methods can be subdivided into several ways. The taxonomy survey of clustering can be found in (Jain and Dubes 1988).

K-means (MacQueen et al. 1967) and DBSCAN (density-based spatial clustering of applications with noise, Ester et al. 1996) are well-known partitioning (i.e., non-hierarchical) algorithms. K-means is used for its simplicity and performance and is supported by many computing libraries. The most significant disadvantage of K-means is that the number of clusters must be defined before the algorithm starts.

DBSCAN works well for connected regions of sufficiently high density; otherwise, the data are marked as noise. For the DBSCAN use, two parameters \(\varepsilon\) and MinSample must be defined; \(\varepsilon\) specifies the maximum allowable distance of points from the cluster center. The cluster is formed at the point if at least MinSample points are at a maximal distance \(\varepsilon\) from this point. In order to improve the DBSCAN time complexity \(\mathcal {O}(N^2)\), it is necessary to involve spatial index structures, such as \(R^*\) tree (Beckmann et al. 1990), kd-tree (Bentley 1975) or at least a grid, then time complexity \(\mathcal {O}(N log N)\) can be achieved. The algorithm does not work well for the variable density of input points.

Revisions of existing studies proposing lineament extraction using line segment clustering are as follows. Mallast et al. (2011) used a singularization of identical results from two automatic extraction algorithms to improve the accuracy of the lineament map. The whole process was made using GIS analysis but without any automation. The method in Jordan and Schott (2005) processed eight different input files to produce eight lineament maps that were overlaid, and the line replicates were manually eliminated.

Other authors (Abdullah et al. 2010; Seleem 2013) work with multiple input files to extract lineaments; they merge the input data to obtain one result.

More references to other methods in the lineament extraction area, such as (Vaz 2011), (Masoud and Koike 2011), and (Soto-Pinto et al. 2013), can be found in (Silhavy et al. 2016). Let us briefly present at least some, namely those which have appeared since the publication of the mentioned paper.

Bonetto et al. (2015) detect linear features on a DTM utilizing algorithms based on principal curvature values. Then, the features are grouped according to data collected from the literature review regarding the expected orientation of lineaments in the studied area.

The paper by Thiele et al. (2017) describes a novel least-cost path method that can “follow” structure traces and lithological contacts between user-defined control points in both 2D gridded datasets (photographs, geophysical imagery, etc.) and dense 3D point clouds (virtual outcrop models). The method is suitable for computer-assisted digitizing structural traces in the point cloud, image, and raster datasets.

Vasuki et al. (2017) is an interactive image segmentation algorithm that harnesses the geologist’s input and exploits automated image analysis to provide a practical tool for lithology boundary detection, using photographic images of rock surfaces. The user is expected to draw rough markings to indicate the locations of different geological units in the image. Image segmentation is performed by segmenting regions based on their homogeneity in color.

Adiri et al. (2017) compares ASTER, Landsat-8, and Sentinel 1 data sensors in automatic lineament extraction, combining image data with pre-existing geological maps, the digital elevation model (DEM), and the ground truth.

Karimi and Karimi (2017) extracts line segments from the image, and cluster analysis is based on (Silhavy et al. 2016) with some smaller differences.

Msaddek et al. (2019), a semi-automatic extraction of lineaments using satellite imagery of Landsat-8 OLI (Operational Land Imager) and digital elevation model of SRTM (Shuttle Radar Topography Mission) is presented. The developed algorithm used for this purpose combines STA (segment tracing algorithm), ALEGHT (automatic lineament extraction by generalized Hough transform) and AERA (alluvial effect reducing algorithm).

Yeomans et al. (2019) presented two complementary but stand-alone OBIA methods for lineament detection (top-down and bottom-up), which both enable semi-automatic regional lineament mapping.

In the work by Mohammadpour et al. (2020), the CANNY algorithm was first employed as an edge-detector filter. Later, Hough transform was used to extract linear features from satellite imagery and geophysical magnetometry data.

The paper by Xu et al. (2020) uses wavelet modulus maximum transformation to detect the edges with four scales on Landsat-8 OLI B5 image and analyzes their multi-scale characteristics. The incomplete lineaments are extracted using the 2D Otsu algorithm. Secondly, the hillshade map generated based on DEM is processed to generate a binarized linear shadow superimposed on the lineaments preliminarily extracted to obtain the optimized lineaments.

The study presented in Salui (2018) provides a decision on using a reliable method and data source for automated lineament extraction.

The following papers are more oriented to software than to the used method: The paper by Masoud and Koike (2017) describes the LINDA tool (LINeament Detection and Analysis), a software developed in Visual Basic, which automates processes of detection and analysis of linear features from grid data of topography (digital elevation model, DEM), gravity and magnetic surfaces, as well as data from remote sensing imagery. NetworkGT (Nyberg et al. 2018) is an open-source toolbox for ArcGIS capable of efficient sampling, analysis, and spatial mapping of geometric and topological attributes of two-dimensional fracture networks. The toolbox helps to extract and plot geometric and topological information from a given two-dimensional fracture network, including rose diagrams, frequency distribution plots and topology, and maps of topological parameters. The paper by Rahnama and Gloaguen (2014) and its later continuation provide a MATLAB-based toolbox TecLines (Tectonic Lineament Analysis) for locating and quantifying lineament patterns using satellite data and digital elevation models.

The algorithm TRACLUS based on a partition-and-group framework presented in Lee et al. (2007) was developed for clustering trajectories, the problem slightly similar to the lineament extraction. The algorithm contains two phases, trajectory partitioning, and line segment clustering. The clustering part is based on the DBSCAN algorithm; therefore, it does not produce good clustering results for data sets with significant differences in densities since the MinSample-\(\varepsilon\) combination cannot then be chosen appropriately for all clusters or easily determined before clustering (the algorithm uses a heuristic to set the parameters properly). For satisfactory results, the algorithm requires connected regions of sufficiently high density; otherwise, the data are marked as noise. Therefore, while working well for trajectories, the algorithm is unsuitable for the lineaments problem.

The first algorithm for automatic clustering in the lineament extraction problem, called multi-hillshade hierarchic clustering (MHHC), was done by Silhavy et al. (2016). The algorithm clusters lineaments to singularize results from multiple different input files. The algorithm provides good results; however, it is relatively slow. Therefore, this paper proposes a modification called accelerated multi-hillshade hierarchic clustering (AMHHC), which preserves the MHHC’s good properties and is faster. The acceleration is achieved by more efficient line segment clustering, understood as an instance of the facility location problem, solved by local search.

The following two sections cover the Local Search algorithm and MHHC as two fundamental sources of the proposed solution.

The clustering used in the proposed algorithm is based on the facility location problem solution. Let us describe the essence of facility location before proceeding to a more formal definition.

Let us have a set of points (sometimes called clients) and a set of facilities (usually also points, sometimes chosen from the set of clients). The task is to attach each particular point to one facility so that some evaluation function is optimized. A typical evaluation function is the sum of the distances of the points from their facilities to be minimized.

The problem is too difficult to find the global optimum, so local techniques and various heuristics are used. For example, first, some initial solution is generated and then is tried to be optimized by local reassignments of the points between facilities, the so-called local search (Korupolu et al. 1998; Charikar and Guha 1999).

The more formal description of the facility location as solved by the local search is as follows (Skála and Kolingerová 2011).

Let \(F= \{\varvec{f}_i, i= 1, 2, \ldots , K\}\) be a set of facilities and \(C= \{\varvec{c}_j, j= 1, 2, \ldots , N\}\) be a set of clients—the points to be allocated to facilities. A new facility \(\varvec{f}_{\varvec{c}_j}\) can be opened at the client \(\varvec{c}_j\), but a facility cost \(t_{\rm{\rm{cost}}}\) has to be paid for opening a new facility. The goal is to minimize the overall clustering cost \(Q\), defined aswhere \(d(\varvec{c}_j,\varvec{f}_i)\) is the distance between a point \(\varvec{c}_j\in C\) and its facility \(\varvec{f}_i\in F\), measured by a metrics.

A high value of the facility cost brings a low number of large clusters and vice versa.

First, a coarse initial solution is found (Meyerson 2001). The first client is taken as a facility; the other clients are then taken in random order. A point \(\varvec{c}_j\) is connected to the closest already open facility \(\varvec{f}_i\) based on the distance \(d(\varvec{c}_j, \varvec{f}_i)\). A new facility \(\varvec{f}_{\varvec{c}_j}\) is opened at the point \(\varvec{c}_j\) if \(d(\varvec{c}_j, \varvec{f}_i) > t_{\rm{cost}}\). Otherwise, it is opened with probability \(d(\varvec{c}_j, \varvec{f}_i)/t_{\rm{cost}}\). This initial coarse solution is improved by further iterations of the following local search step.

The local search step randomly selects a point \(\varvec{c}_p\in C\). For \(\varvec{c}_p\) it is computed whether a new facility \(\varvec{f}_{\varvec{c}_p}\) if opened here could improve the current solution (if \(\varvec{f}_{\varvec{c}_p}\) does not exist, a facility cost \(t_{\rm{cost}}\) would have to be paid for its opening). The points closer to \(\varvec{f}_{\varvec{c}_p}\) than to their current facility can be reassigned. Due to this reassignment, some facilities may become too small and be closed to spare their facility costs.

A possible improvement to the current solution by declaring the point \(\varvec{c}_p\) a new facility \(\varvec{f}_{\varvec{c}_p}\) and reassigning all near points from their facilities to \(\varvec{f}_{\varvec{c}_p}\) is measured by a gain function according to the following relation:where \(t_{\rm{cost}}\) is the facility cost (zero if the facility \(\varvec{f}_{\varvec{c}_p}\) is already open), \(ds_j\) is the distance spared by reassigning the client \(\varvec{c}_j\) from its current facility to the facility candidate \(\varvec{f}_{\varvec{c}_p}\), \(sp_i\) (close spare) is the facility cost minus expenses for reassigning all remaining points from their current facility \(\varvec{f}_i\) to \(\varvec{f}_{\varvec{c}_p}\).

If the current facility \(\varvec{f}_i\) lies closer to \(c_{j}\) than \(\varvec{f}_{\varvec{c}_p}\), then \(ds_j< 0\) and \(ds_j\) are set to zero. Similarly, if \(sp_i< 0\) (facility \(\varvec{f}_i\) has enough points and, therefore, no spare can be achieved by its closure and reassigning all its points to the new facility \(\varvec{f}_{\varvec{c}_p}\)), then \(sp_i\) is set to zero.

If \(\text{gain}(p) > 0\), the facility \(\varvec{f}_{\varvec{c}_p}\) at the point \(\varvec{c}_p\) is opened (if not already open), and reassignments and closures are performed.

The number of iterations of the local search step needed to come to a good clustering solution is at least \(\mathcal {O}(N log N)\) (Charikar and Guha 1999).

Advantages of the facility location/local search use for lineaments in comparison with DBSCAN are the possibility to cluster regardless of the density of the area, no need to build a space index to run fast, and the possibility to distinguish line segments with substantially different angles without joining them into one lineament.

In the following section, the line clustering in the original MHHC is described. More details can be found in Silhavy et al. (2016).

The goal is to group the input line segments into clusters and then filter clusters of small size and compute a representative line segment for each cluster. This representative line segment has the length, orientation, and spatial position calculated as the average from the line segments forming the same cluster. The average line segment is the required lineament, and the resulting set of average line segments is the required output set of extracted lineaments, the algorithm’s goal.

Let us have a set \(L\) of line segments \(\varvec{l}_j, j= 1,2, \ldots N\), where \(\varvec{l}_j\) is described by the following vector:where \(X_j, Y_j\) are coordinates of the start vertex of the line segment, \(\alpha _j\) is the angle between the line segment and the positive x-axis (azimuth) and \(\lambda _j\) is the length of the line segment.

The method needs four user-given parameters. The minimum number of line segments that are allowed to form a cluster is denoted as count threshold (\(\xi _{\rm{cnt}}\)), the maximum angle between line segments in a cluster is called the azimuth threshold (\(\xi _{az}\)) and the minimal and maximal allowed size of the so-called buffer zone is \(bfs_{\rm{max}}\) and \(bfs_{\rm{min}}\), respectively. The parameters are explained below, with proper values in Sect. 6.

The process is shown in more detail in Algorithm 1. The first step (Alg.1, line 1) is the filtration of the input line segments to reduce the amount of processed data. The filtration is based on a grid approach. The line dataset is inserted into a grid, and each line segment increments a counter in the (even partially) covered cell. A higher counter value in the grid cell indicates more line segments in the same cell. The algorithm deletes all the line segments which cover the area with the average cell counter value lower than the given count threshold parameter \(\xi _{\rm{cnt}}\).

Then all remaining line segments are sorted according to their length decreasingly (line 2). The main part of the algorithm processes them one by one in this order (line 4). In each round (lines 5-14), the longest non-processed line segment \(\varvec{l}_j\) is selected to form a cluster, and all near line segments are tried to be attached to this cluster (lines 6-7). To choose the line segments belonging to the currently formed cluster, a buffer zone is introduced as a maximally allowed space surrounding the selected line segment \(\varvec{l}_j\). In other words, the buffer zone determines a minimum distance between two line segments of adjacent clusters. This buffer zone decides which line segment is close enough to be inserted into the cluster. The size of the buffer zone \(bfs\) is computed as:where \(\lambda _j\) is the length of the current investigated line segment \(\varvec{l}_j\). In other words, the buffer zone becomes bigger according to the length of the line segment concerning the minimal \(bfs_{\rm{min}}\) and the maximal \(bfs_{\rm{max}}\) distance.

A line segment is inserted into the current cluster only if its azimuth is similar to the azimuth of the longest line segment in the cluster (the limits of similarity are given by the user parameter azimuth threshold \(\xi _{az}\), line 8).

If the cluster formed this way contains enough line segments (the required number is given by \(\xi _{\rm{cnt}}\), line 9), it is saved (line 10), and the average line segment of this cluster is computed (lines 11-12) using three parameters: the center, the length and the azimuth. These parameters are determined from the cluster characteristics. The length and the azimuth are average values computed from all line segments in the cluster. The center is obtained as a length-weighted average of coordinates of each line segment center in the cluster (see Fig. 2). All the line segments forming the cluster are removed from the data set (line 13), and the algorithm continues with the next yet unprocessed line segment.

Let us move to the time complexity of Algorithm 1. The whole algorithm can be divided into three main parts.

Part 1 (line 1), line segments insertion into the grid and filtration, needs \(\mathcal {O}_r(N)\) time supposing maximally \(\mathcal {O}(\sqrt{N}) \times \mathcal {O}(\sqrt{N})\) size of the grid.

For part 2 (line 2), sorting, some well-known sorting algorithms such as quicksort or merge sort can be used. Using an optimal sorting algorithm, part 2 needs \(\mathcal {O}_s(N \text {log} N)\) time.

The worst scenario of part 3 (line 3-14), the clustering part, can lead to a situation where all checked line segments in L are outside the buffer zones, which means that in every iteration a new cluster is made. As a consequence, step 7 will check all line segments in \(\mathcal {O}(N)\). The overall time complexity of the clustering part is thus \(\mathcal {O}_{cl}(N^2)\).

The total time complexity of clustering line analysis of the MHHC can be summarized as \(\mathcal {O}_{MHHC} = \mathcal {O}_r + \mathcal {O}_s + \mathcal {O}_{cl} = \mathcal {O}(N) + \mathcal {O}(N \text {log} N) + \mathcal {O}(N^2) = \mathcal {O}(N^2)\).

Algorithm 1 checks many possible cases of cluster groups and brings a usable solution. However, due to the extensive search, it is very slow. A more sophisticated clustering method can improve the time complexity and substantially speed up the computation.

The original local search algorithm expects all the point coordinates of the same units in the same interval to work correctly. However, suppose the line segments given by Eq. (3) are used instead of points. In that case, the particular coordinates can have different intervals and units (the azimuth is measured in degrees, and the spatial coordinates are usually in meters).

To balance such heterogeneous coordinates, let us define the weight \(\textbf{w}\) for distance computations. The calculation of the weighted distance \(d_w\) of two points \(\textbf{p}=(p_1,p_2, \ldots p_D)^T\) and \(\textbf{q} = (q_1,q_2, \ldots q_D)^T\) affected by the weight \(\textbf{w} = (w_1, w_2, \dots w_D )^T, w_i\in R_{\emptyset }^+\) is defined as follows:The domain for \(\textbf{w}\) depends on the application or user preferences. By the weights, adding more influence to some of the coordinates is possible.

The final clustering cost \(Q\) in Eq. (1) depends on the individual coordinates’ weight changes. Let us demonstrate the influence for \(D=2\). If the weight of the second coordinate is lower than the weight of the first coordinate, then the final clusters are more elongated in the direction of the second coordinate; see Fig. 3.

If the weights are used, the overall clustering cost \(Q\) is influenced by changing the weighted distance calculation individually \(d_w\). Before calculating the weighted distance \(d_w(\varvec{l}_p, \varvec{l}_q)\) between line segments \(\varvec{l}_p\) and \(\varvec{l}_q\) according to Eq. (5), line segments are tested if they lie in the buffer zone and satisfy the azimuth threshold \(\xi _{az}\). If a segment violates one of these thresholds, the weighted distance \(d_w\) is set to infinity. Otherwise, the computation continues according to Eq. (5). So, the computation of the weighted distance \(d_w\) of two line segments \(\varvec{l}_p\) and \(\varvec{l}_q\) can be formalized as:The proposed algorithm uses the distance \(d_w\) in Eq. (1) instead of d. This modification makes a connection between two line segments violating one of the conditions, which is costly but not impossible due to the randomness of the local search step. It means that, unlike the original cluster line analysis algorithm in MHHC presented in Sect. 4, the resulting cluster may violate either the buffer zone or the azimuth condition.

Another impact of Eq. (6) can be seen on special occasions, where multiple line segments are in the same buffer zone but could represent different lineament features. In that case, the distance between the cluster and line segments is calculated to determine whether the line segment should be connected to the existing cluster or creates a new cluster according to the total clustering cost \(Q\).

The newly proposed algorithm is presented in Algorithm 3, using facility location for input data given as a set of line segments in Algorithm 2.

The main differences against MHHC are as follows. The cluster line analysis in the MHHC algorithm uses filtering (noise reduction) as the first step to save computation time. In the proposed algorithm, it is no more needed. It is advantageous because filtering may expel some “useful” line segments and requires extra time. Instead of being sorted, the line segments are clustered using the facility location.

Another difference from the clustering algorithm in MHHC is a simplification of the buffer zone’s shape around the cluster’s average line segment. Now a rectangular buffer zone is used, and its shape is checked whenever the arrangement of the cluster is changed (new line segments are added or removed from the cluster) and modified if necessary. The width and the height of the buffer zone rectangle are controlled by the parameters \(X\) and \(Y\), respectively.

Let us address the complexity of AMHHC. The worst-case complexity of the proposed algorithm is reigned by the facility location part (step 1 in Algorithm 2), which is \(\mathcal {O}(N^2)\). It means that the AMHHC algorithm is, in the worst case, not better than the MHHC; however, the expected behavior could be better due to the more sophisticated clustering part.

The newly proposed AMHHC algorithm and the existing MHHC algorithm were implemented in Python 3.7 (Kaas 2017) to make a fair comparison. Experiments were run on the computer with Intel ^® Xeon ^® under Windows 10 with 14 GB memory.

The set of parameters for the original MHHC algorithm was chosen to produce the best possible MHHC results: \(\xi _{\rm{cnt}}= 4\), \(\xi _{az}= 20^\circ\), \(bfs_{\rm{max}} = 200m\) and \(bfs_{\rm{min}}=100m\). The parameters for AMHHC were then chosen similarly for a fair comparison. The parameters for AMHHC were: \(\xi _{\rm{cnt}}= 4\), \(\xi _{az}= 20^\circ\), \(X= 150m\) and \(Y= 200m\).

The datasets for the tests were not taken from one particular geographical area but combined from more regions; the main criterion was the number of detected lineaments so that we could produce a table with a growing number of lineaments and compare the runtimes as a function of input size. The tests were run on 13 datasets of various sizes, 1000 up to 300 000 line segments (Kaas and Silhavy 2017a, b). The datasets describe natural areas in Canada, the Czech Republic (the Šumava mountains), and the Slovak Republic (the Žiar and Hronska mountains). Some of these areas were visualized in Silhavy et al. (2016). The two most extensive datasets could not have been processed by the MHHC method due to their more considerable memory requirements.

The quality of results was compared in two ways, by mutual correlations computed from the results and by visual comparison.

The correlation of the line segments was computed by the vector-based comparison (Silhavy et al. 2016), see Algorithm 4. This algorithm has two sets of line segments as input, \(A\), and \(B\). It takes a line segment from \(A\) and looks for a corresponding line segment in \(B\). A corresponding line segment must lie in the defined buffer zone and have the azimuth difference from the tested line segment less than \(\xi _{az}\). The correlation is then determined as the number of the found reference line segments and the tested line segments in percent. A bigger value means a bigger correspondence between both line segment sets. The same test is done with swapped \(A\) and \(B\) sets.

Table 1, column Corr(MHHC, AMHHC), uses the MHHC line segments as \(L_A\) and the AMHHC line segments as \(L_B\), Corr(AMHHC, MHHC) vice versa. Mutual correlations proved a high rate of identity between the results of both methods. Corr(MHHC, AMHHC) reached nearly 100 percent, which means that nearly for each line segment computed by MHHC there is a corresponding line segment computed by AMHHC. Corr(AMHHC, MHHC) came to 95 percent on average, implying that some line segments are computed by AMHHC that do not have a corresponding line segment found by MHHC. These extra line segments in AMHHC are usually those which have been filtered in the noise reduction step in MHHC. Therefore the MHHC\(_{^g-}\) represents the MHHC algorithm without grid filtration (step 1 in Algorithm 1). This phenomenon is confirmed by column Corr(AMHHC, MHHC\(_{g^-}\)), which has increased the correlation to 98 percent on average. The last three columns show the number of resulting clusters in all methods. In summary, we can say that the AMHHC provides similar results (reaching 98 to 100 percent of correlation) to the original MHHC approach.

The statistical results were confirmed by visual comparison. A typical example is shown in Fig. 4a, where the input dataset is represented by gray color, average centers of MHHC by red, and AMHHC by light green. It can be seen that the results are nearly the same. The differences are minimal; see Fig. 4b, where greenly highlighted average centers produced by AMHHC are not present in the result of MHHC. These extra centers are usually present in regions with a higher density of line segments. AMHHC is in some way more careful.

Table 2 shows the total computing times of the original MHHC and AMHHC. The speed-up of AMHHC is shown in the column “MHHC/AMHHC”.

It can be seen that AMHHC is for tested datasets faster; the trend is shown in Fig. 5, i.e., for bigger datasets, there comes a higher speed-up between the proposed algorithm and its predecessor. The speed-up is caused by a more sophisticated clustering approach. The first part of the Algorithm 2 continuously investigates a point against existing facilities. In real data, the number of facilities slowly increases during the algorithm. Therefore, the \(\mathcal {O}(N^2)\) time is rarely needed in practice. The second part of the Algorithm 2 with complexity \(\mathcal {O}(N \text {log} N)\) is enough to make a sufficient clustering solution. In contrast, in MHHC a point is investigated against the rest of the data set; therefore, \(\mathcal {O}(N^2)\) is always needed.

This paper presented a new algorithm, AMHHC, for the spatial line segment clustering in the lineament extraction. The algorithm is based on a modification of the MHHC algorithm. The modification is based on the facility location algorithm for clustering, modified for line segments. The experiments verified that the algorithm is much faster than the original algorithm and provides nearly identical results, keeping the good properties of the original algorithm. Its minor memory requirements allow it to process more extensive data sets.

The proposed solution could be further accelerated using the N-dimensional version of quadtree to restrict the searched space of line segments in the function gain used in Algorithm 2. Instead of checking the whole input data set of the line segments, only those line segments, which can be attached to the newly formed cluster, would be inspected.