This is super cool.

I wonder if you could convert it to colour as well, if you changed the rule from a single thread for the whole thing to three threads for the whole thing (CMY). Might be quite an interesting effect since you'd need to sort of "smudge" colours across the image the same way you're essentially smudging the blacks.

Edit: Wait a minute, actually it wouldn't work because you can't combine colours. Put magenta thread on top of cyan and you'd get... magenta.

You might be able to run the algorithm once on each color component.

I wonder how much better a less greedy algorithm would be-- e.g. one that considered many possible moves a few positions deep, and took one step towards the best... or one that after finishing unwrapped the beginning halfway and rewrapped it backwards from the middle, then unwrapped the end, and rewrapped it forwards from the middle, and repeated until convergence.