vcs.maemo.org Git - opencv/blob - src/cv/cvdistransform.cpp

   1 /*M///////////////////////////////////////////////////////////////////////////////////////\r
   2 //\r
   3 //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.\r
   4 //\r
   5 //  By downloading, copying, installing or using the software you agree to this license.\r
   6 //  If you do not agree to this license, do not download, install,\r
   7 //  copy or use the software.\r
   8 //\r
   9 //\r
  10 //                        Intel License Agreement\r
  11 //                For Open Source Computer Vision Library\r
  12 //\r
  13 // Copyright (C) 2000, Intel Corporation, all rights reserved.\r
  14 // Third party copyrights are property of their respective owners.\r
  15 //\r
  16 // Redistribution and use in source and binary forms, with or without modification,\r
  17 // are permitted provided that the following conditions are met:\r
  18 //\r
  19 //   * Redistribution's of source code must retain the above copyright notice,\r
  20 //     this list of conditions and the following disclaimer.\r
  21 //\r
  22 //   * Redistribution's in binary form must reproduce the above copyright notice,\r
  23 //     this list of conditions and the following disclaimer in the documentation\r
  24 //     and/or other materials provided with the distribution.\r
  25 //\r
  26 //   * The name of Intel Corporation may not be used to endorse or promote products\r
  27 //     derived from this software without specific prior written permission.\r
  28 //\r
  29 // This software is provided by the copyright holders and contributors "as is" and\r
  30 // any express or implied warranties, including, but not limited to, the implied\r
  31 // warranties of merchantability and fitness for a particular purpose are disclaimed.\r
  32 // In no event shall the Intel Corporation or contributors be liable for any direct,\r
  33 // indirect, incidental, special, exemplary, or consequential damages\r
  34 // (including, but not limited to, procurement of substitute goods or services;\r
  35 // loss of use, data, or profits; or business interruption) however caused\r
  36 // and on any theory of liability, whether in contract, strict liability,\r
  37 // or tort (including negligence or otherwise) arising in any way out of\r
  38 // the use of this software, even if advised of the possibility of such damage.\r
  39 //\r
  40 //M*/\r
  41 #include "_cv.h"\r
  42 \r
  43 #define ICV_DIST_SHIFT  16\r
  44 #define ICV_INIT_DIST0  (INT_MAX >> 2)\r
  45 \r
  46 static CvStatus\r
  47 icvInitTopBottom( int* temp, int tempstep, CvSize size, int border )\r
  48 {\r
  49     int i, j;\r
  50     for( i = 0; i < border; i++ )\r
  51     {\r
  52         int* ttop = (int*)(temp + i*tempstep);\r
  53         int* tbottom = (int*)(temp + (size.height + border*2 - i - 1)*tempstep);\r
  54         \r
  55         for( j = 0; j < size.width + border*2; j++ )\r
  56         {\r
  57             ttop[j] = ICV_INIT_DIST0;\r
  58             tbottom[j] = ICV_INIT_DIST0;\r
  59         }\r
  60     }\r
  61 \r
  62     return CV_OK;\r
  63 }\r
  64 \r
  65 \r
  66 static CvStatus CV_STDCALL\r
  67 icvDistanceTransform_3x3_C1R( const uchar* src, int srcstep, int* temp,\r
  68         int step, float* dist, int dststep, CvSize size, const float* metrics )\r
  69 {\r
  70     const int BORDER = 1;\r
  71     int i, j;\r
  72     const int HV_DIST = CV_FLT_TO_FIX( metrics[0], ICV_DIST_SHIFT );\r
  73     const int DIAG_DIST = CV_FLT_TO_FIX( metrics[1], ICV_DIST_SHIFT );\r
  74     const float scale = 1.f/(1 << ICV_DIST_SHIFT);\r
  75 \r
  76     srcstep /= sizeof(src[0]);\r
  77     step /= sizeof(temp[0]);\r
  78     dststep /= sizeof(dist[0]);\r
  79 \r
  80     icvInitTopBottom( temp, step, size, BORDER );\r
  81 \r
  82     // forward pass\r
  83     for( i = 0; i < size.height; i++ )\r
  84     {\r
  85         const uchar* s = src + i*srcstep;\r
  86         int* tmp = (int*)(temp + (i+BORDER)*step) + BORDER;\r
  87 \r
  88         for( j = 0; j < BORDER; j++ )\r
  89             tmp[-j-1] = tmp[size.width + j] = ICV_INIT_DIST0;\r
  90         \r
  91         for( j = 0; j < size.width; j++ )\r
  92         {\r
  93             if( !s[j] )\r
  94                 tmp[j] = 0;\r
  95             else\r
  96             {\r
  97                 int t0 = tmp[j-step-1] + DIAG_DIST;\r
  98                 int t = tmp[j-step] + HV_DIST;\r
  99                 if( t0 > t ) t0 = t;\r
 100                 t = tmp[j-step+1] + DIAG_DIST;\r
 101                 if( t0 > t ) t0 = t;\r
 102                 t = tmp[j-1] + HV_DIST;\r
 103                 if( t0 > t ) t0 = t;\r
 104                 tmp[j] = t0;\r
 105             }\r
 106         }\r
 107     }\r
 108 \r
 109     // backward pass\r
 110     for( i = size.height - 1; i >= 0; i-- )\r
 111     {\r
 112         float* d = (float*)(dist + i*dststep);\r
 113         int* tmp = (int*)(temp + (i+BORDER)*step) + BORDER;\r
 114         \r
 115         for( j = size.width - 1; j >= 0; j-- )\r
 116         {\r
 117             int t0 = tmp[j];\r
 118             if( t0 > HV_DIST )\r
 119             {\r
 120                 int t = tmp[j+step+1] + DIAG_DIST;\r
 121                 if( t0 > t ) t0 = t;\r
 122                 t = tmp[j+step] + HV_DIST;\r
 123                 if( t0 > t ) t0 = t;\r
 124                 t = tmp[j+step-1] + DIAG_DIST;\r
 125                 if( t0 > t ) t0 = t;\r
 126                 t = tmp[j+1] + HV_DIST;\r
 127                 if( t0 > t ) t0 = t;\r
 128                 tmp[j] = t0;\r
 129             }\r
 130             d[j] = (float)(t0 * scale);\r
 131         }\r
 132     }\r
 133 \r
 134     return CV_OK;\r
 135 }\r
 136 \r
 137 \r
 138 static CvStatus CV_STDCALL\r
 139 icvDistanceTransform_5x5_C1R( const uchar* src, int srcstep, int* temp,\r
 140         int step, float* dist, int dststep, CvSize size, const float* metrics )\r
 141 {\r
 142     const int BORDER = 2;\r
 143     int i, j;\r
 144     const int HV_DIST = CV_FLT_TO_FIX( metrics[0], ICV_DIST_SHIFT );\r
 145     const int DIAG_DIST = CV_FLT_TO_FIX( metrics[1], ICV_DIST_SHIFT );\r
 146     const int LONG_DIST = CV_FLT_TO_FIX( metrics[2], ICV_DIST_SHIFT );\r
 147     const float scale = 1.f/(1 << ICV_DIST_SHIFT);\r
 148 \r
 149     srcstep /= sizeof(src[0]);\r
 150     step /= sizeof(temp[0]);\r
 151     dststep /= sizeof(dist[0]);\r
 152 \r
 153     icvInitTopBottom( temp, step, size, BORDER );\r
 154 \r
 155     // forward pass\r
 156     for( i = 0; i < size.height; i++ )\r
 157     {\r
 158         const uchar* s = src + i*srcstep;\r
 159         int* tmp = (int*)(temp + (i+BORDER)*step) + BORDER;\r
 160 \r
 161         for( j = 0; j < BORDER; j++ )\r
 162             tmp[-j-1] = tmp[size.width + j] = ICV_INIT_DIST0;\r
 163         \r
 164         for( j = 0; j < size.width; j++ )\r
 165         {\r
 166             if( !s[j] )\r
 167                 tmp[j] = 0;\r
 168             else\r
 169             {\r
 170                 int t0 = tmp[j-step*2-1] + LONG_DIST;\r
 171                 int t = tmp[j-step*2+1] + LONG_DIST;\r
 172                 if( t0 > t ) t0 = t;\r
 173                 t = tmp[j-step-2] + LONG_DIST;\r
 174                 if( t0 > t ) t0 = t;\r
 175                 t = tmp[j-step-1] + DIAG_DIST;\r
 176                 if( t0 > t ) t0 = t;\r
 177                 t = tmp[j-step] + HV_DIST;\r
 178                 if( t0 > t ) t0 = t;\r
 179                 t = tmp[j-step+1] + DIAG_DIST;\r
 180                 if( t0 > t ) t0 = t;\r
 181                 t = tmp[j-step+2] + LONG_DIST;\r
 182                 if( t0 > t ) t0 = t;\r
 183                 t = tmp[j-1] + HV_DIST;\r
 184                 if( t0 > t ) t0 = t;\r
 185                 tmp[j] = t0;\r
 186             }\r
 187         }\r
 188     }\r
 189 \r
 190     // backward pass\r
 191     for( i = size.height - 1; i >= 0; i-- )\r
 192     {\r
 193         float* d = (float*)(dist + i*dststep);\r
 194         int* tmp = (int*)(temp + (i+BORDER)*step) + BORDER;\r
 195         \r
 196         for( j = size.width - 1; j >= 0; j-- )\r
 197         {\r
 198             int t0 = tmp[j];\r
 199             if( t0 > HV_DIST )\r
 200             {\r
 201                 int t = tmp[j+step*2+1] + LONG_DIST;\r
 202                 if( t0 > t ) t0 = t;\r
 203                 t = tmp[j+step*2-1] + LONG_DIST;\r
 204                 if( t0 > t ) t0 = t;\r
 205                 t = tmp[j+step+2] + LONG_DIST;\r
 206                 if( t0 > t ) t0 = t;\r
 207                 t = tmp[j+step+1] + DIAG_DIST;\r
 208                 if( t0 > t ) t0 = t;\r
 209                 t = tmp[j+step] + HV_DIST;\r
 210                 if( t0 > t ) t0 = t;\r
 211                 t = tmp[j+step-1] + DIAG_DIST;\r
 212                 if( t0 > t ) t0 = t;\r
 213                 t = tmp[j+step-2] + LONG_DIST;\r
 214                 if( t0 > t ) t0 = t;\r
 215                 t = tmp[j+1] + HV_DIST;\r
 216                 if( t0 > t ) t0 = t;\r
 217                 tmp[j] = t0;\r
 218             }\r
 219             d[j] = (float)(t0 * scale);\r
 220         }\r
 221     }\r
 222 \r
 223     return CV_OK;\r
 224 }\r
 225 \r
 226 \r
 227 static CvStatus CV_STDCALL\r
 228 icvDistanceTransformEx_5x5_C1R( const uchar* src, int srcstep, int* temp,\r
 229                 int step, float* dist, int dststep, int* labels, int lstep,\r
 230                 CvSize size, const float* metrics )\r
 231 {\r
 232     const int BORDER = 2;\r
 233     \r
 234     int i, j;\r
 235     const int HV_DIST = CV_FLT_TO_FIX( metrics[0], ICV_DIST_SHIFT );\r
 236     const int DIAG_DIST = CV_FLT_TO_FIX( metrics[1], ICV_DIST_SHIFT );\r
 237     const int LONG_DIST = CV_FLT_TO_FIX( metrics[2], ICV_DIST_SHIFT );\r
 238     const float scale = 1.f/(1 << ICV_DIST_SHIFT);\r
 239 \r
 240     srcstep /= sizeof(src[0]);\r
 241     step /= sizeof(temp[0]);\r
 242     dststep /= sizeof(dist[0]);\r
 243     lstep /= sizeof(labels[0]);\r
 244 \r
 245     icvInitTopBottom( temp, step, size, BORDER );\r
 246 \r
 247     // forward pass\r
 248     for( i = 0; i < size.height; i++ )\r
 249     {\r
 250         const uchar* s = src + i*srcstep;\r
 251         int* tmp = (int*)(temp + (i+BORDER)*step) + BORDER;\r
 252         int* lls = (int*)(labels + i*lstep);\r
 253 \r
 254         for( j = 0; j < BORDER; j++ )\r
 255             tmp[-j-1] = tmp[size.width + j] = ICV_INIT_DIST0;\r
 256         \r
 257         for( j = 0; j < size.width; j++ )\r
 258         {\r
 259             if( !s[j] )\r
 260             {\r
 261                 tmp[j] = 0;\r
 262                 //assert( lls[j] != 0 );\r
 263             }\r
 264             else\r
 265             {\r
 266                 int t0 = ICV_INIT_DIST0, t;\r
 267                 int l0 = 0;\r
 268 \r
 269                 t = tmp[j-step*2-1] + LONG_DIST;\r
 270                 if( t0 > t )\r
 271                 {\r
 272                     t0 = t;\r
 273                     l0 = lls[j-lstep*2-1];\r
 274                 }\r
 275                 t = tmp[j-step*2+1] + LONG_DIST;\r
 276                 if( t0 > t )\r
 277                 {\r
 278                     t0 = t;\r
 279                     l0 = lls[j-lstep*2+1];\r
 280                 }\r
 281                 t = tmp[j-step-2] + LONG_DIST;\r
 282                 if( t0 > t )\r
 283                 {\r
 284                     t0 = t;\r
 285                     l0 = lls[j-lstep-2];\r
 286                 }\r
 287                 t = tmp[j-step-1] + DIAG_DIST;\r
 288                 if( t0 > t )\r
 289                 {\r
 290                     t0 = t;\r
 291                     l0 = lls[j-lstep-1];\r
 292                 }\r
 293                 t = tmp[j-step] + HV_DIST;\r
 294                 if( t0 > t )\r
 295                 {\r
 296                     t0 = t;\r
 297                     l0 = lls[j-lstep];\r
 298                 }\r
 299                 t = tmp[j-step+1] + DIAG_DIST;\r
 300                 if( t0 > t )\r
 301                 {\r
 302                     t0 = t;\r
 303                     l0 = lls[j-lstep+1];\r
 304                 }\r
 305                 t = tmp[j-step+2] + LONG_DIST;\r
 306                 if( t0 > t )\r
 307                 {\r
 308                     t0 = t;\r
 309                     l0 = lls[j-lstep+2];\r
 310                 }\r
 311                 t = tmp[j-1] + HV_DIST;\r
 312                 if( t0 > t )\r
 313                 {\r
 314                     t0 = t;\r
 315                     l0 = lls[j-1];\r
 316                 }\r
 317 \r
 318                 tmp[j] = t0;\r
 319                 lls[j] = l0;\r
 320             }\r
 321         }\r
 322     }\r
 323 \r
 324     // backward pass\r
 325     for( i = size.height - 1; i >= 0; i-- )\r
 326     {\r
 327         float* d = (float*)(dist + i*dststep);\r
 328         int* tmp = (int*)(temp + (i+BORDER)*step) + BORDER;\r
 329         int* lls = (int*)(labels + i*lstep);\r
 330         \r
 331         for( j = size.width - 1; j >= 0; j-- )\r
 332         {\r
 333             int t0 = tmp[j];\r
 334             int l0 = lls[j];\r
 335             if( t0 > HV_DIST )\r
 336             {\r
 337                 int t = tmp[j+step*2+1] + LONG_DIST;\r
 338                 if( t0 > t )\r
 339                 {\r
 340                     t0 = t;\r
 341                     l0 = lls[j+lstep*2+1];\r
 342                 }\r
 343                 t = tmp[j+step*2-1] + LONG_DIST;\r
 344                 if( t0 > t )\r
 345                 {\r
 346                     t0 = t;\r
 347                     l0 = lls[j+lstep*2-1];\r
 348                 }\r
 349                 t = tmp[j+step+2] + LONG_DIST;\r
 350                 if( t0 > t )\r
 351                 {\r
 352                     t0 = t;\r
 353                     l0 = lls[j+lstep+2];\r
 354                 }\r
 355                 t = tmp[j+step+1] + DIAG_DIST;\r
 356                 if( t0 > t )\r
 357                 {\r
 358                     t0 = t;\r
 359                     l0 = lls[j+lstep+1];\r
 360                 }\r
 361                 t = tmp[j+step] + HV_DIST;\r
 362                 if( t0 > t )\r
 363                 {\r
 364                     t0 = t;\r
 365                     l0 = lls[j+lstep];\r
 366                 }\r
 367                 t = tmp[j+step-1] + DIAG_DIST;\r
 368                 if( t0 > t )\r
 369                 {\r
 370                     t0 = t;\r
 371                     l0 = lls[j+lstep-1];\r
 372                 }\r
 373                 t = tmp[j+step-2] + LONG_DIST;\r
 374                 if( t0 > t )\r
 375                 {\r
 376                     t0 = t;\r
 377                     l0 = lls[j+lstep-2];\r
 378                 }\r
 379                 t = tmp[j+1] + HV_DIST;\r
 380                 if( t0 > t )\r
 381                 {\r
 382                     t0 = t;\r
 383                     l0 = lls[j+1];\r
 384                 }\r
 385                 tmp[j] = t0;\r
 386                 lls[j] = l0;\r
 387             }\r
 388             d[j] = (float)(t0 * scale);\r
 389         }\r
 390     }\r
 391 \r
 392     return CV_OK;\r
 393 }\r
 394 \r
 395 \r
 396 static CvStatus\r
 397 icvGetDistanceTransformMask( int maskType, float *metrics )\r
 398 {\r
 399     if( !metrics )\r
 400         return CV_NULLPTR_ERR;\r
 401 \r
 402     switch (maskType)\r
 403     {\r
 404     case 30:\r
 405         metrics[0] = 1.0f;\r
 406         metrics[1] = 1.0f;\r
 407         break;\r
 408 \r
 409     case 31:\r
 410         metrics[0] = 1.0f;\r
 411         metrics[1] = 2.0f;\r
 412         break;\r
 413 \r
 414     case 32:\r
 415         metrics[0] = 0.955f;\r
 416         metrics[1] = 1.3693f;\r
 417         break;\r
 418 \r
 419     case 50:\r
 420         metrics[0] = 1.0f;\r
 421         metrics[1] = 1.0f;\r
 422         metrics[2] = 2.0f;\r
 423         break;\r
 424 \r
 425     case 51:\r
 426         metrics[0] = 1.0f;\r
 427         metrics[1] = 2.0f;\r
 428         metrics[2] = 3.0f;\r
 429         break;\r
 430 \r
 431     case 52:\r
 432         metrics[0] = 1.0f;\r
 433         metrics[1] = 1.4f;\r
 434         metrics[2] = 2.1969f;\r
 435         break;\r
 436     default:\r
 437         return CV_BADRANGE_ERR;\r
 438     }\r
 439 \r
 440     return CV_OK;\r
 441 }\r
 442 \r
 443 \r
 444 static void\r
 445 icvTrueDistTrans( const CvMat* src, CvMat* dst )\r
 446 {\r
 447     CvMat* buffer = 0;\r
 448 \r
 449     CV_FUNCNAME( "cvDistTransform2" );\r
 450 \r
 451     __BEGIN__;\r
 452 \r
 453     int i, m, n;\r
 454     int sstep, dstep;\r
 455     const float inf = 1e6f;\r
 456     int thread_count = cvGetNumThreads();\r
 457     int pass1_sz, pass2_sz;\r
 458 \r
 459     if( !CV_ARE_SIZES_EQ( src, dst ))\r
 460         CV_ERROR( CV_StsUnmatchedSizes, "" );\r
 461 \r
 462     if( CV_MAT_TYPE(src->type) != CV_8UC1 ||\r
 463         CV_MAT_TYPE(dst->type) != CV_32FC1 )\r
 464         CV_ERROR( CV_StsUnsupportedFormat,\r
 465         "The input image must have 8uC1 type and the output one must have 32fC1 type" );\r
 466 \r
 467     m = src->rows;\r
 468     n = src->cols;\r
 469 \r
 470     // (see stage 1 below):\r
 471     // sqr_tab: 2*m, sat_tab: 3*m + 1, d: m*thread_count,\r
 472     pass1_sz = src->rows*(5 + thread_count) + 1;\r
 473     // (see stage 2):\r
 474     // sqr_tab & inv_tab: n each; f & v: n*thread_count each; z: (n+1)*thread_count\r
 475     pass2_sz = src->cols*(2 + thread_count*3) + thread_count;\r
 476     CV_CALL( buffer = cvCreateMat( 1, MAX(pass1_sz, pass2_sz), CV_32FC1 ));\r
 477 \r
 478     sstep = src->step;\r
 479     dstep = dst->step / sizeof(float);\r
 480 \r
 481     // stage 1: compute 1d distance transform of each column\r
 482     {\r
 483     float* sqr_tab = buffer->data.fl;\r
 484     int* sat_tab = (int*)(sqr_tab + m*2);\r
 485     const int shift = m*2;\r
 486 \r
 487     for( i = 0; i < m; i++ )\r
 488         sqr_tab[i] = (float)(i*i);\r
 489     for( i = m; i < m*2; i++ )\r
 490         sqr_tab[i] = inf;\r
 491     for( i = 0; i < shift; i++ )\r
 492         sat_tab[i] = 0;\r
 493     for( ; i <= m*3; i++ )\r
 494         sat_tab[i] = i - shift;\r
 495 \r
 496 #ifdef _OPENMP\r
 497     #pragma omp parallel for num_threads(thread_count)\r
 498 #endif\r
 499     for( i = 0; i < n; i++ )\r
 500     {\r
 501         const uchar* sptr = src->data.ptr + i + (m-1)*sstep;\r
 502         float* dptr = dst->data.fl + i;\r
 503         int* d = (int*)(sat_tab + m*3+1+m*cvGetThreadNum());\r
 504         int j, dist = m-1;\r
 505 \r
 506         for( j = m-1; j >= 0; j--, sptr -= sstep )\r
 507         {\r
 508             dist = (dist + 1) & (sptr[0] == 0 ? 0 : -1);\r
 509             d[j] = dist;\r
 510         }\r
 511 \r
 512         dist = m-1;\r
 513         for( j = 0; j < m; j++, dptr += dstep )\r
 514         {\r
 515             dist = dist + 1 - sat_tab[dist + 1 - d[j] + shift];\r
 516             d[j] = dist;\r
 517             dptr[0] = sqr_tab[dist];\r
 518         }\r
 519     }\r
 520     }\r
 521 \r
 522     // stage 2: compute modified distance transform for each row\r
 523     {\r
 524     float* inv_tab = buffer->data.fl;\r
 525     float* sqr_tab = inv_tab + n;\r
 526 \r
 527     inv_tab[0] = sqr_tab[0] = 0.f;\r
 528     for( i = 1; i < n; i++ )\r
 529     {\r
 530         inv_tab[i] = (float)(0.5/i);\r
 531         sqr_tab[i] = (float)(i*i);\r
 532     }\r
 533 \r
 534 #ifdef _OPENMP\r
 535     #pragma omp parallel for num_threads(thread_count) schedule(dynamic)\r
 536 #endif\r
 537     for( i = 0; i < m; i++ )\r
 538     {\r
 539         float* d = (float*)(dst->data.ptr + i*dst->step);\r
 540         float* f = sqr_tab + n + (n*3+1)*cvGetThreadNum();\r
 541         float* z = f + n;\r
 542         int* v = (int*)(z + n + 1);\r
 543         int p, q, k;\r
 544 \r
 545         v[0] = 0;\r
 546         z[0] = -inf;\r
 547         z[1] = inf;\r
 548         f[0] = d[0];\r
 549 \r
 550         for( q = 1, k = 0; q < n; q++ )\r
 551         {\r
 552             float fq = d[q];\r
 553             f[q] = fq;\r
 554 \r
 555             for(;;k--)\r
 556             {\r
 557                 p = v[k];\r
 558                 float s = (fq + sqr_tab[q] - d[p] - sqr_tab[p])*inv_tab[q - p];\r
 559                 if( s > z[k] )\r
 560                 {\r
 561                     k++;\r
 562                     v[k] = q;\r
 563                     z[k] = s;\r
 564                     z[k+1] = inf;\r
 565                     break;\r
 566                 }\r
 567             }\r
 568         }\r
 569 \r
 570         for( q = 0, k = 0; q < n; q++ )\r
 571         {\r
 572             while( z[k+1] < q )\r
 573                 k++;\r
 574             p = v[k];\r
 575             d[q] = sqr_tab[abs(q - p)] + f[p];\r
 576         }\r
 577     }\r
 578     }\r
 579 \r
 580     cvPow( dst, dst, 0.5 );\r
 581 \r
 582     __END__;\r
 583 \r
 584     cvReleaseMat( &buffer );\r
 585 }\r
 586 \r
 587 \r
 588 /*********************************** IPP functions *********************************/\r
 589 \r
 590 typedef CvStatus (CV_STDCALL * CvIPPDistTransFunc)( const uchar* src, int srcstep,\r
 591                                                     void* dst, int dststep,\r
 592                                                     CvSize size, const void* metrics );\r
 593 \r
 594 typedef CvStatus (CV_STDCALL * CvIPPDistTransFunc2)( uchar* src, int srcstep,\r
 595                                                      CvSize size, const int* metrics );\r
 596 \r
 597 /***********************************************************************************/\r
 598 \r
 599 typedef CvStatus (CV_STDCALL * CvDistTransFunc)( const uchar* src, int srcstep,\r
 600                                                  int* temp, int tempstep,\r
 601                                                  float* dst, int dststep,\r
 602                                                  CvSize size, const float* metrics );\r
 603 \r
 604 \r
 605 /****************************************************************************************\\r
 606  Non-inplace and Inplace 8u->8u Distance Transform for CityBlock (a.k.a. L1) metric\r
 607  (C) 2006 by Jay Stavinzky.\r
 608 \****************************************************************************************/\r
 609 \r
 610 //BEGIN ATS ADDITION\r
 611 /* 8-bit grayscale distance transform function */\r
 612 static void\r
 613 icvDistanceATS_L1_8u( const CvMat* src, CvMat* dst )\r
 614 {\r
 615     CV_FUNCNAME( "cvDistanceATS" );\r
 616 \r
 617     __BEGIN__;\r
 618 \r
 619     int width = src->cols, height = src->rows;\r
 620 \r
 621     int a;\r
 622     uchar lut[256];\r
 623     int x, y;\r
 624     \r
 625     const uchar *sbase = src->data.ptr;\r
 626     uchar *dbase = dst->data.ptr;\r
 627     int srcstep = src->step;\r
 628     int dststep = dst->step;\r
 629 \r
 630     CV_ASSERT( CV_IS_MASK_ARR( src ) && CV_MAT_TYPE( dst->type ) == CV_8UC1 );\r
 631     CV_ASSERT( CV_ARE_SIZES_EQ( src, dst ));\r
 632 \r
 633     ////////////////////// forward scan ////////////////////////\r
 634     for( x = 0; x < 256; x++ )\r
 635         lut[x] = CV_CAST_8U(x+1);\r
 636 \r
 637     //init first pixel to max (we're going to be skipping it)\r
 638     dbase[0] = (uchar)(sbase[0] == 0 ? 0 : 255);\r
 639 \r
 640     //first row (scan west only, skip first pixel)\r
 641     for( x = 1; x < width; x++ )\r
 642         dbase[x] = (uchar)(sbase[x] == 0 ? 0 : lut[dbase[x-1]]);\r
 643 \r
 644     for( y = 1; y < height; y++ )\r
 645     {\r
 646         sbase += srcstep;\r
 647         dbase += dststep;\r
 648 \r
 649         //for left edge, scan north only\r
 650         a = sbase[0] == 0 ? 0 : lut[dbase[-dststep]];\r
 651         dbase[0] = (uchar)a;\r
 652 \r
 653         for( x = 1; x < width; x++ )\r
 654         {\r
 655             a = sbase[x] == 0 ? 0 : lut[MIN(a, dbase[x - dststep])];\r
 656             dbase[x] = (uchar)a;\r
 657         }\r
 658     }\r
 659 \r
 660     ////////////////////// backward scan ///////////////////////\r
 661 \r
 662     a = dbase[width-1];\r
 663 \r
 664     // do last row east pixel scan here (skip bottom right pixel)\r
 665     for( x = width - 2; x >= 0; x-- )\r
 666     {\r
 667         a = lut[a];\r
 668         dbase[x] = (uchar)(CV_CALC_MIN_8U(a, dbase[x]));\r
 669     }\r
 670 \r
 671     // right edge is the only error case\r
 672     for( y = height - 2; y >= 0; y-- )\r
 673     {\r
 674         dbase -= dststep;\r
 675 \r
 676         // do right edge\r
 677         a = lut[dbase[width-1+dststep]];\r
 678         dbase[width-1] = (uchar)(MIN(a, dbase[width-1]));\r
 679 \r
 680         for( x = width - 2; x >= 0; x-- )\r
 681         {\r
 682             int b = dbase[x+dststep];\r
 683             a = lut[MIN(a, b)];\r
 684             dbase[x] = (uchar)(MIN(a, dbase[x]));\r
 685         }\r
 686     }\r
 687 \r
 688     __END__;\r
 689 }\r
 690 //END ATS ADDITION\r
 691 \r
 692 \r
 693 /* Wrapper function for distance transform group */\r
 694 CV_IMPL void\r
 695 cvDistTransform( const void* srcarr, void* dstarr,\r
 696                  int distType, int maskSize,\r
 697                  const float *mask,\r
 698                  void* labelsarr )\r
 699 {\r
 700     CvMat* temp = 0;\r
 701     CvMat* src_copy = 0;\r
 702     CvMemStorage* st = 0;\r
 703     \r
 704     CV_FUNCNAME( "cvDistTransform" );\r
 705 \r
 706     __BEGIN__;\r
 707 \r
 708     float _mask[5] = {0};\r
 709     CvMat srcstub, *src = (CvMat*)srcarr;\r
 710     CvMat dststub, *dst = (CvMat*)dstarr;\r
 711     CvMat lstub, *labels = (CvMat*)labelsarr;\r
 712     CvSize size;\r
 713     //CvIPPDistTransFunc ipp_func = 0;\r
 714     //CvIPPDistTransFunc2 ipp_inp_func = 0;\r
 715 \r
 716     CV_CALL( src = cvGetMat( src, &srcstub ));\r
 717     CV_CALL( dst = cvGetMat( dst, &dststub ));\r
 718 \r
 719     if( !CV_IS_MASK_ARR( src ) || (CV_MAT_TYPE( dst->type ) != CV_32FC1 &&\r
 720         (CV_MAT_TYPE(dst->type) != CV_8UC1 || distType != CV_DIST_L1 || labels)) )\r
 721         CV_ERROR( CV_StsUnsupportedFormat,\r
 722         "source image must be 8uC1 and the distance map must be 32fC1 "\r
 723         "(or 8uC1 in case of simple L1 distance transform)" );\r
 724 \r
 725     if( !CV_ARE_SIZES_EQ( src, dst ))\r
 726         CV_ERROR( CV_StsUnmatchedSizes, "the source and the destination images must be of the same size" );\r
 727 \r
 728     if( maskSize != CV_DIST_MASK_3 && maskSize != CV_DIST_MASK_5 && maskSize != CV_DIST_MASK_PRECISE )\r
 729         CV_ERROR( CV_StsBadSize, "Mask size should be 3 or 5 or 0 (presize)" );\r
 730 \r
 731     if( distType == CV_DIST_C || distType == CV_DIST_L1 )\r
 732         maskSize = !labels ? CV_DIST_MASK_3 : CV_DIST_MASK_5;\r
 733     else if( distType == CV_DIST_L2 && labels )\r
 734         maskSize = CV_DIST_MASK_5;\r
 735 \r
 736     if( maskSize == CV_DIST_MASK_PRECISE )\r
 737     {\r
 738         CV_CALL( icvTrueDistTrans( src, dst ));\r
 739         EXIT;\r
 740     }\r
 741     \r
 742     if( labels )\r
 743     {\r
 744         CV_CALL( labels = cvGetMat( labels, &lstub ));\r
 745         if( CV_MAT_TYPE( labels->type ) != CV_32SC1 )\r
 746             CV_ERROR( CV_StsUnsupportedFormat, "the output array of labels must be 32sC1" );\r
 747 \r
 748         if( !CV_ARE_SIZES_EQ( labels, dst ))\r
 749             CV_ERROR( CV_StsUnmatchedSizes, "the array of labels has a different size" );\r
 750 \r
 751         if( maskSize == CV_DIST_MASK_3 )\r
 752             CV_ERROR( CV_StsNotImplemented,\r
 753             "3x3 mask can not be used for \"labeled\" distance transform. Use 5x5 mask" );\r
 754     }\r
 755 \r
 756     if( distType == CV_DIST_C || distType == CV_DIST_L1 || distType == CV_DIST_L2 )\r
 757     {\r
 758         icvGetDistanceTransformMask( (distType == CV_DIST_C ? 0 :\r
 759             distType == CV_DIST_L1 ? 1 : 2) + maskSize*10, _mask );\r
 760     }\r
 761     else if( distType == CV_DIST_USER )\r
 762     {\r
 763         if( !mask )\r
 764             CV_ERROR( CV_StsNullPtr, "" );\r
 765 \r
 766         memcpy( _mask, mask, (maskSize/2 + 1)*sizeof(float));\r
 767     }\r
 768 \r
 769     /*if( !labels )\r
 770     {\r
 771         if( CV_MAT_TYPE(dst->type) == CV_32FC1 )\r
 772             ipp_func = (CvIPPDistTransFunc)(maskSize == CV_DIST_MASK_3 ?\r
 773                 icvDistanceTransform_3x3_8u32f_C1R_p : icvDistanceTransform_5x5_8u32f_C1R_p);\r
 774         else if( src->data.ptr != dst->data.ptr )\r
 775             ipp_func = (CvIPPDistTransFunc)icvDistanceTransform_3x3_8u_C1R_p;\r
 776         else\r
 777             ipp_inp_func = icvDistanceTransform_3x3_8u_C1IR_p;\r
 778     }*/\r
 779 \r
 780     size = cvGetMatSize(src);\r
 781 \r
 782     /*if( (ipp_func || ipp_inp_func) && src->cols >= 4 && src->rows >= 2 )\r
 783     {\r
 784         int _imask[3];\r
 785         _imask[0] = cvRound(_mask[0]);\r
 786         _imask[1] = cvRound(_mask[1]);\r
 787         _imask[2] = cvRound(_mask[2]);\r
 788 \r
 789         if( ipp_func )\r
 790         {\r
 791             IPPI_CALL( ipp_func( src->data.ptr, src->step,\r
 792                     dst->data.fl, dst->step, size,\r
 793                     CV_MAT_TYPE(dst->type) == CV_8UC1 ?\r
 794                     (void*)_imask : (void*)_mask ));\r
 795         }\r
 796         else\r
 797         {\r
 798             IPPI_CALL( ipp_inp_func( src->data.ptr, src->step, size, _imask ));\r
 799         }\r
 800     }\r
 801     else*/ if( CV_MAT_TYPE(dst->type) == CV_8UC1 )\r
 802     {\r
 803         CV_CALL( icvDistanceATS_L1_8u( src, dst ));\r
 804     }\r
 805     else\r
 806     {\r
 807         int border = maskSize == CV_DIST_MASK_3 ? 1 : 2;\r
 808         CV_CALL( temp = cvCreateMat( size.height + border*2, size.width + border*2, CV_32SC1 ));\r
 809 \r
 810         if( !labels )\r
 811         {\r
 812             CvDistTransFunc func = maskSize == CV_DIST_MASK_3 ?\r
 813                 icvDistanceTransform_3x3_C1R :\r
 814                 icvDistanceTransform_5x5_C1R;\r
 815 \r
 816             func( src->data.ptr, src->step, temp->data.i, temp->step,\r
 817                   dst->data.fl, dst->step, size, _mask );\r
 818         }\r
 819         else\r
 820         {\r
 821             CvSeq *contours = 0;\r
 822             CvPoint top_left = {0,0}, bottom_right = {size.width-1,size.height-1};\r
 823             int label;\r
 824 \r
 825             CV_CALL( st = cvCreateMemStorage() );\r
 826             CV_CALL( src_copy = cvCreateMat( size.height, size.width, src->type ));\r
 827             cvCmpS( src, 0, src_copy, CV_CMP_EQ );\r
 828             cvFindContours( src_copy, st, &contours, sizeof(CvContour),\r
 829                             CV_RETR_CCOMP, CV_CHAIN_APPROX_SIMPLE );\r
 830             cvZero( labels );\r
 831             for( label = 1; contours != 0; contours = contours->h_next, label++ )\r
 832             {\r
 833                 CvScalar area_color = cvScalarAll(label);\r
 834                 cvDrawContours( labels, contours, area_color, area_color, -255, -1, 8 );\r
 835             }\r
 836 \r
 837             cvCopy( src, src_copy );\r
 838             cvRectangle( src_copy, top_left, bottom_right, cvScalarAll(255), 1, 8 );\r
 839 \r
 840             icvDistanceTransformEx_5x5_C1R( src_copy->data.ptr, src_copy->step, temp->data.i, temp->step,\r
 841                         dst->data.fl, dst->step, labels->data.i, labels->step, size, _mask );\r
 842         }\r
 843     }\r
 844 \r
 845     __END__;\r
 846 \r
 847     cvReleaseMat( &temp );\r
 848     cvReleaseMat( &src_copy );\r
 849     cvReleaseMemStorage( &st );\r
 850 }\r
 851 \r
 852 void cv::distanceTransform( const Mat& src, Mat& dst, Mat& labels,\r
 853                             int distanceType, int maskSize )\r
 854 {\r
 855     dst.create(src.size(), CV_32F);\r
 856     dst.create(src.size(), CV_32S);\r
 857     CvMat _src = src, _dst = dst, _labels = labels;\r
 858     cvDistTransform(&_src, &_dst, distanceType, maskSize, 0, &_labels);\r
 859 }\r
 860 \r
 861 void cv::distanceTransform( const Mat& src, Mat& dst,\r
 862                             int distanceType, int maskSize )\r
 863 {\r
 864     dst.create(src.size(), CV_32F);\r
 865     CvMat _src = src, _dst = dst;\r
 866     cvDistTransform(&_src, &_dst, distanceType, maskSize, 0, 0);\r
 867 }\r
 868 \r
 869 /* End of file. */\r