Accelerating the K-Nearest Neighbors Filtering Algorithm to Optimize the Real-Time Classification of Human Brain Tumor in Hyperspectral Images

Abstract

The use of hyperspectral imaging (HSI) in the medical field is an emerging approach to assist physicians in diagnostic or surgical guidance tasks. However, HSI data processing involves very high computational requirements due to the huge amount of information captured by the sensors. One of the stages with higher computational load is the K-Nearest Neighbors (KNN) filtering algorithm. The main goal of this study is to optimize and parallelize the KNN algorithm by exploiting the GPU technology to obtain real-time processing during brain cancer surgical procedures. This parallel version of the KNN performs the neighbor filtering of a classification map (obtained from a supervised classifier), evaluating the different classes simultaneously. The undertaken optimizations and the computational capabilities of the GPU device throw a speedup up to 66.18× when compared to a sequential implementation.

Keywords: K-nearest neighbors filtering; brain cancer detection; graphics processing units; hyperspectral imaging instrumentation; image processing.

Figure 1

Hyperspectral acquisition system. (A) Schematic diagram of the HS acquisition system; (B) HS acquisition system capturing an image during a neurosurgical operation at the University Hospital Doctor Negrin of Las Palmas de Gran Canaria.

Figure 2

Example of an in-vivo HS human brain image dataset employed in the study (P2C1). (A) Synthetic RGB representation of the HS cube; (B) Supervised classification map obtained using the SVM classifier; (C) One-band representation of the HS cube obtained employing PCA algorithm.

Figure 3

Block diagram of the KNN based spatial-spectral classification.

Figure 4

KNN window searching method example. (A) Minimum window size of the first pixel; (B) Intermediate window size of a pixel near the upper border; (C) Maximum window size of a pixel in the center of the image; (D) Intermediate window size of a pixel near the bottom border; (E) Minimum window size of the last pixel.

Figure 5

Flow diagram of the serial implementation of the KNN filtering algorithm.

Figure 6

Flow diagram of the parallel implementation of the KNN filtering algorithm.

Figure 7

KNN searching new distance evaluation example.

Figure 8

Percentage of pixels that have been misclassified using the Euclidean distance between tumor and healthy tissues (blue), tumor and hypervascularized tissues (orange), tumor tissue and background (gray) and the other misclassifications between healthy, hypervascularized and background (yellow). The results were obtained per each window size implementations compared to the WSize14 for each image of the dataset.

Figure 9

Percentage of misclassified pixels using the Manhattan distance between tumor and healthy tissues (blue), tumor and hypervascularized tissues (orange), tumor tissue and background (gray) and the other misclassifications between healthy, hypervascularized and background (yellow). The results were obtained per different window sizes implementation compared to the WSize14 for each image of the dataset.

Figure 10

Results of the KNN filtering algorithm obtained from the P2C1 image using the Euclidean distance. The first row shows the filtered classification maps generated using different window sizes. The second row presents the binary maps where the pixel differences between the current generated map and the reference one (WSize14) are shown. In addition, the percentage of differences and the execution time results are detailed.

Figure 11

Results of the KNN filtering algorithm obtained from the P2C1 image using the Manhattan distance. The first row shows the filtered classification maps generated using different window sizes. The second row presents the binary maps where the pixel differences between the current generated map and the WSize14. In addition, the percentage of differences and the execution time results are detailed.

Figure 12

Results comparison of the KNN filtered maps from the P2C1 image using both the Manhattan and Euclidean distances. The first row shows the filtered classification maps generated using different window sizes and distance metrics. The second row presents the binary maps where the pixel differences between the current generated map and the reference one (WSize14-Euclidean) are shown. In addition, the percentage of differences and the execution time results are detailed.

Figure 13

Figure of metric computed comparing (A) the Euclidean versions WSize8, WSize6, WSize4 and WSize2 with the reference WSize14-Euclidean, (B) the Manhattan versions WSize8, WSize6, WSize4 and WSize2 with the reference WSize14-Euclidean.