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

[Steven Johnson]

Uoti Urpala wrote:
> On Tue, 2007-02-27 at 13:20 +1100, Steven Johnson wrote:
>   
>> Basically, I couldn't come up with a better algorithm to find maximum 
>> concordance between 2 Palletised Frames, such that the maximum 
>> difference could be encoded as palette data changes, rather than pixel 
>> data changes.  It is quite a complex task, even though at first blush 
>> the requirement seems quite simple.  I have not seen any encoder do this 
>> work (extract palette change info from frames rather than data provided 
>> by the authoring process), and there is no (that I could find), ready 
>> reference on doing such a thing. 
>>     
>
> Do I understand correctly that the problem is finding the permutation of
> palette indices for new picture that keeps the maximum number of pixels
> with the same palette index as the previous picture,
Yes that's the problem.
>  and which can be
> reduced to finding the permutation P which gives the maximum sum over i
> of M(i, P(i)) for a given matrix M? (in this case M(i, j) will be set to
> the number of pixels where palette entry i is used in prev frame and j
> next)?
>   
Presumably.
> 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 read that, didn't help me understand the Hungarian_algorithm much but
then again I ain't no mathematician either.
> The attached program is an example based on some old code of mine. It
> was written basically as a throwaway implementation but an optimized
> one. It should be reasonably fast; reading the matrix with scanf takes
> most of the time for dimensions well into the thousands. Most people
> will probably find it quite hard to understand.
>   
Code I can understand.  Taking what you posted on face value as an
optimal solution in palette_size^3 time, If I was to take your code and
modify it to replace the code I wrote, what sort of licence applies
(GPL, LGPL, some other?).  Most of the code would be the same, assuming
it works, with tweaks to get rid of global data, handle palettes, etc,
so your licence on this effects its usability.  Although I was less than
thrilled by the goto's.

One thing that isn't clear (to me).  What happens when there are no more
values to find, and is it possible to give the same index twice.

For Example:

3 Palette entries:

Old : New : Matches Count
0 : 10 : 9
0 : 11 : 8
1 : 10 : 10
1 : 11 : 7
Every other permutation matches 0 times.

Should give Indexes:
0 becomes 11
1 becomes 10
2..255 becomes 0..9,12..255

Would it, using this algorithm?
What index to index match does it pick for 2..255 matching 0..9,12..255,
as all permutations equal 0?


Steven J