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

[Uoti Urpala]

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)?

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

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.

It finds the permutation giving the _minimum_ value. You want the
opposite in this case so if you want to test it with real palette values
use something like total_pixels-matching_pixels as matrix entries.

The input file syntax is dimensions on the first line, then the entries.
For example with the input

10
 77 36 15 67 74 13 57 37 96 70
 76 80 45 99 40 79 62 98 44 79
 41 24 60 60 63 53 32 74 79  9
 39 19 80 41 56 16 82 12 61 88
 75 52 10 54 35 69 71 35 35 30
 47  4 24  0 55 66 95 77 63 57
 28 13  3 32 25 95 11 58 51  5
 33 38 34  9 40 95 60 11 31 68
 28 28 74 63 36 69 85 82 80 62
 58  1 32 65 16 27 10 71 64 25

the output should be

Minimal result is: 155
Given by permutation 5 4 9 7 2 3 6 8 0 1

The permutation is given as the column to pick in each row, so the
minimum value is 155=13+40+9+12+10+0+11+31+28+1.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: test.c
Type: text/x-csrc
Size: 4208 bytes
Desc: not available
URL: <http://lists.mplayerhq.hu/pipermail/ffmpeg-devel/attachments/20070227/f43986e9/attachment.c>