学步园

pq_new.c

/*

实现productquantization

从一个学习数据集中构建ANN(aproximatenearest neighbor) pq codes.

使用pq*p=pq_new(int nsq,CvMat *v);

nsq:子向量的个数，论文中的m.

v:用于学习的数据集，指向一个CvMat的指针，每一行是一个训练数据。

*/

返回的数据结构

typedef struct pq{
	int nsq;//子向量的个数
	int ks;//子向量的聚类中心个数
	int ds;//子向量的维数 ds=d/nsq;
	CvMat **centroids;//子向量聚类中心的坐标,nsq个CvMat指针，centroid[i]是第i个子向量的中心，ksxds维，表示第i个子向量有ks个中心，中心的坐标是ds维。
	CvMat **assigns;//分配向量，nsq个CvMat指针，assign[i]是第i个子向量的分配id，nx1维，分别表示n个子向量分配到哪一个中心。
}pq;

具体实现

pq* pq_new(int nsq,CvMat * v){
	int n=v->rows;
	int d=v->cols;
	int ds=d/nsq;//dimension of subvectors to quantize
	int nsqbits=1;//default 8
	int ks=pow(2,nsqbits);
	int q;
	int i,j;
	pq *p=(pq*)malloc(sizeof(pq));
	p->nsq=nsq;
	p->ds=ds;
	p->ks=ks;
	p->centroids=(CvMat**)malloc(sizeof(CvMat*)*nsq);
	for(q=0;q<nsq;q++)p->centroids[q]=cvCreateMat(ks,ds,CV_32FC1);
	//assert(res!=NULL);
	CvMat **centers=(CvMat **)malloc(sizeof(CvMat *)*nsq);
	for(q=0;q<nsq;q++)
		centers[q]=cvCreateMat(n,1,CV_32S);
	CvMat *vs=cvCreateMat(n,ds,CV_32FC1);
	//p->centroids=res;assert((p->centroids)[0]!=NULL);
	p->assigns=centers;
	for(q=0;q<nsq;q++){
		//copy the sub vector
		for(i=0;i<n;i++){
			for(j=0;j<ds;j++){
				vs->data.fl[i*vs->cols+j]=v->data.fl[i*v->cols+q*ds+j];
			}
		}
		//vs:n*ds;ks,centers
		//printf("n rows:%d,%d,%d\n",vs->rows,centers[q]->cols,centers[q]->rows);
		cvKMeans2(vs,ks,centers[q],cvTermCriteria(CV_TERMCRIT_ITER,10,0.1),1,0,0,p->centroids[q],0);
	}
	//cvReleaseMat(&vs);
	return p;
}
//测试输出
void pq_print(pq* p){
	printf("nsq:%d;ks:%d;ds:%d\n",p->nsq,p->ks,p->ds);
	printf("assign\n");
	int i,j,k;
	for(i=0;i<p->nsq;i++){
		printf("subvector:%d\n",i);
		for(j=0;j<p->assigns[i]->rows;j++){
			printf("row[%d]=%d,",j,p->assigns[i]->data.i[j]);
		}
		printf("\n");
	}
	printf("\n");
	printf("centers:\n");

	for(i=0;i<p->nsq;i++){
		printf("subvector:%d\n",i);
		for(j=0;j<p->ks;j++){
			printf("centers:%d\n",j);
			for(k=0;k<p->ds;k++)
			{
				printf("dim[%d]=%f,",k,p->centroids[i]->data.fl[j*(p->centroids[i]->cols)+k]);
			}
			printf("\n");
		}
	}
	printf("\n");
}

测试文件

#include"pq_new.h"
int main(){
	float arr[]={1,2,5,6,1.2,2.2,5.3,6.1,0.9,1.8,4.9,6.1};
	CvMat v=cvMat(3,4,CV_32FC1,arr);//v是一个3x4的矩阵
	int nsq=2;//我们设定子向量的个数为2
	pq* p=pq_new(nsq,&v);
	pq_print(p);
}

结果显示：

nsq:2;ks:2;ds:2
assign
subvector:0
row[0]=0,row[1]=1,row[2]=0,
subvector:1
row[0]=1,row[1]=0,row[2]=1,

centers:
subvector:0
centers:0
dim[0]=0.950000,dim[1]=1.900000,
centers:1
dim[0]=1.200000,dim[1]=2.200000,
subvector:1
centers:0
dim[0]=5.300000,dim[1]=6.100000,
centers:1
dim[0]=4.950000,dim[1]=6.050000,

我们的测试数据：

v=

{

  1,  2,  5,  6,
1.2,2.2,5.3,6.1,
0.9,1.8,4.9,6.1

}

v按列被分成了两组子向量。第一组子向量的有两个聚类中心，一(1.2,2.2)和二（0.95，1.9），v的第一祖的第一个向量（1，2）分配到了第一个聚类中心，第二个向量（1.2，2.2）单独分配到第二个聚类中心，第三个向量（0.9，1.8）被分配到第一个聚类中心，依次类推。