Wie ich mit der Hilfe von Sobel-Feldman-Kantendetektion und Circle-Hough-Transformation einen Bot programmierte, um ein bestimmtes Captcha zu überwinden.
Vor geraumer Zeit spielte ich ein Browserspiel, bei dem man alle zehn Minuten eine Interaktion machen konnte, um seine Spielfigur zu verbessern. Da ich mich aber nicht alle zehn Minuten von meiner Arbeit oder dem Schlafen abwenden wollte, schrieb ich kurzerhand einen Bot, der dies für mich erledigen sollte. Die Spieleentwickler hatten dieses Szenario schon vorausgesehen und die Interaktion mit einem Captcha abgesichert. So wurde das Überwinden dieses Captchas zur eigentlichen Herausforderung meines Bots.
Das Captcha bestand aus einem Ausschnitt eines Fotos, meist eine Szene mit Geldscheinen und Münzen, in dem ein zusätzlicher Kreis in variabler Größe und Farbe eingezeichnet war. Zur Bestätigung des Captchas galt es den Kreis anzuklicken.
Für einen Menschen eine triviale Aufgabe, doch wie löst man es programmatisch?
Der Herr der Ringe #
Eine Suche nach “circle detection” (Kreiserkennung) lieferte einen recht plausiblen und intuitiven Algorithmus (beide Eigenschaften helfen dabei, ihn umzusetzen): Die Circle Hough Transformation.
Die Logik hinter der Hough-Transformation, benannt nach Paul V. C. Hough, ist denkbar einfach, aber genial: Für jeden Kantenpixel im Quellbild zeichnet man einen Kreis in einem Akkumulator. Da die Kantenpixel eines Kreise alle den gleichen Abstand vom Mittelpunkt des Kreises haben, treffen sie sich im Akkumulator im Kreismittelpunkt, wodurch dieser besonders hohe Werte enthält.
Die Kante geben #
Im Quellbild sind Kantenpixel solche, die einen starken Kontrast (Unterschied in der Helligkeit) zu Nachbarpixeln haben, in der Fachsprache: einen hohen Gradienten. Das ist auch intuitiv einfach zu erfassen: Sind benachbarte Pixel ähnlich hell oder gefärbt, kann dort keine Kante sein. Für diese recht häufig auftauchende Aufgabe der Kantendetektion gibt es auch entsprechend viele Algorithmen. Üblicherweise werden diese in der Bildbearbeitung als eine 3x3 Matrix definiert, welche eine Filteroperation auf ein Kernpixel und dessen acht Nachbarpixel abbildet.
Von den vielen Möglichkeiten habe ich mir den Sobel-Feldman-Operator,
benannt nach Irwin Sobel und Gary Feldman, ausgesucht. Als Vorlage
diente der Code von Neal Ziring, da dieser direkt
auf dem BufferedImage arbeitet. (Das ist nicht der performanteste Weg, aber ein einfacher).
Der Sobel-Feldman-Filter wandelt das farbige Originalbild in ein Bild mit hellen Pixeln an den Stellen, wo Kanten sind. Da dabei die Farbinformation weg fällt und durch den Wert des Gradienten ersetzt wird, erscheint das Gradientenbild als Graustufenbild.
Hierzu besitzt der Sobel-Feldman-Filter zwei Filter-Matritzen (sobelFeldmanX, sobelFeldmanY), die eine für
horizontale Kanten, die andere für vertikale Kanten. Die Ergebnisgradienten beider Detektionen werden anschließend
kombiniert (level = Math.abs(sumX) + Math.abs(sumY)).
// Die Filter-Matritzen für die horizontalen und vertikalen Kanten
private static int[][]sobelFeldmanX={{-1,0,1},{-2,0,2},{-1,0,1}};
private static int[][]sobelFeldmanY={{1,2,1},{0,0,0},{-1,-2,-1}};
/**
* Wandelt die RGB-Farbwerte in einen Helligkeitswert um
* hierzu http://www.songho.ca/dsp/luminance/luminance.html
*/
public static int lum(int r,int g,int b){
return(r+r+r+b+g+g+g+g)>>3;
}
/**
* Wandelt den RGB-Farbwert in einen Helligkeitswert um
* Hier wird der int-RGB Farbwert in seine drei Komponenten
* R, G und B aufgespalten
*/
public static int rgbToLuminance(int rgb){
int r=(rgb&0xff0000)>>16;
int g=(rgb&0xff00)>>8;
int b=(rgb&0xff);
return lum(r,g,b);
}
/**
* Führt einen Sobel-Feldman-Filter auf dem Bild aus und liefert die gefilterte Kopie.
* nach der Vorlage von Neal Ziring (http://en.allexperts.com/q/Java-1046/2011/5/java-edge-detection.htm)
*/
public static BufferedImage sobel(final BufferedImage image){
final BufferedImage resultImage=createBufferedImage(image.getWidth(),image.getHeight(),BufferedImage.TYPE_BYTE_GRAY);
final int width=image.getWidth();
final int height=image.getHeight();
int level;
for(int x=0;x<width; x++){
for(int y=0;y<height; y++){
level=255;
if((x>0)&&(x< (width-1))&&(y>0)&&(y< (height-1))){
int sumX=0;
int sumY=0;
for(int i=-1;i< 2;i++){
for(int j=-1;j< 2;j++){
sumX+=rgbToLuminance(image.getRGB(x+i,y+j))*sobelFeldmanX[i+1][j+1];
sumY+=rgbToLuminance(image.getRGB(x+i,y+j))*sobelFeldmanY[i+1][j+1];
}
}
// Kombination der horizontalen und vertikalen Gradienten
level=Math.abs(sumX)+Math.abs(sumY);
if(level< 0){
level=0;
}else if(level>255){
level=255;
}
}
resultImage.setRGB(x,y,new Color(level,level,level).getRGB());
}
}
return resultImage;
}
Nur die Harten kommen in den Garten #
Da der Kantendetektor für etwas schwachere Kanten auch viele kleine Werte liefert, habe ich das Bild noch durch einen Schwellwertfilter verarbeitet. Dabei werden nur Werte aufgenommen, die einen bestimmten Schwellwert übersteigen. Dies bringt auch zusätzlich den Vorteil, dass viele Kantenpixel wegfallen, zu denen dann keine Akkumulatorkreise gezeichnet werden müssen.
/**
* Führt einen Schwellwert-Filter auf dem Bild aus und liefert die gefilterte Kopie.
* Dabei werden alle Pixel, die einen kleineren Grauwert als der Schwellwert haben geschwärzt.
*/
public static BufferedImage threshold(final BufferedImage grayscaleImage,final int threshold){
final BufferedImage resultImage=createBufferedImage(grayscaleImage.getWidth(),grayscaleImage.getHeight());
final int width=grayscaleImage.getWidth();
final int height=grayscaleImage.getHeight();
final int rgbBlack=Color.BLACK.getRGB();
for(int x=0;x<width; x++){
for(int y=0;y<height; y++){
int rgb=grayscaleImage.getRGB(x,y);
if(new Color(rgb).getRed()>threshold){
resultImage.setRGB(x,y,rgb);
}else{
resultImage.setRGB(x,y,rgbBlack);
}
}
}
return resultImage;
}
Akkumulation #
Ausgehend vom Kantenbild wird nun für jeden hellen Pixel (jeden Kantenpixel) ein Kreis mit einem fixen Radius auf dem Akkumulatorbild “gezeichnet”. Es wird nicht wirklich gezeichnet, sondern ein Wert an der Position des Pixels erhöht oder akkumuliert, daher auch der Name Akkumulator. Im Prinzip ist der Akkumulator eine Art Histogram, der an den Stellen größere Werte anzeigt, an dem sich besonders viele Kreise treffen und an dem sich damit viele Kantenpixel mit gleichem Abstand befinden.
/**
* Führt einen Circle-Hough-Transform auf dem Bild aus und liefert den Akkumulator als Bild.
* Nach einer Vorlage der University of Southampton (http://users.ecs.soton.ac.uk/msn/book/new_demo/houghCircles/)
*/
public static BufferedImage hough(final BufferedImage edgeImage,final int radius){
final BufferedImage accumulatorImage=createBufferedImage(edgeImage.getWidth(),edgeImage.getHeight(),BufferedImage.TYPE_INT_RGB);
final int width=edgeImage.getWidth();
final int height=edgeImage.getHeight();
int x0,y0,accumulatorValue;
double t;
for(int x=0;x<width; x++){
for(int y=0;y<height; y++){
if(new Color(edgeImage.getRGB(x,y)).getRed()>0){
// Sehr oldschooliges Kreis zeichnen
for(int theta=0;theta< 360;theta++){
t=(theta*3.14159265)/180;
x0=(int)Math.round(x-radius*Math.cos(t));
y0=(int)Math.round(y-radius*Math.sin(t));
if(x0<width &&x0>0&&y0<height &&y0>0){
// Da wir das Ganze als graustufen Bild realisieren,
// ist nur einer der drei Farbkanäle ausreichend.
// Wir nehmen den roten Kanal,
// bei grau haben sowieso alle drei Kanäle den gleichen Wert
accumulatorValue=new Color(accumulatorImage.getRGB(x0,y0)).getRed();
accumulatorImage.setRGB(x0,y0,new Color(accumulatorValue+1,accumulatorValue+1,accumulatorValue+1).getRGB());
}
}
}
}
}
return accumulatorImage;
}
Ich habe hierbei das Berechnen der Kreispixel aus der Vorlage der University of Southampton übernommen, was zwar sehr inperformant ist, aber dafür leserlicher ist, in dem Sinn, dass man den Kreisalgorithmus recht gut erkennen kann:
// 360 Grad
for(int theta=0;theta< 360;theta++){
t=(theta*3.14159265)/180;
x0=(int)Math.round(x-radius*Math.cos(t));
y0=(int)Math.round(y-radius*Math.sin(t));
// ...
Weitaus effizientere Algorithmen zur Rasterung von Kreisen sind vorhanden, die insbesondere auf die aufwändige Berechnung der Winkelfunktionen verzichten. (Eine im Voraus berechnete Tabelle für die Werte der Winkelfunktion wäre ebenfalls effektiver). Ich hatte in einem anderen Zusammenhang schon mal den Midpoint-Algorithmus ausprobiert.
Nach der Akkumulation kann man dann nach den Pixeln suchen, welche die höchsten Akkumulationswerte haben. Dies sind die besten Kandidaten für den Mittelpunkt eines Kreises im Quellbild.
/**
* Ein Kreiskandidat.
*/
public static class HoughCircle {
public int x, y, radius, accumulator;
}
/**
* Liefert aus dem angegebenen Akkumulatorbild alle Kreiskandidaten.
*/
public static List<HoughCircle> getCandidates(final BufferedImage houghAccumulator, final int radius) {
final int width = houghAccumulator.getWidth();
final int height = houghAccumulator.getHeight();
final List<HoughCircle> candidates = new ArrayList<HoughCircle>();
for (int x = 0; x < width; x++) {
for (int y = 0; y < height; y++) {
int accumulator = new Color(houghAccumulator.getRGB(x, y)).getRed();
if (accumulator > 0) {
final HoughCircle candidate = new HoughCircle();
candidate.x = x;
candidate.y = y;
candidate.accumulator = accumulator;
candidate.radius = radius;
candidate.accumulatorImage = houghAccumulator;
candidates.add(candidate);
}
}
}
Collections.sort(candidates, Collections.reverseOrder(new HoughCircleAccumulatComparator()));
return candidates;
}
// Vergleichen zweier Kandidaten anhand der Akkumulatorwerte
public static class HoughCircleAccumulatComparator implements Comparator<HoughCircle> {
public int compare(HoughCircle o1, HoughCircle o2) {
return Integer.compare(o1.accumulator, o2.accumulator);
}
}
Circle Hough Transformation mit Radius 5
Circle Hough Transformation mit Radius 10
Der als Parameter übergebene fixe Radius wird benutzt, um die Kreise im Akkumulator zu zeichnen. Im mittleren Akkumulatorbild mit Radius fünf kann man sehen, dass der gewählte Radius von fünf Pixeln nicht dem Radius des Kreises entspricht, wohingegen das gleiche Bild mit Radius zehn einige sehr viel hellere Pixel beim Kreismittelpunkt liefert. Erst wenn der angegebene Radius mit dem Radius der gesuchten Kreise im Bild übereinstimmt, erhält man auch die richtigen Mittelpunkte. Kennt man den Radius nicht genau, wie in meinem Fall, kann man die Circle Hough Transformation mit verschiedenen Radien ausprobieren und anschließend aus der gesamten Menge der Kandidaten denjenigen auswählen, der den höchsten Akkumulatorwert hat.
/**
* Führt für alle angegebenen Radius einen Circle-Hough-Transform aus und liefert
* denjenigen Kreiskandidaten mit dem höchsten Akkumulatorwert.
*/
public static HoughCircle getBestCandidate(final BufferedImage edgeImage,int minRadius,int maxRadius){
final List<HoughCircle> candidates=new ArrayList<HoughCircle>();
for(int radius=minRadius;radius<=maxRadius;radius++){
final BufferedImage houghImage=hough(edgeImage,radius);
candidates.addAll(getCandidates(houghImage,radius));
}
Collections.sort(candidates,Collections.reverseOrder(new HoughCircleAccumulatComparator()));
if(candidates.isEmpty()){
return null;
}else{
return candidates.get(0);
}
}
Circle Hough Transformation mit hellstem Akkumulatorwert bei Radius 9 bis 12 (von links nach rechts: 9, 11, 9) und dem entsprechenden Kreis
Original mit bestem Wert
Wie man sehen kann, hat der derzeitige Algorithmus beim dritten Bild nicht richtig funktioniert: Statt dem Kreis wurde die “5” links unten gewählt. Die Ziffer auf dem Bild erzeugt durch ihre Rundungen und vielen Kanten ebenfalls einige hohe Akkumulatorwerte.
Erfolg ist das beste Rezept #
Die einfache Lösung mit Sobel-Feldman und Circle Hough Transformation hatte im Fall der Captchabilder eine Trefferquote von etwas mehr als 50%. Das ist eigentlich nicht viel, wo Bildklassifikatoren aus dem Bereich der künstlichen Intelligenz Erkennungsraten von über 85% auf Objekte in beliebigen Bildern ermöglichen, aber für meine Zwecke war es schon vollkommen ausreichend. Wurde eine falsche Koordinate geklickt, so wartete der Bot einige Sekunden, um evtl. Denial-Of-Service-Blockierungsmechanismen zu verhindern, und versuchte es erneut. Das jeder zweite Klick richtig war, war vollkommen ausreichend. Mein Bot lief einige Wochen auf meinem Computer durch, ohne ein einzelnes Problem zu verursachen. Da der Ansatz funktionierte und ich für die Erforschung und Umsetzung bereits so viel Zeit aufgebracht hatte, beließ ich es dabei. Dabei gäbe es durchaus Verbesserungsmöglichkeiten, sowohl in der Performanz als auch zur vor Auslese von Kandidaten. Bei der Anwendung des Sobel-Filters werden keine Farbwechsel berücksichtigt. So sind die Kreise oft, nicht immer, durch eine andere Farbe als der Hintergrund gekennzeichnet. Selbst bei ähnlicher Helligkeit könnte man Blau von Rot besser Unterscheiden und somit den Algorithmus verbessern. Auch gibt es noch alternative Kantendetektoren, wie Canny oder weitere Filterschritte, wie Gauß’sche Weichzeichner, die man auf das Bild anwenden könnte.
Ganz unberücksichtigt waren grundlegend andere Methoden, wie künstliche Neuronale Netze.
Weitere Einsatzmöglichkeiten #
Die Circle Hough Transformation wird an diversen Stellen benutzt, wie z. B. zum Erkennen der Positionen von Augen auf Gesichtern, Köpfe in Überwachungsvideos oder in leichter Abwandlung Gesichtskonturen. Ein schönes Video zeigt, wie die Circle Hough Transformation auch auf Videostreams angewendet werden kann.