1 /*M///////////////////////////////////////////////////////////////////////////////////////
3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
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.
10 // Intel License Agreement
11 // For Open Source Computer Vision Library
13 // Copyright (C) 2000, Intel Corporation, all rights reserved.
14 // Third party copyrights are property of their respective owners.
16 // Redistribution and use in source and binary forms, with or without modification,
17 // are permitted provided that the following conditions are met:
19 // * Redistribution's of source code must retain the above copyright notice,
20 // this list of conditions and the following disclaimer.
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.
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.
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.
46 //#include "windows.h"
48 //#define ALPHA_EXPANSION
50 #ifndef ALPHA_EXPANSION
51 #define ALPHA_BETA_EXCHANGE
56 #define CV_MODULE(xxx) \
57 ( (xxx) < 0 ? -(xxx) : (xxx) )
59 #define CV_MAX3(xxx1,xxx2,xxx3) \
60 ( (xxx1) > (xxx2) && (xxx1) > (xxx3) ? (xxx1) : \
61 (xxx2) > (xxx3) ? (xxx2) : (xxx3) )
63 #define CV_MIN2(xxx1,xxx2) \
64 ( (xxx1) < (xxx2) ? (xxx1) : (xxx2) )
66 #define getSizeForGraph(xxxType) \
67 ( sizeof(xxxType) < 8 ? 8 : sizeof(xxxType) + 4 - sizeof(xxxType) % 4 )
69 #define INT_INFINITY 1000000000
70 #define MAX_DIFFERENCE 10
73 // struct Vertex is used for storing vertices of graph
74 // coord - coordinate corresponding pixel on the real image line
81 // struct Edge is used for storing edges of graph
82 // weight - weight of the edge ( maximum flow via the edge )
83 // flow - current flow via the edge
84 // srcVtx - coordinate of source vertex on the real image line
85 // destVtx - coordinate of destination vertex on the real image line
88 CV_GRAPH_EDGE_FIELDS()
95 // function vFunc is energy function which determines the difference
96 // between two labels ( alpha and beta )
97 // alpha - label number one
98 // beta - label number two
99 inline int vFunc( int alpha, int beta )
107 // function dFunc is energy function which determines energy of interaction
108 // between pixel ( having coordinate xCoord ) and label
109 // leftLine - line of left image
110 // rightLine - line of right image
111 // xCoord - coordinate of pixel on the left image
112 // label - label corresponding to the pixel
113 // width - width of the image line in pixels
114 inline int dFunc( unsigned char* leftLine,
115 unsigned char* rightLine,
120 assert( xCoord >= 0 && xCoord < width );
122 int yCoord = xCoord + label;
124 if( yCoord >= width )
129 r = leftLine[ 3 * xCoord ] - rightLine[ 3 * yCoord ];
130 g = leftLine[ 3 * xCoord + 1 ] - rightLine[ 3 * yCoord + 1 ];
131 b = leftLine[ 3 * xCoord + 2 ] - rightLine[ 3 * yCoord + 2 ];
137 return CV_MAX3( r, g, b );
140 // function allocTempMem allocates all temporary memory needed for work
142 // memPtr - pointer to pointer to the large block of memory
143 // verticesPtr - pointer to pointer to block of memory for
144 // temporary storing vertices
145 // width - width of line in pixels
146 void allocTempMem( int** memPtr,
150 int* tempPtr = ( int* ) malloc( ( width + 2 ) * 7 * sizeof( int ) );
151 *verticesPtr = tempPtr;
152 *memPtr = *verticesPtr + width + 2;
155 // function freeTempMem frees all allocated by allocTempMem function memory
156 // memPtr - pointer to pointer to the large block of memory
157 // verticesPtr - pointer to pointer to block of memory for
158 // temporary storing vertices
159 void freeTempMem( int** memPtr,
162 free( ( void* )( *verticesPtr ) );
167 // function makeGraph creates initial graph to find maximum flow in it
168 // graphPtr - pointer to pointer to CvGraph structure to be filled
169 // leftLine - pointer to the left image line
170 // rightLine - pointer to the right image line
171 // alpha - label number one for doing exchange
172 // beta - label number two for doing exchange
173 // corr - pointer to array of correspondences ( each element
174 // of array includes disparity of pixel on right image
175 // for pixel each on left image ). This pointer direct
176 // to correspondence ofr one line only
177 // width - width of image lines in pixels
178 // storage - pointer to CvMemStorage structure which contains
180 void makeGraph( CvGraph** graphPtr,
181 unsigned char* leftLine,
182 unsigned char* rightLine,
187 CvMemStorage* storage )
192 cvClearGraph( *graphPtr );
195 *graphPtr = cvCreateGraph( CV_SEQ_KIND_GRAPH | CV_GRAPH_FLAG_ORIENTED,
197 getSizeForGraph( Vertex ),
198 getSizeForGraph( Edge ),
202 CvGraph* graph = *graphPtr;
204 #ifdef ALPHA_BETA_EXCHANGE
206 CvGraphVtx* newVtxPtr;
207 for( i = 0; i < width; i ++ )
209 if( corr[i] == alpha || corr[i] == beta ) {
210 cvGraphAddVtx( graph, NULL, &newVtxPtr );
211 ( ( Vertex* )newVtxPtr ) -> coord = i;
213 } /* for( i = 0; i < width; i ++ ) */
214 cvGraphAddVtx( graph, NULL, &newVtxPtr );
216 ( ( Vertex* )newVtxPtr ) -> coord = -2; /* adding alpha vertex */
217 cvGraphAddVtx( graph, NULL, &newVtxPtr );
219 ( ( Vertex* )newVtxPtr ) -> coord = -1; /* adding beta vertex */
221 int alphaVtx = graph -> total - 2;
222 int betaVtx = graph -> total - 1;
223 CvGraphEdge* newEdgePtr;
225 if( graph -> total > 2 )
227 for( i = 0; i < alphaVtx; i ++ )
229 vtxPtr = cvGetGraphVtx( graph, i );
231 /* adding edge oriented from alpha vertex to current vertex */
232 cvGraphAddEdge( graph, alphaVtx, i, NULL, &newEdgePtr );
233 ( ( Edge* )newEdgePtr ) -> weight = dFunc( leftLine,
235 ( ( Vertex* )vtxPtr ) -> coord,
238 ( ( Edge* )newEdgePtr ) -> flow = 0;
240 CvGraphVtx* tempVtxPtr = cvGetGraphVtx( graph, i - 1 );
241 /* if vertices are neighbours */
242 if( ( ( Vertex* )tempVtxPtr ) -> coord + 1 ==
243 ( ( Vertex* )vtxPtr ) -> coord )
245 ( ( Edge* )newEdgePtr ) -> weight +=
246 vFunc( corr[ ( ( Vertex* )tempVtxPtr ) -> coord ],
248 /* adding neighbour edge oriented from current vertex
249 to the previous one */
250 CvGraphEdge* tempEdgePtr;
251 cvGraphAddEdge( graph, i, i - 1, NULL, &tempEdgePtr );
252 ( ( Edge* )tempEdgePtr ) -> weight = vFunc( alpha, beta );
253 ( ( Edge* )tempEdgePtr ) -> flow = 0;
254 ( ( Edge* )tempEdgePtr ) -> srcVtx =
255 ( ( Vertex* )vtxPtr ) -> coord;
256 ( ( Edge* )tempEdgePtr ) -> destVtx =
257 ( ( Vertex* )tempVtxPtr ) -> coord;
260 if( i != alphaVtx - 1 ) {
261 CvGraphVtx* tempVtxPtr = cvGetGraphVtx( graph, i + 1 );
262 /* if vertices are neighbours */
263 if( ( ( Vertex* )tempVtxPtr ) -> coord - 1 ==
264 ( ( Vertex* )vtxPtr ) -> coord )
266 ( ( Edge* )newEdgePtr ) -> weight +=
267 vFunc( corr[ ( ( Vertex* )tempVtxPtr ) -> coord ],
269 /* adding neighbour edge oriented from current vertex
271 CvGraphEdge* tempEdgePtr;
272 cvGraphAddEdge( graph, i, i + 1, NULL, &tempEdgePtr );
273 ( ( Edge* )tempEdgePtr ) -> weight = vFunc( alpha, beta );
274 ( ( Edge* )tempEdgePtr ) -> flow = 0;
275 ( ( Edge* )tempEdgePtr ) -> srcVtx =
276 ( ( Vertex* )vtxPtr ) -> coord;
277 ( ( Edge* )tempEdgePtr ) -> destVtx =
278 ( ( Vertex* )tempVtxPtr ) -> coord;
280 } /* if( i != alphaVtx - 1 ) */
281 ( ( Edge* )newEdgePtr ) -> flow = 0;
282 ( ( Edge* )newEdgePtr ) -> srcVtx = -1; /* source vertex is alpha
284 ( ( Edge* )newEdgePtr ) -> destVtx = ( ( Vertex* )vtxPtr ) -> coord;
286 /* adding edge oriented from current vertex to beta vertex */
287 cvGraphAddEdge( graph, i, betaVtx, NULL, &newEdgePtr );
288 ( ( Edge* )newEdgePtr ) -> weight = dFunc( leftLine,
290 ( ( Vertex* )vtxPtr ) -> coord,
293 ( ( Edge* )newEdgePtr ) -> flow = 0;
295 CvGraphVtx* tempVtxPtr = cvGetGraphVtx( graph, i - 1 );
296 /* if vertices are neighbours */
297 if( ( ( Vertex* )tempVtxPtr ) -> coord + 1 ==
298 ( ( Vertex* )vtxPtr ) -> coord )
300 ( ( Edge* )newEdgePtr ) -> weight +=
301 vFunc( corr[ ( ( Vertex* )tempVtxPtr ) -> coord ],
305 if( i != alphaVtx - 1 ) {
306 CvGraphVtx* tempVtxPtr = cvGetGraphVtx( graph, i + 1 );
307 /* if vertices are neighbours */
308 if( ( ( Vertex* )tempVtxPtr ) -> coord - 1 ==
309 ( ( Vertex* )vtxPtr ) -> coord )
311 ( ( Edge* )newEdgePtr ) -> weight +=
312 vFunc( corr[ ( ( Vertex* )tempVtxPtr ) -> coord ],
315 } /* if( i != alphaVtx - 1 ) */
316 ( ( Edge* )newEdgePtr ) -> flow = 0;
317 ( ( Edge* )newEdgePtr ) -> srcVtx =
318 ( ( Vertex* )vtxPtr ) -> coord;
319 ( ( Edge* )newEdgePtr ) -> destVtx = -2; /* destination vertex is
322 } /* for( i = 0; i < graph -> total - 2; i ++ ) */
324 } /* if( graph -> total > 2 ) */
326 #endif /* #ifdef ALPHA_BETA_EXCHANGE */
328 #ifdef ALPHA_EXPANSION
329 #endif /* #ifdef ALPHA_EXPANSION */
333 // function makeHelpGraph creates help graph using initial graph
334 // graph - pointer to initial graph ( represented by CvGraph
336 // hlpGraphPtr - pointer to pointer to new help graph
337 // storage - pointer to CvStorage structure
338 // mem - pointer to memory allocated by allocTempMem function
339 // vertices - pointer to memory allocated by allocTempMem function
340 // verticesCountPtr- pointer to value containing number of vertices
342 // width - width of image line in pixels
343 int makeHelpGraph( CvGraph* graph,
344 CvGraph** hlpGraphPtr,
345 CvMemStorage* storage,
348 int* verticesCountPtr,
353 int* lengthArr = order + width + 2;
354 int s = graph -> total - 2; /* source vertex */
355 int t = graph -> total - 1; /* terminate vertex */
358 int &verticesCount = *verticesCountPtr;
362 cvClearGraph( *hlpGraphPtr );
365 *hlpGraphPtr = cvCreateGraph( CV_SEQ_KIND_GRAPH |
366 CV_GRAPH_FLAG_ORIENTED,
368 getSizeForGraph( Vertex ),
369 getSizeForGraph( Edge ),
373 hlpGraph = *hlpGraphPtr;
376 for( u = 0; u < graph -> total; u ++ )
378 lengthArr[ u ] = INT_INFINITY;
379 cvGraphAddVtx( hlpGraph, NULL, NULL );
380 } /* for( u = 0; u < graph -> total - 1; u ++ ) */
387 /* add vertex s to order */
388 order[ orderCount ] = s;
391 while( orderCount != orderFirst )
393 /* getting u from order */
394 u = order[ orderFirst ];
397 /* adding u to vertex array */
398 vertices[ verticesCount ] = u;
402 CvGraphVtx* graphVtx = cvGetGraphVtx( graph, u );
404 /* processing all vertices outgoing from vertex u */
405 CvGraphEdge* graphEdge = graphVtx -> first;
408 int tempVtxIdx = cvGraphVtxIdx( graph, graphEdge -> vtx[1] );
409 ofs = tempVtxIdx == u;
414 CvGraphEdge* tempGraphEdge = cvFindGraphEdge( graph, u, v );
415 if( ( lengthArr[ u ] < lengthArr[ v ] )
416 && ( lengthArr[ v ] <= lengthArr[ t ] )
417 && ( ( ( Edge* )tempGraphEdge ) -> flow <
418 ( ( Edge* )tempGraphEdge ) -> weight ) )
420 if( lengthArr[ v ] == INT_INFINITY )
422 /* adding vertex v to order */
423 order[ orderCount ] = v;
426 lengthArr[ v ] = lengthArr[ u ] + 1;
427 CvGraphEdge* tempGraphEdge2;
429 cvGraphAddEdge( hlpGraph, u, v, NULL, &tempGraphEdge2 );
430 ( ( Edge* )tempGraphEdge2 ) -> flow = 0;
432 ( ( Edge* )tempGraphEdge2 ) -> weight =
433 ( ( Edge* )tempGraphEdge ) -> weight -
434 ( ( Edge* )tempGraphEdge ) -> flow;
436 } /* if( length[ v ] == INT_INFINITY ) */
438 } /* if( ( lengthArr[ u ] < lengthArr[ v ] ) ... */
442 graphEdge = graphEdge -> next[ ofs ];
444 } /* while( graphEdge ) */
446 /* processing all vertices incoming to vertex u */
447 graphEdge = graphVtx -> first;
450 int tempVtxIdx = cvGraphVtxIdx( graph, graphEdge -> vtx[1] );
451 ofs = tempVtxIdx == u;
454 tempVtxIdx = cvGraphVtxIdx( graph, graphEdge -> vtx[0] );
457 CvGraphEdge* tempGraphEdge = cvFindGraphEdge( graph, v, u );
458 if( ( lengthArr[ u ] < lengthArr[ v ] )
459 && ( lengthArr[ v ] <= lengthArr[ t ] )
460 && ( ( ( Edge* )tempGraphEdge ) -> flow > 0 ) )
462 if( lengthArr[ v ] == INT_INFINITY )
464 /* adding vertex v to order */
465 order[ orderCount ] = v;
468 lengthArr[ v ] = lengthArr[ u ] + 1;
469 CvGraphEdge* tempGraphEdge3 = cvFindGraphEdge( hlpGraph, u, v );
471 if( tempGraphEdge3 == NULL ||
472 ( ( Edge* )tempGraphEdge3 ) -> weight == 0 )
474 CvGraphEdge* tempGraphEdge2;
475 cvGraphAddEdge( hlpGraph, u, v, NULL,
477 ( ( Edge* )tempGraphEdge2 ) -> flow = 0;
478 ( ( Edge* )tempGraphEdge2 ) -> weight = 0;
479 } /* if( tempGraphEdge3 == NULL || ... */
481 ( ( Edge* )tempGraphEdge3 ) -> weight +=
482 ( ( Edge* )tempGraphEdge ) -> flow;
484 } /* if( length[ v ] == INT_INFINITY ) */
486 } /* if( ( lengthArr[ u ] < lengthArr[ v ] ) ... */
490 graphEdge = graphEdge -> next[ ofs ];
492 } /* while( graphEdge ) */
494 } /* while( orderCount != orderFirst ) */
497 for( i = 0; i < hlpGraph -> total - 2; i ++ )
499 CvGraphVtx* hlpGraphVtxTemp = cvGetGraphVtx( hlpGraph, i );
500 if( hlpGraphVtxTemp ) {
501 if( !hlpGraphVtxTemp -> first ) {
502 cvGraphRemoveVtxByPtr( hlpGraph, hlpGraphVtxTemp );
505 } /* for( i = 0; i < hlpGraph -> total - 2; i ++ ) */
507 return lengthArr[ t ];
509 } /* makeHelpGraph */
511 // function makePseudoMaxFlow increases flow in graph by using hlpGraph
512 // graph - pointer to initial graph
513 // hlpGraph - pointer to help graph
514 // vertices - pointer to vertices array
515 // verticesCount - number of vertices in vertices array
516 // mem - pointer to memory allocated by allocTempMem function
517 // width - width of image line in pixels
518 void makePseudoMaxFlow( CvGraph* graph,
531 int* order = stek + width + 2;
532 int* incomFlow = order + width + 2;
533 int* outgoFlow = incomFlow + width + 2;
534 int* flow = outgoFlow + width + 2;
535 int* cargo = flow+ width + 2;
536 int s = graph -> total - 2; /* source vertex */
537 int t = graph -> total - 1; /* terminate vertex */
538 int realVerticesCount = verticesCount;
542 for( i = 0; i < verticesCount; i ++ )
546 incomFlow[ v ] = outgoFlow[ v ] = 0;
549 incomFlow[ v ] = INT_INFINITY;
552 CvGraphVtx* hlpGraphVtx = cvGetGraphVtx( hlpGraph, v );
553 CvGraphEdge* hlpGraphEdge = hlpGraphVtx -> first;
556 while( hlpGraphEdge )
558 int vtxIdx = cvGraphVtxIdx( hlpGraph,
559 hlpGraphEdge -> vtx[1] );
564 incomFlow[ v ] += ( ( Edge* )hlpGraphEdge ) -> weight;
567 hlpGraphEdge = hlpGraphEdge -> next[ ofs ];
568 } /* while( hlpGraphEdge ) */
570 } /* if( v == s ) else */
573 outgoFlow[ v ] = INT_INFINITY;
576 CvGraphVtx* hlpGraphVtx = cvGetGraphVtx( hlpGraph, v );
577 CvGraphEdge* hlpGraphEdge = hlpGraphVtx -> first;
580 while( hlpGraphEdge )
582 int vtxIdx = cvGraphVtxIdx( hlpGraph,
583 hlpGraphEdge -> vtx[1] );
588 outgoFlow[ v ] += ( ( Edge* )hlpGraphEdge ) -> weight;
591 hlpGraphEdge = hlpGraphEdge -> next[ ofs ];
592 } /* while( hlpGraphEdge ) */
594 } /* if( v == t ) else */
596 flow[ v ] = CV_MIN2( incomFlow[ v ], outgoFlow[ v ] );
599 stek[ stekCount ] = v;
601 } /* if( !flow[ v ] ) */
603 } /* for( i = 0; i < verticesCount; i ++ ) */
605 for( i = 0; i < verticesCount; i ++ )
609 } /* for( i = 0; i < verticesCount; i ++ ) */
611 while( realVerticesCount > 2 )
613 /* deleting all vertices included in stek */
616 v = stek[ stekCount - 1 ];
619 /* deleting edges incoming to v and outgoing from v */
621 CvGraphVtx* hlpGraphVtx = cvGetGraphVtx( hlpGraph, v );
622 CvGraphEdge* hlpGraphEdge;
624 hlpGraphEdge = hlpGraphVtx -> first;
629 while( hlpGraphEdge )
631 CvGraphVtx* hlpGraphVtx2 = hlpGraphEdge -> vtx[ 1 ];
632 int hlpGraphVtxIdx2 = cvGraphVtxIdx( hlpGraph,
634 ofs = hlpGraphVtxIdx2 == v;
638 /* hlpGraphEdge is incoming edge */
639 CvGraphVtx* hlpGraphVtx3 = hlpGraphEdge -> vtx[0];
640 u = cvGraphVtxIdx( hlpGraph,
642 outgoFlow[ u ] -= ( ( Edge* )hlpGraphEdge ) -> weight
643 - ( ( Edge* )hlpGraphEdge ) -> flow;
644 cvGraphRemoveEdgeByPtr( hlpGraph,
647 if( flow[ u ] != 0 ) {
648 flow[ u ] = CV_MIN2( incomFlow[u], outgoFlow[u] );
649 if( flow[ u ] == 0 ) {
650 stek[ stekCount ] = u;
657 /* hlpGraphEdge is outgoing edge */
658 CvGraphVtx* hlpGraphVtx3 = hlpGraphEdge -> vtx[1];
659 int u = cvGraphVtxIdx( hlpGraph,
661 incomFlow[ u ] -= ( ( Edge* )hlpGraphEdge ) -> weight
662 - ( ( Edge* )hlpGraphEdge ) -> flow;
663 cvGraphRemoveEdgeByPtr( hlpGraph,
666 if( flow[ u ] != 0 ) {
667 flow[ u ] = CV_MIN2( incomFlow[u], outgoFlow[u] );
668 if( flow[ u ] == 0 ) {
669 stek[ stekCount ] = u;
673 } /* if( ofs ) else */
675 hlpGraphEdge = hlpGraphEdge -> next[ ofs ];
677 } /* while( hlpGraphEdge ) */
679 /* deleting vertex v */
680 cvGraphRemoveVtx( hlpGraph, v );
681 realVerticesCount --;
683 } /* while( stekCount ) */
685 if( realVerticesCount > 2 ) /* the flow is not max still */
687 int p = INT_INFINITY;
689 CvGraphVtx* graphVtx;
691 if( realVerticesCount == 3 ) {
694 for( i = 0; i < hlpGraph -> total - 2; i ++ )
696 graphVtx = cvGetGraphVtx( hlpGraph, i );
698 v = cvGraphVtxIdx( hlpGraph, graphVtx );
699 if( flow[ v ] < p ) {
705 } /* for( i = 0; i < hlpGraph -> total - 2; i ++ ) */
707 /* building of size p flow from r to t */
708 orderCount = orderFirst = 0;
709 order[ orderCount ] = r;
712 v = order[ orderFirst ];
716 do /* while( v != t ) */
718 incomFlow[ v ] -= cargo[ v ];
719 outgoFlow[ v ] -= cargo[ v ];
720 flow[ v ] -= cargo[ v ];
722 if( flow[ v ] == 0 ) {
723 stek[ stekCount ] = v;
733 CvGraphVtx* hlpGraphVtx2;
734 CvGraphVtx* hlpGraphVtx = cvGetGraphVtx( hlpGraph, v );
735 CvGraphEdge* hlpGraphEdge = hlpGraphVtx -> first;
736 CvGraphEdge* hlpGraphEdge2 = NULL;
738 while( hlpGraphEdge && cargo[ v ] > 0 )
740 hlpGraphVtx2 = hlpGraphEdge -> vtx[ 1 ];
741 u = cvGraphVtxIdx( hlpGraph, hlpGraphVtx2 );
746 if( cargo[ u ] == 0 ) {
747 order[ orderCount ] = u;
750 int delta = ( ( Edge* )hlpGraphEdge ) -> weight
751 - ( ( Edge* )hlpGraphEdge ) -> flow;
752 delta = CV_MIN2( cargo[ v ], delta );
753 ( ( Edge* )hlpGraphEdge ) -> flow += delta;
756 if( ( ( Edge* )hlpGraphEdge ) -> weight ==
757 ( ( Edge* )hlpGraphEdge ) -> flow )
759 /* deleting hlpGraphEdge */
760 hlpGraphEdge2 = hlpGraphEdge -> next[ ofs ];
761 CvGraphEdge* graphEdge =
762 cvFindGraphEdge( graph, v, u );
763 ( ( Edge* )graphEdge ) -> flow +=
764 ( ( Edge* )hlpGraphEdge ) -> flow;
765 cvGraphRemoveEdgeByPtr( hlpGraph,
766 hlpGraphEdge -> vtx[0],
767 hlpGraphEdge -> vtx[1] );
771 if( hlpGraphEdge2 ) {
772 hlpGraphEdge = hlpGraphEdge2;
773 hlpGraphEdge2 = NULL;
776 hlpGraphEdge = hlpGraphEdge -> next[ ofs ];
778 } /* while( hlpGraphEdge && cargo[ v ] > 0 ) */
780 } /* if( v == t ) else */
782 v = order[ orderFirst ];
785 } while( v != t ); /* do */
787 /* building of size p flow from s to r */
788 orderCount = orderFirst = 0;
789 order[ orderCount ] = r;
792 v = order[ orderFirst ];
796 do /* while( v != s ) */
800 incomFlow[ v ] -= cargo[ v ];
801 outgoFlow[ v ] -= cargo[ v ];
802 flow[ v ] -= cargo[ v ];
803 if( flow[ v ] == 0 ) {
804 stek[ stekCount ] = v;
816 CvGraphVtx* hlpGraphVtx = cvGetGraphVtx( hlpGraph, v );
817 CvGraphEdge* hlpGraphEdge = hlpGraphVtx -> first;
818 CvGraphEdge* hlpGraphEdge2 = NULL;
819 while( hlpGraphEdge && cargo[ v ] > 0 )
821 u = cvGraphVtxIdx( hlpGraph,
822 hlpGraphEdge -> vtx[ 1 ] );
827 u = cvGraphVtxIdx( hlpGraph,
828 hlpGraphEdge -> vtx[ 0 ] );
830 if( cargo[ u ] == 0 ) {
831 order[ orderCount ] = u;
835 int delta = ( ( Edge* )hlpGraphEdge ) -> weight
836 - ( ( Edge* )hlpGraphEdge ) -> flow;
838 delta = CV_MIN2( cargo[ v ], delta );
840 (( ( Edge* )hlpGraphEdge ) -> flow) += delta;
845 if( ( ( Edge* )hlpGraphEdge ) -> weight ==
846 ( ( Edge* )hlpGraphEdge ) -> flow )
848 hlpGraphEdge2 = hlpGraphEdge -> next[ ofs ];
849 CvGraphEdge* graphEdge =
850 cvFindGraphEdge( graph, u, v );
851 ( ( Edge* )graphEdge ) -> flow +=
852 ( ( Edge* )hlpGraphEdge ) -> flow;
853 cvGraphRemoveEdgeByPtr( hlpGraph,
854 hlpGraphEdge -> vtx[0],
855 hlpGraphEdge -> vtx[1] );
859 if( hlpGraphEdge2 ) {
860 hlpGraphEdge = hlpGraphEdge2;
861 hlpGraphEdge2 = NULL;
864 hlpGraphEdge = hlpGraphEdge -> next[ ofs ];
866 } /* while( hlpGraphEdge && cargo[ v ] > 0 ) */
868 } /* if( v == s ) else */
870 v = order[ orderFirst ]; //added
871 orderFirst ++; //added
873 } while( v != s ); /* do */
875 } /* if( hlpGraph -> total > 2 ) */
877 } /* while( hlpGraph -> total > 2 ) */
879 } /* makePseudoMaxFlow */
882 // function oneStep produces one alpha-beta exchange for one line of images
883 // leftLine - pointer to the left image line
884 // rightLine - pointer to the right image line
885 // alpha - label number one
886 // beta - label number two
887 // corr - pointer to correspondence array for this line
888 // width - width of image line in pixels
889 // mem - pointer to memory allocated by allocTempMem function
890 // vertices - pointer to vertices array allocated by allocTempMem
892 // storage - pointer to CvMemStorage structure
893 bool oneStep( unsigned char* leftLine,
894 unsigned char* rightLine,
901 CvMemStorage* storage )
903 CvGraph* graph = NULL;
904 CvGraph* hlpGraph = NULL;
905 CvMemStoragePos storagePos;
908 cvSaveMemStoragePos( storage, &storagePos );
912 makeGraph( &graph, leftLine, rightLine, alpha, beta, corr, width, storage );
914 int s = graph -> total - 2; /* source vertex - alpha vertex */
915 //int t = graph -> total - 1; /* terminate vertex - beta vertex */
917 int length = makeHelpGraph( graph,
924 while( length != INT_INFINITY )
927 makePseudoMaxFlow( graph,
933 cvClearGraph( hlpGraph );
934 length = makeHelpGraph( graph,
941 } /* while( length != INT_INFINITY ) */
944 CvGraphVtx* graphVtx;
945 for( i = 0; i < s; i ++ )
947 CvGraphEdge* graphEdge = cvFindGraphEdge( graph, s, i );
949 if( ( ( Edge* )graphEdge ) -> weight ==
950 ( ( Edge* )graphEdge ) -> flow )
951 { /* this vertex must have alpha label */
952 graphVtx = cvGetGraphVtx( graph, i );
953 coord = ( ( Vertex* )graphVtx )-> coord;
954 if( corr[ coord ] != alpha ) {
955 corr[ coord ] = alpha; //added
959 corr[ coord ] = alpha;
961 } /* if( ( ( Edge* )graphEdge ) -> weight == ... */
963 { /* this vertex must have beta label */
964 graphVtx = cvGetGraphVtx( graph, i );
965 coord = ( ( Vertex* )graphVtx )-> coord;
966 if( corr[ coord ] != beta ) {
967 corr[ coord ] = beta; //added
971 corr[ coord ] = beta;
973 } /* if( ( ( Edge* )graphEdge ) -> weight == ... else */
975 } /* for( i = 0; i < s; i ++ ) */
977 cvClearGraph( hlpGraph );
978 cvClearGraph( graph );
980 cvRestoreMemStoragePos( storage, &storagePos );
986 // function initCorr fills correspondence array with initial values
987 // corr - pointer to correspondence array for this line
988 // width - width of image line in pixels
989 // maxPixelDifference - maximum value of difference between the same
990 // point painted on two images
991 void initCorr( int* corr, int width, int maxPixelDifference )
994 int pixelDifferenceRange = maxPixelDifference * 2 + 1;
996 for( i = 0; i < width; i ++ )
998 corr[ i ] = i % pixelDifferenceRange - maxPixelDifference;
1002 // function oneLineCorr fully computes one line of images
1003 // leftLine - pointer to the left image line
1004 // rightLine - pointer to the right image line
1005 // corr - pointer to the correspondence array for one
1007 // mem - pointer to memory allocated by allocTempMem
1009 // vertices - pointer to memory allocated by allocTempMem
1011 // width - width of image line in pixels
1012 // maxPixelDifference - maximum value of pixel differences in pixels
1013 // storage - pointer to CvMemStorage struct which
1014 // contains memory storage
1015 void oneLineCorr( unsigned char* leftLine,
1016 unsigned char* rightLine,
1021 int maxPixelDifference,
1022 CvMemStorage* storage )
1028 initCorr( corr, width, maxPixelDifference );
1033 for( i = - maxPixelDifference; i < maxPixelDifference; i ++ )
1034 for( j = i + 1; j <= maxPixelDifference; j ++ )
1036 result += (int)oneStep( leftLine,
1045 } /* for( j = i + 1; j < width; j ++ ) */
1048 if( count > /*0*//*1*/2 ) {
1052 } /* while( result ) */
1056 // function allLinesCorr computes all lines on the images
1057 // leftImage - pointer to the left image
1058 // leftLineStep - size of line on the left image in bytes
1059 // rightImage - pointer to the right image
1060 // rightLineStep - size of line on the right image in bytes
1061 // width - width of line in pixels
1062 // height - height of image in pixels
1063 // corr - pointer to correspondence array for all lines
1064 // maxPixelDifference - maximum value of difference between the same
1065 // point painted on two images
1066 // storage - pointer to CvMemStorage which contains memory
1068 void allLinesCorr( unsigned char* leftImage,
1070 unsigned char* rightImage,
1075 int maxPixelDifference,
1076 CvMemStorage* storage )
1079 unsigned char* leftLine = leftImage;
1080 unsigned char* rightLine = rightImage;
1088 for( i = 0; i < height; i ++ )
1090 oneLineCorr( leftLine,
1098 leftLine += leftLineStep;
1099 rightLine += rightLineStep;
1100 } /* for( i = 0; i < height; i ++ ) */
1105 } /* allLinesCorr */
1107 // This function produces morphing of two images into one image, which includes morphed
1108 // image or depth map
1109 // _leftImage - pointer to left image
1110 // _leftLineStep - size of line on left image in bytes
1111 // _rightImage - pointer to right image
1112 // _rightLineStep - size of line on right image in bytes
1113 // _resultImage - pointer to result morphed image
1114 // _resultLineStep - size of line on result image in bytes
1115 // _corrArray - pointer to array with correspondences
1116 // _numCorrArray - pointer to array with numbers correspondeces on each line
1117 // width - width of images
1118 // height - height of images
1119 // alpha - position of virtual camera ( 0 corresponds to left image, 1 - to right one )
1120 // imageNeed - defines your wishes. if you want to see normal morphed image you have to set
1121 // this parameter to morphNormalImage ( this is default value ), else if you want
1122 // to see depth map you have to set this parameter to morphDepthMap and set the
1123 // next parameter ( maxPixelDifference ) to real value
1124 // maxPixelDifference - maximum value of pixel difference on two images
1125 void CCvGraphCutMorpher::Morph( unsigned char* _leftImage,
1127 unsigned char* _rightImage,
1129 unsigned char* _resultImage,
1130 int _resultLineStep,
1135 morphImageType imageNeed,
1139 unsigned char* leftArray = _leftImage;
1140 unsigned char* middleArray = _resultImage;
1141 unsigned char* rightArray = _rightImage;
1142 int leftLineSize = _leftLineStep;
1143 int middleLineSize = _resultLineStep;
1144 int rightLineSize = _rightLineStep;
1147 unsigned char* leftTemp;
1148 unsigned char* middleTemp;
1149 unsigned char* rightTemp;
1153 int prevMiddlePixel;
1164 float alpha1 = 1.0f - alpha;
1166 for( lineNumber = 0; lineNumber < height; lineNumber ++ )
1168 leftTemp = leftArray + leftLineSize * lineNumber;
1169 middleTemp = middleArray + middleLineSize * lineNumber;
1170 rightTemp = rightArray + rightLineSize * lineNumber;
1171 memset( ( void* )middleTemp, 0, middleLineSize );
1173 result = _corrArray + width * lineNumber;
1177 prevRightPixel = prevLeftPixel + result[ 0 ];
1178 if( prevRightPixel >= width ) {
1179 prevRightPixel = width - 1;
1181 else if ( prevRightPixel < 0 ) {
1185 (int)( prevLeftPixel * alpha1 + prevRightPixel * alpha );
1186 for( i = 0; i < number - 1; i ++ )
1189 rightPixel = i + result[ i ];
1190 if( rightPixel >= width ) {
1191 rightPixel = width - 1;
1193 else if( rightPixel < 0 ) {
1197 (int)( leftPixel * alpha1 + rightPixel * alpha );
1198 leftPixel3 = leftPixel * 3;
1199 middlePixel3 = middlePixel * 3;
1200 rightPixel3 = rightPixel * 3;
1202 if( imageNeed == morphDepthMap ) {
1203 int t = leftPixel - rightPixel + maxDifference;
1205 t = t * 255 / maxDifference / 2;
1206 middleTemp[ middlePixel3 ] = ( unsigned char )t;
1207 middleTemp[ middlePixel3 + 1 ] = ( unsigned char )t;
1208 middleTemp[ middlePixel3 + 2 ] = ( unsigned char )t;
1209 } // if( imageNeed == morphDepthMap )
1212 middleTemp[ middlePixel3 ] =
1213 (unsigned char)( leftTemp[ leftPixel3 ] * alpha1
1214 + rightTemp[ rightPixel3 ] * alpha );
1215 middleTemp[ middlePixel3 + 1 ] =
1216 (unsigned char)( leftTemp[ leftPixel3 + 1 ] * alpha1
1217 + rightTemp[ rightPixel3 + 1 ] * alpha );
1218 middleTemp[ middlePixel3 + 2 ] =
1219 (unsigned char)( leftTemp[ leftPixel3 + 2 ] * alpha1
1220 + rightTemp[ rightPixel3 + 2 ] * alpha );
1222 if( middlePixel - prevMiddlePixel > 1 ) // occlusion
1224 if( leftPixel - prevLeftPixel > 1 )
1226 int LenSrc = leftPixel - prevLeftPixel - 2;
1227 int LenDest = middlePixel - prevMiddlePixel - 1;
1228 for( j = prevMiddlePixel + 1; j < middlePixel; j ++ )
1230 tempIndex = prevLeftPixel + 1 + LenSrc *
1231 ( j - prevMiddlePixel - 1 ) / LenDest;
1232 middleTemp[ j * 3 ] =
1233 leftTemp[ tempIndex * 3 ];
1234 middleTemp[ j * 3 + 1 ] =
1235 leftTemp[ tempIndex * 3 + 1 ];
1236 middleTemp[ j * 3 + 2 ] =
1237 leftTemp[ tempIndex * 3 + 2 ];
1239 } // if( leftPixel - prevLeftPixel > 1 )
1242 int LenSrc = rightPixel - prevRightPixel - 2;
1243 int LenDest = middlePixel - prevMiddlePixel - 1;
1244 for( j = prevMiddlePixel + 1; j < middlePixel; j ++ )
1246 tempIndex = prevRightPixel + 1 + LenSrc *
1247 ( j - prevMiddlePixel - 1 ) / LenDest;
1248 middleTemp[ j * 3 ] =
1249 rightTemp[ tempIndex * 3 ];
1250 middleTemp[ j * 3 + 1 ] =
1251 rightTemp[ tempIndex * 3 + 1 ];
1252 middleTemp[ j * 3 + 2 ] =
1253 rightTemp[ tempIndex * 3 + 2 ];
1255 } // if( leftPixel - prevLeftPixel > 1 ) else
1257 } // if( middlePixel - prevMiddlePixel > 1 )
1259 } // if( imageNeed == morphDepthMap ) else
1261 if( middlePixel > prevMiddlePixel ) {
1262 if( leftPixel > prevLeftPixel )
1263 prevLeftPixel = leftPixel;
1264 if( rightPixel > prevRightPixel )
1265 prevRightPixel = rightPixel;
1266 prevMiddlePixel = middlePixel;
1268 } // for( i = number - 1; i >= 0; i -- )
1270 } // for( lineNumber = 0; lineNumber < LeftImage -> m_Raster -> GetHeight() )
1274 bool CCvGraphCutMorpher::OnCalculateStereo()
1276 CvSize imageSizeLeft = GetImageSize( m_left_img ),
1277 imageSizeRight = GetImageSize( m_right_img );
1279 if( ( imageSizeLeft.width != imageSizeRight.width )
1280 || ( imageSizeLeft.height != imageSizeRight.height ) )
1289 m_corr = ( int* ) malloc( m_left_img -> width
1290 * m_left_img -> height
1294 m_storage = cvCreateMemStorage( 0 );
1295 m_isStorageAllocated = true;
1297 // Find correspondence for full image and store it to corr array
1298 allLinesCorr( ( unsigned char* )m_left_img -> imageData,
1299 m_left_img -> widthStep,
1300 ( unsigned char* )m_right_img -> imageData,
1301 m_right_img -> widthStep,
1302 m_left_img -> width,
1303 m_left_img -> height,
1305 m_maxPixelDifference,
1308 m_isStereoReady = true;
1313 bool CCvGraphCutMorpher::OnCalculateVirtualImage()
1315 // Output image to ResultImage window
1316 Morph( ( unsigned char* )m_left_img -> imageData,
1317 m_left_img ->widthStep,
1318 ( unsigned char* )m_right_img -> imageData,
1319 m_right_img -> widthStep,
1320 ( unsigned char* )m_virtual_img -> imageData,
1321 m_virtual_img -> widthStep,
1323 m_left_img -> width,
1324 m_left_img -> height,
1327 m_isVirtualImageReady = true;
1332 bool CCvGraphCutMorpher::OnCalculateDisparity()
1334 Morph( ( unsigned char* )m_left_img -> imageData,
1335 m_left_img ->widthStep,
1336 ( unsigned char* )m_right_img -> imageData,
1337 m_right_img -> widthStep,
1338 ( unsigned char* )m_disparity_img -> imageData,
1339 m_disparity_img -> widthStep,
1341 m_left_img -> width,
1342 m_left_img -> height,
1345 m_maxPixelDifference );
1350 bool CCvGraphCutMorpher::OnCalculateDisparityImage()
1352 Morph( ( unsigned char* )m_left_img -> imageData,
1353 m_left_img ->widthStep,
1354 ( unsigned char* )m_right_img -> imageData,
1355 m_right_img -> widthStep,
1356 ( unsigned char* )m_disparity_img -> imageData,
1357 m_disparity_img -> widthStep,
1359 m_left_img -> width,
1360 m_left_img -> height,
1363 m_maxPixelDifference );
1368 CCvGraphCutMorpher::CCvGraphCutMorpher()
1370 m_maxPixelDifference = MAX_DIFFERENCE;
1372 m_isStereoReady = false;
1373 m_isVirtualImageReady = false;
1374 m_isDisparityReady = false;
1376 m_isStorageAllocated = false;