--- /dev/null
+/*M///////////////////////////////////////////////////////////////////////////////////////
+//
+// IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.
+//
+// By downloading, copying, installing or using the software you agree to this license.
+// If you do not agree to this license, do not download, install,
+// copy or use the software.
+//
+//
+// Intel License Agreement
+// For Open Source Computer Vision Library
+//
+// Copyright (C) 2000, Intel Corporation, all rights reserved.
+// Third party copyrights are property of their respective owners.
+//
+// Redistribution and use in source and binary forms, with or without modification,
+// are permitted provided that the following conditions are met:
+//
+// * Redistribution's of source code must retain the above copyright notice,
+// this list of conditions and the following disclaimer.
+//
+// * Redistribution's in binary form must reproduce the above copyright notice,
+// this list of conditions and the following disclaimer in the documentation
+// and/or other materials provided with the distribution.
+//
+// * The name of Intel Corporation may not be used to endorse or promote products
+// derived from this software without specific prior written permission.
+//
+// This software is provided by the copyright holders and contributors "as is" and
+// any express or implied warranties, including, but not limited to, the implied
+// warranties of merchantability and fitness for a particular purpose are disclaimed.
+// In no event shall the Intel Corporation or contributors be liable for any direct,
+// indirect, incidental, special, exemplary, or consequential damages
+// (including, but not limited to, procurement of substitute goods or services;
+// loss of use, data, or profits; or business interruption) however caused
+// and on any theory of liability, whether in contract, strict liability,
+// or tort (including negligence or otherwise) arising in any way out of
+// the use of this software, even if advised of the possibility of such damage.
+//
+//M*/
+#include "_cv.h"
+
+typedef struct
+{
+ float xx;
+ float xy;
+ float yy;
+ float xt;
+ float yt;
+}
+icvDerProduct;
+
+
+#define CONV( A, B, C) ((float)( A + (B<<1) + C ))
+/*F///////////////////////////////////////////////////////////////////////////////////////
+// Name: icvCalcOpticalFlowLK_8u32fR ( Lucas & Kanade method )
+// Purpose: calculate Optical flow for 2 images using Lucas & Kanade algorithm
+// Context:
+// Parameters:
+// imgA, // pointer to first frame ROI
+// imgB, // pointer to second frame ROI
+// imgStep, // width of single row of source images in bytes
+// imgSize, // size of the source image ROI
+// winSize, // size of the averaging window used for grouping
+// velocityX, // pointer to horizontal and
+// velocityY, // vertical components of optical flow ROI
+// velStep // width of single row of velocity frames in bytes
+//
+// Returns: CV_OK - all ok
+// CV_OUTOFMEM_ERR - insufficient memory for function work
+// CV_NULLPTR_ERR - if one of input pointers is NULL
+// CV_BADSIZE_ERR - wrong input sizes interrelation
+//
+// Notes: 1.Optical flow to be computed for every pixel in ROI
+// 2.For calculating spatial derivatives we use 3x3 Sobel operator.
+// 3.We use the following border mode.
+// The last row or column is replicated for the border
+// ( IPL_BORDER_REPLICATE in IPL ).
+//
+//
+//F*/
+static CvStatus CV_STDCALL
+icvCalcOpticalFlowLK_8u32fR( uchar * imgA,
+ uchar * imgB,
+ int imgStep,
+ CvSize imgSize,
+ CvSize winSize,
+ float *velocityX,
+ float *velocityY, int velStep )
+{
+ /* Loops indexes */
+ int i, j, k;
+
+ /* Gaussian separable kernels */
+ float GaussX[16];
+ float GaussY[16];
+ float *KerX;
+ float *KerY;
+
+ /* Buffers for Sobel calculations */
+ float *MemX[2];
+ float *MemY[2];
+
+ float ConvX, ConvY;
+ float GradX, GradY, GradT;
+
+ int winWidth = winSize.width;
+ int winHeight = winSize.height;
+
+ int imageWidth = imgSize.width;
+ int imageHeight = imgSize.height;
+
+ int HorRadius = (winWidth - 1) >> 1;
+ int VerRadius = (winHeight - 1) >> 1;
+
+ int PixelLine;
+ int ConvLine;
+
+ int BufferAddress;
+
+ int BufferHeight = 0;
+ int BufferWidth;
+ int BufferSize;
+
+ /* buffers derivatives product */
+ icvDerProduct *II;
+
+ /* buffers for gaussian horisontal convolution */
+ icvDerProduct *WII;
+
+ /* variables for storing number of first pixel of image line */
+ int Line1;
+ int Line2;
+ int Line3;
+
+ /* we must have 2*2 linear system coeffs
+ | A1B2 B1 | {u} {C1} {0}
+ | | { } + { } = { }
+ | A2 A1B2 | {v} {C2} {0}
+ */
+ float A1B2, A2, B1, C1, C2;
+
+ int pixNumber;
+
+ /* auxiliary */
+ int NoMem = 0;
+
+ velStep /= sizeof(velocityX[0]);
+
+ /* Checking bad arguments */
+ if( imgA == NULL )
+ return CV_NULLPTR_ERR;
+ if( imgB == NULL )
+ return CV_NULLPTR_ERR;
+
+ if( imageHeight < winHeight )
+ return CV_BADSIZE_ERR;
+ if( imageWidth < winWidth )
+ return CV_BADSIZE_ERR;
+
+ if( winHeight >= 16 )
+ return CV_BADSIZE_ERR;
+ if( winWidth >= 16 )
+ return CV_BADSIZE_ERR;
+
+ if( !(winHeight & 1) )
+ return CV_BADSIZE_ERR;
+ if( !(winWidth & 1) )
+ return CV_BADSIZE_ERR;
+
+ BufferHeight = winHeight;
+ BufferWidth = imageWidth;
+
+ /****************************************************************************************/
+ /* Computing Gaussian coeffs */
+ /****************************************************************************************/
+ GaussX[0] = 1;
+ GaussY[0] = 1;
+ for( i = 1; i < winWidth; i++ )
+ {
+ GaussX[i] = 1;
+ for( j = i - 1; j > 0; j-- )
+ {
+ GaussX[j] += GaussX[j - 1];
+ }
+ }
+ for( i = 1; i < winHeight; i++ )
+ {
+ GaussY[i] = 1;
+ for( j = i - 1; j > 0; j-- )
+ {
+ GaussY[j] += GaussY[j - 1];
+ }
+ }
+ KerX = &GaussX[HorRadius];
+ KerY = &GaussY[VerRadius];
+
+ /****************************************************************************************/
+ /* Allocating memory for all buffers */
+ /****************************************************************************************/
+ for( k = 0; k < 2; k++ )
+ {
+ MemX[k] = (float *) cvAlloc( (imgSize.height) * sizeof( float ));
+
+ if( MemX[k] == NULL )
+ NoMem = 1;
+ MemY[k] = (float *) cvAlloc( (imgSize.width) * sizeof( float ));
+
+ if( MemY[k] == NULL )
+ NoMem = 1;
+ }
+
+ BufferSize = BufferHeight * BufferWidth;
+
+ II = (icvDerProduct *) cvAlloc( BufferSize * sizeof( icvDerProduct ));
+ WII = (icvDerProduct *) cvAlloc( BufferSize * sizeof( icvDerProduct ));
+
+
+ if( (II == NULL) || (WII == NULL) )
+ NoMem = 1;
+
+ if( NoMem )
+ {
+ for( k = 0; k < 2; k++ )
+ {
+ if( MemX[k] )
+ cvFree( &MemX[k] );
+
+ if( MemY[k] )
+ cvFree( &MemY[k] );
+ }
+ if( II )
+ cvFree( &II );
+ if( WII )
+ cvFree( &WII );
+
+ return CV_OUTOFMEM_ERR;
+ }
+
+ /****************************************************************************************/
+ /* Calculate first line of memX and memY */
+ /****************************************************************************************/
+ MemY[0][0] = MemY[1][0] = CONV( imgA[0], imgA[0], imgA[1] );
+ MemX[0][0] = MemX[1][0] = CONV( imgA[0], imgA[0], imgA[imgStep] );
+
+ for( j = 1; j < imageWidth - 1; j++ )
+ {
+ MemY[0][j] = MemY[1][j] = CONV( imgA[j - 1], imgA[j], imgA[j + 1] );
+ }
+
+ pixNumber = imgStep;
+ for( i = 1; i < imageHeight - 1; i++ )
+ {
+ MemX[0][i] = MemX[1][i] = CONV( imgA[pixNumber - imgStep],
+ imgA[pixNumber], imgA[pixNumber + imgStep] );
+ pixNumber += imgStep;
+ }
+
+ MemY[0][imageWidth - 1] =
+ MemY[1][imageWidth - 1] = CONV( imgA[imageWidth - 2],
+ imgA[imageWidth - 1], imgA[imageWidth - 1] );
+
+ MemX[0][imageHeight - 1] =
+ MemX[1][imageHeight - 1] = CONV( imgA[pixNumber - imgStep],
+ imgA[pixNumber], imgA[pixNumber] );
+
+
+ /****************************************************************************************/
+ /* begin scan image, calc derivatives and solve system */
+ /****************************************************************************************/
+
+ PixelLine = -VerRadius;
+ ConvLine = 0;
+ BufferAddress = -BufferWidth;
+
+ while( PixelLine < imageHeight )
+ {
+ if( ConvLine < imageHeight )
+ {
+ /*Here we calculate derivatives for line of image */
+ int address;
+
+ i = ConvLine;
+ int L1 = i - 1;
+ int L2 = i;
+ int L3 = i + 1;
+
+ int memYline = L3 & 1;
+
+ if( L1 < 0 )
+ L1 = 0;
+ if( L3 >= imageHeight )
+ L3 = imageHeight - 1;
+
+ BufferAddress += BufferWidth;
+ BufferAddress -= ((BufferAddress >= BufferSize) ? 0xffffffff : 0) & BufferSize;
+
+ address = BufferAddress;
+
+ Line1 = L1 * imgStep;
+ Line2 = L2 * imgStep;
+ Line3 = L3 * imgStep;
+
+ /* Process first pixel */
+ ConvX = CONV( imgA[Line1 + 1], imgA[Line2 + 1], imgA[Line3 + 1] );
+ ConvY = CONV( imgA[Line3], imgA[Line3], imgA[Line3 + 1] );
+
+ GradY = ConvY - MemY[memYline][0];
+ GradX = ConvX - MemX[1][L2];
+
+ MemY[memYline][0] = ConvY;
+ MemX[1][L2] = ConvX;
+
+ GradT = (float) (imgB[Line2] - imgA[Line2]);
+
+ II[address].xx = GradX * GradX;
+ II[address].xy = GradX * GradY;
+ II[address].yy = GradY * GradY;
+ II[address].xt = GradX * GradT;
+ II[address].yt = GradY * GradT;
+ address++;
+ /* Process middle of line */
+ for( j = 1; j < imageWidth - 1; j++ )
+ {
+ ConvX = CONV( imgA[Line1 + j + 1], imgA[Line2 + j + 1], imgA[Line3 + j + 1] );
+ ConvY = CONV( imgA[Line3 + j - 1], imgA[Line3 + j], imgA[Line3 + j + 1] );
+
+ GradY = ConvY - MemY[memYline][j];
+ GradX = ConvX - MemX[(j - 1) & 1][L2];
+
+ MemY[memYline][j] = ConvY;
+ MemX[(j - 1) & 1][L2] = ConvX;
+
+ GradT = (float) (imgB[Line2 + j] - imgA[Line2 + j]);
+
+ II[address].xx = GradX * GradX;
+ II[address].xy = GradX * GradY;
+ II[address].yy = GradY * GradY;
+ II[address].xt = GradX * GradT;
+ II[address].yt = GradY * GradT;
+
+ address++;
+ }
+ /* Process last pixel of line */
+ ConvX = CONV( imgA[Line1 + imageWidth - 1], imgA[Line2 + imageWidth - 1],
+ imgA[Line3 + imageWidth - 1] );
+
+ ConvY = CONV( imgA[Line3 + imageWidth - 2], imgA[Line3 + imageWidth - 1],
+ imgA[Line3 + imageWidth - 1] );
+
+
+ GradY = ConvY - MemY[memYline][imageWidth - 1];
+ GradX = ConvX - MemX[(imageWidth - 2) & 1][L2];
+
+ MemY[memYline][imageWidth - 1] = ConvY;
+
+ GradT = (float) (imgB[Line2 + imageWidth - 1] - imgA[Line2 + imageWidth - 1]);
+
+ II[address].xx = GradX * GradX;
+ II[address].xy = GradX * GradY;
+ II[address].yy = GradY * GradY;
+ II[address].xt = GradX * GradT;
+ II[address].yt = GradY * GradT;
+ address++;
+
+ /* End of derivatives for line */
+
+ /****************************************************************************************/
+ /* ---------Calculating horizontal convolution of processed line----------------------- */
+ /****************************************************************************************/
+ address -= BufferWidth;
+ /* process first HorRadius pixels */
+ for( j = 0; j < HorRadius; j++ )
+ {
+ int jj;
+
+ WII[address].xx = 0;
+ WII[address].xy = 0;
+ WII[address].yy = 0;
+ WII[address].xt = 0;
+ WII[address].yt = 0;
+
+ for( jj = -j; jj <= HorRadius; jj++ )
+ {
+ float Ker = KerX[jj];
+
+ WII[address].xx += II[address + jj].xx * Ker;
+ WII[address].xy += II[address + jj].xy * Ker;
+ WII[address].yy += II[address + jj].yy * Ker;
+ WII[address].xt += II[address + jj].xt * Ker;
+ WII[address].yt += II[address + jj].yt * Ker;
+ }
+ address++;
+ }
+ /* process inner part of line */
+ for( j = HorRadius; j < imageWidth - HorRadius; j++ )
+ {
+ int jj;
+ float Ker0 = KerX[0];
+
+ WII[address].xx = 0;
+ WII[address].xy = 0;
+ WII[address].yy = 0;
+ WII[address].xt = 0;
+ WII[address].yt = 0;
+
+ for( jj = 1; jj <= HorRadius; jj++ )
+ {
+ float Ker = KerX[jj];
+
+ WII[address].xx += (II[address - jj].xx + II[address + jj].xx) * Ker;
+ WII[address].xy += (II[address - jj].xy + II[address + jj].xy) * Ker;
+ WII[address].yy += (II[address - jj].yy + II[address + jj].yy) * Ker;
+ WII[address].xt += (II[address - jj].xt + II[address + jj].xt) * Ker;
+ WII[address].yt += (II[address - jj].yt + II[address + jj].yt) * Ker;
+ }
+ WII[address].xx += II[address].xx * Ker0;
+ WII[address].xy += II[address].xy * Ker0;
+ WII[address].yy += II[address].yy * Ker0;
+ WII[address].xt += II[address].xt * Ker0;
+ WII[address].yt += II[address].yt * Ker0;
+
+ address++;
+ }
+ /* process right side */
+ for( j = imageWidth - HorRadius; j < imageWidth; j++ )
+ {
+ int jj;
+
+ WII[address].xx = 0;
+ WII[address].xy = 0;
+ WII[address].yy = 0;
+ WII[address].xt = 0;
+ WII[address].yt = 0;
+
+ for( jj = -HorRadius; jj < imageWidth - j; jj++ )
+ {
+ float Ker = KerX[jj];
+
+ WII[address].xx += II[address + jj].xx * Ker;
+ WII[address].xy += II[address + jj].xy * Ker;
+ WII[address].yy += II[address + jj].yy * Ker;
+ WII[address].xt += II[address + jj].xt * Ker;
+ WII[address].yt += II[address + jj].yt * Ker;
+ }
+ address++;
+ }
+ }
+
+ /****************************************************************************************/
+ /* Calculating velocity line */
+ /****************************************************************************************/
+ if( PixelLine >= 0 )
+ {
+ int USpace;
+ int BSpace;
+ int address;
+
+ if( PixelLine < VerRadius )
+ USpace = PixelLine;
+ else
+ USpace = VerRadius;
+
+ if( PixelLine >= imageHeight - VerRadius )
+ BSpace = imageHeight - PixelLine - 1;
+ else
+ BSpace = VerRadius;
+
+ address = ((PixelLine - USpace) % BufferHeight) * BufferWidth;
+ for( j = 0; j < imageWidth; j++ )
+ {
+ int addr = address;
+
+ A1B2 = 0;
+ A2 = 0;
+ B1 = 0;
+ C1 = 0;
+ C2 = 0;
+
+ for( i = -USpace; i <= BSpace; i++ )
+ {
+ A2 += WII[addr + j].xx * KerY[i];
+ A1B2 += WII[addr + j].xy * KerY[i];
+ B1 += WII[addr + j].yy * KerY[i];
+ C2 += WII[addr + j].xt * KerY[i];
+ C1 += WII[addr + j].yt * KerY[i];
+
+ addr += BufferWidth;
+ addr -= ((addr >= BufferSize) ? 0xffffffff : 0) & BufferSize;
+ }
+ /****************************************************************************************\
+ * Solve Linear System *
+ \****************************************************************************************/
+ {
+ float delta = (A1B2 * A1B2 - A2 * B1);
+
+ if( delta )
+ {
+ /* system is not singular - solving by Kramer method */
+ float deltaX;
+ float deltaY;
+ float Idelta = 8 / delta;
+
+ deltaX = -(C1 * A1B2 - C2 * B1);
+ deltaY = -(A1B2 * C2 - A2 * C1);
+
+ velocityX[j] = deltaX * Idelta;
+ velocityY[j] = deltaY * Idelta;
+ }
+ else
+ {
+ /* singular system - find optical flow in gradient direction */
+ float Norm = (A1B2 + A2) * (A1B2 + A2) + (B1 + A1B2) * (B1 + A1B2);
+
+ if( Norm )
+ {
+ float IGradNorm = 8 / Norm;
+ float temp = -(C1 + C2) * IGradNorm;
+
+ velocityX[j] = (A1B2 + A2) * temp;
+ velocityY[j] = (B1 + A1B2) * temp;
+
+ }
+ else
+ {
+ velocityX[j] = 0;
+ velocityY[j] = 0;
+ }
+ }
+ }
+ /****************************************************************************************\
+ * End of Solving Linear System *
+ \****************************************************************************************/
+ } /*for */
+ velocityX += velStep;
+ velocityY += velStep;
+ } /*for */
+ PixelLine++;
+ ConvLine++;
+ }
+
+ /* Free memory */
+ for( k = 0; k < 2; k++ )
+ {
+ cvFree( &MemX[k] );
+ cvFree( &MemY[k] );
+ }
+ cvFree( &II );
+ cvFree( &WII );
+
+ return CV_OK;
+} /*icvCalcOpticalFlowLK_8u32fR*/
+
+
+/*F///////////////////////////////////////////////////////////////////////////////////////
+// Name: cvCalcOpticalFlowLK
+// Purpose: Optical flow implementation
+// Context:
+// Parameters:
+// srcA, srcB - source image
+// velx, vely - destination image
+// Returns:
+//
+// Notes:
+//F*/
+CV_IMPL void
+cvCalcOpticalFlowLK( const void* srcarrA, const void* srcarrB, CvSize winSize,
+ void* velarrx, void* velarry )
+{
+ CV_FUNCNAME( "cvCalcOpticalFlowLK" );
+
+ __BEGIN__;
+
+ CvMat stubA, *srcA = (CvMat*)srcarrA;
+ CvMat stubB, *srcB = (CvMat*)srcarrB;
+ CvMat stubx, *velx = (CvMat*)velarrx;
+ CvMat stuby, *vely = (CvMat*)velarry;
+
+ CV_CALL( srcA = cvGetMat( srcA, &stubA ));
+ CV_CALL( srcB = cvGetMat( srcB, &stubB ));
+
+ CV_CALL( velx = cvGetMat( velx, &stubx ));
+ CV_CALL( vely = cvGetMat( vely, &stuby ));
+
+ if( !CV_ARE_TYPES_EQ( srcA, srcB ))
+ CV_ERROR( CV_StsUnmatchedFormats, "Source images have different formats" );
+
+ if( !CV_ARE_TYPES_EQ( velx, vely ))
+ CV_ERROR( CV_StsUnmatchedFormats, "Destination images have different formats" );
+
+ if( !CV_ARE_SIZES_EQ( srcA, srcB ) ||
+ !CV_ARE_SIZES_EQ( velx, vely ) ||
+ !CV_ARE_SIZES_EQ( srcA, velx ))
+ CV_ERROR( CV_StsUnmatchedSizes, "" );
+
+ if( CV_MAT_TYPE( srcA->type ) != CV_8UC1 ||
+ CV_MAT_TYPE( velx->type ) != CV_32FC1 )
+ CV_ERROR( CV_StsUnsupportedFormat, "Source images must have 8uC1 type and "
+ "destination images must have 32fC1 type" );
+
+ if( srcA->step != srcB->step || velx->step != vely->step )
+ CV_ERROR( CV_BadStep, "source and destination images have different step" );
+
+ IPPI_CALL( icvCalcOpticalFlowLK_8u32fR( (uchar*)srcA->data.ptr, (uchar*)srcB->data.ptr,
+ srcA->step, cvGetMatSize( srcA ), winSize,
+ velx->data.fl, vely->data.fl, velx->step ));
+
+ __END__;
+}
+
+/* End of file. */