×

Image segmentation on a quantum computer. (English) Zbl 1327.81124

Summary: In this paper, we address the field of quantum information processing and analyze the prospects of applying quantum computation concepts to image processing tasks. Specifically, we discuss the development of a quantum version for the image segmentation operation. This is an important technique that comes up in many image processing applications. We consider the threshold-based segmentation and show that a quantum circuit to achieve this operation can be built using a quantum oracle that implements the thresholding function. We discuss the circuit implementation of the oracle operator and provide examples of segmenting synthetic and real images. The main advantage of the quantum version for image segmentation over the classical approach is its speedup and is provided by the special properties of quantum information processing: superposition of states and inherent parallelism.

MSC:

81P68 Quantum computation
68Q12 Quantum algorithms and complexity in the theory of computing
68U10 Computing methodologies for image processing
81P15 Quantum measurement theory, state operations, state preparations
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Lloyd, S.: A potentially realizable quantum computer. Science 126, 1569-1571 (1993) · doi:10.1126/science.261.5128.1569
[2] Vendersypen, L., Steffen, M., Breyta, G., Yannoni, C., Cleve, R., Chuang, I.: 5 qubit 215 hz quantum processor. In: Proceedings of 12th Annual Hot Chips Conference, Palo Alto, Stanford University (2000)
[3] Ohlsson, N., Mohan, R., Kroell, S.: Quantum computer hardware based on rare-earth-ion-doped inorganic crystals. Opt. Commun. 201(1-3), 71-77 (2002) · doi:10.1016/S0030-4018(01)01666-2
[4] Fei, X., JiangFeng, D., MingJun, S., Xianyi, Z., Rongdian, H., Jihui, W.: Realization of Fredkin gate by three transition pulses in NMR quantum information processor. Chin. Phys. Lett. 19(8), 1048 (2002) · doi:10.1088/0256-307X/19/8/306
[5] Longdell, J., Sellars, M., Manson, N.: Demonstration of conditional quantum phase shift between ions in a solid. Phys. Rev. Lett. 93(13), 130503 (2004) · doi:10.1103/PhysRevLett.93.130503
[6] Politi, A., Matthews, J., O’Brien, J.: Shor’s quantum factoring algorithm on a photonic chip. Science 325(5945), 1221 (2009) · Zbl 1226.81052 · doi:10.1126/science.1173731
[7] DiCarlo, L., Chow, J., Gambetta, J., Bishop, L.S., Johnson, B., Schuster, D., Majer, J., Blais, A., Frunzio, L., Girvin, S., Schoelkopf, R.: Demonstration of two-qubit algorithms with a superconducting quantum processor. Nature 460(7252), 240-244 (2009) · doi:10.1038/nature08121
[8] Johnson, M.W., Amin, M.H.S., Gildert, S., Lanting, T., Hamze, F., Dickson, N., Harris, R., Berkley, A.J., Johansson, J., Bunyk, P., Chapple, E.M., Enderud, C., Hilton, J.P., Karimi, K., Ladizinsky, E., Ladizinsky, N., Oh, T., Perminov, I., Rich, C., Thom, M.C., Tolkacheva, E., Truncik, C.J.S., Uchaikin, S., Wang, J., Wilson, B., Rose, G.: Quantum annealing with manufactured spins. Nature 473(7346), 194-198 (2011) · doi:10.1038/nature10012
[9] Xu, N., Zhu, J., Lu, D., Zhou, X., Peng, X., Du, J.: Quantum factorization of 143 on a dipolar-coupling nuclear magnetic resonance system. Phys. Rev. Lett. 108, 130501 (2012) · doi:10.1103/PhysRevLett.108.130501
[10] van der Sar, T., Wang, Z.H., Blok, M.S., Bernien, H., Taminiau, T.H., Toyli, D.M., Lidar, D.A., Awschalom, D.D., Hanson, R., Dobrovitski, V.V.: Decoherence-protected quantum gates for a hybrid solid-state spin register. Nature 7392, 82-86 (2012)
[11] Pla, J.J., Tan, K.Y., Dehollain, J.P., Lim, W.H., Morton, J.J.L., Jamieson, D.N., Dzurak, A.S., Morello, A.: A single-atom electron spin qubit in silicon. Nature 489(7417), 541-545 (2012) · doi:10.1038/nature11449
[12] Fijany, A., Williams, C.: Quantum wavelet transform: fast algorithm and complete circuits (1998). arXiv:quant-ph/9809004 · Zbl 0939.42020
[13] Klappenecker, A., Roetteler, M.: Discrete cosine transforms on quantum computers (2001). arXiv:quant-ph/0111038 · Zbl 1337.81036
[14] Tseng, C.C., Hwang, T.M.: Quantum circuit design of \[8\times 88\]×8 discrete cosine transform using its fast computation flow graph. In: IEEE International Symposium on Circuits and Systems, 2005. ISCAS 2005, vol. 1, pp. 828-831, May 2005
[15] Venegas-Andraca, S., Bose, S.: Storing, processing and retrieving an image using quantum mechanics. In: Proceedings of the SPIE 2003 Conference on Quantum Information and Computation, pp. 137-147 (2003) · Zbl 1275.81020
[16] Le, P.Q., Dong, F., Hirota, K.: A flexible representation of quantum images for polynomial preparation, image compression, and processing operations. Quantum Inf. Process. 10, 63-84 (2011) · Zbl 1209.81066 · doi:10.1007/s11128-010-0177-y
[17] Li, H.S., Qingxin, Z., Lan, S., Shen, C.Y., Zhou, R., Mo, J.: Image storage, retrieval, compression and segmentation in a quantum system. Quantum Inf. Process. 12(6), 2269-2290 (2013) · Zbl 1267.81118 · doi:10.1007/s11128-012-0521-5
[18] Yuan, S., Mao, X., Xue, Y., Chen, L., Xiong, Q., Compare, A.: SQR: a simple quantum representation of infrared images. Quantum Inf. Process. 13(6), 1353-1379 (2014) · Zbl 1303.81056
[19] Le, P., Iliyasu, A., Dong, F., Hirota, K.: A flexible representation and invertible transformations for images on quantum computers. In: New Advances in Intelligent Signal Processing, vol. 372 of Studies in Computational Intelligence, pp. 179-202. Springer, Berlin (2011)
[20] Le, P.Q., Iliyasu, A.M., Dong, F., Hirota, K.: Strategies for designing geometric transformations on quantum images. Theor. Comput. Sci. 412, 1406-1418 (2011) · Zbl 1207.68427 · doi:10.1016/j.tcs.2010.11.029
[21] Le, P.Q., Iliyasu, A.M., Dong, F., Hirota, K.: Efficient color transformations on quantum images. JACIII 15, 698-706 (2011)
[22] Yan, F., Le, P.Q., Iliyasu, A.M., Sun, B., Garcia, J.A., Dong, F., Hirota, K.: Assessing the similarity of quantum images based on probability measurements. In: 2012 IEEE Congress on Evolutionary Computation (CEC), pp. 1-6, June 2012
[23] Zhou, R.-G., Wu, Q., Zhang, M.-Q., Shen, C.-Y.: Quantum image encryption and decryption algorithms based on quantum image geometric transformations. Int. J. Theor. Phys. 52(6), 1802-1817 (2013) · doi:10.1007/s10773-012-1274-8
[24] Iliyasu, A.M., Le, P.Q., Dong, F., Hirota, K.: Watermarking and authentication of quantum images based on restricted geometric transformations. Inf. Sci. 186(1), 126-149 (2012) · Zbl 1239.94009 · doi:10.1016/j.ins.2011.09.028
[25] Iliyasu, A.M., Le, P.Q., Yan, F., Sun, B., Garcia, J.A.S., Dong, F., Hirota, K.: A two-tier scheme for greyscale quantum image watermarking and recovery. Int. J. Innov. Comput. Appl. 5, 85-101 (2013) · doi:10.1504/IJICA.2013.053179
[26] Zhang, W.-W., Gao, F., Liu, B., Wen, Q.-Y., Chen, H.: A watermark strategy for quantum images based on quantum Fourier transform. Quantum Inf. Process. 12, 793-803 (2013) · Zbl 1264.81131 · doi:10.1007/s11128-012-0423-6
[27] Zhang, W.-W., Gao, F., Liu, B., Jia, H.-Y., Wen, Q.-Y., Chen, H.: A quantum watermark protocol. Int. J. Theor. Phys. 52(2), 504-513 (2013) · Zbl 1264.81127 · doi:10.1007/s10773-012-1354-9
[28] Iliyasu, A.M., Le, P.Q., Dong, F., Hirota, K.: A framework for representing and producing movies on quantum computers. Int. J. Quantum Inf. 09(06), 1459-1497 (2011) · Zbl 1275.81020 · doi:10.1142/S0219749911008015
[29] Sun, B., Le, P., Iliyasu, A., Yan, F., Garcia, J., Dong, F., Hirota, K.: A multi-channel representation for images on quantum computers using the RGB color space. In: 2011 IEEE 7th International Symposium on Intelligent Signal Processing (WISP), pp. 1-6, Sept 2011
[30] Sun, B., Iliyasu, A., Yan, F., Dong, F., Hirota, K.: An RGB multi-channel representation for images on quantum computers. J. Adv. Comput. Intell. Intell. Inform. 17(3), 404-417 (2013)
[31] Iliyasu, A.M.: Towards realising secure and efficient image and video processing applications on quantum computers. Entropy 15(8), 2874-2974 (2013) · Zbl 1337.81036 · doi:10.3390/e15082874
[32] Caraiman, S., Manta, V.: Image processing using quantum computing. In: v System Theory, Control and Computing (ICSTCC), pp. 1-6, Oct 2012
[33] Zhang, Y., Lu, K., Gao, Y., Wang, M.: NEQR: a novel enhanced quantum representation of digital images. Quantum Inf. Process. 12(8), 2833-2860 (2013) · Zbl 1283.81042 · doi:10.1007/s11128-013-0567-z
[34] Caraiman, S., Manta, V.: Quantum image filtering in the frequency domain. Adv. Electr. Comput. Eng. 13(3), 77-84 (2013) · doi:10.4316/AECE.2013.03013
[35] Caraiman, S., Manta, V.: Histogram-based segmentation of quantum images. Theor. Comput. Sci. 529, 46-60 (2014) · Zbl 1358.68309 · doi:10.1016/j.tcs.2013.08.005
[36] Zhang, Y., Lu, K., hui Gao, Y., Wang, M.: A quantum algorithm of constructing image histogram. World Acad. Sci. Eng. Technol. 7(5), 610-613 (2013)
[37] Caraiman, S., Manta, V.: Image representation and processing using ternary quantum computing. In: Tomassini, M., Antonioni, A., Daolio, F., Buesser, P. (eds.) Adaptive and Natural Computing Algorithms. Lecture Notes in Computer Science, vol. 7824, pp. 366-375. Springer, Berlin (2013)
[38] Zhang, Y., Lu, K., Gao, Y., Xu, K.: A novel quantum representation for log-polar images. Quantum Inf. Process. 12(9), 3103-3126 (2013) · Zbl 1273.81051 · doi:10.1007/s11128-013-0587-8
[39] Venegas-Andraca, S., Ball, J.: Processing images in entangled quantum systems. Quantum Inf. Process. 9, 1-11 (2010) · doi:10.1007/s11128-009-0123-z
[40] Latorre, J.: Image compression and entanglement (2005). arXiv:quant-ph/0510031 · Zbl 1067.81013
[41] Li, H.S., Zhu, Q., Zhou, R.G., Song, L., Yang, X.J.: Multi-dimensional color image storage and retrieval for a normal arbitrary quantum superposition state. Quantum Inf. Process. 13(4), 991-1011 (2014) · Zbl 1291.81100 · doi:10.1007/s11128-013-0705-7
[42] Li, H.S., Zhu, Q., Zhou, R.G., Li, M.C., Song, I., Ian, H.: Multidimensional color image storage, retrieval, and compression based on quantum amplitudes and phases. Inf. Sci. 273, 212-232 (2014) · doi:10.1016/j.ins.2014.03.035
[43] Grover, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing, STOC ’96, New York, NY, USA, pp. 212-219. ACM (1996) · Zbl 0922.68044
[44] Lanzagorta, M., Uhlmann, J.: Hybrid quantum computing: semicloning for general database retrieval. In: Proceedings of SPIE 2005: Quantum Information and Quantum Computation Conference, vol. 5815, pp. 78-86 (2005)
[45] Beach, G., Lomont, C., Cohen, C.: Quantum image processing (QuIP). In: Proceedings of 32nd Workshop on Applied Imagery Pattern Recognition, pp. 39-44, Oct 2003
[46] Nielsen, M., Chuang, I.: Quantum Computation and Quantum Information. Cambridge Series on Information and the Natural Sciences. Cambridge University Press, Cambridge (2000) · Zbl 1049.81015
[47] Deutsch, D., Jozsa, R.: Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. Ser. A Math. Phys. Sci. 439(1907), 553-558 (1992) · Zbl 0792.68058 · doi:10.1098/rspa.1992.0167
[48] Boneh, A., Hofri, M.: The coupon-collector problem revisited—a survey of engineering problems and computational methods. Stoch. Models 13(1), 39-66 (1997) · Zbl 0871.60009 · doi:10.1080/15326349708807412
[49] Leung, D.W.: Quantum computation by measurements. Int. J. Quantum Inf. 02(01), 33-43 (2004) · Zbl 1067.81013 · doi:10.1142/S0219749904000055
[50] Anders, J., Oi, D.K.L., Kashefi, E., Browne, D.E., Andersson, E.: Ancilla-driven universal quantum computation. Phys. Rev. A 82, 020301 (2010) · Zbl 1240.81012 · doi:10.1103/PhysRevA.82.020301
[51] Oliveira, D., Ramos, R.: Quantum bit string comparator: circuits and applications. Quantum Comput. Comput. 7, 17-26 (2007)
[52] Talbi, H., Batouche, M., Draa, A.: A quantum-inspired evolutionary algorithm for multiobjective image segmentation. Int. J. Eng. Nat. Sci. 1(2), 109-114 (2007)
[53] Zhou, C., Hu, Z., Wang, F., Fan, H., Shang, L.: Quantum collapsing median filter. In: 6th International Conference on Intelligent Computing, ICIC 2010, Changsha, China, Aug 18-21 2010. Proceedings, pp. 454-461 (2010) · Zbl 1207.68432
[54] Fu, X., Ding, M., Zhou, C., Sun, Y.: Multi-threshold image segmentation with improved quantum-inspired genetic algorithm. In: Proceedings of SPIE 7495, MIPPR 2009: Automatic Target Recognition and Image Analysis, 749518 (2009)
[55] Zhang, J., Li, H., Tang, Z., Lu, Q., Zheng, X., Zhou, J.: An improved quantum-inspired genetic algorithm for image multilevel thresholding segmentation. Math. Probl. Eng. 2014, 295402 (2014)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.