107 lines
4.1 KiB
Markdown
107 lines
4.1 KiB
Markdown
# Netatmo technical test
|
||
|
||
The subject is available here: [Test Algo](./test_algo.pdf)
|
||
|
||
## 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][1].
|
||
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][2]". 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][3]
|
||
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.
|
||
|
||
## Installation
|
||
|
||
### GUI
|
||
|
||
In order to easily debug and better visualize the problem, I chose to implement
|
||
a minimal GUI using [raylib][4].
|
||
|
||
You can build it with `./build-gui.sh` (you need to installed [raylib required
|
||
libraries](https://github.com/raysan5/raylib/wiki/Working-on-GNU-Linux)).
|
||
|
||
You can add, move, and resize boxes. Processing steps are triggered with
|
||
buttons.
|
||
|
||
### CLI
|
||
|
||
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](https://github.com/raysan5/raylib/wiki/Working-on-GNU-Linux)).
|
||
|
||
## PNG support
|
||
|
||
I chose to support PNG files through the stb files:
|
||
[github.com/nothings/stb](https://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`.
|
||
|
||
## References
|
||
|
||
[1]: https://en.wikipedia.org/wiki/Packing_problems#Packing_of_rectangles
|
||
[2]: https://www.david-colson.com/2020/03/10/exploring-rect-packing.html
|
||
[3]: https://www.researchgate.net/publication/221049934_A_Skyline-Based_Heuristic_for_the_2D_Rectangular_Strip_Packing_Problem
|
||
[4]: https://github.com/raysan5/raylib
|