Вызов

Напишите код, который, учитывая изображение панели из случайного комикса xkcd, возвращает истинное значение, если Blackhat находится в комиксе, или false, если нет.

Кто такой Blackhat?

Blackhat - это неофициальное имя, данное персонажу в комиксах xkcd, который носит черную шляпу:

_{Взято со страницы объяснения xkcd на Blackhat}

Шляпа Блэкхата всегда прямолинейна, черная и выглядит так же, как на картинке выше.

У других персонажей также могут быть шляпы и волосы, но ни у кого из них нет шляп с черными и прямыми краями.

вход

Изображение может быть введено любым способом, каким вы пожелаете, будь то путь к изображению или байты через STDIN. Вам не нужно принимать URL в качестве входных данных.

правила

Жесткое кодирование ответа не запрещено, но оно не ценится.

Вы не можете получить доступ к Интернету, чтобы получить ответ.

Примеры

_{Все изображения вырезаны из изображений с https://xkcd.com}

Blackhat в панели (возврат truthy)

Blackhat нет в панели (возврат falsey)

Тест батареи

20 изображений, которые содержат Blackhat, можно найти здесь: https://beta-decay.github.io/blackhat.zip

20 изображений, которые не содержат Blackhat, можно найти здесь: https://beta-decay.github.io/no_blackhat.zip

Если вам нужно больше изображений для тестирования ваших программ (для подготовки к загадочным тестам), вы можете найти список всех появлений Blackhat здесь: http://www.explainxkcd.com/wiki/index.php/Category: Comics_featuring_Black_Hat

выигрыш

Программа, которая правильно определяет, находится ли Blackhat в комиксе или нет для большинства изображений, побеждает. Ваш заголовок должен включать ваш счет в процентах.

В случае разрыва связей связанным программам будут предоставлены «загадочные» изображения (то есть те, о которых только я знаю). Код, который определяет наиболее правильно, выигрывает тай-брейк.

Загадочные изображения будут раскрыты вместе с оценками.

Примечание: кажется, что имя Рэндалла для него может быть Hat Guy. Я предпочитаю 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';

Чтобы запустить это:

php <filename> <image_path>

Пример:

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

Заметки

• Печатает «true», если находит черную шляпу, и «false», если не находит.
• Это должно работать и в предыдущих версиях PHP, но для безопасности используйте PHP> = 7 с GD .
• Этот скрипт на самом деле пытается найти шляпу, и, таким образом, он может поворачивать изображение много раз и каждый раз проверяет тысячи и тысячи пикселей и подсказок. Таким образом, чем больше изображение или темнее его пиксели, сценарию потребуется больше времени для завершения. Для большинства изображений это может занять от нескольких секунд до минуты.
• Я бы хотел больше тренировать этот сценарий, но у меня не хватает времени для этого.
• Этот сценарий не в гольфе (опять же, потому что у меня не хватает времени), но имеет большой потенциал для игры в гольф в случае ничьей.

Некоторые примеры обнаруженных черных шляп:

Эти примеры получены путем рисования красных линий на специальных точках, найденных на изображении, которое, по мнению сценария, имеет черную шляпу (изображения могут иметь поворот по сравнению с оригинальными).

дополнительный

Перед публикацией я проверил этот сценарий на другом наборе из 15 изображений, 10 с черной шляпой и 5 без черной шляпы, и он также прошел корректно для всех из них (100%).

Вот ZIP-файл, содержащий дополнительные тестовые изображения, которые я использовал: extra.zip

В extra/blackhatкаталоге также доступны результаты обнаружения с красными линиями. Например, extra/blackhat/1.pngэто тестовое изображение и extra/blackhat/1_r.pngрезультат его обнаружения.

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

Улучшение предыдущей версии с добавлением некоторых проверок формы областей-кандидатов.

Ошибки классификации в наборе HAT : изображения 4, 14, 15, 17 .

Ошибки классификации в наборе NON HAT : изображения 4 .

Некоторые примеры исправленных классифицированных изображений:

Пример неправильного классифицированного изображения:

Старая версия (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;

Подход основан на эрозии изображения, аналогичен решению, предложенному Mnemonic, но основан на V-канале изображения HSV. Кроме того, проверяется среднее значение канала выбранной области (а не его размер).

Ошибки классификации в наборе HAT : изображения 4, 5, 10 .

Ошибки классификации в наборе NON HAT : изображения 4, 5, 6, 7, 13, 14 .

Пиф , 62,5%

<214.O.n'z

Принимает имя файла изображения на стандартный ввод. Возвращает, Trueесли среднее значение всех его цветовых компонентов RGB больше 214. Вы правильно поняли: изображения, очевидно, чёрного цвета, как правило, ярче, чем изображения черного цвета.

(Конечно, кто-то может добиться большего успеха - это не код-гольф !)

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

Это выясняет, какие пиксели являются черными, а затем размывает маленькие смежные кусочки. Конечно, возможности для улучшения здесь.