fast_marching_inl.hpp
Go to the documentation of this file.
1 /*M///////////////////////////////////////////////////////////////////////////////////////
2 //
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
4 //
5 // By downloading, copying, installing or using the software you agree to this license.
6 // If you do not agree to this license, do not download, install,
7 // copy or use the software.
8 //
9 //
10 // License Agreement
11 // For Open Source Computer Vision Library
12 //
13 // Copyright (C) 2000-2008, Intel Corporation, all rights reserved.
14 // Copyright (C) 2009-2011, Willow Garage Inc., all rights reserved.
15 // Third party copyrights are property of their respective owners.
16 //
17 // Redistribution and use in source and binary forms, with or without modification,
18 // are permitted provided that the following conditions are met:
19 //
20 // * Redistribution's of source code must retain the above copyright notice,
21 // this list of conditions and the following disclaimer.
22 //
23 // * Redistribution's in binary form must reproduce the above copyright notice,
24 // this list of conditions and the following disclaimer in the documentation
25 // and/or other materials provided with the distribution.
26 //
27 // * The name of the copyright holders may not be used to endorse or promote products
28 // derived from this software without specific prior written permission.
29 //
30 // This software is provided by the copyright holders and contributors "as is" and
31 // any express or implied warranties, including, but not limited to, the implied
32 // warranties of merchantability and fitness for a particular purpose are disclaimed.
33 // In no event shall the Intel Corporation or contributors be liable for any direct,
34 // indirect, incidental, special, exemplary, or consequential damages
35 // (including, but not limited to, procurement of substitute goods or services;
36 // loss of use, data, or profits; or business interruption) however caused
37 // and on any theory of liability, whether in contract, strict liability,
38 // or tort (including negligence or otherwise) arising in any way out of
39 // the use of this software, even if advised of the possibility of such damage.
40 //
41 //M*/
42 
43 #ifndef __OPENCV_VIDEOSTAB_FAST_MARCHING_INL_HPP__
44 #define __OPENCV_VIDEOSTAB_FAST_MARCHING_INL_HPP__
45 
47 
48 namespace cv
49 {
50 namespace videostab
51 {
52 
53 template <typename Inpaint>
54 Inpaint FastMarchingMethod::run(const cv::Mat &mask, Inpaint inpaint)
55 {
56  using namespace std;
57  using namespace cv;
58 
59  CV_Assert(mask.type() == CV_8U);
60 
61  static const int lut[4][2] = {{-1,0}, {0,-1}, {1,0}, {0,1}};
62 
63  mask.copyTo(flag_);
64  flag_.create(mask.size());
65  dist_.create(mask.size());
66  index_.create(mask.size());
67  narrowBand_.clear();
68  size_ = 0;
69 
70  // init
71  for (int y = 0; y < flag_.rows; ++y)
72  {
73  for (int x = 0; x < flag_.cols; ++x)
74  {
75  if (flag_(y,x) == KNOWN)
76  dist_(y,x) = 0.f;
77  else
78  {
79  int n = 0;
80  int nunknown = 0;
81 
82  for (int i = 0; i < 4; ++i)
83  {
84  int xn = x + lut[i][0];
85  int yn = y + lut[i][1];
86 
87  if (xn >= 0 && xn < flag_.cols && yn >= 0 && yn < flag_.rows)
88  {
89  n++;
90  if (flag_(yn,xn) != KNOWN)
91  nunknown++;
92  }
93  }
94 
95  if (n>0 && nunknown == n)
96  {
97  dist_(y,x) = inf_;
98  flag_(y,x) = INSIDE;
99  }
100  else
101  {
102  dist_(y,x) = 0.f;
103  flag_(y,x) = BAND;
104  inpaint(x, y);
105 
106  narrowBand_.push_back(DXY(0.f,x,y));
107  index_(y,x) = size_++;
108  }
109  }
110  }
111  }
112 
113  // make heap
114  for (int i = size_/2-1; i >= 0; --i)
115  heapDown(i);
116 
117  // main cycle
118  while (size_ > 0)
119  {
120  int x = narrowBand_[0].x;
121  int y = narrowBand_[0].y;
122  heapRemoveMin();
123 
124  flag_(y,x) = KNOWN;
125  for (int n = 0; n < 4; ++n)
126  {
127  int xn = x + lut[n][0];
128  int yn = y + lut[n][1];
129 
130  if (xn >= 0 && xn < flag_.cols && yn >= 0 && yn < flag_.rows && flag_(yn,xn) != KNOWN)
131  {
132  dist_(yn,xn) = min(min(solve(xn-1, yn, xn, yn-1), solve(xn+1, yn, xn, yn-1)),
133  min(solve(xn-1, yn, xn, yn+1), solve(xn+1, yn, xn, yn+1)));
134 
135  if (flag_(yn,xn) == INSIDE)
136  {
137  flag_(yn,xn) = BAND;
138  inpaint(xn, yn);
139  heapAdd(DXY(dist_(yn,xn),xn,yn));
140  }
141  else
142  {
143  int i = index_(yn,xn);
144  if (dist_(yn,xn) < narrowBand_[i].dist)
145  {
146  narrowBand_[i].dist = dist_(yn,xn);
147  heapUp(i);
148  }
149  // works better if it's commented out
150  /*else if (dist(yn,xn) > narrowBand[i].dist)
151  {
152  narrowBand[i].dist = dist(yn,xn);
153  heapDown(i);
154  }*/
155  }
156  }
157  }
158  }
159 
160  return inpaint;
161 }
162 
163 } // namespace videostab
164 } // namespace cv
165 
166 #endif
GLenum GLint GLint y
Definition: core_c.h:613
CvArr const CvArr * lut
Definition: core_c.h:1439
CV_EXPORTS_W void inpaint(InputArray src, InputArray inpaintMask, OutputArray dst, double inpaintRadius, int flags)
restores the damaged image areas using one of the available intpainting algorithms ...
void copyTo(OutputArray m) const
copies the matrix content to "m".
CV_EXPORTS_W bool solve(InputArray src1, InputArray src2, OutputArray dst, int flags=DECOMP_LU)
solves linear system or a least-square problem
int type() const
returns element type, similar to CV_MAT_TYPE(cvmat->type)
Definition: mat.hpp:399
CV_EXPORTS_W void min(InputArray src1, InputArray src2, OutputArray dst)
computes per-element minimum of two arrays (dst = min(src1, src2))
GLenum GLint x
Definition: core_c.h:632
GLenum GLsizei n
The n-dimensional matrix class.
Definition: core.hpp:1688
int int y
Definition: highgui_c.h:186
int n
Definition: legacy.hpp:3070
int x
Definition: highgui_c.h:186
MSize size
Definition: core.hpp:2006
GLenum GLint GLuint mask
Definition: tracking.hpp:132
GLclampf f
CvPoint3D64f double * dist
Definition: legacy.hpp:556
Inpaint run(const Mat &mask, Inpaint inpaint)
Definition: fast_marching_inl.hpp:54