fast_marching.hpp

00001 /*M///////////////////////////////////////////////////////////////////////////////////////
00002 //
00003 //  IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
00004 //
00005 //  By downloading, copying, installing or using the software you agree to this license.
00006 //  If you do not agree to this license, do not download, install,
00007 //  copy or use the software.
00008 //
00009 //
00010 //                           License Agreement
00011 //                For Open Source Computer Vision Library
00012 //
00013 // Copyright (C) 2000-2008, Intel Corporation, all rights reserved.
00014 // Copyright (C) 2009-2011, Willow Garage Inc., all rights reserved.
00015 // Third party copyrights are property of their respective owners.
00016 //
00017 // Redistribution and use in source and binary forms, with or without modification,
00018 // are permitted provided that the following conditions are met:
00019 //
00020 //   * Redistribution's of source code must retain the above copyright notice,
00021 //     this list of conditions and the following disclaimer.
00022 //
00023 //   * Redistribution's in binary form must reproduce the above copyright notice,
00024 //     this list of conditions and the following disclaimer in the documentation
00025 //     and/or other materials provided with the distribution.
00026 //
00027 //   * The name of the copyright holders may not be used to endorse or promote products
00028 //     derived from this software without specific prior written permission.
00029 //
00030 // This software is provided by the copyright holders and contributors "as is" and
00031 // any express or implied warranties, including, but not limited to, the implied
00032 // warranties of merchantability and fitness for a particular purpose are disclaimed.
00033 // In no event shall the Intel Corporation or contributors be liable for any direct,
00034 // indirect, incidental, special, exemplary, or consequential damages
00035 // (including, but not limited to, procurement of substitute goods or services;
00036 // loss of use, data, or profits; or business interruption) however caused
00037 // and on any theory of liability, whether in contract, strict liability,
00038 // or tort (including negligence or otherwise) arising in any way out of
00039 // the use of this software, even if advised of the possibility of such damage.
00040 //
00041 //M*/
00042 
00043 #ifndef __OPENCV_VIDEOSTAB_FAST_MARCHING_HPP__
00044 #define __OPENCV_VIDEOSTAB_FAST_MARCHING_HPP__
00045 
00046 #include <cmath>
00047 #include <queue>
00048 #include <algorithm>
00049 #include "opencv2/core.hpp"
00050 
00051 namespace cv
00052 {
00053 namespace videostab
00054 {
00055 
00056 //! @addtogroup videostab_marching
00057 //! @{
00058 
00059 /** @brief Describes the Fast Marching Method implementation.
00060 
00061   See http://iwi.eldoc.ub.rug.nl/FILES/root/2004/JGraphToolsTelea/2004JGraphToolsTelea.pdf
00062  */
00063 class CV_EXPORTS FastMarchingMethod
00064 {
00065 public:
00066     FastMarchingMethod() : inf_(1e6f) {}
00067 
00068     /** @brief Template method that runs the Fast Marching Method.
00069 
00070     @param mask Image mask. 0 value indicates that the pixel value must be inpainted, 255 indicates
00071     that the pixel value is known, other values aren't acceptable.
00072     @param inpaint Inpainting functor that overloads void operator ()(int x, int y).
00073     @return Inpainting functor.
00074      */
00075     template <typename Inpaint>
00076     Inpaint run(const Mat &mask, Inpaint inpaint);
00077 
00078     /**
00079     @return Distance map that's created during working of the method.
00080     */
00081     Mat distanceMap () const { return dist_; }
00082 
00083 private:
00084     enum { INSIDE = 0, BAND = 1, KNOWN = 255 };
00085 
00086     struct DXY
00087     {
00088         float dist;
00089         int x, y;
00090 
00091         DXY() : dist(0), x(0), y(0) {}
00092         DXY(float _dist, int _x, int _y) : dist(_dist), x(_x), y(_y) {}
00093         bool operator <(const DXY &dxy) const { return dist < dxy.dist; }
00094     };
00095 
00096     float solve(int x1, int y1, int x2, int y2) const;
00097     int& indexOf(const DXY &dxy) { return index_(dxy.y, dxy.x); }
00098 
00099     void heapUp(int idx);
00100     void heapDown(int idx);
00101     void heapAdd(const DXY &dxy);
00102     void heapRemoveMin();
00103 
00104     float inf_;
00105 
00106     cv::Mat_<uchar>  flag_; // flag map
00107     cv::Mat_<float>  dist_; // distance map
00108 
00109     cv::Mat_<int>  index_; // index of point in the narrow band
00110     std::vector<DXY> narrowBand_; // narrow band heap
00111     int size_; // narrow band size
00112 };
00113 
00114 //! @}
00115 
00116 } // namespace videostab
00117 } // namespace cv
00118 
00119 #include "fast_marching_inl.hpp"
00120 
00121 #endif
00122