snibgo's ImageMagick pages

Trimming triangles

Remove virtual pixels added by some distortions.

• References
• Sample inputs
• The script
• Cumulating crops
• Future
• Scripts

IM's "-trim" operation removes edge pixels when they are the same, or within "-fuzz" of being the same. We often add a one-pixel border of a certain colour first, and "-trim" will then ensure that no edge contains entirely the border colour, without removing edges that contain a mix of border and non-border pixels. There is always one single perfect solution to that problem, which IM finds.

Sometimes, we want to go further, and ensure that no edge contains any pixels of the border colour. There is generally no single perfect solution to that problem. The result we get depends on the algorithm we use to find it.

Some IM geometric distortions preserves collinearity (points that were on a straight line remain on a straight line). These include -distort Affine, -distort Perspective and -distort SRT. So the four edges of the input image will be four straight lines in the output, and pixels outside this quadrilateral will be populated according to the -virtual-pixel setting.

The overall effect is that triangles or similar shapes are added outside the original image. We may want to crop the output so these added shapes are entirely removed.

Taking this a stage further: we might apply different distortions to frames in a video sequence, and want to find the minimal crop that can be applied equally to all the frames so that all the added shapes are removed.

This is a special case of trimming. For more general cases, see Inner Trim.

References

• Wikipedia: Bresenham's line algorithm.

Sample inputs

We will distort this input image:

set SRC=tt_src.png call %PICTBAT%gridOver ^ toes.png %SRC% 8 8

Images don't usually have grids, but this helps us see what is happening.

Sample distortions:

%IMG7%magick ^ %SRC% ^ -virtual-pixel None ^ -distort SRT 0.8,10 +repage ^ tt_sampdist1.png
%IMG7%magick ^ %SRC% ^ -virtual-pixel None ^ -distort SRT 0.8,30 +repage ^ tt_sampdist2.png
%IMG7%magick ^ %SRC% ^ -virtual-pixel None ^ +distort SRT 0.8,30 +repage ^ tt_sampdist3.png
%IMG7%magick ^ %SRC% ^ -virtual-pixel None ^ +distort perspective ^ "0,0,30,0 260,0,250,10 0,230,0,230 260,230,260,230" ^ +repage ^ tt_sampdist3.png

The script

The script trimTri.bat finds a locally-maximal rectangle of a required aspect ratio, which defaults to the same aspect ratio as the input. This is useful when source images are video frames that have undergone a collinear-preserving distortion, and we want to crop in the video's aspect ratio. The script examines pixels along the diagonals, from the corners inwards using Bresenham's line algorithm, seeking the first white pixel. If the border has no concavity, all pixels within the quadrilateral defined by these four white pixels are white. From the eight coordinates of these four white pixels, the script readily calculates the minimum necessary crop on each of the four sides.

This works for images where, for any two points inside the boundary, all points on the line joining those points are also inside the boundary.

Most images need some pre-processing to make all interior pixels white. For example, when the border is transparent, "-extract Alpha" will make all opaque pixels white.

set ttPREPROC=-alpha extract

The result is the parameters for a crop of the input to the script, with approximately the required aspect ratio. The algorithm does not guarantee the crop is the largest possible crop with that aspect ratio. Nor does it guarantee the crop can't be extended in some direction to make a larger crop (with different aspect ratio).

In the examples, we set ttDEBUG to create a debugging image that is the input image with green lines showing the pixels examined from the corners to find the first white pixels, and a green rectangle showing the crop.

set ttDEBUG=tt_dbg1.png call %PICTBAT%trimTri ^ tt_sampdist1.png tt_abc set tt_abc tt_abc.Bottom=38 tt_abc.Crop=181x157+43+38 tt_abc.H=157 tt_abc.Left=43 tt_abc.Okay=1 tt_abc.Right=43 tt_abc.Top=38 tt_abc.W=181
set ttDEBUG=tt_dbg2.png call %PICTBAT%trimTri ^ tt_sampdist2.png tt_abc set tt_abc tt_abc.Bottom=52 tt_abc.Crop=147x129+60+52 tt_abc.H=129 tt_abc.Left=60 tt_abc.Okay=1 tt_abc.Right=60 tt_abc.Top=52 tt_abc.W=147
set ttDEBUG=tt_dbg3.png call %PICTBAT%trimTri ^ tt_sampdist3.png tt_abc set tt_abc tt_abc.Bottom=2 tt_abc.Crop=227x210+28+24 tt_abc.H=210 tt_abc.Left=28 tt_abc.Okay=1 tt_abc.Right=14 tt_abc.Top=24 tt_abc.W=227
Repeat the last, but find a 2:1 crop set ttDEBUG=tt_dbg4.png call %PICTBAT%trimTri ^ tt_sampdist3.png tt_abc 2x1 set tt_abc tt_abc.Bottom=55 tt_abc.Crop=234x118+24+63 tt_abc.H=118 tt_abc.Left=24 tt_abc.Okay=1 tt_abc.Right=11 tt_abc.Top=63 tt_abc.W=234
Repeat the last, but find a 1:2 crop set ttDEBUG=tt_dbg5.png call %PICTBAT%trimTri ^ tt_sampdist3.png tt_abc 1x2 set tt_abc tt_abc.Bottom=2 tt_abc.Crop=112x225+77+9 tt_abc.H=225 tt_abc.Left=77 tt_abc.Okay=1 tt_abc.Right=80 tt_abc.Top=9 tt_abc.W=112

We show an example from the Inner Trim page. The image already has "white" defining the inner pixels, so we don't need any pre-process.

set ttPREPROC= set ttDEBUG=tt_dbg_bad.png call %PICTBAT%trimTri ^ it_trimbw.png tt_abc set tt_abc tt_abc.Bottom=8 tt_abc.Crop=197x106+25+13 tt_abc.H=106 tt_abc.Left=25 tt_abc.Okay=0 tt_abc.Right=21 tt_abc.Top=13 tt_abc.W=197

The process has failed because the white portion is not entirely convex. The variable tt_abc.Okay registers the failure.

Cumulating crops

When a sequence of video frames have been distorted in different ways, perhaps resulting in different sizes, we want to find a crop that can be applied to all frames such that no frames have virtual pixels.

We call the script for every frame in the series, with the same environment variable prefix. For the first frame in the series, we set parameter %4 to "first" or leave it blank. For each following frame, we set the parameter to "cumul".

The resulting cumulative crop will probably have diverged from the requested aspect ratio. An application may need to apply a further crop to obtain the exact aspect ratio.

For example, we apply a 2:1 crop to each of the first three inputs above, cumulating the result.

set ttDEBUG=
set ttPREPROC=-alpha extract

call %PICTBAT%trimTri ^
  tt_sampdist1.png tt_cumul 2x1 first
if ERRORLEVEL 1 exit /B 1

call %PICTBAT%trimTri ^
  tt_sampdist2.png tt_cumul 2x1 cumul
if ERRORLEVEL 1 exit /B 1

call %PICTBAT%trimTri ^
  tt_sampdist3.png tt_cumul 2x1 cumul
if ERRORLEVEL 1 exit /B 1

set tt_cumul 

tt_cumul.Bottom=69
tt_cumul.Crop=193x98+38+69
tt_cumul.H=98
tt_cumul.Left=38
tt_cumul.Okay=1
tt_cumul.Right=38
tt_cumul.Top=69
tt_cumul.W=193

We check the results:

set RECT=^ rectangle ^ %tt_cumul.Left%,^ %tt_cumul.Top%,^ %%[fx:w-1-%tt_cumul.Right%],^ %%[fx:h-1-%tt_cumul.Bottom%] %IMG7%magick ^ tt_sampdist1.png ^ -fill None -stroke #44f ^ -draw "%RECT%" ^ tt_chk1.png %IMG7%magick ^ tt_sampdist2.png ^ -fill None -stroke #44f ^ -draw "%RECT%" ^ tt_chk2.png %IMG7%magick ^ tt_sampdist3.png ^ -fill None -stroke #44f ^ -draw "%RECT%" ^ tt_chk3.png

As expected, we have found a crop we can apply to all images so that no result contains any virtual pixels.

If input images have no overlap, no solution is possible, and the script will return a negative .W or .H, and a 0 value for .Okay.

Future

The script reads an image multiple times, potentially hundred of times. A process module wouldn't need to do this, so would be much faster.

The script could test that the crop is entirely white.

Sometimes the found crop can be extended before bumping into the boundary (which also changes the aspect ratio). The script could be given an option to do this.

Scripts

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

trimTri.bat

rem %1 is an image, white with black border.
rem %2 prefix for output environment variables.
rem %3 is WxH, required aspect ratio.
rem %4 mode, either "first" or "cumul".
rem Finds crop parameters.
@rem
@rem Also uses:
@rem   ttPREPROC pre-processing for the image eg "-alpha extract".
@rem   ttDEBUG if not blank, writes debugging image
@rem
@rem This script needs IM v7 for the debugging image.

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

@setlocal enabledelayedexpansion

@call echoOffSave

set INFILE=%1

set EvPref=%2
if "%EvPref%"=="." set EvPref=
if "%EvPref%"=="" set EvPref=tt

set Mode=%4
if "%Mode%"=="." set Mode=
if "%Mode%"=="" set Mode=first

if /I not %Mode%==first if /I not %Mode%==cumul (
  echo Mode [%Mode%] should be first or cumul.
)

set TMP_IN=%TEMP%\tt_tmp.miff

set WW=
for /F "usebackq" %%L in (`%IMG7%magick ^
  %INFILE% ^
  %ttPREPROC% ^
  -format "WW=%%w\nHH=%%h\n" ^
  -write info: ^
  %TMP_IN%`) do set %%L

if "%WW%"=="" exit /B 1

echo WW=%WW% HH=%HH%

set reqAR=%3
if "%reqAR%"=="." set reqAR=
set x0=0
set y0=0
if not "%reqAR%"=="" (
  echo reqAR=%reqAR%
  call parseXxY %WW% %HH% %reqAR%

  set raW=!pxxyX!
  set raH=!pxxyY!

  echo raW=!raW! raH=!raH!

  set /A WWraH=%WW%*!raH!
  set /A HHraW=%HH%*!raW!

  echo WWraH=!WWraH! HHraW=!HHraW!

  if !WWraH! GTR !HHraW! (
    echo required is taller
    set /A rqH=%WW%*!raH!/!raW!
    echo rqH=!rqH!
    set /A x0=^(%WW% - %HH%^*!raW!/!raH!^)/2
  ) else if !WWraH! LSS !HHraW! (
    echo required is wider
    set /A rqW=%HH%*!raW!/!raH!
    set /A extraW=^(!rqW!-%WW%^)/2
    echo rqW=!rqW! extraW=!extraW!
    set /A y0x=!extraW!*%HH%/!rqW!
    set /A y0=^(%HH% - %WW%^*!raH!/!raW!^)/2
  )
)

echo x0=%x0% y0=%y0% y0x=%y0x%

if "%x0%"=="." set x0=
if "%x0%"=="" set x0=0
if "%y0%"=="." set y0=
if "%y0%"=="" set y0=0

set x1=
set y1=
for /F "usebackq" %%L in (`%IMG7%magick identify ^
  -format "x1=%%[fx:floor((w-1)/2)]\ny1=%%[fx:floor((h-1)/2)]" ^
  %TMP_IN%`) do set %%L

rem echo x1=%x1% y1=%y1%

if "%x1%"=="" exit /B 1

rem Referece: Bresenham

set /A dx=%x1%-%x0%
set /A dy=%y1%-%y0%
set yi=1
if %dy% LSS 0 (
  set yi=-1
  set dy=-dy
)

set xi=1
if %dx% LSS 0 (
  set xi=-1
  set dx=-dx
)

set x0img=%x0%
set y0img=%y0%

set rev=0
if %dy% GTR %dx% (
  set rev=1

  set t=%x0%
  set x0=%y0%
  set y0=!t!

  set t=%x1%
  set x1=%y1%
  set y1=!t!

  set t=%dx%
  set dx=%dy%
  set dy=!t!
)

set /A D=2*%dy%-%dx%
set /A y=%y0%

set fndTL=0
set fndTR=0
set fndBL=0
set fndBR=0
set fndAll=0

echo off

for /L %%X in (%x0%,%xi%,%x1%) do (
  if !fndAll!==0 (
    if %rev%==0 (
      set imgx=%%X
      set imgy=!y!
    ) else (
      set imgx=!y!
      set imgy=%%X
    )
    for /F "usebackq" %%L in (`%IMG7%magick ^
      %TMP_IN% ^
      -format "vTL=%%[fx:p{!imgx!,!imgy!}]\nvTR=%%[fx:p{w-1-!imgx!,!imgy!}]\nvBL=%%[fx:p{!imgx!,h-1-!imgy!}]\nvBR=%%[fx:p{w-1-!imgx!,h-1-!imgy!}]\n" ^
      info:`) do set %%L

    rem echo !D!  %%X,!y!  rev=%rev% vTL=!vTL! vTR=!vTR! vBL=!vBL! vBR=!vBR!

    if !fndTL!==0 if !vTL!==1 (
      set fndTL=1
      set fndTL.x=!imgx!
      set fndTL.y=!imgy!
    )
    if !fndTR!==0 if !vTR!==1 (
      set fndTR=1
      set fndTR.x=!imgx!
      set fndTR.y=!imgy!
    )
    if !fndBL!==0 if !vBL!==1 (
      set fndBL=1
      set fndBL.x=!imgx!
      set fndBL.y=!imgy!
    )
    if !fndBR!==0 if !vBR!==1 (
      set fndBR=1
      set fndBR.x=!imgx!
      set fndBR.y=!imgy!
    )

    set /A fndAll=!fndTL!*!fndTR!*!fndBL!*!fndBR!

    if !D! GTR 0 (
      set /A y+=%yi%
      set /A D-=2*%dx%
    )
    set /A D+=2*%dy%
  )
)

set Bad=0
if %fndTL%==0 (
  echo %0: TL not found
  set Bad=1
)
if %fndTR%==0 (
  echo %0: TR not found
  set Bad=1
)
if %fndBL%==0 (
  echo %0: BL not found
  set Bad=1
)
if %fndBR%==0 (
  echo %0: BR not found
  set Bad=1
)
if %Bad%==1 exit /B 1

set Left=%fndTL.x%
set Top=%fndTL.y%
set Right=%fndBR.x%
set Bottom=%fndBR.y%

if %Left% LSS %fndBL.x% set Left=%fndBL.x%
if %Top% LSS %fndTR.y% set Top=%fndTR.y%
if %Right% LSS %fndTR.x% set Right=%fndTR.x%
if %Bottom% LSS %fndBL.y% set Bottom=%fndBL.y%

echo LTRB = %Left% %Top% %Right% %Bottom%

rem We could extend the crop here.

if /I %Mode%==cumul (
  if %Left% LSS !%EvPref%.Left! set Left=!%EvPref%.Left!
  if %Top% LSS !%EvPref%.Top! set Top=!%EvPref%.Top!
  if %Right% LSS !%EvPref%.Right! set Right=!%EvPref%.Right!
  if %Bottom% LSS !%EvPref%.Bottom! set Bottom=!%EvPref%.Bottom!
)

set /A nW=%WW%-%Left%-%Right%
set /A nH=%HH%-%Top%-%Bottom%

if not "%ttDEBUG%"=="" %IMG7%magick ^
  %INFILE% ^
  -fill #0f04 -stroke None ^
  -draw "rectangle %Left%,%Top%,%%[fx:w-1-%Right%],%%[fx:h-1-%Bottom%] " ^
  -fill None -stroke #0f0 ^
  -draw "line %x0img%,%y0img%,%fndTL.x%,%fndTL.y%" ^
  -draw "line %%[fx:w-1-%x0img%],%y0img%,%%[fx:w-1-%fndTR.x%],%fndTR.y%" ^
  -draw "line %x0img%,%%[fx:h-1-%y0img%],%fndBL.x%,%%[fx:h-1-%fndBL.y%]" ^
  -draw "line %%[fx:w-1-%x0img%],%%[fx:h-1-%y0img%],%%[fx:w-1-%fndBR.x%],%%[fx:h-1-%fndBR.y%]" ^
  %ttDEBUG%

set sCrop=%nW%x%nH%+%Left%+%Top%

for /F "usebackq" %%L in (`%IMG7%magick ^
  %TMP_IN% ^
  -crop %sCrop% +repage ^
  -format "okay=%%[fx:minima==1?1:0]" ^
  info:`) do set %%L

if %nW% LSS 0 set okay=0
if %nH% LSS 0 set okay=0

if /I %Mode%==cumul if !%EvPref%.Okay!==0 set okay=0


call echoRestore

@endlocal & set %EvPref%.Left=%Left%& set %EvPref%.Top=%Top%& set %EvPref%.Right=%Right%& set %EvPref%.Bottom=%Bottom%& set /A %EvPref%.W=%nW%& set /A %EvPref%.H=%nH%& set %EvPref%.Crop=%sCrop%& set %EvPref%.Okay=%okay%

%IMG7%magick identify -version

Version: ImageMagick 7.0.7-28 Q16 x64 2018-03-25 http://www.imagemagick.org
Copyright: Copyright (C) 1999-2015 ImageMagick Studio LLC
License: http://www.imagemagick.org/script/license.php
Visual C++: 180040629
Features: Cipher DPC HDRI Modules OpenMP 
Delegates (built-in): bzlib cairo flif freetype gslib heic jng jp2 jpeg lcms lqr openexr pangocairo png ps raw rsvg tiff webp xml zlib

Page version v1.0 10-November-2018.

Page created 22-Nov-2018 12:55:36.

Copyright © 2018 Alan Gibson.