# How to get squares from an mask image so that the number of square is minimum

I have a bool image with several irregular regions black(mainly in the middle) and other pixes white(mainly in the outer part). This was from the mask of several rois on an image.

Is there a way to split the white region into sauqres, and get the position and size for each square?
The number of square should be as minimum as possible.

The purpose is to get the assembly of white square information, so that I can set inside the raw hdf5 file as zeros square-after-square.

Thanks.

Below is an illustration of 15x15 bool image with black pixels as mask of roi. I want to get the information of white pixels. The actual image was 42354x53256,and there are 171 slices.

1 Like

It seems to be the same problem as the one posted here:

Can you provide more information on what you are trying to do? Are you looking for the largest set of white square pixels in the pattern?

Hello Mendel -

Your problem is not the so-called “exact-cover” problem, but it reminds
me of it. If the analogy to the exact-cover problem holds, then there
is not an “efficient” (i.e, polynomial-time) algorithm for solving it. (There
may, nonetheless, be an “efficient” algorithm for finding a “good enough”
solution.)

I’m assuming that you gain some efficiency by setting (hopefully big)
squares to zero in your hdf5 file. But there is cost in solving for those
squares.

The black squares in your sample image are not sparse. In such a
case my intuition is that you would be best off following the simple
approach of setting the white pixels to zero in your hdf5 file, one by
one.

But you say that your black regions are mainly in the middle, while
your white regions are mainly in the outer part. So perhaps your
black pixels are sparse, at least in some parts of the image. So
maybe you would gain by setting larger squares to zero all at once.

I would look for a heuristic algorithm that gives you a small number
of larger squares, even if it isn’t guaranteed to give you the smallest
possible number.

A simple approach that comes to mind is to start with a pixel, and
systematically grow a square from it until you hit a black pixel. This
is not guaranteed to be optimum, but I suspect that it will be “good
enough.”

One last point: It sounds like there is no harm in setting any given
pixel in the hdf5 file to zero more than once. In this case there
would be no requirement that the white squares you construct
not overlap. Not imposing such a requirement will potentially let
you cover your white pixels with a smaller number of squares.
(That is, as a general rule, relaxing a constraint on such a
solution never makes the solution less optimal.)

Thanks, mm