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

[Michael Niedermayer]

Hi

On Tue, Feb 27, 2007 at 01:20:21PM +1100, Steven Johnson wrote:
> 
> >  
> >>>    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

yes in the example my suggested algorithm will find the optimal solution
its even possible that my suggested algo id identical to yours just not
so obfuscated

[...]

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

No great genius has ever existed without some touch of madness. -- Aristotle
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20070228/edf82334/attachment.pgp>