Tantangan

Tulis kode yang, diberi gambar panel dari komik xkcd acak, mengembalikan nilai kebenaran jika Blackhat ada di komik atau falsey jika tidak.

Siapa Blackhat?

Blackhat adalah nama tidak resmi yang diberikan kepada karakter dalam komik xkcd yang mengenakan topi hitam:

_{Diambil dari halaman Jelaskan xkcd di Blackhat}

Topi Blackhat selalu bersisi lurus, hitam dan terlihat sama seperti pada gambar di atas.

Karakter lain mungkin juga memiliki topi dan rambut, tetapi tidak ada yang memiliki topi hitam dan lurus.

Memasukkan

Gambar dapat dimasukkan dengan cara apa pun yang Anda inginkan apakah itu jalur ke gambar atau byte melalui STDIN. Anda tidak perlu mengambil URL sebagai input.

Aturan

Hardcoding jawabannya tidak dilarang, tetapi tidak dihargai.

Anda tidak diizinkan mengakses internet untuk mendapatkan jawabannya.

Contohnya

_{Semua gambar dipotong dari gambar dari https://xkcd.com}

Blackhat ada di panel (kembali `truthy`)

Blackhat tidak ada di panel (kembali `falsey`)

Uji Baterai

Ke-20 gambar yang mengandung Blackhat dapat ditemukan di sini: https://beta-decay.github.io/blackhat.zip

Ke-20 gambar yang tidak mengandung Blackhat dapat ditemukan di sini: https://beta-decay.github.io/no_blackhat.zip

Jika Anda ingin lebih banyak gambar untuk diuji dengan program Anda (untuk melatih kasus-kasus uji misteri), Anda dapat menemukan daftar semua penampilan Blackhat di sini: http://www.explainxkcd.com/wiki/index.php/Category: Comics_featuring_Black_Hat

Kemenangan

Program yang mengidentifikasi dengan benar apakah Blackhat ada di komik atau tidak untuk sebagian besar gambar yang menang. Header Anda harus memasukkan skor Anda sebagai persentase.

Jika terjadi tiebreak, program yang diikat akan diberi gambar "misteri" (yaitu yang hanya saya ketahui). Kode yang mengidentifikasi paling benar memenangkan tiebreak.

Gambar misteri akan terungkap bersama dengan skor.

Catatan: sepertinya nama Randall untuknya mungkin Hat Guy. Saya lebih suka Blackhat.

code-challenge image-processing test-battery Peluruhan Beta
sumber

12

Saya tidak akan terkejut jika Mathematica memiliki bawaan untuk itu. ( Untuk referensi )

J. Sallé

5

Saran untuk tie breaker yang berbeda: miliki set gambar yang berbeda dan lebih kecil (misalkan 5 case benar dan 5 false) yang belum diungkap di sini, dan pemenang tie breaker adalah yang paling umum untuk gambar yang tidak diketahui ini. Itu akan memberi insentif pada solusi cerdas yang lebih umum vs solusi yang sesuai dengan gambar spesifik ini.

sundar - Reinstate Monica

3

Kasus uji dengan polisi dan RIAA / MPAA adalah kejahatan. Baterai uji bagus, @BetaDecay.

sundar - Reinstate Monica

1

Mari kita lanjutkan diskusi ini dalam obrolan .

Beta Decay

1

@ Night2 Maaf! Saya hanya berencana untuk membuat dasi. Kerja bagus di 100%!

Beta Decay

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

Untuk menjalankannya:

php <filename> <image_path>

Contoh:

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

Catatan

Mencetak "benar" jika menemukan topi hitam dan "salah" jika tidak menemukannya.
Ini harus bekerja pada versi PHP sebelumnya juga, tetapi agar aman, gunakan PHP> = 7 dengan GD .
Script ini sebenarnya mencoba menemukan topinya dan dengan melakukannya, ia mungkin memutar gambar berkali-kali dan setiap kali memeriksa ribuan dan ribuan piksel dan petunjuk. Jadi, semakin besar gambar atau piksel yang lebih gelap, skrip akan membutuhkan lebih banyak waktu untuk selesai. Namun, perlu beberapa detik hingga satu menit untuk sebagian besar gambar.
Saya ingin sekali melatih naskah ini, tetapi saya tidak punya cukup waktu untuk melakukannya.
Skrip ini tidak golf (lagi karena saya tidak punya cukup waktu), tetapi memiliki banyak potensi untuk bermain golf jika ada seri.

Beberapa contoh topi hitam yang terdeteksi:

Contoh-contoh ini diperoleh dengan menggambar garis merah pada titik-titik khusus yang ditemukan pada gambar yang skrip memutuskan memiliki topi hitam (gambar dapat memiliki rotasi dibandingkan dengan yang asli).

Tambahan

Sebelum memposting di sini, saya melakukan pengujian skrip ini terhadap 15 gambar lainnya, 10 dengan topi hitam dan 5 tanpa topi hitam dan semuanya benar (100%).

Ini adalah file ZIP yang berisi gambar uji ekstra yang saya gunakan: extra.zip

Dalam extra/blackhatdirektori, hasil deteksi dengan garis merah juga tersedia. Misalnya extra/blackhat/1.pngadalah gambar uji dan extra/blackhat/1_r.pngmerupakan hasil pendeteksian.

Night2
sumber

Tiebreak bukan kode golf. Sebagai gantinya, program diberi makan kasus uji tersembunyi sampai tie break diselesaikan. Saya kemudian akan memberi tahu Anda hasilnya dan memposting uji kasus :)

Beta Decay

1

@BetaDecay: Terima kasih atas klarifikasi, kalimat ini (kemenangan tersingkat pada seri) ada di kepala saya dari versi pertanyaan sebelumnya, jadi saya berpikir bahwa jika dasi terjadi pada kasus uji tersembunyi, maka kode tersingkat menang. Salahku!

Night2

7

Anda memenangkan hadiah untuk bahasa pemrosesan gambar paling tidak mungkin :)

Anush

@Anush Yah setidaknya PHP memiliki imagerotatebuilt-in, jadi ...

user202729

Yang saya sukai tentang PHP adalah ia memiliki beberapa fungsi dasar untuk hampir semua hal. Ini telah membundel GD selama bertahun-tahun dan GD sebenarnya memenuhi sebagian besar kebutuhan umum bekerja dengan gambar. Tetapi yang saya sukai tentang PHP adalah selalu ada beberapa ekstensi / paket yang akan memberi Anda lebih banyak (karena memiliki komunitas yang besar). Misalnya ada ekstensi OpenCV untuk PHP yang memungkinkan pemrosesan gambar aktual dilakukan!

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

Peningkatan versi sebelumnya, dengan beberapa cek ditambahkan pada bentuk wilayah kandidat.

Kesalahan klasifikasi dalam set HAT : gambar 4, 14, 15, 17 .

Kesalahan klasifikasi dalam set NON HAT : gambar 4 .

Beberapa contoh gambar rahasia yang dikoreksi:

Contoh gambar rahasia yang salah:

VERSI LAMA (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;

Pendekatan berdasarkan erosi gambar, mirip dengan solusi yang diusulkan oleh Mnemonic, tetapi berdasarkan pada saluran V dari gambar HSV. Selain itu, nilai rata-rata saluran dari area yang dipilih diperiksa (bukan ukurannya).

Kesalahan klasifikasi dalam set HAT : gambar 4, 5, 10 .

Kesalahan klasifikasi dalam set NON HAT : gambar 4, 5, 6, 7, 13, 14 .

PieCot
sumber

7

Pyth , 62,5%

<214.O.n'z

Menerima nama file file gambar di stdin. Kembali Truejika rata-rata semua komponen warna RGB-nya lebih besar dari 214. Anda membacanya dengan benar: rupanya gambar blackhat cenderung lebih cerah daripada gambar no-blackhat.

(Tentunya seseorang dapat berbuat lebih baik — ini bukan golf kode !)

Anders Kaseorg
sumber

2

Saya kagum pada kekuatan Pyth sampai saya menyadari: D

Beta Decay

Untuk sesaat aku berpikir, "Sejak kapan Pyth memiliki built-in untuk mengenali gambar blackhat"

Luis felipe De jesus Munoz

2

\frac{\sum_{i = 25}^{40} (\binom{40}{i})}{2^{40}} \approx 7.7 %

${\sum_{i=25}^{40} {40 \choose i} \over 2^{40}} \approx 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

Ini menentukan piksel mana yang hitam, lalu mengikis potongan kecil yang berdekatan. Tentunya ruang untuk perbaikan di sini.

Zacharý
sumber

Di mana Blackhat?

Tantangan

Siapa Blackhat?

Memasukkan

Aturan

Contohnya

Blackhat ada di panel (kembali `truthy`)

Blackhat tidak ada di panel (kembali `falsey`)

Uji Baterai

Kemenangan

Jawaban:

PHP (> = 7), 100% (40/40)

Catatan

Beberapa contoh topi hitam yang terdeteksi:

Tambahan

Matlab, 87,5%

Pyth , 62,5%

Python 2, 65% 72,5% 77,5% (= 31/40)

Di mana Blackhat?

Tantangan

Siapa Blackhat?

Memasukkan

Aturan

Contohnya

Blackhat ada di panel (kembali truthy)

Blackhat tidak ada di panel (kembali falsey)

Uji Baterai

Kemenangan

Jawaban:

PHP (> = 7), 100% (40/40)

Catatan

Beberapa contoh topi hitam yang terdeteksi:

Tambahan

Matlab, 87,5%

Pyth , 62,5%

Python 2, 65% 72,5% 77,5% (= 31/40)

Blackhat ada di panel (kembali `truthy`)

Blackhat tidak ada di panel (kembali `falsey`)