﻿

Trimming triangles

Remove virtual pixels added by some distortions.

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.

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%
)
)

if %fndTL%==0 (
)
if %fndTR%==0 (
)
if %fndBL%==0 (
)
if %fndBR%==0 (
)

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%```

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

`%IMG7%magick identify -version`
```Version: ImageMagick 7.0.7-28 Q16 x64 2018-03-25 http://www.imagemagick.org
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```

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

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

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.