random generation of smooth irregular binary shapes

[NicolasRobidoux]

Yes. It is really that simple. Just make sure you use a fairly high quality (and large radius) Gaussian blur. With a fast and cheap approximation (using a sparse and low bit-depth LUT) there are artifacts because the thresholding is very permissive, and the blur radius large.

Sorry I am not following this. There would not seem to be a need for a lut approach to a gaussian blur as IM has functions -blur (separable) and -gaussian (2d) blurs already. Both have both radius and sigma, though really only sigma is needed.

This is where the comment comes from: In VIPS/NIP2, one can control how convolutions---this includes Gaussian blur---is done. I've found that if I use a low-bit LUT, I can see artifacts in the final shape: the boundary is not as smooth as it should be (when looked at with a "magnifier"). No such artifacts if I use a float LUT. I've not checked the internals of Gaussian blur in IM, so I issued the warning in case one has the option of goind "very cheap" in the convolution department.

Please explain what you mean by permissive in your context of thresholding. I presume you are thresholding the graylevels in the image after the blur so as to cut down the size of the blurred object and convert to binary. From your paper you mention 2% and 5%. This should be easy with -threshold, unless I misunderstand you technique.

Let's assume that the final shape will be black on white, and that we are not computing in reverse video. "Permissive" means that something that is almost white (within 2% of being white, for example) is still considered part of the shape, hence turned to black by the thresholding. "Restrictive" means that in order to be part of the shape, a pixel has to be very close to black before thresholding.

Things are somewhat confusing because theorists discuss shapes as if they were masks, that is, the shape is implicitly white on a black background. (This makes sense because "1", that is, white, corresponds to being part of the shape.) So, I tried to write the article so that what is written make sense no matter whether one is theorizing or computing. (Possibly, I failed.)

But it does look like you understand perfectly.

The hard part here seems to be your complicated formulae for ensuring random values for the coordinates. IM has a random function in -fx that allows random numbers to be generated within the range 0 to 1. I don't know how to convert those to uniform or gaussian distributions. You have some equations for involving sin, cos, log, etc (not numbered on page 3 (not numbered), which probably could be implemented in -fx. However, IM can generate both uniform and gaussian noise in an image and one can take a series of pixels from that image and get the values to use for the coordinates. But I don't know how accurate these distributions are within IM. So precision/accuracy may be an issue.

Fred

As far as generating seed point locations go, accuracy is not an issue at all. Any uniform distribution on [0,1] can be used and fed into the formulas to get points uniformly distributed in the unit disk (this is the formula with a cosine and a sine), then scaled by the "inner" canvas size. Provided the noise has the proper distribution, it should be just fine. To get a binormally distributed sequence of seed points, you probably can simply scale the Gaussian noise instead of using the formula based on the Box-Muller formula.

Note that although the Gaussian distribution gives more "natural" looking shapes, I find the two uniform distributions more "artistic," especially with few seed points.

[fmw42]

Any uniform distribution on [0,1] can be used and fed into the formulas to get points uniformly distributed in the unit disk (this is the formula with a cosine and a sine), then scaled by the "inner" canvas size.

As I said IM produces random numbers in the range [0,1]. But I don't know if that is uniform, but simply random. If that random set of numbers is fed to your sine and cosine formulae, then does that makes it uniform?

Alternately, IM can generate an image, say 1x32 with either Uniform or Gaussian distributed noise. I can take each odd pixel's value and make that the x coordinate and each even pixel's value and make that the y coordinate to give you 16 x,y pairs. Or better just make two 1x16 noise images -- one for x and one for y. Does that sound reasonable rather than using your uniform and gaussian formula. This is much simpler than trying to compute your formulae, esp the gaussian one.

By the way IM has these distributions:


convert -list noise
Gaussian
Impulse
Laplacian
Multiplicative
Poisson
Random
Uniform


Fred

P.S. If you already have a program to generate your pictures, why do you want/need an IM script?

P.S. 2 IM functions -blur and -gaussian-blur are computed internally to floating point accuracy as far as I know (and output in the usual Q range, default is 16-bits). So there should not be any cheap approximation.

[NicolasRobidoux]

Any uniform distribution on [0,1] can be used and fed into the formulas to get points uniformly distributed in the unit disk (this is the formula with a cosine and a sine), then scaled by the "inner" canvas size.

As I said IM produces random numbers in the range [0,1]. But I don't know if that is uniform, but simply random. If that random set of numbers is fed to your sine and cosine formulae, then does that makes it uniform?

...

convert -list noise
Gaussian
Impulse
Laplacian
Multiplicative
Poisson
Random
Uniform

I'll have to read the documentation/source code to see if Random gives a uniform distribution.

Let me explain: There are three distributions in the plane discussed in the article

1) Uniform on the square

2) Uniform on the disk

3) binormal

If you have a uniform distribution of numbers in [0,1] and take consecutive pairs to make coordinates of points, this gives you a uniform distribution on the square.

If you have a uniform distribution of numbers in [0,1], take consecutive pairs and put them in the cos/sin formula, this gives you a uniform distribution on the disk.

If you have a normal distribution of points and you take consecutive pairs, you get a Gaussian distribution of points in the plane. (You may also start with a uniform distribution and put them in the Box-Muller formula to get the same thing.)

It sounds to me like you can easily get the first and third distributions.

P.S. If you already have a program to generate your pictures, why do you want/need an IM script?

Reason 1: NIP2/VIPS is unlikely to have TCB spline code any time soon. If I was to see whether my hunch that TCB (=Tension-Continuity-Bias splines=KBS=Kochanek-Bartels Splines) gives good result is true, another environment was needed.

Reason 2: My "users" (a colleague at the department and one of his Masters student) are likely to find ImageMagick less intimidating than VIPS/NIP2 (and it appears more likely that they'll be happy with one of the many ImageMagick language bindings).

Reason 3: If it's available as an IM script, it's likely to reach more users faster than as a NIP2 workspace. (In other words, I want to use your programming skill to become famous This being said, I can handle "No, thanks.")

Reason 4: If some other people think about it and/or program it, they may have some good ideas RE: this problem, which I find interesting.

[anthony]

As far as generating seed point locations go, accuracy is not an issue at all. Any uniform distribution on [0,1] can be used and fed into the formulas to get points uniformly distributed in the unit disk (this is the formula with a cosine and a sine), then scaled by the "inner" canvas size. Provided the noise has the proper distribution, it should be just fine. To get a binormally distributed sequence of seed points, you probably can simply scale the Gaussian noise instead of using the formula based on the Box-Muller formula.

I figured by uniform it was as described, directly using the flat distribution of a random numbers to get random points in a square.

I am not familar with generating a set of random but uniform points in a disk. Do you have a specific network reference for that?

I would probably have just taken random uniform square points and 'try again' if the point missed a 'disk mask'. That will get me a uniform disk, but would involve a fast X^2+Y^2 < R^2 condition, not a slow trigonometric sine and cosine formula.
But that is me, and I am not that 'research orientated'.

[NicolasRobidoux]

I am not familar with generating a set of random but uniform points in a disk. Do you have a specific network reference for that?

I would probably have just taken random uniform square points and 'try again' if the point missed a 'disk mask'. That will get me a uniform disk, but would involve a fast X^2+Y^2 < R^2 condition, not a slow trigonometric sine and cosine formula.
But that is me, and I am not that 'research orientated'.

Web reference: http://reference.wolfram.com/mathematic ... ation.html This, apparently, is the standard method.

Now: Your suggestion is dead simple, and indeed computationally cheaper than the standard one. I'll mention it in the article. (I'll have to add an "Acknowledgements" section at the end of the article.) Somebody must have figured out that this actually allows the generation of a uniform distribution on any mask: If the point is "in," it's kept, if the point is "out," it's dropped.

(Note that, on the web, there are quite a few bad suggestions RE: how to generate a uniform distribution on the disk. By bad, I mean that the resulting distribution is NOT uniform on the disk. Yours is not one of them.)

[NicolasRobidoux]

The nice TCB=KBS spline figure is here:
http://en.wikipedia.org/wiki/Kochanek%E ... els_spline

[anthony]

I would probably have just taken random uniform square points and 'try again' if the point missed a 'disk mask'. That will get me a uniform disk, but would involve a fast X^2+Y^2 < R^2 condition, not a slow trigonometric sine and cosine formula.

Now: Your suggestion is dead simple, and indeed computationally cheaper than the standard one. I'll mention it in the article. (I'll have to add an "Acknowledgements" section at the end of the article.) Somebody must have figured out that this actually allows the generation of a uniform distribution on any mask: If the point is "in," it's kept, if the point is "out," it's dropped.

It works, is simple and fast, but it is not efficient unless you have a good mask to bounding rectangle ratio. It is possible to have a VERY slow response in a specific case. But on average it works fast.

(Note that, on the web, there are quite a few bad suggestions RE: how to generate a uniform distribution on the disk. By bad, I mean that the resulting distribution is NOT uniform on the disk. Yours is not one of them.)

Yes I know what you mean. The polar coordinates method comes to mind!

[NicolasRobidoux]

I would probably have just taken random uniform square points and 'try again' if the point missed a 'disk mask'. That will get me a uniform disk, but would involve a fast X^2+Y^2 < R^2 condition, not a slow trigonometric sine and cosine formula.

I was wondering why this approach is not the recommended one, and I think I know why: I'd put Aussie money on that generating one more pair of random values is considerably more expensive than the computation of one cos, one sin and one square root, at least with a high quality random number generator. In addition, impossible to predict branching with a nontrivial function call is involved. Given that the probability that a point is rejected is (4-pi)/4 > 20%, the random generator has to be at most 2.5 times more expensive than the sqrt/cos/sin formula for the "check if in and keep/reject" approach to be cheaper.

This being said, I do like the fact that your approach allows constraining the points to a disk (or any mask) without any regard for the source of the random points.

Furthermore, adding a mask is kind of interesting, because it allows generating random shapes that approximate, in some sense, some given binary shape. Like getting random approximations of Mickey Mouse's shadow. Unfortunately, unless the mask is close to being convex, the approximation will be VERY rough unless the initial closed curves are constrained to be vicinity of the mask (some curve piece may join a finger to the nose).

[NicolasRobidoux]

Quick note: There were typos in the Box-Muller formulas (the ones with logs) in the article. In addition, there is a form that avoids calls to trigonometric functions: http://en.wikipedia.org/wiki/Box%E2%80% ... _transform

Fred: I believe that you'll be using a gaussian random variables generator built into IM, so this should not affect what you do.

[fmw42]

Quick note: There were typos in the Box-Muller formulas (the ones with logs) in the article. In addition, there is a form that avoids calls to trigonometric functions: http://en.wikipedia.org/wiki/Box%E2%80% ... _transform

Fred: I believe that you'll be using a gaussian random variables generator built into IM, so this should not affect what you do.

Nicolas,

At this point I am not sure whether the IM noise image generators match what you want, nor yet exactly how to use them. I was going to start by simply trying to duplicate your concept by calling random() in -fx (for uniform? noise) and scaling to square or circle, then connecting with straight lines, etc. Then if necessary use your other formula (corrected version?) for the gaussian noise.

Then or in the mean time, look into the IM noise generators. I don't know if there is any control on sigma for example in the gaussian noise generator, nor if the formula used is appropriate to what you want. Similarly, I am confused between the IM image noise Random and Uniform. I thought you said that the Random() -fx function was uniform? If so, then what is the difference in the IM noise image formats Random and Uniform. Do you want to look over the image noise generator code? See AddNoiseImage() in fx.c in the Magick directory of the source code.

Fred

[NicolasRobidoux]

Fred:

I'll look into random number generation within IM when I have a minute. (Will be a while.)

A "cheaters" way is to use a csv file with pseudo-random numbers, e.g. the pipoints.csv file linked here:
http://www.vips.ecs.soton.ac.uk/index.p ... xperiments

(Thank you for having a look. As for myself, I'm back to grading/homework prep...)

[NicolasRobidoux]

(Very zen) slides of the talk where this work was presented: http://web.cs.laurentian.ca/nrobidoux/shapes.pdf.
Copy of the article in which this work was published: http://web.cs.laurentian.ca/nrobidoux/m ... tt2011.pdf.