snibgo's ImageMagick pages

Maximum rectangles

Finding the largest rectangle of a given solid colour.

Suppose an image contains some black pixels, or some other specified colour (the "foreground" colour). The black pixels may not be entirely connected. The problem is to find the largest rectangle that is entirely black.

On this page, we consider only rectangles that have sides parallel to the x-axis and y-axis. This doesn't search for rotated rectangles.

The method shown here finds all rectangles that are entirely the foreground colour, to find the largest such rectangle. This can be slow, so an option is to find some of the rectangles. This option is faster but probably won't find the largest rectangle. (The rectangle found will be a local maximum, meaning it can't be made larger in any direction, but it probably won't be a global maximum, meaning a rectangle at a different top-left corner is probably larger.)

The version of IM needs to be built with HDRI, and can be Q16 or Q32. It does not need my process modules.

For the simpler problems of finding the largest square or largest circle, see Maximum squares and circles.

References

This page was inspired by a question on the ImageMagick forum.

The method

The script maxRect.bat uses brute force to find the size of every rectangle that has only foreground colours, and returns the details of the largest.

The script has these steps:

  1. Prepare the image, changing the colour of foreground pixels to one (on a scale of zero to QuantumRange), and all other pixels to zero. The image is grayscale.
  2. Apply the -integral operation, so a simple calculation returns the sum of the pixels in a rectangle.
  3. An -fx operation finds (for each pixel) the size of the largest rectangle that is entirely foreground colour and that has its top-left corner at that location. It records this size in the pixel value.
  4. -identify finds the lightest pixel, so this is the location of the best top-left position.
  5. A -format "%%[fx:...]" operation for just that best location finds the width and height of the largest rectangle at that location.

The first fx explores possible rectangles, from 1x1 upwards. At each rectangle, four lookups into the integral image gives the sum of the values in the rectangle. If the pixels in the rectangle in the input image are all foreground, the values will all be one, so the sum of the values will equal the area (the width times height). If the sum is less than the area, some of the pixels must be zero, so the rectangle contains some non-foreground pixels.

The first -fx finds the width and height of each rectangle, and hence the area of each rectangle. So why do we need a -format "%%[fx:...]" operation to get the width and height? Because -fx can return only one value per pixel. It could include debug() functions to dump width and height values, but that would be a large quantity of data to generate and process. So the first -fx records, for each pixel, the size of the largest rectangle, and -identify finds the location of the largest of those largest, and -format "%%[fx:...]" re-does the processing but only for that top-left location, so that is fast.

Instead of using zero and one for the image that is the input to -integral, we could use a very negative value and one. Then we could simply find the largest sum. But that would rely on the negative values being sufficiently low that just one negative value, when added to perhaps a few million ones, is still negative. On the other hand, we might have a few million negative values (which are integrated) and not many ones, and we must not lose precision or the ones will be swamped. The scheme shown here avoids those difficulties.

The running time is O(w2*h2), so it is fourth order. An alternative algorithm (see the Takoaka reference above) has performance better than third order, but it is much more complex.

The script

The script takes the following parameters:

Parameter Description
%1 Input image to be searched. Must be opaque.
%2 Prefix for output environment variables.
Default: mr_.
%3 Output image, highlighting the found rectangle.
Default: no output image.
%4 Input foreground colour.
Default: Black.
%5 Minimum width and height for rectangles.
Default "1,1".
%6 Maximum width and height for rectangles.
Default: input image width and height (effectively, no maximum).
%7 IM operations to save the rectangle area map.
Default: map is not saved.
%8 Input mask. White where top-left can occur; black where it can't.
Default: no mask.
%9 Increment for rectangle width and height.
Default "1,1".

Only the first parameter is mandatory. As usual in my scripts, any parameter can be "." (dot aka period) to use the default. Trailing "dot" parameters can be omitted.

The script uses the alpha channel to rearrange colours, so any alpha channel will be destroyed.

The script writes numbers that describe the found rectangle to environment variables. The prefix for these variables can be specified.

The increment, minimum and maximum rectangle width and height can be used to increase performance but will then usually not find the global maximal rectangle.

Examples

In the following examples, we make an image and find the largest rectangle that is entirely black. We show the input image, and a version marked up with the found rectangle.

%IMG7%magick ^
  -size 200x200 xc:White ^
  -fill Black ^
  +antialias ^
  -draw "ellipse 100,100 80,40 0,360" ^
  mr_ex_ellip.png

call %PICTBAT%maxRect ^
  mr_ex_ellip.png ex_ellip_ mr_ex_ellip_out.png

set ex_ellip_ 
ex_ellip__area=6669
ex_ellip__H=57
ex_ellip__W=117
ex_ellip__X0=42
ex_ellip__X1=158
ex_ellip__Y0=72
ex_ellip__Y1=128
mr_ex_ellip.png mr_ex_ellip_out.png
%IMG7%magick ^
  -size 200x200 xc:Black ^
  -bordercolor White ^
  -border 5 ^
  mr_ex_black2.png

call %PICTBAT%maxRect ^
  mr_ex_black2.png ex_black2_ mr_ex_black2_out.png

set ex_black2_ 
ex_black2__area=40000
ex_black2__H=200
ex_black2__W=200
ex_black2__X0=5
ex_black2__X1=204
ex_black2__Y0=5
ex_black2__Y1=204
mr_ex_black2.png mr_ex_black2_out.png

Special case: all pixels are black.

%IMG7%magick ^
  -size 200x200 xc:Black ^
  mr_ex_black.png

call %PICTBAT%maxRect ^
  mr_ex_black.png ex_black_ mr_ex_black_out.png

set ex_black_ 
ex_black__area=40000
ex_black__H=200
ex_black__W=200
ex_black__X0=0
ex_black__X1=199
ex_black__Y0=0
ex_black__Y1=199
mr_ex_black.png mr_ex_black_out.png

Special case: exactly one pixel is black.

%IMG7%magick ^
  -size 1x1 xc:Black ^
  -bordercolor White ^
  -border 100 ^
  mr_ex_black3.png

call %PICTBAT%maxRect ^
  mr_ex_black3.png ex_black3_ mr_ex_black3_out.png

set ex_black3_ 
ex_black3__area=1
ex_black3__H=1
ex_black3__W=1
ex_black3__X0=100
ex_black3__X1=100
ex_black3__Y0=100
ex_black3__Y1=100
mr_ex_black3.png mr_ex_black3_out.png

Special case: no black pixels.

%IMG7%magick ^
  -size 200x200 xc:White ^
  mr_ex_white.png

call %PICTBAT%maxRect ^
  mr_ex_white.png ex_white_ mr_ex_white_out.png

set ex_white_ 
ex_white__area=-9e+09
ex_white__H=-999
ex_white__W=-999
ex_white__X0=0
ex_white__X1=-1000
ex_white__Y0=0
ex_white__Y1=-1000

A negative dimension means no rectangle was possible.

mr_ex_white.png mr_ex_white_out.png

The foreground colour can reach the edge of the image:

%IMG7%magick ^
  -size 200x200 xc:White ^
  -fill Black ^
  +antialias ^
  -draw "ellipse 10,100 80,40 0,360" ^
  mr_ex_edge.png

call %PICTBAT%maxRect ^
  mr_ex_edge.png ex_edge_ mr_ex_edge_out.png

set ex_edge_ 
ex_edge__area=3953
ex_edge__H=59
ex_edge__W=67
ex_edge__X0=0
ex_edge__X1=66
ex_edge__Y0=71
ex_edge__Y1=129
mr_ex_edge.png mr_ex_edge_out.png
%IMG7%magick ^
  -size 200x200 xc:White ^
  -fill Black ^
  +antialias ^
  -draw "ellipse 100,10 80,40 0,360" ^
  mr_ex_edge2.png

call %PICTBAT%maxRect ^
  mr_ex_edge2.png ex_edge2_ mr_ex_edge2_out.png

set ex_edge2_ 
ex_edge2__area=4572
ex_edge2__H=36
ex_edge2__W=127
ex_edge2__X0=37
ex_edge2__X1=163
ex_edge2__Y0=0
ex_edge2__Y1=35
mr_ex_edge2.png mr_ex_edge2_out.png

There may be multiple non-connected areas of foreground colour:

%IMG7%magick ^
  -size 200x200 xc:White ^
  -fill Black ^
  +antialias ^
  -draw "ellipse 60,60 40,20 0,360" ^
  -draw "ellipse 110,140 20,60 0,360" ^
  -draw "rectangle 140,30 160,90" ^
  mr_ex_multi.png

call %PICTBAT%maxRect ^
  mr_ex_multi.png ex_multi_ mr_ex_multi_out.png

set ex_multi_ 
ex_multi__area=2581
ex_multi__H=89
ex_multi__W=29
ex_multi__X0=96
ex_multi__X1=124
ex_multi__Y0=96
ex_multi__Y1=184
mr_ex_multi.png mr_ex_multi_out.png

If two or more top-left locations have equally largest rectangles, the script will find only one:

%IMG7%magick ^
  -size 200x200 xc:White ^
  -fill Black ^
  +antialias ^
  -draw "ellipse 60,50 40,20 0,360" ^
  -draw "ellipse 150,90 40,20 0,360" ^
  -draw "ellipse 120,150 40,20 0,360" ^
  mr_ex_equi.png

call %PICTBAT%maxRect ^
  mr_ex_equi.png ex_equi_ mr_ex_equi_out.png

set ex_equi_ 
Channel maximum locations:
  Gray: 65535 (1) 31,36 121,76 91,136
mr_ex_equi.png mr_ex_equi_out.png

If the foreground colour is not black, it must be specified as a parameter to the script.

%IMG7%magick ^
  xc:Lime xc:Red ^
  +append +repage -write mpr:MAP ^
  +delete ^
  toes.png +dither -remap mpr:MAP ^
  mr_ex_toes.png

call %PICTBAT%maxRect ^
  mr_ex_toes.png ex_toes_ ^
  mr_ex_toes_out.png red

set ex_toes_ 
ex_toes__area=10416
ex_toes__H=93
ex_toes__W=112
ex_toes__X0=94
ex_toes__X1=205
ex_toes__Y0=38
ex_toes__Y1=130
mr_ex_toes.png mr_ex_toes_out.png

Instead of exploring every width and height, we can explore, say, every tenth width and every tenth height in the first fx. This will be faster by a factor of up to 100 and will find a local maximum but this may not be the global maximum. (The found width and height will be the best for the found top-left, but a different top-left might have a larger rectangle.)

In these examples, we use the same input image.

call %PICTBAT%maxRect ^
  mr_ex_ellip.png ex_ellip1_ mr_ex_ellip1_out.png ^
  . . . . . "1,1"

set ex_ellip1_ 
ex_ellip1__area=6669
ex_ellip1__H=57
ex_ellip1__W=117
ex_ellip1__X0=42
ex_ellip1__X1=158
ex_ellip1__Y0=72
ex_ellip1__Y1=128

The global maximum has been found.

mr_ex_ellip1_out.png
call %PICTBAT%maxRect ^
  mr_ex_ellip.png ex_ellip10_ mr_ex_ellip10_out.png ^
  . . . . . "10,10"

set ex_ellip10_ 
ex_ellip10__area=6519
ex_ellip10__H=53
ex_ellip10__W=123
ex_ellip10__X0=39
ex_ellip10__X1=161
ex_ellip10__Y0=74
ex_ellip10__Y1=126

The found area is less than the global maximum.

mr_ex_ellip10_out.png
call %PICTBAT%maxRect ^
  mr_ex_ellip.png ex_ellip100_ mr_ex_ellip100_out.png ^
  . . . . . "100,100"

set ex_ellip100_ 
ex_ellip100__area=6489
ex_ellip100__H=63
ex_ellip100__W=103
ex_ellip100__X0=49
ex_ellip100__X1=151
ex_ellip100__Y0=69
ex_ellip100__Y1=131

The found area is less than the global maximum.

mr_ex_ellip100_out.png

We can specify the minimum width and height, and maximum width and height, of the rectangles in the -fx search space. These are used only to find the best top-left location. If the maximum limits are set, the found rectangle may be larger than the limit. Setting these limits will increase the speed.

The minimum settings would be useful if we want to find a suitable location to insert another image, or text. It doesn't bother exploring smaller rectangles so that saves time. If no rectangles exist at or above the minimums, the script returns negative dimensions.

If we set the minimum and maximum to the same values, the script will search for rectangles of only that size, so it will be fast.

call %PICTBAT%maxRect ^
  mr_ex_toes.png ex_toesmin_ ^
  mr_ex_toesmin_out.png red ^
  "30,20" "30,20"

set ex_toesmin_ 
ex_toesmin__area=5762
ex_toesmin__H=134
ex_toesmin__W=43
ex_toesmin__X0=163
ex_toesmin__X1=205
ex_toesmin__Y0=32
ex_toesmin__Y1=165
mr_ex_toes.png mr_ex_toesmin_out.png

The script returns the first location that is the top-left corner of a 30x20 rectangle. It doesn't search for the locations of any other sizes. At that location, the locally maximal rectangle is 43x134 pixels. So if we want to insert a 30x20 object, it could go anywhere within that 43x134 rectangle. (The rectangle area map image shows all locations that can be the top-left corner of a 30x20 rectangle.)

Rectangle area map

A parameter to the script enables us to save the rectangle area map. The parameter should be one or more complete IM operations, such as "-write x.png" or "-auto-level -write x.png".

The map records, at each pixel, the area of the largest rectangle which has that pixel as the top-left corner. Values are on a nominal scale of 0 to QuantumRange. For example, a rectangle with an area of 1000 pixels will have a value of 1000. If Q16 is used, a value of 1000 is 0.015259 of QuantumRange, or 1.5259%. Rectangles can be large, eg 1 million pixels, so QuantumRange can be exceeded. For this reason, we should save as floating-point, or -auto-level if saving to an integer format such as PNG.

This example doesn't make a debug image, but does make a map image:

call %PICTBAT%maxRect ^
  mr_ex_toes.png . . red ^
  . . ^
  "-auto-level -write mr_ex_ram.png"
mr_ex_ram.png

In the map image, lighter pixels show the top-left of larger rectangles. The lightest pixel(s) show the top-left of global maximum(s). Because we have done a -auto-level, the lightest pixels are white.

When two or more top-left locations have equally largest rectangles, the map helps us to retrieve all the rectangles. For example, using the image of three equal ellipses created above:

call %PICTBAT%maxRect ^
  mr_ex_equi.png ex_equi2_ mr_ex_equi2_out.png ^
  . . . ^
  "-auto-level -write mr_ex_equi_map.png"
mr_ex_equi.png mr_ex_equi_map.png
%IMG7%magick ^
  mr_ex_equi_map.png ^
  -define identify:locate=maximum ^
  -identify NULL: 
Channel maximum locations:
  Gray: 65535 (1) 31,36 121,76 91,136

[No image]

As expected, there are three pairs of coordinates.

The map records the maximum area of the found rectangles, but not all possible rectangles may have been found. If increment and maximum have not been set, then the map will include the global maximum. But if either has been set, the global maximum may not have been found.

Masking the search area

A mask can limit the pixels that are considered for the top-left corner of rectangles. The mask should be the same size as the input image, and should contain black and white pixels only. Where the mask is black, that location will not be considered for a top-left corner, Where it is white, the location will be a candidate top-left corner.

A mask has no effect on performance.

For a simple example, we constrain the top-left corner to be within a small central circle.

Make a mask, white where we want the top-left corner.

%IMG7%magick ^
  mr_ex_toes.png ^
  -fill Black -colorize 100 ^
  -fill White -draw ^
    "translate %%[fx:w/2],%%[fx:h/2] circle 0,0,20,0" ^
  mr_mask.png
mr_mask.png
call %PICTBAT%maxRect ^
  mr_ex_toes.png ex_mask_ ^
  mr_ex_mask_out.png red ^
  . . . mr_mask.png

set ex_mask_ 
ex_mask__area=1547
ex_mask__H=13
ex_mask__W=119
ex_mask__X0=148
ex_mask__X1=266
ex_mask__Y0=130
ex_mask__Y1=142
mr_ex_mask_out.png

For a more complex example, we loop through the top-left locations found in the example above:

set ImgNum=0
for /F "usebackq skip=8 tokens=1,2 delims=," %%A in (`%IMG7%magick ^
  mr_ex_equi_map.png ^
  -define "identify:locate=maximum" ^
  -identify NULL: ^| tr " " "\n" `) do (
  echo !ImgNum! [%%A,%%B]

  %IMG7%magick ^
    mr_ex_equi.png ^
    -fill Black -colorize 100 ^
    -fill White -draw "point %%A,%%B" ^
    %TEMP%\mr_mask!ImgNum!.png

  call %PICTBAT%maxRect mr_ex_equi.png . mr_ex_equi_pr!ImgNum!_out.png ^
    . . . . %TEMP%\mr_mask!ImgNum!.png

  set /A ImgNum+=1
)

This has created three images:

mr_ex_equi_pr0_out.png mr_ex_equi_pr1_out.png mr_ex_equi_pr2_out.png

Performance

Performance is reasonable for images of 200x200 pixels; typically 2 seconds on my laptop, but the worst case takes longer. 1000x1000 images take around 30 minutes.

The best-case performance is when no pixels are the foreground colour. The script then takes virtually no time.

The worst-case performance is when all pixels are the foreground colour. For this case, setting the increment for width and height, or maximum width and height, will greatly increase performance while returning the same result.

The increment parameter greatly improves performance (eg an increment of 10 on both directions improves performance by better than a factor of 50) but the result is unlikely to be the global maximum.

Future

A multi-scale approach may assist performance.

The script contains optimisations at each top-left location. In principle, optimisations are also possible across locations. For example, if the largest rectangle found so far has an area of 3000 pixels, then any top-left location to the lower-right of a certain diagonal line cannot have a rectangle larger than 3000 pixels, so need not be considered.

The maximal circle problem is simple, using morphology distance. The maximal ellipse problem has similar difficulties to the maximal rectangle, but integral images are not helpful in that case, as far as I can see. A maximal rectangle defines a possible ellipse, but that ellipse is unlikely to be maximal.

The script finds rectangles that are exactly the foreground colour; it has no "fuzz" facility. This could be added, as an extra step in the pre-processing.

We might want to find the largest rectangle of a given aspect ratio, such as 1:1 (square) or 1:1.618. Fixed-ratio rectangles have one degree of freedom instead of two, so the fx code can be simplified: instead of looping through all combinations of width and height, loop through just one and calculate the other. For aspect ratio 1:1 (squares), see Maximum squares and circles. For other aspect ratios, the image could be resized appropriately, then that is searched for a square.

Scripts

For convenience, .bat scripts are also available in a single zip file. See Zipped BAT files.

maxRect.bat

rem From an opaque image, finds maximal rectangle where all pixels are a given foreground colour.
rem
rem %1 Input image.
rem %2 Prefix for output environment variables.
rem %3 Output image, highlighting the found rectangle. Default: no output image.
rem %4 Input foreground colour. Default: Black.
rem %5 Minimum width and height for rectangles. Default "1,1".
rem %6 Maximum width and height for rectangles. Default: input image width and height.
rem %7 IM operations to save the rectangle area map. Default: map is not saved.
@rem    Example operations:
@rem      -write ramap.png
@rem      -auto-level -write ramap.png
@rem      -define quantum:format=floating-point -write ramap.miff
rem %8 Input mask. White where top-left can occur; black where it can't. Default: no mask.
rem %9 Increment for width and height. Default "1,1".
@rem
@rem Reference: http://im.snibgo.com/maxrect.htm
@rem
@rem See also maxSquare and maxCircle.bat.
@rem
@rem Also need:
@rem   range of top-left locations
@rem

@if "%1"=="" findstr /B "rem @rem" %~f0 & exit /B 1

@setlocal enabledelayedexpansion

@call echoOffSave

call %PICTBAT%setInOut %1 mr

set EnvPref=%2
if "%EnvPref%"=="." set EnvPref=
if "%EnvPref%"=="" set EnvPref=mr_

set OUTFILE=%3
if "%OUTFILE%"=="." set OUTFILE=

set FgndCol=%~4
if "%FgndCol%"=="." set FgndCol=
if "%FgndCol%"=="" set FgndCol=Black

set MinWH=%~5
if "%MinWH%"=="." set MinWH=
if "%MinWH%"=="" set MinWH=1,1

set MaxWH=%~6
if "%MaxWH%"=="." set MaxWH=

set SaveRam=%~7
if "%SaveRam%"=="." set SaveRam=

if "%SaveRam%"=="" (
  set sRAM=
) else (
  set sRAM="(" +clone %SaveRam% +delete ")"
)

set Mask=%~8
if "%Mask%"=="." set Mask=

if "%Mask%"=="" (
  set WrMask1=
  set WrMask2=
  set RdMask1=
  set RdMask2=
) else (
  set WrMask1=-write-mask "%Mask%"
  set WrMask2=+write-mask
  set RdMask1=-read-mask "%Mask%"
  set RdMask2=+read-mask
)

set IncWH=%~9
if "%IncWH%"=="." set IncWH=
if "%IncWH%"=="" set IncWH=1,1

set IncH=1
set IncW=1

call parseCommaList "%IncWH%" num_inc vals_inc

if "%num_inc%"=="1" (
  set IncW=%vals_inc[0]%
  set IncH=1
) else if "%num_inc%"=="2" (
  set IncW=%vals_inc[0]%
  set IncH=%vals_inc[1]%
) else (
  echo Bad parameter IncWH: [%IncWH%]
  exit /B 1
)

echo IncW=%IncW% IncH=%IncH%


set MinW=1
set MinH=1

call parseCommaList "%MinWH%" num_inc vals_inc

if "%num_inc%"=="1" (
  set MinW=%vals_inc[0]%
) else if "%num_inc%"=="2" (
  set MinW=%vals_inc[0]%
  set MinH=%vals_inc[1]%
) else (
  echo Bad parameter MinWH: [%MinWH%]
  exit /B 1
)

echo MinW=%MinW% MinH=%MinH%


set MaxW=w
set MaxH=h

call parseCommaList "%MaxWH%" num_inc vals_inc

if "%num_inc%"=="1" (
  set MaxW=%vals_inc[0]%
) else if "%num_inc%"=="2" (
  set MaxW=%vals_inc[0]%
  set MaxH=%vals_inc[1]%
) else if not "%num_inc%"=="0" (
  echo Bad parameter MaxWH: [%MaxWH%]
  exit /B 1
)

echo MaxW=%MaxW% MaxH=%MaxH%

set TmpFile=%TEMP%\mr_tmp.miff

set X0=
set Y0=

set sFX=^
  maxVal = -9e9; ^
  areaMax = maxVal; ^
  okayW = 1; ^
  pZeroR = p[-1,-1]; ^
  thisMaxH = %MaxH%; ^
  for (ww=%MinW%, ww ^<= %MaxW% ^&^& i+ww ^<= w ^&^& okayW, ^
    wmOne = ww-1; ^
    pwwR = p[wmOne,-1]; ^
    okayH = 1; ^
    for (hh=%MinH%, hh ^<= thisMaxH ^&^& j+hh ^<= h ^&^& okayH, ^
      hmOne = hh-1; ^
      sum = floor ((pZeroR-p[-1,hmOne]-pwwR+p[wmOne,hmOne]) * QuantumRange + 0.5); ^
      area = ww * hh; ^
      if (sum == area, ^
        if (maxVal ^< sum, ^
            maxVal = sum; areaMax = area ^
           , ) ^
      , okayH = 0; thisMaxH = hh; if (hh==1, okayW = 0, ) ^
      ); ^
      hh += %IncH% ^
    ); ^
    ww += %IncW% ^
  ); ^
  if (i == 9999, debug(areaMax) , ); ^
  (areaMax ^< 0) ? 0 : areaMax/QuantumRange;

for /F "usebackq skip=1 tokens=4,5 delims=:(), " %%A in (`%IMG7%magick ^
  %INFILE% ^
  -precision 15 ^
  +transparent %FgndCol% ^
  -fill Black -colorize 100 ^
  -background White -layers Flatten ^
  -colorspace Gray ^
  -alpha off ^
  -negate ^
  -evaluate Min 1 ^
  -define "quantum:format=floating-point" -depth 32 ^
  -integral ^
  -write %TmpFile% ^
  -virtual-pixel Black ^
  %WrMask1% ^
  -fx "%sFX%" ^
  %WrMask2% ^
  %sRAM% ^
  %RdMask1% ^
  -define "identify:locate=maximum" ^
  -define "identify:limit=1" ^
  -identify ^
  %RdMask2% ^
  NULL:`) do (
  set X0=%%A
  set Y0=%%B
  echo top-left at  %%A, %%B
)

if "%X0%"=="" exit /B 1
if "%Y0%"=="" exit /B 1

rem Now find the width and height for the largest rectangle with top-left at X0,Y0.

set sFX2=^
  maxVal = -9e9; ^
  areaMax = maxVal; ^
  okayW = 1; ^
  pZeroR = p[%X0%-1,%Y0%-1]; ^
  thisMaxH = h; ^
  wwAtMax = -999; ^
  hhAtMax = -999; ^
  for (ww=%MinW%, ww ^<= w ^&^& %X0%+ww ^<= w ^&^& okayW, ^
    wmOne = ww-1; ^
    pwwR = p[%X0%+wmOne,%Y0%-1]; ^
    okayH = 1; ^
    for (hh=%MinH%, hh ^<= thisMaxH ^&^& %Y0%+hh ^<= h ^&^& okayH, ^
      hmOne = hh-1; ^
      sum = floor ((pZeroR-p[%X0%-1,%Y0%+hmOne]-pwwR+p[%X0%+wmOne,%Y0%+hmOne]) * QuantumRange + 0.5); ^
      area = ww * hh; ^
      if (sum == area, ^
        if (maxVal ^< sum, ^
            maxVal = sum; areaMax = area; wwAtMax = ww; hhAtMax = hh; ^
           , ) ^
      , okayH = 0; thisMaxH = hh; if (hh==1, okayW = 0, ) ^
      ); ^
      hh++ ^
    ); ^
    ww++ ^
  ); ^
  debug(wwAtMax); ^
  debug(hhAtMax); ^
  debug(areaMax); ^
  areaMax;

set wwAtMax=
set hhAtMax=
for /F "usebackq tokens=2,3 delims=:= " %%A in (`%IMG7%magick ^
  %TmpFile% ^
  -virtual-pixel Black ^
  -format "%%[fx:%sFX2%]\n" ^
  info: 2^>^&1`) do (
  if "%%A"=="wwAtMax" set wwAtMax=%%B
  if "%%A"=="hhAtMax" set hhAtMax=%%B
  if "%%A"=="areaMax" set areaMax=%%B
)
if "%wwAtMax%"=="" exit /B 1
if "%hhAtMax%"=="" exit /B 1

set /A X1=%X0%+%wwAtMax%-1
set /A Y1=%Y0%+%hhAtMax%-1

if not "%OUTFILE%"=="" %IMG7%magick ^
  %INFILE% ^
  -fill sRGBA(100%%,100%%,0,0.75) ^
  -draw "rectangle %X0%,%Y0%,%X1%,%Y1%" ^
  %OUTFILE%

call echoRestore

endlocal & set mrOUTFILE=%OUTFILE%& ^
set %EnvPref%_area=%areaMax%& ^
set %EnvPref%_H=%hhAtMax%& ^
set %EnvPref%_W=%wwAtMax%& ^
set %EnvPref%_X0=%X0%& ^
set %EnvPref%_X1=%X1%& ^
set %EnvPref%_Y0=%Y0%& ^
set %EnvPref%_Y1=%Y1%

All images on this page were created by the commands shown, using:

%IMG7%magick -version
Version: ImageMagick 7.1.1-20 Q16-HDRI x86 98bb1d4:20231008 https://imagemagick.org
Copyright: (C) 1999 ImageMagick Studio LLC
License: https://imagemagick.org/script/license.php
Features: Cipher DPC HDRI OpenCL OpenMP(2.0) 
Delegates (built-in): bzlib cairo freetype gslib heic jng jp2 jpeg jxl lcms lqr lzma openexr pangocairo png ps raqm raw rsvg tiff webp xml zip zlib
Compiler: Visual Studio 2022 (193532217)

To improve internet download speeds, some images may have been automatically converted (by ImageMagick, of course) from PNG or TIFF or MIFF to JPG.

Source file for this web page is maxrect.h1. To re-create this web page, run "procH1 maxrect".


This page, including the images, is my copyright. Anyone is permitted to use or adapt any of the code, scripts or images for any purpose, including commercial use.

Anyone is permitted to re-publish this page, but only for non-commercial use.

Anyone is permitted to link to this page, including for commercial use.


Page version v1.0 1-March-2024.

Page created 22-Apr-2024 14:45:25.

Copyright © 2024 Alan Gibson.