MaskTools 2.0a48

[Manao]

Hi,

As I said in the Avisynth 2.6 thread, I'm working on the MaskTools again. The code has been rewritten from scratch, mainly to make it easily portable to the upcoming Avisynth 3.0.

All inline asm has been ported to nasm. Some filters have disappeared. Some behaviors have changed. All named have changed, to allow you to use both MaskTools v1.5.8 and 2.0a.

Refers to the readme.txt to have a quick summary of the filters and what have changed since the 1.5.8.

This thread is here to collect bug reports and feature requests.

Here is the link to the new version : http://manao4.free.fr/masktools-v2.0a48.zip

Changes from alpha 47 to alpha 48 : * added : signed and unsigned binary shifts to LUTs, ceil/floor/trunc float -> int conversions. @ is now equivalent to °Changes from alpha 46 to alpha 47 : * added : signed and unsigned binary operators to LUTsChanges from alpha 45 to alpha 46 : * fixed : with mt_lutf, "std" mode wasn't working. Could also affect "std" with mt_luts and mt_lutsxChanges from alpha 44 to alpha 45 : * fixed : mt_clamp on sse2 platforms with resolution not multiple of 64
* added : mode parameter to mt_lutspa, to clean up biased/relative messChanges from alpha 43 to alpha 44 : * added : new very flexible mode to mt_luts and mt_lutsxChanges from alpha 42 to alpha 43 : * fixed : optimized versions of small horizontal resolutions with mt_edge, mt_xxpand and mt_xxflate
* fixed : avisynth 2.6 support (likely broken since avisynth 2.6 alpha 2 at least)
* added : hprewitt mode to mt_edge
* added : "biased" option to mt_lutspa
* optimized : prewitt and hprewitt mode for mt_edgeChanges from alpha 41 to alpha 42 : * added : specialized modes for mt_binarize
* added : specialized modes for mt_logicChanges from alpha 40 to alpha 41 : * (re)optimized : mt_edge with custom kernels and divisors that are a power of two</li>
* fixed : mt_edge with custom kernels (has always been broken in C, which became obvious once asm was removed)</li>
* fixed : no more crashes when an input clip isn't YUV planarChanges from alpha 37 to alpha 40 : * optimized : mt_xxpand vertical/horizontal/both modes are asmized
* optimized : mt_xxflate are asmized
* optimized : mt_motion with sse2
* potential fix : mt_merge with mod8 width
* potential : 64 bits build includedChanges from alpha 36 to alpha 37 : * fixed : mt_polish wasn't handling "z", "min", "max", "clip" and "round"
* added : mt_infix, which convert from polish to infix notation
* changed : built with MSVC 2008Changes from alpha 35 to alpha 36 : * fixed : "pi" wasn't properly defined for all lutsChanges from alpha 34 to alpha 35 : * added : mt_lutspaChanges from alpha 32 to alpha 34: * added : support for interleaved2planar hack, enabling 422 support
* changed : both avisynth 2.5 and 2.6 version are builtChange from alpha 31 to 32 * added : mt_lutxyz
* added : mt_lutsx
* fixed : small memory leak in mt_lutsChange from alpha 30 to alpha 31 * fixed : mt_hysteresis was randomly crashing.
* fixed : mt_polish is back.
* added : round, clip, min, max and = for lut.
* adapted : to msvc8 / yasm.Change from alpha 29 to alpha 30 * fixed : luts was crashing if some pixels didn't have any neighbours in the pixels list.
* added : mt_freerectangle, mt_freeellipse and mt_freelosange helpers.Change from alpha 28 to alpha 29 * fixed : intern float to integer conversion that were badly rounding negative
number. That resulted in -1.0 been rounded into 0 (!). Most notably affected was
mt_convolution. Thanks redfordxx for pointing that out.
Change from alpha 27 to alpha 28 * fixed : asm optimizations for mt_inpand/mt_expand/mt_edge ( mostly )Changed from alpha 26 to alpha 27 : * fixed : mt_binarize asm optimizations that borked with some thresholdsChanged from alpha 25 to alpha 26 : * fixed : avs closing issueChanged from alpha 24 to alpha 25 : * added : new html documentation.
* fixed : wrong frame issue.
* fixed : mt_merge with luma=true.Changed from alpha 23 to alpha 24 : * fixed : issues with MT.dll ( thanks tsp, Boulder, vanessam and all those who suffered the bug )
* fixed : check for YV12 colorspace, and report an error if it isn't ( thanks Boulder )
* speed up : median mode for luts ( once again, thanks to tsp )Changelog from alpha 22 to alpha 23: * fix & speed up : median mode, thanks to tsp's insightful remarks. Note to self : think
less like a mathematician, and more like a programmer. Simpler, faster & not bugged.Changelog from alpha 21 to alpha 22 : * added : "med"/"median" mode to luts/lutf
* changed : luts doesn't necessarily consider the center pixel
* changed back : forms helpers prepends (0, 0).
* changed : forms helpers now have a bool "zero" parameter, defaulted to true
* added : bool "luma" parameter to mt_merge, which makes it use the luma mask for
all three planes, and which forces chroma modes to "process" ( u=v=3 )Changelog from alpha 20 to alpha 21 * fixed : some filters were requesting wrong frames, thus creating ghostsChangelog from alpha 19 to alpha 20 : * bugfix releaseChangelog from alpha 18 to alpha 19 : * code refactoring
* fixed : bug with asm and width lower than 64
* fixed : doesn't prepend (0, 0) pixel to the forms helpers
* added : "min/max" mode to mt_edge. The edge value is local max - local min ( taken on a
3x3 square ).
* added : mt_lutf : a frame lut
* added : mt_luts : a spatial lutChangelog from alpha 17 to alpha 18 : * added : mt_makediff, mt_adddiff, mt_average and mt_clamp, ported from mg262's
limitedsupport plugin. The asm code is his, though it has been ported to nasm. They
respectively amount to MakeDiff, AddDiff, SimpleAverage and Clamp.
* added : mt_edge : "prewitt" kernel, taken from mg262's Prewitt filter. Unlike mg262's filter,
there's no multiplier ( it's always 1 ), but mt_edge's thresholds still apply. Results,
and speed, are identical except for the borders, which are now filtered.
* added : "chroma" parameter, taken from mg262's excellent idea. It's a string that,
if used, overrides U and V values. It can be either "process", "copy", "copy first",
"copy second" or a number. "copy" and "copy second" work alike.
* added : vmToon-0.74, adapted to masktools 2.0.
* added : LimitedSharpenFaster, with LimitedSupport functions imported into the masktools.Changelog from alpha 16 to alpha 17 : * changed : behavior of mt_edge with a custom kernel : the automatic normalization factor
is now the sum of the absolute value of the coefficients, ceiled to the next power of two
if that power is <= 128 ( else, it isn't ceiled ).
* added : cartoon mode for mt_edge
* added : modified mfToon script, for masktools v2. mfToonLite's speed goes from 30 fps
to 70 fps, mfToon from 4.5 to 6.5.Changelog from alpha 15 to alpha 16 : * fixed : some asm code used in invert, binarize and memset to a particular value.
Bug made the first 8 pixels of the picture to be incorrect. Also, avoid another nasty issue
that arise when cropping ( not my fault this time, though ).Changelog from alpha 14 to alpha 15 : * fixed : bugs from inflate & deflate ( thx you know you )
* reversed : inflate and deflate now match their masktools' v1 counterparts' behavior.
( if anybody used the new buggy one, let him speak quickly )Changelog from alpha 13 to alpha 14 : * fixed : random crashes with some width and asm functions ( thx Didee )Changelog from alpha 12 to alpha 13 * fixed : mt_merge order swapped for mask operation ( no comment... )Changelog from alpha 11 to alpha 12 * fixed : bug with some width ( mod4 ) for the non processing mode ( != 1 or 3 )
* changed : mt_merge order swapped for mask operationChangelog from alpha 10 to alpha 11 * fixed : mt_convolution's multiple instanciation bugChangelog from alpha 9 to alpha 10 * fixed : offY was always set to offX
* fixed : offsets quirk
* fixed : mt_convolution was crashing with floats
* changed : luts' equal operator is now equivalent to abs(x - y) < 0.000001
* added : bool saturate(true) parameter to mt_convolution
* added : float total(1.0) parameter to mt_convolutionChangelog from alpha 8 to alpha 9 * fixed : mt_lut, mt_lutxy : even faster loading
* fixed : mt_convolution : negative coefficients were offseted by 1
* fixed : mt_convolution : division by zero if the sum of the coefficients was 0.Changelog from alpha 7 to alpha 8 : * fixed : mt_edge in custom mode wasn't working properly
* fixed : mt_edge in custom mode, optimized wasn't working properly either
* fixed : mt_lutxy was slow to load, it's better nowChangelog from alpha 6 to alpha 7 : * fixed : forgot to add functions to the parser. Thanks Didee for pointing that outChangelog from alpha 5 to alpha 6 * fixed : mt_polish ( sin(x+y) wasn't properly converted, while sin((x+y)) was)Changelog from alpha 4 to alpha 5 * added : helpers for creating string for inpand / expand custom modes :
- mt_circle
- mt_square
- mt_diamond
- mt_ellipse
- mt_rectangle
- mt_losange
* added : helper for lut : consersion from infix to reverse polish notation :
- mt_polishChangelog from alpha 3 to alpha 4 * Added : custom modes for inpand / expandChangelog from alpha 2 to alpha 3 : * Fixed : mt_invert, mt_binarize, mt_lutxy, which weren't working properly anymore
* Fixed : offset created by incorrect rounding in mt_convolution
* Fixed : mmx version of edges filters ( soft thresholding, and roberts )
* Fixed : mmx version of motion edge ( soft thresholding )
* added : mt_mappedblurChangelog from alpha 1 to alpha 2 : * added functions to luts : sin, abs, cos, tan, exp, log, acos, atan, asin
* added "vertical", "horizontal" and "both" mode to mt_inpand / mt_expand
* added mt_convolution
* fixed mt_merge behavior for y, u, v = 2.
* added y, u, v = 4, for masked merge : copy the second clip channel. It's worth for any two clips input filters.
* internal changes ( code reorganization )Edit : url updated

[Mug Funky]

w00t! just d/l'd and i'll check it out ASAP.

[unskinnyboy]

Awesome! On it!

[unskinnyboy]

@Manao: This version doesn't seem to work with LimitedSharpen. I get this:

http://img394.imageshack.us/img394/5486/masktoolserror0gg.jpg

Usually this error comes when the MaskTools are not updated (?). But here, is it because of the change in Luts? How do I get this to work with LimitedSharpen now? :(

P.S: I hope I posted in the right place.

[scharfis_brain]

Uhm, read Manaos 1st post more carefully.
Read the readme of Masktools 2.0a

[Didée]

unskinnyboy - read the txt in the package, it cannot work out-of-the-box. All filter names have changed, so you'd have to edit all calls to MaskTools' filters in LS by yourself.

Manao: --> :) <--
I've prepared a small feature suggestion regarding in|expand, but right now it's out of reach, on the other machine ... will post it probably on Tuesday. Basically, it's about the possibility of splitting them into horizontal/vertical operation only. Hopefully this not too extravagant. ;)

[unskinnyboy]

Ah ok. As I thought..wanted to confirm nonetheless..:|

@Didée, Will you be rewriting LS for this version of MaskTools? :)

[AVIL]

Hi,

I've read the readme.txt file with the filters included in the new release. YV12Convolution is not ported to this new tools. I use it, and think is useful because his generality.

I tink also it could be useful a thresholded blur. A filter much like mt_inpand/mt_expand but averaging only those pixels with a value near at the center's value by, at most, a parametred threshold. The rest of the pixels will be discarded for the averaging. It can be parametred also the behaviour of the filter in the case when none neighbour went into average. By example replacing center by 0 or not touching center's value.

Anyway, that's tools are unvaluable. Thanks.

[Manao]

Indeed, YV12Convolution hasn't yet been ported. It'll be, soon I guess.

For the thresholded blur, I can do it, but it already exists. The beavior you're describing looks a lot like deen(a2d / w2d / c2d) behavior, and I don't want to reinvent the wheel ( especially when the existing wheel is fast )

[AVIL]

Hi,

My goal with the thresholded blur is making "edge aware" averaging. All the pixels very different to the center's one (possible edge) are completely discarded (not zeroed) from the average. For my purpose the center must be excluded also.

Convolution3D and (I suppose) Deen don't discard pixels, limit it to the threshold instead. And process the center also. The result is different, mostly if the center is very different from neighbours (isolated dots).

[Manao]

Ok, in that case, I'll see what I can do.

[Didée]

Quickly - -

AVIL: The idea of edge-aware averaging is certainly good, but surely it is more complex ... there arise *many* questions of what to do, what not, and why and how ...
Probably it would be a good idea to make up a separate thread for that. For sure I would participate if you make one ;)

>> Convolution3D and (I suppose) Deen don't discard pixels, limit it to the threshold instead

No. I'm pretty sure (for C3D: absolutely) that pixels within <thresh> contribute to the avaraging, and pixels outside of <thresh> do not. They are not "include-everything-and-limit-the-result" filters.
This' for both filters, and ...

>> And process the center also

both treat <thresh> based on the center pixel, of course. Deen, however, has the possibility to reduce <thresh> as pixels go farther away from the center.


Manao: What I already have thought about is, perhaps, a filter that works similar to the new edgemask-thresholding you did introduce: A kind of blur filter where, for every pixel, the thresholds of what-to-include are given by either one additional clip (thresh radius is specified by this clip) or two additional clips (by which absolute upper & lower thresholds are specified).
This would rise possibilities like selfmade edge-aware blurring (or sharpening), selfmade bilateral filtering, and probably some more I currently can't think of.

However, this definetly should be a separate filter, not part of the MaskTools, IMO.

[AVIL]

@Didée

I'm trying to denoise a video with two copies. Instead of make a mix with overlay, I choose from every copy the pixel who best match an ideal value. I calculate this value averaging the neighbourgs. But the edges (and spurious pixels) distort the prediction. So I wish ignore them.

My information about C3D comes from :

Tutorial about C3D (http://avisynth.unite-video.com/plugins/Convolution3D.htm)

This page states that the surrounding pixels are used always, but with a value adequate to the threshold. And by comparating C3D with average procedure make by scripting with mvtools I agree with the author of the page.

Anyway thanks for your offer.

[Didée]

No.

x1=blankclip(color=$666666,width=640,height=240).converttoyv12()
x2=blankclip(color=$AAAAAA,width=640,height=240).converttoyv12()
before=interleave(x1,x2).assumefieldbased.weave()
after=before.convolution3d(1,16,16,16,16,3,0)
interleave(before,after)
There is zero change. Period. Now try the same with Deen.

Please inform that page's author that he is spreading misinformation. (The page won't even load for me...)


edit (to Manao below): That's unfair, I had no chance to read that page ;)

[Manao]

Actually, the page is correct, but both of you misanderstood it ( I cheated, I'm french :p ) : it says that all value above the threshold are replaced by the center pixel's value. So in Didee'd sample test, nothing is changed.

[AVIL]

@Didée

I apologize for give a link in french. Actually, I work in a french multinational enterprise ("chez Renault") and don't mind that not everybody can read french pages.

@ all

Anyway, I'd prefer not to process the central pixel because it can be spurious. In this case, no neighbourg can be selected, and the adecuate value for my purposes is more difficult to state. Perhaps the average value of the neighbours or the median value (more edge-aware). Actually, I have resolved the process with scripting but involves 8 or 9 convolutions (fast due to yv12convolution) to separate every neighbourg in a different clip and average it with kassandro's corrector filter (for thresholded average). It works but is slow.

Bye

[Manao]

Convolution is coming tonight, hopefully. But i never considered yv12convolution to be fast ( no mmx code ).

[AVIL]

@Manao

Thanks for your quick response. I'd say yv12convolution is fast because the comparation with the alternative (generalconvolution) that involves colourspace conversion (RGB32 only).

[Didée]

AVIL - the problem wasn't the page in french, but rather the "page not found" I was getting. >today< it loads for me, but too late ...


Manao -

>> i never considered yv12convolution to be fast ( no mmx code )

Ah. Would this answer your own wondering, time back, why I'm often using DEdgeMask where YV12Convolution would be the obvious filter? :)


Okay ... here my little suggestion for inpand and expand:

As noted, it would be nice to have the possibility to in/expand only horizontally, or only vertically. When working e.g. with comb masks, or horizontal-only/vertical-only edgemasks, the advantages are obvious.

Plus there's one thing more behind it. When internal code for one-dimensional in/expanding is available, then an additional operation could be implemented: a merging of [normal expand] + [horizontal+vertical expand].
Why? to get "round corner" expanding. Currently, a chain of 10*expand() will turn e.g. a point into a 21*21 square. With "round corner" expanding, one would get a circle of diameter 21. There are cases where this would be desireable, because the "distance" of the filtering is of equal length in all directions, then. For simple expanding, there is a distance deviation of sqrt(2) - - too long in diagonal direction.

For the case of expand, I put together a scripted variant ... of course its pretty slow, but hey, it deals for visualization only.
function expand2(clip clp, int "direction", int "Y", int "U", int "V")
{
direction = default(direction, 3)
Y = default(Y,3)
U = default(U,1)
V = default(V,1)

direction==0 ? clp.expand(Y=Y,U=U,V=V)
\ : direction==1 ? clp.expand_H(Y=Y,U=U,V=V)
\ : direction==2 ? clp.expand_V(Y=Y,U=U,V=V)
\ : direction==3 ? logic( clp.expand_H(Y=Y,U=U,V=V),
\ clp.expand_V(Y=Y,U=U,V=V),
\ "max",Y=Y,U=U,V=V)
\ : direction==4 ? yv12lutxy( clp.expand(Y=Y,U=U,V=V),
\ logic( clp.expand_H(Y=Y,U=U,V=V),
\ clp.expand_V(Y=Y,U=U,V=V),
\ "max",Y=Y,U=U,V=V),
\ "x 71 * y 100 * + 171 /",Y=Y,U=U,V=V)
\ : clp.subtitle("illegal direction :p")
}
function expand_H(clip clp, int "Y", int "U", int "V")
{
Y = default(Y,3)
U = default(U,1)
V = default(V,1)
logic( clp, logic( clp.yv12convolution("1 0 0","1",Y=Y,U=U,V=V),
\ clp.yv12convolution("0 0 1","1",Y=Y,U=U,V=V),
\ "max",Y=Y,U=U,V=V),
\ "max",Y=Y,U=U,V=V)
}
function expand_V(clip clp, int "Y", int "U", int "V")
{
Y = default(Y,3)
U = default(U,1)
V = default(V,1)
logic( clp, logic(clp.yv12convolution("1","1 0 0",Y=Y,U=U,V=V),
\ clp.yv12convolution("1","0 0 1",Y=Y,U=U,V=V),
\ "max",Y=Y,U=U,V=V),
\ "max",Y=Y,U=U,V=V)
}
Procedure:

expand2(direction=0) --> normal expand()

expand2(direction=1) --> horizontal-only expand()

expand2(direction=2) --> vertical-only expand()

expand2(direction=3) --> horizontal+vertical expand() ("triangular" effect when chaining several instances)

expand2(direction=4) --> "round corner" expand()


I think this would be sensible to implement ... in one form or the other, not necessarily the way I did above. Are there any hurdles I don't see?

[Manao]

Didee : OK, so basically, you want the following kernels for inpand / expand :
1 1 111
111 1 111 111
1 1 111
That will be easy to add.

[Didée]

If the plugin will run faster than above function by the same percentage as your post was shorter than mine, then it's OK :D

Oh, the longer part was about the 1 2 1 3 4 3
2 2 2 4 4 4
1 2 1 3 4 3 left kernel, or more exactly the right one. First one would be sufficient (and faster), me thinks.

[Manao]

Changes from alpha 1 to alpha 2 :

* added functions to luts : sin, abs, cos, tan, exp, log, acos, atan, asin
* added "vertical", "horizontal" and "both" mode to mt_inpand / mt_expand
* added mt_convolution
* fixed mt_merge behavior for y, u, v = 2.
* added y, u, v = 4, for mt_merge : copy the second clip channel. It's usable for any two clips input filters.
* internal changes ( code reorganization )You will find it here (http://manao4.free.fr/masktools-v2.0a2.zip)

Didee : weights for morphologic operators won't be implemented ( it would complicate to much the filter, and the speed gain in comparison to other means wouldn't be worth the complication ).

[kassandro]

Okay ... here my little suggestion for inpand and expand:

As noted, it would be nice to have the possibility to in/expand only horizontally, or only vertically. When working e.g. with comb masks, or horizontal-only/vertical-only edgemasks, the advantages are obvious.

Plus there's one thing more behind it. When internal code for one-dimensional in/expanding is available, then an additional operation could be implemented: a merging of [normal expand] + [horizontal+vertical expand].
Why? to get "round corner" expanding. Currently, a chain of 10*expand() will turn e.g. a point into a 21*21 square. With "round corner" expanding, one would get a circle of diameter 21. There are cases where this would be desireable, because the "distance" of the filtering is of equal length in all directions, then. For simple expanding, there is a distance deviation of sqrt(2) - - too long in diagonal direction.

The following filters can be implemented:

ShapeMax(clip input, string "Yshape", string "Ushape", string "Vshape")
ShapeMin(clip input, string "Yshape", string "Ushape", string "Vshape")
ShapeAverage(clip input, string "Yshape", string "Ushape", string "Vshape")

Here Yshape is a string containing pairs of numbers describing a shape. This shape is then translated from (0,0) to any point in the frame, then for each point the maximum over the translated shape is taken to calculate the pixel values of ShapeMax. ShapeMin and ShapeAverage are similar. Of course, for pixels near the boundary not all points of the translated shift are inside the frame. Execution time increases linearily with the number of points of the shape.
While shape strings can be written by hand, it is convenient to have generating function for such strings. It is easy to implement functions like

Circle(R)

which returns a shape string for a circle with radius R.

[Mug Funky]

oooh, that looks interesting. i spy a bokeh-blur filter coming :)

[Manao]

New version up : Alpha 3 (http://manao4.free.fr/masktools-v2.0a3.zip)

Changelog : * Fixed : mt_invert, mt_binarize, mt_lutxy, which weren't working properly anymore
* Fixed : offset created by incorrect rounding in mt_convolution
* Fixed : mmx version of edges filters ( soft thresholding, and roberts )
* Fixed : mmx version of motion edge ( soft thresholding )
* added : mt_mappedblurAs you can see, lots of fixing. My bad...

[tsp]

what about adding support for infix expressions instead of only the reverse polish notation?

[mg262]

An alternative is to allow a 256-sized (or 65536-sized) array stuffed inside a AVSValue as an argument... then people could define functions which operated on such arguments to produce new arrays, and you would have the infix "for free".

(I don't particularly want this method... I'm just throwing it in as an idea.)

[Manao]

what about adding support for infix expressions instead of only the reverse polish notation?Make the parser and the expression builder, i'll include it. But i'll keep using reverse polonese, i don't like parenthesis that much :)

mg262 : would work, if somebody can overload operators in avisynth script parser, which can't be done without hacking avisynth itself. So won't work. But I liked the idea.

Tomorrow morning : custom 'matrices' for inpand / expand.

[kassandro]

Make the parser and the expression builder, i'll include it. But i'll keep using reverse polonese, i don't like parenthesis that much :)

Avisynth has already a C like expression parser (with brackets, of course). Thus, if YV12LUTxy is incorporated into the Avisynth core, then we could use this expression parser to fill the LUTs. Then I could become a lutmaniac as well. The inverse polish notation really drives me nuts.

[tsp]

Make the parser and the expression builder, i'll include it. But i'll keep using reverse polonese, i don't like parenthesis that much :)

Sure I will do that. BTW is your favorit calculator a Hewlett Packard :p

[mg262]

This is a very quick way to build a parser:

http://www.boost.org/libs/spirit/doc/introduction.html

[Manao]

Alpha 4 (http://manao4.free.fr/masktools-v2.0a4.zip)

Changelog ( short ) * added : custom modes for inpand / expandEdit : boost is great, but I did write my reverse polonese 'parser' faster than I failed my attempt to compile spirit. And i don't even want to think at the time the project will take to compile if i use spirit as a parser.

[Didée]

Friends, christmas is very early this year :) - Very nice stuff. Everything is highly appreciated.

Oh, and I definetly vote for keeping reverse polish notation for the expressions. Working with them IMO is really easy ... and honestly said: a regular expression with 8 nested levels of parantheses, written "in one line", might give way more headaches than reverse polish ... ;)

[Manao]

What i'll do once i manage to compile spirit, or if somebody gives me a parser, is to make a filter that converts infix notation to polonese one. So you'll use mt_lut like that : mt_lut(yexpr = ConvertToPolonese("expr"))

[Leak]

polonese
You keep using this word... are you sure it means what you think it means? ;)

Polonese (http://images.google.at/images?q=polonese&btnG=x) vs. RPN (http://en.wikipedia.org/wiki/Reverse_Polish_notation)

*grins, ducks & runs* :D

[Mug Funky]

how about "polish remover"... hehe.

i sorta like inverse-polish too. when you get the hang of it it's quite easy (i never used a hp calculator btw, but they look cool).

[kassandro]

While it is easy to write parsers with postfix notation, Polish notation is against the human brain. Nobody would use Avisynth with scripts like this

16 8 -8 -32 align true = crop

A prefix parser would have been almost as easy to implement, but much more brain friendly. On the other hand infix is really the way to go.
In the early eighties FORTH was regarded as the programming language of the future. It did use postfix notation and never ever a serious application was developed with it. It didn't wonder me at all.

[tsp]

Kassandro good to see that I'm not the only one who thinks postfix notation is not the most readable format for humans.

Manao here is a small function you can include in masktools for the infix to postfix conversion:

// ConvertToPostfix Copyright 2005 Tonny Petersen

// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA, or visit
// http://www.gnu.org/copyleft/gpl.html .

#include "avisynth.h"
#include <string>
#include <sstream>
#include <stack>

using namespace std;

AVSValue __cdecl ConvertToPostfix(AVSValue args, void* user_data, IScriptEnvironment* env)
{
const string numerics("0123456789xy");
string input = args[0].AsString();
string temp;
stringstream output;
stack<string> stringstack;
int pos=0;
int lastpos=pos;
int poplast=0;
while(string::npos!=(pos=input.find_first_of(' ',lastpos))){
temp = input.substr(lastpos,pos-lastpos);
lastpos=pos+1;
//find right parenthesis
while(string::npos !=(pos=temp.find(')'))){
poplast++;
temp.erase(pos,1);
}
//delete spaces and left paranthesis
while(string::npos !=(pos=temp.find_first_of("( "))){
temp.erase(pos,1);
}

//if number output it
if(string::npos != (numerics.find_first_of(temp)) )
{
if(string::npos != temp.find_first_of("xy")&&temp.length()>1)
stringstack.push(temp);
else
{
output<<temp<<" ";
}
}
//else push it
else
stringstack.push(temp);
//pop from stack
while(poplast)
{
poplast--;
output<<stringstack.top()<<" ";
stringstack.pop();
}
}

temp = input.substr(lastpos,input.length()-lastpos);
//find right parenthesis
while(string::npos !=(pos=temp.find(')'))){
poplast++;
temp.erase(pos,1);
}
//delete spaces and left paranthesis
while(string::npos !=(pos=temp.find_first_of("( "))){
temp.erase(pos,1);
}

//if number output it
if(string::npos != (numerics.find_first_of(temp)) )
{
if(string::npos != temp.find_first_of("xy")&&temp.length()>1)
stringstack.push(temp);
else
{
output<<temp;
if(stringstack.size()>0)
output<<" ";
}
}
//else push it
else
stringstack.push(temp);
//pop all operators from stack
while(stringstack.size())
{
poplast--;
output<<stringstack.top();
if(stringstack.size()>1)
output<<" ";
stringstack.pop();
}
input=output.str();
return env->SaveString(input.c_str(),input.length());
}

extern "C" __declspec(dllexport) const char* __stdcall AvisynthPluginInit2(IScriptEnvironment* env) {
env->AddFunction("ConvertToPostfix","s", ConvertToPostfix, 0);
return 0;
}

[mg262]

@tsp,

Can I ask how the function deals with precedence?

[tsp]

It don't manao's parser handles that. It just converts the infix expression to a postfix expression. If that was what you meant. Ie
Contverttopostfix("20 + 1 * 10") returns "20 1 10 * +" and it's mf_lut's responsebility to get the right result out of it. Also before each number/x/y there most be a space (except the first character in the string) so "sin( 2 *( 29 + 5)) is okay but "sin(2 *(29 + 5))" is not.

[Manao]

tsp : thanks for the parser. But do you support ternary operators ( ? : ) ?I don't know how manao's parser handles thatWell, except for ? :, every operators are commutative. a b c ? is translated as a ? b : c.

[Manao]

BTW, what is infix ? It doesn't take operator's priority into account, does it ? Because if so, your parser doesn't work ( 3 * 4 + 8 * 8 returns 3 4 8 8 * + * which is ((8 * 8) + 4) * 3 ).

[tsp]

hmm your are right. Current the expressions is just evaluated from left to right so you have to set the parathesis the right place. I will fix that and also add support for the a?b:c notation currently it just works like a?b c -> a b c? so I only need to add support for the : . So any suggestions about the presedens. Maybe the same as c++ but does that means that ^ sin,cos,abs,log,exp etc. gets the same precedens before the / * or should maybe ^ have the highest precedens?

[mg262]

I would have said:

unary functions
^
* /
+ -

With unary functions you would almost always expect to put brackets after them if they take a compound argument, i.e. sin(4*x), and the above reflects this behaviour.

[tsp]

ok for some strange reason my calculator (a Texas Instrument 86) gives ^ the highest precedens

[Manao]

Ok, finally, I managed to work with spirit. I must aknowledge it's great, though it takes times to compile. Anyway, here is the new build : alpha 5 (http://manao4.free.fr/masktools-v2.0a5.zip)

Changelog : * added : helpers for creating string for inpand / expand custom modes :
- mt_circle
- mt_square
- mt_diamond
- mt_ellipse
- mt_rectangle
- mt_losange
* added : helper for lut : consersion from infix to reverse polish notation :
- mt_polish

[mg262]

Great! Is a losange the same as the diamond but with width and height allowed to differ?

(Not that it's really relevant but I think the English equivalent is lozenge ... it's not a word that is used very often.)

[Manao]

Yep, it is. I wouldn't have thought it would be spelled differently, since it's originally a french word. But that way, it sounds almost alike.

[tsp]

ok now it should work correct allthough I am not entirely sure how a? b+c:d+e is translated correct. I don't think it is possible to translate it correct without using the :

here is the code:

// ConvertTofix.cpp : Defines the entry point for the DLL application.
//

// ConvertToPostfix Copyright 2005 Tonny Petersen

// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA, or visit
// http://www.gnu.org/copyleft/gpl.html .

#include "windows.h"
#include <string>
#include <algorithm>
#include <stack>
#include "avisynth.h"

using namespace std;

class Operator{
string _op;
int _precedens;
public:
Operator(string _operator,int precedens):_op(_operator),_precedens(precedens){};
bool operator==(const string& s) const{return s==_op;}
bool operator>=(const Operator& o) const{return _precedens>=o._precedens;}
operator string(){return _op;}
};

AVSValue __cdecl ConvertToPostFix(AVSValue args, void* user_data, IScriptEnvironment* env)
{
const string numerics("0123456789,.()");
const unsigned int NumberOfOperators=28;
Operator o[NumberOfOperators]={Operator("+",50),Operator("-",50), Operator("/",60), Operator("*",60), Operator("^",70), Operator("%",60) , Operator("&",30), Operator("|",30), Operator("°",30), Operator("!&",40),Operator("<",40), Operator("<=",40), Operator(">",40), Operator(">=",40), Operator("=",40), Operator("!=",40),
Operator("cos",80), Operator("sin",80), Operator("tan",80), Operator("acos",80), Operator("asin",80), Operator("atan",80), Operator("exp",80), Operator("log",80), Operator("abs",80), Operator("?",10),Operator(":",11),Operator("ENDOFLIST",-10)};//the last operator is a dummy operator to signal the end of the list. Also the first 2 characters of an Operator must be unique

string input = args[0].AsString();
transform (input.begin(),input.end(), input.begin(), tolower);
int pos=0;
while(string::npos !=(pos=input.find(' '))){
input.erase(pos,1);
}
string temp("");
string output;
stack<Operator> operatorstack;
for(unsigned int i=0;i<input.length();i++)
{
if(string::npos == numerics.find_first_of(input[i])&&!((input[i]=='x'||input[i]=='y')&&temp==""))
{
temp+=input[i];
Operator* result;
if((result = find(o,o+NumberOfOperators-1,temp))!=(o+NumberOfOperators-1)&&(find(o,o+NumberOfOperators-1,temp+input[i+1])==(o+NumberOfOperators-1))){
if(output.length()&&output[output.length()-1]!=' ')
output+=" ";
if(operatorstack.size()==0)
operatorstack.push(*result);
else
{
while(operatorstack.size()&&operatorstack.top()>=*result)
{
if(!(operatorstack.top()==":")){
output+=operatorstack.top();
output+=" ";
}
operatorstack.pop();
}
operatorstack.push(*result);
}
temp="";
}
}
else if(input[i]=='(')
operatorstack.push(Operator("(",-100));
else if(input[i]==')')
{
if(output.length()&&output[output.length()-1]!=' ')
output+=" ";
while(operatorstack.size()&&!(operatorstack.top()=="("))
{
output+=operatorstack.top();
output+=" ";
operatorstack.pop();
}
if(operatorstack.top()=="(")
operatorstack.pop();
}
else
output+=input[i];

}
if(operatorstack.size()&&output[output.length()-1]!=' ')
output+=" ";
while(operatorstack.size())
{
if(!(operatorstack.top()==":")){
output+=operatorstack.top();
if(operatorstack.size()>1)
output+=" ";
}
operatorstack.pop();
}
return env->SaveString(output.c_str(),output.length());
}

extern "C" __declspec(dllexport) const char* __stdcall AvisynthPluginInit2(IScriptEnvironment* env) {
env->AddFunction("ConvertToPostFix","s", ConvertToPostFix, 0);
return 0;
}

and you don't need spaces in this version so 2*3+4*5+(6*(7+8)) is okay. Even expx is okay = exp(x)
[EDIT]
small change to the code. Should now recognise <= and >= also convert the input string to lowercase so case doesn't matter. Should parse ugly string like "E X p 23> =sIny* expX" correct

[tsp]

Get ConvertToPostfix here (http://www.tsp.person.dk/ConvertToPostfix.zip) if you want to try: