Video Codec Optimization with Genetic Programming Methods

Conceptually video codec can be considered as a function of N arguments (parameters), e.g. x265 encoder command line can be represented as:  x265(me_range, me_method, aq_mode, …). Some parameters are binary (e.g. weightp = on/off), other take a range of values (e.g. me_method=hex, dia, tesa).  The purpose of Evolutionary Programming methods is to optimize encoder parameters on a given set of video sequences, for details pls. read

 

Evolutionary-and-Genetics-methods-in-Video-Coding-Optimization

Typical SW encoder has above 40 mutable parameters, the lion’s share parameters are on/off, i.e. binary parameters.

The number of various configurations exceeds 2^40, this magnitude is similar to the amount of atoms in the Metagalaxy (see https://www.universetoday.com/36302/atoms-in-the-universe/). So, brute-force search for optimal configuration is impractical.

Due to dependencies among parameters we can’t apply gradient-descent methods, where optimization is conducted separately for each parameter, in such case we have to conduct ~40 iterations to get the best configuration.

To solve such kind of optimization three types of the blind optimization are listed below:

1) Egalitarian Evolutionary Method

2) Elitistic Evolutionary Method

3) Genetics Programming Method

 

In the first instance one should specify video sequences belonging to a specific content (gaming, desktop, live video etc.).  Then one needs to determine the fitness function, e.g.

              fitness = 0.5*Performance + 0.5*nPSNR,

here

Performance denotes a normalized (to the range [0..1]) encoding time

nPSNR denotes PSNR normalized to the range [0..1]

 

Termination conditions:

• High entropy threshold (or a measure of homogeneity of population). Pls. bear in mind if the population is nearly homogeneous Evolutionary/Genetics methods achieves a steady-state.
• Max. iterations

To switch on the evolution the initial population must be maximally non-homogeneous to avoid a rapid entrance to a steady state.

 

Note from Biology:

In Biology  the selection for mating is usually not linearly proportional to the delta fitness:  fitness  –  averageFitness .

In hominids groups an alpha male is commonly slightly better (from the evolution point) another males but he takes all females, i.e. “a winner takes all”.

Hence individuals which have fitness values higher the average should get much more chance for mating and those which are below of the average should be rarely chosen for mating.

A potential map from fitness to mating probability should be according to the following capitalistic motto: each rich member gets more richer and each poor individual gets more poor. A socialistic approach, i.e. a linear map from the fitness to the mating probability would not work.