Menu
▾
▴
[Octave-cvsupdate] SF.net SVN: octave:[8034] trunk/octave-forge/main/image
|
From: <ha...@us...> - 2010-12-22 23:02:21
|
Revision: 8034
http://octave.svn.sourceforge.net/octave/?rev=8034&view=rev
Author: hauberg
Date: 2010-12-22 23:02:14 +0000 (Wed, 22 Dec 2010)
Log Message:
-----------
New version of bwboundaries (from A Kelly)
Modified Paths:
--------------
trunk/octave-forge/main/image/INDEX
trunk/octave-forge/main/image/inst/bwboundaries.m
trunk/octave-forge/main/image/src/Makefile
Added Paths:
-----------
trunk/octave-forge/main/image/inst/fchcode.m
trunk/octave-forge/main/image/src/__boundary__.cc
Removed Paths:
-------------
trunk/octave-forge/main/image/src/__imboundary__.cc
Modified: trunk/octave-forge/main/image/INDEX
===================================================================
--- trunk/octave-forge/main/image/INDEX 2010-12-22 08:15:40 UTC (rev 8033)
+++ trunk/octave-forge/main/image/INDEX 2010-12-22 23:02:14 UTC (rev 8034)
@@ -77,6 +77,7 @@
conndef
bwhitmiss
regionprops
+ fchcode
Morhophological Operations
imerode
imdilate
Modified: trunk/octave-forge/main/image/inst/bwboundaries.m
===================================================================
--- trunk/octave-forge/main/image/inst/bwboundaries.m 2010-12-22 08:15:40 UTC (rev 8033)
+++ trunk/octave-forge/main/image/inst/bwboundaries.m 2010-12-22 23:02:14 UTC (rev 8034)
@@ -1,4 +1,5 @@
## Copyright (C) 2010 Soren Hauberg
+## Modified December 2010 by Andrew Kelly, IPS Radio & Space Services
##
## This program is free software; you can redistribute it and/or modify
## it under the terms of the GNU General Public License as published by
@@ -14,87 +15,81 @@
## along with this program; If not, see <http://www.gnu.org/licenses/>.
## -*- texinfo -*-
-## @deftypefn {Function File} {@var{boundaries} = } bwboundaries (@var{BW})
-## @deftypefnx {Function File} {@var{boundaries} = } bwboundaries (@var{BW}, @
-## @var{connectivity})
-## @deftypefnx {Function File} {@var{boundaries} = } bwboundaries (@var{BW}, @
-## @var{connectivity}, @var{options})
-## @deftypefnx {Function File} {[@var{boundaries}, @var{labels}] = } bwboundaries (@dots{})
-## @deftypefnx {Function File} {[@var{boundaries}, @var{labels}, @var{num_labels}] @
-## = } bwboundaries (@dots{})
+## @deftypefn {Function File} {@var{boundaries} = } bwboundaries(@var{BW})
+## @deftypefnx {Function File} {@var{boundaries} = } bwboundaries(@var{BW}, @var{conn})
+## @deftypefnx {Function File} {@var{boundaries} = } bwboundaries(@var{BW}, @var{conn}, @var{holes})
+## @deftypefnx {Function File} {[@var{boundaries}, @var{labels}] = } bwboundaries(@dots{})
+## @deftypefnx {Function File} {[@var{boundaries}, @var{labels}, @var{num_labels}] = } bwboundaries(@dots{})
## Trace the boundaries of the objects in a binary image.
##
## @var{boundaries} is a cell array in which each element is the boundary of an
-## object in the binary image @var{BW}. The boundary of an object is represented
-## by a @var{K} by 2 matrix where each row contains the @var{(x, y)} coordinates
-## of a point on the boundary.
+## object in the binary image @var{BW}. The clockwise boundary of each object is
+## computed by the @code{boundary} function.
##
-## By default the boundaries are computed using 4-connectivity. This can be
-## changed to 8-connectivity by setting @var{connectivity} to 8. Sadly, this
-## feature is not yet implemented.
+## By default the boundaries are computed using 8-connectivity. This can be
+## changed to 4-connectivity by setting @var{conn} to 4.
##
## By default @code{bwboundaries} computes all boundaries in the image, i.e.
## both interior and exterior object boundaries. This behaviour can be changed
-## through the @var{options} input argument. If this is the string @t{"holes"}
-## both boundary types are considered. If it is instead @t{"noholes"}, only exterior
+## through the @var{holes} input argument. If this is @t{'holes'},
+## both boundary types are considered. If it is instead @t{'noholes'}, only exterior
## boundaries will be traced.
##
-## If two or more output arguments are requested, the algorithm also computes
-## the labelled image as returned by @code{bwlabel} in @var{labels}. The number
+## If two or more output arguments are requested, the algorithm also returns
+## the labelled image computed by @code{bwlabel} in @var{labels}. The number
## of labels in this image is optionally returned in @var{num_labels}.
-## @seealso{bwlabel}
+## @seealso{boundary, bwlabel}
## @end deftypefn
-function [B, L, num_labels] = bwboundaries (bw, N = 4, options = "holes")
- ## Check input
+function [bound, labels, num_labels] = bwboundaries (bw, conn=8, holes="holes")
+ # check arguments
if (nargin < 1)
error ("bwboundaries: not enough input arguments");
endif
if (!ismatrix (bw) || ndims (bw) != 2)
error ("bwboundaries: first input argument must be a NxM matrix");
endif
- if (!isscalar (N) || !any (N == [4])) #, 8]))
- error ("bwboundaries: second input argument must be 4");
+ if (!isscalar (conn) || (conn != 4 && conn != 8))
+ error ("bwboundaries: second input argument must be 4 or 8");
endif
- if (!ischar (options) || !any (strcmpi (options, {"holes", "noholes"})))
- error ("bwboundaries: third input must be either \"holes\" or \"noholes\"");
+ if (!ischar (holes) || !any (strcmpi (holes, {'holes', 'noholes'})))
+ error ("bwboundaries: third input must be either \'holes\' or \'noholes\'");
endif
-
- ## Warn if the user request more output arguments than our implementation supports
- if (nargout > 3)
-% warning ("%s %s %s", ...
-% "bwboundaries: adjacency matrix output is currently not supported. " ...
-% "Please contact the Octave-Forge community if you want to contribute " ...
-% "an implementation of this");
- endif
-
- ## Make sure 'bw' is logical
bw = logical (bw);
- ## Found connected components in 'bw', and treat each of them seperatly
- [L, num_labels] = bwlabel (bw, N);
- B = cell (num_labels, 1);
- for n = 1:num_labels
- segment = (L == n);
- [R, C] = find (segment);
- if (numel (R) > 1)
- ## XXX: support 8-neighbors
-% B {n} = __imboundary__ (segment, 4, R (1), C (1));
- B {n} = __imboundary__ (segment.', N, C (1), R (1));
- else
- B {n} = [R, C];
- endif
+ # process each connected region separately
+ [labels, num_labels] = bwlabel (bw, conn);
+ bound = cell (num_labels, 1);
+ for k = 1:num_labels
+ bound {k} = __boundary__ ((labels == k), conn);
endfor
- ## If requested, compute internal boundaries as well
- if (strcmpi (options, "holes"))
- filled = bwfill (bw, "holes", N);
+ # compute internal boundaries as well?
+ if (strcmpi (holes, "holes"))
+ filled = bwfill (bw, "holes", conn);
holes = (filled & !bw);
- [internal, in_label, lin] = bwboundaries (holes, N, "noholes");
- B (end+1:end+lin, 1) = internal;
-
- in_label (in_label != 0) += num_labels;
- L += in_label;
+ [intBounds, intLabels, numIntLabels] = bwboundaries (holes, conn, "noholes");
+
+ bound (end+1 : end+numIntLabels, 1) = intBounds;
+ intLabels (intLabels != 0) += num_labels;
+ labels += intLabels;
endif
endfunction
+
+%!demo
+%! ## Generate a simple image
+%! bw = false (100);
+%! bw (10:30, 40:80) = true;
+%! bw (40:45, 40:80) = true;
+%!
+%! ## Find boundaries
+%! bounds = bwboundaries (bw);
+%!
+%! ## Plot result
+%! imshow (bw);
+%! hold on
+%! for k = 1:numel (bounds)
+%! plot (bounds {k} (:, 2), bounds {k} (:, 1), 'r', 'linewidth', 2);
+%! endfor
+%! hold off
Added: trunk/octave-forge/main/image/inst/fchcode.m
===================================================================
--- trunk/octave-forge/main/image/inst/fchcode.m (rev 0)
+++ trunk/octave-forge/main/image/inst/fchcode.m 2010-12-22 23:02:14 UTC (rev 8034)
@@ -0,0 +1,88 @@
+## Copyright (C) 2010 Andrew Kelly, IPS Radio & Space Services
+##
+## This program is free software; you can redistribute it and/or modify
+## it under the terms of the GNU General Public License as published by
+## the Free Software Foundation; either version 3 of the License, or
+## (at your option) any later version.
+##
+## This program is distributed in the hope that it will be useful,
+## but WITHOUT ANY WARRANTY; without even the implied warranty of
+## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+## GNU General Public License for more details.
+##
+## You should have received a copy of the GNU General Public License
+## along with this program; If not, see <http://www.gnu.org/licenses/>.
+
+## -*- texinfo -*-
+## @deftypefn {Function File} {@var{fcc} = } fchcode (@var{bound})
+## Determine the Freeman chain code for a boundary.
+##
+## @code{fchcode} computes the Freeman chain code for the @var{n}-connected
+## boundary @var{bound}. @var{n} must be either 8 or 4.
+##
+## @var{bound} is a K-by-2 matrix containing the row/column coordinates of points
+## on the boundary. Optionally, the first point can be repeated as the last point,
+## resulting in a (K+1)-by-2 matrix.
+##
+## @var{fcc} is a structure containing the following elements.
+##
+## @example
+## x0y0 = Row/column coordinates where the code starts (1-by-2)
+## fcc = Freeman chain code (1-by-K)
+## diff = First difference of fcc (1-by-K)
+## @end example
+##
+## The code uses the following directions.
+##
+## @example
+## 3 2 1
+## 4 . 0
+## 5 6 7
+## @end example
+##
+## @seealso{bwboundaries}
+## @end deftypefn
+
+function fcc = fchcode (bound)
+
+ # ensure the boundary start and end points are the same
+ if (!isempty (bound) && !isequal (bound (1, :), bound (end, :)))
+ bound = [bound; bound(1, :)];
+ endif
+
+ # number of boundary points
+ n = max (0, rows (bound)-1);
+
+ # structure in which to return results
+ fcc = struct (\
+ 'x0y0', zeros (1, n), \
+ 'fcc', zeros (1, n), \
+ 'diff', zeros (1, n) \
+ );
+
+ # an empty boundary?
+ if (isempty (bound))
+ return;
+ endif
+
+ # direction map
+ dir = [3, 2, 1; \
+ 4, NaN, 0; \
+ 5, 6, 7];
+
+ # coordinates
+ ROW = 1;
+ COL = 2;
+
+ # direction changes as row/column indexes into DIR
+ ch = 2 + diff (bound, 1, ROW);
+
+ # starting point
+ fcc.x0y0 = bound (1, :);
+
+ # chain code
+ fcc.fcc = dir (sub2ind (size (dir), ch (:, ROW), ch (:, COL)))';
+
+ # chain code difference
+ fcc.diff = mod (diff ([fcc.fcc, fcc.fcc(1)]), 8);
+endfunction
Modified: trunk/octave-forge/main/image/src/Makefile
===================================================================
--- trunk/octave-forge/main/image/src/Makefile 2010-12-22 08:15:40 UTC (rev 8033)
+++ trunk/octave-forge/main/image/src/Makefile 2010-12-22 23:02:14 UTC (rev 8034)
@@ -1,5 +1,5 @@
all: __spatial_filtering__.oct __bilateral__.oct __custom_gaussian_smoothing__.oct \
- __imboundary__.oct bwlabel.oct bwfill.oct rotate_scale.oct hough_line.oct \
+ __boundary__.oct bwlabel.oct bwfill.oct rotate_scale.oct hough_line.oct \
graycomatrix.oct deriche.oct __bwdist.oct nonmax_supress.oct
%.oct: %.cc
Added: trunk/octave-forge/main/image/src/__boundary__.cc
===================================================================
--- trunk/octave-forge/main/image/src/__boundary__.cc (rev 0)
+++ trunk/octave-forge/main/image/src/__boundary__.cc 2010-12-22 23:02:14 UTC (rev 8034)
@@ -0,0 +1,181 @@
+/*
+Copyright (C) 2010 Andrew Kelly, IPS Radio & Space Services
+
+This program is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 3 of the License, or
+(at your option) any later version.
+
+This program is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with this program; If not, see <http://www.gnu.org/licenses/>.
+*/
+
+/**
+ * Oct-file to trace the boundary of an object in a binary image.
+ *
+ * b = boundary(region, conn=8)
+ */
+#include <octave/oct.h>
+
+using namespace std;
+
+DEFUN_DLD(__boundary__, args, nargout,
+"-*- texinfo -*-\n\
+@deftypefn {Function File} {@var{b} = } boundary(@var{region})\n\
+@deftypefnx {Function File} {@var{b} = } boundary(@var{region}, @var{conn})\n\
+Trace the boundary of an object in a binary image.\n\
+\n\
+@code{boundary} computes the exterior clockwise boundary of the single \
+@var{conn}-connected object represented by the non-zero pixels \
+of @var{region}. It uses an algorithm based on Moore-neighbour tracing.\n\
+\n\
+@var{conn} can be either 8 (the default) or 4.\n\
+\n\
+@var{b} is an N-by-2 matrix containing the row/column coordinates of points \
+on the boundary. The first boundary point is the first non-zero \
+pixel of @var{region}, as determined by @code{find}. The last boundary \
+point is the same as the first.\n\
+@seealso{boundaries, bwlabel, find}\n\
+@end deftypefn")
+{
+ octave_value_list retval;
+
+ enum { ROW, COL };
+
+ // check number of arguments
+ const int nargin = args.length ();
+ if (nargin > 2 || nargout != 1)
+ {
+ error ("__boundary__: wrong number of input arguments");
+ return retval;
+ }
+
+ // extract arguments
+ const boolMatrix unpadded = args (0).bool_matrix_value ();
+ const int conn = (nargin > 1)
+ ? (int) args (1).scalar_value ()
+ : 8;
+
+ if (error_state)
+ {
+ error ("__boundary__: internal error");
+ return retval;
+ }
+
+ // pad to avoid boundary issues
+ int rows = unpadded.rows ();
+ int cols = unpadded.columns ();
+ boolMatrix region (rows + 2, cols + 2, false);
+ for (int r = 0; r < rows; r++)
+ for (int c = 0; c < cols; c++)
+ region.elem (r+1, c+1) = unpadded (r, c);
+
+ // the padded size
+ rows += 2;
+ cols += 2;
+
+ // find the (first two) true pixels, if any
+ std::vector <int> pixels;
+ for (int i = 0; pixels.size () < 2 && i < region.numel (); ++i)
+ if (region.elem (i))
+ pixels.push_back (i);
+
+ if (pixels.empty ())
+ return retval;
+
+ // the starting boundary point
+ const int start = pixels [0];
+ std::vector <int> bound;
+ bound.push_back (start);
+
+ // is this the only point?
+ if (pixels.size () == 1)
+ bound.push_back (start);
+
+ // otherwise, find the boundary by tracing the Moore neighbourhood of its pixels
+ //
+ // 8-connected: 7 0 1 4-connected: 0
+ // 6 . 2 3 . 1
+ // 5 4 3 2
+ else
+ {
+ // relative row/column positions
+ static const int row8 [] = {-1, -1, 0, 1, 1, 1, 0, -1};
+ static const int col8 [] = { 0, 1, 1, 1, 0, -1, -1, -1};
+ static const int row4 [] = {-1, 0, 1, 0 };
+ static const int col4 [] = { 0, 1, 0, -1 };
+ const int* mr = (conn == 4) ? row4 : row8;
+ const int* mc = (conn == 4) ? col4 : col8;
+
+ // next after backing-up
+ static const int back8 [] = {7, 7, 1, 1, 3, 3, 5, 5};
+ static const int back4 [] = {3, 0, 1, 2};
+ const int* mBack = (conn == 4) ? back4 : back8;
+
+ // relative indexes into the region for the Moore neighbourhood pixels
+ int mi [conn];
+ for (int i = 0; i < conn; ++i)
+ mi[i] = mr[i] + (rows * mc [i]);
+
+ // next neighbourhood pixel
+ static const int next8 [] = {1, 2, 3, 4, 5, 6, 7, 0};
+ static const int next4 [] = {1, 2, 3, 0};
+ const int* mNext = (conn == 4) ? next4 : next8;
+
+ // the final boundary point to be visited
+ int finish = 0;
+ for (int i = 0; i < conn; ++i)
+ if (region.elem(start + mi [i]))
+ finish = start + mi [i];
+
+ // look for the next boundary point, starting at the next neighbour
+ int bp = start;
+ int mCurrent = mNext [0];
+ bool done = false;
+ while (!done)
+ {
+ // next neighbour
+ int cp = bp + mi [mCurrent];
+
+ // if this pixel is false, try the next one
+ if (!region.elem (cp))
+ {
+ mCurrent = mNext [mCurrent];
+ }
+ // otherwise, we have another boundary point
+ else
+ {
+ bound.push_back (cp);
+
+ // either we're back at the start for the last time
+ if (bp == finish && cp == start)
+ {
+ done = true;
+ }
+ // or we step back to where we came in from, and continue
+ else
+ {
+ bp = cp;
+ mCurrent = mBack [mCurrent];
+ }
+ }
+ }
+ }
+
+ // convert boundary points to row/column coordinates
+ Matrix b (bound.size (), 2);
+ for (unsigned int i = 0; i < bound.size (); i++)
+ {
+ const int point = bound [i];
+ b (i, ROW) = point % rows;
+ b (i, COL) = point / rows;
+ }
+
+ retval.append (b);
+ return retval;
+}
Deleted: trunk/octave-forge/main/image/src/__imboundary__.cc
===================================================================
--- trunk/octave-forge/main/image/src/__imboundary__.cc 2010-12-22 08:15:40 UTC (rev 8033)
+++ trunk/octave-forge/main/image/src/__imboundary__.cc 2010-12-22 23:02:14 UTC (rev 8034)
@@ -1,162 +0,0 @@
-// Copyright (C) 2010 Soren Hauberg
-//
-// This program is free software; you can redistribute it and/or
-// modify it under the terms of the GNU General Public License
-// as published by the Free Software Foundation; either version 3
-// of the License, or (at your option) any later version.
-//
-// This program is distributed in the hope that it will be useful, but
-// WITHOUT ANY WARRANTY; without even the implied warranty of
-// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
-// General Public License for more details.
-//
-// You should have received a copy of the GNU General Public License
-// along with this program; if not, see <http://www.gnu.org/licenses/>.
-
-#include <octave/oct.h>
-
-inline int iseven (const int a)
-{
- if ((a % 2) == 0)
- return 1;
- else
- return 0;
-}
-
-Matrix trace_boundary (const boolMatrix &im, const int N, const octave_idx_type r,
- const octave_idx_type c)
-{
- // Get size information
- const octave_idx_type rows = im.rows ();
- const octave_idx_type cols = im.columns ();
-
- // Create list of points
- typedef std::pair<int, int> point;
- std::list <point> P;
-
- // Add first point
- const point P0 (r, c); // first list element
- point P1 (-1, -1); // second list element
- point Pn1 (-1, -1); // second last list element
- P.push_back (P0);
- int len = 1;
-
- // Create a simple lookup table that translates 'dir' to a row and column offset
- const int dir2row4 [] = { 0, -1, 0, +1};
- const int dir2col4 [] = {+1, 0, -1, 0};
- const int dir2row8 [] = { 0, -1, -1, -1, 0, +1, +1, +1};
- const int dir2col8 [] = {+1, +1, 0, -1, -1, -1, 0, +1};
-
- // Start searching from there...
- int dir = N - 1;
- int curr_dir = dir; //(N == 4) ? (dir + 3) % N : (dir + 6 + iseven (dir)) % N;
- int delta_r, delta_c;
- octave_idx_type row = r, col = c;
- while (true)
-// for (int z = 0; z < 1000; z++)
- {
- OCTAVE_QUIT;
-
- // Get next search direction
- if (N == 4)
- {
- //curr_dir = (dir + 3) % N;
- delta_r = dir2row4 [curr_dir];
- delta_c = dir2col4 [curr_dir];
- }
- else
- {
- //curr_dir = (dir + 6 + iseven (dir)) % N;
- delta_r = dir2row8 [curr_dir];
- delta_c = dir2col8 [curr_dir];
- }
-
- // Is a pixel available at the search direction
- const octave_idx_type curr_r = row + delta_r;
- const octave_idx_type curr_c = col + delta_c;
-/* std::cerr << " curr_r = " << curr_r
- << " curr_c = " << curr_c
- << " curr_dir = " << curr_dir
- << " row = " << row
- << " colr = " << col
- << std::endl;
-*/
- if (curr_r >= 0 && curr_r < rows && curr_c >= 0 && curr_c < cols && im (curr_r, curr_c))
- {
- // Update 'dir'
- dir = curr_dir;
- curr_dir = (N == 4) ? (dir + 3) % N : (dir + 6 + iseven (dir)) % N;
-
- // Add point to list
- const point Pn (curr_r, curr_c);
- P.push_back (Pn);
- len ++;
-
- // Update 'row' and 'col'
- row = curr_r;
- col = curr_c;
-
- // Save the second element of P for the stop criteria
- if (len == 2)
- {
- P1.first = curr_r;
- P1.second = curr_c;
- }
-
- // Should we stop?
- if (Pn.first == P1.first && Pn.second == P1.second &&
- Pn1.first == P0.first && Pn1.second == P0.second)
- break;
-
- // Save current point for next time
- Pn1 = Pn;
- }
- else
- {
- // Update search direction
- curr_dir = (curr_dir+1) % N;
- }
- } // end while
-
- // Copy data to output matrix
- Matrix out (len-1, 2);
- std::list<point>::const_iterator iter = P.begin ();
- for (int idx = 0; idx < len-2; iter++, idx++)
- {
- out (idx, 0) = iter->second + 1;
- out (idx, 1) = iter->first + 1;
- }
- out (len-2, 0) = P0.second + 1;
- out (len-2, 1) = P0.first + 1;
-
- return out;
-}
-
-DEFUN_DLD(__imboundary__, args, , "\
--*- texinfo -*-\n\
-@deftypefn {Function File} __imboundary__ (@var{bw}, @var{N}, @var{r}, @var{c})\n\
-Undocumented internal function.\n\
-User interface is available in @code{bwboundaries}.\n\
-@end deftypefn\n\
-")
-{
- // Handle input
- octave_value_list retval;
- if (args.length () != 4) {
- error ("__imboundary__: not enough input arguments");
- return retval;
- }
-
- const boolMatrix im = args (0).bool_matrix_value ();
- const int N = (int) args (1).scalar_value ();
- const octave_idx_type r = (octave_idx_type) args (2).scalar_value () - 1;
- const octave_idx_type c = (octave_idx_type) args (3).scalar_value () - 1;
- if (error_state || (N != 4)) // && N != 8))
- error ("__imboundary__: invalid input arguments");
- else
- {
- Matrix out = trace_boundary (im, N, r, c);
- retval.append (out);
- }
- return retval;
-}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
