Gdzie jest Blackhat?

27

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.

Rozpad beta
źródło
12
Nie zdziwię się, jeśli Mathematica ma do tego wbudowaną funkcję. ( Dla odniesienia )
J. Sallé,
5
Sugestia dotycząca innego przerywnika remisu: miej inny, mniejszy zestaw obrazów (powiedzmy 5 prawdziwych przypadków i 5 fałszów), które nie zostały tutaj ujawnione, a zwycięzcą remisu jest ten, który najlepiej uogólnia te nieznane obrazy. Zachęciłoby to do bardziej ogólnych inteligentniejszych rozwiązań w porównaniu z tymi, które pasują do tych konkretnych obrazów.
sundar - Przywróć Monikę
3
Przypadki testowe z policją i RIAA / MPAA są po prostu złe. Dobra bateria testowa, @BetaDecay.
Sundar - Przywróć Monikę
1
Daj nam kontynuować tę dyskusję w czacie .
Beta Decay
1
@ Night2 Przepraszamy! Chciałem tylko zrobić remis. Dobra robota na 100%!
Beta Decay

Odpowiedzi:

16

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:

wprowadź opis zdjęcia tutaj

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.

Noc 2
źródło
Ten remis nie jest golfem kodowym. Zamiast tego programy są zasilane ukrytymi przypadkami testowymi, aż do rozstrzygnięcia rozstrzygnięcia. Opowiem ci wynik i opublikuję przypadki testowe :)
Rozpad Beta
1
@BetaDecay: Dziękuję za wyjaśnienie, to zdanie (najkrótsze zwycięstwa na remisie) było w mojej głowie z poprzednich wersji pytania, więc pomyślałem, że jeśli remis zdarzy się na ukrytych przypadkach testowych, wtedy najkrótszy kod wygrywa. Mój błąd!
Night2
7
Wygrywasz także nagrodę za najmniej prawdopodobny język przetwarzania obrazu :)
Anush
@Anush Cóż, przynajmniej PHP ma imagerotatewbudowane, więc ...
user202729
W PHP podoba mi się to, że ma podstawową funkcjonalność dla prawie wszystkiego. Od wielu lat łączy GD, a GD faktycznie zaspokaja najczęstsze potrzeby pracy z obrazami. Ale bardziej podoba mi się w PHP, że zawsze są jakieś rozszerzenia / pakiety, które dadzą ci więcej (z powodu dużej społeczności). Na przykład istnieją rozszerzenia OpenCV dla PHP, które umożliwiają faktyczne przetwarzanie obrazu!
Noc2,
8

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: wprowadź opis zdjęcia tutaj wprowadź opis zdjęcia tutaj

Przykład niewłaściwego obrazu niejawnego:

wprowadź opis zdjęcia tutaj

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 .

PieCot
źródło
7

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 !)

Anders Kaseorg
źródło
2
Byłem zdumiony mocą Pytha, dopóki nie zdałem sobie sprawy: D
Beta Decay
Przez chwilę pomyślałem: „Od kiedy Pyth ma wbudowaną funkcję rozpoznawania obrazów blackhatta”
Luis Felipe De Jesus Munoz
2
ja=2540(40ja)2)407,7%
6

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.

Zacharý
źródło