/*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. */