Hallo,

ich benötige etwas Unterstützung beim Erstellen eines Programms zum Lösen einer hacker.org challenge.

Gegeben ist ein Bild mit spiralförmig angeordneten überlappenden Kreisen.
Jeder Kreis repräsentiert ein Bit eines Bildes im png Format.
Ein weißer Kreis entspricht einer Eins und Kreis mit blaugrüner Farbe entspricht einer Null.

Hier ist ein Link zu dem Bild: bit.ly/atDQSn
Die Spur beginnt sich in der Mitte und die ersten Bits lauten:

10001001 ‰
01010000 P
01001110 N
01000111 G
...


Mein bisheriger Ansatz war folgender:
1. Startposition in der Mitte des oberen ganzen Kreises
2. einen schwarzen Kreis zeichnen, der diesen Kreis überdeckt
3. jeweils ein Pixel nach rechts, links, oben und unten gehen und prüfen in welcher Richtung die meißten fabigen Pixel innerhalb eines Kreises mit gleichem Durchmesser entalten sind.
4. Startposition um ein Pixel in die ermittelte Richtung verschieben
5. weiter bei 2.

Leider bekomme ich das alleine nicht implementiert, daher bitte ich um etwas Unterstützung dabei.


Viele Grüße,
Fibber

Hallo,

Mittels IrfanView stark vergrößert und auf einzelne Pixel geklickt:
Dein Blaugrün ist RGB(35,182,53) und das andere ist weiß RGB(255,255,255).Der schwarze Rand eine Mischfarbe und die Umgebung ist reines schwarz.
Der Durchmesser müsste 12 Pixel und der Abstand der Mittelpunkte 2 Pixel sein. Der mittlere Spiralenabstand ist wohl 32 Pixel.
de.wikipedia.org/wik...rchimedische_Spirale
r_spiral(phi) = phi* 32/(2*pi), hier läuft sie aber "links" herum also -phi*32/(2*pi)
Diese 2 Pixel entsprechen dem Bogenmaß also deltaPhi = 2/r_spiral(phi)
Die Tangente an die Spirale im Punkt phi steht da leider nicht, grob 90 Grad zu phi je größer phi desto besser.
Ist ja nicht wichtig, der nächste Mittelpunkt ist dank delta_phi in etwa bekannt.
Jetzt kann man ja wegen mir 3x3 Punkte testen.Anhand des R-Wertes lässt sich dan entscheiden was da wohl sein soll und auch abschätzen wie groß die radiale Abweichung ist.

Gruß Horst

Hallo,

die Spirale ist ja nicht sehr spiralig
Im angehängten Programm lade ich das "Hackerbild" , das ich als BMP vorher abgespeichert habe.
Dann filtere ich mit der RGB-Farbe (NOT(31),NOT(127),Not(127))
Alles was bei Rot kleiner 32 ist damit 0 bei Rot. dies gilt für Farbwerte < 128 bei Grün und Blau ebenfalls.
Damit verbleiben nur noch 14 statt ~11000 verschiedene Farben im Bild und der Übergang zwischen den Kreisen ist besser sichtbar
Dieses Bild wird gespeichert.
Wenn grün und blau je 128 sind entscheidet der Rotwert darüber, ob 0 odser 1 vorliegt.
Die Spirale habe ich nur testhalber darübergezeichnet. Die Abweichungen sind zu groß.

Gruß Horst

Hallo,

@fibber:
Ich habe mal auf simple Art versucht in der Spur der Spirale zu bleben, aber das war wohl nichts.
Ich habe ausgehend vom Ende einen Halbkreis um den geratenen neuen Mittlpunkt( einfach im Bogenabstand 2 im Gegenuhrzeigersinn mit Radius des letzten Punktes) mit Radius 6 geschlagen.
Auf dem Halbkreis habe ich den Beginn von Farbe und das verlassen dieser mit den entsprechenden Winkel festgehalten.
Oweia! Die Mittelung des Winkels führt zu besonders merkwürdigen Beweungen des Mitteltpunktes.
Nur mit Radius=6 und Mittelpunktsabstand zweier Kreise von 2 blieb dieses Kontrukt in der Nähe der Spirale ohne soweit auszureißen, dass ein Spurwechsel stattfand.
Anbei ein kleiner Ausschnitt, wo die enstandenen Mittelpunkte eingtragen sind.
Ich gehe jetzt mal dazu über, den berechneten neuen Mittelpunkt auf dessen Verbindungslinie zum Ausgangspunkt der Spirale in der Mitte des Bildes zu verschieben, sodass er dann gleich weit weg zum schwarz zu liegen kommt.Dazu nehme ich wieder das Originalbild.Es entspricht ja dann dem klassischem linefollower beim Robotern.
Ähnlich: www.youtube.com/watch?v=ppWf3Edw9Z4
Also etwas vorausschauend, damit die Richtung besser stimmt.

Wie weit bist Du gekommen?

Gruß Horst

Ich würds so machen:

Erstmal die Farbwerte "normieren" d.h. alle Pixel durchgehen und entscheiden: Weiß, Blau, oder Schwarz? Dann hast du ja nur noch drei Farbwerte, um die du dich kümmern musst.

Als nächstes legst du den Startpunkt fest, der hat ja einen festen Wert, und folgst dann dieser Schleife:

1. Pixel am Startpunkt auswerten und Bitwert notieren.
2. Eine Methode Aufrufen die - ähnlich wie in Paint - ein Feld von gleicher Farbe übermalt, Parameter ist hier der Startpunkt, so übermalst du den Kreis, den du gerade ausgewertet hast.
3. Ausgehend vom Startpunkt, suchst du jetzt den nächsten Punkt der nicht schwarz ist, das ist dein neuer Kreis. Also: Startpunkt auf den gefundenen Pixel setzen.


Da fehlt noch eine geeignete Abbruchbedingung, aber die wird wohl nicht allzu schwer zu machen sein, die Position des letzten Kreises kannst du ja "manuell" feststellen, und die Schleife abbrechen, wenn man in Punkt 3 an diesen Punkt kommt.

Hallo,

ich komme ja schon einigermassen an.
Nächste Woche mehr, falls es mich noch interessiert...

Gruß Horst

Was bei diesem Bild ggf auch helfen könnte, wäre eine Hough-Kreis-Transformation für alle lokalen Bereiche rund um den aktuallen Startpunkt herum. Damit dürfte man relativ gut die Umrisse der Kreise finden können ...

Auch dürfte durch Opening\Closing der "Kontrast" zwischen zwei Elementen zu verbessern gehen.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Hallo,

ich habe das Bild mit Gimp auf eine schmale einfarbige Pixelspur reduziert, welche mittig durch die Spirale verläuft. Mit Hilfe dieses Bildes sollte es einfacher sein der Spirale zu folgen.

Moderiert von Narses: BMP->PNG

Hallo,

ist GIMP in Delphi geschrieben
Eine Farbe macht die Sache so schön kompakt.
Ich probiere es wie der Roboter im Video, etwas voraus links und rechts neben der Spirale zu bleiben, obwohl das unten im Bild sehr schwer ist, da dort die Spirale sich zur Berührung nähert, da gibt es kein clBlack aber eine Minimum zu den Nachbarn. Noch haut er ab und zu ab.
Erstmal BostonLegal zur Entspannung schauen
Gruß Horst

Horst_H hat folgendes geschrieben :

ist GIMP in Delphi geschrieben

Leider nicht, aber 5 Minuten Vorarbeit mit Gimp spart ein vielfaches an Zeit beim Programmieren

Hallo,

einfaches zählen von Hand, hätte auch schon ein Ergebnis gebracht

Gruß Horst

Wow, mit so viel Interesse an dieser Aufgabe hab ich nun wirklich nicht gerechnet .

Ich habe eure Beiträge grad schonmal kurz überflogen, und werde mich heute abend nach der Arbeit ausgiebiger damit beschäftigen. Bis dahin schonmal vielen Dank für eure Unterstützung.

Viele Grüße,
Fibber