Infinite loop?
Opened this issue · 6 comments
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
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.
Ah, yes, I was feeding it a colour image.
Just encountered the same issue :-( Do you know about a full implementation of this?
I haven't looked recently, but there wasn't one last time I checked.
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
I might look into this myself. I'm experiencing this issue too.