changeset 802:bec6e07f4272

bwmorph: support of N dimensional images and performance increase. * bwmorph.m: add support to N dimensional images for bothat, clean, close, dilate, erode, fill, majority, open, remove, skel-lantuejoul, and tophat. An increased performance of 10-5x was also introduced for clean, fill, majority, and remove, by making use of convn instead of applylut. * NEWS: mention changes to bwmorph including the changes introduced with cset a9226ee5088b.
author Carnë Draug <carandraug@octave.org>
date Wed, 09 Oct 2013 07:37:38 +0100
parents 4598c2a5bf1a
children 8905fa8c4877
files NEWS inst/bwmorph.m
diffstat 2 files changed, 99 insertions(+), 59 deletions(-) [+]
line wrap: on
line diff
--- a/NEWS
+++ b/NEWS
@@ -13,6 +13,10 @@
     functions that use them, such imopen and imclose, get an equivalent
     performance boost.
 
+ ** Most of bwmorph operations now support N dimensional images and have
+    increased performance.  Other Matlab compatibility fixes have been
+    made such as displaying image when there's no output variable.
+
  ** The __spatial_filtering__ function has been mostly rewritten and
     performs in approximattely 1/5 to 2/5 of the previous time, depending
     on the filter.  With this change, all functions dependent on it,
--- a/inst/bwmorph.m
+++ b/inst/bwmorph.m
@@ -24,6 +24,8 @@
 ## table below. By default, @var{n} is 1.  If @var{n} is @code{Inf}, the
 ## operation is continually performed until it no longer changes the image.
 ##
+## In some operations, @var{bw} can be a binary matrix with any number of
+## dimensions (see details on the table of operations).
 ##
 ## Note that the output will always be of class logical, independently of
 ## the class of @var{bw}.
@@ -32,7 +34,9 @@
 ## @item bothat
 ## Performs a bottom hat operation, a closing operation (which is a
 ## dilation followed by an erosion) and finally substracts the original
-## image (see @code{imbothat}).
+## image (see @code{imbothat}).  @var{bw} can have any number of
+## dimensions, and @code{strel ("hypercube", ndims (@var{bw}), 3)} is
+## used as structuring element.
 ##
 ## @item bridge
 ## Performs a bridge operation. Sets a pixel to 1 if it has two nonzero
@@ -40,45 +44,58 @@
 ## 119 3-by-3 patterns which trigger setting a pixel to 1.
 ##
 ## @item clean
-## Performs an isolated pixel remove operation. Sets a pixel to 0 if all
-## of its eight-connected neighbours are 0.
+## Performs an isolated pixel remove operation.  Sets a pixel to 0 if all
+## of its eight-connected neighbours are 0.  @var{bw} can have any number
+## of dimensions in which case connectivity is @code{(3^ndims(@var{bw})) -1},
+## i.e., all of the elements around it.
 ##
 ## @item close
-## Performs closing operation, which is a dilation followed by erosion.
-## It uses a ones(3) matrix as structuring element for both operations
-## (see @code{imclose}).
+## Performs closing operation, which is a dilation followed by erosion
+## (see @code{imclose}).  @var{bw} can have any number of dimensions,
+## and @code{strel ("hypercube", ndims (@var{bw}), 3)} is used as
+## structuring element.
 ##
 ## @item diag
 ## Performs a diagonal fill operation. Sets a pixel to 1 if that
 ## eliminates eight-connectivity of the background.
 ##
 ## @item dilate
-## Performs a dilation operation. It uses ones(3) as structuring element
-## (see @code{imdilate}).
+## Performs a dilation operation (see @code{imdilate}).  @var{bw} can have
+## any number of dimensions, and
+## @code{strel ("hypercube", ndims (@var{bw}), 3)} is used as
+## structuring element.
 ##
 ## @item erode
-## Performs an erosion operation. It uses ones(3) as structuring element
-## (see @code{imerode}).
+## Performs an erosion operation (see @code{imerode}).  @var{bw} can have
+## any number of dimensions, and
+## @code{strel ("hypercube", ndims (@var{bw}), 3)} is used as
+## structuring element.
 ##
 ## @item fill
 ## Performs a interior fill operation. Sets a pixel to 1 if all
-## four-connected pixels are 1.
+## four-connected pixels are 1.  @var{bw} can have any number
+## of dimensions in which case connectivity is @code{(2*ndims(@var{bw}))}.
 ##
 ## @item hbreak
 ## Performs a H-break operation. Breaks (sets to 0) pixels that are
 ## H-connected.
 ##
 ## @item majority
-## Performs a majority black operation. Sets a pixel to 1 if five
-## or more pixels in a 3-by-3 window are 1. If not it is set to 0.
+## Performs a majority black operation.  Sets a pixel to 1 if the majority
+## of the pixels (5 or more for a two dimensional image) in a 3-by-3 window
+## is 1. If not set to 0.  @var{bw} can have any number of dimensions in
+## which case the window has dimensions @code{repmat (3, 1, ndims (@var{bw}))}.
 ##
 ## @item open
 ## Performs an opening operation, which is an erosion followed by a
-## dilation. It uses ones(3) as structuring element (see @code{imopen}).
+## dilation (see @code{imopen}).  @var{bw} can have any number of
+## dimensions, and @code{strel ("hypercube", ndims (@var{bw}), 3)}
+## is used as structuring element.
 ##
 ## @item remove
-## Performs a iterior pixel remove operation. Sets a pixel to 0 if 
-## all of its four-connected neighbours are 1.
+## Performs a iterior pixel remove operation.  Sets a pixel to 0 if
+## all of its four-connected neighbours are 1.  @var{bw} can have any number
+## of dimensions in which case connectivity is @code{(2*ndims(@var{bw}))}.
 ##
 ## @item shrink
 ## Performs a shrink operation. Sets pixels to 0 such that an object
@@ -109,6 +126,8 @@
 ## @var{n} times or number of iterations specified in algorithm
 ## description. It's most useful to run this algorithm with @code{n=Inf}.
 ##
+## @var{bw} can have any number of dimensions.
+##
 ## @item skel-pratt
 ## Performs a skeletonization operation as described by William K. Pratt
 ## in "Digital Image Processing".
@@ -135,7 +154,9 @@
 ## @item tophat
 ## Performs a top hat operation, a opening operation (which is an
 ## erosion followed by a dilation) and finally substracts the original
-## image (see @code{imtophat}).
+## image (see @code{imtophat}).  @var{bw} can have any number of
+## dimensions, and @code{strel ("hypercube", ndims (@var{bw}), 3)}
+## is used as structuring element.
 ## @end table
 ##
 ## Some useful concepts to understant operators:
@@ -223,7 +244,7 @@
   switch (tolower (operation))
     case "bothat"
       loop_once = true;
-      se  = strel ("square", 3);
+      se = strel ("hypercube", ndims (bw), 3);
       morph = @(x) imbothat (x, se);
 
 #    case "branchpoints"
@@ -252,17 +273,21 @@
       morph = @(x) applylut (x, lut);
 
     case "clean"
+      ## Remove elements that are surrounded by false elements. So we
+      ## create a hypercube kernel of side length 3 and values 1, and
+      ## center value with the connectivity value. After convolution,
+      ## only true elements with another one surrounding it, will have
+      ## values above the connectivity (remember that the input matrix
+      ## is binary).
       loop_once = true;
-      ## BW(j,k) = X && (X0||X1||...||X7)
-      ## lut = makelut (inline ("x(2,2)&&any((x.*[1,1,1;1,0,1;1,1,1])(:))", "x"), 3);
-      ## which is the same as...
-      lut = repmat ([false(16, 1); true(16, 1)], 16, 1); # identity
-      lut(17) = false; # isolated to 0
-      morph = @(x) applylut (x, lut);
+      kernel       = ones (repmat (3, 1, ndims (bw)));
+      connectivity = numel (kernel) -1;
+      kernel(ceil (numel (kernel) /2)) = connectivity; # n-dimensional center
+      morph = @(x) convn (x, kernel, "same") > connectivity;
 
     case "close"
       loop_once = true;
-      se = strel ("square", 3);
+      se = strel ("hypercube", ndims (bw), 3);
       morph = @(x) imclose (x, se);
 
     case "diag"
@@ -287,7 +312,7 @@
       morph = @(x) applylut (x, lut);
 
     case "dilate"
-      se = strel ("square", 3);
+      se = strel ("hypercube", ndims (bw), 3);
       morph = @(x) imdilate (x, se);
 
 #    case "endpoints"
@@ -300,17 +325,21 @@
       ## im* functions, and in bwmorph. The rest of bwmorph that uses
       ## erosion (open, close, bothat, and tophat a least), suffer the
       ## same problem. We do not replicate the bug and use imerode.
-      se = strel ("square", 3);
+      se = strel ("hypercube", ndims (bw), 3);
       morph = @(x) imerode (x, se);
 
     case "fill"
+      ## Fill elements that are surrounded by true elements (with
+      ## connectivity 4 and its equivalent to N dimensions).
+      ## So we create a hypercube kernel with the connected pixels as 1
+      ## and the center with the connectivity value. After convolution,
+      ## only true elements, or elements surrounded by true elements
+      ## will have a values >= connectivity.
       loop_once = true;
-      ## lut = makelut (inline ("x(2,2)||(sum((x&[0,1,0;1,0,1;0,1,0])(:))==4)", "x"), 3);
-      ## which is the same as...
-      lut = repmat ([false(16, 1); true(16, 1)], 16, 1); # identity
-      ## 16 exceptions
-      lut([171 172 175 176 235 236 239 240 427 428 431 432 491 492 495 496]) = true;
-      morph = @(x) applylut (x, lut);
+      kernel = double (draw_nd_cross (bw));
+      connectivity = nnz (kernel) -1;
+      kernel(ceil (numel (kernel) /2)) = connectivity;
+      morph = @(x) convn (x, kernel, "same") >= connectivity;
 
     case "hbreak"
       loop_once = true;
@@ -321,37 +350,30 @@
       morph = @(x) applylut (x, lut);
 
     case "majority"
-      ## lut = makelut (inline ("sum((x&ones(3,3))(:))>=5"), 3);
-      lut = logical ([0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;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;0;0;0;1;0;0;0;0;0;0;0;1;0;0;0;1;0;1;1;1;
-                      0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;1;0;0;0;0;0;0;0;1;0;0;0;1;0;1;1;1;
-                      0;0;0;0;0;0;0;1;0;0;0;1;0;1;1;1;0;0;0;1;0;1;1;1;0;1;1;1;1;1;1;1;
-                      0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;1;0;0;0;0;0;0;0;1;0;0;0;1;0;1;1;1;
-                      0;0;0;0;0;0;0;1;0;0;0;1;0;1;1;1;0;0;0;1;0;1;1;1;0;1;1;1;1;1;1;1;
-                      0;0;0;0;0;0;0;1;0;0;0;1;0;1;1;1;0;0;0;1;0;1;1;1;0;1;1;1;1;1;1;1;
-                      0;0;0;1;0;1;1;1;0;1;1;1;1;1;1;1;0;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;
-                      0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;1;0;0;0;0;0;0;0;1;0;0;0;1;0;1;1;1;
-                      0;0;0;0;0;0;0;1;0;0;0;1;0;1;1;1;0;0;0;1;0;1;1;1;0;1;1;1;1;1;1;1;
-                      0;0;0;0;0;0;0;1;0;0;0;1;0;1;1;1;0;0;0;1;0;1;1;1;0;1;1;1;1;1;1;1;
-                      0;0;0;1;0;1;1;1;0;1;1;1;1;1;1;1;0;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;
-                      0;0;0;0;0;0;0;1;0;0;0;1;0;1;1;1;0;0;0;1;0;1;1;1;0;1;1;1;1;1;1;1;
-                      0;0;0;1;0;1;1;1;0;1;1;1;1;1;1;1;0;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;
-                      0;0;0;1;0;1;1;1;0;1;1;1;1;1;1;1;0;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;
-                      0;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1]);
-      morph = @(x) applylut (x, lut);
+      ## If the majority of the elements surrounding an element is true,
+      ## it changes to true. We do this using convolution, with an
+      ## hypercube kernel, any value of the convolution above the half
+      ## number of elements becomes tru
+      kernel   = ones (repmat (3, 1, ndims (bw)));
+      majority = numel (kernel) /2;
+      morph    = @(x) convn (x, kernel, "same") >= majority;
 
     case "open"
       loop_once = true;
-      se = strel ("square", 3);
+      se = strel ("hypercube", ndims (bw), 3);
       morph = @(x) imopen (x, se);
 
     case "remove"
+      ## Remove elements that are surrounded by true elements by 4 connectivity.
+      ## We create a 4 connectivity kernel with -1 values, and a center with
+      ## the number of -1 values. Only true elements can have positives values,
+      ## with a maximum of 4 (or whatever is the connectivity value for that
+      ## number of dimensions) from the kernel center, and -1 per each of the
+      ## connectivity. If all are true, its value will go down to 0.
       loop_once = true;
-      ## lut = makelut (inline ("x(2,2)&&!(sum((x&[0,1,0;1,1,1;0,1,0])(:))==5)", "x"), 3);
-      lut = repmat ([false(16,1); true(16,1)], 16, 1); # identity
-      ## 16 qualifying patterns
-      lut ([187 188 191 192 251 252 255 256 443 444 447 448 507 508 511 512]) = false;
-      morph = @(x) applylut (x, lut);
+      kernel = - double (draw_nd_cross (bw));
+      kernel(ceil (numel (kernel) /2)) = nnz (kernel) -1;
+      morph = @(x) convn (x, kernel, "same") > 0;
 
     case "shrink"
       ## lut1 = makelut ("__conditional_mark_patterns_lut_fun__", 3, "S");
@@ -445,7 +467,7 @@
       ## of this, we will set n to 0 in the end. However, we must take care
       ## to not touch the input image if n already is zero.
       if (n > 0)
-        se  = strel ("square", 3);
+        se = strel ("hypercube", ndims (bw), 3);
         bw_tmp = false (size (bw)); # skeleton result
         i = 1;
         while (i <= n)
@@ -524,7 +546,7 @@
       ## top hat filtering has no effect after being performed once
       ## (inherits this behaviour from closing and opening)
       loop_once = true;
-      se = strel ("square", 3);
+      se = strel ("hypercube", ndims (bw), 3);
       morph = @(x) imtophat (x, se);
 
     otherwise
@@ -560,6 +582,20 @@
 
 endfunction
 
+function nd_cross = draw_nd_cross (bw)
+  ## FIXME there must be an easier way to do this. Also, this should
+  ##       probably be a shape in @strel
+  origin = false (repmat (3, 1, ndims (bw)));
+  center = ceil (numel (origin) /2);
+  origin(center) = true;
+  nd_cross = origin;
+  for dim = 1:ndims (bw)
+    se_size      = ones (1, ndims (bw));
+    se_size(dim) = 3;
+    nd_cross    |= imdilate (origin, true (se_size));
+  endfor
+endfunction
+
 %!demo
 %! bwmorph (true (11), "shrink", Inf)
 %! # Should return 0 matrix with 1 pixel set to 1 at (6,6)