[FFmpeg-devel] [PATCH] [2/??] [3/3] Filter graphs - Parser for a graph description

[Robert Swain]

Hello,

On 21 Mar 2008, at 13:44, vmrsss wrote:
> On 18 Mar 2008, at 22:18, Robert Swain wrote:
>> I like your syntax and prefer it to Vitor's.

I have since changed my mind about this, though they're clearly both  
capable syntaxes, explicit naming is much more comprehensible/ 
intuitive to me when routing the various pads between filters.

The thing I like about your notation for the simpler filters was that  
visualising the graph was easier for parallel branches of filter  
chains as the branches were maintained throughout the notation using  
*. However, visualising the graph from some of the feedback  
examples... I gave up. The other notation is vastly superior in such  
cases though I note that the permutations would help a lot and seem to  
reduce the differences between the two notations significantly.

I think explicit naming is easier for users because they don't have to  
think about the permutations required to obtain the correct ordering.  
Not all (or even many?) users will have the mathematical background or  
intuition to deal with such problems and the syntax shoud, in my  
opinion, be as accessible to all as possible. Especially for more  
complex filter graphs like the ones proposed by Michael highlighting  
the complexity of feedbacks.

>> The diagram for the second of the two examples might be clearer if it
>> were drawn as follows:
>>
>>      ---> filter1 ---> (abc)
>>              |
>>              v
>> (def) ---> filter2 --->
>>
>> I prefer this because the inputs are on the left and the outputs on
>> the right. Please note, however, that the output of filter1 to (abc)
>> would be filter1's second output looking at your diagram. The first
>> output of filter1 goes to filter2 in your diagram.
>
> Ok, let's assume that.
>
>> We have two input streams, the input of filter1 and (def). The inputs
>> of filter2 come from filter1 (or the first output of split in your
>> notation) and from (def). In what order are these fed into filter2?  
>> Is
>> the 'spare' input that isn't used by filter1 to be kept in a list of
>> remaining input possibilities and later used by the next filter that
>> doesn't have enough inputs coming from other filters in the chain?
>> What takes priority - the inputs from the chain or the initial inputs
>> to the graph? Is this just a case that really needs some named  
>> inputs?
>
> Probably the easiest way to look at this is to compose blocks F, G,
> H, ... where each of the blocks is build using * so as the number of
> inputs and outputs matches at each stage. The pairing is then
> straightforward: 1st output from a block is 1st input for the
> successive block, 2nd output from a block is 2nd input for the
> successive block, etc. For instance in the case above:
>
>    - start with F = filter1,split : 1 ---> 2 and G = filter2 : 2 --->
> 1;
> 	then the final filter is (F * nop) , (nop * G) : 2 ---> 2.
> 	This is because:
>
>    - the 2nd input (def) passes the first block untouched to be fed
> to G;
> 	you can do that by writing F*nop : 2 ---> 3
>
>    - now the 1st output of F passes the second block untouched to be
> 	output. you can write that as nop*G : 3 ---> 2.

Originally you wrote:

filter1->filter2
|         ^
v         |
(abc)     (def)

...gives...

filter1, split, (filter2 * nop)

Now you're writing (substituting filter1, split back in...):

(filter1, split) * nop, nop * filter2

Was the "* nop" in "F * nop" implicit? If so, I can accept this but,  
the second input to the graph would have been passed through the * nop  
and filter2 would have used both outputs from the split after filter1,  
which wasn't what was desired from the graph diagram. I think the  
filter2 * nop should have been nop * filter2 as you are now stating.  
This kind of confusion could probably have been avoided using explicit  
naming. :)

> If for instance you want the output from filter1 to be the 2nd (rather
> than the 1st) input to filter2 you could simply replace G by  G' =
> swap,filter2.

Indeed, swapping is simple, until you get to complex permutations but  
then it's reasonable to have some permutation syntax as you mentioned.

> For completeness, in the notation proposed later on by Michael to
> express (filter1, split)*nop , nop*filter2 you'd write something like:
>
> 	(x def)Filter =
> 		(x) filter1, split (k1 k2) , (k2 def) filter2
>
> but I think here you'd still need to clarify the order of Filter's
> outputs (does the first output of Filter comes from filter1 or from
> filter2?) or you'll soon be in trouble

I'm not so sure. As long as the parse direction is well-defined (left  
to right, right to left) the order of the outputs should be clear, at  
least in that example. Maybe more complex graphs would need explicit  
naming of outputs, but that wouldn't be a major issue for the coder of  
the filter, as you demonstrate below.

> so perhaps his proposal should
> be refined into something like
>
> 	(x def) Filter (o1 o2) =
> 		(x) filter1,split (o1 k) , (k def) filter2(o2)
>
> or perhaps
>
> 	Filter(x def) =
> 		let (o1 k) = ( filter1,split )(x)
> 			in let o2 = filter2(k def)
> 				in (o1 o2)
>
> Hope this helps.

It did. Thank you.

Rob