Automated Reconstruction of a 1000-Piece Jigsaw Puzzle

Segmentation • Feature Extraction • Adjacency Graph • Puzzle Assembly

Authors: Kgetja Bruce Mphekgwane (2593733), Ivy Chepkwony (2431951)

---

📘 Project Overview

This project reconstructs a 1000-piece jigsaw puzzle automatically from raw images of puzzle pieces. The full pipeline consists of:

1. Segmentation — Predicting masks for the 500 unlabelled pieces using a trained U-Net.
2. Adjacency Graph Construction — Determining pairwise compatibility to produce a structured graph (graph.json).
3. Puzzle Assembly — Using placements derived from the graph to assemble the final puzzle (final.png).

All training has already been completed; this submission contains inference-only code, as required, but re-training can be done using the segment.py file if needed.

---

📂 Directory Structure (submitted repository)

.
├── run.sh                    # Main inference pipeline 
├── requirements.txt          # Python dependencies
│
├── inference.py              # Runs U-Net segmentation inference
├── build_graph.py            # Builds adjacency graph using masks + features_emb.pkl
├── assemble.py               # Reconstructs final puzzle image, but requires cropped puzzle pieces to do so. 
│
├── extract_features.py       # feature extraction script
├── embedding.py              # embedding computation script that builds vector + applies PCA
├── matching.py               # Matching classes for the building the graph
├── visulalize_graph.py       # Visualizes the graph.json
│
├── outputs/
     └── test_features.pkl        # Output from extract_features and used in embedding.py
     └── features_emb.pkl         # Precomputed per-piece features (used by build_graph.py) after embedding + PCA
└── models/
     └── unet_best.pth        # Trained segmentation model

---

📥 External Directories Expected

NOTE: Dataset in data/ folder not included

./data/images/    # All 1000 puzzle piece images
./data/masks/     # 500 labelled masks (the remaining 500 must be predicted)

---

▶️ How to Run the Full Pipeline

python -m venv .venv
source .venv/bin/activate
pip install -r requirements.txt
bash run.sh

This will generate:

• ./data/pred_masks.png — predicted masks for unlabelled pieces
• graph.json — final structured adjacency graph

---

./outputs/visuals/ — Visualisation & Graph Inspection Artifacts

This directory contains visual outputs generated by the graph‐visualisation pipeline:

• graph_overview.png – NetworkX overview of the full adjacency graph (nodes coloured by piece type, edges representing reciprocal matches).

• graph_export.gexf / graph_export.graphml – Exported graph formats for interactive inspection in tools such as Gephi or Cytoscape.

• adjacency_list.json – A simplified mapping from each piece ID to its neighbouring pieces based on reciprocal matching.

• match_*.jpg – Matched-edge overlay images. Each image displays two candidate neighbouring pieces side-by-side with:

  • cropped bounding boxes,
  • highlighted matched edges,
  • reprojected contour points,
  • zoom-in insets,
  • similarity score.

These files are generated by running:

python visualize_graph.py \
    --graph outputs/graph_emb.json \
    --features outputs/features_emb.pkl \
    --out_dir outputs/visuals \
    --overlay_matches 50