Zoals al gezegd ging ik het graph cut algoritme implementeren. Dit is bij deze gebeurd… hoera.. hoera..

Misschien kan ik wat meer uitleg geven…

Initieel dacht ik om Boost te gebruiken. Helaas bevat Boost standaard geen algoritme om de minimale snede van een graaf te berekenen. (nvdr: het hart van het graph cut algoritme) Dus ging ik op zoek naar alternatieven. Ik kwam de implementatie van Vladimir Kolmogorov en Yuri Boykov tegen. Deze leek te doen wat ik wou, implementeren maar. Helaas bleek deze niet te werken. Vreemd. Men moet precies bij alle noden de gewichten naar de source/sink instellen. Jammer..
Maar nu was ik weer bij af. Geen implementatie.
Na lang zoeken op google (net iets meer dan 5 minuten), vond ik eindelijk een tweede implementatie: Pseudoflow Solver 3. Na een eerste kijk bij de specificatie, leek deze een droom. Echter.. u raadt het al.. dromen zijn bedrog. Pseudoflow Solver 3 (PS3) werkt met pointers, ik kon dus geen variabel aantal bogen in mijn grafe toevoegen. Ik dacht: “geen probleem, even aanpassen in de source”. TIP OF THE ICE BERG! Ik vloog werkelijk van de ene fout naar de andere: eerst de pointers, dan niet-geïnitializeerde waarden, om te vervolgen met infinite loops en te eindigen met random crashes. Dit alles om te merken dat het algoritme ook niet werkte… en veel memory leaks had… weer een dag verloren..
Ik begon de hoop zowat te verliezen, en dacht: “ik ga eens mailen naar de auteurs”, in de hoop dat zij mij wat meer info zouden kunnen geven. Zo gezegd, zo gedaan. Deze middag mail ik hen. Enkele uurtjes later vraagt een van de PS3 auteurs of ik wel weet dat PS3 een array teruggeeft met voor elke node of deze bij de source of de sink hoort. Ik denk bij mezelf: “tuurlijk, weet ik dat, anders had ik die implementatie niet gekozen”…

…
en toen drong het door…
…

Source en sink geven niet de snede weer, maar daar waar de afbeeldingen beginnen!! 20 minuten later werkte het algoritme. Moraal van het verhaal? “Zoals altijd bij programmering, liggen fouten bij eigen code.” Het was dus mijn eigen domme fout.

Graph cut is dus geïmplementeerd, maar werkt nog niet optimaal. De kost functie moet nog beter. Ook omega tiles zijn geïntegreerd, dit was op klein uurtje gebeurd.
De hoofdzaken voor de eerste fase van deel I zijn dus klaar! Nu is het nog tunen tot het gewenste resultaat.
Morgen zal besteed worden aan tunen van de algoritmen. Ik zal dan enkele resultaten op de blog posten.
Donderdag en vrijdag is het de beurt aan de presentatie voor de eerste thesispresentatie van volgende week. (kom allen talrijk kijken )
Volgende week zullen dan nog allerlei optimalisaties aan de programma’s worden doorgevoerd.

Tot zover..

Graag zou ik Bala Chandran bedanken. Dankzij zijn email heb ik mijn graph cut!!

This entry was posted on Wednesday, October 26th, 2005 at 1:32 and is filed under Algemeen, Dutch. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.