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.