27
\$\begingroup\$

Challenge

Write code which, given an image of a panel from a random xkcd comic, returns a truthy value if Blackhat is in the comic or falsey if not.

Who is Blackhat?

Blackhat is the unofficial name given to the character in xkcd comics who wears a black hat:

Taken from the Explain xkcd page on Blackhat

Blackhat's hat is always straight sided, black and looks the same as in the above image.

Other characters may also have hats and hair but none will have hats which are black and straight sided.

Input

The image may be input in anyway you wish whether it be a path to the image or bytes via STDIN. You should not need to take a URL as input.

Rules

Hardcoding the answer is not banned, but it is not appreciated.

You are not allowed to access the internet to get the answer.

Examples

All images cropped from images from https://xkcd.com

Blackhat is in the panel (return truthy)


Blackhat is not in the panel (return falsey)


Test Battery

The 20 images which contain Blackhat can be found here: https://beta-decay.github.io/blackhat.zip

The 20 images which do not contain Blackhat can be found here: https://beta-decay.github.io/no_blackhat.zip

If you want more images to test your programs with (to train for the mystery test cases), you can find a list of all appearances of Blackhat here: http://www.explainxkcd.com/wiki/index.php/Category:Comics_featuring_Black_Hat

Winning

The program which correctly identifies whether Blackhat is in the comic or not for the most images wins. Your header should include your score as a percentage.

In the event of a tiebreak, the tied programs will be given "mystery" images (i.e. ones that only I know about). The code which identifies the most correctly wins the tiebreak.

The mystery images will be revealed along with the scores.

Note: it seems that Randall’s name for him may be Hat Guy. I prefer Blackhat though.

\$\endgroup\$
  • 12
    \$\begingroup\$ I'll not be surprised if Mathematica has a built-in for that. (For reference) \$\endgroup\$ – J. Sallé Jul 23 '18 at 17:04
  • 5
    \$\begingroup\$ Suggestion for a different tie breaker: have a different, smaller set of images (say 5 true cases and 5 false) that are unrevealed here, and the winner of the tie breaker is the one that generalises best to these unknown images. That would incentivize the more generic smarter solutions vs ones that overfit to these specific images. \$\endgroup\$ – sundar - Reinstate Monica Jul 23 '18 at 22:10
  • 3
    \$\begingroup\$ The test cases with the police and with the RIAA/MPAA are just evil. Good test battery, @BetaDecay. \$\endgroup\$ – sundar - Reinstate Monica Jul 24 '18 at 18:09
  • 1
    \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ – Beta Decay Jul 25 '18 at 20:48
  • 1
    \$\begingroup\$ @Night2 Sorry! I only planned to make any of there was tie. Nice work on 100% though! \$\endgroup\$ – Beta Decay Jul 30 '18 at 17:52
16
+500
\$\begingroup\$

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

To run it:

php <filename> <image_path>

Example:

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

Notes

  • Prints "true" if finds black hat and "false" if doesn't find it.
  • This should work on previous versions of PHP as well, but to be safe, use PHP>=7 with GD.
  • This script actually tries to find the hat and by doing so, it might rotate the image many many times and each time checks for thousands and thousands of pixels and clues. So the larger the image is or the more dark pixels it has, the script will take more time to finish. It should take a few seconds to a minute for majority of images though.
  • I would love to train this script more, but I don't have enough time to do so.
  • This script is not golfed (again because I don't have enough time), but has lots of potential to golf in case of a tie.

Some examples of detected black hats:

enter image description here

These examples are acquired by drawing red lines on special points found on the image that script decided has a black hat (images can have rotation compared to original ones).


Extra

Before posting here, I did test this script against another set of 15 images, 10 with black hat and 5 without black hat and it went correct for all of them as well (100%).

Here is the ZIP file containing extra test images I used: extra.zip

In the extra/blackhat directory, the detection results with red lines are also available. For example extra/blackhat/1.png is the test image and extra/blackhat/1_r.png is the detection result of it.

\$\endgroup\$
  • \$\begingroup\$ The tiebreak isn't code golf. Instead, the programs are fed hidden test cases until the tie break is resolved. I'll then tell you the result and post the test cases :) \$\endgroup\$ – Beta Decay Jul 29 '18 at 19:14
  • 1
    \$\begingroup\$ @BetaDecay: Thanks for clarification, this sentence (shortest wins on a tie) was in my head from previous versions of the question, so I was thinking that if a tie happens on hidden test cases, then shortest code wins. My bad! \$\endgroup\$ – Night2 Jul 29 '18 at 19:24
  • 7
    \$\begingroup\$ You win the prize for least likely image processing language too :) \$\endgroup\$ – Anush Jul 29 '18 at 20:58
  • \$\begingroup\$ @Anush Well at least PHP has imagerotate built-in, so... \$\endgroup\$ – user202729 Jul 30 '18 at 5:30
  • \$\begingroup\$ What I like about PHP is that it has some basic functionality for almost anything. It has bundled GD for so many years and GD actually satisfies most common needs of working with images. But what I like more about PHP is that there are always some extensions/packages which will give you more (because of having a huge community). For example there are OpenCV extensions for PHP which allow actual image processing to be done! \$\endgroup\$ – Night2 Jul 30 '18 at 6:35
8
\$\begingroup\$

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

Enhancement of the previous version, with some checks added on the shape of the candidate regions.

Classification errors in HAT set: images 4, 14, 15, 17.

Classification errors in NON HAT set: images 4.

Some examples of corrected classified images: enter image description here enter image description here

Example of a wrong classified image:

enter image description here

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

Approach based on image erosion, similar to the solution proposed by Mnemonic, but based on V channel of the HSV image. Moreover, the mean value of the channel of the selected area is checked (not its size).

Classification errors in HAT set: images 4, 5, 10.

Classification errors in NON HAT set: images 4, 5, 6, 7, 13, 14.

\$\endgroup\$
7
\$\begingroup\$

Pyth, 62.5%

<214.O.n'z

Accepts the filename of an image file on stdin. Returns True if the average of all its RGB color components are greater than 214. You read that right: apparently blackhat images tend to be brighter than no-blackhat images.

(Surely someone can do better—this isn’t !)

\$\endgroup\$
  • 2
    \$\begingroup\$ I was amazed at the power of Pyth until I realised :D \$\endgroup\$ – Beta Decay Jul 26 '18 at 19:38
  • \$\begingroup\$ For an instant I thought "Since when Pyth has a built in for recognizing blackhat images" \$\endgroup\$ – Luis felipe De jesus Munoz Jul 26 '18 at 19:40
  • 2
    \$\begingroup\$ 62.5% is 25 out of 40 images. A random guessing program (with fixed seed, something like that) would have a probability of \${\sum_{i=25}^{40} {40 \choose i} \over 2^{40}} \approx 7.7\% \$ of doing at least as good as that. \$\endgroup\$ – user202729 Jul 27 '18 at 4:35
6
\$\begingroup\$

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

This figures out which pixels are black, then erodes away small contiguous pieces. Certainly room for improvement here.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.