A quantum moving target segmentation algorithm for grayscale video

Wenjie Liu, Lu Wang, Qingshan WuarXiv 2023 · DOI · arXiv

Introduction

Moving Target Segmentation (MTS) is a fundamental task in computer vision, essential for applications ranging from autonomous traffic monitoring to security surveillance. As video resolutions and frame rates continue to increase, classical computational architectures face significant bottlenecks in real-time processing. Quantum computing offers a potential solution through quantum parallelism. This paper presents a novel quantum algorithm for segmenting moving targets in grayscale videos, utilizing a three-frame difference method to achieve exponential speedup over classical approaches.

Methodology

Quantum Video Representation

The algorithm utilizes the Quantum Video Novel Enhanced Quantum Representation (QVNEQR), an extension of the NEQR model. QVNEQR encodes grayscale values and spatial-temporal coordinates (pixel positions and frame indices) into the basis states of a quantum system. This representation allows for efficient pixel-wise operations across the entire video volume simultaneously.

Three-Frame Difference and QAS

To avoid the "ghosting" artifacts common in two-frame subtraction, the researchers implemented a three-frame difference method. This approach compares a target frame ($k$) with both its predecessor ($k-1$) and successor ($k+1$).

A critical component of this process is the Quantum Absolute Value Subtractor (QAS). Because quantum circuits cannot easily represent negative values in this context, the QAS uses a custom-designed Quantum Comparator (QC) and CSWAP gates to ensure the smaller grayscale value is always subtracted from the larger one, yielding an absolute difference.

Architecture of the Quantum Absolute Value Subtractor (QAS) incorporating the custom Quantum Comparator (QC).

Algorithmic Workflow

  1. Cycle Shift Transformation (CT): Aligns adjacent frames in superposition.
  2. Quantum Binarization (QB): Compares frame differences against a threshold ($T$) to generate a binary motion mask.
  3. Quantum AND Operation: Uses Toffoli gates to intersect the results of the two difference calculations, isolating the moving target from background noise.

Key Results and Performance Analysis

Resource Efficiency

The researchers developed a highly optimized quantum comparator that significantly reduces the computational overhead compared to previous state-of-the-art designs. As shown in the comparison table below, the proposed comparator achieves a quantum cost of $7n+6$, where $n$ is the number of qubits representing grayscale levels. This is a substantial improvement over existing methods that require costs as high as $30n-15$.

Comparison of resource requirements and quantum cost across different quantum comparator designs.

Computational Complexity

The primary advantage of this quantum algorithm is its efficiency. The total complexity is $O(n^2 + q)$, where $n$ relates to image dimensions and $q$ to grayscale depth. In contrast, classical algorithms must iterate through every pixel and frame, resulting in an exponential complexity of $O(2^{2n+m})$. This transition from exponential to polynomial time complexity represents a significant "quantum advantage."

Experimental Validation

The algorithm was validated using the ibm-qasm-simulator on the IBM Q cloud platform. Simulations on a $4 \times 4$ pixel, 4-frame synthetic video demonstrated that the quantum output perfectly matched classical three-frame difference results, confirming the theoretical soundness of the circuit design.

Conclusion

This research demonstrates a viable path for real-time video processing on future quantum hardware. By optimizing the quantum comparator and leveraging the QVNEQR model, the algorithm achieves significant reductions in both qubit requirements and gate operations. Future work will focus on adapting the algorithm for dynamic backgrounds and extending the framework to support multi-channel RGB color video.

Summary updated

BibTeX
@misc{liu2023quantum,
  author = {Wenjie Liu and Lu Wang and Qingshan Wu},
  title = {{A quantum moving target segmentation algorithm for grayscale video}},
  year = {2023},
  eprint = {2310.03038},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2310.03038},
}
Figure