4

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:

enter image description here

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).

Reunanen
  • 7,921
  • 2
  • 35
  • 57
  • Have you looked at boundingRect? http://docs.opencv.org/2.4/modules/imgproc/doc/structural_analysis_and_shape_descriptors.html?highlight=boundingrect#boundingrect – noel Oct 04 '17 at 12:23
  • @shakabra Yes, I have. Do you have a specific suggestion as to how it could be used to solve the problem that I have described? – Reunanen Oct 04 '17 at 13:23
  • I think you will hardly find existing implementation for GPU. Most expensive part of solution is maximum matching, after that is bipartite graph creation. There are few research papers about GPU matching implementation, hardly there are good implementations of them around. Graph creation requires testing intersection of all x cuts to all y cuts, which probably can be done on GPU with some clever data structure but I suppose it will not be of large gain overall. – Ante Oct 06 '17 at 09:16
  • @Ante I'd be perfectly fine with a CPU implementation. (Did I say GPU somewhere?) – Reunanen Oct 08 '17 at 13:02
  • @Reunanen You mentioned OpenCV. I thought you are targeting GPUs. I don't know about open implementation. I made one (for similar project) and I was surprised how simple it was to implement. I think I used someone's matching. – Ante Oct 08 '17 at 15:36

0 Answers0