Assignment 03

The best shape detection algorithm is...

Deadline is 2025-01-17@18:00

Late submission? 10% will be removed for each day that you are late (3 days max)

This is a group assignment (in a team of 3 or 4); you are free to form your own teams

Overview

The aim of this assignment is to implement and compare the three algorithms for shape detection described in the book (Section 11.4: (1) RANSAC, (2) region growing, and (3) Hough transform). You will implement these so that planes in point clouds that be detected.

The descriptions in the book are generic and do not account for all the complex cases that can arise; you should aim at making them work with real-world datasets. Also, you will need to implement the algorithms in such a way that all the planes can be detected in the input point cloud.

The input point cloud will be a subset of AHN where the ground and the vegetation have been removed, you only have the points representing the BK-City building. The final result has to be written to an ASCII PLY file (see below).

You also need to submit a report in which you document your implementations and compare them (see below for details).

The starting code

Code is in the /hw/03/ folder of the GitLab repository of the course.

You are not allowed to modify the geo1015_hw03.py file, I will use it to test your submission.

The code reads the params.json file, which triggers one or more of the 3 shape detection algorithms. Each of the 3 algorithm has its own Python unit; this is where you should add your code.

{
  "input_file": "../data/bk_subset1.laz",
  "RANSAC": {
    "k": 15,             //-- max number of iterations
    "min_score": 15,     //-- a plane is formed by a minimum of 15 points
    "epsilon": 0.3       //-- error threshold to the plane
  },
  "RegionGrowing": {
    "k": 15,             //-- a plane is formed by a minimum of 15 points
    "max_angle": 10.0    //-- angle threshold
  },
  "HoughTransform": {
    "alpha": 15,         //-- minimum count in the accumulator
    "epsilon": 0.3       //-- error threshold to the plane
  }
}

Notice that some parameters for the methods are provided, but you are allowed to add other ones (for instance if you try to improve the algorithm and want to expose a parameter).

Everything from the Python standard library is fine: math, json, sys, etc. No external libraries can be used, except: rerun, Numpy, and SciPy. If you want to use a specific library, just ask me first on discord to know if it’s allowed.

The report to submit

The report should be ~20 pages and be in PDF format (no Word please). For each of the 3 algorithms, you should:

At the end, you should mention which one of the 3 methods, in your opinion, is the best, and why.

You should also add a section describing who-did-what in the team (we will check the git commits to ensure that all shared the workload; all of you have to participate).

The output format: PLY

Your output file has to be a PLY file (see Appendix A.2 of the book). In addition to the point coordinates it should contain a property segment_id of type int. This property indicates for each point to which plane it belongs (as each plane should have a unique segment_id). Note that the value segment_id==0 is special! It means a point does not belong to any plane; the segment_id’s of your planes should thus start at 1. All input points should be in the output PLY file.

The given code already outputs the PLY for you (you’re welcome).

ply
format ascii 1.0
element vertex 10000
property float x
property float y
property float z
property int segment_id
end_header
85176.77 446742.10 1.49 0
85175.69 446742.58 1.52 1
85174.45 446741.94 9.52 1
...

Using rerun as a viewer/logger

rerun is a great logger and visualiser that I highly recommend for this assignment (and for when developing geometric algorithms in general). It allows to visualise the different steps of your implementation, and thus is really helpful for debugging. The starting code has an example how to use it (in ransac.py).

Be aware: There is a small hiccup at the moment: rerun cannot use numpy version 2.0 and higher, and startinpy forced you to install numpy>=2.0… Thus, if you want to use rerun, you should either:

  1. create a new Python venv
  2. install rerun: pip install rerun-sdk (this installs the viewer too)

or

  1. install startinpy v0.12.1: pip install startinpy -U (which doesn’t enforce numpy>=2.0.0), or delete it completely: pip uninstall startinpy
  2. downgrade your numpy to v1.26: pip install numpy==1.26
  3. install rerun: pip install rerun-sdk (this installs the viewer too)

Marking

Criterion Points
report quality 4
RANSAC 2
region growing 2
Hough transform 2

What to submit and how to submit it

The submission process will be significantly different from the other assignments: you have to create a private GitHub repository where all the code and the report go.

Before the deadline, you need to invite both @HideBa and @hugoledoux as collaborators to the repository (how to do this).

After that email me (h.ledoux@tudelft.nl) with (one email per team):

  1. the URL of the repository,
  2. the name and student number of each member.

Do not add or modify anything after the deadline! You will get penalised for late submission.

The structure of your repository should be as follows (if you have more files before submission, just delete them from the final version please):

├── report
│   └── report.pdf 
│   └── (report.ipynb if used)
│   └── (report.tex if used)
│   └── (report.docx if used)
├── data
│   └── out_bk.ply 
│   └── out_bk_subset1.ply 
├── code
│   └── geo1015_hw03.py
│   └── ransac.py
│   └── regiongrowing.py
│   └── houghtransform.py
│   └── ... (any code goes in that folder, you can create new folders in that folder)
└── README.md

The /data folder contains the output you obtain with your code for the 2 dataset given in the starting code.

In the README.md, add the name and student number of each of the members.

[last updated: 2024-12-16 19:45]