Abstract
Hyperspectral images contain large spectral information with an abundance of redundancy and a curse of dimensionality. Due to the absence of prior knowledge or availability of ground-truth data, clustering of these images becomes a herculean task. Hence, unsupervised cluster detection methods are more beneficial for utilising hyperspectral images in real-life scenarios. In this paper, six multilevel quantum inspired metaheuristics are proposed viz., Qubit Genetic Algorithm, Qutrit Genetic Algorithm, Qubit Multi-exemplar Particle Swarm Optimization Algorithm, Qutrit Multi-exemplar Particle Swarm Optimization Algorithm, Qubit Artificial Humming Bird Algorithm, and Qutrit Artificial Humming Bird Algorithm, for determining the optimal number of clusters in hyperspectral images automatically. Binary and ternary quantum versions of the algorithms are developed to enhance their exploration and exploitation capabilities. Simple algorithms for implementing quantum rotation gates are developed to bring diversity in the population without resorting to look-up tables. One of the main features of quantum gates is that they are reversible in nature. This property has been utilized for implementing quantum disaster operations. The application of a dynamic number of exemplars also enhances the performance of the Multi-exemplar Particle Swarm Optimization Algorithm. The six proposed algorithms are compared to the classical Genetic Algorithm, Multi-exemplar Particle Swarm Optimization Algorithm, and Artificial Humming Bird Algorithm. All the nine algorithms are applied on three hyperspectral image datasets viz., Pavia University, Indian Pines, and Xuzhou HYSPEX datasets. Statistical tests like mean, standard deviation, Kruskal Wallis test, and Tukey’s Post Hoc test are performed on all the nine algorithms to establish their efficiencies. Three cluster validity indices viz., Xie-Beni Index, Object-based Validation with densities, and Correlation Based Cluster Validity Index are used as the fitness function. The F, F’, and Q scores are used to compare the clustered images. The proposed algorithms are found to perform better in most of the cases when compared to their classical counterparts. It is also observed that the qutrit versions of the algorithms are found to converge faster. They also provide the optimal number of clusters almost equivalent to the number of classes identified in the ground-truth image.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Code and Data availability
The software code for the proposed algorithm is publicly available at GitHub: https://github.com/Tulika-opt/Multi-Level-QIM-for-Automatic-Clustering-of-HSI.git
References
Abdollahzadeh B, Soleimanian Gharehchopogh F, Mirjalili S (2021) Artificial gorilla troops optimizer: A new nature-inspired metaheuristic algorithm for global optimization problems. Int J Intell Syst 36(10):5887–5958
Abualigah L, Elaziz MA, Sumari P et al (2022) Reptile search algorithm (rsa): A nature-inspired meta-heuristic optimizer. Exp Syst Appl 191:116158
Abualigah L, Gandomi AH, Elaziz MA, et al (2021) Advances in meta-heuristic optimization algorithms in big data text clustering. Electronics 10(2):101
Acampora G, Schiattarella R, Vitiello A (2022) Using quantum amplitude amplification in genetic algorithms. Exp Syst Appl 209:118203
Agushaka JO, Ezugwu AE, Abualigah L (2022) Dwarf mongoose optimization algorithm. Comput Methods Appl Mech Eng 391:114570
Akinola OA, Ezugwu AE, Oyelade ON et al (2022) A hybrid binary dwarf mongoose optimization algorithm with simulated annealing for feature selection on high dimensional multi-class datasets. Sci Rep 12:14945
Aliniya Z, Mirroshandel SA (2019) A novel combinatorial merge-split approach for automatic clustering using imperialist competitive algorithm. Exp Syst Appl 117:243–266
Almotairi KH, Abualigah L (2022) Hybrid reptile search algorithm and remora optimization algorithm for optimization tasks and data clustering. Symmetry 14(3)
Arora S, Singh S (2019) Butterfly optimization algorithm: a novel approach for global optimization. Soft Comput 23:715–734
Askarzadeh A (2016) A novel metaheuristic method for solving constrained engineering optimization problems: Crow search algorithm. Comput Struct 169:1–12
Baker FB, Hubert LJ (1975) Measuring the power of hierarchical cluster analysis. J Am Stat Assoc 70(349):31–38
Baumgardner MF, Biehl LL, Landgrebe DA (2015) 220 band aviris hyperspectral image data set: June 12, 1992 indian pine test site 3. https://purr.purdue.edu/publications/1947/1. Accessed 09 May 2019
Bezdek JC, Ehrlich R, Full W (1984) Fcm: The fuzzy c-means clustering algorithm. Comput Geosci 10(2):191–203
Borsotti M, Campadelli P, Schettini R (1998) Quantitative evaluation of color image segmentation results. Patt Recog Lett 19(8):741–747
Cai Y, Liu X, Cai Z (2020) Bs-nets: An end-to-end framework for band selection of hyperspectral image. IEEE Trans Geosci Remote Sens 58(3):1969–1984
Caliński T, JA H (1974) A dendrite method for cluster analysis. Commun Stat Theory Methods 3:1–27
Cao F, Mishra DR, Schalles JF et al (2018) Evaluating ultraviolet (uv) based photochemistry in optically complex coastal waters using the hyperspectral imager for the coastal ocean (hico). Estuar Coast Shelf Sci 215:199–206
Dey A, Dey S, Bhattacharyya S et al (2020) Novel quantum inspired approaches for automatic clustering of gray level images using particle swarm optimization, spider monkey optimization and ageist spider monkey optimization algorithms. Appl Soft Comput 88:106040
Ding C, Zheng M, Chen F, et al (2022) Hyperspectral image classification promotion using clustering inspired active learning. Remote Sensing 14(3):596. https://doi.org/10.3390/rs14030596. Accessed 1 May 2023
Dorigo M, Maniezzo V, Colorni A (1996) Ant system: optimization by a colony of cooperating agents. IEEE Trans Syst Man Cybern B (Cybern) 26(1):29–41
Dunn JC (1973) A fuzzy relative of the isodata process and its use in detecting compact well-separated clusters. J Cybern 3(3):32–57
Duong HQ, Nguyen QH, Ngguyen DT et al (2022) Pso based hybrid pid-flc sugeno control for excitation system of large synchronous motor. Emerg Sci J 6:1375–1393
Dutta T, Bhattacharyya S, Dey S et al (2020) Border collie optimization. IEEE. Access 8:109177–109197
Dutta T, Dey S, Bhattacharyya S (2020) Automatic Clustering of Hyperspectral Images Using Qutrit Based Particle Swarm Optimization. Springer Singapore, Singapore, pp 21–31
Dutta T, Dey S, Bhattacharyya S et al (2021) Quantum fractional order darwinian particle swarm optimization for hyperspectral multi-level image thresholding. Appl Soft Comput 113:107976
Dutta T, Dey S, Bhattacharyya S et al (2021) Hyperspectral multi-level image thresholding using qutrit genetic algorithm. Exp Syst Appl 181:115107
Dutta T, Bhattacharyya S, Mukhopadhyay S (2021a) Automatic clustering of hyperspectral images using qutrit exponential decomposition particle swarm optimization. In: 2021 IEEE International India Geoscience and Remote Sensing Symposium (InGARSS). pp 289–292
Elmaizi A, Nhaila H, Sarhrouni E et al (2019) A novel information gain based approach for classification and dimensionality reduction of hyperspectral images. Procedia Comput Sci 148:126–134
Ezugwu AE, Adeleke OJ, Akinyelu AA et al (2020) A conceptual comparison of several metaheuristic algorithms on continuous optimization problems. Neural Comput Appl 32:6207–6251
Fang L, Qiu T, Zhao H et al (2019) A hybrid active contour model based on global and local information for medical image segmentation. Multidim Syst Signal Process 30(2):689–703
Gharehchopogh F (2022) Quantum-inspired metaheuristic algorithms: comprehensive survey and classification. Artif Intell Rev
Ghosh SK, Ghosh A (2022) Correlation based cluster validity index for recognition of leukemia mediating biomarkers. In: Mandal JK, De D (eds) Advanced Techniques for IoT Applications. Springer Singapore, Singapore, pp 65–74
Goh A, Vidal R (2007) Segmenting motions of different types by unsupervised manifold clustering. In: 2007 IEEE Conference on Computer Vision and Pattern Recognition. pp 1–6
Gokhale P, Baker JM, Duckering C et al (2020) Extending the frontier of quantum computers with qutrits. IEEE Micro 40(3):64–72
Green A, Berman M, Switzer P et al (1988) A transformation for ordering multispectral data in terms of image quality with implications for noise removal. IEEE Trans Geosci Remote Sens 26(1):65–74
Han KH, Kim JH (2002) Quantum-inspired evolutionary algorithm for a class of combinatorial optimization. IEEE Trans Evol Comput 6(6):580–593
Han T, Niu S, Gao X et al (2022) Deep low-rank graph convolutional subspace clustering for hyperspectral image. IEEE Trans Geosci Remote Sens 60:1–13
Heidari AA, Mirjalili S, Faris H et al (2019) Harris hawks optimization: Algorithm and applications. Futur Gener Comput Syst 97:849–872
He C, Zhang Y, Gong D, et al (2022) A multi-task bee colony band selection algorithm with variable-size clustering for hyperspectral images. IEEE Trans Evol Comput 1:26
Hilali-Jaghdam I, Ishak AB, Abdel-Khalek S et al (2020) Quantum and classical genetic algorithms for multilevel segmentation of medical images: A comparative study. Comput Commun 162:83–93
Holland JH (1992) Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. MIT Press, Cambridge
Hughes G (1968) On the mean accuracy of statistical pattern recognizers. IEEE Trans Inf Theory 14(1):55–63
Huo F, Sun X, Ren W (2020) Multilevel image threshold segmentation using an improved bloch quantum artificial bee colony algorithm. Multimedia Tools Appl 79:2447–2471
ibm (2022) Untitled circuit - ibm quantum. https://quantum-computing.ibm.com/composer/files/23775edf4643561fe64d3e5253939e74. Accessed 30 June 2022
ipd (2019) Purr - publications: 220 band aviris hyperspectral image data set: June 12, 1992 indian pine test site 3. https://purr.purdue.edu/publications/1947/1. Accessed 5 Sept 2019
Javed A, Kim YC, Khoo MCK et al (2016) Dynamic 3-d mr visualization and detection of upper airway obstruction during sleep using region-growing segmentation. IEEE Trans Biomed Eng 63(2):431–437
Jia H, Peng X, Lang C (2021) Remora optimization algorithm. Expert Syst Appl 185:115665
Kelam H, Venkatesan M (2019) Optimal band selection using generalized covering-based rough sets on hyperspectral remote sensing big data. In: Peter JD, Alavi AH, Javadi B (eds) Advances in Big Data and Cloud Computing. Springer Singapore, Singapore, pp 263–273
Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings of ICNN’95 - International Conference on Neural Networks, vol 4. pp 1942–1948
Khalaf T, Çağlar H, Çağlar A et al (2020) Particle swarm optimization based approach for estimation of costs and duration of construction projects. Civil Eng J 6:384–401
Khrissi L, Akkad NE, Satori H et al (2022) Clustering method and sine cosine algorithm for image segmentation. Evol Intell 15:669–682
Kruskal WH, Wallis WA (1952) Use of ranks in one-criterion variance analysis. J Am Stat Assoc 47(260):583–621
Li F, Zhang P, Huchuan L (2018) Unsupervised band selection of hyperspectral images via multi-dictionary sparse representation. IEEE Access 6:71632–71643
Li JY, Guo SM, Gu L et al (2022) Quantum evolutionary algorithm based power optimization control strategy for china initiative accelerator driven subcritical system. Ann Nucl Energy 166:108678
Liao W, Pizurica A, Scheunders P et al (2013) Semisupervised local discriminant analysis for feature extraction in hyperspectral images. IEEE Trans Geosci Remote Sens 51(1):184–198
Li C, Tang X, Shi L, et al (2022a) A two-staged feature extraction method based on total variation for hyperspectral images. Remote Sens 14(2):302
Liu T, Zhang P, Cui G et al (2021) Fracture performance prediction of polyvinyl alcohol fiber-reinforced cementitious composites containing nano-sio2 using least-squares support vector machine optimized with quantum-behaved particle swarm optimization algorithm. Theor Appl Fract Mech 115:103074
Long W, Jiao J, Liang X et al (2018) An exploration-enhanced grey wolf optimizer to solve high-dimensional numerical optimization. Eng Appl Artif Intell 68:63–80
Loubiére P, Jourdan A, Siarry P, Chelouah R (2018) A sensitivity analysis method aimed at enhancing the metaheuristics for continuous optimization. Artif Intell Rev 50:625–647
Ma B, Qi J, Wu Y et al (2022) Parameter estimation of the covid-19 transmission model using an improved quantum-behaved particle swarm optimization algorithm. Digit Signal Process 127:103577
Macqueen J (1967) Some methods for classification and analysis of multivariate observations. In: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Statistics. pp 281–297
Maulik U, Bandyopadhyay S (2002) Performance evaluation of some clustering algorithms and validity indices. IEEE Trans Patt Anal Mach Intell 24:1650–1654
McMahon D (2008) Quantum Computing Explained. Wiley, Hoboken
Mirjalili S, Mirjalili SM, Lewis A (2014) Grey wolf optimizer. Adv Eng Softw 69:46–61
Mousavi S, Afghah F, Ashdown JD et al (2019) Use of a quantum genetic algorithm for coalition formation in large-scale uav networks. Ad Hoc Netw 87:26–36
Muazu AA, Hashim AS, Sarlan A (2022) Review of nature inspired metaheuristic algorithm selection for combinatorial t-way testing. IEEE Access 10:27404–27431
Narayanan A, Moore M (1996) Quantum-inspired genetic algorithms. In: Proceedings of IEEE International Conference on Evolutionary Computation. pp 61–66
Nielsen MA, Chuang I (2002) Quantum computation and quantum information. Am J Phys 70(5):558–559
Oh E, Lee H (2022) Effective route generation framework using quantum mechanism-based multi-directional and parallel ant colony optimization. Comput Ind Eng 169:108–308
pav (2019) Hyperspectral data set. http://lesun.weebly.com/hyperspectral-data-set.html. Accessed 5 Sept 2019
Pavlidis A, Floratos E (2021) Quantum-fourier-transform-based quantum arithmetic with qudits. Phys Rev A 103:032417
Rodarmel C, Shan J (2002) Principal component analysis for hyperspectral image classification. Surv Land inf Syst 62:115–123
Rodriguez A, Laio A (2014) Clustering by fast search and find of density peaks. Science 344(6191):1492–1496
Rylander B, Soule T, Foster J, et al (2000) Quantum genetic algorithms. In: Proceedings of the 2nd Annual Conference on Genetic and Evolutionary Computation, GECCO’00. Morgan Kaufmann Publishers Inc., San Francisco, p 373
S. Menesy A, Sultan HM, Selim A, G. Ashmawy M, Kamel S (2020) Developing and applying chaotic harris hawks optimization technique for extracting parameters of several proton exchange membrane fuel cell stacks. IEEE Access 8:1146–1159
Saremi S, Mirjalili S, Lewis A (2017) Grasshopper optimisation algorithm: Theory and application. Adv Eng Softw 105:30–47
Sobol IM (1993) Sensitivity estimates for nonlinear mathematical models. Math. Model. Comput. Exp 1(4):407–414
Song W, Hua Z (2020) Multi-exemplar particle swarm optimization. IEEE. Access 8:176363–176374
Storn R, Price K (1997) Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces. J Global Optim 11(4):341–359
Sudjalim TR, Woods MG, Manton DJ et al (2007) Prevention of demineralization around orthodontic brackets in vitro. Am J Orthod Dentofac Orthop 131(6):705.e1-705.e9
Surono S, Goh KW, Onn C et al (2022) Optimization of markov weighted fuzzy time series forecasting using genetic algorithm (ga) and particle swarm optimization (pso). Emerg Sci J 6:1375–1393
Tan K, Wu F, Du Q et al (2019) A parallel gaussian-bernoulli restricted boltzmann machine for mining area classification with hyperspectral imagery. IEEE J Sel Top Appl Earth Obs Remote Sens 12(2):627–636
Tavakkol B, Choi J, Jeong MK et al (2022) Object-based cluster validation with densities. Pattern Recog 121:108223
Tkachuk V (2018) Quantum genetic algorithm based on qutrits and its application. Mathematical Problems in Engineering 2018(8614073):8. https://doi.org/10.1155/2018/8614073
Tu S, Rehman OU, Rehman SU et al (2020) A novel quantum inspired particle swarm optimization algorithm for electromagnetic applications. IEEE Access 8:21909–21916
Vaswani A, Shazeer N, Parmar N et al (2017) Attention is all you need, NIPS’17. Curran Associates Inc., Red Hook, pp 6000–6010
Villa A, Benediktsson JA, Chanussot J et al (2011) Hyperspectral image classification with independent component discriminant analysis. IEEE Trans Geosci Remote Sens 49(12):4865–4876
Wang X, Tan K, Du Q et al (2019) Caps-triplegan: Gan-assisted capsnet for hyperspectral image classification. IEEE Trans Geosci Remote Sens 57(9):7232–7245
Weijtmans P, C.Shan, Tan T, et al (2019) A dual stream network for tumor detection in hyperspectral images. In: 2019 IEEE 16th International Symposium on Biomedical Imaging (ISBI 2019). pp 1256–1259
Wolpert D, Macready W (1997) No free lunch theorems for optimization. IEEE Trans Evol Comput 1(1):67–82
Wu YC, Lee W, Chien CW (2011) Modified the performance of differential evolution algorithm with dual evolution strategy. In: International conference on machine learning and computing. pp 57–63
Wu T, Wu D, Jia H, et al (2022) A modified gorilla troops optimizer for global optimization problem. Appl Sci 12(19):10144
Xie XL, Beni G (1991) A validity measure for fuzzy clustering. IEEE Trans Pattern Anal Mach Intell 13(8):841–847
Xie F, Li F, Lei C et al (2019) Unsupervised band selection based on artificial bee colony algorithm for hyperspectral image classification. Appl Soft Comput 75:428–440
Zhang H, Zhai H, Zhang L et al (2016) Spectral-spatial sparse subspace clustering for hyperspectral remote sensing images. IEEE Trans Geosci Remote Sens 54(6):3672–3684
Zhang Q, Li H, Liu Y et al (2021) A new quantum particle swarm optimization algorithm for controller placement problem in software-defined networking. Comput Electr Eng 95:107–456
Zhang Y, Desai MD, Zhang J, et al (1999) Adaptive subspace decomposition for hyperspectral data dimensionality reduction. In: Proceedings 1999 International Conference on Image Processing (Cat. 99CH36348). pp 326–329
Zhao W, Wang L, Mirjalili S (2022) Artificial hummingbird algorithm: A new bio-inspired optimizer with its engineering applications. Comput Methods Appl Mech Eng 388:114–194
Zhao K, Dai Y, Jia Z, et al (2021) General fuzzy c-means clustering strategy: Using objective function to control fuzziness of clustering results. IEEE Trans Fuzzy Syst 1:388
Zhong Y, Zhang L, Gong W (2011) Unsupervised remote sensing image classification using an artificial immune network. Int J Remote Sens 32(19):5461–5483
Zhong Z, Li J, Luo Z et al (2018) Spectral-spatial residual network for hyperspectral image classification: A 3-d deep learning framework. IEEE Trans Geosci Remote Sens 56(2):847–858
Funding
The authors hereby declare that this work received no funding from any funding organization.
Author information
Authors and Affiliations
Contributions
Conceptualization, Methodology, Writing - original draft preparation: Tulika Dutta; Formal analysis and investigation, Writing - review and editing: Siddhartha Bhattacharyya; Writing - review and editing, Supervision: Bijaya Ketan Panigrahi; Writing - review and editing, Supervision: Ivan Zelinka; Supervision: Leo Mrsic.
Corresponding author
Ethics declarations
Conflict of interest
The authors hereby declare that they have no conflicting interest with the reviewers or any funding organization.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Siddhartha Bhattacharyya, Bijaya Ketan Panigrahi, Ivan Zelinka, and Leo Mrsic have contributed equally to this work.
Supplementary Information
Below is the link to the electronic supplementary material.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Dutta, T., Bhattacharyya, S., Panigrahi, B.K. et al. Multi-level quantum inspired metaheuristics for automatic clustering of hyperspectral images. Quantum Mach. Intell. 5, 22 (2023). https://doi.org/10.1007/s42484-023-00110-7
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s42484-023-00110-7