Quantum algorithm for visual tracking

Abstract

Visual tracking (VT) is the process of locating a moving object of interest in a video. It is a fundamental problem in computer vision, with various applications in human-computer interaction, security and surveillance, robot perception, traffic control, etc. In this paper, we address this problem for the first time in the quantum setting, and present a quantum algorithm for VT based on the framework proposed by Henriques et al. [IEEE Trans. Pattern Anal. Mach. Intell., 7, 583 (2015)]. Our algorithm comprises two phases: training and detection. In the training phase, in order to discriminate the object and background, the algorithm trains a ridge regression classifier in the quantum state form where the optimal fitting parameters of ridge regression are encoded in the amplitudes. In the detection phase, the classifier is then employed to generate a quantum state whose amplitudes encode the responses of all the candidate image patches. The algorithm is shown to be polylogarithmic in scaling, when the image data matrices have low condition numbers, and therefore may achieve exponential speedup over the best classical counterpart. However, only quadratic speedup can be achieved when the algorithm is applied to implement the ultimate task of Henriques's framework, i.e., detecting the object position. We also discuss two other important applications related to VT: (1) object disappearance detection and (2) motion behavior matching, where much more significant speedup over the classical methods can be achieved. This work demonstrates the power of quantum computing in solving computer vision problems.

arXiv comment10 pages, 9 figures

References in corpus (22)

• High-Speed Tracking with Kernelized Correlation Filters
• Quantum Machine Learning
• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum algorithm for solving linear systems of equations
• Quantum support vector machine for big data classification
• Quantum fingerprinting
• Quantum algorithms: an overview
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Toward the first quantum simulation with quantum speedup
• Quantum Data Fitting
• Prediction by linear regression on a quantum computer
• Learning the quantum algorithm for state overlap
• Creating superpositions that correspond to efficiently integrable probability distributions
• The SWAP test and the Hong-Ou-Mandel effect are equivalent
• A quantum Fredkin gate
• Quantum Algorithm for Linear Regression
• Quantum machine learning for quantum anomaly detection
• Quantum Discriminant Analysis for Dimensionality Reduction and Classification
• Measuring the Renyi entropy of a two-site Fermi-Hubbard model on a trapped ion quantum computer
• Quantum algorithm for association rules mining
• Quantum algorithm for association rules mining
• Machine learning \& artificial intelligence in the quantum domain

Cited by in corpus (14)

• Quantum generative adversarial network for generating discrete distribution
• Quantum data compression by principal component analysis
• Quantum walk-based portfolio optimisation
• Improved quantum algorithm for A-optimal projection
• Quantum algorithms for anomaly detection using amplitude estimation
• A brief introduction to quantum algorithms
• Quantum algorithm for Neighborhood Preserving Embedding
• Experimental implementation of quantum algorithm for association rules mining
• Quantum Alternating Operator Ansatz for Solving the Minimum Exact Cover Problem
• Quantum Algorithm for Unsupervised Anomaly Detection
• Ancilla-Error-Transparent Controlled Beam Splitter Gate
• Everything You Always Wanted to Know About Quantum Circuits
• A Critical and Moving-Forward View on Quantum Image Processing
• Quantum Algorithms for Prediction Based on Ridge Regression