Anirudh1950's picture
Publish project from GitHub
740910f verified
|
Raw History Blame Contribute Delete
7.37 kB
---
tags:
- depth-estimation
- stereo-vision
- path-planning
- opencv
---
> **Project page:** [https://huggingface.co/spaces/Anirudh1950/Stereo-Vision-Multi-Agent-Pathfinding](https://huggingface.co/spaces/Anirudh1950/Stereo-Vision-Multi-Agent-Pathfinding)
# Computer Vision & Pathfinding Research
This repository contains my solutions for the **Vecros Technical Assignment**. It implements research-grade algorithms for Stereo Vision (Problem 1) and Multi-Agent Pathfinding (Problem 2).
The focus has been on **mathematical robustness** and **optimality** rather than just getting code to run.
---
## 🛠️ Table of Contents
- [Problem 1: Stereo Vision (SfM Backend)](#problem-1-stereo-vision-structure-from-motion)
- [Problem 2: 3D Multi-Agent Pathfinding](#problem-2-3d-multi-agent-pathfinding)
- [Installation](#installation)
- [Usage](#usage)
- [Results](#results)
---
## ⚡ Quick Reference (Run Commands)
Copy-paste these commands to verify the solution:
### 1. Problem 1: Stereo Vision (All Modes)
Runs SGBM Dense Depth + MAGSAC++ Pose + Sparse Bundle Adjustment.
**Option A: Middlebury Dataset (Default)**
```bash
python main.py --problem 1 --dataset middlebury --data-path "./Dataset/Adirondack-perfect/Adirondack-perfect"
```
**Option B: Custom Image Pair**
Run on any two images (calibration optional, defaults to approx).
```bash
python main.py --problem 1 --dataset custom --img1 "data/left.jpg" --img2 "data/right.jpg"
```
**Option C: KITTI Odometry Dataset**
Requires `pykitti` and a downloaded sequence (e.g., Sequence 00).
```bash
python main.py --problem 1 --dataset kitti --data-path "path/to/kitti/dataset" --sequence 00
```
### 2. Problem 2: Pathfinding (All Solver Modes)
**Option A: Compare Mode (Recommended)**
Runs both Fast + Optimal solvers and benchmarks them.
```bash
python main.py --problem 2 --solver compare --grid-size 50
```
**Option B: CBS Only (Optimal)**
Runs only the Conflict-Based Search (guaranteed shortest path).
```bash
python main.py --problem 2 --solver cbs --grid-size 50
```
**Option C: Optimized Only (Fast)**
Runs only the fast heuristics-based solver (no optimality guarantee).
```bash
python main.py --problem 2 --solver optimized --grid-size 50
```
### 3. Problem 2: Pathfinding (Custom Scenario)
Runs a 4-agent conflict scenario (or any number).
```bash
python main.py --problem 2 --paths "0,0,0:10,10,10" "10,0,0:0,10,0" "5,5,0:5,5,10" "0,5,5:10,5,5"
```
---
## Problem 1: Stereo Vision (Structure-from-Motion)
This is a complete Visual Odometry backend. Instead of simple disparity mapping, I built a pipeline that performs **Sparse Bundle Adjustment** to recover optimal camera poses.
### Key Algorithms
1. **Feature Detection**: SIFT with **Sub-Pixel Refinement** (`cv2.cornerSubPix`) for high-precision keypoints.
2. **Matching**: FLANN-based matching with Lowe's Ratio Test (0.75).
3. **Pose Estimation**: **MAGSAC++** (`cv2.USAC_MAGSAC`), which is significantly more robust to outliers than standard RANSAC.
4. **Optimization (The "Special Sauce")**:
* **True Bundle Adjustment**: A custom `scipy` solver that optimizes **Pose ($R,t$) + 3D Points ($X$)** simultaneously.
* **Sparse Jacobian**: Implemented the analytical sparsity pattern to solve for thousands of parameters in milliseconds.
* **Trajectory Smoothing**: Exponential Moving Average (EMA) to clean up jitter in video sequences.
5. **Moving Object Rejection**: Uses Epipolar Residuals to filter out dynamic actors (humans, cars) that violate the static geometry constraint.
---
## Problem 2: 3D Multi-Agent Pathfinding
A swarm navigation system capable of planning collision-free paths for multiple agents in a dense 3D grid.
### Key Algorithms
1. **Conflict-Based Search (CBS)**:
* This is an **Optimal Solver**. It guarantees the mathematically shortest path for the swarm (minimizing Flowtime or Makespan).
* Unlike simple Prioritized Planning (which fails in tight spaces), CBS resolves conflicts by exploring a constraint tree.
2. **Constraint Checking**:
* **Vertex Conflicts**: Prevents two agents from occupying the same $(x,y,z)$ at time $t$.
* **Edge Conflicts**: Prevents agents from "swapping" places ($u \to v$ vs $v \to u$) to ensure physical feasibility.
3. **Visualization**:
* Generates an interactive 3D HTML animation using Plotly.
---
## 🔧 Installation
### 1. Clone & Install Dependencies
```bash
pip install -r requirements.txt
```
*(Requires: `numpy`, `opencv-python`, `scipy`, `matplotlib`, `plotly`)*
### 2. Dataset Setup
I tested this on the **Middlebury 2014 Stereo Dataset**.
- Ensure your data is in `Dataset/Adirondack-perfect/Adirondack-perfect/`.
- Required files: `im0.png`, `im1.png`, `calib.txt`.
---
## 🚀 Usage
### Run Problem 1 (Stereo Vision)
```bash
# Run on the included Middlebury dataset
python main.py --problem 1 --dataset middlebury --data-path "./Dataset/Adirondack-perfect/Adirondack-perfect"
```
*Check the console for Bundle Adjustment convergence stats!*
### Run Problem 2 (Pathfinding)
```bash
# Run the "Comparison Mode" (Fast Heuristic vs Optimal CBS)
python main.py --problem 2 --solver compare --grid-size 50
# Run a Custom Scenario (3 Agents)
# Format: "startX,startY,startZ:endX,endY,endZ"
python main.py --problem 2 --paths "0,0,0:10,10,10" "10,0,0:0,10,0" "5,5,0:5,5,10"
```
---
## 📊 Results
All outputs are saved to the `results/` directory.
### Problem 1 Output (`results/problem1/`)
**1. Dense Disparity Map (SGBM)**
![Dense Disparity](results/problem1/disparity_dense.png)
**2. Robust Feature Matching (Left/Right)**
![Feature Matches](results/problem1/matches.png)
**3. SfM Error Metrics (Bundle Adjustment Improvement)**
![Error Metrics](results/problem1/error_metrics.png)
### Problem 2 Output (`results/problem2/`)
**1. 3D Agent Paths (Comparison)**
| Fast Solver (Baseline) | CBS Solver (Optimal) |
| :---: | :---: |
| ![Fast 3D](results/problem2/fast/paths_3d_static.png) | ![CBS 3D](results/problem2/cbs/paths_3d_static.png) |
**2. Position vs Time (Conflict Analysis)**
| Fast Solver | CBS Solver |
| :---: | :---: |
| ![Fast Time](results/problem2/fast/paths_time_position.png) | ![CBS Time](results/problem2/cbs/paths_time_position.png) |
**3. Interactive Animation**
- `trajectory_vis.html`: **Open this in your browser!** It's an interactive 3D player where you can scrub through time to see the agents move.
- `metrics.txt`: Comparison of execution time and path cost between the Fast and CBS solvers.
---
### Future Improvements
If I had more time, I would:
1. **Deep Learning**: Replace SIFT with **SuperPoint+SuperGlue** for better matching in textureless areas.
2. **Loop Closure**: Implement a Bag-of-Words (DBoW2) system to recognize previously visited locations and correct long-term drift in SLAM.
---
**Author**: Anirudh
---
Source code: https://github.com/rudzz1950/Stereo-Vision-Multi-Agent-Pathfinding
## Run locally
```bash
pip install -r requirements.txt
python app.py
```
`app.py` is a Gradio app; the original project scripts are unchanged alongside it.