diff options
author | Michael Niedermayer <michaelni@gmx.at> | 2008-08-17 15:28:12 +0000 |
---|---|---|
committer | Michael Niedermayer <michaelni@gmx.at> | 2008-08-17 15:28:12 +0000 |
commit | 7a0d00d49e587767e158f3af8f3d0d31d26faff7 (patch) | |
tree | f43f4c0b079181defc7dc32490adf512a90e2baa /libavutil | |
parent | 83e92ab6b8dbde42fd6039cb767443d9cf300404 (diff) | |
download | ffmpeg-7a0d00d49e587767e158f3af8f3d0d31d26faff7.tar.gz |
Principal component analysis
(will be cleaned up in next commits)
Originally committed as revision 14802 to svn://svn.ffmpeg.org/ffmpeg/trunk
Diffstat (limited to 'libavutil')
-rw-r--r-- | libavutil/pca.c | 231 | ||||
-rw-r--r-- | libavutil/pca.h | 31 |
2 files changed, 262 insertions, 0 deletions
diff --git a/libavutil/pca.c b/libavutil/pca.c new file mode 100644 index 0000000000..7be4404749 --- /dev/null +++ b/libavutil/pca.c @@ -0,0 +1,231 @@ +/* + * Principal component analysis + * Copyright (c) 2004 Michael Niedermayer <michaelni@gmx.at> + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + */ + +/** + * @file pca.c + * Principal component analysis + */ + +#include <math.h> +#include "avcodec.h" +#include "pca.h" + +int ff_pca_init(PCA *pca, int n){ + if(n<=0) + return -1; + + pca->n= n; + pca->count=0; + pca->covariance= av_mallocz(sizeof(double)*n*n); + pca->mean= av_mallocz(sizeof(double)*n); + + return 0; +} + +void ff_pca_free(PCA *pca){ + av_freep(&pca->covariance); + av_freep(&pca->mean); +} + +void ff_pca_add(PCA *pca, double *v){ + int i, j; + const int n= pca->n; + + for(i=0; i<n; i++){ + pca->mean[i] += v[i]; + for(j=i; j<n; j++) + pca->covariance[j + i*n] += v[i]*v[j]; + } + pca->count++; +} + +int ff_pca(PCA *pca, double *eigenvector, double *eigenvalue){ + int i, j, k, pass; + const int n= pca->n; + double z[n]; + + memset(eigenvector, 0, sizeof(double)*n*n); + + for(j=0; j<n; j++){ + pca->mean[j] /= pca->count; + eigenvector[j + j*n] = 1.0; + for(i=0; i<=j; i++){ + pca->covariance[j + i*n] /= pca->count; + pca->covariance[j + i*n] -= pca->mean[i] * pca->mean[j]; + pca->covariance[i + j*n] = pca->covariance[j + i*n]; + } + eigenvalue[j]= pca->covariance[j + j*n]; + z[j]= 0; + } + + for(pass=0; pass < 50; pass++){ + double sum=0; + + for(i=0; i<n; i++) + for(j=i+1; j<n; j++) + sum += fabs(pca->covariance[j + i*n]); + + if(sum == 0){ + for(i=0; i<n; i++){ + double maxvalue= -1; + for(j=i; j<n; j++){ + if(eigenvalue[j] > maxvalue){ + maxvalue= eigenvalue[j]; + k= j; + } + } + eigenvalue[k]= eigenvalue[i]; + eigenvalue[i]= maxvalue; + for(j=0; j<n; j++){ + double tmp= eigenvector[k + j*n]; + eigenvector[k + j*n]= eigenvector[i + j*n]; + eigenvector[i + j*n]= tmp; + } + } + return pass; + } + + for(i=0; i<n; i++){ + for(j=i+1; j<n; j++){ + double covar= pca->covariance[j + i*n]; + double t,c,s,tau,theta, h; + + if(pass < 3 && fabs(covar) < sum / (5*n*n)) //FIXME why pass < 3 + continue; + if(fabs(covar) == 0.0) //FIXME shouldnt be needed + continue; + if(pass >=3 && fabs((eigenvalue[j]+z[j])/covar) > (1LL<<32) && fabs((eigenvalue[i]+z[i])/covar) > (1LL<<32)){ + pca->covariance[j + i*n]=0.0; + continue; + } + + h= (eigenvalue[j]+z[j]) - (eigenvalue[i]+z[i]); + theta=0.5*h/covar; + t=1.0/(fabs(theta)+sqrt(1.0+theta*theta)); + if(theta < 0.0) t = -t; + + c=1.0/sqrt(1+t*t); + s=t*c; + tau=s/(1.0+c); + z[i] -= t*covar; + z[j] += t*covar; + +#define ROTATE(a,i,j,k,l)\ + double g=a[j + i*n];\ + double h=a[l + k*n];\ + a[j + i*n]=g-s*(h+g*tau);\ + a[l + k*n]=h+s*(g-h*tau); + for(k=0; k<n; k++) { + if(k!=i && k!=j){ + ROTATE(pca->covariance,FFMIN(k,i),FFMAX(k,i),FFMIN(k,j),FFMAX(k,j)) + } + ROTATE(eigenvector,k,i,k,j) + } + pca->covariance[j + i*n]=0.0; + } + } + for (i=0; i<n; i++) { + eigenvalue[i] += z[i]; + z[i]=0.0; + } + } + + return -1; +} + +#if 1 + +#undef printf +#include <stdio.h> +#include <stdlib.h> + +int main(){ + PCA pca; + int i, j, k; +#define LEN 8 + double eigenvector[LEN*LEN]; + double eigenvalue[LEN]; + + ff_pca_init(&pca, LEN); + + for(i=0; i<9000000; i++){ + double v[2*LEN+100]; + double sum=0; + int pos= random()%LEN; + int v2= (random()%101) - 50; + v[0]= (random()%101) - 50; + for(j=1; j<8; j++){ + if(j<=pos) v[j]= v[0]; + else v[j]= v2; + sum += v[j]; + } +/* for(j=0; j<LEN; j++){ + v[j] -= v[pos]; + }*/ +// sum += random()%10; +/* for(j=0; j<LEN; j++){ + v[j] -= sum/LEN; + }*/ +// lbt1(v+100,v+100,LEN); + ff_pca_add(&pca, v); + } + + + ff_pca(&pca, eigenvector, eigenvalue); + for(i=0; i<LEN; i++){ + pca.count= 1; + pca.mean[i]= 0; + +// (0.5^|x|)^2 = 0.5^2|x| = 0.25^|x| + + +// pca.covariance[i + i*LEN]= pow(0.5, fabs + for(j=i; j<LEN; j++){ + printf("%f ", pca.covariance[i + j*LEN]); + } + printf("\n"); + } + +#if 1 + for(i=0; i<LEN; i++){ + double v[LEN]; + double error=0; + memset(v, 0, sizeof(v)); + for(j=0; j<LEN; j++){ + for(k=0; k<LEN; k++){ + v[j] += pca.covariance[FFMIN(k,j) + FFMAX(k,j)*LEN] * eigenvector[i + k*LEN]; + } + v[j] /= eigenvalue[i]; + error += fabs(v[j] - eigenvector[i + j*LEN]); + } + printf("%f ", error); + } + printf("\n"); +#endif + for(i=0; i<LEN; i++){ + for(j=0; j<LEN; j++){ + printf("%9.6f ", eigenvector[i + j*LEN]); + } + printf(" %9.1f %f\n", eigenvalue[i], eigenvalue[i]/eigenvalue[0]); + } + + return 0; +} +#endif diff --git a/libavutil/pca.h b/libavutil/pca.h new file mode 100644 index 0000000000..de729840a4 --- /dev/null +++ b/libavutil/pca.h @@ -0,0 +1,31 @@ +/* + * Principal component analysis + * Copyright (c) 2004 Michael Niedermayer <michaelni@gmx.at> + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA + * + */ + +/** + * @file pca.h + * Principal component analysis + */ + +typedef struct PCA{ + int count; + int n; + double *covariance; + double *mean; +}PCA; |