# HG changeset patch
# User Hartmut Gimpel <hg_code@gmx.de>
# Date 1659886241 -7200
#      Sun Aug 07 17:30:41 2022 +0200
# Node ID aad33859ad9fc58b9b4a9e5442e3338a3049d2b6
# Parent  5fdfac2d8d4c708c24098a104bb0c33ca8a02387
bwmorph: improve algorithm for "spur" processing (bug #62452)

inst/bwmorph.m: change algorithm for "spur" to improve compatibility
                add more BISTs

diff -r 5fdfac2d8d4c -r aad33859ad9f inst/bwmorph.m
--- a/inst/bwmorph.m	Sat Jul 16 22:17:18 2022 +0300
+++ b/inst/bwmorph.m	Sun Aug 07 17:30:41 2022 +0200
@@ -509,11 +509,34 @@
       endif
 
     case "spur"
-      ## lut = makelut(inline("xor(x(2,2),(sum((x&[0,1,0;1,0,1;0,1,0])(:))==0)&&(sum((x&[1,0,1;0,0,0;1,0,1])(:))==1)&&x(2,2))","x"),3);
-      ## which is the same as
-      lut = repmat ([false(16, 1); true(16,1)], 16, 1); # identity
-      lut([18, 21, 81, 273]) = false; # 4 qualifying patterns
-      morph = @(x) applylut (x, lut);
+      ## generating funtion:
+      ## # 1. padding
+      ## bw = padarray (bw, [1 1], true);
+      ## # 2. use structuring elements from en.wikipedia.org/wiki/Pruning_(morphology)#Structuring_Elements
+      ## #    to find end points and remove them
+      ## endpoints_fcn = @(x) x(5) && ((x(2) && all (! x([4 6 7 8 9])))...
+      ##   ||(x(4) && all (! x([2 3 6 8 9])))...
+      ##   ||(x(8) && all (! x([1 2 3 4 6])))...
+      ##   ||(x(6) && all (! x([1 2 4 7 8])))...
+      ##   ||(sum(x(:)) == 2 && any (x(:) & [1 0 1;0 0 0;1 0 1](:))));
+      ## endpoints_lut = makelut(endpoints_fcn, 3);
+      ## endpoints_image = applylut(bw, lut);
+      ## # 3. keep one endpoint of two element patterns, and keep single pixels
+      ## endpoints_keep_fcn = @(x) (x(5) && sum(x(:)) == 2 ...
+      ##   && any (x(:) & [1 0 0;0 0 1;1 1 0](:)))...          # two elements pattern
+      ##   || (x(5) && sum(x(:)) == 1);                        # single pixel
+      ## endpoints_keep_lut = makelut(endpoints_keep_fcn, 3);
+      ## remaining_endpoints_image = applylut(endpoints_image, endpoints_keep_lut);
+      ## bw = xor(bw, remaining_endpoints_image);
+      ## # 4. remove padding
+      ## morph = bw(2:end-1, 2:end-1);
+      lut1 = false (512, 1);
+      lut2 = false (512, 1);
+      lut1([18, 19, 20, 21, 23, 24, 25, 26, 49, 53, 81, 89, 90, 145, ...
+             209, 273, 305, 309, 401, 465]) = true;
+      lut2([17, 19, 25, 81, 273]) = true;
+      morph = @(x) xor (x, applylut (applylut (padarray (x, [1 1], true), ...
+                        lut1), lut2)(2:end-1, 2:end-1));
 
     case "thicken"
       if (n > 0)
@@ -786,8 +809,8 @@
 %!                 1  1  1  1  1]);
 %! assert (bwmorph (in, "remove", Inf), out);
 
-%!xtest
-%! ## tests for spur are failing (matlab incompatible)
+%!test
+%! ## tests for spur: see bug 62452
 %! in  = logical ([0  1  0  0  0
 %!                 1  0  0  1  0
 %!                 1  0  1  0  0
@@ -808,6 +831,109 @@
 %!                 1  1  1  1  1]);
 %! assert (bwmorph (in, "spur", Inf), out);
 
+%!test
+%! in = [1 1 1 1 1
+%!       1 0 0 0 1
+%!       1 0 1 0 1
+%!       1 0 1 0 1
+%!       1 1 1 1 1];
+%! out = [1 1 1 1 1
+%!        1 0 0 0 1
+%!        1 0 0 0 1
+%!        1 0 1 0 1
+%!        1 1 1 1 1];
+%! assert (bwmorph (in, "spur"), logical (out));
+
+%!test
+%! in = [1 1 1 1
+%!       1 0 0 1
+%!       1 0 1 1
+%!       1 0 0 1
+%!       1 1 1 1];
+%! out = [1 1 1 1
+%!        1 0 0 1
+%!        1 0 0 1
+%!        1 0 0 1
+%!        1 1 1 1];
+%! assert (bwmorph (in, "spur"), logical (out));
+
+%!test    # for "spur" on border pixels
+%! a = [1 0 1
+%!      0 0 0
+%!      1 0 1];
+%! a_out = [1 0 1
+%!          0 0 0
+%!          1 0 1];
+%! b = [0 0 1 0 0
+%!      0 0 0 0 0
+%!      1 0 1 0 1
+%!      0 0 0 0 0
+%!      0 0 1 0 0];
+%! b_out = [0 0 0 0 0
+%!          0 0 0 0 0
+%!          0 0 1 0 0
+%!          0 0 0 0 0
+%!          0 0 0 0 0];
+%! c = [1 1 0 1
+%!      0 0 0 1
+%!      1 0 0 0
+%!      1 0 1 1];
+%! c_out = [1 1 0 1
+%!          0 0 0 1
+%!          1 0 0 0
+%!          1 0 1 1];
+%! d = [1 0 1 1
+%!      1 0 0 0
+%!      0 0 0 1
+%!      1 1 0 1];
+%! d_out = [1 0 1 1
+%!          1 0 0 0
+%!          0 0 0 1
+%!          1 1 0 1];
+%! e = [0 1 0 0 0
+%!      0 1 0 1 1
+%!      0 0 0 0 0
+%!      1 1 0 1 0
+%!      0 0 0 1 0];
+%! e_out = [0 1 0 0 0
+%!          0 0 0 0 1
+%!          0 0 0 0 0
+%!          1 0 0 0 0
+%!          0 0 0 1 0];
+%! f = [0 1 1 0 0
+%!      0 0 0 0 1
+%!      1 0 0 0 1
+%!      1 0 0 0 0
+%!      0 0 1 1 0];
+%! f_out = [0 1 1 0 0
+%!          0 0 0 0 1
+%!          1 0 0 0 1
+%!          1 0 0 0 0
+%!          0 0 1 1 0];
+%! g = [1 0 0 1 0 0 1 0
+%!      0 1 0 0 1 0 0 1
+%!      0 0 0 0 0 0 0 0
+%!      1 0 0 1 0 0 1 0
+%!      0 1 0 0 1 0 0 1
+%!      0 0 0 0 0 0 0 0
+%!      1 0 0 1 0 0 1 0
+%!      0 1 0 0 1 0 0 1];
+%! g_out = [1 0 0 1 0 0 1 0
+%!          0 0 0 0 0 0 0 1
+%!          0 0 0 0 0 0 0 0
+%!          1 0 0 1 0 0 0 0
+%!          0 0 0 0 0 0 0 1
+%!          0 0 0 0 0 0 0 0
+%!          1 0 0 0 0 0 0 0
+%!          0 1 0 0 1 0 0 1];
+%! assert (bwmorph (a, "spur"), logical (a_out));
+%! assert (bwmorph (b, "spur"), logical (b_out));
+%! assert (bwmorph (c, "spur"), logical (c_out));
+%! assert (bwmorph (d, "spur"), logical (d_out));
+%! assert (bwmorph (e, "spur"), logical (e_out));
+%! assert (bwmorph (f, "spur"), logical (f_out));
+%! assert (bwmorph (g, "spur"), logical (g_out));
+
 ## several tests for "thicken":
 %!test
 %! bw = false (3, 3);
