問題
birthday0410.contest.atcoder.jp
解法
343点までしか取れていませんが，満点を取ろうとするとキツいので勘弁して下さい。
まずはノイズを取るためにメディアンフィルタをかけます。注目している画素と，そのマスの周囲8画素の合計9画素の中で黒と白の多いほうに置き換えるだけです。かなりきれいにノイズが取れます。
フィルタ前
フィルタ後
次にUnionFindなどを使って連結成分を取り出します。この問題で与えられる文字は，幸運なことに「÷」のように複数の連結成分で構成されている文字が無くどの文字も連結しているため，連結成分を取り出せば1文字を取り出すことが出来ます。また，連結成分のx座標の重心を計算してソートすれば左の文字から右の文字へ並べ替えることが出来ます。
このとき，メディアンフィルタで取り切れていないノイズが存在するかもしれないので，連結成分の大きさがしきい値よりも小さい場合には無視するといった処理を入れると良いかもしれません。
ここまでの処理で1文字分の画像を取り出すことができます。入力を文字ごとに分割して出力するまでの処理を以下に示します。
#include <bits/stdc++.h> using namespace std; #define int long long #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define DEBUG(x) cerr << #x << " = " << x << endl const int INF = (int)1e9; const int param_R = 1; const int param_I = 5; const int param_nrows = 65; const int param_ncols = 38; struct UnionFind { vector<int> data; UnionFind(int v) : data(v, -1) {} int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); } bool same(int x, int y) { return root(x) == root(y); } int size(int x) { return -data[root(x)]; } void merge(int x, int y) { x = root(x), y = root(y); if (x != y) { if (size(y) > size(x)) swap(x, y); data[x] += data[y]; data[y] = x; } } }; int T, W, H; bool B[65][9001]; bool B_next[65][9001]; int L[65][9000]; void median_filter() { REP(i,H) REP(j,W) { int w = 0, b = 0; const int R = param_R; for(int dy = -R; dy <= R; ++dy) for(int dx = -R; dx <= R; ++dx) { int ny = i + dy; int nx = j + dx; if(0 <= ny && ny < H && 0 <= nx && nx < W) { (B[ny][nx] == 0 ? w : b) += 1; } } B_next[i][j] = (b > w); } REP(i,H) REP(j,W) B[i][j] = B_next[i][j]; } void input() { cin >> T >> W >> H; REP(i, H) { string S; cin >> S; REP(j, W) { B[i][j] = (S[j] == '#'); } } } int labeling() { UnionFind unionFind(W*H); REP(i,H) REP(j,W) { for(int dy = -1; dy <= 1; ++dy) for(int dx = -1; dx <= 1; ++dx) { int ny = i + dy; int nx = j + dx; if(0 <= ny && ny < H && 0 <= nx && nx < W) { if(B[i][j] && B[ny][nx]) unionFind.merge(i*W + j, ny*W + nx); } } } map<int, int> labels; REP(i,H) REP(j,W) { if(B[i][j]) { if(unionFind.size(i*W + j) <= param_I) { B[i][j] = false; } else { labels[unionFind.root(i*W + j)] = -1; } } } { int n = 0; for(auto &iter : labels) iter.second = n++; } memset(L, -1, sizeof(L)); REP(i,H) REP(j,W) { if(B[i][j]) { L[i][j] = labels[unionFind.root(i*W + j)]; } } return labels.size(); } vector<vector<vector<bool>>> split_chars(int n_labels) { vector<int> C(n_labels, 0); vector<int> cx(n_labels, 0); vector<int> cy(n_labels, 0); REP(i,H) REP(j,W) { if(L[i][j] != -1) { ++C[L[i][j]]; cy[L[i][j]] += i; cx[L[i][j]] += j; } } vector<pair<int, int>> center_sort; REP(n,n_labels) { cy[n] /= C[n]; cx[n] /= C[n]; center_sort.emplace_back(cx[n], n); } map<int, int> label_to_pos; sort(center_sort.begin(), center_sort.end()); { REP(i,n_labels) { label_to_pos[center_sort[i].second] = i; } } vector<vector<vector<bool>>> MB( n_labels, vector<vector<bool>>( param_nrows, vector<bool>(param_ncols, false))); REP(i,H) REP(j,W) { if(L[i][j] != -1) { int pos = label_to_pos[L[i][j]]; int y = i - (cy[L[i][j]] - param_nrows / 2); int x = j - (cx[L[i][j]] - param_ncols / 2); MB[pos][y][x] = true; } } return MB; } void output_each(vector<vector<vector<bool>>> chars) { cout << chars.size() << endl; REP(k,chars.size()) { cout << param_ncols << ' ' << param_nrows << endl; REP(i,param_nrows) { REP(j,param_ncols) { cout << (chars[k][i][j] ? '#' : '.'); } cout << endl; } } } signed main() { input(); median_filter(); median_filter(); int n_labels = labeling(); vector<vector<vector<bool>>> chars = split_chars(n_labels); output_each(chars); }
あとは文字認識を実装すればよいだけです。今回は画素値をそのまま特徴量として線形SVMに突っ込む方法で，どこまでのスコアが得られるのか確かめました。
まず学習用のデータセットを作る必要があります。問題文に書いてあるデータ生成の手順に従ってデータを生成する方法が正攻法な気がしますが，今回は問題ページで配布されている X_data.zip の中身を↑のコードで1文字ごとに分割したものを使いました。出力された文字ごとの画像を人手で分類したものを配布します。有効に活用してください。
前述したように，今回は画素値をそのまま特徴量として入力し，線形SVMで分類しました。性能を考えれば畳み込みニューラルネットワークを使うのが最も良い選択だと思いますが，AtCoderのような形式では以下のような理由で使いにくいです。
- モデルを学習する時点では手元で動作させるので便利なライブラリを使い放題ですが，AtCoderでは各プログラミング言語の標準以外のライブラリはほとんど使用できないので，推論を行う部分はライブラリを使わずに自分で書く必要があります。
- 問題ページに書いてあるように「AtCoderで送信できるソースコードはUTF-8で60,000文字以下」という厳しい制約があり，学習したモデルのパラメータをソースコードに埋め込むことを考えるとパラメータ数が大きくなる方法は使えません。
SVMのような線形分類器なら，推論の部分は を計算するだけなので簡単に実装できます。問題は重みベクトル
の部分がソースコードに埋め込めるサイズになるかどうかなのですが，普通にやると60,000文字制限に引っかかるのでL1正則化を使って重みベクトルをスパース (非ゼロ要素が少ないベクトル) にして圧縮します。学習にはscikit-learnに入っているLIBLINEARを使いました。学習部分のソースコードを以下に示します。
# coding: UTF-8 from __future__ import absolute_import, division, print_function, unicode_literals import os import sys import glob import cv2 import scipy import sklearn.svm import sklearn.grid_search import sklearn.metrics import sklearn.externals # http://d.hatena.ne.jp/hoxo_m/20110618/p1 def best_cv_num(n): return int(1+scipy.log2(n)) def main(): tags = '0 1 2 3 4 5 6 7 8 9 lp rp plus minus mul div'.split() X = [] y = [] for i, tag in enumerate(tags): fnames = glob.glob(os.path.join('annotated', tag, '*.png')) for fname in fnames: # グレースケールとして読み込む img = cv2.imread(fname, flags=0) img = img.flatten() # H行W列の行列から1行H*W列のベクトルに変換 X.append(img) y.append(i) X = scipy.vstack(X) # 黒=0, 白=255 から 黒=1, 白=0に変換 X[X == 255] = 1 X = 1 - X # L1正則化のときはdual=Trueは使えない clf = sklearn.svm.LinearSVC(penalty='l1', dual=False) params = { 'C': scipy.logspace(-5, 15, base=2, num=1000), } # グリッドサーチで良いパラメータを探す # 正解率を評価指標としてクロスバリデーション cv = sklearn.grid_search.RandomizedSearchCV( clf, params, n_iter=30, scoring='accuracy', n_jobs=-1, cv=best_cv_num(len(y)), verbose=3) cv.fit(X, y) # モデルデータをファイルに保存する sklearn.externals.joblib.dump(cv.best_estimator_, 'model/svm.pkl') print('best_score_ =', cv.best_score_) print('best_params_ =', cv.best_params_) print(tags) print(sklearn.metrics.confusion_matrix(y, cv.predict(X))) if __name__ == '__main__': main()
得られたモデルで文字認識を実装した結果，317点が得られました。
http://birthday0410.contest.atcoder.jp/submissions/602453
問題ページに書いてある方法で学習データを増やすことで343点まで上がりました。
http://birthday0410.contest.atcoder.jp/submissions/602474
この問題では，数式の中のどれか1文字を誤認識するだけで誤答となってしまうため，99%の性能が得られていても十分ではありません。画素値をそのまま特徴量とする方法では，画素と画素の隣接関係などがモデルで表現できていないため，どうしても性能が落ちてしまいます。今後の展望として，文字の幅，高さ，黒画素の割合，穴の数，モーメントといった自明な特徴量を導入することなどが考えられます。
