source: 3DVCSoftware/trunk/source/App/utils/BitrateTargeting/GuessLambdaModifiers.cpp @ 1413

Last change on this file since 1413 was 1413, checked in by tech, 6 years ago

Merged HTM-16.2-dev@1412

File size: 15.9 KB
Line 
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-2017, 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
39namespace
40{
41  /// Formatted input for a bitrate vector
42  /// \param left The input stream that contains the bitrate vector
43  /// \param right The vector to be written to
44  /// \pre right must be empty
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
83  /// Makes a next guess for a single Lambda-modifier based on only one previous guess
84  /// \param initialAdjustmentParameter The proportionality to use between the target bitrate and the previous guess
85  /// \param target The target bitrate value that this Lambda-modifier is trying to reach
86  /// \param previousPoint The previous guess
87  /// \return The Lambda-modifier guess
88  /// \pre The given point must contain only positive non-zero values
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
102double 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
118double guessLambdaModifier(
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
178namespace
179{
180  /// Extracts a single point at the given index from a full meta-log entry
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
189  /// Calculates the inter dampening factor based
190  /// \param parameter The inter dampening parameter which determines how severely the inter dampening factor is affected by Lambda-modifier changes at previous temporal layers
191  /// \param cumulativeDelta The sum of the percentage changes of the Lambda-modifiers at the previous temporal layers
192  /// \return The calculated inter dampening factor
193  /// \pre cumulativeDelta must be non-negative
194  /// \pre parameter must be non-negative
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
203std::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
241namespace
242{
243  /// Ignores all of the the characters up to and including a given character
244  /// \param i The active input stream
245  /// \param character The character to ignore up to
246  /// \throw MetaLogParseException if the stream goes bad before character is encountered or just after character is encountered
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
257  /// Parses a Lambda-modifier map
258  /// \param right The map to write the output to
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
349  /// Extracts the indexes from the given maps
350  /// \return The set of indexes
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
362void guessLambdaModifiers(
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  {
373    throw InitialAdjustmentParameterParseException( );
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
389    MetaLogEntry< std::map< unsigned char, double > > entry;
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  {
433    throw MismatchedIndexesException( );
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    {
441      throw MismatchedIndexesException( );
442    }
443    if( i->bitrateVector.size( ) != targetVector.size( ) )
444    {
445      throw MismatchedIndexesException( );
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}
Note: See TracBrowser for help on using the repository browser.