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

[Michael Niedermayer]

Hi

On Tue, Feb 27, 2007 at 11:42:47AM +0200, 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, 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)?

yes


> 
> 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 ...

[...]
-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Concerning the gods, I have no means of knowing whether they exist or not
or of what sort they may be, because of the obscurity of the subject, and
the brevity of human life -- Protagoras
-------------- 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/853ca967/attachment.pgp>