Go to file
Fabien Freling 9a4e8e3a5c add lldb 2023-08-08 09:46:36 +02:00
src fix offset when solo rect 2022-02-18 13:28:59 +01:00
.gitignore rename output bins 2022-02-18 12:53:48 +01:00
README.md update doc 2022-02-18 13:19:31 +01:00
Tupfile.ini initial commit 2022-02-11 19:03:22 +01:00
build-cli.sh rename output bins 2022-02-18 12:53:48 +01:00
build-gui.sh rename output bins 2022-02-18 12:53:48 +01:00
justfile fix justfile 2022-02-18 13:21:03 +01:00
lenna.png add bounding box 2022-02-12 00:28:54 +01:00
shell.nix add lldb 2023-08-08 09:46:36 +02:00
test_algo.pdf initial commit 2022-02-11 19:03:22 +01:00


Netatmo technical test

The subject is available here: Test Algo

Question 1

As a preprocessing step of a second algorithm A2, we would like to combine all the regions corresponding to the bounding boxes into a new image FRegions of dimension D × D, where D given by A2 and D < min(M, N )

This is a packing problem, as described on Wikipedia. Since this is NP-hard, we know the "exact" solution might be unreachable but we could find a solution that is good enough for our needs.

I looked up some solutions online and found a great article by David Colson: "Exploring rectangle packing algorithms". It gives a lot a references and compares different algorithms.

I decided to implement his naive "row packer" to quickly have an implementation and try it out.

If I were to implement a more robust algorithm, I would choose the Skyline approach. It looks likes a good trade-off of quality and performance.

Question 2

A2 then takes as input F Regions and outputs new bounding boxes B. We would like now to compute the location of each of these new bounding boxes in F reference

To map the new bounding boxes into the original frame F, we need to have a mapping between the bounding boxes of F and the ones we packed into FRegions. During the packing, I saved the bounding boxes position in FRegions, so the mapping was straightforward:

  1. detect in which bounding box in FRegions the new bounding box is contained
  2. apply the transformation from FRegions to F

Because we look into every bounding box to find the enclosing one, we have a complexity of N^2. Depending of the numbers of boxes, it could be problematic. We can make it faster by using a spatially sorted structure like a quad-tree, but it seems a bit overkill in this case.

If we didn't have knowledge of the bounding boxes position in FRegions, we could recompute them by looking at pixel similarity between F and FRegions but it would be costly, and a bit wasteful since we already computed the bounding boxes.

Question 3

We would like now to be able to provide to the algorithm A2 either the region-based image or the initial image without transformation, which modifications to your code architecture do you suggest in order to handle this?

To support either a packed image (the region-based one) or a sparse image (the initial image limited to the bounding boxes), the easiest solution is to add support for a binary mask. In the same way A2 is suppose to ignore zeros valud in the region-based frame, it could be modified to ignore areas in an image where the mask is set to zero.



In order to easily debug and better visualize the problem, I chose to implement a minimal GUI using raylib.

You can build it with ./build-gui.sh (you need to installed raylib required libraries).

You can add, move, and resize boxes. Processing steps are triggered with buttons.


A commandline sample is also available, in case the raylib library cannot be built, or if we need to benchmark performance.

You can build it with ./build-cli.sh (you need to installed raylib required libraries).

PNG support

I chose to support PNG files through the stb files: github.com/nothings/stb. I could have implemented basic image support with the PNM format but I think it is nicer to support common image formats with a simple library.

3rd party libraries

I use 2 external libraries for better visualization:

  • stb files (for PNG)
  • raylib (for GUI)

I don't rely on them for the algorithm implementation and the core of the exercise doesn't rely on external libraries.

To avoid name collision, I created my own namespace freling.