random generation of smooth irregular binary shapes

[NicolasRobidoux]

I am just about to submit an article about a very simple method of generating connected smooth irregular binary shapes.

If someone (Fred?) would write an ImageMagick script that does more or less the same thing,

1) I'd be very thankful, and

2) I'd happily mention it in the article.

A draft copy of the article is here: http://web.cs.laurentian.ca/nrobidoux/misc/shapes.pdf.

NIP2 (New Image Processing 2) implementations of the method, as well as some "random alphabets" generated with it, are found here:
http://www.vips.ecs.soton.ac.uk/index.p ... xperiments.

With very but not overly permissive thresholds (13/255, say) and moderate numbers (7 to 20, say) of seed points, the resulting shapes are, in my opinion, "artistically interesting."

[anthony]

I did some work of creating random spots of color. Though it did not guarantee connected shapes.
http://www.imagemagick.org/Usage/misc/#spots

Here is an example command...
Basically a random image, surrounded by a black virtual pixel landscape, and then blurred.

Code: Select all

   convert -size 100x100 xc: -channel G +noise Random -virtual-pixel Black \
               -blur 0x7 -threshold 50% -separate +channel   random_spot1.png

Hmmm... About your 1 point image...
I have never liked how many drawing programs fail to generate a disk when drawing a single point line!
I mean just because a line is of zero length does not mean the 'point' does not have thickness!
One way to fix that is for the single point case draw a line of 'sub-pixel' length.
For example draw the 'point line' 0.0001 pixels long... From IM Examples, drawing circles.
http://www.imagemagick.org/Usage/draw/#circles

Code: Select all

  convert -size 100x60 xc:  -stroke Blue  -strokewidth 50 \
          -draw 'stroke-linecap round line 50,30 50,30.0001' \
          circle_line.gif

[fmw42]

Anthony (and Nicolas),

I have been looking at Nicolas's paper (so far not a full read, just Table 1). Seems like one needs to draw lines between the N points. However, he does not say what points to connect with lines -- is it just the outer points? or every point to every other point? If the former, then how does one select those points.

In any case, I was thinking that one could draw lines from point to point in the order the points are generated as in a (possibly crossing) polygon, then get the convex hull (using -morphology) of the polygon and fill the hull. Then blur, etc. However, I don't really know if the convex hull from the polygon will make sense. You have more experience with that. Any thoughts about this approach?

Alternately one could draw the lines and do an iterative morphologic close until no further changes to hopefully fill any holes, then do the convex hull and fill that, if the convex hull is even needed.

Any thoughts about these ideas?

I need to read the full paper to get a better idea of what is needed and if this is possible with IM.

Fred

[anthony]

In a related item. The use of gaussian distributions to generate 'blob' effects.

A 3-dimensional version of this is already in use in Povray (known as 'blobs'). Basically lines (3-D cylinders) are drawn between points, but the surface is the expanded by performing a gaussian distribution and addition with other nearby lines.

The result is that lines that join together seem to flow and join together as they approach each other.
Here are some old images I created (60 random points on a sphere joined to neighbours via triangulation.


The first is just the points (spheres) conneted by plain cylinders. The second is the same but with 'blobs'.

Some documentation on 3-D povray Blobs...

http://www.povray.org/documentation/view/3.6.1/71/
http://runevision.com/3d/blobs/

[NicolasRobidoux]

In a related item. The use of gaussian distributions to generate 'blob' effects.

A 3-dimensional version of this is already in use in Povray (known as 'blobs'). Basically lines (3-D cylinders) are drawn between points, but the surface is the expanded by performing a gaussian distribution and addition with other nearby lines...

Thank you very much Anthony. This really looks like something I should have known about, but did not.

[NicolasRobidoux]

...I have been looking at Nicolas's paper (so far not a full read, just Table 1). Seems like one needs to draw lines between the N points. However, he does not say what points to connect with lines -- is it just the outer points? or every point to every other point? If the former, then how does one select those points.

In any case, I was thinking that one could draw lines from point to point in the order the points are generated as in a (possibly crossing) polygon, then get the convex hull (using -morphology) of the polygon and fill the hull. Then blur, etc. However, I don't really know if the convex hull from the polygon will make sense. You have more experience with that. Any thoughts about this approach?

Alternately one could draw the lines and do an iterative morphologic close until no further changes to hopefully fill any holes, then do the convex hull and fill that, if the convex hull is even needed.

Any thoughts about these ideas?
...

Hmmm. 'Looks like I may need to write the paper more carefully.

Some comments:

The closed polygonal curve is generated by joining the points, in order, by straight lines. It's that simple. (Part of my surprise is how interesting the shapes turn out to be with this very simple minded approach.) The lines may or may not cross, etc. Exactly the kind of "bulbous blobs" that are avoided in the POVray by putting negative blobs at the intersections actually lead to "interesting shapes" when the thresholding is sufficiently permissive. I do nothing to avoid their effect.

The convex hull will produce boring shapes, because blurring then thresholding a convex shape produces a dilated + rounded version of it (kind of like inflating a balloon version of the convex shape). I actually want holes in the shape prior to the blurring so that the shape expand "nonlinearly", even if those holes are filled in in the end: it affects "the outer shape."

One of the points of the articles is that if you don't mind having holes, you can ensure a connected shape without resorting to topological operations: just threshold sufficiently permissively.

(Removing holes, on the other hand, is not something I know how to do without morphological operations.)

Although I've not done it for the article, I really believe that Kochanek-Bartels splines (a.k.a. TCB-splines) would give better results than linear splines.

[NicolasRobidoux]

...In a related item. The use of gaussian distributions to generate 'blob' effects...

Anthony:

Would you happen to have any citation or web site or ??? where people (you?) generated "blobs" by joining randomly generated points by curves/straight line segments/triangulations/... then blurring then thresholding, or something kind of like it?

I see that basically you had this idea yourself (unless you took it from someone?). Anything I could cite?

[anthony]

The closed polygonal curve is generated by joining the points, in order, by straight lines. It's that simple. (Part of my surprise is how interesting the shapes turn out to be with this very simple minded approach.) The lines may or may not cross, etc. Exactly the kind of "bulbous blobs" that are avoided in the POVray by putting negative blobs at the intersections actually lead to "interesting shapes" when the thresholding is sufficiently permissive. I do nothing to avoid their effect.

that may not be a problem, as Povray generated the 'linear blur' of the two lines (cylinders) then adds them. However you are generating a blur after the two lines have been drawn (overlaid not added) As such you do not get greater than 1.0 additions to your 'fields'. However it is a closely related variant, and 3-D as well.

But Fred was right, you don't actually mention how the lines connect up the points. I am sure for example you do not want a triangulization, as that will generate a convex hull. On the other hand you probably don't want too many line crossings either as these just fill the inside of the shape with a mass of lines.

(Removing holes, on the other hand, is not something I know how to do without morphological operations.)

Just flood-fill the outside of the shape with some color, and then use that color to define you new shape without holes.
You can actually use that with a 'fuzz factor' as your threholding step.

[fmw42]

The closed polygonal curve is generated by joining the points, in order, by straight lines. It's that simple. (Part of my surprise is how interesting the shapes turn out to be with this very simple minded approach.) The lines may or may not cross, etc. Exactly the kind of "bulbous blobs" that are avoided in the POVray by putting negative blobs at the intersections actually lead to "interesting shapes" when the thresholding is sufficiently permissive. I do nothing to avoid their effect.

OK. That was what I thought as the simple minded approach, but was not sure that was what you want. So you only connect them in order with rather thick lines (eg 13 pixels?) and then blur and threshold. Is that correct?.

The convex hull will produce boring shapes, because blurring then thresholding a convex shape produces a dilated + rounded version of it (kind of like inflating a balloon version of the convex shape). I actually want holes in the shape prior to the blurring so that the shape expand "nonlinearly", even if those holes are filled in in the end: it affects "the outer shape."

Right. I thought that might be the case in hind sight after reading your paper.

One of the points of the articles is that if you don't mind having holes, you can ensure a connected shape without resorting to topological operations: just threshold sufficiently permissively.

(Removing holes, on the other hand, is not something I know how to do without morphological operations.)

Yes, Anthony's solution above is much better than using morphology.

Although I've not done it for the article, I really believe that Kochanek-Bartels splines (a.k.a. TCB-splines) would give better results than linear splines.

I have a script that does splines of various kinds, esp, Catmull-Rom and KBS (Catmull-Rom with tension and bias). See http://www.fmwconcepts.com/imagemagick/spline/index.php I am unfamiliar with TCB splines.

Fred

[NicolasRobidoux]

The closed polygonal curve is generated by joining the points, in order, by straight lines. It's that simple. (Part of my surprise is how interesting the shapes turn out to be with this very simple minded approach.) The lines may or may not cross, etc. Exactly the kind of "bulbous blobs" that are avoided in the POVray by putting negative blobs at the intersections actually lead to "interesting shapes" when the thresholding is sufficiently permissive. I do nothing to avoid their effect.

OK. That was what I thought as the simple minded approach, but was not sure that was what you want. So you only connect them in order with rather thick lines (eg 13 pixels?) and then blur and threshold. Is that correct?.

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.

One of the points of the articles is that if you don't mind having holes, you can ensure a connected shape without resorting to topological operations: just threshold sufficiently permissively.

(Removing holes, on the other hand, is not something I know how to do without morphological operations.)

Yes, Anthony's solution above is much better than using morphology.

To my defense: I view flood fill as a morphological operation. For one thing, it is not local. (Now if this is not splitting hair!)

Although I've not done it for the article, I really believe that Kochanek-Bartels splines (a.k.a. TCB-splines) would give better results than linear splines.

I have a script that does splines of various kinds, esp, Catmull-Rom and KBS (Catmull-Rom with tension and bias). See http://www.fmwconcepts.com/imagemagick/spline/index.php I am unfamiliar with TCB splines.

Fred

KBS=TCB. It's just another acronym.

Thanks and cheers,

nicolas

[NicolasRobidoux]

I've updated the draft, adding a reference to Anthony's "dithering" method as described in IM Examples and a few other tweaks. The update is here: http://web.cs.laurentian.ca/nrobidoux/misc/shapes.pdf

I've not quite figured how to mention POVray, given that the only example of doing something like what the article describes with it appears to me to be Anthony's, right in this forum topic, which is not quite citation material.

Thank you Anthony and Fred.

[fmw42]

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.

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.

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

[fmw42]

I've updated the draft, adding a reference to Anthony's "dithering" method as described in IM Examples and a few other tweaks. The update is here: http://web.cs.laurentian.ca/nrobidoux/misc/shapes.pdf

I've not quite figured how to mention POVray, given that the only example of doing something like what the article describes with it appears to me to be Anthony's, right in this forum topic, which is not quite citation material.

Thank you Anthony and Fred.

I presume you elaborated on connecting the points is sequence, as well.

Fred

[NicolasRobidoux]

I presume you elaborated on connecting the points is sequence, as well.

Fred

Yes I did:

Do you think this is clear enough?

Note that consecutive random points are joined. In addition, the
last point is joined back to the first. That is, a closed curve is
generated by Steps 1 and 2, not a triangulation or convex hull, and
self-crossings are not avoided.

[fmw42]

I presume you elaborated on connecting the points is sequence, as well.

Fred

Yes I did:

Do you think this is clear enough?

Note that consecutive random points are joined. In addition, the
last point is joined back to the first. That is, a closed curve is
generated by Steps 1 and 2, not a triangulation or convex hull, and
self-crossings are not avoided.

Yes, that is very clear.

Fred

P.S. See my questions and comments in my previous post above.