pca.c 6.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256
  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. if (!pca)
  40. return NULL;
  41. pca->n= n;
  42. pca->z = av_malloc(sizeof(*pca->z) * n);
  43. pca->count=0;
  44. pca->covariance= av_calloc(n*n, sizeof(double));
  45. pca->mean= av_calloc(n, sizeof(double));
  46. if (!pca->z || !pca->covariance || !pca->mean) {
  47. ff_pca_free(pca);
  48. return NULL;
  49. }
  50. return pca;
  51. }
  52. void ff_pca_free(PCA *pca){
  53. av_freep(&pca->covariance);
  54. av_freep(&pca->mean);
  55. av_freep(&pca->z);
  56. av_free(pca);
  57. }
  58. void ff_pca_add(PCA *pca, double *v){
  59. int i, j;
  60. const int n= pca->n;
  61. for(i=0; i<n; i++){
  62. pca->mean[i] += v[i];
  63. for(j=i; j<n; j++)
  64. pca->covariance[j + i*n] += v[i]*v[j];
  65. }
  66. pca->count++;
  67. }
  68. int ff_pca(PCA *pca, double *eigenvector, double *eigenvalue){
  69. int i, j, pass;
  70. int k=0;
  71. const int n= pca->n;
  72. double *z = pca->z;
  73. memset(eigenvector, 0, sizeof(double)*n*n);
  74. for(j=0; j<n; j++){
  75. pca->mean[j] /= pca->count;
  76. eigenvector[j + j*n] = 1.0;
  77. for(i=0; i<=j; i++){
  78. pca->covariance[j + i*n] /= pca->count;
  79. pca->covariance[j + i*n] -= pca->mean[i] * pca->mean[j];
  80. pca->covariance[i + j*n] = pca->covariance[j + i*n];
  81. }
  82. eigenvalue[j]= pca->covariance[j + j*n];
  83. z[j]= 0;
  84. }
  85. for(pass=0; pass < 50; pass++){
  86. double sum=0;
  87. for(i=0; i<n; i++)
  88. for(j=i+1; j<n; j++)
  89. sum += fabs(pca->covariance[j + i*n]);
  90. if(sum == 0){
  91. for(i=0; i<n; i++){
  92. double maxvalue= -1;
  93. for(j=i; j<n; j++){
  94. if(eigenvalue[j] > maxvalue){
  95. maxvalue= eigenvalue[j];
  96. k= j;
  97. }
  98. }
  99. eigenvalue[k]= eigenvalue[i];
  100. eigenvalue[i]= maxvalue;
  101. for(j=0; j<n; j++){
  102. double tmp= eigenvector[k + j*n];
  103. eigenvector[k + j*n]= eigenvector[i + j*n];
  104. eigenvector[i + j*n]= tmp;
  105. }
  106. }
  107. return pass;
  108. }
  109. for(i=0; i<n; i++){
  110. for(j=i+1; j<n; j++){
  111. double covar= pca->covariance[j + i*n];
  112. double t,c,s,tau,theta, h;
  113. if(pass < 3 && fabs(covar) < sum / (5*n*n)) //FIXME why pass < 3
  114. continue;
  115. if(fabs(covar) == 0.0) //FIXME should not be needed
  116. continue;
  117. if(pass >=3 && fabs((eigenvalue[j]+z[j])/covar) > (1LL<<32) && fabs((eigenvalue[i]+z[i])/covar) > (1LL<<32)){
  118. pca->covariance[j + i*n]=0.0;
  119. continue;
  120. }
  121. h= (eigenvalue[j]+z[j]) - (eigenvalue[i]+z[i]);
  122. theta=0.5*h/covar;
  123. t=1.0/(fabs(theta)+sqrt(1.0+theta*theta));
  124. if(theta < 0.0) t = -t;
  125. c=1.0/sqrt(1+t*t);
  126. s=t*c;
  127. tau=s/(1.0+c);
  128. z[i] -= t*covar;
  129. z[j] += t*covar;
  130. #define ROTATE(a,i,j,k,l) {\
  131. double g=a[j + i*n];\
  132. double h=a[l + k*n];\
  133. a[j + i*n]=g-s*(h+g*tau);\
  134. a[l + k*n]=h+s*(g-h*tau); }
  135. for(k=0; k<n; k++) {
  136. if(k!=i && k!=j){
  137. ROTATE(pca->covariance,FFMIN(k,i),FFMAX(k,i),FFMIN(k,j),FFMAX(k,j))
  138. }
  139. ROTATE(eigenvector,k,i,k,j)
  140. }
  141. pca->covariance[j + i*n]=0.0;
  142. }
  143. }
  144. for (i=0; i<n; i++) {
  145. eigenvalue[i] += z[i];
  146. z[i]=0.0;
  147. }
  148. }
  149. return -1;
  150. }
  151. #ifdef TEST
  152. #undef printf
  153. #include <stdio.h>
  154. #include <stdlib.h>
  155. #include "lfg.h"
  156. int main(void){
  157. PCA *pca;
  158. int i, j, k;
  159. #define LEN 8
  160. double eigenvector[LEN*LEN];
  161. double eigenvalue[LEN];
  162. AVLFG prng;
  163. av_lfg_init(&prng, 1);
  164. pca= ff_pca_init(LEN);
  165. for(i=0; i<9000000; i++){
  166. double v[2*LEN+100];
  167. double sum=0;
  168. int pos = av_lfg_get(&prng) % LEN;
  169. int v2 = av_lfg_get(&prng) % 101 - 50;
  170. v[0] = av_lfg_get(&prng) % 101 - 50;
  171. for(j=1; j<8; j++){
  172. if(j<=pos) v[j]= v[0];
  173. else v[j]= v2;
  174. sum += v[j];
  175. }
  176. /* for(j=0; j<LEN; j++){
  177. v[j] -= v[pos];
  178. }*/
  179. // sum += av_lfg_get(&prng) % 10;
  180. /* for(j=0; j<LEN; j++){
  181. v[j] -= sum/LEN;
  182. }*/
  183. // lbt1(v+100,v+100,LEN);
  184. ff_pca_add(pca, v);
  185. }
  186. ff_pca(pca, eigenvector, eigenvalue);
  187. for(i=0; i<LEN; i++){
  188. pca->count= 1;
  189. pca->mean[i]= 0;
  190. // (0.5^|x|)^2 = 0.5^2|x| = 0.25^|x|
  191. // pca.covariance[i + i*LEN]= pow(0.5, fabs
  192. for(j=i; j<LEN; j++){
  193. printf("%f ", pca->covariance[i + j*LEN]);
  194. }
  195. printf("\n");
  196. }
  197. for(i=0; i<LEN; i++){
  198. double v[LEN];
  199. double error=0;
  200. memset(v, 0, sizeof(v));
  201. for(j=0; j<LEN; j++){
  202. for(k=0; k<LEN; k++){
  203. v[j] += pca->covariance[FFMIN(k,j) + FFMAX(k,j)*LEN] * eigenvector[i + k*LEN];
  204. }
  205. v[j] /= eigenvalue[i];
  206. error += fabs(v[j] - eigenvector[i + j*LEN]);
  207. }
  208. printf("%f ", error);
  209. }
  210. printf("\n");
  211. for(i=0; i<LEN; i++){
  212. for(j=0; j<LEN; j++){
  213. printf("%9.6f ", eigenvector[i + j*LEN]);
  214. }
  215. printf(" %9.1f %f\n", eigenvalue[i], eigenvalue[i]/eigenvalue[0]);
  216. }
  217. return 0;
  218. }
  219. #endif