Quantum algorithm for visual tracking

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 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.

Figure 1

Schematic of visual tracking by training and detection. The (red) circles represent the object in the training and detection frame. The (black) rectangles in the training frame denote sample image patches for training, and those in the detection frame denote the candidate image patches for detection. The training-detection procedure is run successively over contiguous frames to track the object in the video.

Figure 2

Quantum circuit for the training phase. Here the numbers 1, 2, 3, and 4 denote the sequence of four steps of the training phase, “/” denotes a bundle of wires, $H$ denotes the Hadamard operation, $FT$ represents the quantum Fourier transformation [6], and controlled $R_0$ denotes the controlled rotation in the training step (3).

Figure 3

Quantum circuit for generating $\left|\widehat{\mathbf{y}}\right.〉$. Here the numbers 1, 2, 3, and 4 denote the four sequential steps of the detection phase, and controlled $R_1$ denotes the controlled rotation in the detection step (3).

Figure 4

Quantum circuit of swap test for estimating the overlap, $\mathrm{Tr}\left({\rho }_1{\rho }_2\right)$, between two states with density matrices ${\rho }_1$ and ${\rho }_2$, where SWAP denotes the SWAP unitary operation implemented by a series of elementary one-qubit or two-qubit gates [6]. The probability of obtaining the measurement outcome $\left|0\right.〉$ after measuring the top ancilla qubit is $\frac{1+\mathrm{Tr}\left({\rho }_1{\rho }_2\right)}{2}$, which reveals the estimate of $\mathrm{Tr}\left({\rho }_1{\rho }_2\right)$ by repeating the circuit for a sufficient number of times. In our case, we are to estimate the overlap between the two pure states ${\rho }_1=\left|\widehat{\mathbf{y}}\rangle \langle \widehat{\mathbf{y}}\right|$ and ${\rho }_2=\left|\mathbf{1}\rangle \langle \mathbf{1}\right|, \mathrm{Tr}\left({\rho }_1{\rho }_2\right)=P_1={\left|\langle \widehat{\mathbf{y}}\left|\mathbf{1}\right.〉\right|}^2$.

Figure 5

Figure (a) is the training frame, where the object is placed at the center. The black (bigger) rectangle denotes the image patch and the red (smaller) rectangle denotes the object. Figure (b) is the detection frame where the object moves 3 pixels to the right relative to that in (a) but still exists in the patch. Figure (c) is the detection frame where the object disappears relative to that in (b), and the dashed rectangle denotes the position where the object should be. All the three frames are one-dimensional gray scale images of 50 pixels. The patch and the object are of 20 pixels and 10 pixels, respectively.

Figure 6

Comparison between the 50 values of $P_1$ for the case where the object exists and those for the case where the object disappears after running the experiment in Fig. 5 for 50 times.

Figure 7

Simple example for motion behavior matching. Here the rectangle with blue border denotes the frame, the red circles denote the object, the black arrowed lines correspond to the $Z$-shape motion template, and the numbers $1,2,...,7$ are to mark seven selected positions in the template. The initial frame of the video contains the object located in position 1. If the object motion behavior in the video matches the template, the object in seven appropriately selected frames of the video should be located at these seven positions.