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

[Steven Johnson]

>   
>>>     return 0; // Must be equal.
>>> }
>>>
>>> int ff_ifr_optimise(AVFrame *cur, AVFrame *prev, AVFrame *remap, int width, int height)
>>> {
>>>       
>> very very messy
>>
>> concordance[256*256][2];
>> for all pixels
>>     concordance[256*prevpix + pixel][0]++;
>> for all x
>>     concordance[x][1]= x;
>>
>> sort concordance[2] elements per [0]
>>
>> for(x=0; x<256*256; x++){
>>     int match= concordance[x][1];
>>     int m0= match & 255;
>>     int m1= match >> 8;
>>     if(mapped[0][m0]>=0 || mapped[1][m1]>=0)
>>         continue;
>>     mapped[0][m0]= m1;
>>     mapped[1][m1]= m0;
>> }
>>
>> PS: the solution is of course not optimal but i see no obvious way how to
>> find the optimal solution in P time
>>     
>
> I never reviewed that code and I am not familiar with it, I would ask
> the author.
>
> Steve, could you comment on this?
>   
Yes, I can comment,

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. 

It appears that the solution proposed above does not take into 
consideration the iterative nature of the problem.

For Example,

Index 0 matches with index 5 1000 times.
Index 1 matches with index 5 900 times and index 7 800 times.

In this example, maximum concordance is achieved by saying that Index 0 
becomes index 5 in the next frame.  Were it not for that decision, we 
would have said that Index 1 should become index 5, but because index 0 
is now matched as index 5, we can not have 2 indexes from the previous 
frame match 1 index in the next, because presumably they should be 
different colours.  So, we need to find the next most matching for Index 
1, which is now index 7.  So the result would be:

Index 0 becomes index 5
Index 1 becomes index 7

If that makes any sense.  Obviously with 256 indexes that can match 256 
other indexes, the problem set is quite large, which is why I store the 
data like I do.  I tried to make the algorithm as simple as possible, 
and it is quite complex, so I busted it down into very distinct 
processing steps, and tried to add a fair amount of commenting to try 
and aid understandability.  It took a fair amount of time to come to 
this algorithm, as most of them I tried were no better than doing 
nothing.  The solution I came to is actually quite quick given the 
problem, it is just complex.  I disagree that it is messy, in fact I 
spent a lot of time making sure it was quite readable.  Or in this case 
does "messy" = "complex and hard to understand" because it is certainly 
"complex and hard to understand", but given the problem is itself 
"complex with no obvious solution", Is it really a problem?

Or is their some other problem I have failed to appreciate?

Steven J
> --
> Alex Beregszaszi
>
>
>
>