| As one of the important branches of information science, digital image processing is the core procedure in many applications, including weapon navigation, medical care and web retrieval. With recent dramatic developments in image sensors, the numbers of images are inceasing rapidly and the image size is becoming larger. However, classical computing has nearly reached its performance bound, which results in the often overwhelming runtime and the unacceptable accuracy of classical image-processing algorithms. Therefore, the exploration for novel models of high performance computing has never been stopped.As the most promising candidate to overcome the limitations of classical computing, quantum computing has been a hot topic in the near decades. Especially after the two most representative researches, namely, the quantum integer factoring algorithm designed by P. Shor in 1994 and the Grover’s quantum search algorithm in 1996, the amazing power of quantum computation has been witnessed, which have motivated more researchers to re-explore our world from the quantum perspective. However, image processing based on quantum mechanics is still in its infancy; most researches concentrate the quantum representation of digital images while there are few quantum algorithms to deal with the complex image-processing tasks. Therefore, how to use quantum mechanics to improve the performance of classical image processing is still an open problem.To cope with this problem, an entire quantum image-processing system is constructed in this dissertation. Using the excellent properties of quantum mechanics, the system can perform the image-processing tasks with better runtime and higher accuracy than the classical counterparts. From quantum image storage, to quantum image pre-processing, finally to quantum image classification, this quantum image-processing system consists of three bottom-to-up levels:1. Quantum image representationIn order to utilize quantum mechanics to perform image processing, the information of images should be stored into quantum state firstly. O ne of the common drawbacks of all the state-of-the-art quantum image representations is to use the quantum amplitude to store the color information of image pixels. In this dissertation, the novel enhanced quantum representation model, NEQR, is designed which uses the basis state of quantum sequence to store the color information for the first time. Compared with the nearest model FRQI, NEQR can perform more kinds of quantum image geometric and color transformations, and achieve 1.5 times of the improvement ratio of quantum image compression. Meanwhile, the classical image could be re-shaped from NEQR.The new model is available for all the pixel images. Based on NEQR, an improved model QUALPI is designed which is the first model to store the log-polar images. Therefore, the new quantum image representation model is more suitable to be the basis of the whole quantum image-processing system.2. Quantum image pre-processing algorithmsThe pixel information of digital image is difficult to understand. Therefore, based on the quantum image models, some quantum image pre-processing algorithms are designed, which are used to extract more efficient information from quantum images rather than pixels.In this level, four representative quantum image pre-processing algorithms are discussed respectively:1) Quantum algorithm for edge extraction. The new algorithm uses the Grover’s technique to find out all the pixels of which the edges consist. Compared with Sobel, the famous classical edge extraction algorithm, our new algorithm can achieve an approximately exponential speedup.2) Quantum image histogram construction. In this algorithm, all the pixels with the same color will be grouped and counted via a quantum accelerator. Performance comparison reveals that the new algorithm could achieve an approximately quadratic speedup than the classical method.3) Local feature extraction from quantum images. By designing the quantum image adder and subtracter, the gradient computation of all the pixels of images can be done simultaneously. There is an approximately exponential speedup achieved by the newly proposed algorithm, compared with the traditional feature detectors.4) Quantum image registration algorithm. In this algorithm, the quantum state of the reference image is firstly expanded to an image set in which each element represents a transformed result of the reference image. And then Grover’s technique is utilized to find out the observed image in the set. Comparison with the classical brute- force image registration method demonstrates that our quantum algorithm can achieve a quartic speedup.3. Quantum image classification algorithms based on image similarity.Image classification is one of the important image-processing tasks. Graph-based image classification is an efficient method in this field. In the second level of the quantum system, quantum feature extractor has been studied, which is just the bridge between quantum image and graph. Therefore, in this level, quantum walk on graphs is explored to measure the image similarity which will be used to perform image classification.In this dissertation, a novel quantum algorithm, Qwalk, is designed to detect the maximum common sub-graph isomorphism based on discrete-time quantum walk. Via the exploration on the destructive interference of quantum walk, it is discovered that all the isomorphic sub-structures between two input graphs can be fast located in one run of discrete-time quantum walk on the auxiliary graph. Through merging these sub-structures, an approximate result can be obtained. Extensive experiments show that Qwalk achieves better accuracy, universality and robustness compared with the state-of-the-art approximate methods. Meanwhile Qwalk is the fastest algorithm among all the methods for general graphs.Based on discrete-time quantum walk, a novel graph kernel, QW, is also proposed in this level, which is a tailored tool to measure graph similarity. Via the exploration on the constructive interference of quantum walk, it is discovered that even the slight dissimilarity can be amplified by quantum walk so that the graph features extracted from quantum walk have powerful discrimination. To design the new quantum graph kernel, the state transformation of quantum walk is used to build the feature vector for every graph and then graph similarity locates at the vector distance. Through comparisons with the state-of-the-art graph kernels, QW yields approximately 5%-15% accuracy improvement in graph classification on some real- world databases. Moreover, some similar and non-isomorphic unlabeled graphs which cannot be classified by the traditional kernels, including the cospectal graphs and regular graphs, can be distinguished by QW. To overcome the high cost problem of QW, a fast computation method is designed for the first time. Based on this fast method, QW can achieve the same time consumption with the random walk kernel. Therefore, QW is proven to be more effective than others in graph matching.From the images to the result of image classification, the whole quantum image-processing system could replace the classical image processing and achieve better runtime and accuracy. Meanwhile, some principles of the construction of this system, such as designing from bottom to up and beginning with quantum model for information storage, are also very significant for the research on how to use quantum mechanics in other branches of information processing.
|
PDF Full Text Request