A quantum algorithm for the segmentation of a moving target in grayscale videos

Computer vision algorithms have become increasingly advanced over the past decades, enabling the development of sophisticated technologies to monitor specific environments, detect objects of interest in video footage and uncover suspicious activities in CCTV recordings. Some of these algorithms are specifically designed to detect and isolate moving objects or people of interest in a video, a task known as moving target segmentation.

While some conventional algorithms for moving target segmentation attained promising results, most of them perform poorly in real-time (i.e., when analyzing videos that are not pre-recorded but are being captured in the present moment). Some research teams have thus been trying to tackle this problem using alternative types of algorithms, such as so-called quantum algorithms.

Researchers at Nanjing University of Information Science and Technology and Southeast University in China recently developed a new quantum algorithm for the segmentation of moving targets in grayscale videos. This algorithm, published in Advanced Quantum Technologies, was found to outperform classical approaches in tasks that involve the analysis of video footage in real-time.

"Our previous work has been devoted to quantum image segmentation algorithms and we have published several papers, but those are all on static targets," Wenjie Liu, one of the researchers who carried out the study, told Tech Xplore. "We wondered if we could further segment moving targets and extend the application from image to video. We checked the related research on quantum video and found that the research in this area is scarce."

The algorithm developed by Liu and his colleagues utilizes quantum mechanical processes to rapidly segment moving targets in grayscale videos. This segmented person or object can then be recognized as a target and monitored using additional computational methods.

"First, we store the classical grayscale video into some qubits, let the frame and pixel positions be in superposition state, and let the grayscale values of the pixels be entangled with them to obtain the quantum video V_k," Liu said. "Then the video is circularly shifted to obtain two other new videos, V_k-1 and V_k+1, in which the positions of the frames are shifted forward and backward by one unit, respectively, compared to the original video. These three videos share positional qubits. The two newly obtained videos are then allowed to do absolute value subtraction operation with the original video, i.e., B_k-1=|V_k-V_k-1|,B_k+1=|V_k-V_k+1|. Then B_k-1 and B_k+1 are binarized to get b_k-1 and b_k+1. b_k-1 and b_k+1 are added to get the final result, and then measurements are performed to restore to the classic video."

To allow their algorithm to discriminate between threshold and grayscale values, Liu and his colleagues incorporated a so-called quantum comparator that requires less computational power. In addition, the team designed various quantum circuit units utilizing fewer quantum bits and quantum gates.

"The complete quantum circuit was assembled based on these units," Liu said. "Compared with the classic counterpart, we attained an exponential speedup, and the algorithm's complexity is also superior to the existing quantum algorithms, The pixel positions in an image are stored into quantum bits in the superposition state, and then the quantum bits of gray value information are entangled with the position information quantum bits so that an image or a video is in the superposition state. The computational operation on a pixel in the image (or video) in the superposition state is equivalent to the computational operation on the whole image (or the whole video), so that the computational complexity can be reduced exponentially."

Liu and his colleagues evaluated their algorithm in a series of tests, comparing its performance to that of a classical algorithm for moving target segmentation. Their algorithm was found to be significantly faster than classical models, while retaining the same accuracy.

"The complexity of the algorithm is exponentially decreased compared to its classical counterpart," Liu said. "In addition, we designed a quantum comparator with fewer quantum gates and qubits, which can be used in any task that requires comparison of values and can effectively reduce the complexity of the algorithm."

In the future, the algorithm created by this team of researchers could be developed further and tested on more real-world footage. Concurrently, this work could inspire the development of new highly performing quantum algorithms for other advanced computer vision applications.

"Currently, our research focuses on how to process images more simply in the spatial domain with quantum circuits, and the effect can be further improved," Liu added. "In the future, to get better processing results, we will expand our research to processing images with quantum neural networks. In addition, the existing quantum technology cannot realize the use of large-scale qubits in the short term, so the hybrid classical-quantum neural network is also a better choice."

© 2023 Science X Network