Ofuton Reading (Android app)

Ofuton Reading

app for reading in your bed

GooglePlay

award

GitHub

 

おふとんリーディング (Androidアプリ)

おふとんリーディング

寝ながら本を読むためのアプリです。

GooglePlay

授賞式

GitHub

 

傾き・反り・影がある文書画像の行認識(その4)

前回の記事から1週間ちょっとたちました。
プロットした点から外れ値を取り除きました。

外れ値を取り除いた

点が2つだけになった列が残っているのはあまり気にしないでください。消します。

やらなければならないこと

1. 曲線が直線になるように画像を変形する

2つの線の幅が変わるから(たとえば500ピクセルあった幅が400ピクセルになる)、どのピクセルを選ぶかというアルゴリズムを考えたが、その実装をしてない。

曲線の方程式を引数に渡したものの、制御点を渡すのを忘れてた。3次スプライン曲線は複数の3次関数をつなぎ合わせたものだって認識がどうも抜けるな。

2. 3次スプライン曲線の制御点を増やす

ご覧の通り、プロットした点に沿った曲線になっていない(左端のほうはほぼぴったりでも右端のほうは直線状になっているなど)。いまは3次関数を2つだけ繋いでいる(制御点が3つ)だが、3つ、4つと増やす必要がある(しかしあんまり増やすと計算量が増える)。

制御点がいくつでも大丈夫なようにコードを書き換えなくちゃいけない。

3. 位置関係による分類

これはまだ手をつけてません。

上の方にあって、専有面積が大きいものが店名、その下が電話番号とかをやる。

2年間のまとめ(成績発表)

2年次通年or集中
A+ (創成2年) 情報メディア特別演習 ← おふとんリーディング
A+ (全学群1年) アラビア語基礎BI ← やさしい先生(ネイティブ)
C (全学群1年) ドイツ語基礎AI ← 再履修用にもぐった
C (全学群1年) ドイツ語基礎BI ← 再履修用にもぐった
D (創成1-4年) 情報メディア創成特別講義A

2年次秋学期

A+ (全学群1年) ロシア語基礎AII ← 大好きな先生(日本人)
A+ (全学群1年) ロシア語基礎BII
A+ (創成3,4年) システム運用・管理
A (創成2年) ネットワークメディア概論
A (社工2年) 基本製図 ← 突然建築がやりたくなって
A (情報2年) ソフトウェア技法
B (創成2年) CG基礎
B (看護1年) 精神看護学概論
C (化学1年) 基礎有機化学
D (創成2年) Webプログラミング
D (創成2年) コンテンツ流通基盤概論
D (生物1年) 植物生理学概論
D (物理1年) 力学2
D (応理1年) 熱力学
D (工シス1年) 電磁気学I ← 神授業
無 (情報3,4年) コンピュータネットワーク
無 (工シス2年) 機械設計
無 (数学1年) 微積分II
無 (生物1年) 動物生理学概論
無 (化学1年) 基礎無機化学
無 (社工1年) 都市計画の歴史

2年次春学期

A+ (全学群1年) ロシア語基礎AI
A+ (全学群1年) ロシア語基礎BI
A (創成1年(再履修)) 解析II ← 唯一の再履修(しなきゃよかった)
A (創成2年) データ構造とアルゴリズム
B (人文2-4年) インド古典語初級A ← 予習量が多すぎた
B (化学1年) 化学結合論
B (情報2年) 論理システム
B (創成2年) 確率と統計
C (全学群1年) アラビア語基礎AI ← 先生の性格が合わない
C (生物1年) 生化学概論
C (創成2年) データ構造とアルゴリズム実習
D (創成2年) データ工学概論
D (創成2年) 認知科学
D (共通2年) 応用体育フィットネストレーニング
無 (物理1年) 力学1
無 (数学1年) 微積分I
無 (数学1年) 線形代数I

1年次通年or集中
A (全学群) 障害学生支援技術
A (共通1年) 基礎体育
B (共通1年) 英語基礎
C (共通1年) 異文化と英語
D (共通1年) 総合英語
D (心理3年) 発達心理学特講

1年次3学期
A (総合II) デザインと社会3
A (総合II) 歯科医学と医学の接点、口腔外科とは
A (創成1年) プログラミングII
A (創成1年) コンテンツ応用論
B (情報1年) 論理回路
C (創成1年) 線形代数II
C (創成1年) 情報数学I
C (生物1年) 細胞学概論
D (創成1年) プログラミング実習II
D (情報2年) 機械語序論

1年次2学期
A (創成1年) 教養と科学
A (創成1年) プログラミングI
B (創成1年) プログラミング実習I
B (創成1年) コンピュータシステムとOS
C (総合II) 形成外科学入門
C (創成1年) 線形代数I
D (創成1年) 解析II

1年次1学期
P (総合I) フレッシュマン・セミナー
A (総合II) 現代物理学への招待I
B (総合II) 日常生活の中で見られる神経筋疾患
B (創成1年) 解析I
D (創成1年) コンピュータリテラシ
D (創成1年) コンピュータリテラシ実習
D (創成1年) 情報メディア概論
D (総合I) 心と体に安全で快適なキャンパスI

筑波大学じゃない人向け解説
A+ 優よりすごい何か
A 優
B 良
C 可
D 不可
P 合格(成績評定がない授業)
F 不合格(成績評定がない授業)
学類 学科のこと
学群 学部のこと
春学期・秋学期 筑波大学は3学期制から2学期制(6学期制)になりました。

机を傾かせるアタッチメント作ったよ

こんにちは、首こりをなんとかする会(1人)DIY部(1人)です。

ついに机を傾かせるアタッチメントができました。
写真
1枚目: 30°モードDSC01924
2枚目: 30°モード(スケルトン)前からDSC01929
3枚目: 30°モード(スケルトン)後ろからDSC01928
4枚目: 60°モードDSC01925
5枚目: 60°モード(スケルトン)前からDSC01926
6枚目: 60°モード(スケルトン)後ろからDSC01927
7枚目: 落下防止用の柵を取り付けた図DSC01930
8枚目: Macを載せた図DSC01931

材料費
レッドパイン集成材(910×400×18) 1380円
ホワイトパイン集成材(600×45×24) 298円×3
ホワイトパイン集成材(600×90×15) 368円×4
ホワイトパイン集成材(600×55×15) 238円×2
カット代 150円
瞬間接着剤 298円
ミニアングル(補強金具)2個入り 278円
皿木ねじ(φ3.1×32)たくさん 100円
超低頭皿木ねじ(φ3.1×13)たくさん 128円
蝶番(幅38)2個入り 228円×3
合計5860円
DIYは高い!!!!!!

つくるの面倒だし、DIYは高いので、山善さんとかアイリスオーヤマさんとか、製品化してくれませんかね〜〜〜〜勝手に作っていいよ!!!!!アイデア料とか要らないから!!!!!じゃんじゃんつくろう!!!!!!

我ながらよくできたなーと思います。
失敗しなかったのは奇跡に近い。
あと手動ドライバーで余裕だったのが嬉しい。電動ドライバー持ってないです。
当初は、板が机よりも下まで伸びている姿を想像していましたが、
蝶番で繋いだ部分の強度が不安だし、これ全体が倒れるのを防ぐためにフックを作らないといけなくなるんだけど、そうすると「これは600mmの奥行きの机 にしか使えません!」ということになってしまう。だから、単純に机の上にポンっと乗せるようにしました。最近届いた引き出しのないシンプルな机だと、これ でも十分快適であることが分かったというのもあります。考えているうちにどんどん実装を簡単にしていくのはハッカソンみたいでよかったですね。

Javaのリスト速度対決

配列、ArrayList、LinkedListの速度対決をしてみました。
データ構造とアルゴリズムを習ってからずっと気になっていたんですが、
今必要に迫られて計測してみました。

条件

  • 要素数は7990272個です(中途半端)
  • for文を回す時間を計測します。初期化部分は含めません。
  • 要素はint(Integer)型です。
  • i: 0から7990271を動くindexです。
  • MAX: 7990272
  • 「10回だけ」とか指定がなければMAX回for文を回しています。

配列
普通の配列は速いですが、あとから追加・削除はできません。

  • 代入 14ms
  • 取得 14ms

ArrayList
ArrayListは以前からよく使っていました。
要素の取得は、普通の配列と遜色ない速さで嬉しいです。
要素の追加は、LinkedListより速いですね。
要素の削除は、先頭からやると、7990272回配列をコピーすることになるので、とんでもない時間がかかるようです。
末尾を削除するなら、LinkedListとほぼ同じ時間でできました。

  • add  226ms
    • ※要素を末尾に追加します
  • get(i) 19ms
    • ※指定したインデックスの要素を取得します
  • remove(0) 終わらないのであきらめた
    • ※指定したインデックスの要素を削除します
    • 一番遅いと思われる0番目を削除し続けました(1回ずつ配列を作り直すため)
  • remove(MAX – i – 1) 66ms
    • ※指定したインデックスの要素を削除します
    • 一番速いと思われる末尾の要素を削除し続けました
  • remove(3000000)を10回だけ 22ms
    • 真ん中へんの要素(3000000番目)を削除しました
    • めちゃくちゃ時間がかかりそうなので、10回だけやりました(この結果から7990272回やると恐ろしい時間がかかるのが分かります)

LinkedList
LinkedListは、普通に全ての要素を取得しようとするととんでもない時間がかかります。
先頭・末尾から削除しつつ取得すれば、かなり速く取得できます。
要素の追加は何故かArrayListより時間がかかるようです。

  • add  1070ms
    • ※要素を末尾に追加します
  • offer 1335ms
    • ※要素を末尾に追加します
  • push 1417ms
    • ※要素を先頭に追加します
  • pollFirst 55ms
    • ※先頭の要素を取得して削除します
  • pollLast 58ms
    • ※末尾の要素を取得して削除します
  • removeFirst 58ms
    • ※先頭の要素を取得して削除します
  • removeLast 69ms
    • ※末尾の要素を取得して削除します
  • get(i) 終わらないので諦めた
    • ※指定したインデックスの要素を取得します
  • remove(3000000)を10回だけ 87ms
    • 真ん中へんの要素(3000000番目)を削除しました
    • LinkedListの参照を3000000回たどる方が、ArrayListをコピーするよりも時間がかかることが分かります。

まとめ

  • もちろん普通の配列は速い。
  • でもArrayListを多用しても平気そう。特に要素の取得は普通の配列に迫る速さ。
  • 普通はわざわざLinkedListを使う必要はなさそう。要素の追加が遅いし、要素を削除せずに取得する方法は遅くて使えない。要素を削除する場合も、末尾から削除する場合はArrayListでも速い。中途半端な部分を削除する場合もArrayListを使った方がよさそう。
  • 先頭から削除する場合のみLinkedListを使う。

傾き・反り・影がある文書画像の行認識(その3)

お昼に引き続き進捗報告です。
3次スプライン曲線のフィッティングをしました。
前回の記事にも追記したのですが、曲線フィッティングによる歪み補正のアイデアは、この論文
http://human.ait.kyushu-u.ac.jp/~uchida/Papers/IS1-037.pdf
からもらっています(全く同じ実装ではありません。この論文はスキャナによる白黒2値画像を対象にしているからです)。
論文を読んで実装するのはつらいですね…審査員はその世界のトップだからソースコードがなくても再現できるだろうけど、初心者にとってはつらいです。ソースコードを添付する習慣はできないのでしょうか。

前回、40分割塗りつぶし画像のゴミをとりました。
そこからまず曲線をフィッティングさせる点をプロットします。
plot

フィッティングをします。
制御点を色々動かして、プロットした点との距離の和が最小になるものを求めます。
curve

これでフィッティングはできました。
変な方向に行ってるやつがいるのは、プロットした点に外れ値があるせいです。
次は、この外れ値を除去して、画像を変形するところまで行きましょう。

ここまでくるのに結構疲れました。
for文の階層を間違えたり、連立方程式の係数を間違えたりして、うまくいかなかったからです。
幻想的な曲線群が得られたときはどうしようかと思いました。
curve_0

傾き・反り・影がある文書画像の行認識(その2)

現在の進捗報告です。

前回「40列分割塗りつぶし」画像を得ました。
このあと何をやりたいかというと、

  1. 3次スプライン曲線をあてはめる(Curve Fitting)
  2. 3次スプライン曲線がまっすぐになるように画像全体を変形させる
  3. まっすぐになった画像から文字行を切り出す
  4. OCRにかける
  5. OCR結果に基づいて分類する

慣れてる人がやれば一瞬で終わりそうですが、まだ1にも到達していません。

1に到達するためには、以下を逆順に解決する必要があります。

  1. 3次スプライン曲線をあてはめる点の集合を求める
  2. 点の集合を求めるために、文字行を抜き出す
  3. 文字行を抜き出すために、ゴミを取り除く

まず、異様に縦長の部分を取り除きました(白黒反転してるのは気にしない)
異様に縦長のものを取り除く

次に、行っぽいものを抽出して、短い行は取り除きました。
行の抽出は、画像に対してラベリング処理(ピクセル単位)をすると遅いので、各矩形の情報を数値でもっておいて、矩形単位で処理をしました。
行を抽出

これで点の集合が求められるので、次は3次スプライン曲線をフィッティングします。
(点の集合から外れ値を取り除いた方が良さそうですが、後回しにしましょう。全体の完成が先。)

3次スプライン曲線を求めるための連立方程式を解く部分だけはつくりました。
線形代数Iで習ったガウスの消去法ですね。
制御点(3つの予定)を移動させながら各点との距離の和が最小になる組合せを求める予定。

追記

3次スプライン曲線をあてはめて変形させるというアイデアは、以下の論文から得ました。
「大局的最適化に基づく文書画像の湾曲歪み補正法」
http://human.ait.kyushu-u.ac.jp/~uchida/Papers/IS1-037.pdf

3次スプライン曲線による補完を理解するには、次のページがものすごく分かりやすかったです。
「3次スプライン補間を手作業で行う – ますぽんの雑記」
http://d.hatena.ne.jp/mscp/20091227/1261940720

連立方程式を解くための処理はこちらから。他にも数学的トピックがたくさん載っています。
「Java & C++ & Visual C++ Sample Program」
http://www.geocities.jp/java_sample_program/GaussNoSyoukyoHou.html

傾き・反り・影がある文書画像の行認識(その1)

こういう画像から行を抜き出したいです。

認識したい画像

スキャンした画像を想定しているおふとんリーディングと比べて、カメラで撮った画像なので、難しいところがたくさんあります。

  • 背景が真っ白じゃない。
  • 真っ白じゃないだけでなく影が入っている。
  • 文書の外側(机とか)まで入っている。
  • 紙が傾いている。
  • 傾いているだけじゃなく、反っている。

これを、次のようにします。思いつきです。

  1. エッジ抽出
  2. エッジ抽出した画像を2値化
  3. 2値化した画像に対して、「ある行に黒いピクセルがひとつでも入っていればその行を全て黒く塗りつぶす」処理を、画像全体を40列に分割して行う

1. エッジ抽出

エッジ抽出なら、背景が白くなくても、影が入っていても(影は明暗の変化が文字よりはゆるやかな気がするから)、文書の外側が入っていても(平坦な机とかなら問題なさそう)、文字だけが抽出できる気がした。Sobelフィルタを使った。もっといいのがあるらしいけど。

sobel

2. 2値化

大津の閾値判別法っていう判別法があるらしいので、閾値を自動判別させて2値化しました。今回の閾値は輝度が22より明るければ白くすることになりました。

22

3. 40列分割塗りつぶし

40列というのは経験則です。1〜100分割くらいして、見た目いい感じに塗りつぶせてるのが30〜40分割くらいでした。どの画像もレシート全体が写っているなら、分割数は固定でもいいのかなと思って。

stair_40

こうすると、同じ行の文字はだいたいくっつくから、曲がったり斜めになっていても行が抽出できるかなと思った。

でも、離れている文字はくっついていないし、近くにある文字も所々くっついてない。

だからこの結果を使って直接文字行を抽出しようとするより、この結果を使って、行の外形を求めて、それに曲線を当てはめて、画像全体の歪みを直した方がいいのかなと。ゆがみが直れば後は左上から順番に走査すればいいよね。