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.

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
ca_lab.png

Skeletonize the image, 8-connected.

%IM%convert ^
  %SRC% ^
  -virtual-pixel Edge ^
  -morphology Thinning:-1 Skeleton ^
  pss_skel.png
pss_skel.png

From the 8-connected skeleton, we can make a 4-connected skeleton.

%IM%convert ^
  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.

pss_skel_4.png

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=78 

A blink comparison shows the removed lines

%IM%convert ^
  -delay 50 ^
  pss_skel.png ^
  pss_out1.png ^
  pss_out1.gif
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=191 

A blink comparison shows the removed lines

%IM%convert ^
  -delay 50 ^
  pss_skel.png ^
  pss_out2.png ^
  pss_out2.gif
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=275 

A blink comparison shows the removed lines

%IM%convert ^
  -delay 50 ^
  pss_skel.png ^
  pss_out3.png ^
  pss_out3.gif
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=354 

A blink comparison shows the removed lines

%IM%convert ^
  -delay 50 ^
  pss_skel.png ^
  pss_out3r.png ^
  pss_out3r.gif
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
pss_simpseg.png

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

%IM%convert ^
  pss_out3.png ^
  pss_simpseg.png ^
  -compose Lighten -composite ^
  pss_out4.png
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.)

%IM%convert ^
  -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 ^
  pss_pf_src.png
pss_pf_src.png
call %PICTBAT%pruneStubs ^
  pss_pf_src.png pss_pf_out1.png 5
pss_pf_out1.png
%IM%convert ^
  pss_pf_src.png ^
  -trim ^
  -bordercolor Black -border 1 ^
  pss_pf_trm.png
pss_pf_trm.png
call %PICTBAT%pruneStubs ^
  pss_pf_trm.png pss_pf_out2.png 5

%IM%convert ^
  pss_pf_out2.png ^
  -shave 1 ^
  -background Black ^
  -layers Flatten ^
  pss_pf_out2.png
pss_pf_out2.png

Future

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

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,
rem makes output %2 version with short stubs removed.
rem %3 threshold for stub removal, integer number of pixels.
rem   Stubs larger than this will not be removed.

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

@setlocal enabledelayedexpansion

@call echoOffSave

call %PICTBAT%setInOut %1 ps

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 (`%IM%convert ^
  xc: -format "QNUM=%%q" info:`) do set %%L

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

%IM%convert ^
  %INFILE% ^
-fill White +opaque Black ^
  +repage ^
  ( -clone 0 ^
    -morphology HMT LineEnds ^
    +write %ENDS% ^
    +delete ^
  ) ^
  -define morphology:compose=Darken ^
  -morphology Thinning "LineJunctions;LineJunctions:3>;LineJunctions:5" ^
  %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 (`%IM%convert ^
      %ENDS% ^
      -transparent Black ^
      sparse-color:- ^| sed -e 's/ /\n/g' `) do @(
      @echo color %%X,%%Y floodfill
      @set /A nPruned+=1
    )
  ) >%FLOODLIST%

  rem type %FLOODLIST%

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

  goto end
)

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

if ERRORLEVEL 1 exit /B 1

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% (
    set CH_EXCL=!CH_EXCL!,!ID!
    set /A nExcl+=1
  )
)

if %HAS_ANY%==0 (
  echo ** 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

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

if ERRORLEVEL 1 exit /B 1

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


:end

call echoRestore

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

pruneStubsRep.bat

rem Repeatedly calls pruneStubs until nPruned is zero.

set TMP_IMG=psr_tmp.miff

%IM%convert %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

%IM%convert %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.

@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 (`%IM%convert ^
    %INFILE% ^
    -morphology thicken "3>:-,0,-,1,-,1,0,1,0" ^
    -morphology thicken "3>:-,0,0,1,-,0,0,1,-" ^
    +write %SKEL4% ^
    ^( +clone ^
       -define "morphology:compose=Darken" ^
       -morphology Thinning "LineJunctions;LineJunctions:3>;LineJunctions:5" ^
    ^) ^
    -compose Difference -composite ^
    -morphology Thinning "Rectangle:2x1;Rectangle:1x2" ^
    -transparent Black ^
    sparse-color:- ^| sed -e 's/ /\n/g' `) do @(
    @echo color %%X,%%Y floodfill
  )
) >%FLOODLIST%

rem type %FLOODLIST%

%IM%convert ^
  %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%

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

%IM%identify -version
Version: ImageMagick 6.9.5-3 Q16 x86 2016-07-22 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 Modules OpenMP 
Delegates (built-in): bzlib cairo flif freetype jng jp2 jpeg lcms lqr openexr pangocairo png ps 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 prunestubs.h1. To re-create this web page, run "procH1 prunestubs".


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 22-June-2016.

Page created 23-Jul-2016 13:25:02.

Copyright © 2016 Alan Gibson.