Q. Is it possible to infer an open path "running down the middle" of a closed contour?

I dreamed that someone had set up the math for this, but when I woke up today and hunted for it, I can't find it. (I even searched on 'path' at gimpscripts.com!)

It seems that it would be practical, in that it would enable an "area" to be paintable by stroking along its, found, path (in contrast to merely filling/dump-painting it), but a difficult problem to solve mathematically. The phrase "relaxation method" comes to mind, but after that exertion, my mind is spent. I have already made the closed path as thin as practicable using "Shrink", without breaking it into separate islands. And therein might lie the seed of an approach: follow the Shrink algorithm "while maintaining connectivity." (Whatever that means; as I said, my mind's spent.)

In my particular case, I have the, thin, closed outline of a river system (think tree branches) and I would like to obtain from it an open-path representation (which could be stroked in various ways) to reproduce it. Stroking the closed path is unappealling, as is hand-fitting a million-some points to create one. An open path could also be followed to generate XYI triplets for use in CNC as we discussed here.

Thank you.

I have an idea that it might be approached by processing a closed path off-line.

Here are a couple of figures: of the original, simple path [Edit: created with Path tool], and of the enclosing path created with Save-Selection-As-Path [Edit: after stroking the first path with a 1-pixel brush and selecting that].

From staring at these and my real problem, it occurred to me--and probably laughably obvious to everyone else--that nodes "close" to each other should be replaced by their average to simplify the representation.

A websearch on data clustering turned up something called the Markov Cluster Algorithm, MCL, which promises to simplify
"networks" of nodes and weighted, as I understand it, edges. http://www.micans.org/mcl/

Now, if a closed-path representation could be read out into a network representation, it might be fed to a MCL to be "reduced/relaxed" to a simpler network, which could be read back out as, at least, a simpler closed-path representation.

Failing that, the nodes could be read out of the XML representation of the exported path and classified onto lists for later evaluation, processing and re-classification.

Nutty. I know. But my other idea was to try to "walk" a node between the contours of a closed-path, zapping it if it crossed either--like they were part of an electric fence. In fact, that reminded me of a phrase I know very little about: random walk. And hunting up some background information on that to add to this pile of motivation, I discovered that "[an] image is modeled as a graph, in which each pixel corresponds to a node which is connected to neighboring pixels by edges, and the edges are weighted to reflect the similarity between the pixels."[1]

Apparently all "we" need to do is to have "you" [2] program the random-walk algorithm for an image of the closed path on a background...
[1] https://en.wikipedia.org/wiki/Random_walker_algorithm
[2] Theoretically, "I" could learn from here, given enough time[3]:
https://www.khanacademy.org/computing/c ... ndom-walks
[3] https://en.wikipedia.org/wiki/Infinite_monkey_theorem

Wallace,

I'm sorry. I am a born confuser.

The first image was of an open path concocted with the Path tool (by drawing 4 paths actually and combining visual paths into one

I stroked that path with a 1-pixel brush (and failed to mention it).

Then I selected-by-color what was stroked and the second image shows the closed path created by GIMP (2.8).

I would like to be able to get an open path, either from "Selection-To-Path" tool directly or by processing the closed path that results from that.

Hope that's clearer. [because I have also made edits...]

Some more experimentation.

I can, at least, "reduce" the closed path of Bezier curves to a path of line segments. I exported the closed path with Ofnuts' fine path to/from CSV plugin, for the simple path, and for one with a Bezier node added to one leg.

I loaded them both into openoffice Calc and discovered the 1st and last pairs of columns held coordinates of the control points (and just now discovered the same information in ofnuts' plugin NB. to newbies: Did you know you can READ the scripts with a text editor?)

I copied the central pair of columns overtop of the control columns, wiping out curvature information and used the plugin again to load
the edited CSV back into the project.

I am currently drowning in Molasses Swamp trying to see if I can find "similar" nodes, and replace them with their averages, inside
a spreadsheet. Almost certainly the wrong tool, but from what I skimmed about Markov and random-walk, I'm not eager to exchange
a Swamp for Black Hole.

"Surely the problem of simplifying and replacing the outline of a line with a 0-width line has been solved by computer scientists."
he said, hopefully, his feet making sucking sounds as the Swamp burped.

Wallace,

NO! I was not aware of it, although I do recall seeing some of the items on the settings menu: I've been racking my brain but cannot recall where.

I did find that the "Selection Editor" on the Select pulldown menu has a "Selection-to-path" icon and which hints "Shift Advanced Options" when hovered over.


I'll have to puzzle through the selections to see if there's a way to force an open path.

Thank you for some hope.

Wallace,

I've tried several combinations (of extreme values) and all seem to, while definitely changing the shape of the saved path, not change the "type" from closed to open.

I would guess these options affect the smoothedness of the saved path, but never reduce the number of nodes which is what I am after.

Thank you, yes. I'm well acquainted with ofnuts' prodigious "community grants." Some people wish they could be Super or Bat or Spider or Wo man. I'd want to be able to code like ofnuts and his confreres.

But I've been searching more deeply on the subject and learned it's a tough nut. (Esper had a thread a few years ago asking about reducing a font to its "line essences" (essentially)). [Edit: viewtopic.php?f=4&t=8553]

My opiniion is that it definitely would have to be done offline because every node would need to be compared to every other node, not just those "close" on the same stroke, in case other strokes are "near" too. I propose to read nodes off the path, examine them, and store them, with node-ids, in matrix order, along with pointers to their neighbors along the link, for later processing to identify which nodes are "close" to each other and then to replace all such nodes, on all strokes, with their average position,... gets complicated quickly.

Seems like I heard about this in artificial intelligence years ago all those years ago. Just can't remember anything anymore.

(Someone on Esper's thread suggested "shrinking" a selection while prohibiting it from every getting thinner than one pixel, to which a response was made that it was harder to do than it appears. That made me imagine "smart" pixels which "have a say" in whether they get removed from a path or not. Object-orientation and all that you know, but again I declaim through my haberdash.)

Wallace,

I did look at Inkscape briefly. I was a little disconcerted to find I was asked for the size of the canvas when I was importing a graph from GIMP--that made me worry that scale might not be preserved going back and forth.

Nothing jumped out at me in terms of high-powered path processing, but I did not look into nearly as many corners as I have in GIMP.

Thanks for the idea. I'll give it a serious look (and even search some on the web).
--
David

Inkscape XML Editor is worth a look.
Export GIMP paths from the path dialog menu, merged or separately.

(Whoops, ninja'd by you Odinbc as I hit submit.)

@Wallace
I did look at Inkscape, and it's advice that "Trace Bitmap" uses Potrace ultimately led me to find autotrace (which traces centerlines, unlike the former), but all I can report is that no obvious "Way How to Proceed" revealed itself, and ultimately I just kept wandering around lost in the woods, looking under rocks. Inkscape's reminder of Potrace's reminder of autotrace at least reminded me that THAT is where I saw arguments similar to what are in the Selection Editor's menu's Advance Settings.

Still Inkscape shows promise in that its Path->Simplify routine DOES seem to reduce the number of nodes. However, at the same time, it also adds wild curvature (possibly because it imagines the curves pass through removed points...). The result is a rather a modern artist's impression of what a river system _should_ looks like. No doubt this is due to my choices for Tracing and my choice of threshold for Simplifying, but there are no obvious guides for the un-mathed.

I did use my trick of importing the new simplified Inkscape path into GIMP, then exporting it with ofnuts to-CSV, then over-copying the Bezier control points in openoffice with the endpoints and importing the edited CSV back into GIMP. That removed all the curvature, but revealed that in the process of simplification, Inkscape left behind a horde of orphaned nodes--degenerate paths.

So, Inkscape is a "possible" but it would take someone with insight to guide the processes to the desired result I think.

@Odinbc
I didn't stumble across an XML editor, but did find a hint about using Shift-Ctrl-X to open an XML description of the path from which I was able to copy, piece-by-piece, the path into a text editor for creating an xml/svg description to pull into GIMP.

It seems to boil down to "what settings in what steps should be chosen to extract a simple, open path from a Trace of a bitmap containing black lines on white?"

I'm attaching what the simplified path looks like when imported into GIMP and a copy of the settings I used for TraceBitmap. (The only "setting" I found for simplification is a One-Size-Fits-All "Simplification Preferences" in File->InkscapePrefs->Misc

I did some more hunting re: Inkscape and found this:
http://stackoverflow.com/questions/6386 ... ove-curves

which I'll quote:
Q. Is there any tool or formula to convert these curves into simple coordinates?

R1. In Inkscape:
Select the Edit Path By Nodes tool (F2).
Click on your path to select it
[Edit: Do Path->Simplify to reduce number of nodes.][Commentary: No matter how passively or
aggressively the simplification, nodes are only reduced "along" paths, never "across." That is,
the simplified path will remain "closed" and the figure will continue to have "area" (and look weirder
and weirder as simplification/node-reduction continues.]
Ctrl-A to select all the nodes in that path
Click Make Selected Segments Lines (on the toolbar at the top - the icon is a straight diagonal line between two
square nodes). [Commentary: Because the path is still closed, the figure, an area bounded by weird
curves, will be replaced by an area bounded by weird lines.]
R2. For automation, try the included "Flatten Bezier" extension in Inkscape.

This sound promising (and sounds like what I've been doing with openoffice calc: ).

That is an XML Editor. You can edit or draw XML descriptions of an SVG drawing. A Path example in XML.

@Wallace

Doesn't work... The path-simplification step in Inkscape, no matter the "simplification threshold" NEVER interrupts the essential connectedness of the path. By that I mean, I believe the algorithm only considers combining points which are close and already connected. What is essential for reducing a closed path to an open one which can approximate the original by stroking is to combine strokes where both endpoints are close to each other. (Going back to the idea of "smart" nodes, I envision now a "forum" where all the strokes (now) advertise their positions to each other and when they receive favorable responses of closeness, pair off to discuss further, ultimately joining where possible, before starting another round.)

I'm afraid a new algorithm is called-for. And I think that a function that would save a "representation of a line" to a true line (open path) in either GIMP or Inkscape would prove its usefulness over time as people discovered new applications for it. I admit that's easy to say.

@Odinbc

Thank you for that link. I've had a very hard time (I suspect it's my search history) getting links to definitive pages like that. I typically have to wade through reams of consumer links.

I have to ask: is there a similar reference for GIMP? (I don't know, but it will also help to have a pointer
in this thread.)

As I was saying, what's needed is a new way to simplify paths which (identifies and) preserves the general orientation of their strokes.

Here's a GIMP project containing only a simple, open, path to test Inkscape's algorithm. (It can be closed and tried too.)

I want to replace the closed [sorry, open in this picture] path representing a putative invisible open path with an open path representing the putative center-line of the closed path.
[Edit: I can see that the obvious thing is to replace each pair of close nodes by their average locations.]

BTW, I should add that another problem with Inkscape Path->Simplify is that nodes that were close are often replaced by nodes that are not...

...so, when this is finally possible [Future? Saaa-LUTE!], it will behoove us to render the open path first and then simplify that.