Mono Captcha (Incinerator) - 画像から数字を読み取れ

どんな問題？

Mono Captcha
http://www.checkio.org/mission/mono-captcha/

0と1からなる画像データには、数字が表示されている。この数字を読み取れ。
各数字は 3×5ピクセル、桁と桁の間には1ピクセル幅のスペースが入る。
各数字には1ピクセル以内のノイズが含まれることがある。

電光掲示板の数字を読み取るような感じ。
画像にはノイズが含まれるので、フォントと完全に一致するわけではないのがポイント。

各数字は必ず幅3ピクセルで表示される。数字の「1」のフォントは、左側の2ピクセルの幅しか使っていないが、右に1ピクセルずれることは無いようだ。また、画像データの左端と右端は必ずスペースになっている。

例題：

checkio([[0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0],
         [0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0],
         [0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0],
         [0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0],
         [0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0]]) == 394
checkio([[0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0],
         [0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0],
         [0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0],
         [0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0],
         [0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0]]) == 394

2個目の問題にはノイズが含まれている。

どうやって解く？

引数の画像データ(image)を分解する。
フォントデータと比較して、最もエラーの少ない数字を探す。

という流れかな。あらかじめ0～9のフォントデータを作成しておく方がいいかもしれない。

引数の分解

引数(image)は、下記のような list of listで渡される。

[[0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0],
 [0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0],
 [0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0],
 [0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0],
 [0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0]]

まず、ここから、数字を1桁ずつ取り出す関数を作った。
imageの分割は、単純にindex=1～3が1文字目、index=5～7が2文字目、としている。

def split_image(image):
    for i in range(1, len(image[0]), 4):
        yield [c for line in image for c in line[i: i + 3]]

数字1桁ごとに、横3ピクセル×高さ5ピクセルの合計15ピクセルのリストを生成する。数字の0なら

[1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1]

となる。

フォント辞書の作成

数字フォントのデータは、FONT定数として '-' と 'X' で定義されている。

FONT = ("--X--XXX-XXX-X-X-XXX--XX-XXX-XXX--XX-XX--"
        "-XX----X---X-X-X-X---X-----X-X-X-X-X-X-X-"
        "--X---XX--X--XXX-XX--XXX--X--XXX-XXX-X-X-"
        "--X--X-----X---X---X-X-X-X---X-X---X-X-X-"
        "--X--XXX-XXX---X-XX---XX-X---XXX-XX---XX-")

まぎらわしいが、長～い1つの文字列である。
1234567890 という順番で並んでいるので、これを1文字分ずつ分割する。
比較しやすくするために、引数と同じ15ピクセルのリストに変換しておきたい。

まず、FONT定数を、引数の画像データと同じ形式（list of list）に変換する。
それを先ほど作成した split_image() 関数で1文字ずつ分解する。
そして、各数字のフォントデータを、'0'～'9'をKeyとする辞書に格納する。

def make_font_dic():
    # 文字列の'-'と'X'を、0と1に変換
    data = [1 if c == 'X' else 0 for c in FONT]

    # 画像データと同じ形式に変換
    width = len(data) // 5
    image = [data[i:i + width] for i in range(0, len(data), width)]

    # 1文字ずつ '0'～'9'をキーとする辞書に格納
    return dict(zip('1234567890', split_image(image)))

FONT_DIC = make_font_dic()

これで、FONT_DIC['1'] とすれば、数字1のフォントデータが得られるようになった。

引数の画像データとフォントデータを比較する

引数の画像データから1文字分取り出して、フォント辞書から最もエラーが少ない数字を選び出す。

def checkio(image):
    def get_error_count(pixels, font):
        return len([i for i in range(len(font)) if pixels[i] != font[i]])

    result = ''
    for data in split_image(image):
        result += min(FONT_DIC, key=lambda k: get_error_count(data, FONT_DIC[k]))
    return int(result)

問題文では、1文字につきノイズ（エラー）は1ピクセルまでと決められていた。
上のコードでは、もっともエラーの少ない数字が選ばれているが、エラーが2以上なら例外を出した方がいいかもしれない。

def checkio(image):
    def get_error_count(pixels, font):
        return len([i for i in range(len(font)) if pixels[i] != font[i]])

    result = ''
    for data in split_image(image):
        error, num = min((get_error_count(data, FONT_DIC[n]), n) for n in FONT_DIC)
        if error > 1:
            raise Exception('too much error')
        result += num
    return int(result)

まとめ

FONT = ("--X--XXX-XXX-X-X-XXX--XX-XXX-XXX--XX-XX--"
        "-XX----X---X-X-X-X---X-----X-X-X-X-X-X-X-"
        "--X---XX--X--XXX-XX--XXX--X--XXX-XXX-X-X-"
        "--X--X-----X---X---X-X-X-X---X-X---X-X-X-"
        "--X--XXX-XXX---X-XX---XX-X---XXX-XX---XX-")

def split_image(image):
    for i in range(1, len(image[0]), 4):
        yield [c for line in image for c in line[i: i + 3]]

def make_font_dic():
    data = [1 if c == 'X' else 0 for c in FONT]
    width = len(data) // 5
    image = [data[i:i + width] for i in range(0, len(data), width)]
    return dict(zip('1234567890', split_image(image)))

FONT_DIC = make_font_dic()  # ex. FONT_DIC['0'] = [1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1]

def checkio(image):
    def get_error_count(pixels, font):
        return len([i for i in range(len(font)) if pixels[i] != font[i]])

    result = ''
    for data in split_image(image):
        error, num = min((get_error_count(data, FONT_DIC[n]), n) for n in FONT_DIC)
        if error > 1:
            raise Exception('too much noise')
        result += num
    return int(result)

よし完成！

summer_tree_home

Check iOでPython3をマスターするぜっ