Pattern Recognition (Mine) - パターン認識

どんな問題？

Pattern Recognition
http://www.checkio.org/mission/matrix-pattern/

0と1のモノクロ画像データから、指定のパターンを見つけ出せ。

引数では、パターンと画像が、0と1 の list of list で指定される。
画像の上から順にスキャンしていき、パターンが見つかれば、画像データの 0→2、1→3 の変換を行う。パターンが重なっている場合は、最初に見つかったパターン（左上）が優先される。
戻り値は、変換した画像データを返す。

パターン、画像とも、幅と高さは10以下。

例題：

checkio([[1, 0], [1, 1]],
        [[0, 1, 0, 1, 0],
         [0, 1, 1, 0, 0],
         [1, 0, 1, 1, 0],
         [1, 1, 0, 1, 1],
         [0, 1, 1, 0, 0]]) == [[0, 3, 2, 1, 0],
                               [0, 3, 3, 0, 0],
                               [3, 2, 1, 3, 2],
                               [3, 3, 0, 3, 3],
                               [0, 1, 1, 0, 0]]
checkio([[1, 1], [1, 1]],
        [[1, 1, 1],
         [1, 1, 1],
         [1, 1, 1]]) == [[3, 3, 1],
                         [3, 3, 1],
                         [1, 1, 1]]

どうやって解く？

画像の左上から順番に、パターンと同じサイズを切り出して調べていけばいいかな。
画像 image から、位置(x,y)とサイズ(pw,ph)を指定して取り出すには、

[image[iy][x:x + pw] for iy in range(y, y + ph)]

となる。これをパターンと比較すればいい。

パターンが見つかったときの、0→2、1→3 の変換もスライスを使って行った。

for iy in range(y, y + ph):
    image[iy][x:x + pw] = [e + 2 for e in image[iy][x:x + pw]]

メモ：スライスを使ったリストの置換

今まであまり使ったことがなかったが、Pythonでは、スライスを使ってリストの要素を置換できる。

>>> a = [1, 2, 3, 4, 5]
>>> a[2:4]
[3, 4]
>>> a[2:4] = [6, 7]  # スライスに代入
>>> a
[1, 2, 6, 7, 5]
>>> a[2:4] = [8, 9, 10]  # 要素数が異なってもOK
>>> a
[1, 2, 8, 9, 10, 5]

まとめ

def checkio(pattern, image):
    pw, ph = len(pattern[0]), len(pattern)
    iw, ih = len(image[0]), len(image)
    for y in range(ih - ph + 1):
        for x in range(iw - pw + 1):
            if [image[iy][x:x + pw] for iy in range(y, y + ph)] == pattern:
                for iy in range(y, y + ph):
                    image[iy][x:x + pw] = [e + 2 for e in image[iy][x:x + pw]]
    return image

http://www.checkio.org/mission/matrix-pattern/publications/natsuki/python-3/first/