[FFmpeg-devel] [PATCH 2/3] avfiltergraph: don't query formats if filter has uninitialized inputs

[Nicolas George]

Le quintidi 15 floréal, an CCXX, Michael Niedermayer a écrit :
> after merging formats
> each filters output could be choosen so as to maximize the similarity
> to its input and minimize loss of information.

That does not work with amerge. Lavfi has two models for the
interdependencies of formats for links:

- the links point to the same list of format, in the end they will have the
  same format;

- the links point to different lists, lavfi can choose the formats
  independently.

amerge does not fit these models: it accepts anything as input, but the
format for the output is entirely determined by the formats for the inputs,
with a non-trivial function.

The solution would probably be to re-call query_format during the graph
configuration to let it recompute the output format.

> iam not sure i interpret this code correctly but if so 
> that loop could take [quadratic] time i think.

I believe the complexity would be:

	total_number_of_filter × max_depth_of_dependencies

As currently, only amerge induces dependencies, max_depth_of_dependencies
should stay rather low.

>						 This could be avoided
> by changing "each filter" to limit itself to filters still needing
> to be configured and filters connected to changed filters

Unless I am mistaken, this could still have a quadratic worst case if the
filters are in reverse dependency order, it only lowers from N² to N²/2, but
with additional bookkeeping. Only a real topological sort algorithm would do
really better. But as I said, this worst case is probably very unlikely, so
it does not matter.

Regards,

-- 
  Nicolas George
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20120503/c74ebe1f/attachment.asc>