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

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

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

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

2012年センター試験結果まとめ

2012センター採点
倫政 80/100
国語 164/200(論42小38古42漢42)
英語 190/200
リス 42/50
化学 74/100
物理 86/100
数IA 91/100
数IIB 77/100

合計 804/950 (全て)
762/900 (リスニングなし)
757.6/900 (英リスニング200点圧縮)


昨年と比較(2011年センター試験)
政経 63/100
国語 125/200
英語 185/200
リス 48/50
化学 86/100
物理 79/100
数IA 73/100
数IIB 77/100

合計 736/950 (全て)
688/900 (リスニングなし)
689.4/900 (英リスニング200点圧縮)