Herausforderung

Schreiben Sie Code, der bei einem Bild eines Panels aus einem zufälligen xkcd-Comic einen Wahrheitswert zurückgibt, wenn sich Blackhat im Comic befindet oder wenn nicht.

Wer ist Blackhat?

Blackhat ist der inoffizielle Name der Figur in XKCD-Comics, die einen schwarzen Hut trägt:

_{Entnommen aus der Erklärung der xkcd-Seite zu Blackhat}

Der Hut von Blackhat ist immer gerade, schwarz und sieht genauso aus wie auf dem obigen Bild.

Andere Charaktere haben möglicherweise auch Hüte und Haare, aber keine hat Hüte, die schwarz und gerade sind.

Eingang

Das Bild kann in beliebiger Weise eingegeben werden, ob es sich um einen Pfad zum Bild oder um Bytes über STDIN handelt. Sie sollten keine URL als Eingabe benötigen.

Regeln

Das Hardcodieren der Antwort ist nicht verboten, wird aber nicht gewürdigt.

Sie dürfen nicht auf das Internet zugreifen, um die Antwort zu erhalten.

Beispiele

_{Alle Bilder stammen aus Bildern von https://xkcd.com}

Blackhat ist im Panel (Return truthy)

Blackhat ist nicht im Panel (Return falsey)

Batterie testen

Die 20 Bilder, die Blackhat enthalten, finden Sie hier: https://beta-decay.github.io/blackhat.zip

Die 20 Bilder, die keinen Blackhat enthalten, finden Sie hier: https://beta-decay.github.io/no_blackhat.zip

Wenn Sie möchten, dass mehr Bilder Ihre Programme testen (um auf die mysteriösen Testfälle zu trainieren), finden Sie hier eine Liste aller Erscheinungsbilder von Blackhat: http://www.explainxkcd.com/wiki/index.php/Category: Comics_featuring_Black_Hat

Gewinnen

Das Programm, das für die meisten Bilder korrekt identifiziert, ob Blackhat im Comic ist oder nicht, gewinnt. Ihre Kopfzeile sollte Ihre Punktzahl als Prozentsatz enthalten.

Im Falle eines Unentschieden erhalten die gebundenen Programme "mysteriöse" Bilder (dh solche, die nur ich kenne). Der Code, der am besten identifiziert, gewinnt den Tiebreak.

Die mysteriösen Bilder werden zusammen mit den Partituren enthüllt.

Hinweis: Es scheint, dass Randalls Name für ihn Hat Guy sein könnte. Ich bevorzuge allerdings Blackhat.

PHP (> = 7), 100% (40/40)

<?php

set_time_limit(0);

class BlackHat
{
    const ROTATION_RANGE = 45;

    private $image;
    private $currentImage;
    private $currentImageWidth;
    private $currentImageHeight;

    public function __construct($path)
    {
        $this->image = imagecreatefrompng($path);
    }

    public function hasBlackHat()
    {
        $angles = [0];

        for ($i = 1; $i <= self::ROTATION_RANGE; $i++) {
            $angles[] = $i;
            $angles[] = -$i;
        }

        foreach ($angles as $angle) {
            if ($angle == 0) {
                $this->currentImage = $this->image;
            } else {
                $this->currentImage = $this->rotate($angle);
            }

            $this->currentImageWidth = imagesx($this->currentImage);
            $this->currentImageHeight = imagesy($this->currentImage);

            if ($this->findBlackHat()) return true;
        }

        return false;
    }

    private function findBlackHat()
    {
        for ($y = 0; $y < $this->currentImageHeight; $y++) {
            for ($x = 0; $x < $this->currentImageWidth; $x++) {
                if ($this->isBlackish($x, $y) && $this->isHat($x, $y)) return true;
            }
        }

        return false;
    }

    private function isHat($x, $y)
    {
        $hatWidth = $this->getBlackishSequenceSize($x, $y, 'right');
        if ($hatWidth < 10) return false;

        $hatHeight = $this->getBlackishSequenceSize($x, $y, 'bottom');

        $hatLeftRim = $hatRightRim = 0;
        for (; ; $hatHeight--) {
            if ($hatHeight < 5) return false;

            $hatLeftRim = $this->getBlackishSequenceSize($x, $y + $hatHeight, 'left');
            if ($hatLeftRim < 3) continue;

            $hatRightRim = $this->getBlackishSequenceSize($x + $hatWidth, $y + $hatHeight, 'right');
            if ($hatRightRim < 2) $hatRightRim = $this->getBlackishSequenceSize($x + $hatWidth, $y + $hatHeight, 'right', 'isLessBlackish');
            if ($hatRightRim < 2) continue;

            break;
        }

        $ratio = $hatWidth / $hatHeight;
        if ($ratio < 2 || $ratio > 4.2) return false;

        $widthRatio = $hatWidth / ($hatLeftRim + $hatRightRim);
        if ($widthRatio < 0.83) return false;
        if ($hatHeight / $hatLeftRim < 1 || $hatHeight / $hatRightRim < 1) return false;

        $pointsScore = 0;
        if ($this->isSurroundedBy($x, $y, 3, true, true, false, false)) $pointsScore++;
        if ($this->isSurroundedBy($x + $hatWidth, $y, 3, true, false, false, true)) $pointsScore++;
        if ($this->isSurroundedBy($x, $y + $hatHeight, 3, false, false, true, false)) $pointsScore++;
        if ($this->isSurroundedBy($x + $hatWidth, $y + $hatHeight, 3, false, false, true, false)) $pointsScore++;
        if ($this->isSurroundedBy($x - $hatLeftRim, $y + $hatHeight, 3, true, true, true, false)) $pointsScore++;
        if ($this->isSurroundedBy($x + $hatWidth + $hatRightRim, $y + $hatHeight, 3, true, false, true, true)) $pointsScore++;
        if ($pointsScore < 3 || ($hatHeight >= 19 && $pointsScore < 4) || ($hatHeight >= 28 && $pointsScore < 5)) return false;

        $middleCheckSize = ($hatHeight >= 15 ? 3 : 2);
        if (!$this->isSurroundedBy($x + (int)($hatWidth / 2), $y, $middleCheckSize, true, null, null, null)) return false;
        if (!$this->isSurroundedBy($x + (int)($hatWidth / 2), $y + $hatHeight, $middleCheckSize, null, null, true, null)) {
            if (!$this->isSurroundedBy($x + (int)(($hatWidth / 4) * 3), $y + $hatHeight, $middleCheckSize, null, null, true, null)) return false;
        }
        if (!$this->isSurroundedBy($x, $y + (int)($hatHeight / 2), $middleCheckSize + 1, null, true, null, null)) return false;
        if (!$this->isSurroundedBy($x + $hatWidth, $y + (int)($hatHeight / 2), $middleCheckSize, null, null, null, true)) return false;

        $badBlacks = 0;
        for ($i = 1; $i <= 3; $i++) {
            if ($y - $i >= 0) {
                if ($this->isBlackish($x, $y - $i)) $badBlacks++;
            }

            if ($x - $i >= 0 && $y - $i >= 0) {
                if ($this->isBlackish($x - $i, $y - $i)) $badBlacks++;
            }
        }
        if ($badBlacks > 2) return false;

        $total = ($hatWidth + 1) * ($hatHeight + 1);
        $blacks = 0;
        for ($i = $x; $i <= $x + $hatWidth; $i++) {
            for ($j = $y; $j <= $y + $hatHeight; $j++) {
                $isBlack = $this->isBlackish($i, $j);
                if ($isBlack) $blacks++;
            }
        }

        if (($total / $blacks > 1.15)) return false;

        return true;
    }

    private function getColor($x, $y)
    {
        return imagecolorsforindex($this->currentImage, imagecolorat($this->currentImage, $x, $y));
    }

    private function isBlackish($x, $y)
    {
        $color = $this->getColor($x, $y);
        return ($color['red'] < 78 && $color['green'] < 78 && $color['blue'] < 78 && $color['alpha'] < 30);
    }

    private function isLessBlackish($x, $y)
    {
        $color = $this->getColor($x, $y);
        return ($color['red'] < 96 && $color['green'] < 96 && $color['blue'] < 96 && $color['alpha'] < 40);
    }

    private function getBlackishSequenceSize($x, $y, $direction, $fn = 'isBlackish')
    {
        $size = 0;

        if ($direction == 'right') {
            for ($x++; ; $x++) {
                if ($x >= $this->currentImageWidth) break;
                if (!$this->$fn($x, $y)) break;
                $size++;
            }
        } elseif ($direction == 'left') {
            for ($x--; ; $x--) {
                if ($x < 0) break;
                if (!$this->$fn($x, $y)) break;
                $size++;
            }
        } elseif ($direction == 'bottom') {
            for ($y++; ; $y++) {
                if ($y >= $this->currentImageHeight) break;
                if (!$this->$fn($x, $y)) break;
                $size++;
            }
        }

        return $size;
    }

    private function isSurroundedBy($x, $y, $size, $top = null, $left = null, $bottom = null, $right = null)
    {
        if ($top !== null) {
            $flag = false;
            for ($i = 1; $i <= $size; $i++) {
                if ($y - $i < 0) break;
                $isBlackish = $this->isBlackish($x, $y - $i);

                if (
                    ($top && !$isBlackish) ||
                    (!$top && $isBlackish)
                ) {
                    $flag = true;
                } elseif ($flag) {
                    return false;
                }
            }
            if (!$flag) return false;
        }

        if ($left !== null) {
            $flag = false;
            for ($i = 1; $i <= $size; $i++) {
                if ($x - $i < 0) break;
                $isBlackish = $this->isBlackish($x - $i, $y);

                if (
                    ($left && !$isBlackish) ||
                    (!$left && $isBlackish)
                ) {
                    $flag = true;
                } elseif ($flag) {
                    return false;
                }
            }
            if (!$flag) return false;
        }

        if ($bottom !== null) {
            $flag = false;
            for ($i = 1; $i <= $size; $i++) {
                if ($y + $i >= $this->currentImageHeight) break;
                $isBlackish = $this->isBlackish($x, $y + $i);

                if (
                    ($bottom && !$isBlackish) ||
                    (!$bottom && $isBlackish)
                ) {
                    $flag = true;
                } elseif ($flag) {
                    return false;
                }
            }
            if (!$flag) return false;
        }

        if ($right !== null) {
            $flag = false;
            for ($i = 1; $i <= $size; $i++) {
                if ($x + $i >= $this->currentImageWidth) break;
                $isBlackish = $this->isBlackish($x + $i, $y);

                if (
                    ($right && !$isBlackish) ||
                    (!$right && $isBlackish)
                ) {
                    $flag = true;
                } elseif ($flag) {
                    return false;
                }
            }
            if (!$flag) return false;
        }

        return true;
    }

    private function rotate($angle)
    {
        return imagerotate($this->image, $angle, imagecolorallocate($this->image, 255, 255, 255));
    }
}

$bh = new BlackHat($argv[1]);
echo $bh->hasBlackHat() ? 'true' : 'false';

Um es auszuführen:

php <filename> <image_path>

Beispiel:

php black_hat.php "/tmp/blackhat/1.PNG"

Anmerkungen

• Gibt "true" aus, wenn der schwarze Hut gefunden wird, und "false", wenn er nicht gefunden wird.
• Dies sollte auch mit früheren PHP-Versionen funktionieren. Verwenden Sie jedoch aus Sicherheitsgründen PHP> = 7 mit GD .
• Dieses Skript versucht tatsächlich, den Hut zu finden. Auf diese Weise wird das Bild möglicherweise viele Male gedreht und jedes Mal nach Tausenden und Abertausenden von Pixeln und Hinweisen gesucht. Je größer das Bild ist oder je mehr dunkle Pixel es hat, desto länger dauert es, bis das Skript fertig ist. Bei den meisten Bildern sollte es jedoch einige Sekunden bis eine Minute dauern.
• Ich würde dieses Skript gerne mehr trainieren, aber ich habe nicht genug Zeit, dies zu tun.
• Dieses Skript wird nicht gespielt (wieder, weil ich nicht genug Zeit habe), hat aber im Falle eines Unentschieden viel Potenzial zum Golfen.

Einige Beispiele für erkannte schwarze Hüte:

Diese Beispiele werden durch Zeichnen roter Linien an speziellen Punkten auf dem Bild erhalten, für die das Skript entschieden hat, dass sie einen schwarzen Hut haben (Bilder können im Vergleich zu Originalen eine Rotation aufweisen).

Extra

Bevor ich hier gepostet habe, habe ich dieses Skript mit einem anderen Satz von 15 Bildern getestet, 10 mit schwarzem Hut und 5 ohne schwarzen Hut, und es hat auch für alle von ihnen funktioniert (100%).

Hier ist die ZIP-Datei mit zusätzlichen Testbildern, die ich verwendet habe: extra.zip

Im extra/blackhatVerzeichnis sind auch die Erkennungsergebnisse mit roten Linien verfügbar. Zum Beispiel extra/blackhat/1.pngist das Testbild und extra/blackhat/1_r.pngist das Erkennungsergebnis davon.

Matlab, 87,5%

function hat=is_blackhat_here2(filepath)

img_hsv = rgb2hsv(imread(filepath));
img_v = img_hsv(:,:,3);

bw = imdilate(imerode( ~im2bw(img_v), strel('disk', 4, 8)), strel('disk', 4, 8));
bw = bwlabel(bw, 8);
bw = imdilate(imerode(bw, strel('disk', 1, 4)), strel('disk', 1, 4));
bw = bwlabel(bw, 4);

region_stats = regionprops(logical(bw), 'all');
hat = false;
for i = 1 : numel(region_stats)
    if mean(img_v(region_stats(i).PixelIdxList)) < 0.15 ...
            && region_stats(i).Area > 30 ...
            && region_stats(i).Solidity > 0.88 ...
            && region_stats(i).Eccentricity > 0.6 ...
            && region_stats(i).Eccentricity < 1 ...
            && abs(region_stats(i).Orientation) < 75...
            && region_stats(i).MinorAxisLength / region_stats(i).MajorAxisLength < 0.5;
        hat = true;
        break;
    end
end

Verbesserung der Vorgängerversion mit einigen Überprüfungen der Form der Kandidatenregionen.

Klassifizierungsfehler im HAT-Set : Bilder 4, 14, 15, 17 .

Klassifizierungsfehler im NON HAT Set : Bilder 4 .

Einige Beispiele für korrigierte klassifizierte Bilder:

Beispiel für ein falsch klassifiziertes Bild:

ALTE VERSION (77,5%)

function hat=is_blackhat_here(filepath)

img_hsv = rgb2hsv(imread(filepath));
img_v = img_hsv(:,:,3);
bw = imerode(~im2bw(img_v), strel('disk', 5, 8));

hat =  mean(img_v(bw)) < 0.04;

Ansatz basierend auf Bildabtragung, ähnlich der von Mnemonic vorgeschlagenen Lösung, jedoch basierend auf dem V-Kanal des HSV-Bildes. Außerdem wird der Mittelwert des Kanals des ausgewählten Bereichs überprüft (nicht dessen Größe).

Klassifizierungsfehler im HAT-Satz : Bilder 4, 5, 10 .

Klassifizierungsfehler im NON HAT-Satz : Bilder 4, 5, 6, 7, 13, 14 .

Pyth , 62,5%

<214.O.n'z

Akzeptiert den Dateinamen einer Bilddatei auf stdin. Kehrt zurückTrue wenn der Durchschnitt aller RGB-Farbkomponenten größer als 214 ist. Sie haben richtig gelesen: Anscheinend sind Schwarzhutbilder heller als Schwarzhutbilder.

(Sicher kann jemand es besser machen - das ist kein Code-Golf !)

Python 2, 65% 72,5% 77,5% (= 31/40)

import cv2
import numpy as np
from scipy import misc

def blackhat(path):
    im = misc.imread(path)
    black = (im[:, :, 0] < 10) & (im[:, :, 1] < 10) & (im[:, :, 2] < 10)
    black = black.astype(np.ubyte)

    black = cv2.erode(black, np.ones((3, 3)), iterations=3)

    return 5 < np.sum(black) < 2000

Dadurch wird herausgefunden, welche Pixel schwarz sind, und es werden kleine zusammenhängende Teile abgetragen. Hier gibt es sicherlich Verbesserungspotential.