snibgo's ImageMagick pages
Maximum squares and circles
Finding the largest shapes 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 square and largest circle that are entirely black.
On this page, we consider only squares that have sides parallel to the x-axis and y-axis. This doesn't search for rotated squares.
The version of IM does not need to be built with HDRI, and can be Q16 or Q32. It does not need my
process modules.
This page is about finding maximal squares and circles only. These are fairly easy tasks. See also
Maximum rectangles for that more difficult task.
The scripts
maxSquare.bat and
maxCircle.bat uses morphology distance to find the size of every square and circle that have only foreground colours, and returns the details of the largest.
The scripts have these steps:
- Prepare the image, changing the colour of foreground pixels to black, and all other pixels to white. The image is grayscale.
- Apply a -morphology distance operation, which gives the maximum radius at each pixel.
- -identify finds the lightest pixel, so this is the location of the maximum radius at all pixels.
- Adjust the details if the diameters can be extended by one.
The scripts use two variations of -morphology distance: Chebyshev for squares, and Euclidean for circles. These give the "radius", the distance from the centre pixel to the nearest non-foreground pixel. As we want the shape to include the last foreground pixel but not the first non-foreground pixel, we need to subtract one from the radius.
The diameter of the circle (or width and height of the square) are twice the radius plus one. But when the radius and the centre coordinates are integers, the diameter (= 2 * radius + 1) is an odd number, although the gap we are trying to fill may have an even number of pixels.
To fix this problem, we examine the pixels to the east, south-east and south of the found centre. If all four pixels have the same maximum radius, then the square or circle can be extended by one pixel to the east and south.
For the test, we crop to the 4 pixels, then the standard_deviation is zero if the four pixels have the same value.
For the circle: the found radius can be non-integer. Without antialias, IM's -draw "circle cx,cy vx,vy" has an even diameter when the centre coordinates are an integer plus 0.5.
The scripts take the following parameters:
| Parameter |
Description |
| %1 |
Input image to be searched. Must be opaque. |
| %2 |
Prefix for output environment variables.
Default: msq_ or mci_. |
| %3 |
Output image, highlighting the found shape.
Default: no output image. |
| %4 |
Input foreground colour.
Default: Black. |
| %5 |
Minimum radius.
Default "0" (no minimum). |
| %6 |
Maximum radius.
Default: no maximum. |
| %7 |
IM operations to save the
radius map.
Default: map is not saved. |
| %8 |
Input
mask. White where centre can occur; black where it can't.
Default: no mask. |
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 scripts write numbers that describe the found square or circle to environment variables. The prefix for these variables can be specified.
In the following examples, we make an image and find the largest square and largest circle that are entirely black. We show the input image, and versions marked up with the found square and circle.
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" ^
msc_ex_edge.png
call %PICTBAT%maxSquare ^
msc_ex_edge.png ex_edge_ msc_ex_edge_out.png
set ex_edge_
ex_edge__area=3844
ex_edge__Rad=30.5
ex_edge__X0=0
ex_edge__X1=61
ex_edge__XC=30
ex_edge__Y0=69
ex_edge__Y1=130
ex_edge__YC=99
call %PICTBAT%maxCircle ^
msc_ex_edge.png ex_edge_c_ msc_ex_edge_c_out.png
set ex_edge_c_
ex_edge_c__Rad=36
ex_edge_c__XC=36
ex_edge_c__YC=100
|
|
%IMG7%magick ^
-size 200x200 xc:White ^
-fill Black ^
+antialias ^
-draw "ellipse 100,10 80,40 0,360" ^
msc_ex_edge2.png
call %PICTBAT%maxSquare ^
msc_ex_edge2.png ex_edge2_ msc_ex_edge2_out.png
set ex_edge2_
ex_edge2__area=2401
ex_edge2__Rad=24
ex_edge2__X0=73
ex_edge2__X1=121
ex_edge2__XC=97
ex_edge2__Y0=0
ex_edge2__Y1=48
ex_edge2__YC=24
call %PICTBAT%maxCircle ^
msc_ex_edge2.png ex_edge2_c_ msc_ex_edge2_c_out.png
set ex_edge2_c_
ex_edge2_c__Rad=25
ex_edge2_c__XC=94
ex_edge2_c__YC=25
|
|
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" ^
msc_ex_multi.png
call %PICTBAT%maxSquare ^
msc_ex_multi.png ex_multi_ msc_ex_multi_out.png
set ex_multi_
ex_multi__area=1521
ex_multi__Rad=19
ex_multi__X0=91
ex_multi__X1=129
ex_multi__XC=110
ex_multi__Y0=118
ex_multi__Y1=156
ex_multi__YC=137
call %PICTBAT%maxCircle ^
msc_ex_multi.png ex_multi_c_ msc_ex_multi_c_out.png
set ex_multi_c_
ex_multi_c__Rad=20
ex_multi_c__XC=56
ex_multi_c__YC=60
|
|
If two or more centre locations have equally largest squares or circles, the scripts 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" ^
msc_ex_equi.png
call %PICTBAT%maxSquare ^
msc_ex_equi.png ex_equi_ msc_ex_equi_out.png
set ex_equi_
Channel maximum locations:
Gray: 65535 (1) 59,50 60,50 61,50 149,90 150,90 151,90 119,150 120,150 121,150
call %PICTBAT%maxCircle ^
msc_ex_equi.png ex_equi_c_ msc_ex_equi_c_out.png
set ex_equi_c_
ex_equi_c__Rad=20
ex_equi_c__XC=56
ex_equi_c__YC=50
|
|
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 ^
msc_ex_toes.png
call %PICTBAT%maxSquare ^
msc_ex_toes.png ex_toes_ ^
msc_ex_toes_out.png red
set ex_toes_
ex_toes__area=8649
ex_toes__Rad=46
ex_toes__X0=94
ex_toes__X1=186
ex_toes__XC=140
ex_toes__Y0=38
ex_toes__Y1=130
ex_toes__YC=84
call %PICTBAT%maxCircle ^
msc_ex_toes.png ex_toes_c_ ^
msc_ex_toes_c_out.png red
set ex_toes_c_
ex_equi_c__Rad=20
ex_equi_c__XC=56
ex_equi_c__YC=50
|
|
For squares, the script easily calculates the area. For circles, the approximate area is pi*rad2. I haven't reverse-engineered the rasterizing code to derive a general formula for the exact area. We can find the area from the debugging image:
%IMG7%magick ^
msc_ex_equi_c_out.png ^
-fill Black -opaque White ^
-fill White +opaque Black ^
-format "area=%%[fx:floor(mean*w*h+0.5)]\n" ^
info:
area=1313
We can specify the minimum and maximum radius of the shapes. If either or both of these are set, the script will ignore pixels where the maximum radius at that pixel is outside the limits.
If the minimum radius is set, for example to 20, then any pixels where the maximum available radius is less than 20 will be ignored.
If the maximum radius is set, for example to 30, then any pixels where the maximum available radius is more than 30 will be ignored.
For example, if the minimum is set to 20 and the maximum to 30, then the script will find pixels where the maximum radius is between 20 and 30, inclusive, and will return the first of these.
Setting these limits will slightly increase the time taken.
If no pixels are found where the maximum radius is between the limits, the script returns a negative radius.
If we set the minimum and maximum to the same value, the script will find only pixels where the maximum radius is that value.
call %PICTBAT%maxSquare ^
msc_ex_toes.png ex_toesmin_ ^
msc_ex_toesmin_out.png red ^
"20" "30"
set ex_toesmin_
ex_toesmin__area=1681
ex_toesmin__Rad=20
ex_toesmin__X0=163
ex_toesmin__X1=203
ex_toesmin__XC=183
ex_toesmin__Y0=32
ex_toesmin__Y1=72
ex_toesmin__YC=52
call %PICTBAT%maxCircle ^
msc_ex_toes.png ex_toesmin_c_ ^
msc_ex_toesmin_c_out.png red ^
"20" "30"
set ex_toesmin_c_
ex_toesmin_c__Rad=20
ex_toesmin_c__XC=106
ex_toesmin_c__YC=52
|
|
The script returns the first location that has its maximum square or circle within the limits set by the script parameters. Internally to the script, it finds the maximum square or circle at all locations, then eliminates those with radius outside the limits.
A parameter to the script enables us to save the radius 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 radius of the largest square or circle centred on that pixel. These are the values returned by morphology distance, without adustment for the problem that these always yield odd-sized diameters. Values are integers on a nominal scale of 0 to QuantumRange. For example, if the radius map pixel has a value of 100, the maximal radius square at that location has a radius of 99 or 99.5 pixels. If Q16 is used, a value of 100 is 0.0015259 of QuantumRange, or 0.15259%. Radii 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.
These examples don't make a debug image, but do make map images:
call %PICTBAT%maxSquare ^
msc_ex_toes.png . . red ^
. . ^
"-auto-level -write msc_ex_ram.png"
|
|
call %PICTBAT%maxCircle ^
msc_ex_toes.png . . red ^
. . ^
"-auto-level -write msc_ex_ram_c.png"
|
|
The map images for squares and circles are similar, but not identical.
In the map image, lighter pixels show the centres of larger squares or circles. The lightest pixel(s) show the centres of global maximum(s). Because we have done a -auto-level, the lightest pixels are white.
When two or more locations have equally largest squares or circles, the map helps us to retrieve all the shapes. For example, using the image of three equal ellipses created above:
call %PICTBAT%maxSquare ^
msc_ex_equi.png ex_equi2_ msc_ex_equi2_out.png ^
. . . ^
"-auto-level -write msc_ex_equi_map.png"
|
|
We can find the maximum pixels:
%IMG7%magick ^
msc_ex_equi_map.png ^
-define identify:locate=maximum ^
-identify NULL:
Channel maximum locations:
Gray: 65535 (1) 59,50 60,50 61,50 149,90 150,90 151,90 119,150 120,150 121,150
As expected, we have found pairs of coordinates in three areas. However, each area has three adjacent pixels of the maximum lightness. We can reduce the adjacent pixels to isolated pixels like this:
%IMG7%magick ^
msc_ex_equi_map.png ^
-fill Black +opaque White ^
-morphology Thinning:-1 "Skeleton;LineEnds:1^>" ^
-define identify:locate=maximum ^
-identify NULL:
Channel maximum locations:
Gray: 65535 (1) 60,50 150,90 120,150
The map records the maximum radii of the found shapes, but not all possible shapes 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.
A mask can limit the pixels that are considered for the centre of shapes. 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 centre, Where it is white, the location will be a candidate centre.
A mask has no effect on performance.
For a simple example, we constrain the centre to be within a small central circle.
For a more complex example, we loop through the centre locations found in the example above:
set ImgNum=0
for /F "usebackq skip=8 tokens=1,2 delims=," %%A in (`%IMG7%magick ^
msc_ex_equi_map.png ^
-fill Black +opaque White ^
-morphology Thinning:-1 "Skeleton;LineEnds:1^>" ^
-define "identify:locate=maximum" ^
-identify NULL: ^| tr " " "\n" `) do (
echo !ImgNum! [%%A,%%B]
%IMG7%magick ^
msc_ex_equi.png ^
-fill Black -colorize 100 ^
-fill White -draw "point %%A,%%B" ^
%TEMP%\msc_mask!ImgNum!.png
call %PICTBAT%maxSquare msc_ex_equi.png . msc_ex_equi_pr!ImgNum!_out.png ^
. . . . %TEMP%\msc_mask!ImgNum!.png
set /A ImgNum+=1
)
This has created three images:
Elapsed time is proportional to the number of pixels in the image, and is not a problem: maxSquare.bat takes about 0.4 seconds for a 1000x1000 pixel input and maxCircle.bat takes about 0.8 seconds.
A script for maximum ellipse could be useful.
The scripts find shapes that are exactly the foreground colour; it has no "fuzz" facility. This could be added, as an extra step in the pre-processing.
For convenience, .bat scripts are also available in a single zip file. See
Zipped BAT files.
rem From an opaque image, finds maximal square 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 square. Default: no output image.
rem %4 Input foreground colour. Default: Black.
rem %5 Minimum radius. Default "0".
rem %6 Maximum radius. Default: no maximum.
rem %7 IM operations to save the radius 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 centre can occur; black where it can't. Default: no mask.
@rem
@rem Reference: http://im.snibgo.com/maxrect.htm
@rem
@rem See also maxCircle.bat and maxRect.bat.
@if "%1"=="" findstr /B "rem @rem" %~f0 & exit /B 1
@setlocal enabledelayedexpansion
@call echoOffSave
call %PICTBAT%setInOut %1 msq
set EnvPref=%2
if "%EnvPref%"=="." set EnvPref=
if "%EnvPref%"=="" set EnvPref=msq_
set OUTFILE=%3
if "%OUTFILE%"=="." set OUTFILE=
set FgndCol=%~4
if "%FgndCol%"=="." set FgndCol=
if "%FgndCol%"=="" set FgndCol=Black
set MinRad=%~5
if "%MinRad%"=="." set MinRad=
rem if "%MinRad%"=="" set MinRad=0
set MaxRad=%~6
if "%MaxRad%"=="." set MaxRad=
set sMinRad=
if not "%MinRad%"=="" set sMinRad=-black-threshold %%[fx:%MinRad%+1-epsilon]
set sMaxRad=
if not "%MaxRad%"=="" set sMaxRad=-white-threshold %%[fx:%MinRad%+1] -fill Black -opaque White
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 RdMask1="%Mask%" -compose Multiply -composite +compose
set RdMask2=
)
set TmpFile=%TEMP%\msq_tmp.miff
for /F "usebackq skip=1 tokens=2,4,5 delims=:(), " %%A in (`%IMG7%magick ^
%INFILE% ^
-precision 15 ^
+transparent %FgndCol% ^
-fill White -colorize 100 ^
-background Black -layers Flatten ^
-colorspace Gray ^
-alpha off ^
-virtual-pixel Black ^
-morphology Distance "Chebyshev:1,1" ^
-write ftxt:f.txt ^
%sMinRad% %sMaxRad% ^
+depth ^
^( +clone ^
-define "quantum:format=floating-point" ^
-write %TmpFile% ^
+delete ^
^) ^
%sRAM% ^
%RdMask1% ^
-colorspace Gray ^
-write ftxt:f2.txt ^
-define "identify:locate=maximum" ^
-define "identify:limit=1" ^
-identify ^
%RdMask2% ^
NULL:`) do (
set /A Rad=%%A-1
set XC=%%B
set YC=%%C
)
if ERRORLEVEL 1 exit /B 1
if "%Rad%"=="" exit /B 1
echo Centre at %XC%,%YC% Rad=%Rad%
set /A X0=%XC%-(%Rad%)
set /A Y0=%YC%-(%Rad%)
set /A X1=%XC%+(%Rad%)
set /A Y1=%YC%+(%Rad%)
rem FIXME: if central 4 pixels are equal, increment X1 and Y1.
if not %Rad% LSS 0 (
for /F "usebackq" %%L in (`%IMG7%magick ^
%TmpFile% ^
-crop 2x2+%XC%+%YC% +repage ^
-format "SD4=%%[fx:standard_deviation]\n" ^
info:`) do set %%L
if "!SD4!"=="0" (
set /A X1+=1
set /A Y1+=1
set Rad=%Rad%.5
)
)
set /A Area=(%X1%-%X0%+1)*(%Y1%-%Y0%+1)
if not "%OUTFILE%"=="" %IMG7%magick ^
%INFILE% ^
-fill sRGBA(100%%,100%%,0,0.75) ^
+antialias ^
-draw "rectangle %X0%,%Y0% %X1%,%Y1%" ^
%OUTFILE%
call echoRestore
endlocal & set msqOUTFILE=%OUTFILE%& ^
set %EnvPref%_area=%Area%& ^
set %EnvPref%_XC=%XC%& ^
set %EnvPref%_YC=%YC%& ^
set %EnvPref%_Rad=%Rad%& ^
set %EnvPref%_X0=%X0%& ^
set %EnvPref%_X1=%X1%& ^
set %EnvPref%_Y0=%Y0%& ^
set %EnvPref%_Y1=%Y1%
rem From an opaque image, finds maximal circle 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 circle. Default: no output image.
rem %4 Input foreground colour. Default: Black.
rem %5 Minimum radius. Default "0".
rem %6 Maximum radius. Default: no maximum.
rem %7 IM operations to save the radius 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 centre can occur; black where it can't. Default: no mask.
@rem
@rem Reference: http://im.snibgo.com/maxrect.htm
@rem
@rem See also maxSquare.bat and maxRect.bat.
@rem
@if "%1"=="" findstr /B "rem @rem" %~f0 & exit /B 1
@setlocal enabledelayedexpansion
@call echoOffSave
call %PICTBAT%setInOut %1 mci
set EnvPref=%2
if "%EnvPref%"=="." set EnvPref=
if "%EnvPref%"=="" set EnvPref=mci_
set OUTFILE=%3
if "%OUTFILE%"=="." set OUTFILE=
set FgndCol=%~4
if "%FgndCol%"=="." set FgndCol=
if "%FgndCol%"=="" set FgndCol=Black
set MinRad=%~5
if "%MinRad%"=="." set MinRad=
rem if "%MinRad%"=="" set MinRad=0
set MaxRad=%~6
if "%MaxRad%"=="." set MaxRad=
set sMinRad=
if not "%MinRad%"=="" set sMinRad=-black-threshold %%[fx:%MinRad%+1-epsilon]
set sMaxRad=
if not "%MaxRad%"=="" set sMaxRad=-white-threshold %%[fx:%MinRad%+1] -fill Black -opaque White
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 RdMask1="%Mask%" -compose Multiply -composite +compose
set RdMask2=
)
set TmpFile=%TEMP%\mci_tmp.miff
for /F "usebackq skip=1 tokens=2,4,5 delims=:(), " %%A in (`%IMG7%magick ^
%INFILE% ^
-precision 15 ^
+transparent %FgndCol% ^
-fill White -colorize 100 ^
-background Black -layers Flatten ^
-colorspace Gray ^
-alpha off ^
-virtual-pixel Black ^
-morphology Distance "Euclidean:7,1" ^
%sMinRad% %sMaxRad% ^
+depth ^
^( +clone ^
-define "quantum:format=floating-point" ^
-write %TmpFile% ^
+delete ^
^) ^
%sRAM% ^
%RdMask1% ^
-define "identify:locate=maximum" ^
-define "identify:limit=1" ^
-identify ^
%RdMask2% ^
NULL:`) do (
set Rad=%%A
set XC=%%B
set YC=%%C
)
if ERRORLEVEL 1 exit /B 1
if "%Rad%"=="" exit /B 1
rem Note: Rad may not be integer.
for /F "usebackq" %%L in (`%IMG7%magick ^
xc: ^
-format "Rad=%%[fx:floor(%Rad%+0.5)-1]\n" ^
info:`) do set %%L
rem If radius is not negative and central 4 pixels are equal, increment XC and YC by 0.5.
if not %Rad% LSS 0 (
for /F "usebackq" %%L in (`%IMG7%magick ^
%TmpFile% ^
-crop 2x2+%XC%+%YC% +repage ^
-format "SD4=%%[fx:standard_deviation]\n" ^
info:`) do set %%L
if "!SD4!"=="0" (
set XC=%XC%.5
set YC=%YC%.5
set /A Rad+=1
)
)
echo Centre at %XC%,%YC% Rad=%Rad%
if not "%OUTFILE%"=="" (
if %Rad%==0 (
set sDRAW=point %XC%,%YC%
) else (
set sDRAW=translate %XC%,%YC% circle 0,0,%Rad%,0
)
%IMG7%magick ^
%INFILE% ^
-fill "sRGBA^(100%%,100%%,0,0.75^)" ^
+antialias ^
-draw "!sDRAW!" ^
%OUTFILE%
)
call echoRestore
endlocal & set mciOUTFILE=%OUTFILE%& ^
set %EnvPref%_XC=%XC%& ^
set %EnvPref%_YC=%YC%& ^
set %EnvPref%_Rad=%Rad%
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 maxsqc.h1. To re-create this web page, run "procH1 maxsqc".
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 7-March-2024.
Page created 22-Apr-2024 14:11:00.
Copyright © 2024 Alan Gibson.
