snibgo's ImageMagick pages

Pruning skeleton stubs

Skeleton images often contain stubs: short segments at the ends or along their length. This method removes them.

• Sample input
• The method
• The script
• Simple segments
• Performance
• Remove non-segmenting lines
• Future
• Scripts

Skeletons are useful simplifications of thick lines. However, at the ends of the thick lines, or where they thicken or bend, the skeletal line will have short stubs. We may want to remove these for technical or aesthetic reasons.

Sample input

We use an image from the Canny edge detection page.

set SRC=ca_lab.png
Skeletonize the image, 8-connected. %IMG7%magick ^ %SRC% ^ -virtual-pixel Edge ^ -morphology Thinning:-1 Skeleton -clamp ^ pss_skel.png
From the 8-connected skeleton, we can make a 4-connected skeleton. %IMG7%magick ^ pss_skel.png ^ -morphology thicken "3>:-,0,-,1,-,1,0,1,0" ^ -morphology thicken "3>:-,0,0,1,-,0,0,1,-" ^ pss_skel_4.png This method adds some white pixels, and doesn't remove any.

The method

The method starts from a skeleton image with white lines on a black background, and an integer threshold parameter MAX_SIZE. The ouput has stubs smaller than or equal to MAX_SIZE removed, ie turned black.

1. Find the line ends and write them (as white pixels on black background) into image ENDS.
2. Remove junctions and write the remainder into image SEGS.
3. Dilate the ENDS, using SEGS as a mask ("conditional dilation"). Dilate with a 3x3 square, so the dilation moves diagonally as well as vertically and horizontally. Dilate enough times to ensure we get at least MAX_SIZE pixels, from the line-end. This gives us the image ENDSEGS, the image of segments that each have at least one line-end.
4. Using connected-components, create a text list of these end-segments, in the file SEGSLIST.
5. For each segment in SEGSLIST: If the area is larger than the MAX_SIZE, add the ID to an exclusion list.
6. Using connected-components again on ENDSEGS, this time with the exclusion list, create an image. The exclusion list has turned the background and long end-segments transparent, so flatten against black, and negate so we have black short end-segments on a white background.
7. Find the darker of these, and the input pixels.
8. Isolated points will be classed as segments, but do not have a line-end, so they are not classed as end-segments. Remove them using morphology HMT to turn black any isolated white pixels that are surrounded by black.

SEGSLIST will also contain one component for the black background. The above assumes it will contain more than MAX_SIZE pixels, so we don't need to worry about it.

Lines with no junctions have up to two ends, and are segments, so short lines with at least one end will be removed. Segments between junctions have no line-ends, so will not be removed however short they are.

Junctions themselves will not be removed. A junction can be a single pixel, or two adjacent pixels, or a cross of five white pixels. So a component that has only three or more short stubs, meeting at a junction, will have the stubs removed but the junction will remain.

A line that runs to an edge of the image doesn't have an end there. We can add a black border to give ends to those lines, and shave off the border after running the script.

To remove all stubs, irrespective of length, we can give a very large value for the script parameter MAX_SIZE. But this is also used for the number of iteration of a conditional dilation, so performance suffers. Instead, use "all" for MAX_SIZE. This creates a 4-connected skeleton, removes junctions to leave just segments, flood-fills from the line-ends to remove end-segments, takes a difference so we have only end-segmnts, and darkens the input with these.

Where a junction has two or more short stubs, we might want to remove just the shortest stub or all but the longest stub. This might be done by painting a gradient line along end-segments, from the ends. Around a junction, the lightest pixel is on the longest end-segment, and the darkest non-black pixel is in the shortest end-segment.

The script

The script pruneStubs.bat performs the above operations.

The script will not remove loops, however small they are. It isn't iterative: removing stubs will make junctions into line-ends, so segments that were originally between junctions become stubs, and these will not be removed.

It does return psNPruned, the number of stubs that it has pruned. psNPruned excludes the count of any 1x1 non-stubs that were removed.

Remove stubs that are no longer than 5 pixels. call %PICTBAT%pruneStubs ^ pss_skel.png pss_out1.png 5 if ERRORLEVEL 1 goto error echo psNPruned=%psNPruned% psNPruned=114 A blink comparison shows the removed lines %IMG7%magick ^ -delay 50 ^ pss_skel.png ^ pss_out1.png ^ pss_out1.gif
Remove stubs that are no longer than 50 pixels. call %PICTBAT%pruneStubs ^ pss_skel.png pss_out2.png 50 if ERRORLEVEL 1 goto error echo psNPruned=%psNPruned% psNPruned=291 A blink comparison shows the removed lines %IMG7%magick ^ -delay 50 ^ pss_skel.png ^ pss_out2.png ^ pss_out2.gif
Remove all stubs, whatever the length. call %PICTBAT%pruneStubs ^ pss_skel.png pss_out3.png all if ERRORLEVEL 1 goto error echo psNPruned=%psNPruned% psNPruned=361 A blink comparison shows the removed lines %IMG7%magick ^ -delay 50 ^ pss_skel.png ^ pss_out3.png ^ pss_out3.gif

The script pruneStubsRep.bat repeatedly calls pruneStubs.bat until psNPruned is zero. The result has only lines with no ends, which are loops, and segments between loops or an image edge.

Repeatedly remove all stubs, whatever the length. call %PICTBAT%pruneStubsRep ^ pss_skel.png pss_out3r.png all if ERRORLEVEL 1 goto error echo psrTotPruned=%psrTotPruned% psrTotPruned=942 A blink comparison shows the removed lines %IMG7%magick ^ -delay 50 ^ pss_skel.png ^ pss_out3r.png ^ pss_out3r.gif

Simple segments

Where a line has at least one end but no junctions, pruneStubs.bat regards it as a stub so will remove it (if it is short enough). But we might not want those junction-less lines to be removed.

Instead of making pruneStubs.bat even more complex, we provide a script nonJcnLines.bat which turns black all components with junctions, so leaving only the simple segments with no junctions. It works like this:

1. Make a 4-connected skeleton and write a list of junction coordinates.
2. Flood the 4-connected skeleton from those coordinates. This leaves only the simple segments of the 4-connected skeleton.
3. For the output, take the darker of the input and the result of step (2).

The flood-fill is slow. Thinning reduces the number of flood-fills.

call %PICTBAT%nonJcnLines ^ pss_skel.png pss_simpseg.png

We can use this to paint the simple segments back into any result.

%IMG7%magick ^ pss_out3.png ^ pss_simpseg.png ^ -compose Lighten -composite ^ pss_out4.png

Performance

Morphology can be unacceptably slow for large images, eg 7000x5000 pixels. We are often concerned with only a small part of the image. The scripts pruneStubs.bat and nonJcnLines.bat retain canvas metadata, so an image can be trimmed before calling the script, and restored afterwards. We will generally need to add a border of the background colour, and shave that off afterwards. (Lines that extend to an image edge don't have line-ends there.)

Make a sample. %IMG7%magick ^ -size 300x200 xc:Black ^ -stroke White ^ -draw "line 50,100 250,100" ^ -draw "line 70,90 70,110" ^ -draw "line 245,100 295,190" ^ -morphology Thinning:-1 Skeleton -clamp ^ pss_pf_src.png
Prune stubs from the sample. call %PICTBAT%pruneStubs ^ pss_pf_src.png pss_pf_out1.png 5
Trim the sample. %IMG7%magick ^ pss_pf_src.png ^ -trim ^ -bordercolor Black -border 1 ^ pss_pf_trm.png
Prune the trimmed version, and flatten to get the original size. call %PICTBAT%pruneStubs ^ pss_pf_trm.png pss_pf_out2.png 5 %IMG7%magick ^ pss_pf_out2.png ^ -shave 1 ^ -background Black ^ -layers Flatten ^ pss_pf_out2.png

Remove non-segmenting lines

We might want to remove lines that do not segment the image.

%IMG7%magick ^ %SRC% -negate ^ ( +clone ^ -connected-components 4 -auto-level ^ ) ^ +swap -alpha off ^ -compose CopyOpacity -composite ^ pss_seg0.png call %PICTBAT%shiftFill ^ pss_seg0.png . pss_seg1.png %IMG7%magick ^ pss_seg1.png ^ -statistic StandardDeviation 2x2 ^ -alpha off -threshold 0 ^ pss_segs_only.png

Another example of this technique is shown at Partition boundary masks.

Future

Blah.

Scripts

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

pruneStubs.bat

rem From %1, image of skeletonized white lines on black background, fully opaque,
rem makes output %2 version with short stubs removed.
rem %3 threshold for stub removal, integer number of pixels, or "all".
rem   Stubs larger than this will not be removed.
@rem
@rem Updated:
@rem   15-Feb-2017 added limit so exclusion string doesn't break line length limit.
@rem   6-August-2022 for IM v7
@rem


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

@setlocal enabledelayedexpansion

@call echoOffSave

call %PICTBAT%setInOut %1 ps

echo %0: %1 %2 %3

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

set MAX_SIZE=%3
if "%MAX_SIZE%"=="." set MAX_SIZE=
if "%MAX_SIZE%"=="" set MAX_SIZE=10

set DO_ALL=0
if /I "%MAX_SIZE%" EQU "all" set DO_ALL=1

set EXT=.miff
set ENDS=%BASENAME%_ends_ps%EXT%
set SEGS=%BASENAME%_segs_ps%EXT%
set ENDSEGS=%BASENAME%_endsegs_ps%EXT%
set SEGSLIST=%BASENAME%_graysegs_ps.lis
set ENDSLIST=%BASENAME%_ends_ps.lis
set FLOODLIST=%BASENAME%_flood_ps.lis

for /F "usebackq" %%L in (`%IMG7%magick ^
  xc: -format "QNUM=%%q" info:`) do set %%L

for /F "usebackq" %%L in (`%IMG7%magick identify ^
  -format "CANVAS=%%P%%O" %INFILE%`) do set %%L

%IMG7%magick ^
  %INFILE% ^
-fill White +opaque Black ^
  +repage ^
  ( -clone 0 ^
    -morphology HMT LineEnds ^
    -alpha off ^
    +write %ENDS% ^
    +delete ^
  ) ^
  -define morphology:compose=Darken ^
  -morphology Thinning "LineJunctions;LineJunctions:3>;LineJunctions:5" -clamp ^
  -alpha off ^
  %SEGS%

if ERRORLEVEL 1 exit /B 1

set /A N_DILATE=2*%MAX_SIZE%

set nPruned=0

if %DO_ALL%==1 (

  (
    for /F "usebackq tokens=1-2 delims=, " %%X in (`%IMG7%magick ^
      %ENDS% ^
      -transparent Black ^
      sparse-color:- ^| sed -e 's/ /\n/g' `) do @(
      @echo color %%X,%%Y floodfill
      @set /A nPruned+=1
    )
  ) >%FLOODLIST%

  type %FLOODLIST%

rem       -morphology thicken "3>:-,0,-,1,-,1,0,1,0" 
rem       -morphology thicken "3>:-,0,0,1,-,0,0,1,-" 

  %IMG7%magick ^
    %INFILE% ^
    -alpha off ^
    ^( +clone ^
       -define "morphology:compose=Darken" ^
       -morphology Thinning "LineJunctions;LineJunctions:3>;LineJunctions:5" -clamp ^
      -alpha off ^
       ^( +clone ^
          -fill Black -draw @%FLOODLIST% ^
       ^) ^
       -compose Difference -composite ^
       -alpha off ^
       -negate ^
    ^) ^
    -compose Darken -composite ^
    ^( +clone ^
       -morphology Hit-and-Miss "3x3:0,0,0,0,1,0,0,0,0" ^
       -alpha off ^
       -negate ^
    ^) ^
    -compose Darken -composite ^
    -compose Over ^
    -alpha off ^
    %OUTFILE%

  goto end
)

%IMG7%magick ^
  %SEGS% -negate +write mpr:MASK +delete ^
  %ENDS% ^
  -write-mask mpr:MASK ^
  -morphology Dilate:%N_DILATE% Square ^
  +write-mask ^
  -alpha off ^
  +write %ENDSEGS% ^
  -define "connected-components:verbose=true" ^
  -connected-components 8 ^
  NULL: >%SEGSLIST%

if ERRORLEVEL 1 exit /B 1

:: Building the string: 1000 is okay; 2200 breaks line length.

set HAS_ANY=0
set CH_COLS=
set CH_EXCL=
set nFnd=0
set nExcl=0
for /F "skip=1 tokens=1-5 delims=: " %%A in (%SEGSLIST%) do (
  set HAS_ANY=1
  set /A nFnd+=1

  set ID=%%A
  set BND_BOX=%%B
  set CENTROID=%%C
  set AREA=%%D
  set COL=%%E

  if !AREA! GTR %MAX_SIZE% if !nExcl! LSS 1000 (
    set CH_EXCL=!CH_EXCL!,!ID!
    set /A nExcl+=1
  )
)

echo %0: SEGSLIST=%SEGSLIST% nFnd=%nFnd% nExcl=%nExcl%

if %HAS_ANY%==0 (
  echo %0: ** No components?? **
  exit /B 1
)

:: remove leading comma
set CH_EXCL=%CH_EXCL:~1%
rem echo CH_EXCL=%CH_EXCL%

:: FIXME? not necessarily an error.
if "%CH_EXCL%"=="" exit /B 1

%IMG7%magick ^
  %ENDSEGS% ^
  -define "connected-components:remove=%CH_EXCL%" ^
  -define "connected-components:mean-color=true" ^
  -connected-components 8 ^
  -background Black -layers Flatten ^
  -fill White +opaque Black ^
  -alpha off ^
  -negate ^
  %INFILE% ^
  +repage ^
  -compose Darken -composite ^
  ( +clone ^
    -morphology Hit-and-Miss "3x3:0,0,0,0,1,0,0,0,0" ^
    -alpha off ^
    -negate ^
  ) ^
  -compose Darken -composite ^
  -compose Over ^
  -repage %CANVAS% ^
  -alpha off ^
  %OUTFILE%

if ERRORLEVEL 1 exit /B 1

set /A nPruned=%nFnd%-%nExcl%


:end

echo %0 end: outfile=%OUTFILE%

call echoRestore

endlocal & set psOUTFILE=%OUTFILE%& set psNPruned=%nPruned%

pruneStubsRep.bat

rem Repeatedly calls pruneStubs until nPruned is zero.
@rem
@rem Updated:
@rem   6-August-2022 for IM v7
@rem

set TMP_IMG=psr_tmp.miff

%IMG7%magick %1 %TMP_IMG%
if ERRORLEVEL 1 exit /B 1

set psrTotPruned=0

:loop

call %PICTBAT%pruneStubs %TMP_IMG% %TMP_IMG% %3

set /A psrTotPruned+=%psNPruned%

if %psNPruned% GTR 0 goto loop

%IMG7%magick %TMP_IMG% %2
if ERRORLEVEL 1 exit /B 1

nonJcnLines.bat

rem Given %1 is image with white lines on black blackground,
rem creates output %2 with just the lines that have no junctions.
@rem
@rem Updated:
@rem   24-August-2022 for IM v7.
@rem

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

@setlocal enabledelayedexpansion

@call echoOffSave

call %PICTBAT%setInOut %1 njl

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

set EXT=.miff
set SKEL4=%BASENAME%_skel4_njl%EXT%
set FLOODLIST=%BASENAME%_flood_njl.lis
set FLOODSCR=%BASENAME%_flood_njl.bat

(
  for /F "usebackq tokens=1-2 delims=, " %%X in (`%IMG7%magick ^
    %INFILE% ^
    -morphology thicken "3>:-,0,-,1,-,1,0,1,0" -clamp ^
    -morphology thicken "3>:-,0,0,1,-,0,0,1,-" -clamp ^
    +write %SKEL4% ^
    ^( +clone ^
       -define "morphology:compose=Darken" ^
       -morphology Thinning "LineJunctions;LineJunctions:3>;LineJunctions:5" -clamp ^
    ^) ^
    -compose Difference -composite ^
    -morphology Thinning "Rectangle:2x1;Rectangle:1x2" -clamp ^
    -transparent Black ^
    sparse-color:- ^| sed -e 's/ /\n/g' `) do @(
    @echo color %%X,%%Y floodfill
  )
) >%FLOODLIST%

rem type %FLOODLIST%

%IMG7%magick ^
  %INFILE% ^
  ( %SKEL4% ^
    -fill Black -draw @%FLOODLIST% ^
  ) ^
  -compose Darken -composite ^
  %OUTFILE%

rem cPrefix /i%FLOODSCR% /r" ^"
rem echo ^) -compose Darken -composite %OUTFILE% >>%FLOODSCR%
rem
rem type %FLOODSCR%
rem call %FLOODSCR%

call echoRestore

@endlocal & set njlOUTFILE=%OUTFILE%

%IMG7%magick -version

Version: ImageMagick 7.1.0-47 Q16-HDRI x64 15861e0:20220827 https://imagemagick.org
Copyright: (C) 1999 ImageMagick Studio LLC
License: https://imagemagick.org/script/license.php
Features: Cipher DPC HDRI OpenCL 
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 (193331629)

Page version v1.0 22-June-2016.

Page created 24-Sep-2022 02:56:24.

Copyright © 2022 Alan Gibson.