# Spectra-Based Selective Searching for Hyperspectral Anomaly Detection
## 2 Materials and Methods
### Proposed Anomaly Detection Algorithm  
#### 2.2.1 Oversegmentation of HSI  
As regions can yield richer information than a single pixel, we regard regions instead of pixels as the basic unit to more precisely represent background and anomaly characteristics. Therefore, we adapt the graph-based image segmentation algorithm [41] to hyperspectral images to integrate neighboring pixels with high similarity into a series of regions. In general, a hyperspectral image can be represented as \(HSI=(X,E)\), which is composed of pixel spectra \(x\in X\) and edges \(\left(x_{i},x_{j}\right)\in E\) representing the connection of the pairs of neighboring pixels. Each edge \(\left(x_{i},x_{j}\right)\in E\) has a corresponding weight \(w(x_{i},x_{j})\) which is the spectral similarity between the two neighboring pixels \(x_{i}\) and \(x_{j}\) connected by that edge. The segmentation of the HSI is a subdivision of the pixels into a series of regions such that each region corresponds to a connected component C and the pixels in each component are homogeneous. This requires that edges between two pixels in the same region should have relatively low weights, meaning that they are more similar. In order to effectively separate anomaly pixels from background pixels, we define the weight \(w(x_{i},x_{j})\) as the following dynamic similarity operator according to the measurement of spectral similarity. \[w=Ent\times(1-r)+LD \tag{5}\]  
The smaller the weight, the more similar are the two pixels, and the sooner the two pixels will be combined into a region. In addition to the definition of edge weights, the criterion for determining whether two components can be the same component is critical. In general, when the weight between two connected components is less than the maximum value of the internal weights for the two components, they can be considered as the same component. In math, this criterion can be expressed as  
\[Con\big{(}C_{i},C_{j}\big{)}=\left\{ \begin{array}{ll}true&if\;Diff\big{(}C_{ i},C_{j}\big{)}\leq MIDC\big{(}C_{i},C_{j}\big{)}\\ false&otherwise\end{array} \right. \tag{6}\]  
where \(Con\big{(}C_{i},C_{j}\big{)}\) represents whether two components \(\big{(}C_{i},C_{j}\big{)}\) should be connected and become the same component, and \(Diff\big{(}C_{i},C_{j}\big{)}\) describes the difference between two components and is defined as the minimum weight connecting the two components, as follows:  
\[Diff\big{(}C_{i},C_{j}\big{)}=\min_{x_{1}\in C_{i},x_{2}\in C_{j},(x_{1},x_{2 })\in E}w(x_{1},x_{2}) \tag{7}\]  
\(MIDC\big{(}C_{i},C_{j}\big{)}\) is the minimum internal difference, which is defined as  
\[MIDC\big{(}C_{i},C_{j}\big{)}=\min\big{(}IDC(C_{i})+\tau(C_{i}),IDC\big{(}C_{ j}\big{)}+\tau(C_{j})\big{)} \tag{8}\]  
where \(IDC(C)\) is the largest weight of the minimum spanning tree (MST) of the component \(MST(C,E)\) and expresses the internal difference of a component, given by  
\[IDC=\max_{e\in MST(C,E)}w(e) \tag{9}\]  
For small components, \(IDC(C)\) cannot accurately estimate the local characteristics of the component. For example, \(IDC(C)=0\) when the component is a single pixel. Therefore, the threshold function \(\tau(C)\) is necessary for segmentation to control the degree of difference between two different components to be greater than their respective internal differences. \[\tau(C)=\frac{K}{[C]} \tag{10}\]  
where, \([C]\) denotes the number of pixels in component \(C\) and \(K\) is a constant parameter that controls the size of the formed components, therefore setting a scale of oversegmentation. A larger \(K\) creates a preference for larger components. Moreover, \(K\) is not the minimum component size. This threshold function can make the segmentation criterion adaptive, which can preserve detail in the information of high-variability regions while ignoring detail in low-variability regions. Anomalies can occur at any location and in any shape within the HSI. This oversegmentation method is completely data-driven and divides the image into a series of initial regions with freewill shape and size.