From: <st...@us...> - 2009-04-18 12:20:56
|
Revision: 5720 http://octave.svn.sourceforge.net/octave/?rev=5720&view=rev Author: stegu Date: 2009-04-18 12:20:45 +0000 (Sat, 18 Apr 2009) Log Message: ----------- Complete rewrite of __bwdist.cc Modified Paths: -------------- trunk/octave-forge/main/image/src/__bwdist.cc Added Paths: ----------- trunk/octave-forge/main/image/src/edtfunc.c Modified: trunk/octave-forge/main/image/src/__bwdist.cc =================================================================== --- trunk/octave-forge/main/image/src/__bwdist.cc 2009-04-18 12:19:29 UTC (rev 5719) +++ trunk/octave-forge/main/image/src/__bwdist.cc 2009-04-18 12:20:45 UTC (rev 5720) @@ -1,163 +1,192 @@ +// bwdist.cc - OCT file, implements the BWDIST function +// Depends on "edtfunc.c" for the actual computations /* -Copyright (C) 2006 Pedro Felzenszwalb -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 2 of the License, or -(at your option) any later version. +Copyright (C) 2009 Stefan Gustavson (ste...@gm...) -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. +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/>. +along with Octave; see the file COPYING. If not, see +<http://www.gnu.org/licenses/>. + */ -/* - * Remark by Søren Hauberg, december 28th 2006. - * - * This code was mainly written by Pedro Felzenszwalb and published - * on http://people.cs.uchicago.edu/~pff/dt/ - * Pedro kindly released his code under the GPL and I ported it to - * Octave. - */ - #include <octave/oct.h> -#define INF 1E20 -template <class T> -inline T square(const T &x) { return x*x; }; +#ifdef __cplusplus +extern "C" +{ +#endif -/* dt of 1d function using squared distance */ -static float* dt (float *f, int n) +#define DIST_EUCLIDEAN(x,y) ((int)(x)*(x) + (y)*(y)) +#define MAX(x,y) ((x)>(y) ? (x) : (y)) +#define DIST_CHESSBOARD(x,y) (MAX(abs(x), abs(y))) +#define DIST_CITYBLOCK(x,y) (abs(x) + abs(y)) +#define SQRT2_1 0.4142136536 +#define DIST_QUASI_EUCLIDEAN(x,y) (abs(x)>abs(y) ? (abs(x) + SQRT2_1 * abs(y)) : (SQRT2_1 * abs(x) + abs(y))) + +#define DIST(x,y) DIST_EUCLIDEAN(x,y) +#define FUNCNAME euclidean +#include "edtfunc.c" +#undef DIST +#undef FUNCNAME + +#define DIST(x,y) DIST_CHESSBOARD(x,y) +#define FUNCNAME chessboard +#include "edtfunc.c" +#undef DIST +#undef FUNCNAME + +#define DIST(x,y) DIST_CITYBLOCK(x,y) +#define FUNCNAME cityblock +#include "edtfunc.c" +#undef DIST +#undef FUNCNAME + +#define DIST(x,y) DIST_QUASI_EUCLIDEAN(x,y) +#define FUNCNAME quasi_euclidean +#include "edtfunc.c" +#undef DIST +#undef FUNCNAME + +#ifdef __cplusplus +} /* end extern "C" */ +#endif + +DEFUN_DLD (bwdist, args, nargout, +"-*- texinfo -*-\n\ +@deftypefn {Function File} {@var{D} =} bwdist(@var{bw})\n\ +Computes the distance transform of the image @var{bw}.\n\ +@var{bw} should be a binary 2D array, either a Boolean array or a\n\ +numeric array containing only the values 0 and 1.\n\ +The return value @var{D} is a double matrix of the same size as @var{bw}.\n\ +Elements with value 0 are considered background pixels, elements\n\ +with value 1 are considered object pixels. The return value\n\ +for each background pixel is the distance (according to the chosen\n\ +metric) to the closest object pixel. For each object pixel the\n\ +return value is 0.\n\ +\n\ +@deftypefnx{Function File} {@var{D} =} bwdist(@var{bw}, @var{method})\n\ +\n\ +@var{method} is a string to choose the distance metric. Currently\n\ +available metrics are 'euclidean', 'chessboard', 'cityblock' and\n\ +'quasi-euclidean', which may each be abbreviated\n\ +to any string starting with 'e', 'ch', 'ci' and 'q', respectively.\n\ +If @var{method} is not specified, 'euclidean' is the default.\n\ +\n\ +@deftypefnx {Function File} {[@var{D},@var{C}] =} bwdist(@var{bw}, @var{method})\n\ +\n\ +If a second output argument is given, the linear index for the\n\ +closest object pixel is returned for each pixel. (For object\n\ +pixels, the index points to the pixel itself.) The return value C\n\ +is a matrix the same size as @var{bw}.\n\n\ +@end deftypefn") { - float *d = new float[n]; - int *v = new int[n]; - float *z = new float[n+1]; - int k = 0; - v[0] = 0; - z[0] = -INF; - z[1] = +INF; - for (int q = 1; q <= n-1; q++) - { - float s = ((f[q] + square (q)) - (f[v[k]] + square (v[k])))/(2*q-2*v[k]); - while (s <= z[k]) - { - k--; - s = ((f[q] + square (q)) - (f[v[k]] + square (v[k])))/(2*q-2*v[k]); - } - k++; - v[k] = q; - z[k] = s; - z[k+1] = +INF; + const int nargin = args.length(); + octave_value_list retval; + + /* Check for proper number of input and output arguments */ + if ((nargin < 1) || (nargin>2)) { + error ("bwdist accepts only one or two input parameters."); + } + else if (nargout > 2) { + error ("bwdist returns at most 2 output parameters."); + } + else { + /* Make sure input is a matrix */ + const Matrix bw = args(0).matrix_value(); + if (error_state) { + error ("bwdist input argument must be a matrix"); + return retval; } + /* Warn if input is not a binary image */ + if(bw.any_element_not_one_or_zero()) { + warning ("bwdist input contains values other than 1 and 0."); + } - k = 0; - for (int q = 0; q <= n-1; q++) - { - while (z[k+1] < q) - k++; - d[q] = square (q-v[k]) + f[v[k]]; + /* Everything seems to be OK to proceed */ + dim_vector dims = bw.dims(); + int rows = dims(0); + int cols = dims(1); + int caseMethod = 0; // Default 0 means Euclidean + if(nargin > 1) { + charMatrix method = args(1).char_matrix_value(); + if(method(0) == 'e') caseMethod = 0; // Euclidean; + else if (method(0) == 'c') { + if(method(1) == 'h') caseMethod = 1; // chessboard + else if(method(1) == 'i') caseMethod = 2; // cityblock + } + else if(method(0) == 'q') caseMethod = 3; // quasi-Euclidean + else { + warning ("unknown metric, using 'euclidean'"); + caseMethod = 0; + } } - delete [] v; - delete [] z; - return d; -} + if (!error_state) { + /* Allocate two arrays for temporary output values */ + OCTAVE_LOCAL_BUFFER (short, xdist, dims.numel()); + OCTAVE_LOCAL_BUFFER (short, ydist, dims.numel()); -/* dt of 2d function using squared distance */ -static void dt (NDArray &im) -{ - const int width = im.dim1 (); - const int height = im.dim2 (); - float *f = new float[std::max(width,height)]; + /* Create final output array */ + Matrix D (rows, cols); - // transform along columns - for (int x = 0; x < width; x++) - { - for (int y = 0; y < height; y++) - { - f[y] = im (x, y); - } - float *d = dt (f, height); - for (int y = 0; y < height; y++) - { - im (x, y) = d[y]; - } - delete [] d; - } + /* Call the appropriate C subroutine and compute output */ + switch(caseMethod) { - // transform along rows - for (int y = 0; y < height; y++) - { - for (int x = 0; x < width; x++) - { - f[x] = im (x, y); - } - float *d = dt (f, width); - for (int x = 0; x < width; x++) - { - im (x, y) = d[x]; - } - delete [] d; - } + case 1: + chessboard(bw, rows, cols, xdist, ydist); + for(int i=0; i<rows*cols; i++) { + D(i) = DIST_CHESSBOARD(xdist[i], ydist[i]); + } + break; - delete [] f; -} + case 2: + cityblock(bw, rows, cols, xdist, ydist); + for(int i=0; i<rows*cols; i++) { + D(i) = DIST_CITYBLOCK(xdist[i], ydist[i]); + } + break; + case 3: + quasi_euclidean(bw, rows, cols, xdist, ydist); + for(int i=0; i<rows*cols; i++) { + D(i) = DIST_QUASI_EUCLIDEAN(xdist[i], ydist[i]); + } + break; -/* dt of binary image using squared distance */ -void dt (const boolNDArray &im, NDArray &out) -{ - const int width = im.dim1 (); - const int height = im.dim2 (); + case 0: + default: + euclidean(bw, rows, cols, xdist, ydist); + /* Remember sqrt() for the final output */ + for(int i=0; i<rows*cols; i++) { + D(i) = sqrt((double)DIST_EUCLIDEAN(xdist[i], ydist[i])); + } + break; + } - for (int y = 0; y < height; y++) - { - for (int x = 0; x < width; x++) - { - if (im (x, y)) - out (x, y) = 0; - else - out (x, y) = INF; - } - } + retval(0) = D; - dt (out); -} - -DEFUN_DLD (__bwdist, args, nargout, "\ --*- texinfo -*-\n\ -@deftypefn {Function File} __bwdist (@var{bw})\n\ -Computes the Euclidian Distance Transform for a binary image @var{bw}.\n\ -You should not call this function directly, instead call 'bwdist'.\n\ -@seealso{bwdist}\n\ -@end deftypefn\n\ -") -{ - octave_value_list retval; - - const boolNDArray bw = args(0).bool_array_value (); - if (error_state) - { - error ("__bwdist: input must be a boolean matrix"); - return retval; + if(nargout > 1) { + /* Create a second output array */ + Matrix C (rows, cols); + /* Compute optional 'index to closest object pixel' */ + for(int i=0; i<rows*cols; i++) { + C (i) = i+1 - xdist[i] - ydist[i]*rows; + } + retval(1) = C; + } } - - const dim_vector dims = bw.dims (); - if (dims.length () != 2) - { - error ("__bwdist: currently only binary images are supported"); - return retval; - } - - NDArray out (dims); - - dt (bw, out); - - retval.append (out); + } return retval; } Added: trunk/octave-forge/main/image/src/edtfunc.c =================================================================== --- trunk/octave-forge/main/image/src/edtfunc.c (rev 0) +++ trunk/octave-forge/main/image/src/edtfunc.c 2009-04-18 12:20:45 UTC (rev 5720) @@ -0,0 +1,380 @@ +// edtfunc.c - Euclidean distance transform of a binary image +/* + +Copyright (C) 2009 Stefan Gustavson (ste...@gm...) + +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 Octave; see the file COPYING. If not, see +<http://www.gnu.org/licenses/>. + +*/ + +/* + * This is a sweep-and-update Euclidean distance transform of + * a binary image. All positive pixels are considered object + * pixels, zero or negative pixels are treated as background. + * + * By Stefan Gustavson (ste...@gm...). + * + * Originally written in 1994, based on paper-only descriptions + * of the SSED8 algorithm, invented by Per-Erik Danielsson + * and improved by Ingemar Ragnemalm. This is a classic algorithm + * with roots in the 1980s, still very good for the 2D case. + * + * Updated in 2004 to treat pixels at image edges correctly, + * and to improve code readability. + * + * Edited in 2009 to form the foundation for Octave BWDIST: + * added #define-configurable distance measure and function name + * + */ + +#ifndef DIST +#define DIST(x,y) ((int)(x) * (x) + (y) * (y)) +#endif + +#ifndef FUNCNAME +#define FUNCNAME edt +#endif + +void FUNCNAME(const Matrix &img, int w, int h, short *distx, short *disty) +{ + int x, y, i; + int offset_u, offset_ur, offset_r, offset_rd, + offset_d, offset_dl, offset_l, offset_lu; + double olddist2, newdist2, newdistx, newdisty; + int changed; + + /* Initialize index offsets for the current image width */ + offset_u = -w; + offset_ur = -w+1; + offset_r = 1; + offset_rd = w+1; + offset_d = w; + offset_dl = w-1; + offset_l = -1; + offset_lu = -w-1; + + /* Initialize the distance images to be all large values */ + for(i=0; i<w*h; i++) + if(img(i) <= 0.0) + { + distx[i] = 32000; // Large but still representable in a short, and + disty[i] = 32000; // 32000^2 + 32000^2 does not overflow an int + } + else + { + distx[i] = 0; + disty[i] = 0; + } + + /* Perform the transformation */ + do + { + changed = 0; + + /* Scan rows, except first row */ + for(y=1; y<h; y++) + { + + /* move index to leftmost pixel of current row */ + i = y*w; + + /* scan right, propagate distances from above & left */ + + /* Leftmost pixel is special, has no left neighbors */ + olddist2 = DIST(distx[i], disty[i]); + if(olddist2 > 0) // If not already zero distance + { + newdistx = distx[i+offset_u]; + newdisty = disty[i+offset_u]+1; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + olddist2=newdist2; + changed = 1; + } + + newdistx = distx[i+offset_ur]-1; + newdisty = disty[i+offset_ur]+1; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + changed = 1; + } + } + i++; + + /* Middle pixels have all neighbors */ + for(x=2; x<w-1; x++, i++) + { + olddist2 = DIST(distx[i], disty[i]); + if(olddist2 == 0) continue; // Already zero distance + + newdistx = distx[i+offset_l]+1; + newdisty = disty[i+offset_l]; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + olddist2=newdist2; + changed = 1; + } + + newdistx = distx[i+offset_lu]+1; + newdisty = disty[i+offset_lu]+1; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + olddist2=newdist2; + changed = 1; + } + + newdistx = distx[i+offset_u]; + newdisty = disty[i+offset_u]+1; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + olddist2=newdist2; + changed = 1; + } + + newdistx = distx[i+offset_ur]-1; + newdisty = disty[i+offset_ur]+1; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + changed = 1; + } + } + + /* Rightmost pixel of row is special, has no right neighbors */ + i++; + olddist2 = DIST(distx[i], disty[i]); + if(olddist2 > 0) // If not already zero distance + { + newdistx = distx[i+offset_l]+1; + newdisty = disty[i+offset_l]; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + olddist2=newdist2; + changed = 1; + } + + newdistx = distx[i+offset_lu]+1; + newdisty = disty[i+offset_lu]+1; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + olddist2=newdist2; + changed = 1; + } + + newdistx = distx[i+offset_u]; + newdisty = disty[i+offset_u]+1; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + olddist2=newdist2; + changed = 1; + } + } + + /* Move index to second rightmost pixel of current row. */ + /* Rightmost pixel is skipped, it has no right neighbor. */ + i = y*w + w-2; + + /* scan left, propagate distance from right */ + for(x=w-2; x>=0; x--, i--) + { + olddist2 = DIST(distx[i], disty[i]); + if(olddist2 == 0) continue; // Already zero distance + + newdistx = distx[i+offset_r]-1; + newdisty = disty[i+offset_r]; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + changed = 1; + } + } + } + + /* Scan rows in reverse order, except last row */ + for(y=h-2; y>=0; y--) + { + /* move index to rightmost pixel of current row */ + i = y*w + w-1; + + /* Scan left, propagate distances from below & right */ + + /* Rightmost pixel is special, has no right neighbors */ + olddist2 = DIST(distx[i], disty[i]); + if(olddist2 > 0) // If not already zero distance + { + newdistx = distx[i+offset_d]; + newdisty = disty[i+offset_d]-1; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + olddist2=newdist2; + changed = 1; + } + + newdistx = distx[i+offset_dl]+1; + newdisty = disty[i+offset_dl]-1; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + changed = 1; + } + } + i--; + + /* Middle pixels have all neighbors */ + for(x=w-2; x>0; x--, i--) + { + olddist2 = DIST(distx[i], disty[i]); + if(olddist2 == 0) continue; // Already zero distance + + newdistx = distx[i+offset_r]-1; + newdisty = disty[i+offset_r]; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + olddist2=newdist2; + changed = 1; + } + + newdistx = distx[i+offset_rd]-1; + newdisty = disty[i+offset_rd]-1; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + olddist2=newdist2; + changed = 1; + } + + newdistx = distx[i+offset_d]; + newdisty = disty[i+offset_d]-1; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + olddist2=newdist2; + changed = 1; + } + + newdistx = distx[i+offset_dl]+1; + newdisty = disty[i+offset_dl]-1; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + changed = 1; + } + } + /* Leftmost pixel is special, has no left neighbors */ + olddist2 = DIST(distx[i], disty[i]); + if(olddist2 > 0) // If not already zero distance + { + newdistx = distx[i+offset_r]-1; + newdisty = disty[i+offset_r]; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + olddist2=newdist2; + changed = 1; + } + + newdistx = distx[i+offset_rd]-1; + newdisty = disty[i+offset_rd]-1; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + olddist2=newdist2; + changed = 1; + } + + newdistx = distx[i+offset_d]; + newdisty = disty[i+offset_d]-1; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + olddist2=newdist2; + changed = 1; + } + } + + /* Move index to second leftmost pixel of current row. */ + /* Leftmost pixel is skipped, it has no left neighbor. */ + i = y*w + 1; + for(x=1; x<w; x++, i++) + { + /* scan right, propagate distance from left */ + olddist2 = DIST(distx[i], disty[i]); + if(olddist2 == 0) continue; // Already zero distance + + newdistx = distx[i+offset_l]+1; + newdisty = disty[i+offset_l]; + newdist2 = DIST(newdistx, newdisty); + if(newdist2 < olddist2) + { + distx[i]=newdistx; + disty[i]=newdisty; + changed = 1; + } + } + } + } + while(changed); // Sweep until no more updates are made + + /* The transformation is completed. */ + +} Property changes on: trunk/octave-forge/main/image/src/edtfunc.c ___________________________________________________________________ Added: svn:executable + * This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <ha...@us...> - 2010-03-06 08:52:26
|
Revision: 7001 http://octave.svn.sourceforge.net/octave/?rev=7001&view=rev Author: hauberg Date: 2010-03-06 08:52:20 +0000 (Sat, 06 Mar 2010) Log Message: ----------- Remove JPEG and PNG functions and as a result simplify build system Modified Paths: -------------- trunk/octave-forge/main/image/src/Makefile Removed Paths: ------------- trunk/octave-forge/main/image/src/Makeconf.in trunk/octave-forge/main/image/src/autogen.sh trunk/octave-forge/main/image/src/configure.base trunk/octave-forge/main/image/src/jpgread.cc trunk/octave-forge/main/image/src/jpgwrite.cc trunk/octave-forge/main/image/src/pngcanvas.h trunk/octave-forge/main/image/src/pngread.cc trunk/octave-forge/main/image/src/pngwrite.cc Deleted: trunk/octave-forge/main/image/src/Makeconf.in =================================================================== --- trunk/octave-forge/main/image/src/Makeconf.in 2010-03-05 23:45:42 UTC (rev 7000) +++ trunk/octave-forge/main/image/src/Makeconf.in 2010-03-06 08:52:20 UTC (rev 7001) @@ -1,14 +0,0 @@ - -## Makeconf is automatically generated from Makeconf.base and Makeconf.add -## in the various subdirectories. To regenerate, use ./autogen.sh to -## create a new ./Makeconf.in, then use ./configure to generate a new -## Makeconf. - -@DEFHAVE_JPEG@ -@DEFHAVE_PNG@ -MKOCTFILE=@MKOCTFILE@ - -%.o: %.c ; $(MKOCTFILE) -c $< -%.o: %.f ; $(MKOCTFILE) -c $< -%.o: %.cc ; $(MKOCTFILE) -c $< -%.oct: %.cc ; $(MKOCTFILE) $< Modified: trunk/octave-forge/main/image/src/Makefile =================================================================== --- trunk/octave-forge/main/image/src/Makefile 2010-03-05 23:45:42 UTC (rev 7000) +++ trunk/octave-forge/main/image/src/Makefile 2010-03-06 08:52:20 UTC (rev 7001) @@ -1,28 +1,9 @@ -sinclude Makeconf - -ifdef HAVE_JPEG - JPEG=jpgwrite.oct jpgread.oct -endif - -ifdef HAVE_PNG - PNG=pngread.oct pngwrite.oct -endif - all: __spatial_filtering__.oct __bilateral__.oct __custom_gaussian_smoothing__.oct \ __imboundary__.oct bwlabel.oct bwfill.oct rotate_scale.oct hough_line.oct \ - graycomatrix.oct deriche.oct __bwdist.oct nonmax_supress.oct \ - $(JPEG) $(PNG) + graycomatrix.oct deriche.oct __bwdist.oct nonmax_supress.oct -jpgread.oct: jpgread.cc - $(MKOCTFILE) $< -ljpeg +%.oct: %.cc + mkoctfile -Wall $< -jpgwrite.oct: jpgwrite.cc - $(MKOCTFILE) $< -ljpeg - -pngread.oct: pngread.cc - $(MKOCTFILE) $< -lpng - -pngwrite.oct: pngwrite.cc - $(MKOCTFILE) $< -lpng - -clean: ; -$(RM) *.o octave-core core *.oct *~ +clean: + rm -f *.o octave-core core *.oct *~ Deleted: trunk/octave-forge/main/image/src/autogen.sh =================================================================== --- trunk/octave-forge/main/image/src/autogen.sh 2010-03-05 23:45:42 UTC (rev 7000) +++ trunk/octave-forge/main/image/src/autogen.sh 2010-03-06 08:52:20 UTC (rev 7001) @@ -1,27 +0,0 @@ -#! /bin/sh - -## Generate ./configure -rm -f configure.in -echo "dnl --- DO NOT EDIT --- Automatically generated by autogen.sh" > configure.in -cat configure.base >> configure.in -cat <<EOF >> configure.in - AC_OUTPUT(\$CONFIGURE_OUTPUTS) - dnl XXX FIXME XXX chmod is not in autoconf's list of portable functions - - echo " " - echo " \"\\\$prefix\" is \$prefix" - echo " \"\\\$exec_prefix\" is \$exec_prefix" - AC_MSG_RESULT([\$STATUS_MSG - -find . -name NOINSTALL -print # shows which toolboxes won't be installed -]) -EOF - -autoconf configure.in > configure.tmp -if [ diff configure.tmp configure > /dev/null 2>&1 ]; then - rm -f configure.tmp; -else - mv -f configure.tmp configure - chmod 0755 configure -fi -rm -f configure.in Deleted: trunk/octave-forge/main/image/src/configure.base =================================================================== --- trunk/octave-forge/main/image/src/configure.base 2010-03-05 23:45:42 UTC (rev 7000) +++ trunk/octave-forge/main/image/src/configure.base 2010-03-06 08:52:20 UTC (rev 7001) @@ -1,64 +0,0 @@ -dnl The configure script is generated by autogen.sh from configure.base -dnl and the various configure.add files in the source tree. Edit -dnl configure.base and reprocess rather than modifying ./configure. - -dnl autoconf 2.13 certainly doesn't work! What is the minimum requirement? -AC_PREREQ(2.2) - -AC_INIT(configure.base) - -MKOCTFILE=mkoctfile -AC_SUBST(MKOCTFILE) - -dnl Strip on windows, don't strip on Mac OS/X or IRIX -dnl For the rest, you can force strip using MKOCTFILE="mkoctfile -s" -dnl or avoid strip using STRIP=: before ./configure -case "$canonical_host_type" in - powerpc-apple-darwin*|*-sgi-*) - STRIP=: - ;; - *-cygwin-*|*-mingw-*) - MKOCTFILE="$MKOCTFILE -s" - ;; -esac - -dnl Define the following macro: -dnl OF_CHECK_LIB(lib,fn,true,false,helpers) -dnl This is just like AC_CHECK_LIB, but it doesn't update LIBS -AC_DEFUN([OF_CHECK_LIB], -[save_LIBS="$LIBS" -AC_CHECK_LIB($1,$2,$3,$4,$5) -LIBS="$save_LIBS" -]) - -AC_DEFINE(have_jpeg) -AC_CHECK_HEADER(jpeglib.h, have_jpeg=yes, have_jpeg=no) -if test $have_jpeg = yes ; then - OF_CHECK_LIB(jpeg, jpeg_std_error, have_jpeg=yes, have_jpeg=no) - if test $have_jpeg = no ; then - IMAGESTATUS="libjpeg not found" - else - IMAGESTATUS="jpeg" - AC_SUBST(DEFHAVE_JPEG) - DEFHAVE_JPEG="HAVE_JPEG=1" - fi -else - IMAGESTATUS="jpeglib.h not found" -fi - -AC_DEFINE(have_png) -AC_CHECK_HEADER(png.h, have_png=yes, have_png=no) -if test $have_png = yes ; then - OF_CHECK_LIB(png, png_set_sig_bytes, have_png=yes, have_png=no) - if test $have_png = no ; then - IMAGESTATUS="$IMAGESTATUS, libpng not found" - else - IMAGESTATUS="$IMAGESTATUS, png" - AC_SUBST(DEFHAVE_PNG) - DEFHAVE_PNG="HAVE_PNG=1" - fi -else - IMAGESTATUS="$IMAGESTATUS, png.h not found" -fi - -CONFIGURE_OUTPUTS="Makeconf" Deleted: trunk/octave-forge/main/image/src/jpgread.cc =================================================================== --- trunk/octave-forge/main/image/src/jpgread.cc 2010-03-05 23:45:42 UTC (rev 7000) +++ trunk/octave-forge/main/image/src/jpgread.cc 2010-03-06 08:52:20 UTC (rev 7001) @@ -1,183 +0,0 @@ - // - // This is a hack into octave - // based on jpgread.c by jpgread by Drea Thomas, The Mathworks and the - // examples in the IJG distribution. - // - // (C) 1998 Andy Adler. This code is in the public domain - // USE THIS CODE AT YOUR OWN RISK - // - // $Id$ - // - -/* Modified: Stefan van der Walt <st...@su...> - * Date: 27 January 2004 - * - Manual error handler to prevent segfaults in Octave. - * - Use uint8NDArray for output. - */ - -/* - * Compilation: - * First, try - * mkoctfile jpgread.cc -ljpeg - * - * If this doesn't work, install the jpeg library which is part of - * "The Independent JPEG Group's JPEG software" collection. - * - * The jpeg library came from - * - * ftp://ftp.uu.net/graphics/jpeg/jpegsrc.v6.tar.gz - * - * Extract and build the library: - * tar xvfz jpegsrc.v6.tar.gz - * cd jpeg-6b - * ./configure - * make - * make test - * - * Compile this file using: - * mkoctfile jpgread.cc -I<jpeg-6b include dir> -L<jpeg-6b lib dir> -ljpeg - */ - -#include <octave/oct.h> -#include <iostream> -#include <csetjmp> - -#ifdef __cplusplus -extern "C" { -#endif - -#include "jpeglib.h" - -#ifdef __cplusplus -} //extern "C" -#endif - -struct oct_error_mgr { - struct jpeg_error_mgr pub; /* "public" fields */ - jmp_buf setjmp_buffer; /* for return to caller */ -}; - -typedef struct oct_error_mgr * oct_error_ptr; - -METHODDEF(void) -oct_error_exit (j_common_ptr cinfo) -{ - /* cinfo->err really points to an oct_error_mgr struct, so coerce pointer */ - oct_error_ptr octerr = (oct_error_ptr) cinfo->err; - - /* Format error message and send to interpreter */ - char errmsg[JMSG_LENGTH_MAX]; - (octerr->pub.format_message)(cinfo, errmsg); - error("jpgread: %s", errmsg); - - /* Return control to the setjmp point */ - longjmp(octerr->setjmp_buffer, 1); -} - -DEFUN_DLD (jpgread, args, nargout , "\ --*- texinfo -*-\n\ -@deftypefn {Function File} {@var{I} =} jpgread(@var{filename})\n\ -Read a JPEG file from disk.\n\ -\n\ -For a grey-level image, the output is an MxN matrix. For a\n\ -colour image, three such matrices are returned (MxNx3),\n\ -representing the red, green and blue components. The output\n\ -is of class 'uint8'.\n\ -\n\ -@seealso{imread, im2double, im2gray, im2rgb}\n\ -@end deftypefn\n\ -") { - warning ("'jpgread' has been deprecated in favor of 'imread'. This function will be removed from future versions of the 'image' package."); - octave_value_list retval; - int nargin = args.length(); - - FILE * infile; - - JSAMPARRAY buffer; - long row_stride; - struct jpeg_decompress_struct cinfo; - struct oct_error_mgr jerr; - - // - // We bail out if the input parameters are bad - // - if ((nargin != 1) || !args(0).is_string() || (nargout != 1)) { - print_usage (); - return retval; - } - - // - // Open jpg file - // - std::string filename = args(0).string_value(); - if ((infile = fopen(filename.c_str(), "rb")) == NULL) { - error("jpgread: couldn't open file %s", filename.c_str()); - return retval; - } - - // - // Initialize the jpeg library - // - cinfo.err = jpeg_std_error(&jerr.pub); - jerr.pub.error_exit = oct_error_exit; - if (setjmp(jerr.setjmp_buffer)) { - /* If we get here, the JPEG code has signaled an error. - * We need to clean up the JPEG object, close the input file, and return. - */ - jpeg_destroy_decompress(&cinfo); - fclose(infile); - return retval; - } - - jpeg_create_decompress(&cinfo); - - // - // Read the jpg header to get info about size and color depth - // - jpeg_stdio_src(&cinfo, infile); - jpeg_read_header(&cinfo, TRUE); - jpeg_start_decompress(&cinfo); - - // - // Allocate buffer for one scan line - // - row_stride = cinfo.output_width * cinfo.output_components; - buffer = (*cinfo.mem->alloc_sarray) - ((j_common_ptr) &cinfo, JPOOL_IMAGE, row_stride, 1); - - // - // Create an NDArray for the output. Loop through each of the - // scanlines and copy the image data from the buffer. - // - - dim_vector dim = dim_vector(); - dim.resize(3); - dim(0) = cinfo.output_height; - dim(1) = cinfo.output_width; - dim(2) = cinfo.output_components; - uint8NDArray out = uint8NDArray(dim, 0); - - Array<int> coord = Array<int> (3); - for (unsigned long j=0; cinfo.output_scanline < cinfo.output_height; j++) { - jpeg_read_scanlines(&cinfo, buffer, 1); - - coord(0) = j; - for (unsigned long i=0; i<cinfo.output_width; i++) { - coord(1) = i; - for (int c = 0; c < cinfo.output_components; c++) { - coord(2) = c; - out(coord) = buffer[0][i*cinfo.output_components+c]; - } - } - } - retval.append(out.squeeze()); - - // - // Clean up - // - jpeg_finish_decompress(&cinfo); - jpeg_destroy_decompress(&cinfo); - fclose(infile); - - return retval; -} Deleted: trunk/octave-forge/main/image/src/jpgwrite.cc =================================================================== --- trunk/octave-forge/main/image/src/jpgwrite.cc 2010-03-05 23:45:42 UTC (rev 7000) +++ trunk/octave-forge/main/image/src/jpgwrite.cc 2010-03-06 08:52:20 UTC (rev 7001) @@ -1,258 +0,0 @@ - // This is a hack into octave - // based on jpgwrite.c by jpgread by Drea Thomas, The Mathworks, and the - // examples in the IJG distribution. - // - // (C) 1998 Andy Adler. This code is in the public domain - // USE THIS CODE AT YOUR OWN RISK - // - // $Id$ - // - -#include <octave/oct.h> -#include <iostream> - -#ifdef __cplusplus -extern "C" { -#endif - -#include "jpeglib.h" - -#ifdef __cplusplus -} //extern "C" -#endif - -#define GRAYIMAGES - -/* - * Simple jpeg writing MEX-file. - * - * Synopsis: - * jpgwrite(filename,r,g,b,quality) - * - * Compilation: - * First, try - * mkoctfile jpgwrite.cc -ljpeg - * - * If this doesn't work, then do - * - * Calls the jpeg library which is part of - * "The Independent JPEG Group's JPEG software" collection. - * - * The jpeg library came from, - * - * ftp://ftp.uu.net/graphics/jpeg/jpegsrc.v6.tar.gz - */ - -DEFUN_DLD (jpgwrite, args, , "\ --*- texinfo -*-\n\ -@deftypefn {Function File} jpgwrite(@var{filename}, @var{R}, @var{G}, @var{B}, @var{quality})\n\ -@deftypefnx{Function File} jpgwrite(@var{filename}, @var{I}, @var{quality})\n\ -Write a JPEG file to disc.\n\ -\n\ -If three matrices @var{R}, @var{G}, and @var{B} are given the function will write\n\ -a color image to the disc, where @var{R} is the red channel, @var{G} the green channel,\n\ -and @var{B} the blue channel of the image.\n\ -\n\ -If only one matrix @var{I} is given the function writes a gray-scale image to the disc.\n\ -\n\ -In all cases the data matrices should have integer values between 0 and 255.\n\ -\n\ -If specified, @var{quality} should be in the range 1-100 and will default to\n\ -75 if not specified. 100 is best quality, and 1 is best compression.\n\ -@seealso{jpgread, imwrite}\n\ -@end deftypefn\n\ -") { - warning ("'jpgwrite' has been deprecated in favor of 'imwrite'. This function will be removed from future versions of the 'image' package."); - octave_value_list retval; - int nargin = args.length(); - - FILE * outfile; - - JSAMPARRAY buffer; - struct jpeg_compress_struct cinfo; - struct jpeg_error_mgr jerr; - int quality=75; //default value - -// -// We bail out if the input parameters are bad -// - if (nargin < 2 || !args(0).is_string() ) { - print_usage (); - return retval; - } - - -// -// Open jpg file -// - std::string filename = args(0).string_value(); - if ((outfile = fopen(filename.c_str(), "wb")) == NULL) { - error("Couldn't open file"); - return retval; - } - -// -// Set Jpeg parameters -// - if (nargin == 3) { - quality= (int) args(2).double_value(); - } else if (nargin == 5) { - quality= (int) args(4).double_value(); - } - -// -// Initialize the jpeg library -// Read the jpg header to get info about size and color depth -// - cinfo.err = jpeg_std_error(&jerr); - jpeg_create_compress(&cinfo); - jpeg_stdio_dest(&cinfo, outfile); - - -// -// set parameters for compression -// - - if ( nargin <= 3 ) { -// -// we're here because only one matrix of grey scale values was provided -// - Matrix avg= args(1).matrix_value(); - long image_width = args(1).columns(); - long image_height = args(1).rows(); - - - cinfo.image_width = image_width; /* image width and height, in pixels */ - cinfo.image_height = image_height; -#ifdef GRAYIMAGES - cinfo.input_components = 1; - cinfo.input_components = JCS_GRAYSCALE; -#else - cinfo.input_components = 3; - cinfo.in_color_space = JCS_RGB; -#endif - jpeg_set_defaults(&cinfo); - jpeg_set_quality(&cinfo, quality, TRUE /* limit to baseline-JPEG values */); -// -// start compressor -// - jpeg_start_compress(&cinfo, TRUE); - -// -// Allocate buffer for one scan line -// - long row_stride = image_width * cinfo.input_components ; - buffer = (*cinfo.mem->alloc_sarray) - ((j_common_ptr) &cinfo, JPOOL_IMAGE, row_stride, 1); -// -// Now, loop thru each of the scanlines. For each, copy the image -// data from the buffer, data must be [0 255] -// - for( long j=0; cinfo.next_scanline < cinfo.image_height; j++) { - for(unsigned long i=0; i<cinfo.image_width; i++) { -#ifdef GRAYIMAGES - buffer[0][i] = (unsigned char) avg(j,i); -#else - buffer[0][i*3+0] = (unsigned char) avg(j,i); - buffer[0][i*3+1] = (unsigned char) avg(j,i); - buffer[0][i*3+2] = (unsigned char) avg(j,i); -#endif - } - jpeg_write_scanlines(&cinfo, buffer,1); - } - - } // if nargin <= 3 - else { -// -// we're here because red green and blue matrices were provided -// we assume that they're the same size -// - Matrix red = args(1).matrix_value(); - Matrix green= args(2).matrix_value(); - Matrix blue = args(3).matrix_value(); - long image_width = args(1).columns(); - long image_height = args(1).rows(); - - if ( args(2).columns() != image_width || - args(3).columns() != image_width || - args(2).rows() != image_height || - args(3).rows() != image_height ) { - error("R,G,B matrix sizes aren't the same"); - return retval; - } - - cinfo.image_width = image_width; /* image width and height, in pixels */ - cinfo.image_height = image_height; - cinfo.input_components = 3; /* # of color components per pixel */ - cinfo.in_color_space = JCS_RGB; /* colorspace of input image */ - jpeg_set_defaults(&cinfo); - jpeg_set_quality(&cinfo, quality, TRUE ); -// -// start compressor -// - jpeg_start_compress(&cinfo, TRUE); - -// -// Allocate buffer for one scan line -// - long row_stride = image_width * 3; /* JSAMPLEs per row in image_buffer */ - buffer = (*cinfo.mem->alloc_sarray) - ((j_common_ptr) &cinfo, JPOOL_IMAGE, row_stride, 1); -// -// Now, loop thru each of the scanlines. For each, copy the image -// data from the buffer, data must be [0 255] -// - for( long j=0; cinfo.next_scanline < cinfo.image_height; j++) { - for(unsigned long i=0; i<cinfo.image_width; i++) { - buffer[0][i*3+0] = (unsigned char) red(j,i); - buffer[0][i*3+1] = (unsigned char) green(j,i); - buffer[0][i*3+2] = (unsigned char) blue(j,i); - } - jpeg_write_scanlines(&cinfo, buffer,1); - } - - } // else nargin > 3 - -// -// Clean up -// - - jpeg_finish_compress(&cinfo); - fclose(outfile); - jpeg_destroy_compress(&cinfo); - - - return retval; - -} - -/* - -%!test -%! if exist("jpgwrite","file") -%! ## build test image for r/w tests -%! x=linspace(-8,8,200); -%! [xx,yy]=meshgrid(x,x); -%! r=sqrt(xx.^2+yy.^2) + eps; -%! map=colormap(hsv); -%! A=sin(r)./r; -%! minval = min(A(:)); -%! maxval = max(A(:)); -%! z = round ((A-minval)/(maxval - minval) * (rows(colormap) - 1)) + 1; -%! Rw=Gw=Bw=z; -%! Rw(:)=fix(255*map(z,1)); -%! Gw(:)=fix(255*map(z,2)); -%! Bw(:)=fix(255*map(z,3)); -%! Aw=fix(255*(1-r/max(r(:)))); ## Fade to nothing at the corners -%! jpgwrite('test.jpg',Rw,Gw,Bw); -%! stats=stat("test.jpg"); -%! assert(stats.size,6423); -%! im = jpgread('test.jpg'); -%! Rr = im(:,:,1); Gr = im(:,:,2); Br = im(:,:,3); -%! assert(all(Rw(:)-double(Rr(:))<35)); -%! assert(all(Gw(:)-double(Gr(:))<35)); -%! assert(all(Bw(:)-double(Br(:))<35)); -%! unlink('test.jpg'); -%! endif - -*/ Deleted: trunk/octave-forge/main/image/src/pngcanvas.h =================================================================== --- trunk/octave-forge/main/image/src/pngcanvas.h 2010-03-05 23:45:42 UTC (rev 7000) +++ trunk/octave-forge/main/image/src/pngcanvas.h 2010-03-06 08:52:20 UTC (rev 7001) @@ -1,75 +0,0 @@ -/* - * readpng.h - * - * Copyright (C) 2003 Nadav Rotem <nad...@ho...> - * - * 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 2 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 Library 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/>. - */ - -/* - * Modified: Stefan van der Walt <st...@su...> - * Date: 28 January 2005 - * - Fix bugs, restructure - */ - -typedef struct -{ - int width; - int height; - int bit_depth; - int color_type; - unsigned char **row_pointers; -} canvas; - -//////////////Libcanvas/////////// -canvas *new_canvas(int width, int height, int stride) -{ - // Default stride if none given - if (stride==0) stride=width*4; - - // Clean allocation of canvas structure - canvas *can=new(canvas); - unsigned char *image_data = new unsigned char[stride*height]; - unsigned char **row_pointers = new unsigned char *[height]; - if (can == NULL || image_data == NULL || row_pointers == NULL) - { - if (can == NULL) delete can; - if (image_data == NULL) delete[] image_data; - if (row_pointers == NULL) delete[] row_pointers; - return NULL; - } - - // Fill in canvas structure - can->width=width; - can->height=height; - can->bit_depth=8; - can->color_type=PNG_COLOR_TYPE_RGB_ALPHA; - can->row_pointers = row_pointers; - for (int i=0; i < height; i++) row_pointers[i] = image_data + i*stride; - - return can; -} - -void delete_canvas(canvas *can) -{ - - if (can!=NULL) - { - delete[] can->row_pointers[0]; - delete[] can->row_pointers; - delete can; - } - return; -} - Deleted: trunk/octave-forge/main/image/src/pngread.cc =================================================================== --- trunk/octave-forge/main/image/src/pngread.cc 2010-03-05 23:45:42 UTC (rev 7000) +++ trunk/octave-forge/main/image/src/pngread.cc 2010-03-06 08:52:20 UTC (rev 7001) @@ -1,295 +0,0 @@ -/* - * pngread.cc - * - * Copyright (C) 2003 Nadav Rotem <nad...@ho...> - * - * 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 2 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 Library 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/>. - */ - -/* - -Load PNG files to octave using libpng; - - PNG (Portable Network Graphics) is an extensible file format for the - lossless, portable, well-compressed storage of raster images. PNG pro- - vides a patent-free replacement for GIF and can also replace many com- - mon uses of TIFF. Indexed-color, grayscale, and truecolor images are - supported, plus an optional alpha channel. Sample depths range from 1 - to 16 bits. - -*/ - -/* - * Modified: Stefan van der Walt <st...@su...> - * Date: 28 January 2005 - * - Fix bugs, restructure - */ - -#include "png.h" -#include "pngcanvas.h" -#include <octave/oct.h> - -canvas *load_canvas(char *filename); - -DEFUN_DLD (pngread, args, nargout , -"-*- texinfo -*-\n\ -@deftypefn {Loadable Function} {[@var{I}, @var{alpha}] =} pngread(@var{filename})\n\ -\n\ -Read a PNG file from disk.\n\ -\n\ -The image is returned as a matrix of dimension MxN (for grey-level images)\n\ -or MxNx3 (for colour images). The numeric type of @var{I} and @var{alpha}\n\ -is @code{uint8} for grey-level and RGB images, or @code{logical} for\n\ -black-and-white images.\n\ -\n\ -@end deftypefn\n\ -@seealso{imread}") -{ - warning ("'pngread' has been deprecated in favor of 'imread'. This function will be removed from future versions of the 'image' package."); - octave_value_list retval; - int nargin = args.length(); - - // - // We bail out if the input parameters are bad - // - if (nargin != 1 || !args(0).is_string()) { - print_usage (); - return retval; - } - - // - // Load png file - // - canvas *pic=load_canvas((char *)args(0).string_value().c_str()); - if (!pic) return retval; - - dim_vector dim = dim_vector(); - dim.resize(3); - dim(0) = pic->height; - dim(1) = pic->width; - dim(2) = 3; - - if ( (pic->color_type == PNG_COLOR_TYPE_GRAY) || - (pic->color_type == PNG_COLOR_TYPE_GRAY_ALPHA) || - ((pic->color_type == PNG_COLOR_TYPE_PALETTE) && (pic->bit_depth == 1)) ) - dim(2) = 1; - - if (pic->bit_depth > 1 && pic->bit_depth < 8) - pic->bit_depth = 8; //this should never happen according to load_canvas code - - int isAlfaChannelPresent = 0; - if ( pic->color_type & PNG_COLOR_MASK_ALPHA) - isAlfaChannelPresent=1; - - - NDArray out(dim); - - dim.resize(2); - NDArray alpha(dim); - - Array<int> coord = Array<int> (3); - - int major_byte, minor_byte,row_pxl_position; - /* calculate the number of color channels (including alpha) per pixel */ - int ElementsPerPixel=out.dims()(2)+isAlfaChannelPresent; - for (unsigned long j=0; j < pic->height; j++) { - coord(0) = j; - for (unsigned long i=0; i < pic->width; i++) { - coord(1) = i; - - for (int c = 0; c < out.dims()(2); c++) { - coord(2) = c; - switch(pic->bit_depth) { - case 8: - row_pxl_position=(i*ElementsPerPixel+c); - out(coord) = pic->row_pointers[j][row_pxl_position]; - break; - case 16: - // converting big endian - row_pxl_position=2*(i*ElementsPerPixel+c); - major_byte=pic->row_pointers[j][row_pxl_position]; - minor_byte=pic->row_pointers[j][row_pxl_position+1] ; - out(coord) = major_byte*256+minor_byte; - break; - default: - printf("do not know how to handle bit depth of %d\n",pic->bit_depth); - } - } - if (isAlfaChannelPresent) { // it always should according to load canvas code - switch(pic->bit_depth) { - case 8: - row_pxl_position=(i*ElementsPerPixel+ElementsPerPixel-1); - alpha(j,i) = pic->row_pointers[j][row_pxl_position]; - break; - case 16: - // converting big endian - row_pxl_position=2*(i*ElementsPerPixel+ElementsPerPixel-1); - major_byte = pic->row_pointers[j][row_pxl_position]; - minor_byte = pic->row_pointers[j][row_pxl_position+1]; - alpha(j,i) = major_byte*256+minor_byte; - break; - default: - printf("do not know how to handle bit depth of %d\n",pic->bit_depth); - } - } else { - alpha(j,i) = 255; - } - } - } - out = out.squeeze(); - - switch (pic->bit_depth) { - case 1: - retval.append((boolNDArray)out); - retval.append((boolNDArray)alpha); - break; - case 8: - retval.append((uint8NDArray)out); - retval.append((uint8NDArray)alpha); - break; - case 16: - retval.append((uint16NDArray)out); - retval.append((uint16NDArray)alpha); - break; - default: - retval.append(out); - retval.append(alpha); - } - - delete_canvas(pic); - return retval; -} - -canvas *load_canvas(char *filename) -{ - png_structp png_ptr; - png_infop info_ptr; - - FILE *infile = fopen(filename,"rb"); - if (!infile) { - error("pngread could not open file %s", filename); - return NULL; - } - - unsigned char sig[8]; - const size_t bytes_read = fread (sig, 1, 8, infile); - if (!png_check_sig (sig, 8) || bytes_read != 8) { - error ("pngread invalid signature in %s", filename); - fclose (infile); - return NULL; - } - - png_ptr = png_create_read_struct(PNG_LIBPNG_VER_STRING,NULL,NULL,NULL); - if (!png_ptr) { - error("pngread out of memory"); - fclose(infile); - return NULL; - } - - info_ptr = png_create_info_struct(png_ptr); - if(!info_ptr) { - error("pngread can't generate info"); - png_destroy_read_struct(&png_ptr,NULL,NULL); - fclose(infile); - return NULL; - } - - /* Set error handling */ - if (setjmp(png_jmpbuf(png_ptr))) { - error("pngread: libpng exited abnormally"); - png_destroy_read_struct(&png_ptr, &info_ptr, png_infopp_NULL); - fclose(infile); - return NULL; - } - - png_init_io(png_ptr, infile); - png_set_sig_bytes(png_ptr, 8); - png_read_info(png_ptr, info_ptr); - - png_uint_32 width,height; - int color_type, bit_depth; - png_get_IHDR(png_ptr,info_ptr,&width,&height, - &bit_depth,&color_type,NULL,NULL,NULL); - - /* Transform grayscale images with depths < 8-bit to 8-bit, change - * paletted images to RGB, and add a full alpha channel if there is - * transparency information in a tRNS chunk. - */ - if (color_type == PNG_COLOR_TYPE_PALETTE) { - png_set_palette_to_rgb(png_ptr); - } - if (color_type == PNG_COLOR_TYPE_GRAY && bit_depth < 8) { - png_set_gray_1_2_4_to_8(png_ptr); // this function deprecated need to be redone - bit_depth=8; - info_ptr->bit_depth=bit_depth; - } - if (png_get_valid(png_ptr, info_ptr, PNG_INFO_tRNS)) { //add alpha - png_set_tRNS_to_alpha(png_ptr); - } - - // Always transform image to RGB - if (color_type == PNG_COLOR_TYPE_GRAY - || color_type == PNG_COLOR_TYPE_GRAY_ALPHA) - { - png_set_gray_to_rgb(png_ptr); - color_type= (color_type | PNG_COLOR_MASK_COLOR); - info_ptr->color_type=color_type; - } - - // If no alpha layer is present, create one - if (!(color_type & PNG_COLOR_MASK_ALPHA)) - { - png_set_add_alpha(png_ptr, 0xff, PNG_FILLER_AFTER); - color_type= (color_type | PNG_COLOR_MASK_ALPHA); - info_ptr->color_type=color_type; - } - - if (bit_depth < 8) { - png_set_packing(png_ptr); - bit_depth=8; - info_ptr->bit_depth=bit_depth; - } - - // Hey! Our signal could be small and in the lower bits, - // leave our data alone and do not decrease accuracy - // 16 -> 8 bits commented out - // For now, use 8-bit only - //if (bit_depth == 16) { - //png_set_strip_16(png_ptr); - //bit_depth=8; - //info_ptr->bit_depth=bit_depth; - //} - - png_read_update_info(png_ptr,info_ptr); - - // Read the data from the file - int stride = png_get_rowbytes(png_ptr, info_ptr); - canvas *can = new_canvas(width, height, stride); - - if (can) { - png_read_image(png_ptr, can->row_pointers); - } else { - error("pngread out of memory"); - } - - png_read_end(png_ptr,NULL); - png_destroy_read_struct(&png_ptr, &info_ptr, (png_infopp)NULL); - - fclose(infile); - - // Set color type and depth. Used to determine octave output arguments. - can->color_type = color_type; - can->bit_depth = bit_depth; - return can; -} Deleted: trunk/octave-forge/main/image/src/pngwrite.cc =================================================================== --- trunk/octave-forge/main/image/src/pngwrite.cc 2010-03-05 23:45:42 UTC (rev 7000) +++ trunk/octave-forge/main/image/src/pngwrite.cc 2010-03-06 08:52:20 UTC (rev 7001) @@ -1,205 +0,0 @@ -/* - * pngwrite.cc - * - * Copyright (C) 2003 Nadav Rotem <nad...@ho...> - * - * 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 2 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 Library 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/>. - */ - -/* - -Write PNG files to disk from octave - - PNG (Portable Network Graphics) is an extensible file format for the - lossless, portable, well-compressed storage of raster images. PNG pro- - vides a patent-free replacement for GIF and can also replace many com- - mon uses of TIFF. Indexed-color, grayscale, and truecolor images are - supported, plus an optional alpha channel. Sample depths range from 1 - to 16 bits. - -*/ - -/* - * Modified: Stefan van der Walt <st...@su...> - * Date: 28 January 2005 - * - Fix bugs, restructure - */ - -#include "png.h" -#include "pngcanvas.h" -#include <octave/oct.h> - -void save_canvas(canvas *can, char *filename); - -DEFUN_DLD (pngwrite, args, ,"\ --*- texinfo -*-\n\ -@deftypefn {Function File} pngwrite(@var{filename}, @var{R}, @var{G}, @var{B}, @var{A})\n\ -Writes a png file to the disk using the Red, Green, Blue and Alpha matrices.\n\ -\n\ -Data must be [0 255] or the high bytes will be lost.\n\ -@seealso{imwrite}\n\ -@end deftypefn\n\ -") { - warning ("'pngwrite' has been deprecated in favor of 'imwrite'. This function will be removed from future versions of the 'image' package."); - octave_value_list retval; - int nargin = args.length(); - - // - // We bail out if the input parameters are bad - // - if (nargin < 5 || !args(0).is_string() ) { - print_usage (); - return retval; - } - - Matrix red = args(1).matrix_value(); - Matrix green= args(2).matrix_value(); - Matrix blue = args(3).matrix_value(); - Matrix alpha= args(4).matrix_value(); - - long image_width = args(1).columns(); - long image_height = args(1).rows(); - - if ( args(2).columns() != image_width || - args(3).columns() != image_width || - args(4).columns() != image_width || - args(2).rows() != image_height || - args(3).rows() != image_height || - args(4).rows() != image_height ) - { - error("pngwrite R,G,B,A matrix sizes aren't the same"); - return retval; - } - - canvas *pic=new_canvas(image_width, image_height, image_width*4); - if (!pic) { - error("pngwrite out of memory"); - return retval; - } - - for(int i=0; i < pic->width; i++) { - for(int j=0; j < pic->height; j++) { - pic->row_pointers[j][i*4+0]=(unsigned char)(red(j,i)); - pic->row_pointers[j][i*4+1]=(unsigned char)(green(j,i)); - pic->row_pointers[j][i*4+2]=(unsigned char)(blue(j,i)); - pic->row_pointers[j][i*4+3]=(unsigned char)(alpha(j,i)); - } - } - - - save_canvas(pic,(char *)args(0).string_value().c_str()); - delete_canvas(pic); - - return retval; -} - -void save_canvas(canvas *can,char *filename) -{ - FILE *fp; - png_structp png_ptr; - png_infop info_ptr; - - fp = fopen(filename, "wb"); - if (fp == NULL) { - error("pngwrite could not open %s", filename); - return; - } - - png_ptr = png_create_write_struct(PNG_LIBPNG_VER_STRING, NULL, NULL, NULL); - if (!png_ptr) { - fclose(fp); - error("pngwrite: cannot create write structure"); - return; - } - - info_ptr = png_create_info_struct(png_ptr); - if (!info_ptr) { - fclose(fp); - error("pngwrite: cannot not create image structure"); - png_destroy_write_struct(&png_ptr, png_infopp_NULL); - return; - } - - if (setjmp(png_jmpbuf(png_ptr))) { - fclose(fp); - png_destroy_write_struct(&png_ptr, &info_ptr); - error("pngread: libpng exited abnormally"); - return; - } - - png_init_io(png_ptr, fp); - png_set_compression_level(png_ptr, 3); - - png_set_IHDR(png_ptr, info_ptr, can->width, can->height, - can->bit_depth, can->color_type, PNG_INTERLACE_NONE, - PNG_COMPRESSION_TYPE_DEFAULT, PNG_FILTER_TYPE_DEFAULT); - - - png_set_gAMA(png_ptr, info_ptr, 0.7); - - time_t gmt; - png_time mod_time; - png_text text_ptr[2]; - time(&gmt); - png_convert_from_time_t(&mod_time, gmt); - png_set_tIME(png_ptr, info_ptr, &mod_time); - text_ptr[0].key = png_charp ("Created by"); - text_ptr[0].text = png_charp ("Octave"); - text_ptr[0].compression = PNG_TEXT_COMPRESSION_NONE; - - png_set_text(png_ptr, info_ptr, text_ptr, 1); - - png_write_info(png_ptr, info_ptr); - png_write_image(png_ptr, can->row_pointers); - png_write_end(png_ptr, info_ptr); - png_destroy_write_struct(&png_ptr, &info_ptr); - fclose(fp); -} - -/* - -%!test -%! if exist("jpgwrite","file") -%! ## build test image for r/w tests -%! x=linspace(-8,8,200); -%! [xx,yy]=meshgrid(x,x); -%! r=sqrt(xx.^2+yy.^2) + eps; -%! map=colormap(hsv); -%! A=sin(r)./r; -%! minval = min(A(:)); -%! maxval = max(A(:)); -%! z = round ((A-minval)/(maxval - minval) * (rows(colormap) - 1)) + 1; -%! Rw=Gw=Bw=z; -%! Rw(:)=fix(255*map(z,1)); -%! Gw(:)=fix(255*map(z,2)); -%! Bw(:)=fix(255*map(z,3)); -%! Aw=fix(255*(1-r/max(r(:)))); ## Fade to nothing at the corners -%! pngwrite('test.png',Rw,Gw,Bw,Aw); -%! stats=stat("test.png"); -%! assert(stats.size,24738); -%! im = pngread('test.png'); -%! Rr = im(:,:,1); Gr = im(:,:,2); Br = im(:,:,3); -%! assert(all(double(Rr(:))==Rw(:))); -%! assert(all(double(Gr(:))==Gw(:))); -%! assert(all(double(Br(:))==Bw(:))); -%! [im,Ar] = pngread('test.png'); -%! Rr = im(:,:,1); Gr = im(:,:,2); Br = im(:,:,3); -%! assert(all(double(Rr(:))==Rw(:))); -%! assert(all(double(Gr(:))==Gw(:))); -%! assert(all(double(Br(:))==Bw(:))); -%! assert(all(double(Ar(:))==Aw(:))); -%! unlink('test.png'); -%! endif - -*/ This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <jo...@us...> - 2011-11-18 07:08:16
|
Revision: 9127 http://octave.svn.sourceforge.net/octave/?rev=9127&view=rev Author: jordigh Date: 2011-11-18 07:08:09 +0000 (Fri, 18 Nov 2011) Log Message: ----------- Add preliminary implementation of bwlabeln Modified Paths: -------------- trunk/octave-forge/main/image/src/bwlabel.cc Added Paths: ----------- trunk/octave-forge/main/image/src/bwlabeln.cc Modified: trunk/octave-forge/main/image/src/bwlabel.cc =================================================================== --- trunk/octave-forge/main/image/src/bwlabel.cc 2011-11-17 22:36:25 UTC (rev 9126) +++ trunk/octave-forge/main/image/src/bwlabel.cc 2011-11-18 07:08:09 UTC (rev 9127) @@ -5,7 +5,7 @@ copyright 2002 Jeffrey E. Boyd - uses 4, 6, or 8 connectedness - - See BKP Horn, Robot Vision, MIT Press, 1986, p 66 - 71 + - See BKP Horn, Robot Vision, MIT Press, 1986, p 66 - 71 labeling scheme @@ -16,15 +16,15 @@ +-+-+-+ | | | | +-+-+-+ - + A is the center pixel of a neighborhood. In the 3 versions of connectedness: - + 4: A connects to B and C 6: A connects to B, C, and D 8: A connects to B, C, D, and E - - + + --------------------------------------------------------------------- */ @@ -50,13 +50,13 @@ print_usage (); return true; } - + if (!args (0).is_bool_matrix ()) { error ("bwlabel: first input argument must be a 'logical' matrix"); return true; } - + if (nargin == 2) { if (!args (1).is_real_scalar ()) @@ -71,8 +71,8 @@ return true; } } - - return false; + + return false; } DEFUN_DLD(bwlabel, args, , "\ @@ -96,30 +96,30 @@ octave_value_list rval; if (any_bad_argument (args)) return rval; - + // input arguments boolMatrix BW = args (0).bool_matrix_value (); // the input binary image int nr = BW.rows (); int nc = BW.columns (); - + // n-hood connectivity int n; if (args.length () < 2) n = 8; else n = args (1).int_value (); - + // results Matrix L (nr, nc); // the label image int nobj; // number of objects found in image - + // other variables int ntable; // number of elements in the component table/tree - + OCTAVE_LOCAL_BUFFER (int, lset, nr * nc); // label table/tree ntable = 0; lset [0] = 0; - + for (int r = 0; r < nr; r++) { for (int c = 0; c < nc; c++) @@ -132,22 +132,22 @@ B = 0; else B = find (lset, (int)L.elem (r, c-1)); - + if (r == 0) C = 0; else C = find (lset, (int)L.elem (r-1, c)); - + if (r == 0 || c == 0) D = 0; else D = find (lset, (int)L.elem (r-1, c-1)); - + if (r == 0 || c == nc - 1) E = 0; else E = find (lset, (int)L.elem(r-1, c+1)); - + if (n == 4) { // apply 4 connectedness @@ -236,9 +236,9 @@ { tlabel = E; } - + L.elem (r, c) = tlabel; - + if (B && B != tlabel) lset [B] = tlabel; if (C && C != tlabel) @@ -262,7 +262,7 @@ } } } - + // consolidate component table for (int i = 0; i <= ntable; i++) lset [i] = find (lset, i); @@ -271,7 +271,7 @@ for (int r = 0; r < nr; r++) for (int c = 0; c < nc; c++) L.elem (r, c) = lset [(int)L.elem (r, c)]; - + // count up the objects in the image for (int i = 0; i <= ntable; i++) lset [i] = 0; @@ -300,5 +300,3 @@ /* %!assert(bwlabel(logical([0 1 0; 0 0 0; 1 0 1])),[0 1 0; 0 0 0; 2 0 3]); */ - - Added: trunk/octave-forge/main/image/src/bwlabeln.cc =================================================================== --- trunk/octave-forge/main/image/src/bwlabeln.cc (rev 0) +++ trunk/octave-forge/main/image/src/bwlabeln.cc 2011-11-18 07:08:09 UTC (rev 9127) @@ -0,0 +1,299 @@ +// bwlabeln.cc --- + +// Copyright © 2011 Jordi Gutiérrez Hermoso <jo...@oc...> + +// Author: Jordi Gutiérrez Hermoso + +// 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 <oct.h> +#include <set> +#include "union-find.h++" + + +dim_vector conn26_dim(3,3,3); +boolNDArray conn26(conn26_dim,1); +typedef Array<octave_idx_type> coord; + +bool operator== (const coord& a, const coord& b) +{ + if (a.nelem () != b.nelem()) + return false; + for (octave_idx_type i = 0; i < a.nelem (); i++) + if ( a(i) != b(i) ) + return false; + + return true; +} + +bool in_range (const coord& a, const dim_vector& size_vec) +{ + for(octave_idx_type i = 0; i < a.nelem (); i++) + if (a(i) < 0 or a(i) >= size_vec(i)) + return false; + return true; +} + +//Lexicographic order for coords +bool operator< (const coord& a, const coord& b) +{ + octave_idx_type na = a.nelem (), nb = b.nelem (); + if (na < nb) + return true; + if (na > nb) + return false; + octave_idx_type i = 0; + while (a(i) == b(i) and i < na) + { + i++; + } + + if (i == na //They're equal, but this is strict order + or a(i) > b(i) ) + return false; + + return true; +} + +struct coord_hash +{ + inline size_t operator() (const coord& c) const + { + size_t seed = 0; + for(octave_idx_type i = 0; i < c.nelem (); i++) + { + //Boost's hash + seed ^= c(i) + 0x9e3779b9 + (seed<<6) + (seed>>2); + } + return seed; + } + + inline size_t operator()(size_t s) const + { + return s; + } +}; + +namespace { + +// A few basic utility functions +//{ +inline +coord +to_coord(const dim_vector& dv, + octave_idx_type k) +{ + octave_idx_type n = dv.length (); + coord retval ( dim_vector (n, 1)); + for (octave_idx_type j = 0; j < n; j++) + { + retval(j) = k % dv(j); + k /= dv(j); + } + return retval; +} + +inline +coord +operator+ (const coord& a, const coord& b) +{ + octave_idx_type na = a.nelem (); + coord retval( dim_vector(na,1) ); + for (octave_idx_type i = 0; i < na; i++) + { + retval(i) = a(i) + b(i); + } + return retval; +} + + +inline +coord +operator- (const coord& a, const coord& b) +{ + octave_idx_type na = a.nelem (); + coord retval( dim_vector(na,1) ); + for (octave_idx_type i = 0; i < na; i++) + { + retval(i) = a(i) - b(i); + } + return retval; +} + + +inline +coord +operator- (const coord& a) +{ + octave_idx_type na = a.nelem (); + coord retval( dim_vector(na,1) ); + for (octave_idx_type i = 0; i < na; i++) + { + retval(i) = -a(i); + } + return retval; +} +//} + +bool any_bad_argument (const octave_value_list& args) +{ + return false; + + const int nargin = args.length (); + if (nargin < 1 || nargin > 2) + { + print_usage (); + return true; + } + + if (!args (0).is_bool_type ()) + { + error ("bwlabeln: first input argument must be a 'logical' ND-array"); + return true; + } + + if (nargin == 2) + { + if (!args (1).is_real_scalar () && ! args(1).is_bool_type()) + { + error ("bwlabeln: second input argument must be a real scalar " + "or a 'logical' connectivity array"); + return true; + } + } + + return false; +} + +//debug +#include <iostream> +using namespace std; + +ostream& +operator<< (ostream& os, const coord& aidx) +{ + for (octave_idx_type i = 0; i < aidx.nelem (); i++) + os << aidx(i) + 1 << " "; + return os; +} + +set<coord> +populate_neighbours(const boolNDArray& conn_mask) +{ + set<coord> neighbours; + + dim_vector conn_size = conn_mask.dims (); + coord centre(dim_vector(conn_size.length (), 1), 1); + coord zero(dim_vector(conn_size.length (), 1), 0); + for (octave_idx_type idx = 0; idx < conn_mask.nelem (); idx++) + { + if (conn_mask(idx)) + { + coord aidx = to_coord(conn_size, idx) - centre; + //The zero coordinates are the centre, and the negative ones + //are the ones reflected about the centre, and we don't need + //to consider those. + if( aidx == zero or neighbours.find(-aidx) != neighbours.end() ) + continue; + neighbours.insert (aidx); + } + } + return neighbours; +} + +DEFUN_DLD(bwlabeln, args, , "\ +-*- texinfo -*-\n\ +@deftypefn {Function File} {[@var{l}, @var{num}] =} bwlabeln(@var{bw}, @var{n})\n\ +\n\ +Labels foreground objects in the n-dimensional binary image @var{bw}.\n\ +The output @var{l} is an Nd-array where 0 indicates a background\n\ +pixel, 1 indicates that the pixel belong to object number 1, 2 that\n\ +the pixel belong to object number 2, etc. The total number of objects\n\ +is @var{num}.\n\ +\n\ +@end deftypefn\n\ +") +{ + octave_value_list rval; + + union_find<coord, coord_hash> u_f; + + if (any_bad_argument (args)) + return rval; + + boolNDArray BW = args (0).bool_array_value (); + + dim_vector size_vec = BW.dims (); + + int nargin = args.length (); + + //Connectivity mask + boolNDArray conn_mask; + if( nargin == 1) + conn_mask = conn26; //Implement this properly later + else + conn_mask = conn26; + + set<coord> neighbours = populate_neighbours(conn_mask); + + for (octave_idx_type idx = 0; idx < BW.nelem (); idx++) + { + if (BW(idx)) + { + coord aidx = to_coord (size_vec, idx); + + //Insert this one into its group + u_f.find_id(aidx); + + //Replace this with C++0x range-based for loop later + //(implemented in gcc 4.6) + for (auto nbr = neighbours.begin (); nbr!= neighbours.end (); nbr++) + { + coord n = *nbr + aidx; + if (in_range (n,size_vec) and BW(n) ) + u_f.unite (n,aidx); + } + } + } + + NDArray L (size_vec, 0); + unordered_map<octave_idx_type, octave_idx_type> ids_to_label; + octave_idx_type next_label = 1; + + auto idxs = u_f.get_objects (); + + //C++0x foreach later + for (auto idx = idxs.begin (); idx != idxs.end (); idx++) + { + octave_idx_type label; + octave_idx_type id = u_f.find_id (idx->first); + auto try_label = ids_to_label.find (id); + if( try_label == ids_to_label.end ()) + { + label = next_label++; + ids_to_label[id] = label; + } + else + { + label = try_label -> second; + } + + L(idx->first) = label; + } + + rval(0) = L; + rval(1) = ids_to_label.size (); + return rval; +} +}//anonymous namespace This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <jo...@us...> - 2012-09-05 19:14:20
|
Revision: 10965 http://octave.svn.sourceforge.net/octave/?rev=10965&view=rev Author: jordigh Date: 2012-09-05 19:14:14 +0000 (Wed, 05 Sep 2012) Log Message: ----------- Further speedups to bwlabeln Modified Paths: -------------- trunk/octave-forge/main/image/src/Makefile trunk/octave-forge/main/image/src/bwlabeln.cc trunk/octave-forge/main/image/src/union-find.h++ Modified: trunk/octave-forge/main/image/src/Makefile =================================================================== --- trunk/octave-forge/main/image/src/Makefile 2012-09-05 10:21:06 UTC (rev 10964) +++ trunk/octave-forge/main/image/src/Makefile 2012-09-05 19:14:14 UTC (rev 10965) @@ -5,7 +5,7 @@ %.oct: %.cc mkoctfile -Wall $< -bwlabeln.oct: bwlabeln.cc +bwlabeln.oct: bwlabeln.cc union-find.h++ CXXFLAGS='-g -O2 -std=c++0x -Wall' mkoctfile $< clean: Modified: trunk/octave-forge/main/image/src/bwlabeln.cc =================================================================== --- trunk/octave-forge/main/image/src/bwlabeln.cc 2012-09-05 10:21:06 UTC (rev 10964) +++ trunk/octave-forge/main/image/src/bwlabeln.cc 2012-09-05 19:14:14 UTC (rev 10965) @@ -18,6 +18,7 @@ #include <oct.h> #include <set> #include "union-find.h++" +#include <unordered_map> typedef Array<octave_idx_type> coord; @@ -295,8 +296,6 @@ { octave_value_list rval; - union_find<octave_idx_type> u_f; - octave_idx_type nargin = args.length (); if (nargin < 1 || nargin > 2) @@ -373,6 +372,7 @@ L.insert(BW, coord (dim_vector (size_vec.length (), 1), 1)); double* L_vec = L.fortran_vec (); + union_find u_f (L.nelem ()); for (octave_idx_type BWidx = 0; BWidx < BW.nelem (); BWidx++) { @@ -381,7 +381,7 @@ if (L_vec[Lidx]) { //Insert this one into its group - u_f.find_id(Lidx); + u_f.find (Lidx); //Replace this with C++0x range-based for loop later //(implemented in gcc 4.6) @@ -395,17 +395,16 @@ } - unordered_map<octave_idx_type, octave_idx_type> ids_to_label; + std::unordered_map<octave_idx_type, octave_idx_type> ids_to_label; octave_idx_type next_label = 1; - auto idxs = u_f.get_objects (); + auto idxs = u_f.get_ids (); //C++0x foreach later - for (auto idx = idxs.begin (); idx != idxs.end (); idx++) { octave_idx_type label; - octave_idx_type id = u_f.find_id (idx->first); + octave_idx_type id = u_f.find (*idx); auto try_label = ids_to_label.find (id); if( try_label == ids_to_label.end ()) { @@ -417,7 +416,7 @@ label = try_label -> second; } - L_vec[idx->first] = label; + L_vec[*idx] = label; } rval(0) = L; Modified: trunk/octave-forge/main/image/src/union-find.h++ =================================================================== --- trunk/octave-forge/main/image/src/union-find.h++ 2012-09-05 10:21:06 UTC (rev 10964) +++ trunk/octave-forge/main/image/src/union-find.h++ 2012-09-05 19:14:14 UTC (rev 10965) @@ -15,118 +15,85 @@ // union-find.h++ -#include <unordered_map> -#include <list> +#include <vector> -using std::unordered_map; -using std::list; +struct voxel{ + octave_idx_type rank; + octave_idx_type parent; +}; -// T - type of object we're union-finding for -// H - hash for the map -template <typename T, typename H = std::hash<T> > class union_find { -//Dramatis personae private: + std::vector<voxel*> voxels; - //Each root has rank. - unordered_map<octave_idx_type, octave_idx_type, H> num_ranks; - - //Each object points to its parent, possibly itself. - unordered_map<octave_idx_type, octave_idx_type, H> parent_pointers; - - //Represent each object by a number and vice versa. - unordered_map<octave_idx_type, T, H> num_to_objects; - unordered_map<T, octave_idx_type, H> objects_to_num; - -// Act 1 public: - //Insert a collection of objects - void insert_objects (const list<T>& objects) + union_find (octave_idx_type s) : voxels (s, NULL) {}; + + ~union_find () { - for (auto i = objects.begin (); i != objects.end (); i++) - { - find (*i); - } + for (auto v = voxels.begin(); v != voxels.end(); v++) + delete *v; } - //Give the root representative id for this object, or insert into a //new set if none is found - octave_idx_type find_id (const T& object) + octave_idx_type find (octave_idx_type idx) { //Insert new element if not found - if (objects_to_num.find (object) == objects_to_num.end () ) + auto v = voxels[idx]; + if (!v) { - //Assign number serially to objects - octave_idx_type obj_num = objects_to_num.size ()+1; - - num_ranks[obj_num] = 0; - objects_to_num[object] = obj_num; - num_to_objects[obj_num] = object; - parent_pointers[obj_num] = obj_num; - return obj_num; + voxel* new_voxel = new voxel; + new_voxel->rank = 0; + new_voxel->parent = idx; + voxels[idx] = new_voxel; + return idx; } - //Path from this element to its root, we'll build it. - list<octave_idx_type> path (1, objects_to_num[object]); - octave_idx_type par = parent_pointers[path.back ()]; - while ( par != path.back () ) - { - path.push_back (par); - par = parent_pointers[par]; - } + voxel* elt = v; + if (elt->parent != idx) + elt->parent = find (elt->parent); - //Update everything we've seen to point to the root. - for (auto i = path.begin (); i != path.end (); i++) - { - parent_pointers[*i] = par; - } - - return par; + return elt->parent; } - T find( const T& object) - { - return num_to_objects[find_id (object)]; - } - //Given two objects, unite the sets to which they belong - void unite (const T& obj1, const T& obj2) + void unite (octave_idx_type idx1, octave_idx_type idx2) { - octave_idx_type on1 = find_id(obj1), on2 = find_id(obj2); + octave_idx_type root1 = find (idx1), root2 = find (idx2); //Check if any union needs to be done, maybe they already are //in the same set. - if (on1 != on2) + voxel *v1 = voxels[root1], *v2 = voxels[root2]; + if (root1 != root2) { - octave_idx_type r1 = num_ranks[on1], r2 = num_ranks[on2]; - if ( r1 < r2) - { - parent_pointers[on1] = on2; - num_ranks.erase (on1); //Only root nodes need a rank - } - else if (r2 > r1) - { - parent_pointers[on2] = on1; - num_ranks.erase (on2); - } + + if ( v1->rank > v2->rank) + v1->parent = root2; + else if (v1->rank < v2->rank) + v2->parent = root1; else { - parent_pointers[on2] = on1; - num_ranks.erase (on2); - num_ranks[on1]++; + v2->parent = root1; + v1->rank++; } } } - const unordered_map<T, octave_idx_type, H>& get_objects() + std::vector<octave_idx_type> get_ids() { - return objects_to_num; + std::vector<octave_idx_type> ids; + + for (size_t i = 0; i < voxels.size (); i++) + if (voxels[i]) + ids.push_back (i); + + return ids; }; }; This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <jo...@us...> - 2012-09-05 20:02:46
|
Revision: 10966 http://octave.svn.sourceforge.net/octave/?rev=10966&view=rev Author: jordigh Date: 2012-09-05 20:02:40 +0000 (Wed, 05 Sep 2012) Log Message: ----------- Remove zero padding from bwlabeln output Modified Paths: -------------- trunk/octave-forge/main/image/src/bwlabeln.cc trunk/octave-forge/main/image/src/union-find.h++ Modified: trunk/octave-forge/main/image/src/bwlabeln.cc =================================================================== --- trunk/octave-forge/main/image/src/bwlabeln.cc 2012-09-05 19:14:14 UTC (rev 10965) +++ trunk/octave-forge/main/image/src/bwlabeln.cc 2012-09-05 20:02:40 UTC (rev 10966) @@ -412,14 +412,17 @@ ids_to_label[id] = label; } else - { label = try_label -> second; - } L_vec[*idx] = label; } - rval(0) = L; + // Remove the zero padding... + Array<idx_vector> inner_slice (dim_vector (size_vec.length (), 1)); + for (octave_idx_type i = 0; i < padded_size.length (); i++) + inner_slice(i) = idx_vector (1, padded_size(i) - 1); + + rval(0) = L.index (inner_slice); rval(1) = ids_to_label.size (); return rval; } Modified: trunk/octave-forge/main/image/src/union-find.h++ =================================================================== --- trunk/octave-forge/main/image/src/union-find.h++ 2012-09-05 19:14:14 UTC (rev 10965) +++ trunk/octave-forge/main/image/src/union-find.h++ 2012-09-05 20:02:40 UTC (rev 10966) @@ -71,8 +71,6 @@ voxel *v1 = voxels[root1], *v2 = voxels[root2]; if (root1 != root2) { - - if ( v1->rank > v2->rank) v1->parent = root2; else if (v1->rank < v2->rank) This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |
From: <jo...@us...> - 2012-09-07 15:24:55
|
Revision: 10980 http://octave.svn.sourceforge.net/octave/?rev=10980&view=rev Author: jordigh Date: 2012-09-07 15:24:49 +0000 (Fri, 07 Sep 2012) Log Message: ----------- bwlabeln.cc: Add a few comments about the union-find data structure. Modified Paths: -------------- trunk/octave-forge/main/image/src/bwlabeln.cc trunk/octave-forge/main/image/src/union-find.h++ Modified: trunk/octave-forge/main/image/src/bwlabeln.cc =================================================================== --- trunk/octave-forge/main/image/src/bwlabeln.cc 2012-09-07 15:21:39 UTC (rev 10979) +++ trunk/octave-forge/main/image/src/bwlabeln.cc 2012-09-07 15:24:49 UTC (rev 10980) @@ -282,6 +282,9 @@ the pixel belong to object number 2, etc. The total number of objects\n\ is @var{num}.\n\ \n\ +The algorithm used is a disjoint-set data structure, a.k.a. union-find.\n\ +See, for example, http://en.wikipedia.org/wiki/Union-find\n\ +\n\ @seealso{bwconncomp, bwlabel, regionprops}\n\ @end deftypefn\n\ ") Modified: trunk/octave-forge/main/image/src/union-find.h++ =================================================================== --- trunk/octave-forge/main/image/src/union-find.h++ 2012-09-07 15:21:39 UTC (rev 10979) +++ trunk/octave-forge/main/image/src/union-find.h++ 2012-09-07 15:24:49 UTC (rev 10980) @@ -24,6 +24,8 @@ class union_find { + // Union-find data structure, see e.g. + // http://en.wikipedia.org/wiki/Union-find private: std::vector<voxel*> voxels; This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |