dt.h
Go to the documentation of this file.
00001 /*
00002 Copyright (C) 2006 Pedro Felzenszwalb
00003 
00004 This program is free software; you can redistribute it and/or modify
00005 it under the terms of the GNU General Public License as published by
00006 the Free Software Foundation; either version 2 of the License, or
00007 (at your option) any later version.
00008 
00009 This program is distributed in the hope that it will be useful,
00010 but WITHOUT ANY WARRANTY; without even the implied warranty of
00011 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012 GNU General Public License for more details.
00013 
00014 You should have received a copy of the GNU General Public License
00015 along with this program; if not, write to the Free Software
00016 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
00017 */
00018 
00019 /* distance transform */
00020 
00021 #pragma once
00022 
00023 #include <algorithm>
00024 
00025 #include "image.h"
00026 #include "imconv.h"
00027 
00028 namespace distance_transform
00029 {
00030   const double INF  = 1E20;
00031 
00032   /* dt of 1d function using squared distance */
00033   static float *dt(float *f, int n) {
00034     float *d = new float[n];
00035     int *v = new int[n];
00036     float *z = new float[n+1];
00037     int k = 0;
00038     v[0] = 0;
00039     z[0] = -INF;
00040     z[1] = +INF;
00041     for (int q = 1; q <= n-1; q++) {
00042       float s  = ((f[q]+square(q))-(f[v[k]]+square(v[k])))/(2*q-2*v[k]);
00043       while (s <= z[k]) {
00044         k--;
00045         s  = ((f[q]+square(q))-(f[v[k]]+square(v[k])))/(2*q-2*v[k]);
00046       }
00047       k++;
00048       v[k] = q;
00049       z[k] = s;
00050       z[k+1] = +INF;
00051     }
00052 
00053     k = 0;
00054     for (int q = 0; q <= n-1; q++) {
00055       while (z[k+1] < q)
00056         k++;
00057       d[q] = square(q-v[k]) + f[v[k]];
00058     }
00059 
00060     delete [] v;
00061     delete [] z;
00062     return d;
00063   }
00064 
00065   /* dt of 2d function using squared distance */
00066   static void dt(image<float> *im) {
00067     int width = im->width();
00068     int height = im->height();
00069     float *f = new float[std::max(width,height)];
00070 
00071     // transform along columns
00072     for (int x = 0; x < width; x++) {
00073       for (int y = 0; y < height; y++) {
00074         f[y] = imRef(im, x, y);
00075       }
00076       float *d = dt(f, height);
00077       for (int y = 0; y < height; y++) {
00078         imRef(im, x, y) = d[y];
00079       }
00080       delete [] d;
00081     }
00082 
00083     // transform along rows
00084     for (int y = 0; y < height; y++) {
00085       for (int x = 0; x < width; x++) {
00086         f[x] = imRef(im, x, y);
00087       }
00088       float *d = dt(f, width);
00089       for (int x = 0; x < width; x++) {
00090         imRef(im, x, y) = d[x];
00091       }
00092       delete [] d;
00093     }
00094 
00095     delete f;
00096   }
00097 
00098   /* dt of binary image using squared distance */
00099   static image<float> *dt(image<uchar> *im, uchar on = 1) {
00100     int width = im->width();
00101     int height = im->height();
00102 
00103     image<float> *out = new image<float>(width, height, false);
00104     for (int y = 0; y < height; y++) {
00105       for (int x = 0; x < width; x++) {
00106         if (imRef(im, x, y) == on)
00107     imRef(out, x, y) = 0;
00108         else
00109     imRef(out, x, y) = INF;
00110       }
00111     }
00112 
00113     dt(out);
00114     return out;
00115   }
00116 
00117 } // namespace


grid_map_sdf
Author(s): Takahiro Miki , Péter Fankhauser
autogenerated on Mon Oct 9 2017 03:09:34