problems.mot
The mot package provides Re-Identification (Re-ID) post-processing algorithms.
The re-id algorithms are designed to enhance Multi-Object Tracking (MOT) pipelines. It is specifically intended to pair with Ultralytics YOLO trackers or similar object detection frameworks and leverages quantum-enhanced techniques and Binary Linear Programming (BLP) methods for advanced post-processing.
The goal of this module is to resolve identity switches and improve tracking consistency across frames by applying advanced optimization techniques after the initial tracking stage. While Ultralytics provides robust detection and tracking, identity consistency can degrade in challenging scenarios such as occlusions, crowded scenes, or long-term tracking. This algorithm addresses those issues through network flow optimization and QUBO-based formulations.
The re_id feature relies on a network flow optimization that can be approached in two ways: the classical method formulates the problem as a Mixed-Integer Linear Program (MILP), while the quantum approach casts it as a QUBO, which can be then be solved using various QUBO solvers from , including solvers that use a quantum backends.
The re_id feature relies on a network flow optimization problem that can be
approached in two ways:
Classical approach: Solves the problem using traditional Mixed-Integer Linear Program solving techniques.
Quantum approach: Casts the problem as a QUBO, which can be solved usingvarious QUBO solvers from our
tno.quantum.optimization.qubo.solverspackageincluding those using quantum backends.
The exact problem formulations can be found in the documentation of
run_classic() and run_qubo(). See below for basic
usage examples. See our examples overview for a more advanced example on end-to-end
usage with ultralytics.
Classically:
from tno.quantum.problems.mot import FlowReID from tno.quantum.problems.mot.dataset import load_dataset # Load detection sequence det_sequence = load_dataset() # Initialize FlowReID flow_reid_obj = FlowReID() # Run classic solver updated_sequence = flow_reid_obj.run_classic(det_sequence) print("Classic Re-ID completed.") print(f"Number of frames processed: {len(updated_sequence)}")This prints the following result:
Classic Re-ID completed. Number of frames processed: ...
Quantum:
from tno.quantum.problems.mot import FlowReID from tno.quantum.problems.mot.dataset import load_dataset # Load detection sequence det_sequence = load_dataset() # Initialize FlowReID flow_reid_obj = FlowReID() # Configure quantum solver (Simulated Annealing) solver_config_SA = { "name": "simulated_annealing_solver", "options": {"num_reads": 100, "num_sweeps": 200}, } # Alternatively, configure Quantum Annealing solver config_QA = { "name": "d_wave_sampler_solver", "options": { "num_reads": 500, "annealing_time": 1000, "reuse_embedding": True} } # Run QUBO-based solver updated_sequence = flow_reid_obj.run_qubo(det_sequence, solver_config_SA) print("Quantum Re-ID completed.") print(f"Number of frames processed: {len(updated_sequence)}")This prints the following result:
Quantum Re-ID completed. Number of frames processed: ...
- class tno.quantum.problems.mot.DetectionSequence(det_sequence)[source]
-
Class containing a sequence of FrameDets.
- det_sequence
List of FrameDets, each containing detections for a single frame.
- classmethod from_dataframe(detections)[source]
Creates an instance of the class from a pandas DataFrame.
- Parameters:
detections (
DataFrame) – A DataFrame containing detections. Uses the from_dataframe method from the FrameDets class, so the DataFrame should be structured as described in the FrameDets class.- Return type:
- Returns:
An instance of DetectionSequence consisting of FrameDets for each frame.
- class tno.quantum.problems.mot.FlowReID[source]
Bases:
objectClass to initialize the flow re-identification object.
- pick_sequences(det_sequence, min_len=50, max_len=80)[source]
Picks frame sequences to run re-id on.
Sequences containing new id’s are selected for the re-id module. The sequences are checked for compatibility with the re-id module.
- run_classic(det_sequence)[source]
Runs re-id using a classic MILP solver from SciPy.
The classic approach solves the following network flow model:
Capacity constraint: At most one unit of flow per edge.
Flow conservation: Incoming flow equals outgoing flow for intermediate nodes.
Boundary condition: One unit of flow originates from each initial node.
This approach uses SciPy’s MILP solver
milp().The decision variables are:
1. \(x_{ijt} \in \{0, 1\}\) representing whether detection \(i\) in frame \(t\) is associated with detection \(j\) in frame \(t+1\).
\(x_{ijt} = 1\) Detection \(i\) at time \(t\) and detection \(j\) at time \(t+1\) belong to the same object.
\(x_{ijt} = 0\) No association.
2. \(y_{ij} \in \{0, 1\}\) representing additional edges introduced when the number of detections in intermediate frames drops below the initial frame count.
\(y_{ij} = 1\) Detection \(i\) in frame \(f_1\) is linked to detection \(j\) in frame \(f_2\) to maintain feasibility.
\(y_{ij} = 0\) No link between these detections.
When the number of detections drops below the initial layer, additional edges are introduced between frames \(f_1\) and \(f_2\) to maintain feasibility:
\[\begin{split}\begin{split} & \sum_{j=1}^{nd_{f_1+1}} x_{ijf_1} + \sum_{j=1}^{nd_{f_2}} y_{ij} \leq 1, \quad i = 1, \dots, nd_{f_1} \\ & \sum_{j=1}^{nd_{f_1-1}} x_{jif_1-1} = \sum_{j=1}^{nd_{f_1+1}} x_{ijf_1} + \sum_{j=1}^{nd_{f_2}} y_{ij}, \quad i = 1, \dots, nd_{f_1} \\ & \sum_{j=1}^{nd_{f_2-1}} x_{jif_2-1} + \sum_{j=1}^{nd_{f_1}} y_{ji} = \sum_{j=1}^{nd_{f_2+1}} x_{ijf_2}, \quad i = 1, \dots, nd_{f_2}. \end{split}\end{split}\]- Parameters:
det_sequence (
DetectionSequence) – detection sequence to re-id.- Return type:
- Returns:
The detection sequence after re-id.
- run_continuous_reid(det_sequence)[source]
Runs re-id continuously.
- Parameters:
det_sequence (
DetectionSequence) – detection sequence- Return type:
- Returns:
The detection sequence after re-id on several frame sequences.
- run_qubo(det_sequence, solver_config=None)[source]
Runs re-id using a qubo model.
Instead of handling constraints explicitly, we add penalty terms to the objective function:
\[\begin{split}\\\mathbf{c}^T \mathbf{x} + \lambda H(\mathbf{x})\end{split}\]\(\mathbf{c}^T \mathbf{x}\): Original cost function.
\(H(\mathbf{x})\): Penalty function encoding constraints.
\(\lambda\): Penalty weight ensuring feasibility.
By tuning \(\lambda\), minimizing this unconstrained quadratic objective yields feasible solutions.
For a constraint of the form \(\mathbf{a}^T \mathbf{x} = b\):
\[\begin{split}\\H_1(\mathbf{x}) = (\mathbf{a}^T \mathbf{x} - b)^2\end{split}\]This penalty is zero when the constraint is satisfied and positive otherwise.
For a constraint of the form \(\sum{x_i} \leq 1\):
\[\begin{split}\\H_2( \mathbf{x} ) = \sum_{i<j}{x_i x_j}\end{split}\]This ensures that at most one variable in the set can take the value 1.
- Parameters:
det_sequence (
DetectionSequence) – detection sequence to re-id.solver_config (
SolverConfig|Mapping[str,Any] |None) – Configuration for the qubo solver to use. Must be aSolverConfigor a mapping with"name"and"options"keys. IfNone(default) is provided, theSimulatedAnnealingSolverwill be used, i.e.{"name": "simulated_annealing_solver", "options": {}}.
- Return type:
- Returns:
The detection sequence after re-id. If the solver did not converge to a feasible solution, returns the input detection sequence.
- class tno.quantum.problems.mot.FrameDets[source]
Bases:
objectClass containing all detections in one frame.
- frame_number
Frame number.
- conf
Confidence scores of the detections.
- cls
Classes of the detections.
- xywh
Box coordinates with shape (n_boxes, 4) using xywh format (coord of center, width, height).
- xyxy
Box coordinates with shape (n_boxes, 4) using xyxy format (top left, bottom right).
- ids
Ids associated with the box.
- size
Number of detections in the frame.
- classmethod from_dataframe(detections)[source]
Creates an instance of the class from a pandas DataFrame.
- Parameters:
detections (
DataFrame) –A DataFrame containing detections. The columns should be structured as follows:
0: Frame number
1: Detection ID (not used in this implementation)
2: x center of the bounding box
3: y center of the bounding box
4: Width of the bounding box
5: Height of the bounding box
6: Confidence score of the detection
- Return type:
- Returns:
An instance of FrameDets with detections for a single frame.
- classmethod from_ultralytics_tracker(tracks)[source]
Creates an instance of the class from the output of the ultralytics tracker.
- Parameters:
tracks (
ndarray[tuple[Any,...],dtype[float64]]) –An array of shape (n_tracks, 6) where each row contains:
x1: x coordinate of the top-left corner
y1: y coordinate of the top-left corner
x2: x coordinate of the bottom-right corner
y2: y coordinate of the bottom-right corner
id: Detection ID
conf: Confidence score
- Return type:
- Returns:
An instance of FrameDets with detections for a single frame.
- tno.quantum.problems.mot.calculate_cost(det_sequence)[source]
Calculates the cost array of a detection sequence.
The cost array is computed based on the Intersection over Union (IoU) between bounding boxes in consecutive frames of a detection sequence.
- Parameters:
det_sequence (
DetectionSequence) – A sequence of detections (FrameDets) for each frame, where each FrameDets contains bounding boxes in the format xyxy.- Return type:
- Returns:
The cost values computed between all pairs of bounding boxes in consecutive frames, flattened into a 1D array.
- tno.quantum.problems.mot.compute_iou(box1, box2)[source]
Computes the Intersection over Union (IoU) between two bounding boxes.
The bounding boxes are represented in the format [x, y, x, y], with the first x, y being the bottom-left corner coordinates and the second pair being the top-right corner coordinates. The IoU value is a number between 0 and 1, where 0 means no overlap and 1 means complete overlap.
- tno.quantum.problems.mot.ultralytics_track(det_sequence, tracker)[source]
Runs the ultralytics tracking algorithm on the already extracted detections.
- Parameters:
det_sequence (
DetectionSequence) – sequence of detections per frame.tracker (
BYTETracker) – tracker object.
- Return type:
- Returns:
An updated DetectionSequence with id’s.