$search
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 // Intel License Agreement 00011 // For Open Source Computer Vision Library 00012 // 00013 // Copyright (C) 2000, Intel Corporation, all rights reserved. 00014 // Third party copyrights are property of their respective owners. 00015 // 00016 // Redistribution and use in source and binary forms, with or without modification, 00017 // are permitted provided that the following conditions are met: 00018 // 00019 // * Redistribution's of source code must retain the above copyright notice, 00020 // this list of conditions and the following disclaimer. 00021 // 00022 // * Redistribution's in binary form must reproduce the above copyright notice, 00023 // this list of conditions and the following disclaimer in the documentation 00024 // and/or other materials provided with the distribution. 00025 // 00026 // * The name of Intel Corporation may not be used to endorse or promote products 00027 // derived from this software without specific prior written permission. 00028 // 00029 // This software is provided by the copyright holders and contributors "as is" and 00030 // any express or implied warranties, including, but not limited to, the implied 00031 // warranties of merchantability and fitness for a particular purpose are disclaimed. 00032 // In no event shall the Intel Corporation or contributors be liable for any direct, 00033 // indirect, incidental, special, exemplary, or consequential damages 00034 // (including, but not limited to, procurement of substitute goods or services; 00035 // loss of use, data, or profits; or business interruption) however caused 00036 // and on any theory of liability, whether in contract, strict liability, 00037 // or tort (including negligence or otherwise) arising in any way out of 00038 // the use of this software, even if advised of the possibility of such damage. 00039 // 00040 //M*/ 00041 00042 #ifndef _CV_GCGRAPH_H_ 00043 #define _CV_GCGRAPH_H_ 00044 00045 using namespace std; 00046 00047 template <class TWeight> class GCGraph 00048 { 00049 public: 00050 GCGraph(); 00051 GCGraph( unsigned int vtxCount, unsigned int edgeCount ); 00052 ~GCGraph(); 00053 void create( unsigned int vtxCount, unsigned int edgeCount ); 00054 int addVtx(); 00055 void addEdges( int i, int j, TWeight w, TWeight revw ); 00056 void addTermWeights( int i, TWeight sourceW, TWeight sinkW ); 00057 TWeight maxFlow(); 00058 bool inSourceSegment( int i ); 00059 private: 00060 class Vtx 00061 { 00062 public: 00063 Vtx *next; // initialized and used in maxFlow() only 00064 int parent; 00065 int first; 00066 int ts; 00067 int dist; 00068 TWeight weight; 00069 uchar t; 00070 }; 00071 class Edge 00072 { 00073 public: 00074 int dst; 00075 int next; 00076 TWeight weight; 00077 }; 00078 00079 vector<Vtx> vtcs; 00080 vector<Edge> edges; 00081 TWeight flow; 00082 }; 00083 00084 template <class TWeight> 00085 GCGraph<TWeight>::GCGraph() 00086 { 00087 flow = 0; 00088 } 00089 template <class TWeight> 00090 GCGraph<TWeight>::GCGraph( unsigned int vtxCount, unsigned int edgeCount ) 00091 { 00092 create( vtxCount, edgeCount ); 00093 } 00094 template <class TWeight> 00095 GCGraph<TWeight>::~GCGraph() 00096 { 00097 } 00098 template <class TWeight> 00099 void GCGraph<TWeight>::create( unsigned int vtxCount, unsigned int edgeCount ) 00100 { 00101 vtcs.reserve( vtxCount ); 00102 edges.reserve( edgeCount ); 00103 flow = 0; 00104 } 00105 00106 template <class TWeight> 00107 int GCGraph<TWeight>::addVtx() 00108 { 00109 Vtx v; 00110 memset( &v, 0, sizeof(Vtx)); 00111 vtcs.push_back(v); 00112 return (int)vtcs.size() - 1; 00113 } 00114 00115 template <class TWeight> 00116 void GCGraph<TWeight>::addEdges( int i, int j, TWeight w, TWeight revw ) 00117 { 00118 CV_Assert( i>=0 && i<(int)vtcs.size() ); 00119 CV_Assert( j>=0 && j<(int)vtcs.size() ); 00120 CV_Assert( w>=0 && revw>=0 ); 00121 CV_Assert( i != j ); 00122 00123 Edge fromI, toI; 00124 fromI.dst = j; 00125 fromI.next = vtcs[i].first; 00126 fromI.weight = w; 00127 vtcs[i].first = (int)edges.size(); 00128 edges.push_back( fromI ); 00129 00130 toI.dst = i; 00131 toI.next = vtcs[j].first; 00132 toI.weight = revw; 00133 vtcs[j].first = (int)edges.size(); 00134 edges.push_back( toI ); 00135 } 00136 00137 template <class TWeight> 00138 void GCGraph<TWeight>::addTermWeights( int i, TWeight sourceW, TWeight sinkW ) 00139 { 00140 CV_Assert( i>=0 && i<(int)vtcs.size() ); 00141 00142 TWeight dw = vtcs[i].weight; 00143 if( dw > 0 ) 00144 sourceW += dw; 00145 else 00146 sinkW -= dw; 00147 flow += (sourceW < sinkW) ? sourceW : sinkW; 00148 vtcs[i].weight = sourceW - sinkW; 00149 } 00150 00151 template <class TWeight> 00152 TWeight GCGraph<TWeight>::maxFlow() 00153 { 00154 const int TERMINAL = -1, ORPHAN = -2; 00155 Vtx stub, *nilNode = &stub, *first = nilNode, *last = nilNode; 00156 int curr_ts = 0; 00157 stub.next = nilNode; 00158 Vtx *vtxPtr = &vtcs[0]; 00159 Edge *edgePtr = &edges[0]; 00160 00161 vector<Vtx*> orphans; 00162 00163 // initialize the active queue and the graph vertices 00164 for( int i = 0; i < (int)vtcs.size(); i++ ) 00165 { 00166 Vtx* v = vtxPtr + i; 00167 v->ts = 0; 00168 if( v->weight != 0 ) 00169 { 00170 last = last->next = v; 00171 v->dist = 1; 00172 v->parent = TERMINAL; 00173 v->t = v->weight < 0; 00174 } 00175 else 00176 v->parent = 0; 00177 } 00178 first = first->next; 00179 last->next = nilNode; 00180 nilNode->next = 0; 00181 00182 // run the search-path -> augment-graph -> restore-trees loop 00183 for(;;) 00184 { 00185 Vtx* v, *u; 00186 int e0 = -1, ei = 0, ej = 0; 00187 TWeight minWeight, weight; 00188 uchar vt; 00189 00190 // grow S & T search trees, find an edge connecting them 00191 while( first != nilNode ) 00192 { 00193 v = first; 00194 if( v->parent ) 00195 { 00196 vt = v->t; 00197 for( ei = v->first; ei != 0; ei = edgePtr[ei].next ) 00198 { 00199 if( edgePtr[ei^vt].weight == 0 ) 00200 continue; 00201 u = vtxPtr+edgePtr[ei].dst; 00202 if( !u->parent ) 00203 { 00204 u->t = vt; 00205 u->parent = ei ^ 1; 00206 u->ts = v->ts; 00207 u->dist = v->dist + 1; 00208 if( !u->next ) 00209 { 00210 u->next = nilNode; 00211 last = last->next = u; 00212 } 00213 continue; 00214 } 00215 00216 if( u->t != vt ) 00217 { 00218 e0 = ei ^ vt; 00219 break; 00220 } 00221 00222 if( u->dist > v->dist+1 && u->ts <= v->ts ) 00223 { 00224 // reassign the parent 00225 u->parent = ei ^ 1; 00226 u->ts = v->ts; 00227 u->dist = v->dist + 1; 00228 } 00229 } 00230 if( e0 > 0 ) 00231 break; 00232 } 00233 // exclude the vertex from the active list 00234 first = first->next; 00235 v->next = 0; 00236 } 00237 00238 if( e0 <= 0 ) 00239 break; 00240 00241 // find the minimum edge weight along the path 00242 minWeight = edgePtr[e0].weight; 00243 assert( minWeight > 0 ); 00244 // k = 1: source tree, k = 0: destination tree 00245 for( int k = 1; k >= 0; k-- ) 00246 { 00247 for( v = vtxPtr+edgePtr[e0^k].dst;; v = vtxPtr+edgePtr[ei].dst ) 00248 { 00249 if( (ei = v->parent) < 0 ) 00250 break; 00251 weight = edgePtr[ei^k].weight; 00252 minWeight = MIN(minWeight, weight); 00253 assert( minWeight > 0 ); 00254 } 00255 weight = fabs(v->weight); 00256 minWeight = MIN(minWeight, weight); 00257 assert( minWeight > 0 ); 00258 } 00259 00260 // modify weights of the edges along the path and collect orphans 00261 edgePtr[e0].weight -= minWeight; 00262 edgePtr[e0^1].weight += minWeight; 00263 flow += minWeight; 00264 00265 // k = 1: source tree, k = 0: destination tree 00266 for( int k = 1; k >= 0; k-- ) 00267 { 00268 for( v = vtxPtr+edgePtr[e0^k].dst;; v = vtxPtr+edgePtr[ei].dst ) 00269 { 00270 if( (ei = v->parent) < 0 ) 00271 break; 00272 edgePtr[ei^(k^1)].weight += minWeight; 00273 if( (edgePtr[ei^k].weight -= minWeight) == 0 ) 00274 { 00275 orphans.push_back(v); 00276 v->parent = ORPHAN; 00277 } 00278 } 00279 00280 v->weight = v->weight + minWeight*(1-k*2); 00281 if( v->weight == 0 ) 00282 { 00283 orphans.push_back(v); 00284 v->parent = ORPHAN; 00285 } 00286 } 00287 00288 // restore the search trees by finding new parents for the orphans 00289 curr_ts++; 00290 while( !orphans.empty() ) 00291 { 00292 Vtx* v = orphans.back(); 00293 orphans.pop_back(); 00294 00295 int d, minDist = INT_MAX; 00296 e0 = 0; 00297 vt = v->t; 00298 00299 for( ei = v->first; ei != 0; ei = edgePtr[ei].next ) 00300 { 00301 if( edgePtr[ei^(vt^1)].weight == 0 ) 00302 continue; 00303 u = vtxPtr+edgePtr[ei].dst; 00304 if( u->t != vt || u->parent == 0 ) 00305 continue; 00306 // compute the distance to the tree root 00307 for( d = 0;; ) 00308 { 00309 if( u->ts == curr_ts ) 00310 { 00311 d += u->dist; 00312 break; 00313 } 00314 ej = u->parent; 00315 d++; 00316 if( ej < 0 ) 00317 { 00318 if( ej == ORPHAN ) 00319 d = INT_MAX-1; 00320 else 00321 { 00322 u->ts = curr_ts; 00323 u->dist = 1; 00324 } 00325 break; 00326 } 00327 u = vtxPtr+edgePtr[ej].dst; 00328 } 00329 00330 // update the distance 00331 if( ++d < INT_MAX ) 00332 { 00333 if( d < minDist ) 00334 { 00335 minDist = d; 00336 e0 = ei; 00337 } 00338 for( u = vtxPtr+edgePtr[ei].dst; u->ts != curr_ts; u = vtxPtr+edgePtr[u->parent].dst ) 00339 { 00340 u->ts = curr_ts; 00341 u->dist = --d; 00342 } 00343 } 00344 } 00345 00346 if( (v->parent = e0) > 0 ) 00347 { 00348 v->ts = curr_ts; 00349 v->dist = minDist; 00350 continue; 00351 } 00352 00353 /* no parent is found */ 00354 v->ts = 0; 00355 for( ei = v->first; ei != 0; ei = edgePtr[ei].next ) 00356 { 00357 u = vtxPtr+edgePtr[ei].dst; 00358 ej = u->parent; 00359 if( u->t != vt || !ej ) 00360 continue; 00361 if( edgePtr[ei^(vt^1)].weight && !u->next ) 00362 { 00363 u->next = nilNode; 00364 last = last->next = u; 00365 } 00366 if( ej > 0 && vtxPtr+edgePtr[ej].dst == v ) 00367 { 00368 orphans.push_back(u); 00369 u->parent = ORPHAN; 00370 } 00371 } 00372 } 00373 } 00374 return flow; 00375 } 00376 00377 template <class TWeight> 00378 bool GCGraph<TWeight>::inSourceSegment( int i ) 00379 { 00380 CV_Assert( i>=0 && i<(int)vtcs.size() ); 00381 return vtcs[i].t == 0; 00382 }; 00383 00384 #endif