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
46 #include "opencv2/videostab/fast_marching.hpp"
47
48 namespace cv
49 {
50 namespace videostab
51 {
52
53 template <typename Inpaint>
run(const cv::Mat & mask,Inpaint inpaint)54 Inpaint FastMarchingMethod::run(const cv::Mat &mask, Inpaint inpaint)
55 {
56 using namespace cv;
57
58 CV_Assert(mask.type() == CV_8U);
59
60 static const int lut[4][2] = {{-1,0}, {0,-1}, {1,0}, {0,1}};
61
62 mask.copyTo(flag_);
63 flag_.create(mask.size());
64 dist_.create(mask.size());
65 index_.create(mask.size());
66 narrowBand_.clear();
67 size_ = 0;
68
69 // init
70 for (int y = 0; y < flag_.rows; ++y)
71 {
72 for (int x = 0; x < flag_.cols; ++x)
73 {
74 if (flag_(y,x) == KNOWN)
75 dist_(y,x) = 0.f;
76 else
77 {
78 int n = 0;
79 int nunknown = 0;
80
81 for (int i = 0; i < 4; ++i)
82 {
83 int xn = x + lut[i][0];
84 int yn = y + lut[i][1];
85
86 if (xn >= 0 && xn < flag_.cols && yn >= 0 && yn < flag_.rows)
87 {
88 n++;
89 if (flag_(yn,xn) != KNOWN)
90 nunknown++;
91 }
92 }
93
94 if (n>0 && nunknown == n)
95 {
96 dist_(y,x) = inf_;
97 flag_(y,x) = INSIDE;
98 }
99 else
100 {
101 dist_(y,x) = 0.f;
102 flag_(y,x) = BAND;
103 inpaint(x, y);
104
105 narrowBand_.push_back(DXY(0.f,x,y));
106 index_(y,x) = size_++;
107 }
108 }
109 }
110 }
111
112 // make heap
113 for (int i = size_/2-1; i >= 0; --i)
114 heapDown(i);
115
116 // main cycle
117 while (size_ > 0)
118 {
119 int x = narrowBand_[0].x;
120 int y = narrowBand_[0].y;
121 heapRemoveMin();
122
123 flag_(y,x) = KNOWN;
124 for (int n = 0; n < 4; ++n)
125 {
126 int xn = x + lut[n][0];
127 int yn = y + lut[n][1];
128
129 if (xn >= 0 && xn < flag_.cols && yn >= 0 && yn < flag_.rows && flag_(yn,xn) != KNOWN)
130 {
131 dist_(yn,xn) = std::min(std::min(solve(xn-1, yn, xn, yn-1), solve(xn+1, yn, xn, yn-1)),
132 std::min(solve(xn-1, yn, xn, yn+1), solve(xn+1, yn, xn, yn+1)));
133
134 if (flag_(yn,xn) == INSIDE)
135 {
136 flag_(yn,xn) = BAND;
137 inpaint(xn, yn);
138 heapAdd(DXY(dist_(yn,xn),xn,yn));
139 }
140 else
141 {
142 int i = index_(yn,xn);
143 if (dist_(yn,xn) < narrowBand_[i].dist)
144 {
145 narrowBand_[i].dist = dist_(yn,xn);
146 heapUp(i);
147 }
148 // works better if it's commented out
149 /*else if (dist(yn,xn) > narrowBand[i].dist)
150 {
151 narrowBand[i].dist = dist(yn,xn);
152 heapDown(i);
153 }*/
154 }
155 }
156 }
157 }
158
159 return inpaint;
160 }
161
162 } // namespace videostab
163 } // namespace cv
164
165 #endif
166