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
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]
Hallo gigagames,
interessante Aufgabe.
Die Bilder können auch frei gedreht sein?
Ich würde so rangehen:
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 😉
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 😉
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
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 -.-
Link auf Filehoster entfernt.
Bitte beachte [Hinweis] Wie poste ich richtig?, Punkt 6.1
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.
@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)
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 😃
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 ?
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]
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 ... ?
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