Wyzwanie

Napisz kod, który, biorąc pod uwagę obraz panelu z przypadkowego komiksu xkcd, zwraca prawdziwą wartość, jeśli Blackhat jest w komiksie lub falsey, jeśli nie.

Kim jest Blackhat?

Blackhat to nieoficjalna nazwa nadana postaci w komiksach xkcd, która nosi czarny kapelusz:

_{Zaczerpnięte ze strony Wyjaśnij xkcd na Blackhat}

Kapelusz Blackhata jest zawsze prosty, czarny i wygląda tak samo jak na powyższym zdjęciu.

Inne postacie mogą również mieć czapki i włosy, ale żadna nie będzie miała czapek, które są czarne i proste.

Wkład

Obraz może być wprowadzany w dowolny sposób, niezależnie od tego, czy będzie to ścieżka do obrazu, czy bajtów przez STDIN. Nie musisz przyjmować adresu URL jako danych wejściowych.

Zasady

Kodowanie odpowiedzi nie jest zbanowane, ale nie jest doceniane.

Nie możesz uzyskać dostępu do Internetu, aby uzyskać odpowiedź.

Przykłady

_{Wszystkie obrazy przycięte z obrazów z https://xkcd.com}

Blackhat jest w panelu (powrót truthy)

Blackhat nie ma w panelu (powrót falsey)

Sprawdź akumulator

20 zdjęć zawierających Blackhat można znaleźć tutaj: https://beta-decay.github.io/blackhat.zip

20 zdjęć, które nie zawierają Blackhat, można znaleźć tutaj: https://beta-decay.github.io/no_blackhat.zip

Jeśli chcesz, aby więcej obrazów testowało twoje programy (aby trenować dla tajemniczych przypadków testowych), możesz znaleźć listę wszystkich wyglądów Blackhat tutaj: http://www.explainxkcd.com/wiki/index.php/Category: Comics_featuring_Black_Hat

Zwycięski

Wygrywa program, który poprawnie identyfikuje, czy Blackhat jest w komiksie, czy nie dla większości obrazów. Nagłówek powinien zawierać wynik procentowy.

W przypadku rozstrzygnięcia remisu powiązane programy otrzymają „tajemnicze” obrazy (tj. Takie, o których tylko ja wiem). Kod identyfikujący najbardziej poprawnie wygrywa rozstrzygnięcie.

Tajemnicze obrazy zostaną ujawnione wraz z partyturami.

Uwaga: wydaje się, że Randall ma na imię Hat Hat. Wolę 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';

Aby uruchomić:

php <filename> <image_path>

Przykład:

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

Notatki

• Drukuje „prawda”, jeśli znajdzie czarny kapelusz, i „fałsz”, jeśli go nie znajdzie.
• Powinno to również działać na poprzednich wersjach PHP, ale dla bezpieczeństwa użyj PHP> = 7 z GD .
• Ten skrypt faktycznie próbuje znaleźć kapelusz, a tym samym może obrócić obraz wiele razy i za każdym razem sprawdza tysiące pikseli i wskazówek. Im większy obraz lub więcej ciemnych pikseli, tym więcej czasu zajmie ukończenie skryptu. Jednak większość zdjęć powinna zająć od kilku sekund do minuty.
• Chciałbym więcej ćwiczyć ten skrypt, ale nie mam na to czasu.
• Ten skrypt nie jest golfem (ponownie, ponieważ nie mam wystarczająco dużo czasu), ale ma duży potencjał do gry w golfa w przypadku remisu.

Niektóre przykłady wykrytych czarnych czapek:

Przykłady te uzyskuje się poprzez narysowanie czerwonych linii na specjalnych punktach na obrazie, które według skryptu ma czarny kapelusz (obrazy mogą się obracać w porównaniu do oryginalnych).

Dodatkowy

Przed opublikowaniem tutaj przetestowałem ten skrypt na innym zestawie 15 obrazów, 10 z czarnym kapeluszem i 5 bez czarnego kapelusza, i wszystko poszło poprawnie (100%).

Oto plik ZIP zawierający dodatkowe obrazy testowe, których użyłem: extra.zip

W extra/blackhatkatalogu dostępne są również wyniki wykrywania z czerwonymi liniami. Na przykład extra/blackhat/1.pngjest obraz testowy i extra/blackhat/1_r.pngjest wynikiem jego wykrycia.

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

Udoskonalenie poprzedniej wersji, z pewnymi poprawkami dotyczącymi kształtu regionów kandydujących.

Błędy klasyfikacji w zestawie HAT : obrazy 4, 14, 15, 17 .

Błędy klasyfikacji w zestawie NON HAT : obrazy 4 .

Niektóre przykłady poprawionych zdjęć niejawnych:

Przykład niewłaściwego obrazu niejawnego:

WERSJA STARE (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;

Podejście oparte na erozji obrazu, podobne do rozwiązania zaproponowanego przez Mnemonic, ale oparte na kanale V obrazu HSV. Ponadto sprawdzana jest średnia wartość kanału wybranego obszaru (a nie jego rozmiar).

Błędy klasyfikacji w zestawie HAT : obrazy 4, 5, 10 .

Błędy klasyfikacji w zestawie NON HAT : obrazy 4, 5, 6, 7, 13, 14 .

Pyth , 62,5%

<214.O.n'z

Akceptuje nazwę pliku obrazu na standardowym wejściu. Zwraca, Truejeśli średnia wszystkich jego składników koloru RGB jest większa niż 214. Czytasz to dobrze: najwyraźniej obrazy czarno-białe wydają się być jaśniejsze niż obrazy bez czarno-białych.

(Z pewnością ktoś może zrobić lepiej - to nie jest golf golfowy !)

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

To określa, które piksele są czarne, a następnie erozuje małe, ciągłe kawałki. Z pewnością jest tu miejsce na ulepszenia.