lk算法
‘壹’ cvcalcopticalflowpyrlk在opencv哪个库里面
void cvCalcOpticalFlowLK( const CvArr* prev, const CvArr* curr, CvSize win_size, CvArr* velx, CvArr* vely );
void cvCalcOpticalFlowPyrLK( const CvArr* prev, const CvArr* curr, CvArr* prev_pyr, CvArr* curr_pyr,
const CvPoint2D32f* prev_features, CvPoint2D32f* curr_features,
int count, CvSize win_size, int level, char* status,
float* track_error, CvTermCriteria criteria, int flags );
对比这两个函数，前者cvCalcOpticalFlowLK(参数中包含光流速度（稠密的光流场） CvArr* velx, CvArr* vely ，然而
cvCalcOpticalFlowPyrLK的参数中确实两个特征点数组CvPoint2D32f* prev_features, CvPoint2D32f* curr_features。
对于cvCalcOpticalFlowLK函数的原理，《learning opencv》中介绍的比较清楚，也可以参考http://www.360doc.com/content/11/0210/17/5367933_91913320.shtml这篇博文。
cvCalcOpticalFlowPyrLK函数给人的感觉更像块匹配，用归一化相关求出特征点在下一帧的位移，这好像和光流机Lk算法关系不大。查阅了相关文献，思考 cvCalcOpticalFlowPyrLK的原理，确实和块匹配类似，只不过没有空归一化相关的方法，用的偏导的方法。由偏导的方法也就和LK算法及光流挂上了钩。
金字塔LK算法（cvCalcOpticalFlowPyrLK）的两个特点，一、金字塔原理；二、偏导方法求解位移。
‘贰’ 实现改进后的顺序查找
你看一下对你有没有帮助啊！ // search.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "LinkTable.h"
#define MAX_KEY 500
//------------------------------数组实现部分----------------------------------
/**//*
无序数组顺序查找算法函数nsq_Order_Search<用数组实现>
参数描述：
int array[] :被查找数组
int n :被查找数组元素个数
int key :被查找的关键值
返回值:
如果没有找到: nsq_Order_Search = -1
否则: nsq_Order_Search = key数组下标
*/
int nsq_Order_Search(int array[],int n,int key)
...{
int i;
array[n] = key;
/**//*for循环后面的分号必不可少*/
for(i=0;key!=array[i];i++);
return(i<n?i:-1);
}
/**//*
有序数组顺序查找算法函数sq_Order_Search<用数组实现>
参数描述：
int array[] :被查找数组
int n :被查找数组元素个数
int key :被查找的关键值
返回值:
如果没有找到: sq_Order_Search = -1
否则: sq_Order_Search = key数组下标
*/
int sq_Order_Search(int array[],int n,int key)
...{
int i;
array[n] = MAX_KEY;
/**//*for循环后面的分号必不可少*/
for(i=0;key>array[i];i++);
if(i<n && array[i] == key)
return(i);
else
return(-1);
}
/**//*
有序数组二分查找算法函数sq_Dichotomy_Search0<用数组实现>
参数描述：
int array[] :被查找数组
int n :被查找数组元素个数
int key :被查找的关键值
返回值:
如果没有找到: sq_Dichotomy_Search0 = -1
否则: sq_Dichotomy_Search0 = key数组下标
*/
int sq_Dichotomy_Search0(int array[],int n,int key)
...{
int low,high,mid;
low = 0;
high = n - 1;
while(low<=high)
...{
mid = (high+low)/2;
if(array[mid] == key)
return(mid);
/**//*key>array[mid] 表明要求查找的值在[mid+1,high]*/
/**//*否则,在[low,mid-1]*/
if(key > array[mid])
low = mid + 1;
else
high = mid - 1;
}
return(-1);
}
/**//*
有序数组插值查找算法函数sq_Dichotomy_Search1<用数组实现>
(插值查找算法是二分查找算法的改进)
参数描述：
int array[] :被查找数组
int n :被查找数组元素个数
int key :被查找的关键值
返回值:
如果没有找到: sq_Dichotomy_Search1 = -1
否则: sq_Dichotomy_Search1 = key数组下标
*/
int sq_Dichotomy_Search1(int array[],int n,int key)
...{
int low,high, //二分数组的上,下标
pos; //查找码的大致(估算)位置
low = 0;
high = n-1;
while(low <= high)
...{
pos = (key-array[low])/(array[high]-array[low])*(high-low)+low;
/**//*找到关键值,中途退出*/
if(key == array[pos])
return(pos);
if(key > array[pos])
low = pos + 1;
else
high = pos - 1;
}
/**//*没有找到,返回-1*/
return(-1);
}
//------------------------------数组实现部分----------------------------------
//------------------------------链表实现部分----------------------------------
/**//*
无序链表顺序查找算法函数nlk_Order_Serach<用链表实现>
[查找思想:遍历链表的所有节点]
参数描述：
Node *head :被查找链表的首指针
int key :被查找的关键值
返回值:
如果没有找到: nlk_Order_Serach = NULL
否则: nlk_Order_Serach = 键值为key的节点的指针
*/
Node *nlk_Order_Serach(Node *head,int key)
...{
for(;head!=NULL && head->data != key;head = head->link);
return(head);
}
/**//*
有序链表顺序查找算法函数lk_Order_Serach<用链表实现>
[查找思想:依次遍历链表的节点,发现节点不在key的范围时提前结束查找]
参数描述：
Node *head :被查找链表的首指针
int key :被查找的关键值
返回值:
如果没有找到: lk_Order_Serach = NULL
否则: lk_Order_Serach = 键值为key的节点的指针
*/
Node *lk_Order_Search(Node *head,int key)
...{
for(;head!=NULL && head->data < key;head=head->link);
/**//*当遍历指针为NULL或没有找到键值为key的节点,返回NULL(表明没有找到)*/
/**//*否则,返回head(表明已经找到)*/
return(head==NULL || head->data != key ? NULL : head);
}
/**//*
有序链表动态查找算法函数lk_Dynamic_Search<用链表实现>
[查找思想:依次遍历链表的节点,发现节点不在key的范围时提前结束查找]
参数描述：
Node *head: 被查找链表的首指针
Node **p; 键值为key的节点的前驱指针(回传参数)
Node **q: 键值为key的节点指针(回传参数)
int key : 被查找的关键值
注意:
当 *p == NULL 且 *q != NULL,链表的首节点键值为key
当 *p != NULL 且 *q != NULL,链表的中间(非首,尾)节点键值为key
当 *p != NULL 且 *q == NULL,链表的尾节点键值为key
当 *p == NULL 且 *q == NULL,链表是空链表
*/
void lk_Dynamic_Search(Node *head,Node **p,Node **q,int key)
...{
Node *pre,*cur;
pre = NULL;
cur = head;
for(;cur != NULL && cur->data < key;pre = cur,cur = cur->link)
*p = pre;
*q = cur;
}
/**//*
有序链表动态插入算法函数lk_Dynamic_Insert<用链表实现>
参数描述：
Node *head: 被插入链表的首指针
int key : 被插入的关键值
返回值:
lk_Dynamic_Search = 插入键值为key的节点后的链表首指针
*/
Node *lk_Dynamic_Insert(Node *head,int key)
...{
Node
*x, //插入节点的前驱节点
*y, //插入节点的后续节点
*p; //插入的节点
p = (Node *)malloc(sizeof(Node));
p->data = key;
p->link = NULL;
lk_Dynamic_Search(head,&x,&y,key);
if(x==NULL)
...{
p->link = x;
head = p;
}
else
...{
p->link = x->link;
x->link = p;
}
ListLinkTable(head,"插入节点");
return(head);
}
/**//*
有序链表动态删除算法函数lk_Dynamic_Delete<用链表实现>
参数描述：
Node *head: 被删除链表的首指针
int key : 被删除的关键值
返回值:
lk_Dynamic_Delete = 删除键值为key的节点后的链表首指针
*/
Node *lk_Dynamic_Delete(Node *head,int key)
...{
Node *x, //删除节点的前驱节点
*y; //删除的节点
lk_Dynamic_Search(head,&x,&y,key);
if(x==NULL)
/**//*因为x=NLLL时,y指向首指针*/
head = y->link;
else
x->link = y->link;
free(y);
ListLinkTable(head,"删除节点");
return(head);
}
//------------------------------链表实现部分----------------------------------
int main(int argc, char* argv[])
...{
Node *head;
//Node *p,*x,*y;
int KEY;
int count,i;
//int result;
KEY = 11;
//PrintArrayValue(TestArray2,DEFAULT_ARRAY_SIZE,"原始");
//result = sq_Dichotomy_Search1(TestArray2,DEFAULT_ARRAY_SIZE,KEY);
//printf("查找结果是：数组[%d] = %d ",result,TestArray2[result]);
head = CreateLinkTable(DEFAULT_ARRAY_SIZE,TestArray2);
ListLinkTable(head,"原始");
/**//*
p = lk_Order_Search(head,KEY);
if(p==NULL)
printf(" 查找结果是：指定链表中没有[数据域 = %d]的节点! ",KEY);
else
printf(" 查找结果是：节点.Data = %d 节点.Link = %d 节点.Addr = %d ",p->data,p->link,p);
*/
printf("输入插入节点的个数： ");
scanf("%d",&count);
for(i=0;i<count;i++)
...{
printf("输入插入节点的数据域： ");
scanf("%d",&KEY);
lk_Dynamic_Insert(head,KEY);
}
do
...{
printf("输入删除节点的数据域： ");
scanf("%d",&KEY);
lk_Dynamic_Delete(head,KEY);
}while(head!=NULL);
printf(" 应用程序正在运行...... ");
return 0;
}
‘叁’ 数据挖掘中的apriori算法的具体步骤是什么
算法：Apriori
输入：D - 事务数据库；min_sup - 最小支持度计数阈值
输出：L - D中的频繁项集
方法：
L1=find_frequent_1-itemsets(D); // 找出所有频繁1项集
For(k=2;Lk-1!=null;k++){
Ck=apriori_gen(Lk-1); // 产生候选，并剪枝
For each 事务t in D{ // 扫描D进行候选计数
Ct =subset(Ck,t); // 得到t的子集
For each 候选c 属于 Ct
c.count++;
}
Lk={c属于Ck | c.count>=min_sup}
}
Return L=所有的频繁集；
Procere apriori_gen(Lk-1:frequent(k-1)-itemsets)
For each项集l1属于Lk-1
For each项集 l2属于Lk-1
If((l1[1]=l2[1])&&( l1[2]=l2[2])&&……..
&& (l1[k-2]=l2[k-2])&&(l1[k-1]<l2[k-1])) then{
c=l1连接l2 //连接步：产生候选
if has_infrequent_subset(c,Lk-1) then
delete c; //剪枝步：删除非频繁候选
else add c to Ck;
}
Return Ck;
Procere has_infrequent_sub(c:candidate k-itemset; Lk-1:frequent(k-1)-itemsets)
For each(k-1)-subset s of c
If s不属于Lk-1 then
Return true;
Return false;
‘肆’ 急求算法！！
晕倒，全部分数只有20分，看在你的诚意，给你写第一个吧。
第一题如果直接举证相乘是三次的，比较是二次的，综合起来是三次，不满足你的要求。
但是我们换一种思路，利用随机算法，一个1*n的矩阵乘以一个n*n的矩阵是一个1*n的矩阵，乘法次数是二次的，因此如果把等式两边同时乘以一个1*n的矩阵两边还是相等的，但是复杂度只有n*n。
那个1*n矩阵怎么得到呢？随机就可以，两次左右的随机就能保证正确性了，下面是代码，格式是先读入一个n，然后读入两个n*n个矩阵（就是2*n*n个整数），如果AB=C输出YES，否则输出NO，采用了两次随机判定，判误率很高，但是没算过，随机种子是我随手打的，取得好一点可能判误率更高。
#include<stdio.h>
#include<stdlib.h>
int i,j,n,a[500][500],b[500][500],c[500][500];
bool can;
void oper()
{
int i,j,temp[500],mid[500],s,tempb[500];
for (i=0;i<n;i++) mid[i]=rand()%100+1;
for (i=0;i<n;i++)
{
temp[i]=0;
for (j=0;j<n;j++)
temp[i]+=mid[j]*a[j][i];
}
for (i=0;i<n;i++)
{
tempb[i]=0;
for (j=0;j<n;j++)
tempb[i]+=temp[j]*b[j][i];
}
for (i=0;i<n;i++)
{
s=0;
for (j=0;j<n;j++)
s+=mid[j]*c[j][i];
if (s!=tempb[i])
{
can=false;
return;
}
}
}
int main()
{
srand(756);
scanf("%d",&n);
for (i=0;i<n;i++)
for (j=0;j<n;j++)
scanf("%d",&a[i][j]);
for (i=0;i<n;i++)
for (j=0;j<n;j++)
scanf("%d",&b[i][j]);
for (i=0;i<n;i++)
for (j=0;j<n;j++)
scanf("%d",&c[i][j]);
can=true;
for (i=0;i<2;i++)
{
oper();
if (!can) break;
}
if (can) printf("YES\n");
else printf("NO\n");
return 0;
}
‘伍’ 利用Apriori算法产生频繁项集，（min sup=0.6），给出具体计算过程
Apriori算法是一种发现频繁项集的基本算法。算法使用频繁项集性质的先验知识。Apriori算法使用一种称为逐层搜索的迭代方法，其中K项集用于探索(k+1)项集。首先，通过扫描数据库，累计每个项的计数，并收集满足最小支持度的项，找出频繁1项集的集合。该集合记为L1.然后，使用L1找出频繁2项集的集合L2，使用L2找到L3，如此下去，直到不能再找到频繁k项集。Apriori算法的主要步骤如下：(1)扫描事务数据库中的每个事务，产生候选1．项集的集合Cl；(2)根据最小支持度min_sup，由候选l-项集的集合Cl产生频繁1一项集的集合Ll；(3)对k=l；(4)由Lk执行连接和剪枝操作，产生候选(k+1)．项集的集合Ck+l-(5)根据最小支持度min_sup，由候选(k+1)一项集的集合Ck+l产生频繁(k+1)-项集的集合Lk+1．(6)若L?≠①，则k．k+1，跳往步骤(4)；否则，跳往步骤(7)；(7)根据最小置信度min_conf,由频繁项集产生强关联规则，结束。
‘陆’ 编写顺序查找算法的程序
查找算法集：顺序查找、二分查找、插值查找、动态查找(数组实现、链表实现)
// search.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "LinkTable.h"
#define MAX_KEY 500
//------------------------------数组实现部分----------------------------------
/**//*
无序数组顺序查找算法函数nsq_Order_Search<用数组实现>
参数描述：
int array[] :被查找数组
int n :被查找数组元素个数
int key :被查找的关键值
返回值:
如果没有找到: nsq_Order_Search = -1
否则: nsq_Order_Search = key数组下标
*/
int nsq_Order_Search(int array[],int n,int key)
...{
int i;
array[n] = key;
/**//*for循环后面的分号必不可少*/
for(i=0;key!=array[i];i++);
return(i<n?i:-1);
}
/**//*
有序数组顺序查找算法函数sq_Order_Search<用数组实现>
参数描述：
int array[] :被查找数组
int n :被查找数组元素个数
int key :被查找的关键值
返回值:
如果没有找到: sq_Order_Search = -1
否则: sq_Order_Search = key数组下标
*/
int sq_Order_Search(int array[],int n,int key)
...{
int i;
array[n] = MAX_KEY;
/**//*for循环后面的分号必不可少*/
for(i=0;key>array[i];i++);
if(i<n && array[i] == key)
return(i);
else
return(-1);
}
/**//*
有序数组二分查找算法函数sq_Dichotomy_Search0<用数组实现>
参数描述：
int array[] :被查找数组
int n :被查找数组元素个数
int key :被查找的关键值
返回值:
如果没有找到: sq_Dichotomy_Search0 = -1
否则: sq_Dichotomy_Search0 = key数组下标
*/
int sq_Dichotomy_Search0(int array[],int n,int key)
...{
int low,high,mid;
low = 0;
high = n - 1;
while(low<=high)
...{
mid = (high+low)/2;
if(array[mid] == key)
return(mid);
/**//*key>array[mid] 表明要求查找的值在[mid+1,high]*/
/**//*否则,在[low,mid-1]*/
if(key > array[mid])
low = mid + 1;
else
high = mid - 1;
}
return(-1);
}
/**//*
有序数组插值查找算法函数sq_Dichotomy_Search1<用数组实现>
(插值查找算法是二分查找算法的改进)
参数描述：
int array[] :被查找数组
int n :被查找数组元素个数
int key :被查找的关键值
返回值:
如果没有找到: sq_Dichotomy_Search1 = -1
否则: sq_Dichotomy_Search1 = key数组下标
*/
int sq_Dichotomy_Search1(int array[],int n,int key)
...{
int low,high, //二分数组的上,下标
pos; //查找码的大致(估算)位置
low = 0;
high = n-1;
while(low <= high)
...{
pos = (key-array[low])/(array[high]-array[low])*(high-low)+low;
/**//*找到关键值,中途退出*/
if(key == array[pos])
return(pos);
if(key > array[pos])
low = pos + 1;
else
high = pos - 1;
}
/**//*没有找到,返回-1*/
return(-1);
}
//------------------------------数组实现部分----------------------------------
//------------------------------链表实现部分----------------------------------
/**//*
无序链表顺序查找算法函数nlk_Order_Serach<用链表实现>
[查找思想:遍历链表的所有节点]
参数描述：
Node *head :被查找链表的首指针
int key :被查找的关键值
返回值:
如果没有找到: nlk_Order_Serach = NULL
否则: nlk_Order_Serach = 键值为key的节点的指针
*/
Node *nlk_Order_Serach(Node *head,int key)
...{
for(;head!=NULL && head->data != key;head = head->link);
return(head);
}
/**//*
有序链表顺序查找算法函数lk_Order_Serach<用链表实现>
[查找思想:依次遍历链表的节点,发现节点不在key的范围时提前结束查找]
参数描述：
Node *head :被查找链表的首指针
int key :被查找的关键值
返回值:
如果没有找到: lk_Order_Serach = NULL
否则: lk_Order_Serach = 键值为key的节点的指针
*/
Node *lk_Order_Search(Node *head,int key)
...{
for(;head!=NULL && head->data < key;head=head->link);
/**//*当遍历指针为NULL或没有找到键值为key的节点,返回NULL(表明没有找到)*/
/**//*否则,返回head(表明已经找到)*/
return(head==NULL || head->data != key ? NULL : head);
}
/**//*
有序链表动态查找算法函数lk_Dynamic_Search<用链表实现>
[查找思想:依次遍历链表的节点,发现节点不在key的范围时提前结束查找]
参数描述：
Node *head: 被查找链表的首指针
Node **p; 键值为key的节点的前驱指针(回传参数)
Node **q: 键值为key的节点指针(回传参数)
int key : 被查找的关键值
注意:
当 *p == NULL 且 *q != NULL,链表的首节点键值为key
当 *p != NULL 且 *q != NULL,链表的中间(非首,尾)节点键值为key
当 *p != NULL 且 *q == NULL,链表的尾节点键值为key
当 *p == NULL 且 *q == NULL,链表是空链表
*/
void lk_Dynamic_Search(Node *head,Node **p,Node **q,int key)
...{
Node *pre,*cur;
pre = NULL;
cur = head;
for(;cur != NULL && cur->data < key;pre = cur,cur = cur->link)
*p = pre;
*q = cur;
}
/**//*
有序链表动态插入算法函数lk_Dynamic_Insert<用链表实现>
参数描述：
Node *head: 被插入链表的首指针
int key : 被插入的关键值
返回值:
lk_Dynamic_Search = 插入键值为key的节点后的链表首指针
*/
Node *lk_Dynamic_Insert(Node *head,int key)
...{
Node
*x, //插入节点的前驱节点
*y, //插入节点的后续节点
*p; //插入的节点
p = (Node *)malloc(sizeof(Node));
p->data = key;
p->link = NULL;
lk_Dynamic_Search(head,&x,&y,key);
if(x==NULL)
...{
p->link = x;
head = p;
}
else
...{
p->link = x->link;
x->link = p;
}
ListLinkTable(head,"插入节点");
return(head);
}
/**//*
有序链表动态删除算法函数lk_Dynamic_Delete<用链表实现>
参数描述：
Node *head: 被删除链表的首指针
int key : 被删除的关键值
返回值:
lk_Dynamic_Delete = 删除键值为key的节点后的链表首指针
*/
Node *lk_Dynamic_Delete(Node *head,int key)
...{
Node *x, //删除节点的前驱节点
*y; //删除的节点
lk_Dynamic_Search(head,&x,&y,key);
if(x==NULL)
/**//*因为x=NLLL时,y指向首指针*/
head = y->link;
else
x->link = y->link;
free(y);
ListLinkTable(head,"删除节点");
return(head);
}
//------------------------------链表实现部分----------------------------------
int main(int argc, char* argv[])
...{
Node *head;
//Node *p,*x,*y;
int KEY;
int count,i;
//int result;
KEY = 11;
//PrintArrayValue(TestArray2,DEFAULT_ARRAY_SIZE,"原始");
//result = sq_Dichotomy_Search1(TestArray2,DEFAULT_ARRAY_SIZE,KEY);
//printf("查找结果是：数组[%d] = %d ",result,TestArray2[result]);
head = CreateLinkTable(DEFAULT_ARRAY_SIZE,TestArray2);
ListLinkTable(head,"原始");
/**//*
p = lk_Order_Search(head,KEY);
if(p==NULL)
printf(" 查找结果是：指定链表中没有[数据域 = %d]的节点! ",KEY);
else
printf(" 查找结果是：节点.Data = %d 节点.Link = %d 节点.Addr = %d ",p->data,p->link,p);
*/
printf("输入插入节点的个数： ");
scanf("%d",&count);
for(i=0;i<count;i++)
...{
printf("输入插入节点的数据域： ");
scanf("%d",&KEY);
lk_Dynamic_Insert(head,KEY);
}
do
...{
printf("输入删除节点的数据域： ");
scanf("%d",&KEY);
lk_Dynamic_Delete(head,KEY);
}while(head!=NULL);
printf(" 应用程序正在运行...... ");
return 0;
}
‘柒’ 如何使用opencv实现金字塔光流lk跟踪算法
#include <stdio.h>
#include <windows.h>
#include "cv.h"
#include "cxcore.h"
#include "highgui.h"
#include <opencv2\opencv.hpp>
using namespace cv;
static const double pi = 3.14159265358979323846;
inline static double square(int a)
{
return a * a;
}
/*该函数目的：给img分配内存空间，并设定format，如位深以及channel数*/
inline static void allocateOnDemand(IplImage **img, CvSize size, int depth, int channels)
{
if (*img != NULL) return;
*img = cvCreateImage(size, depth, channels);
if (*img == NULL)
{
fprintf(stderr, "Error: Couldn't allocate image. Out of memory?\n");
exit(-1);
}
}
/*主函数，原程序是读取avi视频文件，然后处理，我简单改成从摄像头直接读取数据*/
int main(int argc, char *argv[])
{
//读取摄像头
VideoCapture cap(0);
//读取视频文件
//VideoCapture cap; cap.open("optical_flow_input.avi");
if (!cap.isOpened())
{
return -1;
}
Mat frame;
/*
bool stop = false;
while (!stop)
{
cap >> frame;
// cvtColor(frame, edges, CV_RGB2GRAY);
// GaussianBlur(edges, edges, Size(7, 7), 1.5, 1.5);
// Canny(edges, edges, 0, 30, 3);
// imshow("当前视频", edges);
imshow("当前视频", frame);
if (waitKey(30) >= 0)
stop = true;
}
*/
//CvCapture *input_video = cvCaptureFromFile( "optical_flow_input.avi" );
//cv::VideoCapture cap = *(cv::VideoCapture *) userdata;
//if (input_video == NULL)
// {
// fprintf(stderr, "Error: Can't open video device.\n");
// return -1;
// }
/*先读取一帧，以便得到帧的属性，如长、宽等*/
//cvQueryFrame(input_video);
/*读取帧的属性*/
CvSize frame_size;
frame_size.height = cap.get(CV_CAP_PROP_FRAME_HEIGHT);
frame_size.width = cap.get(CV_CAP_PROP_FRAME_WIDTH);
/*********************************************************/
/*用于把结果写到文件中去,非必要
int frameW = frame_size.height; // 744 for firewire cameras
int frameH = frame_size.width; // 480 for firewire cameras
VideoWriter writer("VideoTest.avi", -1, 25.0, cvSize(frameW, frameH), true);
/*开始光流法*/
//VideoWriter writer("VideoTest.avi", CV_FOURCC('D', 'I', 'V', 'X'), 25.0, Size(640, 480), true);
while (true)
{
static IplImage *frame = NULL, *frame1 = NULL, *frame1_1C = NULL,
*frame2_1C = NULL, *eig_image = NULL, *temp_image = NULL,
*pyramid1 = NULL, *pyramid2 = NULL;
Mat framet;
/*获取第一帧*/
// cap >> framet;
cap.read(framet);
Mat edges;
//黑白抽象滤镜模式
// cvtColor(framet, edges, CV_RGB2GRAY);
// GaussianBlur(edges, edges, Size(7, 7), 1.5, 1.5);
// Canny(edges, edges, 0, 30, 3);
//转换mat格式到lpiimage格式
frame = &IplImage(framet);
if (frame == NULL)
{
fprintf(stderr, "Error: Hmm. The end came sooner than we thought.\n");
return -1;
}
/*由于opencv的光流函数处理的是8位的灰度图，所以需要创建一个同样格式的
IplImage的对象*/
allocateOnDemand(&frame1_1C, frame_size, IPL_DEPTH_8U, 1);
/* 把摄像头图像格式转换成OpenCV惯常处理的图像格式*/
cvConvertImage(frame, frame1_1C, 0);
/* 我们需要把具有全部颜色信息的原帧保存，以备最后在屏幕上显示用*/
allocateOnDemand(&frame1, frame_size, IPL_DEPTH_8U, 3);
cvConvertImage(frame, frame1, 0);
/* 获取第二帧 */
//cap >> framet;
cap.read(framet);
// cvtColor(framet, edges, CV_RGB2GRAY);
// GaussianBlur(edges, edges, Size(7, 7), 1.5, 1.5);
// Canny(edges, edges, 0, 30, 3);
frame = &IplImage(framet);
if (frame == NULL)
{
fprintf(stderr, "Error: Hmm. The end came sooner than we thought.\n");
return -1;
}
/*原理同上*/
allocateOnDemand(&frame2_1C, frame_size, IPL_DEPTH_8U, 1);
cvConvertImage(frame, frame2_1C, 0);
/*********************************************************
开始shi-Tomasi算法，该算法主要用于feature selection,即一张图中哪些是我
们感兴趣需要跟踪的点(interest point)
input:
* "frame1_1C" 输入图像.
* "eig_image" and "temp_image" 只是给该算法提供可操作的内存区域.
* 第一个".01" 规定了特征值的最小质量，因为该算法要得到好的特征点，哪就
需要一个选择的阈值
* 第二个".01" 规定了像素之间最小的距离，用于减少运算复杂度，当然也一定
程度降低了跟踪精度
* "NULL" 意味着处理整张图片，当然你也可以指定一块区域
output:
* "frame1_features" 将会包含fram1的特征值
* "number_of_features" 将在该函数中自动填充上所找到特征值的真实数目,
该值<= 400
**********************************************************/
/*开始准备该算法需要的输入*/
/* 给eig_image,temp_image分配空间*/
allocateOnDemand(&eig_image, frame_size, IPL_DEPTH_32F, 1);
allocateOnDemand(&temp_image, frame_size, IPL_DEPTH_32F, 1);
/* 定义存放frame1特征值的数组，400只是定义一个上限 */
CvPoint2D32f frame1_features[400];
int number_of_features = 400;
/*开始跑shi-tomasi函数*/
cvGoodFeaturesToTrack(frame1_1C, eig_image, temp_image,
frame1_features, &number_of_features, .01, .01, NULL);
/**********************************************************
开始金字塔Lucas Kanade光流法，该算法主要用于feature tracking,即是算出
光流，并跟踪目标。
input:
* "frame1_1C" 输入图像，即8位灰色的第一帧
* "frame2_1C" 第二帧，我们要在其上找出第一帧我们发现的特征点在第二帧
的什么位置
* "pyramid1" and "pyramid2" 是提供给该算法可操作的内存区域，计算中间
数据
* "frame1_features" 由shi-tomasi算法得到的第一帧的特征点.
* "number_of_features" 第一帧特征点的数目
* "optical_flow_termination_criteria" 该算法中迭代终止的判别，这里是
epsilon<0.3，epsilon是两帧中对应特征窗口的光度之差的平方，这个以后的文
章会讲
* "0" 这个我不知道啥意思，反正改成1就出不来光流了，就用作者原话解释把
means disable enhancements. (For example, the second array isn't
pre-initialized with guesses.)
output:
* "frame2_features" 根据第一帧的特征点，在第二帧上所找到的对应点
* "optical_flow_window" lucas-kanade光流算法的运算窗口,具体lucas-kanade
会在下一篇详述
* "5" 指示最大的金字塔层数，0表示只有一层，那就是没用金字塔算法
* "optical_flow_found_feature" 用于指示在第二帧中是否找到对应特征值，
若找到，其值为非零
* "optical_flow_feature_error" 用于存放光流误差
**********************************************************/
/*开始为pyramid lucas kanade光流算法输入做准备*/
CvPoint2D32f frame2_features[400];
/* 该数组相应位置的值为非零，如果frame1中的特征值在frame2中找到 */
char optical_flow_found_feature[400];
/* 数组第i个元素表对应点光流误差*/
float optical_flow_feature_error[400];
/*lucas-kanade光流法运算窗口,这里取3*3的窗口,可以尝试下5*5,区别就是5*5
出现aperture problem的几率较小,3*3运算量小，对于feature selection即shi-tomasi算法来说足够了*/
CvSize optical_flow_window = cvSize(5, 5);
// CvSize optical_flow_window = cvSize(5, 5);
/* 终止规则，当完成20次迭代或者当epsilon<=0.3，迭代终止，可以尝试下别的值*/
CvTermCriteria optical_flow_termination_criteria= cvTermCriteria(CV_TERMCRIT_ITER | CV_TERMCRIT_EPS, 20, .3);
/*分配工作区域*/
allocateOnDemand(&pyramid1, frame_size, IPL_DEPTH_8U, 1);
allocateOnDemand(&pyramid2, frame_size, IPL_DEPTH_8U, 1);
/*开始跑该算法*/
cvCalcOpticalFlowPyrLK(frame1_1C, frame2_1C, pyramid1, pyramid2,frame1_features, frame2_features, number_of_features,
optical_flow_window, 5, optical_flow_found_feature,optical_flow_feature_error, optical_flow_termination_criteria, 0);
/*画光流场，画图是依据两帧对应的特征值，
这个特征值就是图像上我们感兴趣的点，如边缘上的点P(x,y)*/
for (int i = 0; i< number_of_features; i++)
{
/* 如果没找到对应特征点 */
if (optical_flow_found_feature[i] == 0)
continue;
int line_thickness;
line_thickness = 1;
/* CV_RGB(red, green, blue) is the red, green, and blue components
* of the color you want, each out of 255.
*/
CvScalar line_color;
line_color = CV_RGB(255, 0, 0);
/*画箭头,因为帧间的运动很小，所以需要缩放，不然看不见箭头，缩放因子为3*/
CvPoint p, q;
p.x = (int)frame1_features[i].x;
p.y = (int)frame1_features[i].y;
q.x = (int)frame2_features[i].x;
q.y = (int)frame2_features[i].y;
double angle;
angle = atan2((double)p.y - q.y, (double)p.x - q.x);
double hypotenuse;
hypotenuse = sqrt(square(p.y - q.y) + square(p.x - q.x));
/*执行缩放*/
q.x = (int)(p.x - 5 * hypotenuse * cos(angle));
q.y = (int)(p.y - 5 * hypotenuse * sin(angle));
/*画箭头主线*/
/* "frame1"要在frame1上作画.
* "p" 线的开始点.
* "q" 线的终止点.
* "CV_AA" 反锯齿.
* "0" 没有小数位.
*/
cvLine(frame1, p, q, line_color, line_thickness, CV_AA, 0);
/* 画箭的头部*/
p.x = (int)(q.x + 9 * cos(angle + pi / 4));
p.y = (int)(q.y + 9 * sin(angle + pi / 4));
cvLine(frame1, p, q, line_color, line_thickness, CV_AA, 0);
p.x = (int)(q.x + 9 * cos(angle - pi / 4));
p.y = (int)(q.y + 9 * sin(angle - pi / 4));
cvLine(frame1, p, q, line_color, line_thickness, CV_AA, 0);
}
/*显示图像*/
/*创建一个名为optical flow的窗口，大小自动改变*/
cvNamedWindow("Optical Flow", CV_WINDOW_NORMAL);
cvFlip(frame1, NULL, 2);
cvShowImage("Optical Flow", frame1);
/*延时，要不放不了*/
cvWaitKey(33);
/*写入到文件中去*/
// cv::Mat m = cv::cvarrToMat(frame1);//转换lpimgae到mat格式
// writer << m;//opencv3.0 version writer
}
cap.release();
cvWaitKey(33);
system("pause");
}
‘捌’ 编写一个算法来交换单链表中指针P所指结点与其后继结点
void swape(linklist &head,linklist &p)
{
linlklist q=head,r=p->next;
while(q->next!=p)q=q->next;
q->next=r;
p->next=r->next;
r->next=p;
}
‘玖’ 设计一个计算表头指针为LK_h的单链式表长度（即结点个数）的算法
long getLength(Node* h) //Node 为节点类型 { Node *p=h->next; long len=0; while (p!=NULL) { p=p->next; len++; } return len; }
‘拾’ 马尔可夫链算法
// Markov.bss
// 用koodoo语言实现马尔可夫链算法
// 这也是对文件操作、散列数组的演示
// 马尔可夫链算法具体的说明请参阅《程序设计实践》
// (Brian W.Kernighan & Rob Pike着, 裘宗燕译, 机械工业出版社2000版)
// 输入文件: "month.txt" -- 《人月神话》的一段话
// 输出文件: "out1.txt"
// 深圳市蓝星际公司 2004
// [email protected]
// markov chain algorithm for 2-word prefixes
const MAXGEN = 10000;
CR = 0;
Chr(13, CR);
NONWORD = CR;
c2 = 0;
Chr(10, c2);
CR = CR + c2;
w1 = NONWORD;
w2 = NONWORD;
LK = "";
Chr(15, LK);
inFile = "month.txt";
outFile = "out1.txt";
// 只读方式打开输入文件
hd = -1;
FileOpen(inFile, "rt", hd);
if( hd<0 )
{
return(0);
}
statetab = 0;
nsuffix = 0;
s = "";
while(true)
{
FileReadLine(hd, s); // 读一行
if( s=="" )
{
// 到了文件结束
break;
}
m = 0;
AnlyStr(s, " ", m); // 将一行的内容分解为单词, 存放在数组m
num = _retVal; // 单词数
for(i=0; i<num; i++)
{
k1 = w1 + LK + w2; // 将w1, w2连接起来模拟2维数组
v = nsuffix[k1];
t = 0;
Type(v, t);
if( t==0 ) // 表示该下标首次使用
{
nsuffix[k1] = 0;
}
nsuffix[k1] = 1 + nsuffix[k1];
k2 = k1 + LK + nsuffix[k1]; // 模拟3维数组
statetab[k2] = m[i];
w1 = w2;
w2 = m[i];
}
}
FileClose(hd);
// 创建输出文件
hd = -1;
FileOpen(outFile, "w+t", hd);
if( hd<0 )
{
return(0);
}
k1 = w1 + LK + w2;
v = nsuffix[k1];
t = 0;
Type(v, t);
if( t==0 )
{
nsuffix[k1] = 0;
}
nsuffix[k1] = nsuffix[k1] + 1;
k2 = k1 + LK + nsuffix[k1];
statetab[k2] = NONWORD;
w1 = NONWORD;
w2 = NONWORD;
for(i=0; i<MAXGEN; i++)
{
r = 0;
Rand(r);
k1 = w1 + LK + w2;
r = r % nsuffix[k1] + 1;
k2 = k1 + LK + r;
p = statetab[k2];
if( p== NONWORD )
{
break;
}
FileWrite(hd, p);
FileWrite(hd, " ");
w1 = w2;
w2 = p;
}
FileCloseAll();
return(0);