Lustiges Programmieren mit Hypo (Teil n-1)

Daniel · **Joined:** 18.10.2004 13:48 **Posts:** 757

Der Rückgabewert der main()-Funktion (oder genereller des Programmeinstiegspunktes) ist nicht dazu da, Funktionswerte zu liefern, sondern nur zur Fehleranzeige. 0 bedeutet kein Fehler, dann (und nur dann) liefert system() auch 0 zurück. Werte ungleich 0 sind dann wohl implementierungsabhängig, zumindest soweit ich das in Erinnerung habe. Immerhin muß system() auch eigene Fehler anzeigen können, z.B. einen fehlenden Kommando-Interpreter. Du mußt dann wohl einen anderen Weg finden, den zurückgegebenen "Fehlercode" exakt abzufragen, wie das funktioniert weiß ich aber nicht mehr. Ein besserer Weg wäre, die Standardein- und -Ausgabe umzubiegen und dann darüber zwischen den Prozessen zu kommunizieren.

Hypothraxer

Daniel wrote:

Der Rückgabewert der main()-Funktion (oder genereller des Programmeinstiegspunktes) ist nicht dazu da, Funktionswerte zu liefern, sondern nur zur Fehleranzeige. 0 bedeutet kein Fehler, dann (und nur dann) liefert system() auch 0 zurück. Werte ungleich 0 sind dann wohl implementierungsabhängig, zumindest soweit ich das in Erinnerung habe. Immerhin muß system() auch eigene Fehler anzeigen können, z.B. einen fehlenden Kommando-Interpreter. Du mußt dann wohl einen anderen Weg finden, den zurückgegebenen "Fehlercode" exakt abzufragen, wie das funktioniert weiß ich aber nicht mehr. Ein besserer Weg wäre, die Standardein- und -Ausgabe umzubiegen und dann darüber zwischen den Prozessen zu kommunizieren.

Jetzt wo du's sagst, machts natürlich Sinn. Ich hab's jetzt so gelöst, dass ich das C-Programm die Files abspeichern lasse und die Files dann im C++ Programm wieder einlese. Das generiert zwar relativ viele Festplattenzugriffe, ist aber noch vernachlässigbar.

Mehr Sorgen macht mir folgendes:

Code:

for (int i = 0; i < int (dRansacStop); i++)
      //while (iConscensusCountTop < 200)
      {
         while (iRandCheck < 4)
         {
            srand (time(NULL));
            iAdjust = rand() % ip;
            if (iRandCheck == 0)
            {
               AD[iRandCheck].iNr = iAdjust;
               vL[iRandCheck * 2] = SE[AD[iRandCheck].iNr].dX;
               vL[iRandCheck * 2 + 1] = SE[AD[iRandCheck].iNr].dY;

            }
            if (iRandCheck == 1)
            {
               AD[iRandCheck].iNr = iAdjust;
               if (AD[1].iNr == AD[0].iNr)
               {
                  iRandCheck--;
               }
               else
               {
                  vL[iRandCheck * 2] = SE[AD[iRandCheck].iNr].dX;
                  vL[iRandCheck * 2 + 1] = SE[AD[iRandCheck].iNr].dY;
               }

            }
            if (iRandCheck == 2)
            {
               AD[iRandCheck].iNr = iAdjust;
               if (AD[2].iNr == AD[1].iNr || AD[2].iNr == AD[0].iNr)
               {
                  iRandCheck--;
               }
               else
               {
                  vL[iRandCheck * 2] = SE[AD[iRandCheck].iNr].dX;
                  vL[iRandCheck * 2 + 1] = SE[AD[iRandCheck].iNr].dY;
               }

            }
            if (iRandCheck == 3)
            {
               AD[iRandCheck].iNr = iAdjust;
               if (AD[3].iNr == AD[2].iNr || AD[3].iNr == AD[1].iNr || AD[3].iNr == AD[0].iNr)
               {
                  iRandCheck--;
               }
               else
               {
                  vL[iRandCheck * 2] = SE[AD[iRandCheck].iNr].dX;
                  vL[iRandCheck * 2 + 1] = SE[AD[iRandCheck].iNr].dY;
               }

            }
            iRandCheck++;
         }

         iRandCheck = 0;

         for (int s = 0; s < 4; s++)
         {
            mA[s * 2][0] = TE[AD[s].iNr].dX;      // x
            mA[s * 2][1] = TE[AD[s].iNr].dY;  // y
            mA[s * 2][2] = 1;
            mA[s * 2][3] = 0;
            mA[s * 2][4] = 0;
            mA[s * 2][5] = 0;
            mA[s * 2][6] = -SE[AD[s].iNr].dX * TE[AD[s].iNr].dX;
            mA[s * 2][7] = -SE[AD[s].iNr].dX * TE[AD[s].iNr].dY;

            mA[s * 2 + 1][0] = 0;
            mA[s * 2 + 1][1] = 0;
            mA[s * 2 + 1][2] = 0;
            mA[s * 2 + 1][3] = TE[AD[s].iNr].dX;
            mA[s * 2 + 1][4] = TE[AD[s].iNr].dY;
            mA[s * 2 + 1][5] = 1;
            mA[s * 2 + 1][6] = -SE[AD[s].iNr].dY * TE[AD[s].iNr].dX;
            mA[s * 2 + 1][7] = -SE[AD[s].iNr].dY * TE[AD[s].iNr].dY;
         }


         vX = (mA.Transpose() * mP * mA).Inverse() * mA.Transpose() * mP * vL;

         vV = mA * vX - vL;

         mX[0][0] = vX[0];
         mX[0][1] = vX[1];
         mX[0][2] = vX[2];
         mX[1][0] = vX[3];
         mX[1][1] = vX[4];
         mX[1][2] = vX[5];
         mX[2][0] = vX[6];
         mX[2][1] = vX[7];
         mX[2][2] = 1;


         mX = mX.Inverse();

         c11 = mX[0][0];
         c12 = mX[0][1];
         c13 = mX[0][2];
         c21 = mX[1][0];
         c22 = mX[1][1];
         c23 = mX[1][2];
         c31 = mX[2][0];
         c32 = mX[2][1];
         c33 = mX[2][2];

         
         for (int o = 0; o < ip; o++)
         {
            //if (o != AD[0].iNr && o != AD[1].iNr && o != AD[2].iNr && o != AD[3].iNr)
            //{
               dRandomX = (c11 * SE[o].dX + c12 * SE[o].dY + c13) / (c31 * SE[o].dX + c32 * SE[o].dY + c33);
               dRandomY = (c21 * SE[o].dX + c22 * SE[o].dY + c23) / (c31 * SE[o].dX + c32 * SE[o].dY + c33);

               if (sqrt(pow(dRandomX - TE[o].dX, 2) + pow(dRandomY - TE[o].dY, 2)) < 3)
               {
                  SE[o].iFlag = 1;
                  TE[o].iFlag = 1;
                  iConscensusCount++;
               }
               else
               {
                  SE[o].iFlag = 0;
                  TE[o].iFlag = 0;
               }
            //}
         }

         if (iConscensusCount > iConscensusCountTop)
         {
            iConscensusCountTop = iConscensusCount;
            c11Top = c11;
            c12Top = c12;
            c13Top = c13;
            c21Top = c21;
            c22Top = c22;
            c23Top = c23;
            c31Top = c31;
            c32Top = c32;
            c33Top = c33;

         }
         iConscensusCount = 0;
         cout << "Iteration: " << i << " Highest Conscensus: " << iConscensusCountTop << " of " << ip << "\n";
      }

Mit dem probiere ich, mit Punkten aus zwei Datensätzen, eine Matrize zur Berechnung einer projektiven Transformation zwischen den beiden Datensätzen zu erhalten - mittels RANSAC. Das Problem: Es ist lahm - wirklich lahm. Ich bin mir allerdings nicht sicher, woran das liegt. Ich vermute, dass das Generieren der Zufallszahl das Problem sein könnte. Kann es sein, dass das jeweilige Initialisieren mittels

Code:

srand (time(NULL));

das Problem ist? Ich reinitialisiere den immer wieder, in der Hoffnung, dass die Zufallszahlen etwas 'zufälliger' werden.

Daniel · **Joined:** 18.10.2004 13:48 **Posts:** 757

Bei solchen Problemen hilft oft Benchmarking. Wie lahm ist es jetzt und wie schnell ist es, wenn du nicht neu seedest (srand)? In dem Fall aber nicht nötig, ich sehe das Problem schon.

Deine Neuinitialisierung ist eine schwere Katastrophe. Mit time(NULL) bekommst du die Zahl der vergangenen Sekunden seit dem 1. Januar 1970. Sekunden! Das heißt, der Wert ändert sich nur einmal pro Sekunde, damit dein Initialwert für srand und damit die erste abgefragte Zufallszahl. Mal abgesehen von dem unwahrscheinlichen Fall, daß in den ersten Zufallszahlen von vier aufeinanderfolgenden Seedwerten zwei identische Werte sind (wobei der Fall durch dein Modulo wieder wahrscheinlicher wird, aber trotzdem eher selten sein sollte, es sei denn ip ist eher klein), hast du einen Best Case mit einer Laufzeit von vier Sekunden (!) pro Neuinitialisierung. Und davon hast du dRansacStop viele, wieviele das auch immer sein mögen. In jedem Fall inakzeptabel.

Der Standardpseudozufallszahlengenerator taugt nichts. Selbst wenn deine Neuinitialisierung schnell wäre, sie würde nicht wirklich helfen. Das ist ein Generator für Fälle, in denen man mal eben ein paar Zahlen braucht, aber nur so wenige, daß eine Mustererkennung eh witzlos wäre. Deine Lösung lautet daher, einen anderen Generator zu nehmen, den du dann auch nur einmal initialisieren mußt. Schau dich mal nach dem Fast Mersenne Twister um. Das ist zwar nicht der Weisheit letzter Schluß, aber für nichtkryptografische Anwendungen wirst du mit dem glücklich. Die Periodenlänge (Zahl der Zufallszahlen, bis sich die Zahlen wiederholen) ist in der Standardkonfiguration (gibt auch größere) bereits 2^19937-1 (eine Mersennsche Primzahl, daher der Name). Außerdem ist das der einzige Generator, dessen Name ich noch kannte.

Hypothraxer

Ich hab ja irgendwie vermutet, dass es daran liegt. Ich habe mir die RNG-Generatoren der GNU Scientific Library zu Hilfe genommen. Den Mersenne Twister gibt's da auch - aber ich hab ranlux genommen. Ein Zufallszahlgeneratoren der 'luxury random numbers' generiert, kann ja nicht schlecht sein

Resultat? Statt ~2 Minuten rauscht das jetzt in einer Sekunde durch. Tip top! Dank dir recht herzlich! Jetzt hab ich tatsächlich einen automatischen Bildorientierer geschrieben

Mit zwei Bildern, gibt's auf Knopfdruck eine Orientierung und eine grobe 3D Punktwolke. Dichtes Punktmatching ist da noch nicht drin - momentan sind's ~2100 Punkte - es könnten sicher so um die 4'000 - 10'000 werden.

(Ganz automatisch ist es nicht. Ich muss noch ~4 Schlaufen in der Bündelausgleichung 'simulieren'. Ich drücke einfach 4-mal den Knopf und verändere iterativ die Genauigkeit

Wäre aber problemlos auch automatisierbar).

Edit: Wen's interessiert, hier ist das Resultat von Photosynth:

http://photosynth.net/view.aspx?cid=c71 ... cba1398b86

Jetzt muss ich nur noch einen Weg finden, die Punktwolke zu exportieren - es würde mich nämlich sehr interessieren, wie flach die Wand ist, die Photosynth extrahiert. Der Photosynth 3D-Viewer ist ja nicht zu gebrauchen.

Hypothraxer

Ich hätte, zur Abwechslung, eine Allgemeine Frage:

Ich habe zwei Files mit X/Y Werten - in diesen Files gibt's Duplikate. Und die möchte ich loswerden

Die erste, und wohl langsamste Idee:

Ich sortiere die Files in jeweils zwei Arrays - bei jedem einsortieren schaue ich, ob es im 'linken' Array schon so eine X/Y Kombination schon gibt - und wenn ja, schaue ich im 'rechten' Array nach, ob an der selben Stelle ebenfalls das selbe steht, wie das, was ich einsortieren will.

Problem: Das wird gegen Ende hin recht lange dauern (gut - grösser als ~6'000 Zeilen dürfte es nicht sein).

Gibt's da noch eine schnellere Variante?

Edit 1: Photosynth generiert ein paar krasse Ausreisser

Edit 2: Danke noch für den Link mit den EOF-Folien, Dirk! Die ist Gold wert.

Daniel · **Joined:** 18.10.2004 13:48 **Posts:** 757

Hypothraxer wrote:

Ich habe zwei Files mit X/Y Werten - in diesen Files gibt's Duplikate. Und die möchte ich loswerden

Die Punkte einfach aus beiden Dateien sequentiell einlesen und in eine BVH (Bounding Volume Hierarchie) einsortieren, dabei bei jedem Punkt prüfen ob schon ein hinreichend ähnlicher Punkt vorliegt. Dann hast du auch gleich die Duplikate innerhalb einer einzelnen Datei eliminiert. Wenn du das nicht willst, aus der ersten Datei ohne weitere Prüfung einsortieren und aus der zweiten nur prüfen (und die noch nicht vorhandenen übernehmen), aber nicht einsortieren. Wenn du minimale und maximale Positionen kennst und innerhalb dieser Bounding Box die Punkte halbwegs regelmäßig verteilt sind, sollte ein simples Grid ausreichen. Wenn du nicht auf exakte Gleichheit prüfst, sondern Gleichheit bis zu einem gewissen Maximalabstand annimmst, mußt du noch darauf achten, daß zwei "gleiche" Punkte in unmittelbarer Nähe zu einer Grenze im Grid/BVH unterschiedlich einsortiert werden können.

Hypothraxer

Ich werds mir mal bei Gelegenheit ansehen - die BVH tönt sehr interessant und wäre genau das, was ich brauche. Ich habs jetzt mal aus Zeitgründen so gemacht, dass ich jeden Punkt mit dem schon einsortierten Array prüfe - geht auch, aber halt nicht so performant. Danke für den Tipp!

Hypothraxer

Nach einigen Optimierungen, sieht es so aus, als würde der Algorithmus langsam durchstarten - auch wenn er momentan noch _sehr_ langsam ist

17'000+ Punkte aus 2 Bildern sind nicht übel - v.a. weil da noch etwas Verbesserungspotential drin steckt - und man nichts machen muss, als einen Knopf zu drücken und die nächsten 30 Minuten Tee zu trinken.

Bild