Reto

Escriba el código que, dada una imagen de un panel de un cómic xkcd aleatorio, devuelve un valor verdadero si Blackhat está en el cómic o falsey si no.

Quien es Blackhat?

Blackhat es el nombre no oficial dado al personaje en los cómics xkcd que usa un sombrero negro:

_{Tomado de la página Explique xkcd en Blackhat}

El sombrero de Blackhat siempre es recto, negro y tiene el mismo aspecto que en la imagen de arriba.

Otros personajes también pueden tener sombreros y cabello, pero ninguno tendrá sombreros negros y rectos.

Entrada

La imagen se puede ingresar de cualquier manera que desee, ya sea una ruta a la imagen o bytes a través de STDIN. No debería necesitar tomar una URL como entrada.

Reglas

Codificar la respuesta no está prohibido, pero no se agradece.

No está autorizado a acceder a Internet para obtener la respuesta.

Ejemplos

_{Todas las imágenes recortadas de imágenes de https://xkcd.com}

Blackhat está en el panel (volver truthy)

Blackhat no está en el panel (volver falsey)

Prueba de batería

Las 20 imágenes que contienen Blackhat se pueden encontrar aquí: https://beta-decay.github.io/blackhat.zip

Las 20 imágenes que no contienen Blackhat se pueden encontrar aquí: https://beta-decay.github.io/no_blackhat.zip

Si desea obtener más imágenes para probar sus programas (para entrenar para los casos de prueba misteriosos), puede encontrar una lista de todas las apariencias de Blackhat aquí: http://www.explainxkcd.com/wiki/index.php/Category: Comics_featuring_Black_Hat

Victorioso

El programa que identifica correctamente si Blackhat está en el cómic o no para la mayoría de las imágenes gana. Su encabezado debe incluir su puntaje como porcentaje.

En el caso de un desempate, los programas vinculados recibirán imágenes "misteriosas" (es decir, las que solo yo conozco). El código que identifica más correctamente gana el desempate.

Las imágenes misteriosas serán reveladas junto con los puntajes.

Nota: parece que el nombre de Randall para él puede ser Hat Guy. Aunque prefiero 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';

Para ejecutarlo:

php <filename> <image_path>

Ejemplo:

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

Notas

• Imprime "verdadero" si encuentra sombrero negro y "falso" si no lo encuentra.
• Esto también debería funcionar en versiones anteriores de PHP, pero para estar seguro, use PHP> = 7 con GD .
• Este script realmente trata de encontrar el sombrero y al hacerlo, podría rotar la imagen muchas veces y cada vez verifica miles y miles de píxeles y pistas. Por lo tanto, cuanto más grande sea la imagen o más píxeles oscuros tenga, el guión tardará más en terminar. Sin embargo, debería tomar de unos segundos a un minuto para la mayoría de las imágenes.
• Me encantaría entrenar más este script, pero no tengo suficiente tiempo para hacerlo.
• Este script no es golf (nuevamente porque no tengo suficiente tiempo), pero tiene mucho potencial para jugar golf en caso de empate.

Algunos ejemplos de sombreros negros detectados:

Estos ejemplos se obtienen dibujando líneas rojas en puntos especiales encontrados en la imagen que el guión decidió que tiene un sombrero negro (las imágenes pueden tener rotación en comparación con las originales).

Extra

Antes de publicar aquí, probé este script contra otro conjunto de 15 imágenes, 10 con sombrero negro y 5 sin sombrero negro, y también fue correcto para todas ellas (100%).

Aquí está el archivo ZIP que contiene imágenes de prueba adicionales que utilicé: extra.zip

En el extra/blackhatdirectorio, los resultados de detección con líneas rojas también están disponibles. Por ejemplo, extra/blackhat/1.pnges la imagen de prueba y extra/blackhat/1_r.pnges el resultado de la detección de la misma.

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

Mejora de la versión anterior, con algunas comprobaciones agregadas en la forma de las regiones candidatas.

Errores de clasificación en el conjunto HAT : imágenes 4, 14, 15, 17 .

Errores de clasificación en el conjunto NO SOMBRERO : imágenes 4 .

Algunos ejemplos de imágenes clasificadas corregidas:

Ejemplo de una imagen clasificada incorrecta:

ANTIGUA VERSIÓN (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;

Enfoque basado en la erosión de la imagen, similar a la solución propuesta por Mnemonic, pero basado en el canal V de la imagen HSV. Además, se verifica el valor medio del canal del área seleccionada (no su tamaño).

Errores de clasificación en el conjunto HAT : imágenes 4, 5, 10 .

Errores de clasificación en el conjunto NO SOMBRERO : imágenes 4, 5, 6, 7, 13, 14 .

Pyth , 62.5%

<214.O.n'z

Acepta el nombre de archivo de un archivo de imagen en stdin. Devuelve Truesi el promedio de todos sus componentes de color RGB es mayor que 214. Has leído bien: aparentemente las imágenes de sombrero negro tienden a ser más brillantes que las imágenes sin sombrero negro.

(Seguramente alguien puede hacerlo mejor, ¡esto no es código 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

Esto determina qué píxeles son negros y luego erosiona las pequeñas piezas contiguas. Ciertamente hay margen de mejora aquí.