🔧 PatchMatch — Structural Image Editing & Inpainting

A Python implementation of the PatchMatch algorithm based on the paper "PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing" by Barnes et al. (2009).

This project explores the power of randomized correspondence algorithms for structural image editing, focusing on performance optimization using Numba and pyramid-based processing (Coarse-to-Fine).

---

📌 Features & Branches

This repository is organized into two main branches to separate stable implementation from experimental features:

1. main Branch (Stable)

• Full Image Reconstruction: Demonstrates the core NNF (Nearest-Neighbor Field) algorithm. It successfully reconstructs a target image using patches from a source image.
• Visualization: Includes tools to visualize the NNF vectors (color-coded by angle and magnitude).
• Coarse-to-Fine: Implements the pyramid approach to avoid local minima during reconstruction.

2. inpainting Branch (Experimental / WIP)

• Inpainting Framework: Contains the logic for object removal and hole filling.
• Masked SSD: Implements specific distance calculations to ignore masked regions.
• Current Status: This is a Work In Progress. The logic for masked initialization and propagation is present, but the algorithm currently exhibits artifacts (e.g., vertical streaking) in complex scenarios. It serves as a testing ground for future improvements.

---

🛠️ Installation

Prerequisites

Ensure you have Python 3.8+. This project relies on Tkinter for visualization (on Linux, this requires a system-level install).

For Linux (Ubuntu/Debian):

sudo apt update
sudo apt install python3-tk

Setup

1. Clone the repository

2. Create a Virtual Environment (Recommended):

python3 -m venv venv
source venv/bin/activate  # On Windows use: venv\Scripts\activate

3. Install Dependencies:

pip install -r requirements.txt

📂 Project Structure

patchmatch-project/
│
├── data/
│   ├── input/          # Source images and masks
│   └── output/         # Generated results (NNF visualizations, reconstructions)
│
├── docs/               # LaTeX Report and academic documentation
│
├── src/                # Source Code
│   ├── __init__.py
│   ├── patchmatch.py   # Core Algorithm (Class with NNF logic)
│   ├── functions.py    # Helper functions for the Pyramid loop
│   └── utils.py        # Image loading, saving, and visualization tools
│
├── main.py             # Entry point for execution
├── requirements.txt    # Python dependencies
└── README.md           # Project documentation

📄 References

This implementation is based on the following paper:

Barnes, C., Shechtman, E., Finkelstein, A., & Goldman, D. B. (2009). PatchMatch: A Randomized Correspondence Algorithm for Structural Image Editing. ACM Transactions on Graphics (TOG), 28(3), 24.