QSobel:A novel quantum image edge extraction algorithm  

作　　者：ZHANG Yi LU Kai GAO YingHui 

机构地区：[1]Science and Technology on Parallel and Distributed Processing Laboratory,National University of Defense Technology [2]College of Computer,National University of Defense Technology [3]College of Electronic Science and Engineering,National University of Defense Technology

出　　处：《Science China(Information Sciences)》2015年第1期104-116,共13页中国科学（信息科学）（英文版）

基　　金：supported in part by the National High-tech R&D Program of China (863 Program) (Grant Nos. 2012AA01A301 and 2012AA010901);supported by the National Natural Science Foundation of China (Grant Nos. 61170261 and 61103082);the Innovation Fund Sponsor Project of Excellent Postgraduate Student (Grant Nos. B120601 and CX2012A002)

摘　　要：Edge extraction is an indispensable task in digital image processing. With the sharp increase in the image data, real-time problem has become a limitation of the state of the art of edge extraction algorithms.In this paper, QSobel, a novel quantum image edge extraction algorithm is designed based on the flexible representation of quantum image（FRQI） and the famous edge extraction algorithm Sobel. Because FRQI utilizes the superposition state of qubit sequence to store all the pixels of an image, QSobel can calculate the Sobel gradients of the image intensity of all the pixels simultaneously. It is the main reason that QSobel can extract edges quite fast. Through designing and analyzing the quantum circuit of QSobel, we demonstrate that QSobel can extract edges in the computational complexity of O（n2） for a FRQI quantum image with a size of2 n × 2n. Compared with all the classical edge extraction algorithms and the existing quantum edge extraction algorithms, QSobel can utilize quantum parallel computation to reach a significant and exponential speedup.Hence, QSobel would resolve the real-time problem of image edge extraction.Edge extraction is an indispensable task in digital image processing. With the sharp increase in the image data, real-time problem has become a limitation of the state of the art of edge extraction algorithms.In this paper, QSobel, a novel quantum image edge extraction algorithm is designed based on the flexible representation of quantum image（FRQI） and the famous edge extraction algorithm Sobel. Because FRQI utilizes the superposition state of qubit sequence to store all the pixels of an image, QSobel can calculate the Sobel gradients of the image intensity of all the pixels simultaneously. It is the main reason that QSobel can extract edges quite fast. Through designing and analyzing the quantum circuit of QSobel, we demonstrate that QSobel can extract edges in the computational complexity of O（n2） for a FRQI quantum image with a size of2 n × 2n. Compared with all the classical edge extraction algorithms and the existing quantum edge extraction algorithms, QSobel can utilize quantum parallel computation to reach a significant and exponential speedup.Hence, QSobel would resolve the real-time problem of image edge extraction.

关 键 词：edge extraction quantum image processing FRQI SOBEL computational complexity 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术] TP391[自动化与计算机技术—计算机科学与技术]