How do you find the largest empty black rectangle coordinates, width and height

[srini8080]

Centos 8.0
Version: ImageMagick 7.1.1-6 Q16-HDRI x86_64 21020 https://imagemagick.org/
Copyright: (C) 1999 ImageMagick Studio LLC
License: https://imagemagick.org/script/license.php
Features: Cipher DPC HDRI OpenMP(4.5)
Delegates (built-in): bzlib djvu fontconfig freetype jbig jng jp2 jpeg lzma pangocairo png tiff webp x xml zip zlib
Compiler: gcc (8.5)

I have a bunch of images. I want to know the largest empty black rectangle coordinates, width and height so that I can draw a rectangle and put text in them

Thanks,

[fmw42]

That is not a trivial problem. You can solve it relatively easily for the largest circle by finding the maximum brightness from distance morphology. See https://imagemagick.org/Usage/morphology/#distance

A rectangle solution has been implemented in Python. See https://github.com/OpenStitching/lir

[srini8080]

https://stackoverflow.com/questions/21410449/how-do-i-crop-to-largest-interior-bounding-box-in-opencv/21479072#21479072

tried all, did not work. Snigbo's innertrim for unix might help?

[srini8080]

BTW, I could get the circle. I want a max rectangle. Thanks

[snibgo]

Morphology distance directly gives us the largest circle that is available at each pixel, so then we can simply find which pixel has the largest radius.

For rectangles, the task is much harder. Each pixel can be the centre of multiple rectangles with different widths and heights, each of which is a maximum (it can't be extended in any direction). So at each pixel, we need to find which of those maximum rectangles has the maximum area. Then, we can find which pixel has the greatest maximum.

Integral images can be used to find at each pixel, at each possible width, the tallest rectangle, and hence the largest area at that width. Explore the different widths to find the largest area of rectangle centred on that pixel. Explore all the pixels to find which has the largest area.

Doing this in a script would be horribly slow. Some optimisations may be possible. For example, when we know the largest rectangle centred at a pixel, the largest rectangle centred at each of its is likely (but not certain) to have similar dimensions.

The problem can be re-cast. First, generate versions of the input image at all reasonable aspect ratios. Then the task is to find the maximal square at each pixel, at each aspect ratio. The search space for that has only one dimension (the "radius" of the square), so searching is easier. Then we find, for each aspect ratio, which pixel has the largest square. Then we need to examine the solutions found for all the aspect ratios.

See also https://en.wikipedia.org/wiki/Maximum_subarray_problem and https://theory.stanford.edu/~virgi/cs367/papers/maxsubarray.pdf .

(A similar problem is to find the maximal ellipse, which has the same difficulties as the maximal rectangle.)

[srini8080]

From say top 25 circles, get the square. Can we just expand the squares to a rectangles (both directions) to encompass empty space? And take the max area?

That will work for all my images.

[srini8080]

https://github.com/gusenov/max-empty-rect-py

Slow but worked good

[snibgo]

I have written a Windows BAT script to find the maximal rectangle by exhaustive search using IM's -integral and fx. See Maximum rectangles for full details.

For the first supplied image, I run this command:

call %PICTBAT%maxRect %SRC% sriniFull_ dbgFull.png

The text result gives the details (width, height, coords of top-left, coords of bottom-right, etc) of the largest possible black rectangle:

sriniFull__area=110560
sriniFull__crop=691x160+333+864
sriniFull__H=160
sriniFull__W=691
sriniFull__X0=333
sriniFull__X1=1023
sriniFull__Y0=864
sriniFull__Y1=1023

The debugging dbgFull.png image shows the found rectangle:

On my laptop, that command took 41 minutes. Yikes.

We can get a faster result that is probably not a global maximum like this:

call %PICTBAT%maxRect %SRC% sriniFast_ dbgFast.png . "10,10"

The text output is:

sriniFast__area=110285
sriniFast__crop=685x161+333+863
sriniFast__H=161
sriniFast__W=685
sriniFast__X0=333
sriniFast__X1=1017
sriniFast__Y0=863
sriniFast__Y1=1023

That faster command took 29 seconds. The found rectangle is slightly smaller than the maximum.

If that isn't fast enough, then we can use "100,100", which takes 5 seconds, making a rectangle area of 105791 pixels.

[srini8080]

Thanks much. It must have taken you few mins to do this. Now it will take me days to put this into Bash ;-)

Regards

[snibgo]

Yeah, it took a few mins.

Most of the script is to process the input parameters. The important stuff is in the two magick commands, with their fx expressions.

In Windows BAT, environment variables work like this:

set abc=123
echo %abc%

In bash:

abc=123
echo ${abc}

Windows escape char is caret ^. Bash escape char is backslash \.

In Windows BAT, exit /B 1 means exit with an error condition.

If you need more help, just ask.

If you get a bash version working, I encourage you to post it here.