Task
I have a binary image, and I want to extract a relatively small number of rectangles that cover the non-zero area.
I don't really need the smallest set. Of course finding it at least some of the time wouldn't hurt, however average speed on non-pathological cases is much more important for me.
If it helps, you can think of the binary image as a set of 1x1 rectangles. Indeed such a set is trivial to find, and this solution already works for me basically – however, finding any smaller set would speed up other things considerably.
Yet another alternative (more or less equivalent to the above, at least from my point of view) is to have a set of arbitrary contours (including holes) as the input:
Related work
This question has been asked and answered many times; for example, the accepted answer here is great.
There is even a Javascript implementation here.
So the question is not about whether an algorithm exists, or which algorithm is optimal.
The question
Instead, the question is this:
Given the fact that I'm using C++, and OpenCV by the way, is there an implementation that I could easily integrate to my code?
Even better, is there an implementation with a permissive license?
Ideal solution
Ideally, I could just do:
const cv::Mat binary_image = ...; // get input image from somewhere
const std::vector<cv::Rect> rects = dissect(binary_image);
Or:
const std::vector<cv::Rect> initial_rects = ...;
const std::vector<cv::Rect> rects = find_small_dissection(initial_rects);
But of course a solution that doesn't use OpenCV is just fine also; it's no problem at all to convert back and forth. But since OpenCV already has types for image (cv::Mat) and rectangle (cv::Rect), it was convenient to use these definitions above.
Motivation for this question
It's not that I can't take the pseudocode, or the Javascript code, and start porting it to C++ and OpenCV. However, it'll probably take quite a while before my implementation runs bug-free. I'd much rather use that same time testing, and possibly fixing, an existing open-source implementation. If none can be found, then maybe I'll need to write the code myself, however I might not be able to then open-source the result (because I'm developing a commercial product for my client).