Où est Blackhat?

27

Défi

Écrivez du code qui, étant donné une image d'un panneau d'une bande dessinée xkcd aléatoire, renvoie une valeur vraie si Blackhat est dans la bande dessinée ou Falsey sinon.

Qui est Blackhat?

Blackhat est le nom officieux donné au personnage dans les bandes dessinées xkcd qui porte un chapeau noir:

Tiré de la page Explain xkcd sur Blackhat

Le chapeau de Blackhat est toujours rectiligne, noir et ressemble à celui de l'image ci-dessus.

D'autres personnages peuvent également avoir des chapeaux et des cheveux, mais aucun n'aura de chapeaux noirs et droits.

Contribution

L'image peut être saisie comme vous le souhaitez, que ce soit un chemin vers l'image ou des octets via STDIN. Vous ne devriez pas avoir besoin de prendre une URL en entrée.

Règles

Le codage en dur de la réponse n'est pas interdit, mais il n'est pas apprécié.

Vous n'êtes pas autorisé à accéder à Internet pour obtenir la réponse.

Exemples

Toutes les images recadrées à partir d'images de https://xkcd.com

Blackhat est dans le panneau (retour truthy)

Blackhat n'est pas dans le panneau (retour falsey)

Batterie de test

Les 20 images qui contiennent Blackhat peuvent être trouvées ici: https://beta-decay.github.io/blackhat.zip

Les 20 images qui ne contiennent pas de Blackhat se trouvent ici: https://beta-decay.github.io/no_blackhat.zip

Si vous voulez plus d'images pour tester vos programmes (pour vous entraîner aux cas de test mystères), vous pouvez trouver une liste de toutes les apparitions de Blackhat ici: http://www.explainxkcd.com/wiki/index.php/Catégorie: Comics_featuring_Black_Hat

Gagnant

Le programme qui identifie correctement si Blackhat est dans la bande dessinée ou non pour la plupart des images gagne. Votre en-tête doit inclure votre score en pourcentage.

En cas de bris d'égalité, les programmes liés recevront des images "mystères" (c'est-à-dire celles que je connais seulement). Le code qui identifie le plus correctement remporte le tie-break.

Les images mystères seront révélées avec les partitions.

Remarque: il semble que le nom de Randall pour lui soit Hat Guy. Mais je préfère Blackhat.

code-challenge image-processing test-battery Beta Decay
la source
12
Je ne serai pas surpris si Mathematica a une fonction intégrée pour cela. ( Pour référence )
J. Sallé
5
Suggestion pour un bris d'égalité différent: ayez un ensemble d'images différent et plus petit (disons 5 cas réels et 5 faux) qui ne sont pas révélés ici, et le gagnant du bris d'égalité est celui qui se généralise le mieux à ces images inconnues. Cela inciterait les solutions plus génériques plus intelligentes à celles qui s'adaptent à ces images spécifiques.
sundar
3
Les cas de test avec la police et avec la RIAA / MPAA sont tout simplement mauvais. Bonne batterie de test, @BetaDecay.
sundar
1
Continuons cette discussion dans le chat .
Beta Decay
1
@ Night2 Désolé! Je comptais seulement en faire une. Beau travail à 100%!
Beta Decay

Réponses:

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';

Pour l'exécuter:

php <filename> <image_path>

Exemple:

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

Remarques

  • Imprime "vrai" si trouve un chapeau noir et "faux" s'il ne le trouve pas.
  • Cela devrait également fonctionner sur les versions précédentes de PHP, mais pour être sûr, utilisez PHP> = 7 avec GD .
  • Ce script essaie en fait de trouver le chapeau et, ce faisant, il peut faire pivoter l'image plusieurs fois et à chaque fois recherche des milliers et des milliers de pixels et d'indices. Ainsi, plus l'image est grande ou plus elle contient de pixels sombres, le script prendra plus de temps à terminer. Cela devrait prendre quelques secondes à une minute pour la majorité des images.
  • Je serais ravi de former davantage ce script, mais je n'ai pas assez de temps pour le faire.
  • Ce script n'est pas joué (encore une fois parce que je n'ai pas assez de temps), mais a beaucoup de potentiel pour jouer au golf en cas d'égalité.

Quelques exemples de chapeaux noirs détectés:

entrez la description de l'image ici

Ces exemples sont acquis en traçant des lignes rouges sur des points spéciaux trouvés sur l'image dont le script a décidé qu'il a un chapeau noir (les images peuvent avoir une rotation par rapport à celles d'origine).

Supplémentaire

Avant de poster ici, j'ai testé ce script sur un autre ensemble de 15 images, 10 avec un chapeau noir et 5 sans chapeau noir et cela s'est également bien passé pour toutes (100%).

Voici le fichier ZIP contenant des images de test supplémentaires que j'ai utilisées: extra.zip

Dans le extra/blackhatrépertoire, les résultats de détection avec des lignes rouges sont également disponibles. Par exemple, extra/blackhat/1.pngl'image de test extra/blackhat/1_r.pngest le résultat de la détection.

Nuit2
la source
Le tie-break n'est pas du golf de code. Au lieu de cela, les programmes sont alimentés en cas de test cachés jusqu'à ce que le bris d'égalité soit résolu. Je vais ensuite vous dire le résultat et publier les cas de test :)
Beta Decay
1
@BetaDecay: Merci pour la clarification, cette phrase (les gains les plus courts sur une égalité) était dans ma tête des versions précédentes de la question, donc je pensais que si une égalité se produit sur les cas de test cachés, alors le code le plus court l'emporte. Ma faute!
Night2
7
Vous gagnez également le prix du langage de traitement d'image le moins probable :)
Anush
@Anush Eh bien au moins PHP a imagerotateintégré, donc ...
user202729
Ce que j'aime avec PHP, c'est qu'il a des fonctionnalités de base pour presque tout. Il regroupe GD depuis tant d'années et GD répond en fait aux besoins les plus courants de travailler avec des images. Mais ce que j'aime le plus à propos de PHP, c'est qu'il y a toujours des extensions / packages qui vous en donneront plus (en raison de l'énorme communauté). Par exemple, il existe des extensions OpenCV pour PHP qui permettent d'effectuer un traitement d'image réel!
Night2
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

Amélioration de la version précédente, avec quelques contrôles ajoutés sur la forme des régions candidates.

Erreurs de classification dans l' ensemble HAT : images 4, 14, 15, 17 .

Erreurs de classification dans l'ensemble NON HAT : images 4 .

Quelques exemples d'images classées corrigées: entrez la description de l'image ici entrez la description de l'image ici

Exemple d'une image classée incorrecte:

entrez la description de l'image ici

ANCIENNE 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;

Approche basée sur l'érosion de l'image, similaire à la solution proposée par Mnemonic, mais basée sur le canal V de l'image HSV. De plus, la valeur moyenne du canal de la zone sélectionnée est vérifiée (pas sa taille).

Erreurs de classification dans l' ensemble HAT : images 4, 5, 10 .

Erreurs de classification dans l'ensemble NON HAT : images 4, 5, 6, 7, 13, 14 .

PieCot
la source
7

Pyth , 62,5%

<214.O.n'z

Accepte le nom de fichier d'un fichier image sur stdin. Renvoie Truesi la moyenne de toutes ses composantes de couleur RVB est supérieure à 214. Vous avez bien lu: les images apparemment noires ont tendance à être plus lumineuses que les images non noires.

(Certes, quelqu'un peut faire mieux, ce n'est pas du golf de code !)

Anders Kaseorg
la source
2
J'ai été étonné de la puissance de Pyth jusqu'à ce que je réalise: D
Beta Decay
Pendant un instant, j'ai pensé "Depuis quand Pyth a intégré pour reconnaître les images blackhat"
Luis felipe De jesus Munoz
2
∑je=2540(40je)240≈7.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

Cela détermine quels pixels sont noirs, puis érode les petites pièces contiguës. Il y a certainement place à amélioration ici.

Zacharý
la source