﻿﻿

# Tiling with dark paths

An image can be cut by dark paths to make a ragged-edge piece that will tile with itself, in both shape and colour.

This technique is closely related to the simpler Rectangle boundaries with dark paths.

## The method

Given a rectangular image, we can cut out a shape that can be attached to copies of itself like pieces of a jigsaw puzzle. We want the shape and colour to match at the boundary between two tiles. (Other shapes can be used, eg triangles and hexagons. They are not considered here.)

Many algorithms are available for doing this. One algorithm is:

1. Pick four points on the image that form the corners of a rectangle. So two points will be on one row, and two points will be on a different row, exactly below the two upper points.
2. Draw a squiggly line, roughly vertical, that passes exactly between the two left-hand points.
3. Draw an identical line between the two right-hand points.
4. Draw another squiggly line, roughly horizontal, that passes exactly between the two points at the top.
5. Draw an identical line between the two points on the bottom.

The intersecting lines form a rough rectangle in the centre, where the top and bottom edges will align with each other, and so will the left and right sides. The corners would form an exact rectangle, but the sides are not straight. When tiled together, the shapes will match, but the image colours probably won't.

We want a tile that has not only matching shape top/bottom and left/right, but also matching colours. Again there are a number of ways to choose the four points and the squiggly lines that join them so that the colours roughly match. One algorithm is:

1. Chop the image in half vertically.
2. Placing the left half over the right half, find the column with the least difference. This gives us the x-coordinate of the two left-hand points, and also the two right-hand points, being the same x plus half the image width.
3. Similarly, chop the image in half horizontally.
4. Placing the top half over the bottom half, find the row with the least difference. This gives us the y-coordinates.

Now we need the lines between the four corners.

1. From the difference between the left and right sides, find the darkest path that passes exactly through the two points, which are at the same x-ordinate. This defines the left and right edges of the tile.
2. Similarly, the darkest path (roughly horizontal) of the difference between the top and bottom images that passes through the two points at the same y-ordinate gives us the top and bottom tile edges.

Every row of the tile will be exactly half the width of the image, and every column of the tile will be exactly half the height of the image, which is a pleasing property.

Enough discussion. We will make a tile from this grayscale image:

 `set SRC=dp_src2.png` Start by finding the four corners.

Find the difference between the left and right halves.

 ```:skip %IM%convert ^ %SRC% ^ -crop 2x1@ +repage ^ -compose Difference -composite ^ dpt_src2_lr.png ``` Which column is darkest? ```for /F "usebackq delims=, " %%X in (`%IMDEV%convert ^ dpt_src2_lr.png ^ -scale "x1^!" ^ -negate ^ -process onelightest ^ NULL: 2^>^&1`) do set TIL_X=%%X echo TIL_X=%TIL_X% ``` `TIL_X=97 ` [No image]

We similarly find Y:

```for /F "usebackq tokens=2 delims=, " %%Y in (`%IMDEV%convert ^
%SRC% ^
-crop 1x2@ +repage ^
-compose Difference -composite ^
+write dpt_src2_tb.png ^
-scale "1x^!" ^
-negate ^
-process onelightest ^
NULL: 2^>^&1`) do set TIL_Y=%%Y

echo TIL_Y=%TIL_Y% ```
`TIL_Y=40 `

Now we know the x-y coordinates of the top-left corner of the tile. We readily calculate the coordinates of the other corners by adding half the width and height.

```set X0=%TIL_X%
set Y0=%TIL_Y%

for /F "usebackq" %%L in (`%IM%identify ^
-ping ^
-format "WW=%%w\nHH=%%h\nX1=%%[fx:int(%X0%+w/2+0.5)]\nY1=%%[fx:int(%Y0%+h/2+0.5)]" ^
%SRC%`) do set %%L

echo WW=%WW% HH=%HH% X0=%X0% Y0=%Y0% X1=%X1% Y1=%Y1% ```
`WW=300 HH=200 X0=97 Y0=40 X1=247 Y1=140 `

Just for fun, we show these on the image:

 ```%IM%convert ^ %SRC% ^ -stroke Yellow -fill None ^ -draw "translate %X0%,%Y0% circle 0,0 0,10" ^ -draw "translate %X0%,%Y1% circle 0,0 0,10" ^ -draw "translate %X1%,%Y0% circle 0,0 0,10" ^ -draw "translate %X1%,%Y1% circle 0,0 0,10" ^ dpt_src2_4cn.png``` Now we want the darkest paths that pass through these points, both vertically and horizontally. We do this with super-white gates on the difference images. A file format that can record HDRI must be used.

 Put a super-white gate at the two vertical positions. ```call %PICTBAT%supWhGate ^ dpt_src2_lr.png %X0% %Y0% dpt_src2_lr_swg.miff call %PICTBAT%supWhGate ^ dpt_src2_lr_swg.miff %X0% %Y1% dpt_src2_lr_swg.miff``` [No image] Find the darkest path that passes through the gates. ```%IMDEV%convert ^ dpt_src2_lr_swg.miff ^ -process 'darkestpath' ^ +write dpt_src2_lr_swg_ln.png ^ -stroke Yellow -fill None ^ -draw "translate %X0%,%Y0% circle 0,0 0,10" ^ -draw "translate %X0%,%Y1% circle 0,0 0,10" ^ dpt_src2_lr_swg_mp.png```  I use darkestpath. Wouldn't darkestmeander give a closer colour match? Yes it would, because darkestmeander can create paths at more than 45° from the intended direction or even do a U-turn if that creates a darker overall path. But this is also a problem as the vertical and horizontal paths could then cross at more than one point, which would make the tiles overlap each other. With darkestpath, this can not happen.

Now we have the left and right edges of the tile. To find the top and bottom edges, we need to rotate the difference image and adjust the XY values accordingly.

Rotate, and calculate X and Y.

 ```%IMDEV%convert ^ %SRC% ^ -crop 1x2@ +repage ^ -compose Difference -composite ^ -rotate -90 ^ dpt_src2_tb.png set X0R=%Y0% set /A Y0R=%WW%-%X1%-1 set /A Y1R=%WW%-%X0%-1 echo X0R=%X0R% Y0R=%Y0R% Y1R=%Y1R% ``` `X0R=40 Y0R=52 Y1R=202 ` Put a super-white gate at the two (rotated) horizontal positions. ```call %PICTBAT%supWhGate ^ dpt_src2_tb.png ^ %X0R% %Y0R% ^ dpt_src2_tb_swg.miff call %PICTBAT%supWhGate ^ dpt_src2_tb_swg.miff ^ %X0R% %Y1R% ^ dpt_src2_tb_swg.miff``` [No image] Find the darkest path that passes through the gates. ```%IMDEV%convert ^ dpt_src2_tb_swg.miff ^ -process 'darkestpath' ^ +write dpt_src2_tb_swg_ln.png ^ -stroke Yellow -fill None ^ -draw "translate %X0R%,%Y0R% circle 0,0 0,10" ^ -draw "translate %X0R%,%Y1R% circle 0,0 0,10" ^ -rotate 90 ^ dpt_src2_tb_swg_mp.png```  A visual check:

 ```%IM%convert ^ ( dpt_src2_lr_swg_mp.png ( +clone ) +append +repage ) ^ ( dpt_src2_tb_swg_mp.png ( +clone ) -append +repage ) ^ -compose Lighten -composite ^ -fill #f80 -opaque White ^ -transparent Black ^ %SRC% ^ -compose DstOver -composite ^ dpt_chk_swg_mp.png``` From the two line images _swg_ln.png, we make a mask. We use morphology to slightly extend the mask top and left edges, with a fade. This reduces the sharp boundary we would get where tiled images don't match colours exactly.

The following assumes we can turn all pixels to the left of the white line by flood-filling from 0,0. In real life we can't assume this, and should turn flood-fill from all black pixels in column 0, or do the equivalent with morphology. The script uses morphology.

 ```set DIST_KNL=Euclidean:7 set PIX_OUT=2 %IM%convert ^ -fill White ^ ( dpt_src2_lr_swg_ln.png ^ -draw "color 0,0 floodfill" ^ ( +clone ^ -morphology Distance "%DIST_KNL%,%PIX_OUT%^!" ^ -negate ^ ) ^ +swap +append +repage ^ ) ^ ( dpt_src2_tb_swg_ln.png ^ -rotate 90 ^ -draw "color 0,0 floodfill" ^ ( +clone ^ -morphology Distance "%DIST_KNL%,%PIX_OUT%^!" ^ -negate ^ ) ^ +swap -append +repage ^ ) ^ -compose Multiply -composite ^ dpt_src2_mask.png``` Show the source, masked. This is a single tile. ```%IMDEV%convert ^ -fill None ^ %SRC% ^ dpt_src2_mask.png ^ -alpha off ^ -compose CopyOpacity -composite ^ dpt_src2_mskd.png``` Show more tiles: ``` %IM%convert ^ dpt_src2_mskd.png ^ -background None ^ -duplicate 3 ^ -set page +%%[fx:t*w/2]+0 ^ -layers merge ^ -duplicate 2 ^ -set page +0+%%[fx:t*h/2] ^ -layers merge ^ +repage ^ dpt_src2_dup.png``` The left-right boundary is very good. The top-bottom boundary isn't quite as good.

## The script

The script tileDp.bat implements the above. From an image, it creates a tile that is half the width and height.

For convenience, we set up an environment variable with the IM commands to assemble four tiles.

```set TILE_IT=^
-background None ^
-duplicate 1 ^
-set page +%%[fx:t*w/2]+0 ^
-layers merge ^
-duplicate 1 ^
-set page +0+%%[fx:t*h/2] ^
-background White ^
-layers merge ^
+repage```
 ```call %PICTBAT%tileDp %SRC% dpt_scr1.png %IM%convert ^ dpt_scr1.png ^ %TILE_IT% ^ dpt_scr1_dup.png```  The script returns some environment variables:

`set tdp `
```tdpOUTFILE=dpt_scr1.png
tdpX0=97
tdpX1=247
tdpY0=40
tdpY1=140```

## Examples

 ```call %PICTBAT%tileDp ^ toes.png dpt_toes_ex.png %IM%convert ^ dpt_toes_ex.png ^ %TILE_IT% ^ dpt_toes_ex_dup.png``` Left-right is poor because no column in the left half is close to matching a column in the right half.   Debug mode creates some extra images. ```set tdpDEBUG=1 set tdpPREF=dpt_dbg_ call %PICTBAT%tileDp ^ toes.png dpt_toes_dbg.png set tdpPREF= set tdpDEBUG=```          Don't tile horizontally; do tile vertically. ```call %PICTBAT%tileDp ^ toes.png dpt_toes_v.png 0 1 %IM%convert ^ dpt_toes_v.png ^ -duplicate 1 ^ -set page +0+%%[fx:t*h/2] ^ -background White ^ -layers merge ^ dpt_toes_v_dup.png```  Do tile horizontally; don't tile vertically. ```call %PICTBAT%tileDp ^ toes.png dpt_toes_h.png 1 0 %IM%convert ^ dpt_toes_h.png ^ -duplicate 1 ^ -set page +%%[fx:t*w/2]+0 ^ -background White ^ -layers merge ^ dpt_toes_h_dup.png```  The next example works on a photo about 7000x5000 pixels. The results are resized for the web.

 The full-size image, reduced for the web. ```set WEB_SIZE=-resize 600x400 set SRC_LVS=%PICTLIB%20151026\AGA_2680_sRGB.tiff %IM%convert ^ %SRC_LVS% ^ %WEB_SIZE% ^ dpt_lvs_sm.jpg``` Make the tile. ```set tdpFTH_SIZ= call %PICTBAT%tileDp %SRC_LVS% dpt_lvs_tile.tiff set tdpFTH_SIZ= %IM%convert ^ dpt_lvs_tile.tiff ^ -trim +repage ^ %WEB_SIZE% ^ dpt_lvs_tile_sm.jpg``` Assemble four tiles. ```%IM%convert ^ dpt_lvs_tile.tiff ^ %TILE_IT% ^ +write dpt_lvs_tiled4.tiff ^ -trim +repage ^ %WEB_SIZE% ^ dpt_lvs_tiled4_sm.jpg``` Show the centre of the full-size image at 1:1, at the intersection of four tiles. ```set /A DX=%tdpX1%-300 set /A DY=%tdpY1%-200 echo tdpX1=%tdpX1% tdpY1=%tdpY1% DX=%DX% DY=%DY% %IM%convert ^ dpt_lvs_tiled4.tiff ^ -crop 600x400+%DX%+%DY% +repage ^ dpt_lvs_1_1.jpg``` `tdpX1=6916 tdpY1=3183 DX=6616 DY=2983 ` The joins are not easy to identify. • The technique works well with photos containing detail across a large range of frequencies, such as natural textures.
• If the left half is very different to the right half, the column of least difference will have a large difference, and the tiling won't match well.
• Similarly top and bottom.
• The algorithm looks for the lowest (darkest) difference between images. It doesn't deliberately look for shadows in the images themselves, but for ordinary photographs this is often where the lowest differences occur.
• We could encourage the use of shadows by converting one image to a monochrome (say, black to red) and the other image to a different monochrome (say, black to blue).

## Future

The cut lines may not be optimal. For example, we found the least-error column when the left and right sides aligned, but perhaps a smaller least-error column could be found if one image was shifted right or left. This would result in a tile that wasn't exactly half the width of the input image but would have a better colour match when the edges were joined.

Another sub-optimal issue is that we find the least-error column by finding the mean of the columns in their entirety, when we are only really interested in the columns of pixels between the horizontal cuts. Similarly, we are only interested in the least-error of the pixel rows between the vertical cuts. We could find the four points, re-calculate the least-error columns only between the upper and lower points and similarly for the rows. This gives four new points, and we iterate.

Can we make a pyramid, make a tile from each grid, and collapse that? The new pyramid would have transparency.

## Scripts

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

### tileDp.bat

```rem From image %1, make tile half width and height by darkest path method.
rem Output is same width and height as input, but only 1/4 of the pixels are opaque.
rem %2 is optional output file.
@rem
@rem %3 whether to make cuts to tile horizontally  (vertical cuts)
@rem %4 whether to make cuts to tile vertically  (horizontal cuts)
@rem
@rem Also uses:
@rem
@rem   tdpFTH_SIZ feathering size for top and left. 0=no feathering 
@rem   tdpPREF prefix for working files (not output file).
@rem   tdpDEBUG if 1, also creates debugging images.

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

@setlocal

@call echoOffSave

call %PICTBAT%setInOut %1 tdp

if not "%2"=="" set OUTFILE=%2

set DO_H=%3
if "%DO_H%"=="." set DO_H=
if "%DO_H%"=="" set DO_H=1

set DO_V=%4
if "%DO_V%"=="." set DO_V=
if "%DO_V%"=="" set DO_V=1

set DO_BOTH=0
if %DO_H%==1 if %DO_V%==1 set DO_BOTH=1

if "%tdpFTH_SIZ%"=="" set tdpFTH_SIZ=2

echo DO_H=%DO_H% DO_V=%DO_V% DO_BOTH=%DO_BOTH%

if "%tdpPREF%"=="" set tdpPREF=tdp_
set EXT=.miff

set X0=0
set Y0=0

if %DO_H%==1 (
echo %0: find TIL_X
for /F "usebackq delims=, " %%X in (`%IMDEV%convert ^
%INFILE% ^
^( -clone 0 ^
-colorspace Gray ^
-crop 2x1@ +repage ^
-compose Difference -composite ^
+write %tdpPREF%lr%EXT% ^
-scale "x1^!" ^
-negate ^
-process onelightest ^
+delete ^
^) ^
NULL: 2^>^&1`) do set TIL_X=%%X
)

if %DO_V%==1 (
echo %0: find TIL_Y
for /F "usebackq tokens=1 delims=, " %%Y in (`%IMDEV%convert ^
%INFILE% ^
^( -clone 0 ^
-colorspace Gray ^
-crop 1x2@ +repage ^
-compose Difference -composite ^
-rotate -90 ^
+write %tdpPREF%tb%EXT% ^
-scale "x1^!" ^
-negate ^
-process onelightest ^
+delete ^
^) ^
NULL: 2^>^&1`) do set TIL_Y=%%Y
)

set X0=%TIL_X%
set Y0=%TIL_Y%

for /F "usebackq" %%L in (`%IM%identify ^
-ping ^
-format "WW=%%w\nHH=%%h\nX1=%%[fx:int(%X0%+w/2+0.5)]\nY1=%%[fx:int(%Y0%+h/2+0.5)]" ^
%INFILE%`) do set %%L

echo WW=%WW% HH=%HH% X0=%X0% Y0=%Y0% X1=%X1% Y1=%Y1%

if %DO_H%==1 (
echo %0: find vertical path
rem call %PICTBAT%supWhGate ^
rem   %tdpPREF%lr%EXT% %X0% %Y0% %tdpPREF%lr_swg.miff
rem
rem call %PICTBAT%supWhGate ^
rem   %tdpPREF%lr_swg.miff %X0% %Y1% %tdpPREF%lr_swg.miff

call :WhGates %tdpPREF%lr%EXT% !X0! !Y0! !Y1! %tdpPREF%lr_swg.miff

if "%tdpDEBUG%"=="1" (
set sWR_LR_MP=-stroke Yellow -fill None ^
-draw "translate %X0%,%Y0% circle 0,0 0,10" ^
-draw "translate %X0%,%Y1% circle 0,0 0,10" ^
%tdpPREF%lr_swg_mp%EXT%

) else (
set sWR_LR_MP=NULL:
)

%IMDEV%convert ^
%tdpPREF%lr_swg.miff ^
-process 'darkestpath' ^
+write %tdpPREF%lr_swg_ln%EXT% ^
!sWR_LR_MP!
)

if %DO_V%==1 (
echo %0: find horizontal path
set X0R=%Y0%
set /A Y0R=%WW%-%X1%-1
set /A Y1R=%WW%-%X0%-1

echo X0R=!X0R! Y0R=!Y0R! Y1R=!Y1R!

rem call %PICTBAT%supWhGate ^
rem   %tdpPREF%tb%EXT% ^
rem   !X0R! !Y0R! ^
rem   %tdpPREF%tb_swg.miff
rem
rem call %PICTBAT%supWhGate ^
rem   %tdpPREF%tb_swg.miff ^
rem   !X0R! !Y1R! ^
rem   %tdpPREF%tb_swg.miff

call :WhGates %tdpPREF%tb%EXT% !X0R! !Y0R! !Y1R! %tdpPREF%tb_swg.miff

if "%tdpDEBUG%"=="1" (
set sWR_TB_MP=-stroke Yellow -fill None ^
-draw "translate !X0R!,!Y0R! circle 0,0 0,10" ^
-draw "translate !X0R!,!Y1R! circle 0,0 0,10" ^
%tdpPREF%tb_swg_mp%EXT%
) else (
set sWR_TB_MP=NULL:
)

%IMDEV%convert ^
%tdpPREF%tb_swg.miff ^
-process 'darkestpath' ^
+write %tdpPREF%tb_swg_ln%EXT% ^
!sWR_TB_MP!
)

rem Check:
echo %0: check
if %DO_BOTH%==1 if "%tdpDEBUG%"=="1" %IM%convert ^
( %tdpPREF%lr_swg_mp%EXT% ( +clone ) +append +repage ) ^
( %tdpPREF%tb_swg_mp%EXT% ( +clone ) +append +repage -rotate 90 ) ^
-compose Lighten -composite ^
-fill #f80 -opaque White ^
-transparent Black ^
%INFILE% ^
-compose DstOver -composite ^
%tdpPREF%chk_swg_mp%EXT%

set DIST_KNL=Euclidean:7

if "%tdpFTH_SIZ%"=="0" (
set sFEATH=
) else (
set sFEATH=-morphology Distance "%DIST_KNL%,%tdpFTH_SIZ%^^^!"
)

echo tdpFTH_SIZ=%tdpFTH_SIZ% sFEATH=%sFEATH%

if %DO_BOTH%==1 (
%IM%convert ^
-fill White ^
^( %tdpPREF%lr_swg_ln%EXT% ^
-morphology dilate:-1 2x1+1+0:1,1 ^
^( +clone ^
%sFEATH% ^
-negate ^
^) ^
+swap +append +repage ^
^) ^
^( %tdpPREF%tb_swg_ln%EXT% ^
-morphology dilate:-1 2x1+1+0:1,1 ^
-rotate 90 ^
^( +clone ^
%sFEATH% ^
-negate ^
^) ^
+swap -append +repage ^
^) ^
-compose Multiply -composite ^
if ERRORLEVEL 1 exit /B 1

) else if %DO_H%==1 (
%IM%convert ^
-fill White ^
^( %tdpPREF%lr_swg_ln%EXT% ^
-morphology dilate:-1 2x1+1+0:1,1 ^
^( +clone ^
%sFEATH% ^
-negate ^
^) ^
+swap +append +repage ^
^) ^
if ERRORLEVEL 1 exit /B 1

) else if %DO_V%==1 (
%IM%convert ^
-fill White ^
^( %tdpPREF%tb_swg_ln%EXT% ^
-morphology dilate:-1 2x1+1+0:1,1 ^
-rotate 90 ^
^( +clone ^
%sFEATH% ^
-negate ^
^) ^
+swap -append +repage ^
^) ^
if ERRORLEVEL 1 exit /B 1
)

echo %0: make tile
%IMDEV%convert ^
-fill None ^
%INFILE% ^
-alpha off ^
-compose CopyOpacity -composite ^
%OUTFILE%

call echoRestore

endlocal & set tdpOUTFILE=%OUTFILE%& set tdpX0=%X0%& set tdpY0=%Y0%& set tdpX1=%X1%& set tdpY1=%Y1%

exit /B 0

:: ------------- Subroutines -------------

:: %1 input image
:: %2 X
:: %3 Y0
:: %4 Y1
:: %5 output file
:: Assumes WW

:WhGates

for /F "usebackq" %%L in (`%IM%identify ^
-format "Wm1=%%[fx:%WW%-1]\nXm1=%%[fx:%2-1]\nXp1=%%[fx:%2+1]\nHasL=%%[fx:%2>0?1:0]\nHasR=%%[fx:%2<%WW%-1?1:0]" ^
%INFILE%`) do set %%L

if !HasL!==0 (
set DrawL1=
set DrawL2=
) else (
set DrawL1=-draw "line 0,%3 !Xm1!,%3"
set DrawL2=-draw "line 0,%4 !Xm1!,%4"
)

if !HasR!==0 (
set DrawR1=
set DrawR2=
) else (
set DrawR1=-draw "line !Xp1!,%3 !Wm1!,%3"
set DrawR2=-draw "line !Xp1!,%4 !Wm1!,%4"
)

%IMDEV%convert ^
%1 ^
-stroke rgb(100000%%,100000%%,100000%%) ^
!DrawL1! ^
!DrawR1! ^
!DrawL2! ^
!DrawR2! ^
-define quantum:format=floating-point ^
%5

exit /B 0```

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

`%IM%identify -version`
```Version: ImageMagick 6.9.9-50 Q16 x64 2018-06-02 http://www.imagemagick.org
Visual C++: 180040629
Features: Cipher DPC Modules OpenMP
Delegates (built-in): bzlib cairo flif freetype gslib heic jng jp2 jpeg lcms lqr lzma openexr pangocairo png ps raw rsvg tiff webp xml zlib```

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

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.