Wildcard 100

問題

問題は、手書きで書かれた「3」と「6」の大量の画像を渡され、それを以下の要領で処理し、最終的な「3」と「6」の画像の枚数を答える、というものです。

なお画像はMNISTという画像セットの一部のようです。

MNIST handwritten digit database, Yann LeCun, Corinna Cortes and Chris Burges

f:id:fatsheep:20190922155803p:plain — 手書きの3と6の画像群

画像は全部で34022枚あり、そのうち16768枚の画像が「3」
ファイル名は連番であるが、「3」と「6」は順番になっていない
クラスタアルゴリズムなどを使って「3」と「6」を仕分ける
重複した画像があるので重複排除し、「3」と「6」の画像の枚数を答える

Writeup

3と6に分類するためにK-means法を使えないか試してみました。いくつかライブラリなどをインストールし、Pythonでコードを書きました。

カテゴリ数の指定は、画像の種類が「3」と「6」しかないので、2カテゴリの分類で走らせてみました。

コードは以下の通りで、画像をグレースケール（白黒画像で、一番暗いところが0、一番明るいところが255で表現される）で読み込み画像群の2次元配列を作成、それをK-meansにかけクラスタリング、最後にクラスタリングの結果をもとに画像をリネームする、という流れです。

#!/usr/bin/env python

import cv2
import os
from sklearn.cluster import KMeans

imlist = []

# Input images
files = os.listdir('data/')
for file in files:
    tempimage = cv2.imread("data/" + file, 0)
    imlist.append(tempimage.flatten())

# Clustering
result = KMeans(n_clusters=2).fit_predict(imlist)

# Rename files
for i in range(0,len(files)):
    if result[i]==0:
        os.rename('data/' + files[i] , 'data/c0_' + files[i])
    else:
        os.rename('data/' + files[i] , 'data/c1_' + files[i])

結果としては以下のように、なんとなく分類されたようです。

f:id:fatsheep:20190922162219p:plain

また枚数を確認したところ、カテゴリ0（「3」の画像）の個数は16768で、問題で記載されていた枚数と一致したため、うまく分類してくれたようです。

# ls -l data/c0_* | wc -l
16768

正直かなり微妙な感じの画像もありましたが、K-Meansがうまいこと処理してくれました。

分類は成功した（テイ）のであとは重複排除です。同じファイルを排除する、ということで、分類された画像を単純にハッシュ値計算して重複排除します。

# md5sum data/c0_* | cut -d' ' -f1 | sort -u | wc -l
14963
# md5sum data/c1_* | cut -d' ' -f1 | sort -u | wc -l
347

これで答え（TMCTF{14963_347}）が得られたので意気揚々に投入！したのですが通らず・・　途中のクラスタリングが間違っていたかな、、とも思いざっと目視で画像を確認したのですがそのようなものは見つからず。

ここでふと頭をよぎったのが、同じ画像でもファイルとしては別のものがあるんじゃないかということです。

そこでスクリプトを改造し、読み込んだ画像の配列をスクリプトの中で重複排除する（同じ画素値の列を持っている配列要素を削除する）ようにしました。

#!/usr/bin/env python

import cv2
import os
from sklearn.cluster import KMeans

imlist = []
imlist0 = []
imlist1 = []

# Input images
files = os.listdir('data/')
for file in files:
    tempimage = cv2.imread("data/" + file, 0)
    imlist.append(tempimage.flatten())

# Clustering
result = KMeans(n_clusters=2).fit_predict(imlist)

# Dedup
for i in range(0,len(files)):
    if result[i]==0:
        imlist0.append(imlist[i])
    else:
        imlist1.append(imlist[i])
print("c0:")
print(len(set(list(map(tuple,imlist0)))))
print("c1:")
print(len(set(list(map(tuple,imlist1)))))