[37] | 1 | /* file: localmax.c |
---|
| 2 | ** author: Andrea Vedaldi |
---|
| 3 | ** description: Find local maximizer of multi-dimensional array. |
---|
| 4 | **/ |
---|
| 5 | |
---|
| 6 | /* AUTORIGHTS |
---|
| 7 | Copyright (C) 2006 Andrea Vedaldi |
---|
| 8 | |
---|
| 9 | This file is part of VLUtil. |
---|
| 10 | |
---|
| 11 | VLUtil is free software; you can redistribute it and/or modify |
---|
| 12 | it under the terms of the GNU General Public License as published by |
---|
| 13 | the Free Software Foundation; either version 2, or (at your option) |
---|
| 14 | any later version. |
---|
| 15 | |
---|
| 16 | This program is distributed in the hope that it will be useful, |
---|
| 17 | but WITHOUT ANY WARRANTY; without even the implied warranty of |
---|
| 18 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
---|
| 19 | GNU General Public License for more details. |
---|
| 20 | |
---|
| 21 | You should have received a copy of the GNU General Public License |
---|
| 22 | along with this program; if not, write to the Free Software Foundation, |
---|
| 23 | Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. |
---|
| 24 | */ |
---|
| 25 | |
---|
| 26 | #include"mex.h" |
---|
| 27 | #include<mexutils.c> |
---|
| 28 | #include<stdlib.h> |
---|
| 29 | |
---|
| 30 | /** Matlab driver. |
---|
| 31 | **/ |
---|
| 32 | #define greater(a,b) ((a) > (b)+threshold) |
---|
| 33 | |
---|
| 34 | void |
---|
| 35 | mexFunction(int nout, mxArray *out[], |
---|
| 36 | int nin, const mxArray *in[]) |
---|
| 37 | { |
---|
| 38 | int M, N ; |
---|
| 39 | const double* F_pt ; |
---|
| 40 | int ndims ; |
---|
| 41 | int pdims = -1 ; |
---|
| 42 | int* offsets ; |
---|
| 43 | int* midx ; |
---|
| 44 | int* neighbors ; |
---|
| 45 | int nneighbors ; |
---|
| 46 | int* dims ; |
---|
| 47 | enum {F=0,THRESHOLD,P} ; |
---|
| 48 | enum {MAXIMA=0} ; |
---|
| 49 | double threshold = - mxGetInf() ; |
---|
| 50 | |
---|
| 51 | /* ------------------------------------------------------------------ |
---|
| 52 | * Check the arguments |
---|
| 53 | * --------------------------------------------------------------- */ |
---|
| 54 | if (nin < 1) { |
---|
| 55 | mexErrMsgTxt("At least one input argument is required."); |
---|
| 56 | } else if (nin > 3) { |
---|
| 57 | mexErrMsgTxt("At most three arguments are allowed.") ; |
---|
| 58 | } else if (nout > 1) { |
---|
| 59 | mexErrMsgTxt("Too many output arguments"); |
---|
| 60 | } |
---|
| 61 | |
---|
| 62 | /* The input must be a real matrix. */ |
---|
| 63 | if (!mxIsDouble(in[F]) || mxIsComplex(in[F])) { |
---|
| 64 | mexErrMsgTxt("Input must be real matrix."); |
---|
| 65 | } |
---|
| 66 | |
---|
| 67 | if(nin > 1) { |
---|
| 68 | if(!uIsRealScalar(in[THRESHOLD])) { |
---|
| 69 | mexErrMsgTxt("THRESHOLD must be a real scalar.") ; |
---|
| 70 | } |
---|
| 71 | threshold = *mxGetPr(in[THRESHOLD]) ; |
---|
| 72 | } |
---|
| 73 | |
---|
| 74 | if(nin > 2) { |
---|
| 75 | if(!uIsRealScalar(in[P])) |
---|
| 76 | mexErrMsgTxt("P must be a non-negative integer") ; |
---|
| 77 | pdims = (int) *mxGetPr(in[P]) ; |
---|
| 78 | if(pdims < 0) |
---|
| 79 | mexErrMsgTxt("P must be a non-negative integer") ; |
---|
| 80 | } |
---|
| 81 | |
---|
| 82 | ndims = mxGetNumberOfDimensions(in[F]) ; |
---|
| 83 | { |
---|
| 84 | /* We need to make a copy because in one special case (see below) |
---|
| 85 | we need to adjust dims[]. |
---|
| 86 | */ |
---|
| 87 | int d ; |
---|
| 88 | dims = mxMalloc(sizeof(int)*ndims) ; |
---|
| 89 | const int* const_dims = mxGetDimensions(in[F]) ; |
---|
| 90 | for(d=0 ; d < ndims ; ++d) dims[d] = const_dims[d] ; |
---|
| 91 | } |
---|
| 92 | M = dims[0] ; |
---|
| 93 | N = dims[1] ; |
---|
| 94 | F_pt = mxGetPr(in[F]) ; |
---|
| 95 | |
---|
| 96 | /* |
---|
| 97 | If there are only two dimensions and if one is singleton, then |
---|
| 98 | assume that a vector has been provided as input (and treat this |
---|
| 99 | as a COLUMN matrix with p=1). We do this because Matlab does not |
---|
| 100 | distinguish between vectors and 1xN or Mx1 matrices and because |
---|
| 101 | the cases 1xN and Mx1 are trivial (the result is alway empty). |
---|
| 102 | */ |
---|
| 103 | if((ndims == 2) && (pdims < 0) && (M == 1 || N == 1)) { |
---|
| 104 | pdims = 1 ; |
---|
| 105 | M = (M>N)?M:N ; |
---|
| 106 | N = 1 ; |
---|
| 107 | dims[0]=M ; |
---|
| 108 | dims[1]=N ; |
---|
| 109 | } |
---|
| 110 | |
---|
| 111 | /* search the local maxima along the first p dimensions only */ |
---|
| 112 | if(pdims < 0) |
---|
| 113 | pdims = ndims ; |
---|
| 114 | |
---|
| 115 | if(pdims > ndims) { |
---|
| 116 | mxFree(dims) ; |
---|
| 117 | mexErrMsgTxt("P must not be greater than the number of dimensions") ; |
---|
| 118 | } |
---|
| 119 | |
---|
| 120 | /* ------------------------------------------------------------------ |
---|
| 121 | * Do the job |
---|
| 122 | * --------------------------------------------------------------- */ |
---|
| 123 | { |
---|
| 124 | int maxima_size = M*N ; |
---|
| 125 | int* maxima_start = mxMalloc(sizeof(int) * maxima_size) ; |
---|
| 126 | int* maxima_iterator = maxima_start ; |
---|
| 127 | int* maxima_end = maxima_start + maxima_size ; |
---|
| 128 | int i,h,o ; |
---|
| 129 | const double* pt = F_pt ; |
---|
| 130 | |
---|
| 131 | /* Compute the offsets between dimensions. */ |
---|
| 132 | offsets = mxMalloc(sizeof(int) * ndims) ; |
---|
| 133 | offsets[0] = 1 ; |
---|
| 134 | for(h = 1 ; h < ndims ; ++h) |
---|
| 135 | offsets[h] = offsets[h-1]*dims[h-1] ; |
---|
| 136 | |
---|
| 137 | /* Multi-index. */ |
---|
| 138 | midx = mxMalloc(sizeof(int) * ndims) ; |
---|
| 139 | for(h = 0 ; h < ndims ; ++h) |
---|
| 140 | midx[h] = 1 ; |
---|
| 141 | |
---|
| 142 | /* Neighbors. */ |
---|
| 143 | nneighbors = 1 ; |
---|
| 144 | o=0 ; |
---|
| 145 | for(h = 0 ; h < pdims ; ++h) { |
---|
| 146 | nneighbors *= 3 ; |
---|
| 147 | midx[h] = -1 ; |
---|
| 148 | o -= offsets[h] ; |
---|
| 149 | } |
---|
| 150 | nneighbors -= 1 ; |
---|
| 151 | neighbors = mxMalloc(sizeof(int) * nneighbors) ; |
---|
| 152 | i = 0 ; |
---|
| 153 | |
---|
| 154 | while(true) { |
---|
| 155 | if(o != 0 ) |
---|
| 156 | neighbors[i++] = o ; |
---|
| 157 | h = 0 ; |
---|
| 158 | while( o += offsets[h], (++midx[h]) > 1 ) { |
---|
| 159 | o -= 3*offsets[h] ; |
---|
| 160 | midx[h] = -1 ; |
---|
| 161 | if(++h >= pdims) |
---|
| 162 | goto stop ; |
---|
| 163 | } |
---|
| 164 | } |
---|
| 165 | stop: ; |
---|
| 166 | |
---|
| 167 | /* Starts at the corner (1,1,...,1,0,0,...0) */ |
---|
| 168 | for(h = 0 ; h < pdims ; ++h) { |
---|
| 169 | midx[h] = 1 ; |
---|
| 170 | pt += offsets[h] ; |
---|
| 171 | } |
---|
| 172 | for(h = pdims ; h < ndims ; ++h) { |
---|
| 173 | midx[h] = 0 ; |
---|
| 174 | } |
---|
| 175 | |
---|
| 176 | /* --------------------------------------------------------------- |
---|
| 177 | * Loop |
---|
| 178 | * ------------------------------------------------------------ */ |
---|
| 179 | |
---|
| 180 | /* |
---|
| 181 | If any dimension in the first P is less than 3 elements wide |
---|
| 182 | then just return the empty matrix (if we proceed without doing |
---|
| 183 | anything we break the carry reporting algorithm below). |
---|
| 184 | */ |
---|
| 185 | for(h=0 ; h < pdims ; ++h) |
---|
| 186 | if(dims[h] < 3) goto end ; |
---|
| 187 | |
---|
| 188 | while(true) { |
---|
| 189 | |
---|
| 190 | /* Propagate carry along multi index midx */ |
---|
| 191 | h = 0 ; |
---|
| 192 | while((midx[h]) >= dims[h] - 1) { |
---|
| 193 | pt += 2*offsets[h] ; /* skip first and last el. */ |
---|
| 194 | midx[h] = 1 ; |
---|
| 195 | if(++h >= pdims) |
---|
| 196 | goto next_layer ; |
---|
| 197 | ++midx[h] ; |
---|
| 198 | } |
---|
| 199 | |
---|
| 200 | /* |
---|
| 201 | for(h = 0 ; h < ndims ; ++h ) |
---|
| 202 | mexPrintf("%d ", midx[h]) ; |
---|
| 203 | mexPrintf(" -- %d -- pdims %d \n", pt - F_pt,pdims) ; |
---|
| 204 | */ |
---|
| 205 | |
---|
| 206 | /* Scan neighbors */ |
---|
| 207 | double v = *pt ; |
---|
| 208 | bool is_greater = (v >= threshold) ; |
---|
| 209 | i = 0 ; |
---|
| 210 | while(is_greater && i < nneighbors) |
---|
| 211 | is_greater &= v > *(pt + neighbors[i++]) ; |
---|
| 212 | |
---|
| 213 | /* Add the local maximum */ |
---|
| 214 | if(is_greater) { |
---|
| 215 | /* Need more space? */ |
---|
| 216 | if(maxima_iterator == maxima_end) { |
---|
| 217 | maxima_size += M*N ; |
---|
| 218 | maxima_start = mxRealloc(maxima_start, |
---|
| 219 | maxima_size*sizeof(int)) ; |
---|
| 220 | maxima_end = maxima_start + maxima_size ; |
---|
| 221 | maxima_iterator = maxima_end - M*N ; |
---|
| 222 | } |
---|
| 223 | |
---|
| 224 | *maxima_iterator++ = pt - F_pt + 1 ; |
---|
| 225 | } |
---|
| 226 | |
---|
| 227 | /* Go to next element */ |
---|
| 228 | pt += 1 ; |
---|
| 229 | ++midx[0] ; |
---|
| 230 | continue ; |
---|
| 231 | |
---|
| 232 | next_layer: ; |
---|
| 233 | if( h >= ndims ) |
---|
| 234 | goto end ; |
---|
| 235 | |
---|
| 236 | while((++midx[h]) >= dims[h]) { |
---|
| 237 | midx[h] = 0 ; |
---|
| 238 | if(++h >= ndims) |
---|
| 239 | goto end ; |
---|
| 240 | } |
---|
| 241 | } |
---|
| 242 | end:; |
---|
| 243 | /* Return. */ |
---|
| 244 | { |
---|
| 245 | double* M_pt ; |
---|
| 246 | out[MAXIMA] = mxCreateDoubleMatrix |
---|
| 247 | (1, maxima_iterator-maxima_start, mxREAL) ; |
---|
| 248 | maxima_end = maxima_iterator ; |
---|
| 249 | maxima_iterator = maxima_start ; |
---|
| 250 | M_pt = mxGetPr(out[MAXIMA]) ; |
---|
| 251 | while(maxima_iterator != maxima_end) { |
---|
| 252 | *M_pt++ = *maxima_iterator++ ; |
---|
| 253 | } |
---|
| 254 | } |
---|
| 255 | |
---|
| 256 | /* Release space. */ |
---|
| 257 | mxFree(offsets) ; |
---|
| 258 | mxFree(neighbors) ; |
---|
| 259 | mxFree(midx) ; |
---|
| 260 | mxFree(maxima_start) ; |
---|
| 261 | } |
---|
| 262 | mxFree(dims) ; |
---|
| 263 | } |
---|