pca.c 6.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248
  1. /*
  2. * principal component analysis (PCA)
  3. * Copyright (c) 2004 Michael Niedermayer <michaelni@gmx.at>
  4. *
  5. * This file is part of FFmpeg.
  6. *
  7. * FFmpeg is free software; you can redistribute it and/or
  8. * modify it under the terms of the GNU Lesser General Public
  9. * License as published by the Free Software Foundation; either
  10. * version 2.1 of the License, or (at your option) any later version.
  11. *
  12. * FFmpeg is distributed in the hope that it will be useful,
  13. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  15. * Lesser General Public License for more details.
  16. *
  17. * You should have received a copy of the GNU Lesser General Public
  18. * License along with FFmpeg; if not, write to the Free Software
  19. * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  20. */
  21. /**
  22. * @file
  23. * principal component analysis (PCA)
  24. */
  25. #include "common.h"
  26. #include "pca.h"
  27. typedef struct PCA{
  28. int count;
  29. int n;
  30. double *covariance;
  31. double *mean;
  32. double *z;
  33. }PCA;
  34. PCA *ff_pca_init(int n){
  35. PCA *pca;
  36. if(n<=0)
  37. return NULL;
  38. pca= av_mallocz(sizeof(*pca));
  39. pca->n= n;
  40. pca->z = av_malloc_array(n, sizeof(*pca->z));
  41. pca->count=0;
  42. pca->covariance= av_calloc(n*n, sizeof(double));
  43. pca->mean= av_calloc(n, sizeof(double));
  44. return pca;
  45. }
  46. void ff_pca_free(PCA *pca){
  47. av_freep(&pca->covariance);
  48. av_freep(&pca->mean);
  49. av_freep(&pca->z);
  50. av_free(pca);
  51. }
  52. void ff_pca_add(PCA *pca, double *v){
  53. int i, j;
  54. const int n= pca->n;
  55. for(i=0; i<n; i++){
  56. pca->mean[i] += v[i];
  57. for(j=i; j<n; j++)
  58. pca->covariance[j + i*n] += v[i]*v[j];
  59. }
  60. pca->count++;
  61. }
  62. int ff_pca(PCA *pca, double *eigenvector, double *eigenvalue){
  63. int i, j, pass;
  64. int k=0;
  65. const int n= pca->n;
  66. double *z = pca->z;
  67. memset(eigenvector, 0, sizeof(double)*n*n);
  68. for(j=0; j<n; j++){
  69. pca->mean[j] /= pca->count;
  70. eigenvector[j + j*n] = 1.0;
  71. for(i=0; i<=j; i++){
  72. pca->covariance[j + i*n] /= pca->count;
  73. pca->covariance[j + i*n] -= pca->mean[i] * pca->mean[j];
  74. pca->covariance[i + j*n] = pca->covariance[j + i*n];
  75. }
  76. eigenvalue[j]= pca->covariance[j + j*n];
  77. z[j]= 0;
  78. }
  79. for(pass=0; pass < 50; pass++){
  80. double sum=0;
  81. for(i=0; i<n; i++)
  82. for(j=i+1; j<n; j++)
  83. sum += fabs(pca->covariance[j + i*n]);
  84. if(sum == 0){
  85. for(i=0; i<n; i++){
  86. double maxvalue= -1;
  87. for(j=i; j<n; j++){
  88. if(eigenvalue[j] > maxvalue){
  89. maxvalue= eigenvalue[j];
  90. k= j;
  91. }
  92. }
  93. eigenvalue[k]= eigenvalue[i];
  94. eigenvalue[i]= maxvalue;
  95. for(j=0; j<n; j++){
  96. double tmp= eigenvector[k + j*n];
  97. eigenvector[k + j*n]= eigenvector[i + j*n];
  98. eigenvector[i + j*n]= tmp;
  99. }
  100. }
  101. return pass;
  102. }
  103. for(i=0; i<n; i++){
  104. for(j=i+1; j<n; j++){
  105. double covar= pca->covariance[j + i*n];
  106. double t,c,s,tau,theta, h;
  107. if(pass < 3 && fabs(covar) < sum / (5*n*n)) //FIXME why pass < 3
  108. continue;
  109. if(fabs(covar) == 0.0) //FIXME should not be needed
  110. continue;
  111. if(pass >=3 && fabs((eigenvalue[j]+z[j])/covar) > (1LL<<32) && fabs((eigenvalue[i]+z[i])/covar) > (1LL<<32)){
  112. pca->covariance[j + i*n]=0.0;
  113. continue;
  114. }
  115. h= (eigenvalue[j]+z[j]) - (eigenvalue[i]+z[i]);
  116. theta=0.5*h/covar;
  117. t=1.0/(fabs(theta)+sqrt(1.0+theta*theta));
  118. if(theta < 0.0) t = -t;
  119. c=1.0/sqrt(1+t*t);
  120. s=t*c;
  121. tau=s/(1.0+c);
  122. z[i] -= t*covar;
  123. z[j] += t*covar;
  124. #define ROTATE(a,i,j,k,l) {\
  125. double g=a[j + i*n];\
  126. double h=a[l + k*n];\
  127. a[j + i*n]=g-s*(h+g*tau);\
  128. a[l + k*n]=h+s*(g-h*tau); }
  129. for(k=0; k<n; k++) {
  130. if(k!=i && k!=j){
  131. ROTATE(pca->covariance,FFMIN(k,i),FFMAX(k,i),FFMIN(k,j),FFMAX(k,j))
  132. }
  133. ROTATE(eigenvector,k,i,k,j)
  134. }
  135. pca->covariance[j + i*n]=0.0;
  136. }
  137. }
  138. for (i=0; i<n; i++) {
  139. eigenvalue[i] += z[i];
  140. z[i]=0.0;
  141. }
  142. }
  143. return -1;
  144. }
  145. #ifdef TEST
  146. #undef printf
  147. #include <stdio.h>
  148. #include <stdlib.h>
  149. #include "lfg.h"
  150. int main(void){
  151. PCA *pca;
  152. int i, j, k;
  153. #define LEN 8
  154. double eigenvector[LEN*LEN];
  155. double eigenvalue[LEN];
  156. AVLFG prng;
  157. av_lfg_init(&prng, 1);
  158. pca= ff_pca_init(LEN);
  159. for(i=0; i<9000000; i++){
  160. double v[2*LEN+100];
  161. double sum=0;
  162. int pos = av_lfg_get(&prng) % LEN;
  163. int v2 = av_lfg_get(&prng) % 101 - 50;
  164. v[0] = av_lfg_get(&prng) % 101 - 50;
  165. for(j=1; j<8; j++){
  166. if(j<=pos) v[j]= v[0];
  167. else v[j]= v2;
  168. sum += v[j];
  169. }
  170. /* for(j=0; j<LEN; j++){
  171. v[j] -= v[pos];
  172. }*/
  173. // sum += av_lfg_get(&prng) % 10;
  174. /* for(j=0; j<LEN; j++){
  175. v[j] -= sum/LEN;
  176. }*/
  177. // lbt1(v+100,v+100,LEN);
  178. ff_pca_add(pca, v);
  179. }
  180. ff_pca(pca, eigenvector, eigenvalue);
  181. for(i=0; i<LEN; i++){
  182. pca->count= 1;
  183. pca->mean[i]= 0;
  184. // (0.5^|x|)^2 = 0.5^2|x| = 0.25^|x|
  185. // pca.covariance[i + i*LEN]= pow(0.5, fabs
  186. for(j=i; j<LEN; j++){
  187. printf("%f ", pca->covariance[i + j*LEN]);
  188. }
  189. printf("\n");
  190. }
  191. for(i=0; i<LEN; i++){
  192. double v[LEN];
  193. double error=0;
  194. memset(v, 0, sizeof(v));
  195. for(j=0; j<LEN; j++){
  196. for(k=0; k<LEN; k++){
  197. v[j] += pca->covariance[FFMIN(k,j) + FFMAX(k,j)*LEN] * eigenvector[i + k*LEN];
  198. }
  199. v[j] /= eigenvalue[i];
  200. error += fabs(v[j] - eigenvector[i + j*LEN]);
  201. }
  202. printf("%f ", error);
  203. }
  204. printf("\n");
  205. for(i=0; i<LEN; i++){
  206. for(j=0; j<LEN; j++){
  207. printf("%9.6f ", eigenvector[i + j*LEN]);
  208. }
  209. printf(" %9.1f %f\n", eigenvalue[i], eigenvalue[i]/eigenvalue[0]);
  210. }
  211. return 0;
  212. }
  213. #endif