Computer Vision — Assignment 1 Target object: Classmate Pulse 6-subject notebook (illustrated crowd-scene cover) Pipeline: SIFT → from-scratch descriptor matching → Lowe ratio test → 4-D Generalized Hough Transform → RANSAC affine estimation → geometric verification → greedy multi-instance extraction → IoU Non-Maximum Suppression
- Overview
- Assignment Requirements Mapping
- Repository Structure
- Data Collection
- Pipeline Walkthrough (with images)
- Code Reference — what every file does and why
- Full Numerical Results
- Design Decisions & Why They Were Necessary
- Limitations
- How to Run the Project
- Implementation Constraints (what was NOT used)
- Conclusion
This project builds a multi-instance object recognition system that finds every occurrence of a single physical object (a notebook with a distinctive illustrated cover) inside one cluttered scene photo, even when the object is:
- rotated at arbitrary in-plane angles,
- scaled differently (near vs. far from the camera),
- partially occluded by other objects, and
- surrounded by visually similar clutter (the cover art itself is a busy illustration full of repeated shapes — faces, circles, stripes — which is intentionally adversarial for a feature matcher).
OpenCV is used only for image I/O, color conversion, and SIFT keypoint/descriptor extraction (cv2.SIFT_create()), which the assignment explicitly permits. Every other stage of the pipeline — descriptor matching, the Hough transform, affine least-squares estimation, RANSAC, geometric verification, greedy multi-instance extraction, and NMS — is implemented from first principles in plain NumPy, with no cv2.BFMatcher, cv2.FlannBasedMatcher, cv2.estimateAffine2D, cv2.findHomography, or sklearn.cluster anywhere in the codebase.
The final run detected 4 correct instances of the notebook in the cluttered query image, matching the four physical copies photographed in the scene.
| Assignment requirement | Where it's satisfied |
|---|---|
| SIFT feature extraction via OpenCV | src/sift_features.py |
| Descriptor matching from scratch (Euclidean distance) | src/descriptor_matching.py |
| Lowe's ratio test | src/descriptor_matching.py |
| 4-D Generalized Hough Transform (x, y, scale, angle) | src/hough_clustering.py |
Affine transform via Ax = b least squares |
src/affine.py |
| RANSAC | src/ransac.py |
| Collinearity / determinant / scale sanity checks | src/ransac.py, src/verification.py |
| Greedy multi-instance extraction (sequential inlier subtraction) | src/main.py |
| IoU-based Non-Maximum Suppression | src/nms.py |
| Clean final visualization (boxes only, no keypoint clutter) | src/visualization.py |
| Naive-vs-final comparison figures for report | src/generate_report_figures.py |
cv-multi-instance-object-recognition/
│
├── data/
│ ├── template/
│ │ ├── template.jpg # original high-res photo of the isolated notebook
│ │ └── template_work.jpg # resized working copy used for SIFT (1500x2000)
│ │
│ └── query/
│ ├── query.jpg # original high-res cluttered scene photo
│ └── query_work.jpg # resized working copy used for SIFT (1500x2000)
│
├── outputs/
│ ├── naive_match.jpg
│ ├── naive_match_colored.jpg
│ ├── hough_candidates.jpg
│ ├── ransac_verification.jpg
│ ├── final_detection.jpg
│ └── final_detection_work.jpg
│
├── report/
│ ├── figures/
│ │ ├── 01_template.jpg
│ │ ├── 02_query.jpg
│ │ ├── 03_template_sift.jpg
│ │ ├── 04_query_sift.jpg
│ │ ├── 05_naive_matching.jpg
│ │ ├── 06_hough_candidates.jpg
│ │ ├── 07_ransac_verification.jpg
│ │ └── 08_final_detection.jpg
│ └── report.tex
│
├── src/
│ ├── __init__.py
│ ├── config.py # all tunable parameters in one place
│ ├── prepare_images.py # resizes originals into working copies
│ ├── sift_features.py # OpenCV SIFT extraction wrapper
│ ├── descriptor_matching.py # from-scratch NN / ratio-test matcher
│ ├── analyze_ratios.py # empirical study used to pick tau
│ ├── hough_clustering.py # 4-D Generalized Hough Transform
│ ├── affine.py # Ax=b least-squares affine solver
│ ├── ransac.py # RANSAC robust estimator
│ ├── verification.py # geometric sanity checks (det, coverage, RMSE)
│ ├── nms.py # IoU-based Non-Maximum Suppression
│ ├── visualization.py # drawing utilities for every figure
│ ├── generate_report_figures.py # builds the 8 report-ready images
│ ├── test_matching.py # standalone script: SIFT + matching only
│ ├── test_hough.py # standalone script: raw Hough voting only
│ ├── test_hough_candidates.py # standalone script: merged Hough bins
│ └── main.py # orchestrates the full end-to-end pipeline
│
├── .gitignore
├── README.md
└── requirements.txt
Figure 1 — Isolated template of the target notebook (Classmate Pulse, 6-subject).
A single, flat, well-lit photo of the notebook cover was taken in isolation. The original photo is a very high-resolution shot (≈ 6120 × 8160, ~50 megapixels), which is far too large to run SIFT and repeated matching on efficiently, so prepare_images.py produces a resized working copy capped at 1500×2000 using cv2.INTER_AREA interpolation (the best choice for shrinking images, since it area-averages pixels instead of naively skipping them, which avoids aliasing). The original is kept untouched for the deliverable; only the working copy is fed into the pipeline.
Figure 2 — Cluttered query scene: a 2×2 composite of four separate photographs of the same notebook, each captured at a different scale, angle, and level of clutter/occlusion.
The query scene is a 2×2 grid of four individual photographs of the same physical notebook, each shot under different conditions — rotated, placed at a different distance from the camera, and surrounded by different clutter (a second notebook, a scrunchie, a small toy/case, fabric background patterns). This satisfies the assignment's requirement for at least three instances under different scale, rotation, and occlusion, while keeping the four ground-truth object locations unambiguous for grading.
Figure 3 & 4 — SIFT keypoints (green circles, radius ∝ scale, tick ∝ orientation) on the template (left) and the cluttered query (right).
cv2.SIFT_create() is run on both working images. Every keypoint carries (x, y, scale, orientation) plus a 128-dimensional gradient-histogram descriptor. This produced:
- Template: 9,590 keypoints → descriptor matrix
(9590, 128) - Query: 12,976 keypoints → descriptor matrix
(12976, 128)
The query naturally has more keypoints because it contains four notebook copies plus background clutter, all of which generate their own local structure.
Figure 5 — Every query keypoint connected to its best-matching template keypoint, after Lowe's ratio test but before any geometric reasoning.
For every query descriptor, its Euclidean distance to every template descriptor is computed manually (no cv2.BFMatcher). The nearest (d1) and second-nearest (d2) template neighbours are kept, and the match is accepted only if the ratio r = d1/d2 is below a threshold τ. This is what produces the "chaotic" correspondence picture above: even after filtering, thousands of lines crisscross the image, because a match being locally unambiguous does not mean it is globally consistent with a single rigid object pose. This figure is the direct evidence the assignment asks for — proof that naive matching alone is not sufficient.
Figure 6 — Hough voting result. Each yellow marker is a discovered pose hypothesis, labeled with its vote count.
Every accepted match "votes" for where the whole object must be, assuming that particular correspondence is correct. Concretely, each match predicts a hypothesized (x_center, y_center, scale, angle) for the object. Correct matches from the same physical notebook copy all vote for nearly the same 4-D point (because they share the same rigid transform), while incorrect / background matches scatter randomly across the parameter space. Binning these votes turns a needle-in-a-haystack problem into a simple "find the tall bins" problem. The four dominant bins (H1–H4 in the figure) correspond exactly to the four physical notebook instances; the small extra bins (H5–H9, 3–21 votes) are noise clusters that don't survive the next stage.
Figure 7 — One Hough hypothesis after RANSAC + least-squares refinement: 554 inliers out of 634 candidate matches, RMSE ≈ 3.78 px.
Each Hough bin only tells us roughly where an object might be — it does not give a precise, distortion-free transform. For every promising bin, RANSAC repeatedly samples 3 correspondences, rejects near-collinear samples (which would make the transform undefined), solves the resulting Ax = b system for the 6 affine parameters, and counts how many of the other candidate correspondences agree with that transform within an 8-pixel reprojection tolerance. The transform with the largest consensus set is kept and then refined using a least-squares fit over all of its inliers (not just the 3 samples), which is what produces the tight green quadrilateral seen above.
Once one instance is confirmed, all of its RANSAC inlier matches are removed from the match pool, and the Hough voting + RANSAC verification is repeated on what remains. This is what allows the pipeline to find a second, third, and fourth instance instead of just re-finding the strongest one over and over.
Figure 8 — Final output: 4 clean bounding quadrilaterals, one per physical notebook, after IoU-based NMS. No stray keypoints or match lines are drawn.
The four template corners are projected into the scene using each instance's estimated affine transform, producing a quadrilateral per detection. IoU-based NMS then checks pairs of detections for excessive overlap; in this run none of the four boxes overlapped enough to need suppression, so all 4 were kept (Detections before NMS: 4 → Detections after NMS: 4).
Centralizes every tunable constant (Lowe ratio τ, RANSAC iteration count, reprojection threshold, Hough bin widths, minimum inlier count, NMS IoU threshold, working-image size cap). Keeping these in one place means every other module imports from here instead of hard-coding magic numbers, which makes the whole pipeline reproducible and easy to re-tune.
Reads the two original high-resolution photos and produces resized "working" copies (longest side capped near 2000 px, cv2.INTER_AREA interpolation). Why: running SIFT and an O(N×M) brute-force matcher on 50-megapixel originals would be extremely slow and would also generate an unmanageable number of near-duplicate keypoints from noise/JPEG artifacts at full resolution. The resize factor is stored so that, if needed, detected coordinates can be mapped back onto the original full-resolution image.
Thin wrapper around cv2.SIFT_create() that returns, for both images, a list of (x, y, scale, angle) keypoint tuples and their (N, 128) descriptor arrays. This is the only place OpenCV's higher-level vision logic is used, exactly as the assignment allows.
Implements feature correspondence completely from scratch:
- Euclidean distance between two 128-D descriptors, computed via squared distances (avoiding an unnecessary square root during comparison, since ordering is preserved).
- For every scene keypoint, finds its nearest and second-nearest template neighbours (matching scene → template, as recommended by the assignment hint, which is essential when the template can appear multiple times in the scene — matching template → scene would force a 1-to-1 assignment and silently discard 3 of the 4 instances).
- Implements Lowe's ratio test: accepts a match only if
d1/d2 < τ.
Why this design: matching scene-to-template (rather than the more common template-to-scene) means each of the four notebook copies in the query can independently find its own best template match, instead of competing for a single best match per template keypoint.
A diagnostic script that computes the empirical distribution of d1/d2 ratios across all candidate matches, reporting percentiles (10th, 25th, 50th, 75th, 90th, 95th, 99th). This was used to justify tightening the ratio threshold from the commonly cited default of τ = 0.70 down to τ = 0.65 for this specific dataset — at 0.70 the pipeline accepted 2,133 matches (too much noise given the notebook's repetitive illustration), while 0.65 gave a cleaner set of 1,945 matches without discarding the strong correct correspondences.
Implements the 4-D Generalized Hough Transform from scratch:
- For each accepted match, compute the predicted object scale
ŝ = s_scene / s_templateand predicted orientationθ̂ = θ_scene − θ_template(normalized to[-180°, 180°)). - Using the template's known center and the vector from the matched template keypoint to that center, rotate and scale that vector by
(ŝ, θ̂)and add it to the scene keypoint location to get a predicted object center(x̂_c, ŷ_c). - Quantize
(x̂_c, ŷ_c, ŝ, θ̂)into a 4-D histogram (log-spaced bins for scale, since scale ratios are multiplicative, not additive) and accumulate votes. - Merge neighbouring occupied bins (adjacent in x, y, scale, and angle) so a single physical pose isn't fragmented across quantization boundaries, then rank the merged clusters by vote count.
Why: with 4 instances and heavy clutter, only a small fraction of matches are geometrically correct for any single object, which is exactly the scenario where plain RANSAC over all matches at once fails — the inlier ratio is too low. The Hough transform sidesteps this by first roughly separating matches into per-instance groups using their independent pose predictions, so RANSAC only has to clean up one group at a time.
Solves for the 2-D affine transform x' = ax + by + t_x, y' = cx + dy + t_y by stacking every correspondence into a linear system A·p = b (where p = [a, b, c, d, t_x, t_y]) and solving via the normal equations p = (AᵀA)⁻¹Aᵀb. This is a pure NumPy least-squares solve — no cv2.estimateAffine2D.
Implements RANSAC around the affine solver:
- Randomly sample 3 correspondences.
- Reject the sample if the 3 template points (or 3 scene points) are (near-)collinear, since 3 collinear points cannot determine a unique affine map and would produce a degenerate/singular system.
- Fit an affine transform to the 3-point sample.
- Reproject every other candidate correspondence through that transform and measure
‖p'_i − T(p_i)‖₂; count how many fall under the 8-pixel threshold as inliers. - Keep the sample with the largest inlier count across 300 iterations.
- Refit the affine transform using least squares over all inliers of the winning sample (not just the original 3), which substantially reduces the RMSE compared to the raw 3-point fit.
After RANSAC produces a candidate, this module runs the geometric sanity checks required by the assignment before accepting the detection:
- Minimum inlier count — rejects hypotheses with too little support.
- Reprojection RMSE — rejects hypotheses whose "inliers" are only loosely consistent.
- Determinant of the 2×2 linear part
det(M) = ad − bc— a near-zero determinant means the transform has collapsed the template onto a line or point (degenerate), so it is rejected. - Singular-value-based scale & anisotropy checks — bounds how much the fitted transform can stretch the template unevenly in different directions (extreme anisotropy usually means the "match" is a coincidental alignment rather than a real rigid/similarity-like transform of a rectangular notebook).
- Template spatial coverage — checks that inlier points are spread across the template, not clustered in one small repeated pattern (the notebook's cover has many similar-looking faces/circles, so a hypothesis built entirely from one repeated sub-pattern could otherwise get a deceptively low RMSE).
Implements Intersection-over-Union based Non-Maximum Suppression from scratch: computes IoU(A,B) = |A∩B| / |A∪B| between every pair of accepted detection boxes and suppresses the lower-scoring box in any pair whose IoU exceeds the configured threshold.
Contains all drawing utilities (keypoint circles, colored correspondence lines, Hough vote markers, RANSAC quadrilaterals, final clean bounding boxes) used by both the debug scripts and generate_report_figures.py. Keeping drawing code separate from algorithmic code means the same detection results can be visualized in multiple styles (chaotic debug view vs. clean final view) without duplicating pipeline logic.
Runs the full pipeline once and exports the exact 8 figures used in the LaTeX report (01_template.jpg … 08_final_detection.jpg), ensuring the report always reflects the actual current state of the code rather than stale screenshots.
Standalone scripts used during development to inspect intermediate pipeline stages in isolation (raw matching only, raw Hough votes only, merged Hough candidates only) without running the full RANSAC/NMS pipeline — useful for debugging and for producing some of the reported intermediate statistics (e.g. the 310 raw Hough bins, 75 bins with ≥ 3 votes).
The orchestrator: loads images → extracts SIFT → matches descriptors → Lowe filters → loops {Hough vote → take best cluster → RANSAC verify → accept/reject → subtract inliers} until no more valid clusters remain → runs NMS → draws and saves the final output. This is the single entry point that reproduces every number reported below.
| Quantity | Value |
|---|---|
| Working template size | 1500 × 2000 |
| Working query size | 1500 × 2000 |
| Template keypoints | 9,590 |
| Query keypoints | 12,976 |
| Descriptor dimension | 128 |
| τ (threshold) | Accepted matches |
|---|---|
| 0.70 (initial trial) | 2,133 |
| 0.65 (final, used in pipeline) | 1,945 |
Empirical ratio distribution (from analyze_ratios.py, computed over the candidate set examined up to ratio 0.95 — not the full unrestricted distribution of all possible ratios):
| Percentile | Ratio value |
|---|---|
| 10% | 0.3224 |
| 25% | 0.5806 |
| 50% | 0.8627 |
| 75% | 0.9201 |
| 90% | 0.9398 |
| 95% | 0.9450 |
| 99% | 0.9491 |
| Quantity | Value |
|---|---|
| Raw occupied Hough bins | 310 |
| Raw bins with ≥ 3 votes | 75 |
Strongest merged pose hypotheses:
| Candidate | Votes | Center (x, y) | Scale | Angle |
|---|---|---|---|---|
| 1 | 680 | (1193.1, 731.6) | 0.367 | 34.71° |
| 2 | 479 | (223.8, 1620.2) | 0.498 | −151.30° |
| 3 | 467 | (578.9, 824.8) | 0.634 | −10.31° |
| 4 | 194 | (1329.7, 1306.8) | 0.620 | −144.72° |
| Instance | Hough votes | Candidate matches | RANSAC inliers | RMSE (px) | Determinant | Template coverage | Anisotropy |
|---|---|---|---|---|---|---|---|
| 1 | 647 | 634 | 554 | 3.784 | 0.135 | 0.820 | 1.034 |
| 2 | 456 | 453 | 452 | 1.787 | 0.248 | 0.778 | 1.004 |
| 3 | 449 | 445 | 445 | 1.850 | 0.404 | 0.460 | 1.001 |
| 4 | 178 | 177 | 152 | 3.533 | 0.372 | 0.431 | 1.027 |
(Note: "Hough votes" and "candidate matches" differ slightly because template-keypoint deduplication is applied before RANSAC — e.g. instance 1 had 647 raw Hough votes but 634 unique correspondences after deduplication.)
| Stage | Matches remaining |
|---|---|
| Initial | 1,945 |
| After instance 1 removed | 1,391 |
| After instance 2 removed | 939 |
| After instance 3 removed | 494 |
| After instance 4 removed | 342 |
Detections before NMS: 4
Detections after NMS : 4
No pair of the four detections exceeded the configured IoU threshold, so all four were retained — NMS does not need to remove anything for it to have "worked correctly."
Template keypoints = 9,590
Query keypoints = 12,976
Final Lowe matches = 1,945
Strong Hough hypotheses = 4
RANSAC-verified instances = 4
Final NMS detections = 4
- Matching scene → template, not template → scene. With 4 copies of the object in the scene, a template keypoint has 4 legitimate correspondences. Matching template-to-scene would force each template point to pick only one, silently losing 3 of the 4 instances before the Hough stage even runs.
- Tightening τ from 0.70 to 0.65. The notebook cover is a busy illustration with many repeated small shapes (faces, circles), which produces an unusually large number of ambiguous near-duplicate descriptors. The empirical ratio study showed that 0.65 removed a meaningful chunk of these ambiguous matches while barely touching the well-separated correct ones.
- 4-D Hough transform before RANSAC, not RANSAC directly on the full match set. With 1,945 matches spread across 4 objects plus background noise, the inlier ratio for any single object is roughly 15–35%, low enough that unguided RANSAC would need very many iterations (or fail) to find any single instance, let alone all four. The Hough stage pre-groups matches by predicted pose so RANSAC only ever works on an already-mostly-correct subset.
- Rejecting collinear 3-point RANSAC samples. Three collinear points make the
6×6system underdetermined/singular; without this check RANSAC would occasionally propose garbage transforms with huge or undefined scale. - Determinant + anisotropy checks, not inlier count alone. A hypothesis can have many "inliers" purely because it repeatedly matches one small repeated illustration pattern; the determinant and coverage checks catch and reject these degenerate/local hypotheses even when their raw inlier count looks strong.
- Greedy sequential inlier subtraction rather than trying to detect all 4 objects in one pass. Removing the winning instance's inliers before re-running Hough voting is what allows weaker (but still valid) instances — like instance 4, with only 152 inliers — to eventually dominate their own Hough bin instead of being permanently drowned out by the strongest instance's votes.
The query image used here is a 2×2 composite of four separately photographed instances rather than one single photograph of a genuinely cluttered desk/shelf taken in one camera shot. This was a deliberate choice to guarantee clean, unambiguous ground truth for evaluating the pipeline, but it means the four object regions do not sit under one shared global camera geometry — so occasionally a projected affine quadrilateral can extend slightly past the boundary of its own composite panel. This is a property of the experimental setup, not a pipeline bug, and is disclosed here rather than hidden.
Additionally, because the target notebook's cover art contains many visually repeated illustrated elements, local SIFT descriptors can sometimes produce matches that are geometrically self-consistent but wrong (e.g., matching one face illustration to a different, similar-looking face illustration elsewhere on the same cover). The Hough clustering, RANSAC consensus, and — most importantly — the template spatial-coverage check exist specifically to catch and reject this failure mode.
# 1. Activate your virtual environment
source .venv/bin/activate.fish
# 2. Install dependencies
pip install -r requirements.txt
# 3. Build resized working copies from the original photos
python -m src.prepare_images
# 4. (Optional) Inspect intermediate stages individually
python -m src.test_matching # SIFT + descriptor matching only
python -m src.test_hough # raw Hough voting only
python -m src.test_hough_candidates # merged Hough candidates only
# 5. Generate the exact figures used in the report
python -m src.generate_report_figures
# 6. Run the full end-to-end detection pipeline
python -m src.mainFinal outputs are written to outputs/final_detection.jpg and report/figures/08_final_detection.jpg.
Per the assignment rules, the following high-level OpenCV / scikit-learn APIs are never called anywhere in this codebase:
cv2.BFMatcher
cv2.FlannBasedMatcher
cv2.estimateAffine2D
cv2.findHomography
sklearn.cluster.*
OpenCV is used strictly for image I/O, color-space conversion, cv2.SIFT_create(), and basic drawing (circles/lines/text) for visualization — none of which perform the actual matching, clustering, or geometric estimation logic.
The pipeline demonstrates a complete classical, from-scratch, feature-based multi-instance object recognition system. SIFT supplies scale- and rotation-aware local features; a hand-implemented nearest-neighbour matcher with Lowe's ratio test produces tentative correspondences; a from-scratch 4-D Generalized Hough Transform groups those correspondences by consistent object pose; RANSAC with least-squares affine refinement then produces a robust geometric transform per candidate, while determinant, anisotropy, RMSE, and template-coverage checks reject degenerate hypotheses; and greedy sequential inlier subtraction combined with IoU-based NMS produces exactly four clean, non-duplicate detections — matching the four physical copies of the notebook actually present in the scene.