git.maemo.org Git - opencv/blob - cvaux/src/enmin.cpp

   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
  42 #include "_cvaux.h"
  43
  44 #if 0
  45
  46 //#include "windows.h"
  47
  48 //#define ALPHA_EXPANSION
  49
  50 #ifndef ALPHA_EXPANSION
  51     #define ALPHA_BETA_EXCHANGE
  52 #endif
  53
  54 #define MAX_LABEL 20
  55
  56 #define CV_MODULE(xxx) \
  57     ( (xxx) < 0 ? -(xxx) : (xxx) )
  58
  59 #define CV_MAX3(xxx1,xxx2,xxx3) \
  60     ( (xxx1) > (xxx2) && (xxx1) > (xxx3) ? (xxx1) : \
  61         (xxx2) > (xxx3) ? (xxx2) : (xxx3) )
  62
  63 #define CV_MIN2(xxx1,xxx2) \
  64     ( (xxx1) < (xxx2) ? (xxx1) : (xxx2) )
  65
  66 #define getSizeForGraph(xxxType) \
  67     ( sizeof(xxxType) < 8 ? 8 : sizeof(xxxType) + 4 - sizeof(xxxType) % 4 )
  68
  69 #define INT_INFINITY 1000000000
  70 #define MAX_DIFFERENCE 10
  71
  72
  73 // struct Vertex is used for storing vertices of graph
  74 //      coord       - coordinate corresponding pixel on the real image line
  75 struct Vertex
  76 {
  77     CvGraphVtx vtx;
  78     int coord;
  79 };
  80
  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
  86 struct Edge
  87 {
  88     CV_GRAPH_EDGE_FIELDS()
  89     int weight;
  90     int flow;
  91     int srcVtx;
  92     int destVtx;
  93 };
  94
  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 )
 100 {
 101     if( alpha == beta )
 102         return 0;
 103     else
 104         return /*1*//*5*/10;
 105 }
 106
 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,
 116                   int xCoord,
 117                   int label,
 118                   int width)
 119 {
 120     assert( xCoord >= 0 && xCoord < width );
 121     int r, g, b;
 122     int yCoord = xCoord + label;
 123
 124     if( yCoord >= width )
 125         yCoord = width;
 126     if( yCoord < 0 )
 127         yCoord = 0;
 128
 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 ];
 132
 133     r = CV_MODULE( r );
 134     g = CV_MODULE( g );
 135     b = CV_MODULE( b );
 136
 137     return CV_MAX3( r, g, b );
 138 }
 139
 140 // function allocTempMem allocates all temporary memory needed for work
 141 //   of some function
 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,
 147                    int** verticesPtr,
 148                    int width )
 149 {
 150     int* tempPtr = ( int* ) malloc( ( width + 2 ) * 7 * sizeof( int ) );
 151     *verticesPtr = tempPtr;
 152     *memPtr = *verticesPtr + width + 2;
 153 }
 154
 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,
 160                   int** verticesPtr )
 161 {
 162     free( ( void* )( *verticesPtr ) );
 163     *verticesPtr = NULL;
 164     *memPtr = NULL;
 165 }
 166
 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
 179 //                        memory storage
 180 void makeGraph( CvGraph** graphPtr,
 181                 unsigned char* leftLine,
 182                 unsigned char* rightLine,
 183                 int alpha,
 184                 int beta,
 185                 int* corr,
 186                 int width,
 187                 CvMemStorage* storage )
 188 {
 189     int i;
 190
 191     if( *graphPtr )  {
 192         cvClearGraph( *graphPtr );
 193     }
 194     /*else {*/
 195         *graphPtr = cvCreateGraph( CV_SEQ_KIND_GRAPH | CV_GRAPH_FLAG_ORIENTED,
 196                                    sizeof( CvGraph ),
 197                                    getSizeForGraph( Vertex ),
 198                                    getSizeForGraph( Edge ),
 199                                    storage );
 200     /*}*/
 201
 202     CvGraph* graph = *graphPtr;
 203
 204     #ifdef ALPHA_BETA_EXCHANGE
 205
 206     CvGraphVtx* newVtxPtr;
 207     for( i = 0; i < width; i ++ )
 208     {
 209         if( corr[i] == alpha || corr[i] == beta ) {
 210             cvGraphAddVtx( graph, NULL, &newVtxPtr );
 211             ( ( Vertex* )newVtxPtr ) -> coord = i;
 212         }
 213     } /* for( i = 0; i < width; i ++ ) */
 214     cvGraphAddVtx( graph, NULL, &newVtxPtr );
 215     if( newVtxPtr )
 216         ( ( Vertex* )newVtxPtr ) -> coord = -2; /* adding alpha vertex */
 217     cvGraphAddVtx( graph, NULL, &newVtxPtr );
 218     if( newVtxPtr )
 219         ( ( Vertex* )newVtxPtr ) -> coord = -1; /* adding beta vertex */
 220
 221     int alphaVtx = graph -> total - 2;
 222     int betaVtx = graph -> total - 1;
 223     CvGraphEdge* newEdgePtr;
 224     CvGraphVtx* vtxPtr;
 225     if( graph -> total > 2 )
 226     {
 227         for( i = 0; i < alphaVtx; i ++ )
 228         {
 229             vtxPtr = cvGetGraphVtx( graph, i );
 230
 231             /* adding edge oriented from alpha vertex to current vertex */
 232             cvGraphAddEdge( graph, alphaVtx, i, NULL, &newEdgePtr );
 233             ( ( Edge* )newEdgePtr ) -> weight = dFunc( leftLine,
 234                 rightLine,
 235                 ( ( Vertex* )vtxPtr ) -> coord,
 236                 alpha,
 237                 width );
 238             ( ( Edge* )newEdgePtr ) -> flow = 0;
 239             if( i != 0 ) {
 240                 CvGraphVtx* tempVtxPtr = cvGetGraphVtx( graph, i - 1 );
 241                 /* if vertices are neighbours */
 242                 if( ( ( Vertex* )tempVtxPtr ) -> coord + 1 ==
 243                     ( ( Vertex* )vtxPtr ) -> coord )
 244                 {
 245                     ( ( Edge* )newEdgePtr ) -> weight +=
 246                         vFunc( corr[ ( ( Vertex* )tempVtxPtr ) -> coord ],
 247                                alpha );
 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;
 258                 }
 259             } /* if( i != 0 ) */
 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 )
 265                 {
 266                     ( ( Edge* )newEdgePtr ) -> weight +=
 267                         vFunc( corr[ ( ( Vertex* )tempVtxPtr ) -> coord ],
 268                                alpha );
 269                     /* adding neighbour edge oriented from current vertex
 270                        to the next one */
 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;
 279                 }
 280             } /* if( i != alphaVtx - 1 ) */
 281             ( ( Edge* )newEdgePtr ) -> flow = 0;
 282             ( ( Edge* )newEdgePtr ) -> srcVtx = -1; /* source vertex is alpha
 283                                                        vertex */
 284             ( ( Edge* )newEdgePtr ) -> destVtx = ( ( Vertex* )vtxPtr ) -> coord;
 285
 286             /* adding edge oriented from current vertex to beta vertex */
 287             cvGraphAddEdge( graph, i, betaVtx, NULL, &newEdgePtr );
 288             ( ( Edge* )newEdgePtr ) -> weight = dFunc( leftLine,
 289                 rightLine,
 290                 ( ( Vertex* )vtxPtr ) -> coord,
 291                 beta,
 292                 width );
 293             ( ( Edge* )newEdgePtr ) -> flow = 0;
 294             if( i != 0 ) {
 295                 CvGraphVtx* tempVtxPtr = cvGetGraphVtx( graph, i - 1 );
 296                 /* if vertices are neighbours */
 297                 if( ( ( Vertex* )tempVtxPtr ) -> coord + 1 ==
 298                     ( ( Vertex* )vtxPtr ) -> coord )
 299                 {
 300                     ( ( Edge* )newEdgePtr ) -> weight +=
 301                         vFunc( corr[ ( ( Vertex* )tempVtxPtr ) -> coord ],
 302                                beta );
 303                 }
 304             } /* if( i != 0 ) */
 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 )
 310                 {
 311                     ( ( Edge* )newEdgePtr ) -> weight +=
 312                         vFunc( corr[ ( ( Vertex* )tempVtxPtr ) -> coord ],
 313                                beta );
 314                 }
 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
 320                                                         beta vertex */
 321
 322         } /* for( i = 0; i < graph -> total - 2; i ++ ) */
 323
 324     } /* if( graph -> total > 2 ) */
 325
 326     #endif /* #ifdef ALPHA_BETA_EXCHANGE */
 327
 328     #ifdef ALPHA_EXPANSION
 329     #endif /* #ifdef ALPHA_EXPANSION */
 330
 331 } /* makeGraph */
 332
 333 // function makeHelpGraph creates help graph using initial graph
 334 //      graph           - pointer to initial graph ( represented by CvGraph
 335 //                        structure )
 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
 341 //                        in vertices array
 342 //      width           - width of image line in pixels
 343 int makeHelpGraph( CvGraph* graph,
 344                    CvGraph** hlpGraphPtr,
 345                    CvMemStorage* storage,
 346                    int* mem,
 347                    int* vertices,
 348                    int* verticesCountPtr,
 349                    int width )
 350 {
 351     int u, v;
 352     int* order = mem;
 353     int* lengthArr = order + width + 2;
 354     int s = graph -> total - 2; /* source vertex */
 355     int t = graph -> total - 1; /* terminate vertex */
 356     int orderFirst;
 357     int orderCount;
 358     int &verticesCount = *verticesCountPtr;
 359     CvGraph* hlpGraph;
 360
 361     if( *hlpGraphPtr )  {
 362         cvClearGraph( *hlpGraphPtr );
 363     }
 364     else {
 365         *hlpGraphPtr = cvCreateGraph( CV_SEQ_KIND_GRAPH |
 366                                           CV_GRAPH_FLAG_ORIENTED,
 367                                       sizeof( CvGraph ),
 368                                       getSizeForGraph( Vertex ),
 369                                       getSizeForGraph( Edge ),
 370                                       storage );
 371     }
 372
 373     hlpGraph = *hlpGraphPtr;
 374
 375     /* initialization */
 376     for( u = 0; u < graph -> total; u ++ )
 377     {
 378         lengthArr[ u ] = INT_INFINITY;
 379         cvGraphAddVtx( hlpGraph, NULL, NULL );
 380     } /* for( u = 0; u < graph -> total - 1; u ++ ) */
 381
 382     orderFirst = 0;
 383     orderCount = 0;
 384     verticesCount = 0;
 385     lengthArr[ s ] = 0;
 386
 387     /* add vertex s to order */
 388     order[ orderCount ] = s;
 389     orderCount ++;
 390
 391     while( orderCount != orderFirst )
 392     {
 393         /* getting u from order */
 394         u = order[ orderFirst ];
 395         orderFirst ++;
 396
 397         /* adding u to vertex array */
 398         vertices[ verticesCount ] = u;
 399         verticesCount ++;
 400
 401         int ofs;
 402         CvGraphVtx* graphVtx = cvGetGraphVtx( graph, u );
 403
 404         /* processing all vertices outgoing from vertex u */
 405         CvGraphEdge* graphEdge = graphVtx -> first;
 406         while( graphEdge )
 407         {
 408             int tempVtxIdx = cvGraphVtxIdx( graph, graphEdge -> vtx[1] );
 409             ofs = tempVtxIdx == u;
 410             if( !ofs )
 411             {
 412                 v = tempVtxIdx;
 413
 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 ) )
 419                 {
 420                     if( lengthArr[ v ] == INT_INFINITY )
 421                     {
 422                         /* adding vertex v to order */
 423                         order[ orderCount ] = v;
 424                         orderCount ++;
 425
 426                         lengthArr[ v ] = lengthArr[ u ] + 1;
 427                         CvGraphEdge* tempGraphEdge2;
 428
 429                         cvGraphAddEdge( hlpGraph, u, v, NULL, &tempGraphEdge2 );
 430                         ( ( Edge* )tempGraphEdge2 ) -> flow = 0;
 431
 432                         ( ( Edge* )tempGraphEdge2 ) -> weight =
 433                             ( ( Edge* )tempGraphEdge ) -> weight -
 434                             ( ( Edge* )tempGraphEdge ) -> flow;
 435
 436                     } /* if( length[ v ] == INT_INFINITY ) */
 437
 438                 } /* if( ( lengthArr[ u ] < lengthArr[ v ] ) ... */
 439
 440             } /* if( !ofs ) */
 441
 442             graphEdge = graphEdge -> next[ ofs ];
 443
 444         } /* while( graphEdge ) */
 445
 446         /* processing all vertices incoming to vertex u */
 447         graphEdge = graphVtx -> first;
 448         while( graphEdge )
 449         {
 450             int tempVtxIdx = cvGraphVtxIdx( graph, graphEdge -> vtx[1] );
 451             ofs = tempVtxIdx == u;
 452             if( ofs )
 453             {
 454                 tempVtxIdx = cvGraphVtxIdx( graph, graphEdge -> vtx[0] );
 455                 v = tempVtxIdx;
 456
 457                 CvGraphEdge* tempGraphEdge = cvFindGraphEdge( graph, v, u );
 458                 if( ( lengthArr[ u ] < lengthArr[ v ] )
 459                     && ( lengthArr[ v ] <= lengthArr[ t ] )
 460                     && ( ( ( Edge* )tempGraphEdge ) -> flow > 0 ) )
 461                 {
 462                     if( lengthArr[ v ] == INT_INFINITY )
 463                     {
 464                         /* adding vertex v to order */
 465                         order[ orderCount ] = v;
 466                         orderCount ++;
 467
 468                         lengthArr[ v ] = lengthArr[ u ] + 1;
 469                         CvGraphEdge* tempGraphEdge3 = cvFindGraphEdge( hlpGraph, u, v );
 470
 471                         if( tempGraphEdge3 == NULL ||
 472                             ( ( Edge* )tempGraphEdge3 ) -> weight == 0 )
 473                         {
 474                             CvGraphEdge* tempGraphEdge2;
 475                             cvGraphAddEdge( hlpGraph, u, v, NULL,
 476                                 &tempGraphEdge2 );
 477                             ( ( Edge* )tempGraphEdge2 ) -> flow = 0;
 478                             ( ( Edge* )tempGraphEdge2 ) -> weight = 0;
 479                         } /* if( tempGraphEdge3 == NULL || ... */
 480
 481                         ( ( Edge* )tempGraphEdge3 ) -> weight +=
 482                             ( ( Edge* )tempGraphEdge ) -> flow;
 483
 484                     } /* if( length[ v ] == INT_INFINITY ) */
 485
 486                 } /* if( ( lengthArr[ u ] < lengthArr[ v ] ) ... */
 487
 488             } /* if( ofs ) */
 489
 490             graphEdge = graphEdge -> next[ ofs ];
 491
 492         } /* while( graphEdge ) */
 493
 494     } /* while( orderCount != orderFirst ) */
 495
 496     int i;
 497     for( i = 0; i < hlpGraph -> total - 2; i ++ )
 498     {
 499         CvGraphVtx* hlpGraphVtxTemp = cvGetGraphVtx( hlpGraph, i );
 500         if( hlpGraphVtxTemp ) {
 501             if( !hlpGraphVtxTemp -> first ) {
 502                 cvGraphRemoveVtxByPtr( hlpGraph, hlpGraphVtxTemp );
 503             }
 504         }
 505     } /* for( i = 0; i < hlpGraph -> total - 2; i ++ ) */
 506
 507     return lengthArr[ t ];
 508
 509 } /* makeHelpGraph */
 510
 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,
 519                         CvGraph* hlpGraph,
 520                         int* vertices,
 521                         int verticesCount,
 522                         int* mem,
 523                         int width )
 524 {
 525     int stekCount;
 526     int orderFirst;
 527     int orderCount;
 528     int i;
 529     int v, u;
 530     int* stek = mem;
 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;
 539
 540     stekCount = 0;
 541
 542     for( i = 0; i < verticesCount; i ++ )
 543     {
 544         v = vertices[ i ];
 545
 546         incomFlow[ v ] = outgoFlow[ v ] = 0;
 547
 548         if( v == s ) {
 549             incomFlow[ v ] = INT_INFINITY;
 550         } /* if( v == s ) */
 551         else {
 552             CvGraphVtx* hlpGraphVtx = cvGetGraphVtx( hlpGraph, v );
 553             CvGraphEdge* hlpGraphEdge = hlpGraphVtx -> first;
 554             int ofs;
 555
 556             while( hlpGraphEdge )
 557             {
 558                 int vtxIdx = cvGraphVtxIdx( hlpGraph,
 559                     hlpGraphEdge -> vtx[1] );
 560                 ofs = vtxIdx == v;
 561
 562                 if( ofs )
 563                 {
 564                     incomFlow[ v ] += ( ( Edge* )hlpGraphEdge ) -> weight;
 565                 } /* if( ofs ) */
 566
 567                 hlpGraphEdge = hlpGraphEdge -> next[ ofs ];
 568             } /* while( hlpGraphEdge ) */
 569
 570         } /* if( v == s ) else */
 571
 572         if( v == t ) {
 573             outgoFlow[ v ] = INT_INFINITY;
 574         } /* if( v == t ) */
 575         else {
 576             CvGraphVtx* hlpGraphVtx = cvGetGraphVtx( hlpGraph, v );
 577             CvGraphEdge* hlpGraphEdge = hlpGraphVtx -> first;
 578             int ofs;
 579
 580             while( hlpGraphEdge )
 581             {
 582                 int vtxIdx = cvGraphVtxIdx( hlpGraph,
 583                     hlpGraphEdge -> vtx[1] );
 584                 ofs = vtxIdx == v;
 585
 586                 if( !ofs )
 587                 {
 588                     outgoFlow[ v ] += ( ( Edge* )hlpGraphEdge ) -> weight;
 589                 } /* if( ofs ) */
 590
 591                 hlpGraphEdge = hlpGraphEdge -> next[ ofs ];
 592             } /* while( hlpGraphEdge ) */
 593
 594         } /* if( v == t ) else */
 595
 596         flow[ v ] = CV_MIN2( incomFlow[ v ], outgoFlow[ v ] );
 597
 598         if( !flow[ v ] ) {
 599             stek[ stekCount ] = v;
 600             stekCount ++;
 601         } /* if( !flow[ v ] ) */
 602
 603     } /* for( i = 0; i < verticesCount; i ++ ) */
 604
 605     for( i = 0; i < verticesCount; i ++ )
 606     {
 607         v = vertices[ i ];
 608         cargo[ v ] = 0;
 609     } /* for( i = 0; i < verticesCount; i ++ ) */
 610
 611     while( realVerticesCount > 2 )
 612     {
 613         /* deleting all vertices included in stek */
 614         while( stekCount )
 615         {
 616             v = stek[ stekCount - 1 ];
 617             stekCount --;
 618
 619             /* deleting edges incoming to v and outgoing from v */
 620             int ofs;
 621             CvGraphVtx* hlpGraphVtx = cvGetGraphVtx( hlpGraph, v );
 622             CvGraphEdge* hlpGraphEdge;
 623             if( hlpGraphVtx ) {
 624                 hlpGraphEdge = hlpGraphVtx -> first;
 625             }
 626             else {
 627                 hlpGraphEdge = NULL;
 628             }
 629             while( hlpGraphEdge )
 630             {
 631                 CvGraphVtx* hlpGraphVtx2 = hlpGraphEdge -> vtx[ 1 ];
 632                 int hlpGraphVtxIdx2 = cvGraphVtxIdx( hlpGraph,
 633                     hlpGraphVtx2 );
 634                 ofs = hlpGraphVtxIdx2 == v;
 635
 636                 if( ofs )
 637                 {
 638                     /* hlpGraphEdge is incoming edge */
 639                     CvGraphVtx* hlpGraphVtx3 = hlpGraphEdge -> vtx[0];
 640                     u = cvGraphVtxIdx( hlpGraph,
 641                                        hlpGraphVtx3 );
 642                     outgoFlow[ u ] -= ( ( Edge* )hlpGraphEdge ) -> weight
 643                         - ( ( Edge* )hlpGraphEdge ) -> flow;
 644                     cvGraphRemoveEdgeByPtr( hlpGraph,
 645                                             hlpGraphVtx3,
 646                                             hlpGraphVtx2 );
 647                     if( flow[ u ] != 0 ) {
 648                         flow[ u ] = CV_MIN2( incomFlow[u], outgoFlow[u] );
 649                         if( flow[ u ] == 0 ) {
 650                             stek[ stekCount ] = u;
 651                             stekCount ++;
 652                         }
 653                     }
 654                 } /* if( ofs ) */
 655                 else
 656                 {
 657                     /* hlpGraphEdge is outgoing edge */
 658                     CvGraphVtx* hlpGraphVtx3 = hlpGraphEdge -> vtx[1];
 659                     int u = cvGraphVtxIdx( hlpGraph,
 660                                               hlpGraphVtx3 );
 661                     incomFlow[ u ] -= ( ( Edge* )hlpGraphEdge ) -> weight
 662                         - ( ( Edge* )hlpGraphEdge ) -> flow;
 663                     cvGraphRemoveEdgeByPtr( hlpGraph,
 664                                             hlpGraphVtx2,
 665                                             hlpGraphVtx3 );
 666                     if( flow[ u ] != 0 ) {
 667                         flow[ u ] = CV_MIN2( incomFlow[u], outgoFlow[u] );
 668                         if( flow[ u ] == 0 ) {
 669                             stek[ stekCount ] = u;
 670                             stekCount ++;
 671                         }
 672                     }
 673                 } /* if( ofs ) else */
 674
 675                 hlpGraphEdge = hlpGraphEdge -> next[ ofs ];
 676
 677             } /* while( hlpGraphEdge ) */
 678
 679             /* deleting vertex v */
 680             cvGraphRemoveVtx( hlpGraph, v );
 681             realVerticesCount --;
 682
 683         } /* while( stekCount ) */
 684
 685         if( realVerticesCount > 2 ) /* the flow is not max still */
 686         {
 687             int p = INT_INFINITY;
 688             int r = -1;
 689             CvGraphVtx* graphVtx;
 690
 691             if( realVerticesCount == 3 ) {
 692                 r = r;
 693             }
 694             for( i = 0; i < hlpGraph -> total - 2; i ++ )
 695             {
 696                 graphVtx = cvGetGraphVtx( hlpGraph, i );
 697                 if( graphVtx ) {
 698                     v = cvGraphVtxIdx( hlpGraph, graphVtx );
 699                     if( flow[ v ] < p ) {
 700                         r = v;
 701                         p = flow[ v ];
 702                     }
 703                 }
 704
 705             } /* for( i = 0; i < hlpGraph -> total - 2; i ++ ) */
 706
 707             /* building of size p flow from r to t */
 708             orderCount = orderFirst = 0;
 709             order[ orderCount ] = r;
 710             orderCount ++;
 711
 712             v = order[ orderFirst ];
 713             orderFirst ++;
 714
 715             cargo[ r ] = p;
 716             do /* while( v != t ) */
 717             {
 718                 incomFlow[ v ] -= cargo[ v ];
 719                 outgoFlow[ v ] -= cargo[ v ];
 720                 flow[ v ] -= cargo[ v ];
 721
 722                 if( flow[ v ] == 0 ) {
 723                     stek[ stekCount ] = v;
 724                     stekCount ++;
 725                 }
 726
 727                 if( v == t ) {
 728                     cargo[ v ] = p;
 729                 }
 730                 else
 731                 {
 732                     int ofs;
 733                     CvGraphVtx* hlpGraphVtx2;
 734                     CvGraphVtx* hlpGraphVtx = cvGetGraphVtx( hlpGraph, v );
 735                     CvGraphEdge* hlpGraphEdge = hlpGraphVtx -> first;
 736                     CvGraphEdge* hlpGraphEdge2 = NULL;
 737
 738                     while( hlpGraphEdge && cargo[ v ] > 0 )
 739                     {
 740                         hlpGraphVtx2 = hlpGraphEdge -> vtx[ 1 ];
 741                         u = cvGraphVtxIdx( hlpGraph, hlpGraphVtx2 );
 742                         ofs = u == v;
 743
 744                         if( !ofs )
 745                         {
 746                             if( cargo[ u ] == 0 ) {
 747                                 order[ orderCount ] = u;
 748                                 orderCount ++;
 749                             }
 750                             int delta = ( ( Edge* )hlpGraphEdge ) -> weight
 751                                 - ( ( Edge* )hlpGraphEdge ) -> flow;
 752                             delta = CV_MIN2( cargo[ v ], delta );
 753                             ( ( Edge* )hlpGraphEdge ) -> flow += delta;
 754                             cargo[ v ] -= delta;
 755                             cargo[ u ] += delta;
 756                             if( ( ( Edge* )hlpGraphEdge ) -> weight ==
 757                                 ( ( Edge* )hlpGraphEdge ) -> flow )
 758                             {
 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] );
 768                             }
 769                         } /* if( !ofs ) */
 770
 771                         if( hlpGraphEdge2 ) {
 772                             hlpGraphEdge = hlpGraphEdge2;
 773                             hlpGraphEdge2 = NULL;
 774                         }
 775                         else {
 776                             hlpGraphEdge = hlpGraphEdge -> next[ ofs ];
 777                         }
 778                     } /* while( hlpGraphEdge && cargo[ v ] > 0 ) */
 779
 780                 } /* if( v == t ) else */
 781
 782                 v = order[ orderFirst ];
 783                 orderFirst ++;
 784
 785             } while( v != t ); /* do */
 786
 787             /* building of size p flow from s to r */
 788             orderCount = orderFirst = 0;
 789             order[ orderCount ] = r;
 790             orderCount ++;
 791
 792             v = order[ orderFirst ];
 793             orderFirst ++;
 794
 795             cargo[ r ] = p;
 796             do /* while( v != s ) */
 797             {
 798                 if( v != r )
 799                 {
 800                     incomFlow[ v ] -= cargo[ v ];
 801                     outgoFlow[ v ] -= cargo[ v ];
 802                     flow[ v ] -= cargo[ v ];
 803                     if( flow[ v ] == 0 ) {
 804                         stek[ stekCount ] = v;
 805                         stekCount ++;
 806                     }
 807                 } /* if( v != r ) */
 808
 809                 if( v == s ) {
 810                     cargo[ v ] = 0;
 811                 } /* if( v == s ) */
 812                 else
 813                 {
 814                     int ofs;
 815
 816                     CvGraphVtx* hlpGraphVtx = cvGetGraphVtx( hlpGraph, v );
 817                     CvGraphEdge* hlpGraphEdge = hlpGraphVtx -> first;
 818                     CvGraphEdge* hlpGraphEdge2 = NULL;
 819                     while( hlpGraphEdge && cargo[ v ] > 0 )
 820                     {
 821                         u = cvGraphVtxIdx( hlpGraph,
 822                                 hlpGraphEdge -> vtx[ 1 ] );
 823                         ofs = u == v;
 824
 825                         if( ofs )
 826                         {
 827                             u = cvGraphVtxIdx( hlpGraph,
 828                                     hlpGraphEdge -> vtx[ 0 ] );
 829
 830                             if( cargo[ u ] == 0 ) {
 831                                 order[ orderCount ] = u;
 832                                 orderCount ++;
 833                             }
 834
 835                             int delta = ( ( Edge* )hlpGraphEdge ) -> weight
 836                                 - ( ( Edge* )hlpGraphEdge ) -> flow;
 837
 838                             delta = CV_MIN2( cargo[ v ], delta );
 839
 840                             (( ( Edge* )hlpGraphEdge ) -> flow) += delta;
 841
 842                             cargo[ v ] -= delta;
 843                             cargo[ u ] += delta;
 844
 845                             if( ( ( Edge* )hlpGraphEdge ) -> weight ==
 846                                 ( ( Edge* )hlpGraphEdge ) -> flow )
 847                             {
 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] );
 856                             }
 857                         } /* if( ofs ) */
 858
 859                         if( hlpGraphEdge2 ) {
 860                             hlpGraphEdge = hlpGraphEdge2;
 861                             hlpGraphEdge2 = NULL;
 862                         }
 863                         else {
 864                             hlpGraphEdge = hlpGraphEdge -> next[ ofs ];
 865                         }
 866                     } /* while( hlpGraphEdge && cargo[ v ] > 0 ) */
 867
 868                 } /* if( v == s ) else */
 869
 870                 v = order[ orderFirst ]; //added
 871                 orderFirst ++; //added
 872
 873             } while( v != s ); /* do */
 874
 875         } /* if( hlpGraph -> total > 2 ) */
 876
 877     } /* while( hlpGraph -> total > 2 ) */
 878
 879 } /* makePseudoMaxFlow */
 880
 881
 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
 891 //                        function
 892 //      storage         - pointer to CvMemStorage structure
 893 bool oneStep( unsigned char* leftLine,
 894               unsigned char* rightLine,
 895               int alpha,
 896               int beta,
 897               int* corr,
 898               int width,
 899               int* mem,
 900               int* vertices,
 901               CvMemStorage* storage )
 902 {
 903     CvGraph* graph = NULL;
 904     CvGraph* hlpGraph = NULL;
 905     CvMemStoragePos storagePos;
 906     int i;
 907     bool change = false;
 908     cvSaveMemStoragePos( storage, &storagePos );
 909
 910     int verticesCount;
 911
 912     makeGraph( &graph, leftLine, rightLine, alpha, beta, corr, width, storage );
 913
 914     int s = graph -> total - 2; /* source vertex - alpha vertex */
 915     //int t = graph -> total - 1; /* terminate vertex - beta vertex */
 916
 917     int length = makeHelpGraph( graph,
 918                                 &hlpGraph,
 919                                 storage,
 920                                 mem,
 921                                 vertices,
 922                                 &verticesCount,
 923                                 width );
 924     while( length != INT_INFINITY )
 925     {
 926         change = true;
 927         makePseudoMaxFlow( graph,
 928                            hlpGraph,
 929                            vertices,
 930                            verticesCount,
 931                            mem,
 932                            width );
 933         cvClearGraph( hlpGraph );
 934         length = makeHelpGraph( graph,
 935                                 &hlpGraph,
 936                                 storage,
 937                                 mem,
 938                                 vertices,
 939                                 &verticesCount,
 940                                 width );
 941     } /* while( length != INT_INFINITY ) */
 942
 943     int coord;
 944     CvGraphVtx* graphVtx;
 945     for( i = 0; i < s; i ++ )
 946     {
 947         CvGraphEdge* graphEdge = cvFindGraphEdge( graph, s, i );
 948
 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
 956                 change = true;
 957             }
 958             else {
 959                 corr[ coord ] = alpha;
 960             }
 961         } /* if( ( ( Edge* )graphEdge ) -> weight == ... */
 962         else
 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
 968                 change = true;
 969             }
 970             else {
 971                 corr[ coord ] = beta;
 972             }
 973         } /* if( ( ( Edge* )graphEdge ) -> weight == ... else */
 974
 975     } /* for( i = 0; i < s; i ++ ) */
 976
 977     cvClearGraph( hlpGraph );
 978     cvClearGraph( graph );
 979
 980     cvRestoreMemStoragePos( storage, &storagePos );
 981
 982     return change;
 983
 984 } /* oneStep */
 985
 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 )
 992 {
 993     int i;
 994     int pixelDifferenceRange = maxPixelDifference * 2 + 1;
 995
 996     for( i = 0; i < width; i ++ )
 997     {
 998         corr[ i ] = i % pixelDifferenceRange - maxPixelDifference;
 999     }
1000 } /* initCorr */
1001
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
1006 //                                line
1007 //      mem                     - pointer to memory allocated by allocTempMem
1008 //                                function
1009 //      vertices                - pointer to memory allocated by allocTempMem
1010 //                                function
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,
1017                   int* corr,
1018                   int* mem,
1019                   int* vertices,
1020                   int width,
1021                   int maxPixelDifference,
1022                   CvMemStorage* storage )
1023 {
1024     int result = 1;
1025     int count = 0;
1026     int i, j;
1027
1028     initCorr( corr, width, maxPixelDifference );
1029     while( result )
1030     {
1031         result = 0;
1032
1033         for( i = - maxPixelDifference; i < maxPixelDifference; i ++ )
1034         for( j = i + 1; j <= maxPixelDifference; j ++ )
1035         {
1036             result += (int)oneStep( leftLine,
1037                                rightLine,
1038                                i,
1039                                j,
1040                                corr,
1041                                width,
1042                                mem,
1043                                vertices,
1044                                storage );
1045         } /* for( j = i + 1; j < width; j ++ ) */
1046
1047         count ++;
1048         if( count > /*0*//*1*/2 ) {
1049             break;
1050         }
1051
1052     } /* while( result ) */
1053
1054 } /* oneLineCorr */
1055
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
1067 //                            storage
1068 void allLinesCorr( unsigned char* leftImage,
1069                    int leftLineStep,
1070                    unsigned char* rightImage,
1071                    int rightLineStep,
1072                    int width,
1073                    int height,
1074                    int* corr,
1075                    int maxPixelDifference,
1076                    CvMemStorage* storage )
1077 {
1078     int i;
1079     unsigned char* leftLine = leftImage;
1080     unsigned char* rightLine = rightImage;
1081     int* mem;
1082     int* vertices;
1083
1084     allocTempMem( &mem,
1085                   &vertices,
1086                   width );
1087
1088     for( i = 0; i < height; i ++ )
1089     {
1090         oneLineCorr( leftLine,
1091                      rightLine,
1092                      corr + i * width,
1093                      mem,
1094                      vertices,
1095                      width,
1096                      maxPixelDifference,
1097                      storage );
1098         leftLine += leftLineStep;
1099         rightLine += rightLineStep;
1100     } /* for( i = 0; i < height; i ++ ) */
1101
1102     freeTempMem( &mem,
1103                  &vertices );
1104
1105 } /* allLinesCorr */
1106
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,
1126             int _leftLineStep,
1127             unsigned char* _rightImage,
1128             int _rightLineStep,
1129             unsigned char* _resultImage,
1130             int _resultLineStep,
1131             int* _corrArray,
1132             int width,
1133             int height,
1134             float alpha,
1135             morphImageType imageNeed,
1136             int maxDifference
1137           )
1138 {
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;
1145
1146     int lineNumber;
1147     unsigned char* leftTemp;
1148     unsigned char* middleTemp;
1149     unsigned char* rightTemp;
1150     int leftPixel;
1151     int prevLeftPixel;
1152     int middlePixel;
1153     int prevMiddlePixel;
1154     int rightPixel;
1155     int prevRightPixel;
1156     int leftPixel3;
1157     int middlePixel3;
1158     int rightPixel3;
1159     int i;
1160     int j;
1161     int tempIndex;
1162     int* result;
1163     int number;
1164     float alpha1        = 1.0f - alpha;
1165
1166     for( lineNumber = 0; lineNumber < height; lineNumber ++ )
1167     {
1168         leftTemp    = leftArray + leftLineSize * lineNumber;
1169         middleTemp  = middleArray + middleLineSize * lineNumber;
1170         rightTemp   = rightArray + rightLineSize * lineNumber;
1171         memset( ( void* )middleTemp, 0, middleLineSize );
1172
1173         result = _corrArray + width * lineNumber;
1174         number = width;
1175
1176         prevLeftPixel   = 0;
1177         prevRightPixel  = prevLeftPixel + result[ 0 ];
1178         if( prevRightPixel >= width ) {
1179             prevRightPixel = width - 1;
1180         }
1181         else if ( prevRightPixel < 0 ) {
1182             prevRightPixel = 0;
1183         }
1184         prevMiddlePixel =
1185             (int)( prevLeftPixel * alpha1 + prevRightPixel * alpha );
1186         for( i = 0; i < number - 1; i ++ )
1187         {
1188             leftPixel       = i;
1189             rightPixel      = i + result[ i ];
1190             if( rightPixel >= width ) {
1191                 rightPixel = width - 1;
1192             }
1193             else if( rightPixel < 0 ) {
1194                 rightPixel = 0;
1195             }
1196             middlePixel     =
1197                 (int)( leftPixel * alpha1 + rightPixel * alpha );
1198             leftPixel3      = leftPixel * 3;
1199             middlePixel3    = middlePixel * 3;
1200             rightPixel3     = rightPixel * 3;
1201
1202             if( imageNeed == morphDepthMap ) {
1203                 int t   = leftPixel - rightPixel + maxDifference;
1204                 t       = t < 0 ? -t : t;
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 )
1210             else
1211             {
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 );
1221
1222                 if( middlePixel - prevMiddlePixel > 1 ) // occlusion
1223                 {
1224                     if( leftPixel - prevLeftPixel > 1 )
1225                     {
1226                         int LenSrc  = leftPixel - prevLeftPixel - 2;
1227                         int LenDest = middlePixel - prevMiddlePixel - 1;
1228                         for( j = prevMiddlePixel + 1; j < middlePixel; j ++ )
1229                         {
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 ];
1238                         }
1239                     } // if( leftPixel - prevLeftPixel > 1 )
1240                     else
1241                     {
1242                         int LenSrc  = rightPixel - prevRightPixel - 2;
1243                         int LenDest = middlePixel - prevMiddlePixel - 1;
1244                         for( j = prevMiddlePixel + 1; j < middlePixel; j ++ )
1245                         {
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 ];
1254                         }
1255                     } // if( leftPixel - prevLeftPixel > 1 ) else
1256
1257                 } // if( middlePixel - prevMiddlePixel > 1 )
1258
1259             } // if( imageNeed == morphDepthMap ) else
1260
1261             if( middlePixel > prevMiddlePixel ) {
1262                 if( leftPixel > prevLeftPixel )
1263                     prevLeftPixel   = leftPixel;
1264                 if( rightPixel > prevRightPixel )
1265                     prevRightPixel  = rightPixel;
1266                 prevMiddlePixel = middlePixel;
1267             }
1268         } // for( i = number - 1; i >= 0; i -- )
1269
1270     } // for( lineNumber = 0; lineNumber < LeftImage -> m_Raster -> GetHeight() )
1271
1272 } // Morph
1273
1274 bool  CCvGraphCutMorpher::OnCalculateStereo()
1275 {
1276     CvSize imageSizeLeft = GetImageSize( m_left_img ),
1277            imageSizeRight = GetImageSize( m_right_img );
1278
1279     if( ( imageSizeLeft.width != imageSizeRight.width )
1280         || ( imageSizeLeft.height != imageSizeRight.height ) )
1281     {
1282         return false;
1283     }
1284
1285     if( m_corr ) {
1286         free( m_corr );
1287         m_corr = NULL;
1288     }
1289     m_corr = ( int* ) malloc( m_left_img -> width
1290         * m_left_img -> height
1291         * sizeof( int ) );
1292
1293     if( !m_storage ) {
1294         m_storage = cvCreateMemStorage( 0 );
1295         m_isStorageAllocated = true;
1296     }
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,
1304                   m_corr,
1305                   m_maxPixelDifference,
1306                   m_storage );
1307
1308     m_isStereoReady = true;
1309
1310     return true;
1311 }
1312
1313 bool  CCvGraphCutMorpher::OnCalculateVirtualImage()
1314 {
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,
1322            m_corr,
1323            m_left_img -> width,
1324            m_left_img -> height,
1325            m_pan );
1326
1327     m_isVirtualImageReady = true;
1328
1329     return true;
1330 }
1331
1332 bool  CCvGraphCutMorpher::OnCalculateDisparity()
1333 {
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,
1340            m_corr,
1341            m_left_img -> width,
1342            m_left_img -> height,
1343            m_pan,
1344            morphDepthMap,
1345            m_maxPixelDifference );
1346
1347     return true;
1348 }
1349
1350 bool  CCvGraphCutMorpher::OnCalculateDisparityImage()
1351 {
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,
1358            m_corr,
1359            m_left_img -> width,
1360            m_left_img -> height,
1361            m_pan,
1362            morphDepthMap,
1363            m_maxPixelDifference );
1364
1365     return true;
1366 }
1367
1368 CCvGraphCutMorpher::CCvGraphCutMorpher()
1369 {
1370     m_maxPixelDifference = MAX_DIFFERENCE;
1371     m_corr = 0;
1372     m_isStereoReady = false;
1373     m_isVirtualImageReady = false;
1374     m_isDisparityReady = false;
1375     m_storage = NULL;
1376     m_isStorageAllocated = false;
1377 }
1378
1379 #endif
1380
1381 /* End of file */