source: SHVCSoftware/branches/SHM-upgrade/source/App/utils/BitrateTargeting/GuessLambdaModifiers.cpp @ 1465

Last change on this file since 1465 was 595, checked in by seregin, 11 years ago

merge with SHM-5.0-dev branch

  • Property svn:eol-style set to native
File size: 15.0 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-2014, 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( ) ) break;
56      if( bitrate <= ( double )0.0 )
57      {
58        left.setstate( std::istream::failbit );
59      }
60      else
61      {
62        right.push_back( bitrate );
63      }
64      if( !left.good( ) ) break;
65     
66      if( left.peek( ) == ' ' )
67      {
68        left.ignore( );
69      }
70      else
71      {
72        break;
73      }
74    }
75  }
76 
77  /// Makes a next guess for a single Lambda-modifier based on only one previous guess
78  /// \param initialAdjustmentParameter The proportionality to use between the target bitrate and the previous guess
79  /// \param target The target bitrate value that this Lambda-modifier is trying to reach
80  /// \param previousPoint The previous guess
81  /// \return The Lambda-modifier guess
82  /// \pre The given point must contain only positive non-zero values
83  double incrementLambdaModifier(
84      double initialAdjustmentParameter,
85      double targetBitrate,
86      const Point& previousPoint )
87  {
88    assert( ( double )0.0 < previousPoint.lambdaModifier );
89    assert( ( double )0.0 < previousPoint.bitrate );
90   
91    double extrapolated( previousPoint.lambdaModifier * targetBitrate / previousPoint.bitrate );
92    return previousPoint.lambdaModifier + initialAdjustmentParameter * ( extrapolated - previousPoint.lambdaModifier );
93  }
94}
95
96double polateLambdaModifier( double targetBitrate, const Point& point1, const Point& point2 )
97{
98  assert( 0.0 < point1.lambdaModifier );
99  assert( 0.0 < point2.lambdaModifier );
100  assert( 0.0 < point1.bitrate );
101  assert( 0.0 < point2.bitrate );
102  assert( point1.lambdaModifier != point2.lambdaModifier );
103  assert( point1.bitrate != point2.bitrate );
104 
105  // Calculate and return the result
106  double denominator( point1.bitrate - point2.bitrate );
107  double result( point1.lambdaModifier
108      + ( point1.lambdaModifier - point2.lambdaModifier ) / denominator * ( targetBitrate - point1.bitrate ) );
109  return result;
110}
111
112double guessLambdaModifier(
113    double initialAdjustmentParameter,
114    double targetBitrate,
115    const std::list< Point >& pointList,
116    double interDampeningFactor )
117{
118  assert( ( double )0.0 < interDampeningFactor );
119  assert( interDampeningFactor <= ( double )1.0 );
120  assert( !pointList.empty( ) );
121 
122  double preliminaryResult;
123 
124  if( 1 == pointList.size( ) )  // If there is only one prevous point, then we cannot interpolate, so we call incrementLambdaModifier
125  {
126    preliminaryResult = incrementLambdaModifier( initialAdjustmentParameter, targetBitrate, pointList.back( ) );
127  }
128  else  // If there are at least two previous points, then we may be able to interpolate
129  {
130    std::list< Point >::const_reverse_iterator i( pointList.rbegin( ) );
131    Point point1 = *i;
132    ++i;
133    Point point2 = *i;
134   
135    // If the slope is either horizontal or vertical, we cannot interpolate
136    if( point1.lambdaModifier == point2.lambdaModifier || point1.bitrate == point2.bitrate )
137    {
138      preliminaryResult = incrementLambdaModifier( initialAdjustmentParameter, targetBitrate, pointList.back( ) );
139    }
140    else  // If the slope is not horizontal and not vertical, we can interpolate
141    {
142      preliminaryResult = polateLambdaModifier( targetBitrate, point1, point2 );
143    }
144  }
145 
146  double previousResult( pointList.back( ).lambdaModifier );
147 
148  // Apply "intra dampening"
149  {
150    double intermediate( std::log( ( double )1.0 + std::abs( preliminaryResult - previousResult ) / previousResult ) );
151    assert( ( double )0.0 <= intermediate );
152    if( ( preliminaryResult - previousResult ) < 0.0 )
153    {
154      preliminaryResult = previousResult * ( ( double )1.0 - intermediate );
155    }
156    else
157    {
158      preliminaryResult = previousResult * ( ( double )1.0 + intermediate );
159    }
160  }
161 
162  // Apply "inter dampening factor".  If necessary, reduce the factor until a positive result is acheived.
163  double result;
164  do
165  {
166    result = previousResult + interDampeningFactor * ( preliminaryResult - previousResult );
167    interDampeningFactor /= ( double )2.0;
168  } while( result <= ( double )0.0 );
169  return result;
170}
171
172namespace
173{
174  /// Extracts a single point at the given index from a full meta-log entry
175  Point pointFromFullMetaLogEntry( unsigned char index, const MetaLogEntry< std::vector< double > >& fullEntry )
176  {
177    Point result;
178    result.lambdaModifier = fullEntry.lambdaModifiers[ index ];
179    result.bitrate = fullEntry.bitrateVector[ index ];
180    return result;
181  }
182 
183  /// Calculates the inter dampening factor based
184  /// \param parameter The inter dampening parameter which determines how severely the inter dampening factor is affected by Lambda-modifier changes at previous temporal layers
185  /// \param cumulativeDelta The sum of the percentage changes of the Lambda-modifiers at the previous temporal layers
186  /// \return The calculated inter dampening factor
187  /// \pre cumulativeDelta must be non-negative
188  /// \pre parameter must be non-negative
189  double interDampeningFactor( double parameter, double cumulativeDelta )
190  {
191    assert( 0.0 <= cumulativeDelta );
192    assert( 0.0 <= parameter );
193    return ( double )1.0 / ( parameter * cumulativeDelta + ( double )1.0 );
194  }
195}
196
197std::vector< double > guessLambdaModifiers(
198    double initialAdjustmentParameter,
199    const std::vector< double > &targetBitrateVector,
200    const std::list< MetaLogEntry< std::vector< double > > >& metaLogEntryList )
201{
202  assert( !targetBitrateVector.empty( ) );
203  assert( !metaLogEntryList.empty( ) );
204 
205  double cumulativeDelta( 0.0 );
206  std::vector< double > resultVector;
207  for( unsigned char i( 0 ); i < targetBitrateVector.size( ); ++i )
208  {
209    // Populate pointList with up to two of the previous points
210    std::list< Point > pointList;
211    std::list< MetaLogEntry< std::vector< double > > >::const_reverse_iterator j( metaLogEntryList.rbegin( ) );
212    pointList.push_front( pointFromFullMetaLogEntry( i, *j ) );
213    ++j;
214    if( j != metaLogEntryList.rend( ) ) pointList.push_front( pointFromFullMetaLogEntry( i, *j ) );
215   
216    // Calculate the new Lambda-modifier guess and add it to the result vector
217    const double newLambdaModifier( guessLambdaModifier(
218        initialAdjustmentParameter,
219        targetBitrateVector[ i ],  // target bitrate
220        pointList,
221        interDampeningFactor( 50.0, cumulativeDelta ) ) );
222    resultVector.push_back( newLambdaModifier );
223   
224    // Increment the cumulativeDelta
225    const double oldLambdaModifier( pointList.back( ).lambdaModifier );
226    cumulativeDelta += std::abs( newLambdaModifier - oldLambdaModifier ) / oldLambdaModifier;
227  }
228 
229  return resultVector;
230}
231
232namespace
233{
234  /// Ignores all of the the characters up to and including a given character
235  /// \param i The active input stream
236  /// \param character The character to ignore up to
237  /// \throw MetaLogParseException if the stream goes bad before character is encountered or just after character is encountered
238  void ignoreUpTo( std::istream& i, char character )
239  {
240    while( i.good( ) && character != i.get( ) )
241      ;
242    if( !i.good( ) ) throw MetaLogParseException( );
243  }
244 
245  /// Parses a Lambda-modifier map
246  /// \param right The map to write the output to
247  void parseLambdaModifierMap( std::istream& left, std::map< unsigned char, double >& right )
248  {
249    for( ; ; )
250    {
251      assert( left.good( ) );
252     
253      // Ignore the "-LM"
254      if( '-' != left.get( ) ) left.setstate( std::istream::failbit );
255      if( !left.good( ) ) break;
256      if( 'L' != left.get( ) ) left.setstate( std::istream::failbit );
257      if( !left.good( ) ) break;
258      if( 'M' != left.get( ) ) left.setstate( std::istream::failbit );
259      if( !left.good( ) ) break;
260     
261      // Parse the index
262      long indexLong;
263      left >> indexLong;
264      if( !left.good( ) ) break;
265      if( indexLong < std::numeric_limits< unsigned char >::min( ) ) left.setstate( std::istream::failbit );
266      if( std::numeric_limits< unsigned char >::max( ) < indexLong ) left.setstate( std::istream::failbit );
267      if( !left.good( ) ) break;
268      unsigned char index( ( unsigned char )indexLong );
269     
270      if( ' ' != left.get( ) ) left.setstate( std::istream::failbit );
271      if( !left.good( ) ) break;
272     
273      // Parse the Lambda-modifier
274      double lambdaModifier;
275      left >> lambdaModifier;
276      if( lambdaModifier <= ( double )0.0 || ( !right.empty( ) && ( right.count( index ) != 0 || index <= right.rbegin( )->first ) ) )
277      {
278        left.setstate( std::istream::failbit );
279      }
280      else
281      {
282        right[ index ] = lambdaModifier;
283      }
284      if( !left.good( ) ) break;
285     
286      // If we peek and see a space, then there should be more Lambda-modifiers to parse.  Otherwise, we are finished.
287      if( left.peek( ) == ' ' )
288      {
289        left.ignore( );
290      }
291      else
292      {
293        break;
294      }
295    }
296  }
297 
298  /// Extracts the indexes from the given maps
299  /// \return The set of indexes
300  std::set< unsigned char > indexSetFromMap( const std::map< unsigned char, double >& in )
301  {
302    std::set< unsigned char > result;
303    for( typename std::map< unsigned char, double >::const_iterator i( in.begin( ) ); i != in.end( ); ++i )
304    {
305      result.insert( i->first );
306    }
307    return result;
308  }
309}
310
311void guessLambdaModifiers(
312    std::ostream& o,
313    std::istream& initialAdjustmentParameterIstream,
314    std::istream& targetsIstream,
315    std::istream& metaLogIstream )
316{
317  // Parse the initialAdjustmentParameter
318  double initialAdjustmentParameter;
319  initialAdjustmentParameterIstream >> initialAdjustmentParameter;
320  if( initialAdjustmentParameterIstream.fail( ) || initialAdjustmentParameterIstream.good( ) )
321  {
322    throw InitialAdjustmentParameterParseException( );
323  }
324 
325  // Parse the targets
326  std::vector< double > targetVector;
327  parseBitrateVector( targetsIstream, targetVector );
328  if( targetVector.empty( ) || targetsIstream.fail( ) || targetsIstream.good( ) ) throw TargetsParseException( );
329 
330  // Parse the metalog
331  std::list< MetaLogEntry< std::map< unsigned char, double > > > metaLogEntryList;
332  do
333  {
334    // Parse the Lambda-modifiers
335    MetaLogEntry< std::map< unsigned char, double > > entry;
336    parseLambdaModifierMap( metaLogIstream, entry.lambdaModifiers );
337    if( !metaLogIstream.good( ) ) throw MetaLogParseException( );
338   
339    // Skip the ';'
340    if( ';' != metaLogIstream.get( ) ) throw MetaLogParseException( );
341    if( !metaLogIstream.good( ) ) throw MetaLogParseException( );
342   
343    // Parse the bitrates
344    parseBitrateVector( metaLogIstream, entry.bitrateVector );
345    if( metaLogIstream.fail( ) ) throw MetaLogParseException( );
346    metaLogEntryList.push_back( entry );
347   
348    if( !metaLogIstream.good( ) ) break;
349    if( metaLogIstream.get( ) != '\n' ) throw MetaLogParseException( );
350    metaLogIstream.peek( );
351  } while( metaLogIstream.good( ) );
352  if( metaLogEntryList.empty( ) ) throw MetaLogParseException( );  // The meta-log should not be empty
353 
354  // Initialize firstIndexVector and check that the sizes and indexes match
355  std::set< unsigned char > firstIndexSet( indexSetFromMap( metaLogEntryList.front( ).lambdaModifiers ) );
356  if( firstIndexSet.size( ) != targetVector.size( ) ) throw MismatchedIndexesException( );
357  for( std::list< MetaLogEntry< std::map< unsigned char, double > > >::const_iterator i( metaLogEntryList.begin( ) );
358      i != metaLogEntryList.end( );
359      ++i )
360  {
361    if( indexSetFromMap( i->lambdaModifiers ) != firstIndexSet ) throw MismatchedIndexesException( );
362    if( i->bitrateVector.size( ) != targetVector.size( ) ) throw MismatchedIndexesException( );
363  }
364 
365  // Initialize simplifiedMetaLogEntryList
366  std::list< MetaLogEntry< std::vector< double > > > simplifiedMetaLogEntryList;
367  for( std::list< MetaLogEntry< std::map< unsigned char, double > > >::const_iterator i( metaLogEntryList.begin( ) );
368      i != metaLogEntryList.end( );
369      ++i )
370  {
371    simplifiedMetaLogEntryList.push_back( MetaLogEntry< std::vector< double > >( ) );
372    for( std::map< unsigned char, double >::const_iterator j( i->lambdaModifiers.begin( ) ); j != i->lambdaModifiers.end( ); ++j )
373    {
374      simplifiedMetaLogEntryList.back( ).lambdaModifiers.push_back( j->second );
375    }
376    simplifiedMetaLogEntryList.back( ).bitrateVector = i->bitrateVector;
377  }
378 
379  // Run the calculations
380  std::vector< double > resultVector( guessLambdaModifiers( initialAdjustmentParameter, targetVector, simplifiedMetaLogEntryList ) );
381 
382  // Output the results
383  std::set< unsigned char >::const_iterator indexIter( firstIndexSet.begin( ) );
384  std::vector< double >::const_iterator resultIter( resultVector.begin( ) );
385  do
386  {
387    if( indexIter != firstIndexSet.begin( ) ) o << " ";
388    o << "-LM" << ( long )( *indexIter ) << " ";
389    o.setf( std::ostream::fixed, std::ostream::floatfield );
390    o.precision( 7 );
391    o << ( *resultIter );
392   
393    ++indexIter;
394    ++resultIter;
395  } while( indexIter != firstIndexSet.end( ) );
396  assert( resultIter == resultVector.end( ) );  // The index set and the result vector should be the same size
397}
Note: See TracBrowser for help on using the repository browser.