[Ffmpeg-devel] [RFC] [PATCH] FLC/FLX/DTA encoder
Steven Johnson
mplayer
Tue Feb 27 03:20:21 CET 2007
>
>>> 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
>
>
>
>
More information about the ffmpeg-devel
mailing list