Where's Blackhat?

27

5

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.

Beta Decay

Posted 2018-07-23T16:30:32.483

Reputation: 21 478

Major stumbling blocks in no_blackhat.zip: #10 the pilot; #19 the webcams – Jonathan Allan – 2018-07-23T16:39:09.527

@JonathanAllan Similarly in blackhat.zip: #6 two hat black hat and #16 blackhat with a bit of hair – Beta Decay – 2018-07-23T16:42:15.363

12

I'll not be surprised if Mathematica has a built-in for that. (For reference)

– J. Sallé – 2018-07-23T17:04:56.517

5Suggestion 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. – sundar - Reinstate Monica – 2018-07-23T22:10:16.787

3The test cases with the police and with the RIAA/MPAA are just evil. Good test battery, @BetaDecay. – sundar - Reinstate Monica – 2018-07-24T18:09:52.923

1

Let us continue this discussion in chat.

– Beta Decay – 2018-07-25T20:48:03.963

Relevant: "How do I find Waldo with Mathematica", which implements small-area-of-red-and-white-stripes detection in an arbitrary image https://stackoverflow.com/questions/8479058/how-do-i-find-waldo-with-mathematica

– Sparr – 2018-07-26T02:26:42.343

@BetaDecay: Thanks for the bounty! I am curious to see your hidden/mystery images and test my script with them too (but never mind if you haven't created that set yet). – Night2 – 2018-07-30T17:00:37.183

1@Night2 Sorry! I only planned to make any of there was tie. Nice work on 100% though! – Beta Decay – 2018-07-30T17:52:44.140

Answers

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

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.

Night2

Posted 2018-07-23T16:30:32.483

Reputation: 5 484

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 :) – Beta Decay – 2018-07-29T19:14:11.613

1@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! – Night2 – 2018-07-29T19:24:45.180

7You win the prize for least likely image processing language too :) – Anush – 2018-07-29T20:58:32.837

@Anush Well at least PHP has imagerotate built-in, so... – user202729 – 2018-07-30T05:30:33.767

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!

– Night2 – 2018-07-30T06:35:29.363

Checkout Mathematica :) (unfortunately it's not free) – user202729 – 2018-07-31T03:57:34.433

@BetaDecay What's hidden test case score? – user202729 – 2018-07-31T03:58:25.367

We need a golf challenge for solutions that get 100% now. – Anush – 2018-07-31T06:48:24.457

@user202729 There wasn’t a tie, so no hidden test cases were needed – Beta Decay – 2018-07-31T09:09:45.777

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

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.

PieCot

Posted 2018-07-23T16:30:32.483

Reputation: 1 039

7

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

Anders Kaseorg

Posted 2018-07-23T16:30:32.483

Reputation: 29 242

2I was amazed at the power of Pyth until I realised :D – Beta Decay – 2018-07-26T19:38:40.930

For an instant I thought "Since when Pyth has a built in for recognizing blackhat images" – Luis felipe De jesus Munoz – 2018-07-26T19:40:05.267

262.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. – user202729 – 2018-07-27T04:35:08.517

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

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

user48543

Posted 2018-07-23T16:30:32.483

Reputation: