changeset 6:f048aaec1b2d

fill and edge detection operators
author aadler
date Sun, 17 Mar 2002 02:38:52 +0000
parents 3ad01c0606eb
children 2bb14d8244ce
files bwfill.cc bwselect.m edge.m
diffstat 3 files changed, 492 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
new file mode 100644
--- /dev/null
+++ b/bwfill.cc
@@ -0,0 +1,215 @@
+/*
+ * BWFILL: fill a bw image starting at points
+ * imo= block(im, xregs, yregs);
+ *
+ * Copyright (C) 1999 Andy Adler
+ * This code has no warrany whatsoever.
+ * Do what you like with this code as long as you
+ *     leave this copyright in place.
+ *
+ * $Id$
+ */
+
+#include <octave/oct.h>
+
+#define   UP     (-1)
+#define   DN     (+1)
+#define   RT     (+ioM)
+#define   LF     (-ioM)
+
+/*
+ * check if the point needs to be filled, if so
+ * fill it and change the appropriate variables
+ */
+void checkpoint( int pt,
+      unsigned char* imo,
+               int * ptstack,
+               int * npoints ) {
+// printf("filling %d np=%d fill=%d\n",pt,*npoints, *(imo+pt)==0 );
+   if( *(imo+pt) != 0 ) return;
+
+   *(imo+pt) = 2;
+   *(ptstack + (*npoints))= pt;
+   (*npoints)++;
+}
+
+DEFUN_DLD (bwfill, args, ,
+  "[...] = bwfill (...)
+   [BW2,IDX] = BWFILL(BW1,Y,X,N) performs a flood-fill on BW1
+       
+       (X(k), Y(k)) are rows and columns of seed points
+
+   [BW2,IDX] = BWFILL(BW1,'holes',N) fills interior holes in BW1
+
+       N = 4 or 8(default) for neighborhood connectedness
+
+       IDX is the indices of the filled pixels
+       ")
+{
+   octave_value_list retval;
+   octave_value tmp;
+   ColumnVector xseed, yseed ;
+   int nargin = args.length ();
+
+   if (nargin < 2 ) {
+      print_usage ("bwfill");
+      return retval;
+   }
+
+   Matrix       im=    args(0).matrix_value();
+   int          imM=   im.rows();
+   int          imN=   im.columns();
+
+   int          nb=    8;
+   int          npoints= 0;
+   bool         fillmode= false;
+   if (args(1).is_string() && args(1).string_value() == "holes" ) {
+      fillmode= true;
+
+      npoints= 2*( imM + imN - 4 ); // don't start fill from corners
+
+      xseed= ColumnVector( npoints );
+      yseed= ColumnVector( npoints );
+      int idx= 0;
+      for (int j=2; j<= imN-1; j++) {
+         xseed( idx )= j;   yseed( idx++)= 1;   
+         xseed( idx )= j;   yseed( idx++)= imM;   
+      }
+
+      for (int i=2; i<= imM-1; i++) {
+         yseed( idx )= i;   xseed( idx++)= 1;   
+         yseed( idx )= i;   xseed( idx++)= imN;   
+      }
+
+      if (nargin >= 4 ) 
+         nb= (int) args(2).double_value();
+   } // holes mode? 
+   else {
+      {
+         ColumnVector tmp( args(2).vector_value() );
+         xseed= tmp;
+      }
+      {
+         ColumnVector tmp( args(1).vector_value() );
+         yseed= tmp;
+      }
+      npoints= xseed.length();
+      if (nargin >= 4 ) 
+         nb= (int) args(3).double_value();
+   } // holes mode? 
+
+/*
+ * put a one pixel thick boundary around the image
+ *  so that we can be more efficient in the main loop
+ */
+   int           ioM=   imM+2;
+   unsigned char imo[ (imM+2) * (imN+2) ];
+
+   for (int i=0; i<imM; i++) 
+      for (int j=0; j<imN; j++)
+         imo[(i+1) + ioM*(j+1)]= ( im(i,j) > 0 ) ;
+
+   for (int i=0; i<ioM; i++) 
+      imo[i]= imo[i + ioM*(imN+1)] = 3;
+
+   for (int j=1; j<imN+1; j++)
+      imo[ioM*j]= imo[imM+1 + ioM*j] = 3;
+
+// This is obviously big enough for the point stack, but I'm
+// sure it can be smaller. 
+   int     ptstack[ ioM*imN ];
+
+   int seedidx= npoints; 
+   npoints= 0;
+   while ( (--seedidx) >= 0 ) {
+// no need to add 1 to convert indexing style because we're adding a boundary
+      int pt= (int) xseed( seedidx )*ioM + (int) yseed( seedidx ); 
+      checkpoint( pt , imo, ptstack, &npoints );
+   }
+
+   while ( npoints > 0 ) {
+      npoints--;
+      int pt= ptstack[ npoints ];
+      
+      checkpoint( pt + LF, imo, ptstack, &npoints );
+      checkpoint( pt + RT, imo, ptstack, &npoints );
+      checkpoint( pt + UP, imo, ptstack, &npoints );
+      checkpoint( pt + DN, imo, ptstack, &npoints );
+      
+      if (nb==8) {
+         checkpoint( pt + LF + UP, imo, ptstack, &npoints );
+         checkpoint( pt + RT + UP, imo, ptstack, &npoints );
+         checkpoint( pt + LF + DN, imo, ptstack, &npoints );
+         checkpoint( pt + RT + DN, imo, ptstack, &npoints );
+      }
+   } // while ( npoints
+
+   Matrix       imout( imM, imN );
+   ColumnVector idxout (imM*imN );
+   int idx=0;
+
+   int notvalidpt= 0;
+   int idxpoint=   2;
+   if ( fillmode ) {
+      notvalidpt= 2;
+      idxpoint=   0;
+   }
+
+   for (int i=0; i<imM; i++) 
+      for (int j=0; j<imN; j++) {
+         imout(i,j) =    (double) ( imo[(i+1) + ioM*(j+1)] != notvalidpt );
+         if ( imo[(i+1) + ioM*(j+1)] == idxpoint )
+            idxout(idx++) = (double) (i + j*imM + 1);
+      }
+
+   /*
+   Matrix imout( imM+2, imN+2 );
+   for (int i=0; i<imM+2; i++) 
+      for (int j=0; j<imN+2; j++)
+         imout(i,j) = (double) imo[i + ioM*j];
+    */
+
+   retval(0)= imout;
+// we need to do this to be able to return a proper empty vector
+   if (idx > 0) 
+      retval(1)= idxout.extract(0, idx-1);
+   else
+      retval(1)= ColumnVector ( 0 );
+   return retval;
+}
+
+
+/*
+ * $Log$
+ * Revision 1.1  2002/03/17 02:38:51  aadler
+ * fill and edge detection operators
+ *
+ * Revision 1.9  2000/06/16 20:22:47  aadler
+ * mods for 2.1/2.0 compat
+ *
+ * Revision 1.8  2000/06/13 17:27:24  aadler
+ * mods for 2.1.30
+ *
+ * Revision 1.7  1999/06/10 19:42:12  aadler
+ * minor verbose fix
+ *
+ * Revision 1.6  1999/06/08 16:30:30  aadler
+ * bug fix. reversed r,c input arguments
+ *
+ * Revision 1.5  1999/06/08 15:41:02  aadler
+ * now fills in holes
+ *
+ * Revision 1.4  1999/06/08 15:21:02  aadler
+ * fixed bug that so specified points are only used if they can fill
+ *
+ * Revision 1.3  1999/06/08 15:05:08  aadler
+ * now returns 1 and gives index output
+ *
+ * Revision 1.2  1999/06/04 21:58:57  aadler
+ * fixed 8 vs 4 neighborhood
+ *
+ * Revision 1.1  1999/06/04 21:43:20  aadler
+ * Initial revision
+ *
+ *
+ */
new file mode 100644
--- /dev/null
+++ b/bwselect.m
@@ -0,0 +1,37 @@
+function [imout, idx] = bwselect( im, cols, rows, connect )
+# BWSELECT: select connected regions in a binary image
+# [imout, idx] = bwselect( im, cols, rows, connect )
+#
+#   im          -> binary input image
+#   [cols,rows] -> vectors of starting points (x,y)
+#   connect     -> connectedness 4 or 8. default is 8
+#   imout       -> the image of all objects in image im that overlap
+#                  pixels in (cols,rows)
+#   idx         -> index of pixels in imout
+
+# Copyright (C) 1999 Andy Adler
+# This code has no warrany whatsoever.
+# Do what you like with this code as long as you
+#     leave this copyright in place.
+#
+# $Id$
+
+if nargin<4
+   connect= 8;
+end
+
+[jnk,idx]= bwfill( ~im, cols,rows, connect );
+
+imout= zeros( size(jnk) );
+imout( idx ) = 1;
+
+# 
+# $Log$
+# Revision 1.1  2002/03/17 02:38:52  aadler
+# fill and edge detection operators
+#
+# Revision 1.1  1999/06/08 17:06:01  aadler
+# Initial revision
+#
+#
+
new file mode 100644
--- /dev/null
+++ b/edge.m
@@ -0,0 +1,240 @@
+function [imout, thresh] = edge( im, method, thresh, param2 )
+# EDGE: find image edges
+# [imout, thresh] = edge( im, method, thresh, param2 )
+#
+# OUTPUT
+#  imout  -> output image
+#  thresh -> output thresholds
+#
+# INPUT
+#  im     -> input image (greyscale)
+#  thresh -> threshold value (value is estimated if not given)
+#  
+# The following methods are based on high pass filtering the image in
+#   two directions, calculating a combined edge weight from and then thresholding
+#
+# method = 'roberts'
+#     filt1= [1 0 ; 0 -1];   filt2= rot90( filt1 )
+#     combine= sqrt( filt1^2 + filt2^2 )  
+# method = 'sobel'
+#     filt1= [1 2 1;0 0 0;-1 -2 -1];      filt2= rot90( filt1 ) 
+#     combine= sqrt( filt1^2 + filt2^2 )  
+# method = 'prewitt'
+#     filt1= [1 1 1;0 0 0;-1 -1 -1];      filt2= rot90( filt1 ) 
+#     combine= sqrt( filt1^2 + filt2^2 )  
+# method = 'kirsh'
+#     filt1= [1 2 1;0 0 0;-1 -2 -1];  filt2 .. filt8 are 45 degree rotations of filt1
+#     combine= max( filt1 ... filt8 )
+#
+# methods based on filtering the image and finding zero crossings
+#
+# method = 'log' -> Laplacian of Gaussians 
+#      param2 is the standard deviation of the filter, default is 2
+# method = 'zerocross' -> generic zero-crossing filter
+#      param2 is the user supplied filter
+# 
+# method = 'andy' -> my idea
+#      A.Adler's idea (c) 1999. somewhat based on the canny method
+#      Step 1: Do a sobel edge detection and to generate an image at
+#               a high and low threshold
+#      Step 2: Edge extend all edges in the LT image by several pixels,
+#               in the vertical, horizontal, and 45degree directions.
+#               Combine these into edge extended (EE) image
+#      Step 3: Dilate the EE image by 1 step
+#      Step 4: Select all EE features that are connected to features in
+#               the HT image
+#                
+#      Parameters:
+#        param2(1)==0 or 4 or 8 -> perform x connected dilatation (step 3)
+#        param2(2)    dilatation coeficient (threshold) in step 3
+#        param2(3)    length of edge extention convolution (step 2)
+#        param2(4)    coeficient of extention convolution in step 2
+#        defaults = [8 1 3 3]
+
+# Copyright (C) 1999 Andy Adler
+# This code has no warrany whatsoever.
+# Do what you like with this code as long as you
+#     leave this copyright in place.
+#
+# $Id$
+
+[n,m]= size(im);
+xx= 2:m-1;
+yy= 2:n-1;
+
+if   strcmp(method,'roberts') || strcmp(method,'sobel') || ...
+     strcmp(method,'prewitt') 
+     
+
+   if strcmp(method,'roberts') 
+      filt= [1 0;0 -1]/4;               tv= 6;
+   elseif strcmp(method,'sobel') 
+      filt= [1 2 1;0 0 0; -1 -2 -1]/8;  tv= 2;
+   elseif strcmp(method,'prewitt') 
+      filt= [1 1 1;0 0 0; -1 -1 -1]/6;  tv= 4;
+   end
+
+   imo= conv2(im, rot90(filt), 'same').^2 + conv2(im, filt, 'same').^2;
+   
+# check to see if the user supplied a threshold
+# if not, calculate one in the same way as Matlab
+
+   if nargin<3
+      thresh= sqrt( tv* mean(mean( imo(yy,xx) ))  );
+   end
+
+# The filters are defined for sqrt(imo), but since we calculated imo, compare
+#  to thresh ^2
+
+   imout= ( imo >= thresh^2 );   
+
+# Thin the wide edges
+   xpeak= imo(yy,xx-1) <= imo(yy,xx) & imo(yy,xx) > imo(yy,xx+1) ;
+   ypeak= imo(yy-1,xx) <= imo(yy,xx) & imo(yy,xx) > imo(yy+1,xx) ;
+   imout(yy,xx)= imout(yy,xx) & ( xpeak | ypeak );
+
+elseif strcmp(method,'kirsch')   
+
+   filt1= [1 2 1;0 0 0;-1 -2 -1];   fim1= conv2(im,filt1,'same');
+   filt2= [2 1 0;1 0 -1;0 -1 -2];   fim2= conv2(im,filt2,'same');
+   filt3= [1 0 -1;2 0 -2;1 0 -1];   fim3= conv2(im,filt3,'same');
+   filt4= [0 1 2;-1 0 1;-2 -1 0];   fim4= conv2(im,filt4,'same');
+
+   imo= reshape(max([abs(fim1(:)) abs(fim2(:)) abs(fim3(:)) abs(fim4(:))]'),n,m);
+
+   if nargin<3
+      thresh=  2* mean(mean( imo(yy,xx) )) ;
+   end
+
+   imout=  imo >= thresh ;   
+
+# Thin the wide edges
+   xpeak= imo(yy,xx-1) <= imo(yy,xx) & imo(yy,xx) > imo(yy,xx+1) ;
+   ypeak= imo(yy-1,xx) <= imo(yy,xx) & imo(yy,xx) > imo(yy+1,xx) ;
+   imout(yy,xx)= imout(yy,xx) & ( xpeak | ypeak );
+
+elseif  strcmp(method,'log') || strcmp(method,'zerocross') 
+
+   if strcmp(method,'log') 
+      if nargin >= 4;    sd= param2;
+      else               sd= 2;
+      end
+
+      sz= ceil(sd*3);
+      [x,y]= meshgrid( -sz:sz, -sz:sz );
+      filt = exp( -( x.^2 + y.^2 )/2/sd^2 ) .* ...
+                   ( x.^2 + y.^2 - 2*sd^2 ) / 2 / pi / sd^6 ;
+   else
+      filt = param2;
+   end
+   filt = filt - mean(filt(:));
+
+   imo= conv2(im, filt, 'same');
+
+   if nargin<3 || isempty( thresh )
+      thresh=  0.75* mean(mean( abs(imo(yy,xx)) )) ;
+   end
+
+   zcross= imo > 0;
+   yd_zc=  diff( zcross );
+   xd_zc=  diff( zcross' )';
+   yd_io=  abs(diff( imo ) ) > thresh;
+   xd_io=  abs(diff( imo')') > thresh;
+
+# doing it this way puts the transition at the <=0 point
+   xl= zeros(1,m);  yl= zeros(n,1);
+   imout= [    ( yd_zc ==  1 ) & yd_io ; xl] | ...
+          [xl; ( yd_zc == -1 ) & yd_io     ] | ...
+          [    ( xd_zc ==  1 ) & xd_io , yl] | ... 
+          [yl, ( xd_zc == -1 ) & xd_io     ];
+
+elseif  strcmp(method,'canny')  
+    error("method canny not implemented");
+
+elseif  strcmp(method,'andy')  
+
+   filt= [1 2 1;0 0 0; -1 -2 -1]/8;  tv= 2;
+   imo= conv2(im, rot90(filt), 'same').^2 + conv2(im, filt, 'same').^2;
+   if nargin<3 || thresh==[];
+      thresh= sqrt( tv* mean(mean( imo(yy,xx) ))  );
+   end
+#     sum( imo(:)>thresh ) / prod(size(imo))
+   dilate= [1 1 1;1 1 1;1 1 1]; tt= 1; sz=3; dt=3;
+   if nargin>=4
+      # 0 or 4 or 8 connected dilation
+      if length(param2) > 0
+         if      param2(1)==4 ; dilate= [0 1 0;1 1 1;0 1 0];
+         elseif  param2(1)==0 ; dilate= 1;
+         end
+      end
+      # dilation threshold
+      if length(param2) > 2; tt= param2(2); end
+      # edge extention length
+      if length(param2) > 2; sz= param2(3); end
+      # edge extention threshold
+      if length(param2) > 3; dt= param2(4); end
+      
+   end
+   fobliq= [0 0 0 0 1;0 0 0 .5 .5;0 0 0 1 0;0 0 .5 .5 0;0 0 1 0 0; 
+                      0 .5 .5 0 0;0 1 0 0 0;.5 .5 0 0 0;1 0 0 0 0];
+   fobliq= fobliq( 5-sz:5+sz, 3-ceil(sz/2):3+ceil(sz/2) );
+
+   xpeak= imo(yy,xx-1) <= imo(yy,xx) & imo(yy,xx) > imo(yy,xx+1) ;
+   ypeak= imo(yy-1,xx) <= imo(yy,xx) & imo(yy,xx) > imo(yy+1,xx) ;
+
+   imht= ( imo >= thresh^2 * 2); # high threshold image   
+   imht(yy,xx)= imht(yy,xx) & ( xpeak | ypeak );
+   imht([1,n],:)=0; imht(:,[1,m])=0;
+
+%  imlt= ( imo >= thresh^2 / 2); # low threshold image   
+   imlt= ( imo >= thresh^2 / 1); # low threshold image   
+   imlt(yy,xx)= imlt(yy,xx) & ( xpeak | ypeak );
+   imlt([1,n],:)=0; imlt(:,[1,m])=0;
+
+# now we edge extend the low thresh image in 4 directions
+
+   imee= ( conv2( imlt, ones(2*sz+1,1)    , 'same') > tt ) | ...
+         ( conv2( imlt, ones(1,2*sz+1)    , 'same') > tt ) | ...
+         ( conv2( imlt, eye(2*sz+1)       , 'same') > tt ) | ...
+         ( conv2( imlt, rot90(eye(2*sz+1)), 'same') > tt ) | ...
+         ( conv2( imlt, fobliq            , 'same') > tt ) | ...
+         ( conv2( imlt, fobliq'           , 'same') > tt ) | ...
+         ( conv2( imlt, rot90(fobliq)     , 'same') > tt ) | ...
+         ( conv2( imlt, flipud(fobliq)    , 'same') > tt );
+#  imee(yy,xx)= conv2(imee(yy,xx),ones(3),'same') & ( xpeak | ypeak );
+   imee= conv2(imee,dilate,'same') > dt; #
+
+%  ff= find( imht==1 );
+%  imout = bwselect( imee, rem(ff-1, n)+1, ceil(ff/n), 8);  
+   imout = imee;
+
+
+else
+
+   error (['Method ' method ' is not recognized']);
+
+end
+
+
+
+
+# 
+# $Log$
+# Revision 1.1  2002/03/17 02:38:52  aadler
+# fill and edge detection operators
+#
+# Revision 1.4  2000/11/20 17:13:07  aadler
+# works?
+#
+# Revision 1.3  1999/06/09 17:29:36  aadler
+# implemented 'andy' mode edge detection
+#
+# Revision 1.2  1999/06/08 14:26:50  aadler
+# zero-cross and LoG filters work
+#
+# Revision 1.1  1999/06/07 21:01:38  aadler
+# Initial revision
+#
+#
+
+#