The next step of the algorithm is to improve this graph further more with three heuristics. I'll try to implement this step during the next two weeks.
I implemented this step and graph is fully optimized, but I found a strange behaviour in paper's algorithm.
I'm attaching 2 files this time.
heuristics_evolution.zip has some sample images generated from newer code and its only purpose is to show progress (even if you don't look the source code).
pape error.zip has details about the strange behaviour I found in the paper's algorithm. Maybe some images from the supplementary material were tunned. Maybe they pressed the wrong keys when they were writing the paper. Maybe they changed one of the algorithms and forget to update the paper. Maybe I'm the one wrong here.
It's not possible to replicate their results with this error, but I'll let users of libdepixelize to provide values to tune the algorithm and get the same results. I think the "tunned" value is the one from "sparse pixels" heuristic, but I need to analyze all sample images to be sure and I'll only do it after I implement the full algorithm (this would make analyze easier).
Next step is to implement a voronoi diagram (I may blog about this).
One extra note:
This algorithm uses the same procedure to detect dissimlar colors from hqx filter and this algorithm don't support alpha channel, but several hqx libraries have alpha channel support. I intend to implement alpha channel support in libdepixelize, but I need to reasearch how to do it and I want to obey my timeline, then this *extra* feature will be done *after* my timeline.