gcgraph.hpp 12 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393
  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. // Intel License Agreement
  11. // For Open Source Computer Vision Library
  12. //
  13. // Copyright (C) 2000, Intel Corporation, all rights reserved.
  14. // Third party copyrights are property of their respective owners.
  15. //
  16. // Redistribution and use in source and binary forms, with or without modification,
  17. // are permitted provided that the following conditions are met:
  18. //
  19. // * Redistribution's of source code must retain the above copyright notice,
  20. // this list of conditions and the following disclaimer.
  21. //
  22. // * Redistribution's in binary form must reproduce the above copyright notice,
  23. // this list of conditions and the following disclaimer in the documentation
  24. // and/or other materials provided with the distribution.
  25. //
  26. // * The name of Intel Corporation may not be used to endorse or promote products
  27. // derived from this software without specific prior written permission.
  28. //
  29. // This software is provided by the copyright holders and contributors "as is" and
  30. // any express or implied warranties, including, but not limited to, the implied
  31. // warranties of merchantability and fitness for a particular purpose are disclaimed.
  32. // In no event shall the Intel Corporation or contributors be liable for any direct,
  33. // indirect, incidental, special, exemplary, or consequential damages
  34. // (including, but not limited to, procurement of substitute goods or services;
  35. // loss of use, data, or profits; or business interruption) however caused
  36. // and on any theory of liability, whether in contract, strict liability,
  37. // or tort (including negligence or otherwise) arising in any way out of
  38. // the use of this software, even if advised of the possibility of such damage.
  39. //
  40. //M*/
  41. #ifndef OPENCV_IMGPROC_DETAIL_GCGRAPH_HPP
  42. #define OPENCV_IMGPROC_DETAIL_GCGRAPH_HPP
  43. //! @cond IGNORED
  44. namespace cv { namespace detail {
  45. template <class TWeight> class GCGraph
  46. {
  47. public:
  48. GCGraph();
  49. GCGraph( unsigned int vtxCount, unsigned int edgeCount );
  50. ~GCGraph();
  51. void create( unsigned int vtxCount, unsigned int edgeCount );
  52. int addVtx();
  53. void addEdges( int i, int j, TWeight w, TWeight revw );
  54. void addTermWeights( int i, TWeight sourceW, TWeight sinkW );
  55. TWeight maxFlow();
  56. bool inSourceSegment( int i );
  57. private:
  58. class Vtx
  59. {
  60. public:
  61. Vtx *next; // initialized and used in maxFlow() only
  62. int parent;
  63. int first;
  64. int ts;
  65. int dist;
  66. TWeight weight;
  67. uchar t;
  68. };
  69. class Edge
  70. {
  71. public:
  72. int dst;
  73. int next;
  74. TWeight weight;
  75. };
  76. std::vector<Vtx> vtcs;
  77. std::vector<Edge> edges;
  78. TWeight flow;
  79. };
  80. template <class TWeight>
  81. GCGraph<TWeight>::GCGraph()
  82. {
  83. flow = 0;
  84. }
  85. template <class TWeight>
  86. GCGraph<TWeight>::GCGraph( unsigned int vtxCount, unsigned int edgeCount )
  87. {
  88. create( vtxCount, edgeCount );
  89. }
  90. template <class TWeight>
  91. GCGraph<TWeight>::~GCGraph()
  92. {
  93. }
  94. template <class TWeight>
  95. void GCGraph<TWeight>::create( unsigned int vtxCount, unsigned int edgeCount )
  96. {
  97. vtcs.reserve( vtxCount );
  98. edges.reserve( edgeCount + 2 );
  99. flow = 0;
  100. }
  101. template <class TWeight>
  102. int GCGraph<TWeight>::addVtx()
  103. {
  104. Vtx v;
  105. memset( &v, 0, sizeof(Vtx));
  106. vtcs.push_back(v);
  107. return (int)vtcs.size() - 1;
  108. }
  109. template <class TWeight>
  110. void GCGraph<TWeight>::addEdges( int i, int j, TWeight w, TWeight revw )
  111. {
  112. CV_Assert( i>=0 && i<(int)vtcs.size() );
  113. CV_Assert( j>=0 && j<(int)vtcs.size() );
  114. CV_Assert( w>=0 && revw>=0 );
  115. CV_Assert( i != j );
  116. if( !edges.size() )
  117. edges.resize( 2 );
  118. Edge fromI, toI;
  119. fromI.dst = j;
  120. fromI.next = vtcs[i].first;
  121. fromI.weight = w;
  122. vtcs[i].first = (int)edges.size();
  123. edges.push_back( fromI );
  124. toI.dst = i;
  125. toI.next = vtcs[j].first;
  126. toI.weight = revw;
  127. vtcs[j].first = (int)edges.size();
  128. edges.push_back( toI );
  129. }
  130. template <class TWeight>
  131. void GCGraph<TWeight>::addTermWeights( int i, TWeight sourceW, TWeight sinkW )
  132. {
  133. CV_Assert( i>=0 && i<(int)vtcs.size() );
  134. TWeight dw = vtcs[i].weight;
  135. if( dw > 0 )
  136. sourceW += dw;
  137. else
  138. sinkW -= dw;
  139. flow += (sourceW < sinkW) ? sourceW : sinkW;
  140. vtcs[i].weight = sourceW - sinkW;
  141. }
  142. template <class TWeight>
  143. TWeight GCGraph<TWeight>::maxFlow()
  144. {
  145. const int TERMINAL = -1, ORPHAN = -2;
  146. Vtx stub, *nilNode = &stub, *first = nilNode, *last = nilNode;
  147. int curr_ts = 0;
  148. stub.next = nilNode;
  149. Vtx *vtxPtr = &vtcs[0];
  150. Edge *edgePtr = &edges[0];
  151. std::vector<Vtx*> orphans;
  152. // initialize the active queue and the graph vertices
  153. for( int i = 0; i < (int)vtcs.size(); i++ )
  154. {
  155. Vtx* v = vtxPtr + i;
  156. v->ts = 0;
  157. if( v->weight != 0 )
  158. {
  159. last = last->next = v;
  160. v->dist = 1;
  161. v->parent = TERMINAL;
  162. v->t = v->weight < 0;
  163. }
  164. else
  165. v->parent = 0;
  166. }
  167. first = first->next;
  168. last->next = nilNode;
  169. nilNode->next = 0;
  170. // run the search-path -> augment-graph -> restore-trees loop
  171. for(;;)
  172. {
  173. Vtx* v, *u;
  174. int e0 = -1, ei = 0, ej = 0;
  175. TWeight minWeight, weight;
  176. uchar vt;
  177. // grow S & T search trees, find an edge connecting them
  178. while( first != nilNode )
  179. {
  180. v = first;
  181. if( v->parent )
  182. {
  183. vt = v->t;
  184. for( ei = v->first; ei != 0; ei = edgePtr[ei].next )
  185. {
  186. if( edgePtr[ei^vt].weight == 0 )
  187. continue;
  188. u = vtxPtr+edgePtr[ei].dst;
  189. if( !u->parent )
  190. {
  191. u->t = vt;
  192. u->parent = ei ^ 1;
  193. u->ts = v->ts;
  194. u->dist = v->dist + 1;
  195. if( !u->next )
  196. {
  197. u->next = nilNode;
  198. last = last->next = u;
  199. }
  200. continue;
  201. }
  202. if( u->t != vt )
  203. {
  204. e0 = ei ^ vt;
  205. break;
  206. }
  207. if( u->dist > v->dist+1 && u->ts <= v->ts )
  208. {
  209. // reassign the parent
  210. u->parent = ei ^ 1;
  211. u->ts = v->ts;
  212. u->dist = v->dist + 1;
  213. }
  214. }
  215. if( e0 > 0 )
  216. break;
  217. }
  218. // exclude the vertex from the active list
  219. first = first->next;
  220. v->next = 0;
  221. }
  222. if( e0 <= 0 )
  223. break;
  224. // find the minimum edge weight along the path
  225. minWeight = edgePtr[e0].weight;
  226. CV_Assert( minWeight > 0 );
  227. // k = 1: source tree, k = 0: destination tree
  228. for( int k = 1; k >= 0; k-- )
  229. {
  230. for( v = vtxPtr+edgePtr[e0^k].dst;; v = vtxPtr+edgePtr[ei].dst )
  231. {
  232. if( (ei = v->parent) < 0 )
  233. break;
  234. weight = edgePtr[ei^k].weight;
  235. minWeight = MIN(minWeight, weight);
  236. CV_Assert( minWeight > 0 );
  237. }
  238. weight = fabs(v->weight);
  239. minWeight = MIN(minWeight, weight);
  240. CV_Assert( minWeight > 0 );
  241. }
  242. // modify weights of the edges along the path and collect orphans
  243. edgePtr[e0].weight -= minWeight;
  244. edgePtr[e0^1].weight += minWeight;
  245. flow += minWeight;
  246. // k = 1: source tree, k = 0: destination tree
  247. for( int k = 1; k >= 0; k-- )
  248. {
  249. for( v = vtxPtr+edgePtr[e0^k].dst;; v = vtxPtr+edgePtr[ei].dst )
  250. {
  251. if( (ei = v->parent) < 0 )
  252. break;
  253. edgePtr[ei^(k^1)].weight += minWeight;
  254. if( (edgePtr[ei^k].weight -= minWeight) == 0 )
  255. {
  256. orphans.push_back(v);
  257. v->parent = ORPHAN;
  258. }
  259. }
  260. v->weight = v->weight + minWeight*(1-k*2);
  261. if( v->weight == 0 )
  262. {
  263. orphans.push_back(v);
  264. v->parent = ORPHAN;
  265. }
  266. }
  267. // restore the search trees by finding new parents for the orphans
  268. curr_ts++;
  269. while( !orphans.empty() )
  270. {
  271. Vtx* v2 = orphans.back();
  272. orphans.pop_back();
  273. int d, minDist = INT_MAX;
  274. e0 = 0;
  275. vt = v2->t;
  276. for( ei = v2->first; ei != 0; ei = edgePtr[ei].next )
  277. {
  278. if( edgePtr[ei^(vt^1)].weight == 0 )
  279. continue;
  280. u = vtxPtr+edgePtr[ei].dst;
  281. if( u->t != vt || u->parent == 0 )
  282. continue;
  283. // compute the distance to the tree root
  284. for( d = 0;; )
  285. {
  286. if( u->ts == curr_ts )
  287. {
  288. d += u->dist;
  289. break;
  290. }
  291. ej = u->parent;
  292. d++;
  293. if( ej < 0 )
  294. {
  295. if( ej == ORPHAN )
  296. d = INT_MAX-1;
  297. else
  298. {
  299. u->ts = curr_ts;
  300. u->dist = 1;
  301. }
  302. break;
  303. }
  304. u = vtxPtr+edgePtr[ej].dst;
  305. }
  306. // update the distance
  307. if( ++d < INT_MAX )
  308. {
  309. if( d < minDist )
  310. {
  311. minDist = d;
  312. e0 = ei;
  313. }
  314. for( u = vtxPtr+edgePtr[ei].dst; u->ts != curr_ts; u = vtxPtr+edgePtr[u->parent].dst )
  315. {
  316. u->ts = curr_ts;
  317. u->dist = --d;
  318. }
  319. }
  320. }
  321. if( (v2->parent = e0) > 0 )
  322. {
  323. v2->ts = curr_ts;
  324. v2->dist = minDist;
  325. continue;
  326. }
  327. /* no parent is found */
  328. v2->ts = 0;
  329. for( ei = v2->first; ei != 0; ei = edgePtr[ei].next )
  330. {
  331. u = vtxPtr+edgePtr[ei].dst;
  332. ej = u->parent;
  333. if( u->t != vt || !ej )
  334. continue;
  335. if( edgePtr[ei^(vt^1)].weight && !u->next )
  336. {
  337. u->next = nilNode;
  338. last = last->next = u;
  339. }
  340. if( ej > 0 && vtxPtr+edgePtr[ej].dst == v2 )
  341. {
  342. orphans.push_back(u);
  343. u->parent = ORPHAN;
  344. }
  345. }
  346. }
  347. }
  348. return flow;
  349. }
  350. template <class TWeight>
  351. bool GCGraph<TWeight>::inSourceSegment( int i )
  352. {
  353. CV_Assert( i>=0 && i<(int)vtcs.size() );
  354. return vtcs[i].t == 0;
  355. }
  356. }} // namespace detail, cv
  357. //! @endcond
  358. #endif // OPENCV_IMGPROC_DETAIL_GCGRAPH_HPP