HEVC Test Model (HM)  HM-16.3
GuessLambdaModifiers.cpp
Go to the documentation of this file.
1 /* The copyright in this software is being made available under the BSD
2  * License, included below. This software may be subject to other third party
3  * and contributor rights, including patent rights, and no such rights are
4  * granted under this license.
5  *
6  * Copyright (c) 2010-2015, ITU/ISO/IEC
7  * All rights reserved.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions are met:
11  *
12  * * Redistributions of source code must retain the above copyright notice,
13  * this list of conditions and the following disclaimer.
14  * * Redistributions in binary form must reproduce the above copyright notice,
15  * this list of conditions and the following disclaimer in the documentation
16  * and/or other materials provided with the distribution.
17  * * Neither the name of the ITU/ISO/IEC nor the names of its contributors may
18  * be used to endorse or promote products derived from this software without
19  * specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
22  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS
25  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
26  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
27  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
28  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
29  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
30  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
31  * THE POSSIBILITY OF SUCH DAMAGE.
32  */
33 
34 #include "GuessLambdaModifiers.h"
35 #include <limits>
36 #include <cassert>
37 #include <cmath>
38 
39 namespace
40 {
45  void parseBitrateVector( std::istream& left, std::vector< double >& right )
46  {
47  assert( right.empty( ) );
48 
49  for( ; ; )
50  {
51  assert( left.good( ) );
52 
53  double bitrate;
54  left >> bitrate;
55  if( left.fail( ) )
56  {
57  break;
58  }
59  if( bitrate <= ( double )0.0 )
60  {
61  left.setstate( std::istream::failbit );
62  }
63  else
64  {
65  right.push_back( bitrate );
66  }
67  if( !left.good( ) )
68  {
69  break;
70  }
71 
72  if( left.peek( ) == ' ' )
73  {
74  left.ignore( );
75  }
76  else
77  {
78  break;
79  }
80  }
81  }
82 
89  double incrementLambdaModifier(
90  double initialAdjustmentParameter,
91  double targetBitrate,
92  const Point& previousPoint )
93  {
94  assert( ( double )0.0 < previousPoint.lambdaModifier );
95  assert( ( double )0.0 < previousPoint.bitrate );
96 
97  double extrapolated( previousPoint.lambdaModifier * targetBitrate / previousPoint.bitrate );
98  return previousPoint.lambdaModifier + initialAdjustmentParameter * ( extrapolated - previousPoint.lambdaModifier );
99  }
100 }
101 
102 double polateLambdaModifier( double targetBitrate, const Point& point1, const Point& point2 )
103 {
104  assert( 0.0 < point1.lambdaModifier );
105  assert( 0.0 < point2.lambdaModifier );
106  assert( 0.0 < point1.bitrate );
107  assert( 0.0 < point2.bitrate );
108  assert( point1.lambdaModifier != point2.lambdaModifier );
109  assert( point1.bitrate != point2.bitrate );
110 
111  // Calculate and return the result
112  double denominator( point1.bitrate - point2.bitrate );
113  double result( point1.lambdaModifier
114  + ( point1.lambdaModifier - point2.lambdaModifier ) / denominator * ( targetBitrate - point1.bitrate ) );
115  return result;
116 }
117 
119  double initialAdjustmentParameter,
120  double targetBitrate,
121  const std::list< Point >& pointList,
122  double interDampeningFactor )
123 {
124  assert( ( double )0.0 < interDampeningFactor );
125  assert( interDampeningFactor <= ( double )1.0 );
126  assert( !pointList.empty( ) );
127 
128  double preliminaryResult;
129 
130  if( 1 == pointList.size( ) ) // If there is only one prevous point, then we cannot interpolate, so we call incrementLambdaModifier
131  {
132  preliminaryResult = incrementLambdaModifier( initialAdjustmentParameter, targetBitrate, pointList.back( ) );
133  }
134  else // If there are at least two previous points, then we may be able to interpolate
135  {
136  std::list< Point >::const_reverse_iterator i( pointList.rbegin( ) );
137  Point point1 = *i;
138  ++i;
139  Point point2 = *i;
140 
141  // If the slope is either horizontal or vertical, we cannot interpolate
142  if( point1.lambdaModifier == point2.lambdaModifier || point1.bitrate == point2.bitrate )
143  {
144  preliminaryResult = incrementLambdaModifier( initialAdjustmentParameter, targetBitrate, pointList.back( ) );
145  }
146  else // If the slope is not horizontal and not vertical, we can interpolate
147  {
148  preliminaryResult = polateLambdaModifier( targetBitrate, point1, point2 );
149  }
150  }
151 
152  double previousResult( pointList.back( ).lambdaModifier );
153 
154  // Apply "intra dampening"
155  {
156  double intermediate( std::log( ( double )1.0 + std::abs( preliminaryResult - previousResult ) / previousResult ) );
157  assert( ( double )0.0 <= intermediate );
158  if( ( preliminaryResult - previousResult ) < 0.0 )
159  {
160  preliminaryResult = previousResult * ( ( double )1.0 - intermediate );
161  }
162  else
163  {
164  preliminaryResult = previousResult * ( ( double )1.0 + intermediate );
165  }
166  }
167 
168  // Apply "inter dampening factor". If necessary, reduce the factor until a positive result is acheived.
169  double result;
170  do
171  {
172  result = previousResult + interDampeningFactor * ( preliminaryResult - previousResult );
173  interDampeningFactor /= ( double )2.0;
174  } while( result <= ( double )0.0 );
175  return result;
176 }
177 
178 namespace
179 {
181  Point pointFromFullMetaLogEntry( unsigned char index, const MetaLogEntry< std::vector< double > >& fullEntry )
182  {
183  Point result;
184  result.lambdaModifier = fullEntry.lambdaModifiers[ index ];
185  result.bitrate = fullEntry.bitrateVector[ index ];
186  return result;
187  }
188 
195  double interDampeningFactor( double parameter, double cumulativeDelta )
196  {
197  assert( 0.0 <= cumulativeDelta );
198  assert( 0.0 <= parameter );
199  return ( double )1.0 / ( parameter * cumulativeDelta + ( double )1.0 );
200  }
201 }
202 
203 std::vector< double > guessLambdaModifiers(
204  double initialAdjustmentParameter,
205  const std::vector< double > &targetBitrateVector,
206  const std::list< MetaLogEntry< std::vector< double > > >& metaLogEntryList )
207 {
208  assert( !targetBitrateVector.empty( ) );
209  assert( !metaLogEntryList.empty( ) );
210 
211  double cumulativeDelta( 0.0 );
212  std::vector< double > resultVector;
213  for( unsigned char i( 0 ); i < targetBitrateVector.size( ); ++i )
214  {
215  // Populate pointList with up to two of the previous points
216  std::list< Point > pointList;
217  std::list< MetaLogEntry< std::vector< double > > >::const_reverse_iterator j( metaLogEntryList.rbegin( ) );
218  pointList.push_front( pointFromFullMetaLogEntry( i, *j ) );
219  ++j;
220  if( j != metaLogEntryList.rend( ) )
221  {
222  pointList.push_front( pointFromFullMetaLogEntry( i, *j ) );
223  }
224 
225  // Calculate the new Lambda-modifier guess and add it to the result vector
226  const double newLambdaModifier( guessLambdaModifier(
227  initialAdjustmentParameter,
228  targetBitrateVector[ i ], // target bitrate
229  pointList,
230  interDampeningFactor( 50.0, cumulativeDelta ) ) );
231  resultVector.push_back( newLambdaModifier );
232 
233  // Increment the cumulativeDelta
234  const double oldLambdaModifier( pointList.back( ).lambdaModifier );
235  cumulativeDelta += std::abs( newLambdaModifier - oldLambdaModifier ) / oldLambdaModifier;
236  }
237 
238  return resultVector;
239 }
240 
241 namespace
242 {
247  void ignoreUpTo( std::istream& i, char character )
248  {
249  while( i.good( ) && character != i.get( ) )
250  ;
251  if( !i.good( ) )
252  {
253  throw MetaLogParseException( );
254  }
255  }
256 
259  void parseLambdaModifierMap( std::istream& left, std::map< unsigned char, double >& right )
260  {
261  for( ; ; )
262  {
263  assert( left.good( ) );
264 
265  // Ignore the "-LM"
266  if( '-' != left.get( ) )
267  {
268  left.setstate( std::istream::failbit );
269  }
270  if( !left.good( ) )
271  {
272  break;
273  }
274  if( 'L' != left.get( ) )
275  {
276  left.setstate( std::istream::failbit );
277  }
278  if( !left.good( ) )
279  {
280  break;
281  }
282  if( 'M' != left.get( ) )
283  {
284  left.setstate( std::istream::failbit );
285  }
286  if( !left.good( ) )
287  {
288  break;
289  }
290 
291  // Parse the index
292  long indexLong;
293  left >> indexLong;
294  if( !left.good( ) )
295  {
296  break;
297  }
298  if( indexLong < std::numeric_limits< unsigned char >::min( ) )
299  {
300  left.setstate( std::istream::failbit );
301  }
302  if( std::numeric_limits< unsigned char >::max( ) < indexLong )
303  {
304  left.setstate( std::istream::failbit );
305  }
306  if( !left.good( ) )
307  {
308  break;
309  }
310  unsigned char index( ( unsigned char )indexLong );
311 
312  if( ' ' != left.get( ) )
313  {
314  left.setstate( std::istream::failbit );
315  }
316  if( !left.good( ) )
317  {
318  break;
319  }
320 
321  // Parse the Lambda-modifier
322  double lambdaModifier;
323  left >> lambdaModifier;
324  if( lambdaModifier <= ( double )0.0 || ( !right.empty( ) && ( right.count( index ) != 0 || index <= right.rbegin( )->first ) ) )
325  {
326  left.setstate( std::istream::failbit );
327  }
328  else
329  {
330  right[ index ] = lambdaModifier;
331  }
332  if( !left.good( ) )
333  {
334  break;
335  }
336 
337  // If we peek and see a space, then there should be more Lambda-modifiers to parse. Otherwise, we are finished.
338  if( left.peek( ) == ' ' )
339  {
340  left.ignore( );
341  }
342  else
343  {
344  break;
345  }
346  }
347  }
348 
351  std::set< unsigned char > indexSetFromMap( const std::map< unsigned char, double >& in )
352  {
353  std::set< unsigned char > result;
354  for( typename std::map< unsigned char, double >::const_iterator i( in.begin( ) ); i != in.end( ); ++i )
355  {
356  result.insert( i->first );
357  }
358  return result;
359  }
360 }
361 
363  std::ostream& o,
364  std::istream& initialAdjustmentParameterIstream,
365  std::istream& targetsIstream,
366  std::istream& metaLogIstream )
367 {
368  // Parse the initialAdjustmentParameter
369  double initialAdjustmentParameter;
370  initialAdjustmentParameterIstream >> initialAdjustmentParameter;
371  if( initialAdjustmentParameterIstream.fail( ) || initialAdjustmentParameterIstream.good( ) )
372  {
374  }
375 
376  // Parse the targets
377  std::vector< double > targetVector;
378  parseBitrateVector( targetsIstream, targetVector );
379  if( targetVector.empty( ) || targetsIstream.fail( ) || targetsIstream.good( ) )
380  {
381  throw TargetsParseException( );
382  }
383 
384  // Parse the metalog
385  std::list< MetaLogEntry< std::map< unsigned char, double > > > metaLogEntryList;
386  do
387  {
388  // Parse the Lambda-modifiers
390  parseLambdaModifierMap( metaLogIstream, entry.lambdaModifiers );
391  if( !metaLogIstream.good( ) )
392  {
393  throw MetaLogParseException( );
394  }
395 
396  // Skip the ';'
397  if( ';' != metaLogIstream.get( ) )
398  {
399  throw MetaLogParseException( );
400  }
401  if( !metaLogIstream.good( ) )
402  {
403  throw MetaLogParseException( );
404  }
405 
406  // Parse the bitrates
407  parseBitrateVector( metaLogIstream, entry.bitrateVector );
408  if( metaLogIstream.fail( ) )
409  {
410  throw MetaLogParseException( );
411  }
412  metaLogEntryList.push_back( entry );
413 
414  if( !metaLogIstream.good( ) )
415  {
416  break;
417  }
418  if( metaLogIstream.get( ) != '\n' )
419  {
420  throw MetaLogParseException( );
421  }
422  metaLogIstream.peek( );
423  } while( metaLogIstream.good( ) );
424  if( metaLogEntryList.empty( ) )
425  {
426  throw MetaLogParseException( ); // The meta-log should not be empty
427  }
428 
429  // Initialize firstIndexVector and check that the sizes and indexes match
430  std::set< unsigned char > firstIndexSet( indexSetFromMap( metaLogEntryList.front( ).lambdaModifiers ) );
431  if( firstIndexSet.size( ) != targetVector.size( ) )
432  {
434  }
435  for( std::list< MetaLogEntry< std::map< unsigned char, double > > >::const_iterator i( metaLogEntryList.begin( ) );
436  i != metaLogEntryList.end( );
437  ++i )
438  {
439  if( indexSetFromMap( i->lambdaModifiers ) != firstIndexSet )
440  {
442  }
443  if( i->bitrateVector.size( ) != targetVector.size( ) )
444  {
446  }
447  }
448 
449  // Initialize simplifiedMetaLogEntryList
450  std::list< MetaLogEntry< std::vector< double > > > simplifiedMetaLogEntryList;
451  for( std::list< MetaLogEntry< std::map< unsigned char, double > > >::const_iterator i( metaLogEntryList.begin( ) );
452  i != metaLogEntryList.end( );
453  ++i )
454  {
455  simplifiedMetaLogEntryList.push_back( MetaLogEntry< std::vector< double > >( ) );
456  for( std::map< unsigned char, double >::const_iterator j( i->lambdaModifiers.begin( ) ); j != i->lambdaModifiers.end( ); ++j )
457  {
458  simplifiedMetaLogEntryList.back( ).lambdaModifiers.push_back( j->second );
459  }
460  simplifiedMetaLogEntryList.back( ).bitrateVector = i->bitrateVector;
461  }
462 
463  // Run the calculations
464  std::vector< double > resultVector( guessLambdaModifiers( initialAdjustmentParameter, targetVector, simplifiedMetaLogEntryList ) );
465 
466  // Output the results
467  std::set< unsigned char >::const_iterator indexIter( firstIndexSet.begin( ) );
468  std::vector< double >::const_iterator resultIter( resultVector.begin( ) );
469  do
470  {
471  if( indexIter != firstIndexSet.begin( ) )
472  {
473  o << " ";
474  }
475  o << "-LM" << ( long )( *indexIter ) << " ";
476  o.setf( std::ostream::fixed, std::ostream::floatfield );
477  o.precision( 7 );
478  o << ( *resultIter );
479 
480  ++indexIter;
481  ++resultIter;
482  } while( indexIter != firstIndexSet.end( ) );
483  assert( resultIter == resultVector.end( ) ); // The index set and the result vector should be the same size
484 }
double bitrate
Contains a Lambda-modifier and bitrate for only a single index.
Thrown if there is an error parsing the initial adjustment parameter.
Thrown if there is an error parsing the targets.
std::vector< double > guessLambdaModifiers(double initialAdjustmentParameter, const std::vector< double > &targetBitrateVector, const std::list< MetaLogEntry< std::vector< double > > > &metaLogEntryList)
TLambdaModifier lambdaModifiers
std::vector< double > bitrateVector
Thrown if there is an error parsing the meta-log.
Full meta-log entry.
double polateLambdaModifier(double targetBitrate, const Point &point1, const Point &point2)
double lambdaModifier
double guessLambdaModifier(double initialAdjustmentParameter, double targetBitrate, const std::list< Point > &pointList, double interDampeningFactor)
Thrown if there is a mismatch in the vector sizes or the Lambda-modifier indexes. ...