## ffmpeg / libavutil / lls.c @ 0b006599

History | View | Annotate | Download (4.04 KB)

1 | 82ab5ad7 | Michael Niedermayer | ```
/*
``` |
---|---|---|---|

2 | ```
* linear least squares model
``` |
||

3 | ```
*
``` |
||

4 | ```
* Copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at>
``` |
||

5 | ```
*
``` |
||

6 | b78e7197 | Diego Biurrun | ```
* This file is part of FFmpeg.
``` |

7 | ```
*
``` |
||

8 | ```
* FFmpeg is free software; you can redistribute it and/or
``` |
||

9 | 82ab5ad7 | Michael Niedermayer | ```
* modify it under the terms of the GNU Lesser General Public
``` |

10 | ```
* License as published by the Free Software Foundation; either
``` |
||

11 | b78e7197 | Diego Biurrun | ```
* version 2.1 of the License, or (at your option) any later version.
``` |

12 | 82ab5ad7 | Michael Niedermayer | ```
*
``` |

13 | b78e7197 | Diego Biurrun | ```
* FFmpeg is distributed in the hope that it will be useful,
``` |

14 | 82ab5ad7 | Michael Niedermayer | ```
* but WITHOUT ANY WARRANTY; without even the implied warranty of
``` |

15 | ```
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
``` |
||

16 | ```
* Lesser General Public License for more details.
``` |
||

17 | ```
*
``` |
||

18 | ```
* You should have received a copy of the GNU Lesser General Public
``` |
||

19 | b78e7197 | Diego Biurrun | ```
* License along with FFmpeg; if not, write to the Free Software
``` |

20 | 538389c9 | Diego Biurrun | ```
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
``` |

21 | 82ab5ad7 | Michael Niedermayer | ```
*/
``` |

22 | |||

23 | ```
/**
``` |
||

24 | ```
* @file lls.c
``` |
||

25 | ```
* linear least squares model
``` |
||

26 | ```
*/
``` |
||

27 | |||

28 | #include <math.h> |
||

29 | #include <string.h> |
||

30 | |||

31 | #include "lls.h" |
||

32 | |||

33 | ```
#ifdef TEST
``` |
||

34 | ```
#define av_log(a,b,...) printf(__VA_ARGS__)
``` |
||

35 | ```
#endif
``` |
||

36 | |||

37 | void av_init_lls(LLSModel *m, int indep_count){ |
||

38 | memset(m, 0, sizeof(LLSModel)); |
||

39 | |||

40 | m->indep_count= indep_count; |
||

41 | } |
||

42 | |||

43 | void av_update_lls(LLSModel *m, double *var, double decay){ |
||

44 | ```
int i,j;
``` |
||

45 | |||

46 | for(i=0; i<=m->indep_count; i++){ |
||

47 | ```
for(j=i; j<=m->indep_count; j++){
``` |
||

48 | m->covariance[i][j] *= decay; |
||

49 | m->covariance[i][j] += var[i]*var[j]; |
||

50 | } |
||

51 | } |
||

52 | } |
||

53 | |||

54 | 408ec4e2 | Michael Niedermayer | void av_solve_lls(LLSModel *m, double threshold, int min_order){ |

55 | 82ab5ad7 | Michael Niedermayer | ```
int i,j,k;
``` |

56 | double (*factor)[MAX_VARS+1]= &m->covariance[1][0]; |
||

57 | double (*covar )[MAX_VARS+1]= &m->covariance[1][1]; |
||

58 | double *covar_y = m->covariance[0]; |
||

59 | ```
int count= m->indep_count;
``` |
||

60 | |||

61 | for(i=0; i<count; i++){ |
||

62 | ```
for(j=i; j<count; j++){
``` |
||

63 | ```
double sum= covar[i][j];
``` |
||

64 | |||

65 | for(k=i-1; k>=0; k--) |
||

66 | sum -= factor[i][k]*factor[j][k]; |
||

67 | |||

68 | ```
if(i==j){
``` |
||

69 | ```
if(sum < threshold)
``` |
||

70 | sum= 1.0; |
||

71 | factor[i][i]= sqrt(sum); |
||

72 | ```
}else
``` |
||

73 | factor[j][i]= sum / factor[i][i]; |
||

74 | } |
||

75 | } |
||

76 | for(i=0; i<count; i++){ |
||

77 | double sum= covar_y[i+1]; |
||

78 | for(k=i-1; k>=0; k--) |
||

79 | 408ec4e2 | Michael Niedermayer | ```
sum -= factor[i][k]*m->coeff[0][k];
``` |

80 | ```
m->coeff[0][i]= sum / factor[i][i];
``` |
||

81 | 82ab5ad7 | Michael Niedermayer | } |

82 | |||

83 | 408ec4e2 | Michael Niedermayer | for(j=count-1; j>=min_order; j--){ |

84 | for(i=j; i>=0; i--){ |
||

85 | double sum= m->coeff[0][i]; |
||

86 | for(k=i+1; k<=j; k++) |
||

87 | sum -= factor[k][i]*m->coeff[j][k]; |
||

88 | m->coeff[j][i]= sum / factor[i][i]; |
||

89 | } |
||

90 | 82ab5ad7 | Michael Niedermayer | |

91 | 408ec4e2 | Michael Niedermayer | ```
m->variance[j]= covar_y[0];
``` |

92 | for(i=0; i<=j; i++){ |
||

93 | double sum= m->coeff[j][i]*covar[i][i] - 2*covar_y[i+1]; |
||

94 | for(k=0; k<i; k++) |
||

95 | ```
sum += 2*m->coeff[j][k]*covar[k][i];
``` |
||

96 | m->variance[j] += m->coeff[j][i]*sum; |
||

97 | } |
||

98 | 82ab5ad7 | Michael Niedermayer | } |

99 | } |
||

100 | |||

101 | 408ec4e2 | Michael Niedermayer | double av_evaluate_lls(LLSModel *m, double *param, int order){ |

102 | 82ab5ad7 | Michael Niedermayer | ```
int i;
``` |

103 | double out= 0; |
||

104 | |||

105 | 408ec4e2 | Michael Niedermayer | for(i=0; i<=order; i++) |

106 | out+= param[i]*m->coeff[order][i]; |
||

107 | 82ab5ad7 | Michael Niedermayer | |

108 | ```
return out;
``` |
||

109 | } |
||

110 | |||

111 | ```
#ifdef TEST
``` |
||

112 | |||

113 | #include <stdlib.h> |
||

114 | #include <stdio.h> |
||

115 | |||

116 | ```
int main(){
``` |
||

117 | LLSModel m; |
||

118 | 408ec4e2 | Michael Niedermayer | ```
int i, order;
``` |

119 | 82ab5ad7 | Michael Niedermayer | |

120 | ```
av_init_lls(&m, 3);
``` |
||

121 | |||

122 | for(i=0; i<100; i++){ |
||

123 | double var[4]; |
||

124 | ```
double eval, variance;
``` |
||

125 | 408ec4e2 | Michael Niedermayer | ```
#if 0
``` |

126 | 82ab5ad7 | Michael Niedermayer | ```
var[1] = rand() / (double)RAND_MAX;
``` |

127 | ```
var[2] = rand() / (double)RAND_MAX;
``` |
||

128 | ```
var[3] = rand() / (double)RAND_MAX;
``` |
||

129 | |||

130 | 408ec4e2 | Michael Niedermayer | ```
var[2]= var[1] + var[3]/2;
``` |

131 | 82ab5ad7 | Michael Niedermayer | |

132 | ```
var[0] = var[1] + var[2] + var[3] + var[1]*var[2]/100;
``` |
||

133 | 408ec4e2 | Michael Niedermayer | ```
#else
``` |

134 | var[0] = (rand() / (double)RAND_MAX - 0.5)*2; |
||

135 | var[1] = var[0] + rand() / (double)RAND_MAX - 0.5; |
||

136 | var[2] = var[1] + rand() / (double)RAND_MAX - 0.5; |
||

137 | var[3] = var[2] + rand() / (double)RAND_MAX - 0.5; |
||

138 | ```
#endif
``` |
||

139 | 82ab5ad7 | Michael Niedermayer | av_update_lls(&m, var, 0.99); |

140 | 408ec4e2 | Michael Niedermayer | av_solve_lls(&m, 0.001, 0); |

141 | for(order=0; order<3; order++){ |
||

142 | ```
eval= av_evaluate_lls(&m, var+1, order);
``` |
||

143 | av_log(NULL, AV_LOG_DEBUG, "real:%f order:%d pred:%f var:%f coeffs:%f %f %f\n", |
||

144 | var[0], order, eval, sqrt(m.variance[order] / (i+1)), |
||

145 | m.coeff[order][0], m.coeff[order][1], m.coeff[order][2]); |
||

146 | } |
||

147 | 82ab5ad7 | Michael Niedermayer | } |

148 | return 0; |
||

149 | } |
||

150 | |||

151 | `#endif` |