Laden...

6-teiliges Puzzle lösen

Erstellt von gigagames vor 8 Jahren Letzter Beitrag vor 8 Jahren 3.068 Views
G
gigagames Themenstarter:in
13 Beiträge seit 2015
vor 8 Jahren
6-teiliges Puzzle lösen

Hallo,
ich habe ein paar Puzzle Bilder, die ich via c# lösen möchte
Das Puzzle besteht aus 6 Teilen, diese sind zusammen in einen Bild (.png) -> Siehe anhang
Die lösung dies Puzzles wäre :
5-1-2
4-3-6

Das Bild habe ich jetzt in 6Teile unterteilt und die weißen ränder entfernt

Nun kommt der schwere teil, das Puzzle lösen..
wie geh ich am besten vor ? Mir fällt nicht wirklich was ein.
Brutforce geht nicht, da man nur 1 versuch hat.

danke
lg giga

J
251 Beiträge seit 2012
vor 8 Jahren

da man nur 1 versuch hat.

Naja wenn das bei den Spezifikation mit der Bedingung..püüh da bleibt wohl try'n'Error und genau ein mal 😄

Weißt das Programm zum Zeitpunkt des Lösens wie das Ergebnis aussieht?

[Edit] Man könnte sich die Pixel am Rand betrachten und versuchen sie mit den anderen Stücke zu verbinden [/Edit]

S
322 Beiträge seit 2007
vor 8 Jahren

Hallo gigagames,

interessante Aufgabe.
Die Bilder können auch frei gedreht sein?

Ich würde so rangehen:

  • Kantenbild (binär) erstellen (z.B. mit Emgu-CV)
  • Von jedem Bild den Rand (oben, rechts, unten, links) jeweils als Byte-Array extrahieren
  • Nun die Ränder miteinander vergleichen und das best passende finden
  • Merke die Bilder die an zwei Seiten keinen Partner haben (Ecken)
  • Nun ein Eck-Bild an die erste stelle hinlegen und dann nacheinander alle passenden Bilder positionieren.

Es kann dann natürlich sein dass das zusammengesetzte Bild insgesamt verdreht ist, dass kann man nicht so einfach bestimmen wie rum das Bild gedreht gehört. Wenn aber die Bilder nicht verdreht sein können dann ist es noch einfacher.

Viel Erfolg dabei 😉

D
985 Beiträge seit 2014
vor 8 Jahren

Jedem, dem es noch nicht aufgefallen ist, sei gesagt, dass zwischen den Bilder immer ein paar Pixel fehlen. Somit läuft ein einfacher Kantenvergleich ins Leere 😉

G
gigagames Themenstarter:in
13 Beiträge seit 2015
vor 8 Jahren

Weißt das Programm zum Zeitpunkt des Lösens wie das Ergebnis aussieht?
Leider nein, wenn es so wäre, wäre kein problem da 😦

Hier noch mal 2 Bilder

  1. Solved (Anhang)
  2. "Durcheinandner"

Jedem, dem es noch nicht aufgefallen ist, sei gesagt, dass zwischen den Bilder immer ein paar Pixel fehlen. Somit läuft ein einfacher Kantenvergleich ins Leere 😉

Das problem ist oben zusehen, ist mir vorher auch nicht aufgefallen -.-

Hinweis von MrSparkle vor 8 Jahren

Link auf Filehoster entfernt.

Bitte beachte [Hinweis] Wie poste ich richtig?, Punkt 6.1

J
251 Beiträge seit 2012
vor 8 Jahren

Es fehlen Pixel... mhh kam mir zwar bissel spanisch vor... Wenn ich mir die Lösung betrachte, weicht sie stark von meiner Definition eines klassischen Puzzles ab 😄

Den Kantenvergleich könnte man erweitern mit einer Abweichungsrate in wie weit sich ein Pixel in etwa verschieben kann. Selbst wenn kein Pixel fehlen würde, müssen nicht alle Pixel auf einer x- bzw. y-Achse sich befinden. Also war eine gewisse Streuung schon gegeben.

G
gigagames Themenstarter:in
13 Beiträge seit 2015
vor 8 Jahren

@Jamikus - zwischen den puzzel stücken sind in diesen "gelb" ton ränder, dadurch fällt das mit denn fehlenden pixeln weniger auf (optische täuschung ?)


Wie würde das mit einer "Abweichungsrate" aussehen ?
Einen "Kantenverglich" habe ich schon mehr oder weniger :


 for(int i = 0; i < bitmapMatchinPoints.GetLength(0) - 1; i++) //Anzahl der Bilder -1 (5)
            {
                for(int j = i + 1; j < bitmapMatchinPoints.GetLength(1); j++) //Anzahl der Bilder - wobei das anfangs bild i + 1 ist (da man ja 2bilder in jeden durchlauf überprüft)
                {
                    for(int side = 0; side < 1; side++) //4 Seiten
                    {
                        if(side == 0) //top - bottom vergleich von der oberen seite mit der unten seite eine2ten bildes
                        {
                            for(int k = 0; k < fastBitmaps[i].Width; k++) //Jeder pixel der oberen seite von bild 1 wird mit der unten von bild 2 verglichen 
                            {
                                Color A = fastBitmaps[i].GetPixel(k, 0); //Bild1 Farbcode an pixel k, der höhe 0 (TOP)
                                Color B = fastBitmaps[j].GetPixel(k, fastBitmaps[j].Height - 1); //Bild 2 Farbcode an pixel k, der höhe des Bildes (Bottom)

                                Red = A.R - Black.R;
                                Green = A.G - Black.G;
                                Blue = A.B - Black.B;
                                int distance = Red * Red + Green * Green + Blue * Blue;
                                if(distance < Toleranz) //Vergleich ob der Pixel in Bild 1 in Toleranzbereich liegt und noch als "Schwarz" durchgeht
                                {

                                    Red = B.R - A.R;
                                    Green = B.G - A.G;
                                    Blue = B.B - A.B;
                                    //distance = Red * Red + Green * Green + Blue * Blue;

                                    distance = (A.R - B.R) * (A.R - B.R) + (A.G - B.G) * (A.G - B.G) + (A.B - B.B); //Vergleiche Pixel von Bild1 mit Bild2 liegen diese in Toleranzbereich


                                    if(distance < Toleranz) //Wenn in Toleranzbereich dann
                                    {
                                        bitmapMatchinPoints[i, j, 0] = bitmapMatchinPoints[i, j, 0] + 1; //Zähle denn Zähler an dieser stelle hoch
                                        bitmapMatchinPoints[j, i, 1] = bitmapMatchinPoints[j, i, 1] + 1; //Zähle denn Zähler an dieser stelle hoch
                                    }
                                }
							}
						}
					}
				}
			}				

Edit:
was ich mir auch noch verstellen könnte das es klappt,
Der rand ist zwischen jeden bild 10Pixel breit, und der rand ganz außen 5Pixel Breit,
Vlt würde es klappen wenn man jedes der Bilder an rand 5pixel weiterzeichnet (dafür müsste man schauen immer am rand schauen wie die 3vorherige pixel verlaufen und so weiterzeichnen)
Wäre das so vlt lösbar ? (wobei ich hier keine wirkliche idee hätte wie ich das umsetzen soll)

J
251 Beiträge seit 2012
vor 8 Jahren

Die Abweichung hätte die selbe Funktion wie die Farb-"Toleranz".
Wenn ich in deinen Code überschlage wird jeder Pixel mit seinen gegenüber Pixel verglichen. Als Abweichung könnte man z.B. 2-3 Pixel nach vorn bzw. hinten mit nehmen. Eine Linie, die senk - oder waagerechts wäre, würde auf 1:1 positiv reagieren. Dies ist aber bei deinen Beispiel nicht immer gegeben (besonders wegen den fehlenden Pixel).

Um evtl. Fehler gegenzuwirken würde ich dazu die Anzahl der möglichen Verbindungen mit jeden Puzzle-Teil vergleichen. So höher die Anzahl umso wahrscheinlicher, dass es ein Puzzlepaar ist.

Fehler sind aber dennoch dann nicht auszuschließen, so dass nicht passende Teile mit einander verbunden werden.
Mit paar Tests könnte man die eine oder andere Stelle verbessern bzw. jemand hat nen besseren Gedankengang 😃

G
gigagames Themenstarter:in
13 Beiträge seit 2015
vor 8 Jahren

Um evtl. Fehler gegenzuwirken würde ich dazu die Anzahl der möglichen Verbindungen mit jeden Puzzle-Teil vergleichen. So höher die Anzahl umso wahrscheinlicher, dass es ein Puzzlepaar ist.

Wie meinst du das ?

jemand hat nen besseren Gedankengang 😃

Siehe mein edit, wäre das vlt so ne lösung ?

J
251 Beiträge seit 2012
vor 8 Jahren

Sicherlich könnte man weiterzeichnen. Dabei würde evtl. Richtungswechsel/Abweichungen nicht bedacht.

Das mit der Anzahl der mög. Verbindungen ist so gemeint, dass wann immer ein Pixel von Puzzle A mit ein Pixel von Puzzle B passt (inbegriffen Farb- und Bereich-Toleranz) ein möglicher Verbindungpunkt entsteht.
Eine Kante hat n-Verdingungspunkte. Wenn man also ein Puzzle-Teil mit jedes andere Puzzle-Teil vergleicht an der Kante, erhalte ich im optimalsten Fall für jedes Teil eine verschiedene Anzahl an mögl. Verbindungspunkte. Dadurch vertraue ich der höchsten Anzahl mehr als die niedriegste.

[Edit]
Evtl. würde ich die dominierde Farbe nicht betrachten. Bei dir bsp. Sepia? Als Hintergrund-Farbe bekommt man sehr viele mög. Verbindungspunkte.
[\Edit]

G
gigagames Themenstarter:in
13 Beiträge seit 2015
vor 8 Jahren

Die Hintergrundfarbe (dies Gelb) ignoriere ich ja eh schon :


Red = A.R - Black.R;
                                Green = A.G - Black.G;
                                Blue = A.B - Black.B;
                                int distance = Red * Red + Green * Green + Blue * Blue;

(Siehe in code oben)
Da überprüfe ich ja, ob der pixel schwarz ist


Also mit der Abweichung so machen :


if(distance < Toleranz)
                                {
                                    for (int l = -3; l < 4; l++)
                                    {
                                        if (((k + l) < (fastBitmaps[j].Width - 1)) && (k + l) >= 0)
                                        {
                                            Color B = fastBitmaps[j].GetPixel((k + l), fastBitmaps[j].Height - 1);
                                            Red = B.R - A.R;
                                            Green = B.G - A.G;
                                            Blue = B.B - A.B;
                                            distance = Red * Red + Green * Green + Blue * Blue;

                                            if(distance < Toleranz)
                                            {
                                                bitmapMatchinPoints[i, j, 0] = bitmapMatchinPoints[i, j, 0] + 1;
                                                bitmapMatchinPoints[j, i, 1] = bitmapMatchinPoints[j, i, 1] + 1;
                                            }
                                        }
                                    }

Richtig ?
Wenn ja, wie schaue ich am ende ambesten wo die meisten matching punkte sind ?
da ich ja diverses berücksichtigen muss:
Wo hat welches bild die meisten punkte und mit welchen bild.
Das das andere Bild an der stelle mit denn bild auch die meisten matching punkte oder hat es mit nen anderen bild mehr ... ?

5.657 Beiträge seit 2006
vor 8 Jahren

Hi gigagames,

Richtig ?

Gegenfrage: Wird denn das erwartete Ergebnis ausgegeben?

Falls nicht, solltest du deinen Code debuggen und testen, um herauszufinden, wo deine Berechnungen nicht dem erwarteten Ergebnis entsprechen. Wenn du dir geeignete Unit-Tests schreibst, kannst du deinen Code schrittweise anpassen und verbessern, bis alle Tests erfolgreich durchlaufen. Siehe dazu: [Artikel] Unit-Tests: Einführung in das Unit-Testing mit VisualStudio.

Prinzipiell scheint mir dein Ansatz aber nicht besonders erfolgversprechend zu sein. Auch wenn deine Einzelbilder auf einem festgelegten Raster liegen (was die ganze Sache schon einfacher macht), geht es eher in Richtung der Image stitching-Verfahren, bei denen mehrere Einzelbilder zu einem Bild zusammengefügt werden, so daß dabei möglichst wenig Artefakte entstehen. Deine Annahme, daß die beiden Ränder der zusammengehörigen Bilder die gleichen Pixelwerte aufweisen, wäre jedenfalls schon verkehrt, wenn es keine zusätzlichen Bild-Ränder geben würde. Im Grunde gibt es immer nur eine bestimmte Wahrscheinlichkeit, nach der zwei Bilder zusammenpassen, wie Jamikus bereits erwähnte:

Um evtl. Fehler gegenzuwirken würde ich dazu die Anzahl der möglichen Verbindungen mit jeden Puzzle-Teil vergleichen. So höher die Anzahl umso wahrscheinlicher, dass es ein Puzzlepaar ist.
Wie meinst du das ?

Du mußt die Wahrscheinlichkeit berechnen, nach der zwei Bilder an einem bestimmten Rand zusammengehören. Dann wählst du jeweils die Reihenfolge mit der höchsten Wahrscheinlichkeit aus.

Christian

Weeks of programming can save you hours of planning