Free-Hack Allgemeiner Coding Wettbewerb

[blackberry]

http://webctf.kilu.de/blackberry/image.php
Da die Frage nach einem solchen Wettbewerb aufkam, gibt es jetzt auch einen ;)

Bei diesem Wettbewerb stelle ich die Aufgabe und wenn es gut läuft, gibt es sicher auch noch weitere Wettbewerbe.

Also um was geht es (Hintergrund):
Es wurde immer mal wieder gefragt wie man CAPTCHAs in Account-Checkern anzeigt.
Diese Aufgabe soll die Grundlagen eines OCR-Systems (Optical Character Recognization) vermitteln.
Der Einfachheit halber geht es dabei jedoch nicht um das Erkennen von Buchstaben, sondern von einfachen geometrischen Figuren (genauer gesagt Dreiecke, Vierecke und Kreise).

Um was geht es also genau?
Ein Bild, das jedes mal von einem PHP Skript neu generiert wird (also gibt es immer genug Testobjekte) kodiert einen 4-Zeichen langen String (das Verfahren wird auf der Webseite erläutert), den es zu dekodieren gillt.

Welche Programmiersprachen sind erlaubt?
Prinzipiell alle.

Wieviel Zeit steht zur Verfügung?
Ich habe so an 3 Wochen gedacht.
Also genug Zeit.
Abgabeschluss: 02.10.2009

Wie Parse ich Bilder?
Das müsst ihr wissen.
Ich kann folgendes Sagen:
mit PHP solltet ihr die GD Funktionen nutzen ( http://us2.php.net/manual/en/book.image.php )
mit C bzw. C++ empfiehlt sich ebenfalls GB ( http://www.libgd.org )
hpoc_ meinte mit Perl könnte man ImageMagick nutzen ( http://www.imagemagick.org/script/perl-magick.php )
ThePapst hat gesagt die "Graphics" Klasse aus dem "System"-Namespace stellt unter .NET die nötigen Methoden zur Verfügung.
Wenn jemand sonst noch Tipps hinsichtlich der Bildbearbeitung in anderen Sprachen hat, kann er diese gerne hier posten.

Gibt es Preise?
Es wird momentan noch über mögliche Preise nachgedacht, jedoch möchte ich nicht in Aussicht stellen, dass es welche geben wird.
Wer mitmacht, macht das in erster Linie wegen dem Spaß am Programmieren und Lösen von Problemen.
Also kurz gesagt: vielleicht gibt es was, aber macht euch keine Hoffnungen.

Gibt es sonst noch was zu beachten?
Die vom Skript "image.php" (siehe Link unten) erzeugten Bilder sind Paletten-Bilder.
Dies macht diese zwar kleiner, aber die echten RGB-Werte auszulesen etwas kniffliger.
Also überlegt euch was um Paletten-basierte Bilder in TrueColor-Bilder umzuwandeln, sonst werden eure Resultate etwas verwunderlich.

Wie groß wird das Programm?
Schwer zu sagen. Meine Lösung in C umfasst zwei Dateien und eine Summe von 285 Zeilen (nein, ich nehme nicht Teil, ich wollte meine Aufgabe nur testen).
Da das Programm in C geschrieben ist, kann es sein, dass man in Sprachen wie Perl weniger Zeilen/Zeit braucht, da man dabei nicht so auf Datentypen usw. achten muss.
Gebraucht habe ich ~2 Stunden - ausgegangen davon, dass ich mich mit LibGD2 schon auskannte, eine Idee zur Umsetzung hatte und sowas ähnliches schonmal gemacht hatte.
Ich meine also 3 Wochen sind für so eine Aufgabe genug Zeit - auch für eventuelle Optimierung und Feinabstimmung.

Was wird bewertet?
In erster Linie die Funktionalität. Wenn das Programm die Aufgabe zuverlässig (also bei jedem Bild!!) erfüllt ist das schonmal ein Pluspunkt.
Im weiteren wird die Art der Lösung bewertet: wie effizient wird das Bild geparst, auf welche Art werden die Figuren erkannt (dabei gibt es zweifellos mehrere Möglichkeiten).
Ob die Lösung die schnellste ist, oder nicht wird nicht bewertet (allein schon deshalb, weil die Sprachen an sich unterschiedliche Laufzeiten besitzen).
Eine Lösung die mehr Aufwand (Code, oder komplexere Überlegungen) benötigt, aber das Problem auf kreative Weise löst wird auf keinen Fall schlechter bewertet.

Wer bewertet?
Das Free-Hack Team (in erster Linie wahrscheinlich die Mods der entsprechenden Sections).

Muss das Programm die Bilder von image.php downloaden und dann parsen?
Das wäre zwar nett, aber ich stelle es nicht als Anforderung.
Bei dem Wettbewerb sollten alle gängigen Sprachen eingesetzt werden können.
Das Bild zu downloaden hat wieder mit Sockets und Networking zutun.
Das mag in einigen Sprachen einfach sein, ist es jedoch nicht in allen und es wäre darum unfair Leuten, die gerne in Sprache XYZ programmieren abzuverlangen einen eigenen HTTP-Client zum Download zu schreiben, während andere nur ein Paket importieren und eine Funktion aufrufen um das selbe zu bewerkstelligen.
Die Antwort auf die Frage ist also: nein, die Bilder können auch auf der Festplatte sein.
(das soll aber niemanden hindern, der das trotzdem gerne einbauen würde)

Wo wird abgegeben?
Bei mir. Am besten per PM (die Sources werden am Schluss alle veröffentlicht).
Bitte nicht hier reinschreiben, weil es bei dieser Aufgabe hauptsächlich um das erkennen des Problems und finden eines Lösungswegs dafür geht (die Umsetzung ist weniger schwierig) und das Posten von Sources den anderen Teilnehmern diesen Prozess abnehmen würde - ihr würdet also nur der Konkurenz helfen.

Anforderungen an den Sourcecode?
Es werden keine fertigen Programme akzeptiert - das sollte klar sein.
Der Sourcecode sollte also gut lesbar sein (Einrücken und ein guter Stil sind Pflicht!!) und Kommentare enthalten.
Zum Thema Kommentare: jeder weiß was eine Funktion ist, also kommentiert bitte euren Denkprozess und dessen Umsetzung im Code und nicht jede Zeile.

Wer beantwortet meine Fragen?
Der Wettbewerb wurde intern diskutiert und die Moderatoren für die einzelnen Programmiersprachen, die hier im Forum gängig sind stehen dahinter.
Solltet ihr also Fragen bezüglich Bildverarbeitung haben könnt ihr die entsprechenden Moderatoren ansprechen.
Solltet ihr Fragen zu den Bildern oder der Aufgabenstellung haben bin ich euer Ansprechpartner (am besten hier im Thread).

Wo kann ich anfangen?
Wenn ihr hier angekommen seid und Lust auf die Aufgabe habt, dann findet ihr eine genaue Beschreibung des Sachverhalts, sowie den Sourcecode des Bildgenerators und Beispiele dort:
http://webctf.kilu.de/blackberry/ (http://webctf.kilu.de/blackberry/)
(danke an tmh für's uploaden <3)

Wer hat schon abgegeben?
(1) bl0b (http://free-hack.com/member.php?u=56327); Sprache: C++; Zeilen: 90; Arbeitszeit: 30 min (nach seiner Angabe); schöner Code, schöne Lösung :)
(2) naroht (http://free-hack.com/member.php?u=54408); Sprache: Java; Zeilen: 241; sogar mit GUI und lädt die Bilder auf Knopfdruck neu von der Webseite - nett
(3) Mr. Loom aka crusher (http://free-hack.com/member.php?u=38917); Sprache: C; Zeilen: 225; vollkommen anderer Ansatz als bei den ersten beiden - funktioniert einwandfrei
(4) h0yt3r (http://free-hack.com/member.php?find=lastposter&f=725); Sprache: Perl; Zeilen: 75; hübsch
(5) EBFE (http://free-hack.com/member.php?u=55471); Sprachen: Java + Prolog; Zeilen: 92;
(6) -tmh- (http://free-hack.com/member.php?u=35776); Sprache: Delphi; Zeilen: 262;
(7) finsternacht (http://free-hack.com/member.php?u=62326); Sprache: Python; Zeilen: 250;
// die Nummerierung entspricht den Abgabezeiten und stellt keine Wertung dar!
// Zeilenangaben mit Kommentaren

Viel Spaß!
mfG. BlackBerry

[Atbash]

Coole Idee, werde auf jeden Fall versuchen mitzumachen, hab allerdings keine Ahnung von GDI+.
Wünsche allen Teilnehmern viel Glück.

Grüße
atbash

[Hu5eL]

ich verstehe diese berechnung nicht... kann das einer erklären
wie soll ich an den "index" des arrays kommen?
gibt doch nur folgende möglichkeit:
kreis, dreieck, viereck,
farbe.

stellt die farbe den index da ?!

ps: perl ist auch erlaubt... daffür gibts auch gd

[blackberry]

@Hu5eL
Da du das dem Anschein nach in Perl machen willst hilft dir vielleicht dieses kleine Snippet:


#!/usr/bin/perl

use warnings;
use strict;

# Großbuchstaben Array
my @_A = split(//, "ABCDEFGHIJKLMNOPQRSTUVWXYZ");
# Kleinbuchstaben Array
my @_a = split(//, "abcdefghijklmnopqrstuvwxyz");
# Zahlen Array
my @_0 = split(//, "0123456789");

# es sind 4 Figuren --> 4 Zeichen zu dekodieren
for(my $zeichenZahl = 0; $zeichenZahl < 4; $zeichenZahl++)
{
# [...]

my $figur = "Dreieck"; # Hier die Figur bestimmen

my @array; # der Array in dem wir den Zeichen-Index suchen
if ($figur eq "Dreieck")
{
@array = @_A;
}
elsif ($figur eq "Viereck")
{
@array = @_a;
}
elsif ($figur eq "Kreis")
{
@array = @_0;
}

my $zahl; # Zahl aus dem Bild holen (wie? - siehe Beschreibung)
my $index = 5; # aus Zahl berechnen --> Zahl = (Index * 7) + 50 nach Index umstellen

# gibt in diesem Beispile "Zeichen: F" aus
print "Zeichen: $array[$index]\n";
}

Dort wo ich Werte eingetragen habe sollst du meistens die echten berechnen...

Ansonsten nochmal schnell die Theorie für alle:
Die kodierten Zeichen sind entweder Großbuchstaben, Kleinbuchstaben, oder Ziffern.

Ist die Figur ein Dreieck, so stellt der Index einen Großbuchstaben dar.
Ist die Figur ein Viereck, so stellt der Index einen Kleinbuchstaben dar.
Ist die Figur ein Kreis, so stellt der Index eine Ziffer dar.

Ein Pixel im Bild besteht aus 4 Bytes.
Diese stellen folgendes dar:
Alpha-Wert des Pixels (die Transparenz - hab ich nur der Vollständigkeit halber genannt - bei dieser Aufgabe ist dieser Wert unwichtig)
Rot-Wert des Pixels
Grün-Wert des Pixels
Blau-Wert des Pixels

Ein Pixel in einer Figur (z.B. einem Kreis) enthält entweder im Rot-Wert, im Grün-Wert, oder im Blau-Wert die für uns wichtige "Zahl" (siehe Gleichung auf der Webseite).
Die anderen Werte sind 0.

Beispiel:
Alpha = 0; Rot = 0; Grün = 123; Blau = 0;
---> Zahl = Grün = 123

Aus der Zahl kannst du durch Umstellen der Gleichung den Index berechnen.
Dieser Index ist der Index des gesuchten Zeichens im vom Figurentyp bestimmten Array.

Beispiel:
Figur = Dreieck
---> Array = Großbuchstaben (ABCDEFGHIJKLMNOPQRSTUVWXYZ)
Index = 5
---> gesuchtes Zeichen = F


mfG. BlackBerry

[D@go]

super Idee,
hab zwar noch keine Ahnung wie genau man da
am besten rangeht, aber das wird schon werden :D

werd sicher auch am Wettbewerb teilnehmen,
schonmal großes Lob für die Ausarbeitung des Wettbewerbs :)


LG
D@go

[SleiZer]

Klingt gut der Wettbewerb, werde mich auf jedenfall mal dran versuchen.

Das mit der Index Zahl und dem Farbwert ist mir nicht ganz klar ...

Im genannten Beispiel wäre es ja rgb(0.123.0)

Index = (Zahl - 50 ) / 7

Im unseren Beispiel kommt bei mir 10,43 raus und nicht 5!
Wo ist mein Denkfehler?

[blackberry]

123 = einmal auf der Tastertur rumgehackt - ich hab ja gesagt die Zahlen nicht ganz ernst nehmen.

Deine Lösung mit 10,43 wäre für dieses Ausgangsbeispiel jedoch korrekt.
Du hast das Problem folglich richtig erkannt - mach dir keine Sorgen ;)

[crusher]

3 Stunden Arbeit in C und die Sache war sauber geritzt.

[l4nk4b3l]

Hm, das berechnen ist kein Problem. Die Ausgabe auch nicht. Das Problem das ich habe ist das ich keine Ahnung habe wie ich die einzelnen Formen erkennen soll.. Habe bisher auch nie so etwas in der Art gemacht. Für ein paar allgemeine Tipps wäre ich sehr dankbar(Da ich es in C# umsetze).

Gruß,
Lankabel

[crusher]

Wenn du's so machen willst wie ich brauchst du dir nur die Ecken der Formen genau ansehen, dann ein wenig vergleichen und schon kann man die 3 Formen erkennen.

[blackberry]

@tmh
Da ich kein Delphi kann und es auch sinnlos wäre für ein "kleines" (??) Programm IDE + Compiler zu downloaden würde ich sagen:
src + .exe + kurze Beschreibung was benötigt wird (vielleicht will es sich KingC0bra mal ansehen... keine Ahnung) per PM.

Danke für die Teilnahme :)

[Sirect]

Kurze Frage:

Ich bin fertig, aber eine Schwäche hat das Tool. Kann es vorkommen dass 2 Formen die gleiche Farbe haben? Also Exakt die gleiche? Das würde dem Tool nämlich nicht bekommen :D

[crusher]

Natürlich können 2 Figuren die selbe Farbe haben.

[blackberry]

Wenn man zwei gleiche Zeichen hat, haben diese mit einer Wahrscheinlichkeit von 33.33% die selbe Farbe (da ja mit gleicher Wahrscheinlichkeit immer entschieden wird, ob ([7 * ZeichenIndex] + 50) den Rot, Grün oder Blauwert im Bild darstellt)

[finsternacht]

Hi, ich möchte an dem Wettbewerb mit Python teilnehmen.
Daraus ergeben sich für mich 2 Fragen:
A) meines Erachtens bräuchte ich PIL (Python Imaging Library), ist das erlaubt wenn ich die verwende?
B) soll ich auch eine .exe erzeugen? (zb mit py2exe)

[bl0b]

Habe mich jetzt nochmals hingesetzt und das ganze in 25 zeilen (inkl. ein paar Leerzeilen und nicht mehr als 1 Semikolon pro zeile) hingekriegt. Natürlich nicht mehr ganz so gut lesbar, aber noch immer valides C. Ausserdem denke ich, dass ich so ziemlich die effizienteste Methode gefunden habe die aufgabe zu lösen, lasse mich aber gerne eines anderen belehren.

So long
bl0b

[blackberry]

A) meines Erachtens bräuchte ich PIL (Python Imaging Library), ist das erlaubt wenn ich die verwende?
B) soll ich auch eine .exe erzeugen? (zb mit py2exe)

A) Ja.
B) Nein.

[krypt0n]

Gibt es wieder einmal so einen Wettbewerb, den ich eventuell episch für mich entscheiden könnte?

[Th3_Cr4xX]

@krypt0n
nicht wenn ich teilnehme ;)