[Ffmpeg-devel] [RFC] [PATCH] FLC/FLX/DTA encoder

[Steven Johnson]

Michael Niedermayer wrote:
> Hi
>
>   
>   
>> If so then the optimal answer can be found in about palette_size^3 time
>> (after M has been calculated) using the Hungarian algorithm
>> http://en.wikipedia.org/wiki/Hungarian_algorithm
>>     
>
> i didnt know this one, very interresting, though iam not sure if 256^3
> is ok in practice
> its also a question of complexity and how much better it is in practice
> it would definitly be interresting to compare it against the heuristic
> currently used and the one suggested by me ...
>
>   
Agreed. 

Matching indexes across frames is vital to getting good compression in a 
palletised format, so "for me" if it was a trade of speed vs size, I 
would go with size every time.  It is compression after all, which for 
this sort of image is usually not done in real time, so the extra time 
taken to get a better compressed result is worth it, "in my case".  
Other people have different needs and speed will be more important than 
size. Such is life :)

I will try and knock something up, so all 3 algorithms can be trailed to 
compare size of resulting remapped frames after compression, and speed.  
I will also test to see if My algorithm and Michael's do in fact produce 
the same result.  If they do, I will definitely drop mine, as there is 
less code in Michael's.

Steven J