[Question]
  [
## 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](http://www.explainxkcd.com/wiki/index.php/Black_Hat) is the unofficial name given to the character in xkcd comics who wears a black hat:
![](https://www.explainxkcd.com/wiki/images/6/6d/BlackHat_head.png)
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`)
![](https://i.stack.imgur.com/w4ngj.jpg)
---
![](https://i.stack.imgur.com/LAork.jpg)
### Blackhat is not in the panel (return `falsey`)
![](https://i.stack.imgur.com/f4wSK.jpg)
---
![](https://i.stack.imgur.com/x6ZV5.jpg)
## 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.
  
[Answer]
# [PHP](http://www.php.net/) (>=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](http://php.net/manual/en/book.image.php).
* 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](https://i.stack.imgur.com/mwx0q.png)](https://i.stack.imgur.com/mwx0q.png)
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](https://www.dropbox.com/s/1krz98hd8mbsetb/extra.zip?dl=1)
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.
[Answer]
## 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](https://i.stack.imgur.com/j0mUm.png)](https://i.stack.imgur.com/j0mUm.png)
[![enter image description here](https://i.stack.imgur.com/ldwBM.png)](https://i.stack.imgur.com/ldwBM.png)
Example of a wrong classified image:
[![enter image description here](https://i.stack.imgur.com/H9yES.png)](https://i.stack.imgur.com/H9yES.png)
**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**.
[Answer]
# [Pyth](https://github.com/isaacg1/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 [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'")!)
[Answer]
# 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.
]