Infinite loop?

[stolk]

Seems to get stuck in an infinite loop? The original Microsoft research paper mentions sub second run times to process an image. But this code runs for minutes at 100% CPU, and when I stop the script, this is the call stack I see:

$ time ./depixel_png.py --to-svg bt_02.png Processing bt_02.png... ^CTraceback (most recent call last): File "./depixel_png.py", line 83, in main() File "./depixel_png.py", line 79, in main process_file(options, filename) File "./depixel_png.py", line 55, in process_file data.depixel() File "/usr/local/lib/python2.7/dist-packages/depixel-0.1-py2.7.egg/depixel/depixeler.py", line 338, in depixel self.add_shape_outlines() File "/usr/local/lib/python2.7/dist-packages/depixel-0.1-py2.7.egg/depixel/depixeler.py", line 551, in add_shape_outlines path = self.make_path(graph) File "/usr/local/lib/python2.7/dist-packages/depixel-0.1-py2.7.egg/depixel/depixeler.py", line 538, in make_path path = Path(graph) File "/usr/local/lib/python2.7/dist-packages/depixel-0.1-py2.7.egg/depixel/depixeler.py", line 608, in init self.path = self._make_path(shape_graph) File "/usr/local/lib/python2.7/dist-packages/depixel-0.1-py2.7.egg/depixel/depixeler.py", line 625, in _make_path for neighbor in shape_graph.neighbors(path[-1]): File "/usr/lib/python2.7/dist-packages/networkx/classes/graph.py", line 977, in neighbors return list(self.adj[n]) KeyboardInterrupt

real 5m57.368s user 5m57.220s sys 0m0.346s

ubuntu 14.04 lts pyhton 2.7.6 networkx 1.8.1 source image: bt_02.png: PNG image data, 42 x 14, 8-bit colormap, non-interlaced

[jerith]

Do you have a copy of the source image I can look at?

My implementation is incomplete and I suspect you're running into one of the cases it doesn't handle. Specifically, it doesn't know what to do when it encounters a three-way junction, which is possible with non-monochromatic inputs.

[stolk]

Ah, yes, I was feeding it a colour image.

[sreuter]

Just encountered the same issue :-( Do you know about a full implementation of this?

[jerith]

I haven't looked recently, but there wasn't one last time I checked.

[ideasman42]

Looked into this, the error is caused by having pixel content at the top-right of the image (any pixels touching the top or the right hand side of the image).

Logically, this should just be a matter of adding edges for the size + 1 on X and Y axis. However trying to do this, I ran into problems where it expects another row/column of pixels too.

As a last-resort, I managed to come up with a weak workaround which was to fake resizing the canvas on the top-right, Filling with empty pixels, then exiting if an infinite loop is found (when the path can't grow anymore). This isn't really a solution, just posting here in case others want to investigate the issue further.

Heres the commit for the workaround: https://github.com/ideasman42/depixel/commit/cdf50b3399e6376ce5d60d714fb80e1e47ab3a23

[GarethPW]

I might look into this myself. I'm experiencing this issue too.