# Segment-Based Clustering of Hyperspectral Images Using Tree-Based Data Partitioning Structures
## 2 Methodology
### K-Means Clustering  
Hyperspectral images have high spectral resolution; hence, a high redundancy is present in the data from the neighboring bands. Consequently, neighboring bands of the image are highly correlated. In addition, the large amount of data present increases the processing complexity and time. In order to effectively remove the correlation among the bands and reduce the size of HSI data, principal component analysis (PCA) is utilized as a pre-processing technique, such that the optimum linear combination of the original bands is produced. The extracted features are then embedded with the segmentation map of the BPT stage before k-means clustering is applied. The embedding approach that is used by CLUS-BPT assigns a set of PCA-reduced pixel values for each region from the segmentation map. For instance, the data structure of a region represented by pruned tree node number 5 (\(P_{R}(5)\)) that is shown in Figure 3 contains the following objects:  
Figure 2: Binary partition trees (BPT) construction using a region merging algorithm as adapted from [27]. * region label: a unique region number,
* bounding box: a rectangular box formed by \(i\) and \(j\) pixel coordinates of the segmentation map with the size of the box equal to the number of pixels included in the region and
* PCA data values: a vector containing the PCA-reduced values with the pixel coordinates corresponding to the coordinates of the _bounding box_. Region label and bounding box data objects are set for each node during BPT construction. In contrast, PCA data values are assigned to the node during the embedding process based on their positions that correspond to the bounding box coordinates of the region on the segmentation map. The segmentation map is a set of boundaries between data points of the values that were obtained by PCA, as depicted in Figure 4. The tree containing the segmentation map embedded with the PCA data values is fed to the clustering stage, which gives labels to the formed regions. CLUS-BPT performs an efficient k-means clustering algorithm that is specifically designed for a multidimensional binary space partition tree, called kd-tree [30]. The goal of k-means clustering is to find the minimum argument for each cluster group and calculate the distances of each point in a cluster to the centroid of that cluster. The complexity of the algorithm increases linearly with the number of centers, data points, dimensions in a data set, and iterations number. A straightforward implementation of k-means standard algorithm in high-dimensional HSI data sets can be quite slow, due to the cost of computing nearest neighbors [25; 30]. The filtering algorithm that is introduced in [30] is applicable for the BPT data structure used throughout the stages of CLUS-BPT. The main idea of the filtering algorithm is to prune (filter) down the search space for the optimal cluster partition, such that the computation burden is reduced. At the initial iteration of clustering, the regions of the segmentation map act as a base for the algorithm to start from. During clustering, these regions are either differentiated or joined by assigning them cluster labels as the tree is traversed. Algorithm 1 shows a pseudo code for one iteration of the filtering algorithm. Each node \(P_{R}(i)\) of the BPT tree represents a region and it is associated with the bounding box (\(C\)) information from which the number of pixels (\(count\)) is deduced. A new data vector representing the sum of the associated  
Figure 4: Principal component analysis (PCA) and segmentation map embedding example. Figure 3: Example of a BPT pruned tree after embedding. pixels (the weighted centroid, \(wgt\_Cent\)) is added to the tree and it is used for updating the cluster centers after each iteration. The actual centroid is computed as \(wgt\_Cent/count\). In addition, a set of possible candidate centers \(U\) is kept for each node and is propagated down the tree [30].