PSNRとSSIMの違い（総論）
さて、本日は、再びSSIMの話題です。お題は、
後だしジャンケンはやめましょう
です。
前にPSNRとSSIMというのを比較しました*1。簡単にまとめると、「PSNRより、SSIMの方が、私たちの感覚に近い結果を出してくれる」というものでした。一般論としては、合ってるような気がします。
ところが、SSIMというものは、実務上、困ったことを巻き起こします。
SSIMというのは、その計算式の都合上、無限のバリエーションがあるのです。
ちょっと、そのあたりを確認してみましょう。
PSNRというのは、計算式*2を見てみると、ユーザーが勝手に選択できるようなオプションがありません*3。つまり、（グレースケール同士の比較である限り）誰が、どこで、どのプログラムを使って計算しようと、PSNRの値は同じものが出てくるはずです。なので、「PSNRを35±0.5にしろ」と指示して、それを第三者が機械的にチェックして、外れているものは、ダメーというような検査（監査）は意味があります。
ところが、SSIMというのは事情が異なります。SSIMの計算式*4には、ユーザーが勝手に選択できるようなオプションがあります。
（マニアな領域）
例えば、http://www.ece.uwaterloo.ca/~z70wang/research/ssim/ssim_index.mにある、
C1 = (K(1)*L)^2;
C2 = (K(2)*L)^2;という部分で、K(1)、K(2)、Lなどがそうです。
ただ、計算式の中に入っているオプションは、大して大きな違いを産まない*5ので、ここでは無視してみましょう。
計算式のオプションが無視できたとしても、実際の計算を行う上で、いくつかの重要なオプションがあります。その代表は、ガウシアンフィルターとディスタンスです。
ガウシアンフィルターもディスタンスも、公式*6に発表されている計算式
には載っていません。ところが、実際の計算をする段階では、だいたい出現します。例えて言えば、各省庁は通達というものを出して、法律を実際に運用するための具体的なルールを提示しています*7。それと似たようなもので、SSIMの計算式上、どこにも載っていないのですが、実際の計算をする上で、例示されています。ガウシアンフィルターやディスタンスを使ったほうが、より良いSSIMの値が出てくる、と信じている研究者がいるからです。
さて、話が長くなっちゃうといけませんので、ガウシアンフィルターとディスタンスの詳細は、次回以降に回しましょう。今日のところは、SSIMの実際の計算において、ユーザーが勝手に選択できるようなオプションがある、ということだけ押えてください。
そして、ここからが重要なのですが、（PSNRと異なり）誰が、どこで、どのプログラムを使って計算したかによって、SSIMの値は全く別のものになる可能性があります。なので、「SSIMを90以上にしろ」と指示して、それを第三者が機械的にチェックして、外れているものは、ダメーというような検査（監査）では恣意性*8が残ります。
なので、SSIMの値を指定して発注するときは、「必ず、SSIMの計算式を具体的に提示して、この計算式で○○以上になるようにしろ」という風に指示するようにしましょうね。
*1:http://d.hatena.ne.jp/denshikA/20090921
*2:http://d.hatena.ne.jp/makorin72/20080710を見ると良いでしょう
*3:唯一、誤差が生じるとすると、log10という定数を小数点以下何桁まで使うのかってことくらいなもんです。
*4:http://www.ece.uwaterloo.ca/~z70wang/research/ssim/ssim_index.mを見ると良いでしょう
*5:でも、小さな違いは産むので、注意してくださいね
*6:何を持って公式かという基準はないのですが、私が勝手に、これは公式だな、と勝手に判断しているもの、についてです。
*7:http://123k.zei.ac/kihonn/hourei.html
*8:事前に具体的な計算式を提示せず、後になって、SSIM値が規定を外れています、と指摘するのは、「後だしジャンケン」のようなものですので
OWRから、再び、OCRへ
本日のお題：所信貫徹
前回、最近のOCRというのは、実はOWRであることを説明しました。ところが、今日は、最近のOCRというのは、実はOWRであるんだけど、さらに、もう一歩進んで、OCRに回帰しているんだよ、という点を見ていきましょう。
さて、ちょっと離れた場所からスタートしましょう。
「所信貫徹*1」というキーワードで、Googleに聞いてみましょう。
という感じで、「もしかして、あなた、初志貫徹のこと言いたいの？」と見透かしてきます。
Googleは、
「初志貫徹」という言葉は、「初心貫徹」や「所信貫徹」などと、よく混同される
ということをご存知です。賢いですね*2。
このような、よく混同（Confusion）される単語などを関係付けておくものとして、Confusion Matrix（コンフュージョン・マトリックス）という表（Matrix）があります。
Googleが持っているConfusion Matrixは、
などが関連付けられているのでしょう。
最近、Googleが日本語入力システムを発表しましたが、技術的には、同じ類ですね。その開発者のブログにこう書いてありました。
スペルミスの多くがインプットメソッドの誤変換に起因していることと、チームで開発した「もしかして」システムが高い精度でそれらを修正していく様を目の当たりにして、Google 日本語入力の可能性を確信しました。
さて、話をOCRへ戻しますと、すでに、みなさんもお察しのように、OCRで使うConfusion Matrixは、OCRの変換の時に発生するであろう混同（Confusion）を集めてきて、作られます。（みなさん、日本語での例がお知りになりたいようですので、リクエストにお応えして）例えば、「意見」と「煮見」*3、「点数」と「占一数」*4など。
そして、前回からの続きで言いますと、OWRは変換時に、辞書との照合により、「もしかしたら、この単語は、変換を間違えたかもしれないな」とお知らせをしてきます。それを受けて、次のシステムがConfusion Matrixと照合することで、「もしかして、○○ですか」というリストを作成することができるわけです。そして、次のシステムないし人間に最終判断を委ねるのです。
というわけで、最近のちゃんとしたOCRというのは、ちゃんと混同（Confusion）を認識（Recognition）しているわけでして、その意味で、OCR（Optical Confusion Recognition）なのです。ただし、OCRをこの意味で使っているのは、誰もいないので、ご注意あれ。
さて、ここで、確認問題です。*5
私は、
このページ（http://www8.cao.go.jp/youth/kenkyu/tekiou_g/pdf/0-1.html）は、OCRで一度読まれて、そのデータを元に作成されたHTMLである
と疑っています。なぜでしょ？（しばらく考えてから、http://denshika.cc/ocr.phpへどうぞ）
*1:この言葉は、言いたいことは分かるけど、おそらく、単なる言い間違いか、自分の信念（所信）を意地でも押し通して（貫徹）やるぞー、という意味の造語かな。
*2:たまに、ウルセーなー、と思うことがありますが
*3:http://www.google.co.jp/search?q=%22%8E%CF%8C%A9%82%F0%22
*4:これは日本語の縦書きをOCR変換するとき出現するもので、「点」の下の4つの点々を、漢数字の「一」と混同するわけです。こちらから確認してみよう。http://www.google.co.jp/search?q=%22%90%E8%88%EA%90%94%22
*5:って、なんで突然？
OCRからOWRへ
本日のお題：
wordFromDictionary="false"
さて、新年なので話題を変えて、OCRについて進めていきましょう。
OCRというのは、本名、Optical Character Recognitionですので、その名前が示すとおり、文字（Character）単位の認識（Recognition）をしていきます。ところが、こんなことを額面どおりに行っているソフトは、おもちゃOCRだけです。
ちゃんとしたOCRは、OCRという名前がついていても、実は、OWRとなっていて、Optical Word Recognitionという感じで、単語（Word）単位の認識（Recognition）をしていきます。
分かりやすくするために、例で見て行きましょう。
前（http://d.hatena.ne.jp/denshikA/20091010）にも書きましたが、OCRというのは、EとB、CとOを勘違いしやすいので、
は
と変換される
可能性があります。ところが、PIBOBSというのは、英単語としては存在していません（よね？？）。*1
なので、各文字が変換される時でも、変換された後でも良いのですが、英語辞書との照合をすることで、OWRソフトは、「この変換は、もしかしたら、ヘンテコ変換かもしれないな」と理解することができるわけです。
世界最強のOCR*2であるAbbyy社のOCRを例にしてみると、辞書に載っていないと思われる場合には、
wordFromDictionary="false"
というのが埋め込まれていて、逆に、辞書に載っていたぞという場合には、
wordFromDictionary="true"
というのが埋め込まれています。
実際に確認してみましょう。
http://www.archive.org/stream/treasureisland09stevgoog#page/n14/mode/1upに行ってみると、
という部分があります。この部分に含む本全体のOCRデータは、こちらで入手できます。*3
http://ia360602.us.archive.org/3/items/treasureisland09stevgoog/treasureisland09stevgoog_abbyy.gz
この部分は、「PIBOBS OP EIGHT」と変換されてしまっているのですが、「PIBOBS」と「EIGHT」に該当する部分は、それぞれ、この部分です。（一行が長ったらしいのですが、改行すると余計見にくくなるので、横に大きくはみ出るようにしています。）
(注)
１．の行が、フォントや文字間などについてお知らせしています。
２．の行が、それぞれ、1文字に関する情報（位置、大きさ、そのほかごちゃごちゃ）をお伝えしています*4。
PIBOBS部分
P
i
B
O
B
S
EIGHT部分
E
i
g
h
t
この例ですと、「PIBOBS」は英語辞書に載っていないので、「wordFromDictionary="false"」となっています。一方、「EIGHT」は英語辞書に載っていますので、「wordFromDictionary="true"」となっています。ご確認ください。
しかし、かなり重要なことですが、辞書に載っていないことと、誤変換は、イコールではありません。例として、こんなことがあります。
なので、OWRが、辞書に載っていないことだけを理由に、勝手に書き換えをしたりすると危険です。そこで、OWRは辞書に載っていないことを理解しても、何も処理せずに、単に、間違いかもしれないな、という記録を残して、次のシステムにバトンタッチするのです。
というわけで、本日のところは、OCRというのは、実はOWRであり、辞書との照合により、誤変換の可能性をお知らせする機能がついていることを見てみました。あとは、OCR結果を分析するときに、システムが、誤変換の可能性箇所として何らかの処理をするようにすれば、変換精度が上がるかもしれませんね、ということです。
*1:どこかの言葉で、存在しているかもしれませんが。
*2:あちこちで、Abbyy社のOCRをほめるクセがあるため、Abbyy社の回し者ではないのか、とよく言われますが、全然関係ありませんよ
*3:Internet Archiveというところは、全ての情報を公開していく、とても良い団体ですので、こういう例示をするときは、かなり役に立ちます。感謝
*4:OCRのデータを初めて見る方は、びっくりするかもしれませんが、画面上たった1文字のものでも、OCRデータに変換すると、1文字あたり250文字くらいになります。
*5:コンピュータの話題で、Peer to Peerの部分が、Beer to Beerになっていたら、とてもおもしろい、とは思うんですが
*6:実は、よくある
電子化検定2009
今年最後のエントリです。なので、突然ですが、「電検」こと電子化検定を行います。
あなたは何級？
以下の問題にすばやく答えよ。制限時間13分くらい。
（問題1）左上のような画像を2値化した場合、右上のように消えてしまう文字がある。なぜか？
（問題2）消えてしまわないようにするためには、どうすれば良いか？あっさり述べよ。
（問題3）このような2値化の問題とOCRの関係について、かなり簡潔に述べよ。
続きを見る前に、じっくり考えてみましょう。
（問題1の回答例）
まず、大前提を確認しましょう。
2値化というのは、「黒と白しか使わない」画像にすることです。例を挙げれば、FAXなどがそうです。カラーじゃない、ということで、グレースケールと混乱する場合がありますが、2値化された画像は、灰色もありません。とても、ファイルサイズが小さくなるのですが、文字や形が欠けちゃう、という欠点があります。
次に、以下の2点を押えましょう。
- カラー画像を2値化するためには、まず、カラー画像をグレースケールっぽく変換する必要があります。
- グレースケールは、「どんくらい白いか」という程度が256段階で設定されていますが、その何段階目以上を白として、何段階目以下を黒とするのか、を決めなくてはいけません。
まず、グレースケールにする段階で、http://d.hatena.ne.jp/denshikA/20091119でも述べたとおり、
元画像 みんな平等 優劣つけた RGBを平等に扱ってしまうと、消えてしまう文字があります。なので、問題の右上のように文字が消えてしまったのは、このグレースケールにする変換方法がマズかったのかもしれません。グレースケールにするとき、RGBには何らかの形で優劣をつけてあげましょう。
次に、ちゃんと文字を消さずにグレースケール変換できたとして、今度は、白黒の境界線をどこにするのか、を検討してみます。
カラーをうまくグレースケールに変換できると、
※青をグレースケール変換したものが限りなく黒っぽいですが、微妙に黒じゃないんです。このような感じで、左から、黒、青、赤、緑、白と並ぶはずです。そうすると、境界線の候補としては、A〜Fまでの6種類があります。
AとFを境界とした場合は自明なので省略いたします。
Bを境界とした場合、
Cを境界とした場合、
Dを境界とした場合、
Eを境界とした場合、
さて、ここまでくれば、後は簡単です。
例えば、仮にDを境界線としたとします。
この場合、
「緑地に白文字」は、両方とも白に変換されてしまうので、文字がつぶれます。
「赤地に緑文字」は、赤が黒に変換されて、緑が白に変換されますので、文字がつぶれません。
「青地に赤文字」は、両方とも黒に変換されてしまうので、文字がつぶれます。では、Cを境界線としてみると、
「緑地に白文字」は、両方とも白に変換されてしまうので、文字がつぶれます。
「青地に赤文字」は、青が黒に変換されて、赤が白に変換されますので、文字がつぶれません。
「黒地に青文字」は、両方とも黒に変換されてしまうので、文字がつぶれます。という感じで、どこに境界線をもってきたとしても、かならずつぶれてしまう組み合わせが出てきます。
つまり、カラー画像を、普通に2値化したら、どっかの文字や形がつぶれてしまう可能性は、かなり高い、ということです。背景が真っ白で、そこにいろんな色で文字が書かれているなら構わないのですが、背景がいろんな色で、そこの上に、いろんな色で文字が書かれている、という場合、非常に困ってしまうわけです。
ちなみに、問題の画像の右側ですが、これはDを境界線としているようです。
（問題2の回答例）
画像を分割して、部分ごとに2値化する。*2
（問題3の回答例）
OCRにかける場合、何らかの形で2値化らしきことをしなくてはいけないので、2値化によって消える文字があると、（OCRの誤認識だとかそんなこと以前の問題として、）全く認識できない、という問題が発生して、かなり困る。
全問正解者は1級。
2問正解者は2級。
1問正解者は3級。
正解なしは4級。
認定書を希望の方は、コメント欄に、何級だったぞー、とお書きください。後日、認定書をお送りします。
*1:昨今の不況を反映して、「赤地」とするべきところが、「赤字」となっておりますが、年末なので、許してください。
画像データの模式図（まとめ）
本日のお題画像：
過去2回、画像データの模式図に挑戦したのですが、話を分かりやすくするために、多少、画像をゆがめてありました。今回は、どんな感じでゆがめたのかをお話します。
まず、グレースケールで行きましょう。
前々回、下の左の画像は、右のような感じで、保存されてます、と言いました。
ところが、よく見てみたり、よく考えてみると、この右の画像はおかしいわけです。白っぽい部分は箱の上に位置して、黒っぽい部分は箱の下の方に位置するはずが、必ずしもそうなっていないわけです。とくに、箱の左下の隅にかけて、黒っぽい部分がありますが、そのすぐ横の白い部分が、りんごの灰色部分より下に来ているようにみえます。
なんで、こんなことになっているのか、というと、まずはイメージをつかんでいただくために、画像をゆがめたからです。どんな感じでゆがめたのか、というと、下の左画像を、空間に配置すると、実は右画像のようになります。
でも、これでは、あまりに見づらいので、滑らかな平面になるように、こんな感じでゆがめていったのです。
カラーについても同様で、本当なら、こうなるのですが、
見づらいので、滑らかにして、
こうなったのです。
箱の上面に張り付いた画像が空間に配置され、そのあと、滑らかになっていくムービーです。音楽がついていませんので、鼻歌でも歌いながら、眺めてください。
というわけで、数回にわたり、画像データの模式図に挑戦したのですが、イメージをつけやすいように、画像をゆがめていたわけで、ある程度のイメージがついたら、本当は、こんな感じで保存されているんだ、と頭の中を修正しておいてください。
ちなみに、今回行ったような凸凹を滑らかにするような画像処理は、かなり頻繁に行われています。SSIMを計算するときにも、使うことがあります。
画像データの模式図（カラー編）
本日のお題画像：
前回、グレースケール画像について、模式図に挑戦してみました。
念のため、もう一度言っておきますと、模式図というのは、
おおよその理解を得るために、正確とは言えないかもしれないけど、とりあえず図示してみました
というような意味だと思います。そして、「画像データというのが、パソコンの中にどんな感じで保存されているのか」というのは、パソコンの中をのぞいても決して見ることができないので、模式図を使って、こんな感じで保存されているじゃないでしょうか、探っているわけです。ただし、あくまで模式図ですので、あまり深刻に考えこまないでください。
というわけで、本日は、カラー画像についてです。
前に（http://d.hatena.ne.jp/denshikA/20091130）、
カラー画像というのは、RGBにも分解できるんだけど、それだけじゃなくて、他にもいろいろと分解する方法があるんだよ
というお話をしました。とはいうものも、やはり、何かとRGBなわけです。
さっそくですが、RGBに分解してみます。
続いて、早速、箱にしてみます。
RGBのRにおいて、「どんくらい赤いのか」という度合いが256段階でつけられています。同様に、GもBも、256段階評価がされています。なので、グレースケールの時と同じように、その度合いを箱の中の高さ方向の位置だとして、配置してみましょう*1。黒っぽいほど、箱の下のほうに配置され、赤っぽかったり、緑っぽかったり、青っぽかったり、すればするほど、上の方に位置する、という感じです。
さて、この3つの箱は、カラー画像の大きな箱の中にどのように配置されているのでしょうか？おそらく、こんな感じで、縦に積み上げられているようです。
なので、こういうことでしょう。
まとめましょう。
というカラーの画像データは、
の中に
*2 こんな感じで積まれた
*3 の中で、
こんな感じで保存されている
ようなんです。
（おまけ）
ちなみに、元のカラー画像のまま、Yという尺度で高さ方向に配置していくと、こんな感じになりますムービーを作りました。陽気な音楽が流れますので、職場でご覧になる場合は、音量などに気をつけてください。
*1:今回も、話の筋がひん曲がらない程度に、画像をゆがめてありますので、ご注意ください
画像データの模式図（グレースケール編）
本日のお題画像：
模式図というのは、
おおよその理解を得るために、正確とは言えないかもしれないけど、とりあえず図示してみました
というような意味だと思います。
本日は、画像データの模式図に挑戦します。「画像データというのが、パソコンの中にどんな感じで保存されているのか」というのは、パソコンの中をのぞいても決して見ることができないでしょう。でも、模式図を使って、こんな感じで保存されているような気がします、というくらいなら、できそうな気もします。ただし、あくまで模式図ですので、あまり深刻に考えこまないでください。
前回（http://d.hatena.ne.jp/denshikA/20091204）、画像データは、「平らなもの」ではなくて、「ちょっとした箱のようなもの」ではないでしょうか、とお話しました。
つまり、こういうことです。
前回はここまでだったのですが、画像が箱の上面に貼り付いているだけ、というのは、なんとなく手抜きの気がします。なので、もう少し工夫してみましょう。
グレースケール画像というのは、黒から白までを256段階に分割して、どんくらい白いのか、という数字に置き換えています。つまり、
0なら黒
（100なら、濃いグレー）
128ならグレー
（200なら、薄いグレー）
255なら白
という感じです。左から順番に並べると、こんな感じです。
0 128 255
この「どんくらい白いのか」という数字を、先ほどの「画像の箱」における高さ方向の位置だと考えてみると、
こんな感じになるのが、お分かりいただけると思います。
つまり、
という画像データは、
のように保存されている
ようなんです。
理解を深めるために、次も眺めてみてください*3。左の画像は、右のような感じで保存されているのが、お分かりになるでしょう。
では、次にこの画像なら、どうなるでしょう？
正解*4はこちら。⇒ http://denshika.cc/moshikizu.php
ここで、整理しておきますと、
画像データは、箱の中で、白っぽい部分は上の方に、黒っぽい部分は下の方に保存されている
わけです。このことを念頭に、
この画像を空間に配置してみると、冒頭のような
というようなものになります*5。
分かりづらいかもしれないので、動画も用意してみました。「画像データの箱」を回転させてみたのですが、余計分からなくなってしまったら、ごめんなさい。
というわけで、今回は、画像データがパソコンの中でどのように保存されているのか、という模式図に挑戦してみました。画像データというものをこの模式図で理解していると、PSNRやSSIMのことがもう少しわかってくるのではないか、と思います。ただ、今回は、ここまででやめて、次回は、カラー画像の模式図を見て、そのあと、これらの模式図を使って、PSNRやSSIMを見ていく、という流れになるかもしれません。
*1:http://japan.internet.com/webtech/20090914/14.htmlより借用
*2:http://japan.internet.com/webtech/20090914/14.htmlより借用
*3:大人の事情により、若干ゆがめてありますが、話の筋としては間違っていないでしょう
*4:「正解」と呼んで良いのか知りませんが
*5:こちらも、話の筋としてはおかしくならない程度に、多少ゆがめてありますので、ご了承くださいませ
