へっぽこ知識で作る画像処理プログラム 「自炊本のページ抜けチェック」 2日目

はじめに

1日目では何を作るか、どういった方針で作るか、ということをまとめて書いたので早速作り始めていこうかと思います。

さっそく考える

まずは余白を検出しよう、と考えた

作りたいのは電子書籍チェックプログラム、チェックするうえで必要なのはページ番号です。
ページ番号は1日目で紹介した 本の各部名称 によるとノンブルと呼ぶらしいです。フランス語らしいのでここではページ番号と呼びます。

電子書籍チェックプログラムではページ番号を切り出し、それをページごとに並べることでページ抜けをチェックしやすくすることを目標としています。なのでページ番号を切り抜く必要があります。

そのページ番号は本を構成するものの中で最も外側にあります。もっとも外側ということは余白に隣接しているということになります。
ですから余白を検出できればページ番号を切り出すのも簡単なのでは？と考えました。

ですが、ページ番号の場所を正確に特定するには余白だけではダメだということに気が付きました。
ページ番号と本文とのスペースと余白に接していない側のページ番号の端を検出しないといけません。

結果からいうとこの方法だと無駄に難しくしてしまうのでダメだな、と思いました。
直感でしかないのですが、小手先の技術だけでやろうとしていたので知恵を絞らないと後々辛くなりそうだな、と思ったのです。

余白じゃなくて文字のない領域を検出してしまえばいいんだ

私が作ろうとしている電子書籍チェックプログラムはページ番号さえ切り出せれば簡単なのではと思っていたのですが、 ページ番号を切り出すことだけを考えていたせいで余計に難しく考えてしまっていました。

どうすれば簡単になるかというと、大きく考え、ページに存在する文字のない領域を検出するのです。

文字のない領域はどこに文字がいっぱいあって、どこにないのかがわかればよいわけですが、そんな都合のよい方法がありました。
画像処理の基礎の一つである積分画像を使います。

積分画像は顔検出で使われるHaar-like特徴の抽出で使われていたと思います。

積分と書かれると難しく思われるかもしれませんが、デジタルの世界での積分はただの足し算です。
積分画像が何であるか図を使って説明するとたったこれだけ。

積分画像の何がうれしいのかというと、一度積分画像を作っておくと特定の領域の画素値の合計が 4つの値の足し引きだけで計算できるのです。

ただ今はこの計算を行わず、積分画像の値をそのまま使います。
さらに使うのは積分画像の右端1列と下端1行の値だけです。 この2箇所は文字のない領域を見つけるのにとても重要な場所で、この2か所を調べるだけで文字のない領域を調べることができるのです！

積分画像の右端1列には画素が属する行までの画素値の総和が入っており、同様に下端1行には画素が属する列までの画素値の総和が入っています。
ゆえにこの2つをそれぞれを調べると画像の縦方向と横方向それぞれの画素値の変化を知ることができます。

今回は文字のない領域を調べたいわけですが、文字のない領域ではその変化が0になるはずです。 ということは積分画像の右端1列と下端1行を調べ、変化のない領域を見つければ良さそうではありませんか！

さっそくプログラムを書いてみる

こまごまとした準備

小説をスキャンした画像を用意するのですが。。。

ということでプログラムを書いてみましょう。しかし、画像がないと画像処理できません。しかし処理対象が小説というものなのでそれをこういった場に掲載するというのはそれはそれで問題がありそうです。なので画像については各々探してもらうということで・・・

ここで処理結果を出すときは小説の画像を一部切り抜いたものを利用しようと思います。

環境設定

C++、OpenCVとCMakeを使います

1日目にも書きましたが、プログラミング言語にはC++、画像処理ライブラリにはOpenCV、ビルドツールにはCMake、ビルドにはVisual Studioを使います。
OpenCVは言わずと知れた画像処理ライブラリです。バージョンが3系になってから積極的な開発が行われており、強力なライブラリとして成長しています。
CMakeはOSやコンパイラなどの開発環境に依存しないビルドツールです。CMakeでビルドの設定を書くとWindowsであればVisual Studio向けのソリューションファイルを、UnixやLinuxであればMakefileを、Macであれば何かを生成してくれ、とても便利です。
これは特にVisual Studioを使っている人にお勧めのものです。Visual Studioでは設定の変更が基本GUIで、同じ設定のソリューションファイルを作ろうとするとGUIでポチポチしなければならず辛い思いをします。
しかしCMakeはテキストファイルですのでそのままコピーし、内容を少し書き換えるだけで同じ設定のものを作ることが可能です。ライブラリのリンクに必要な設定などもVisual StudioのGUIで設定するのに比べたらめちゃくちゃ楽です！なのでおススメ。

Pythonでも書くよ、と言いましたが1日分のC++での成果物をまるっとPythonに書き換えたものを一緒に載せようと思います。 C++と書き方が異なり、分かり難そうなところはコメントで解説を入れようかと思います。

OpenCV

OpenCVはこちらで配布されています。

OpenCV download | SourceForge.net

OSにあったopencv-3.1.0.exeやzipをダウンロードしてください。
これを展開して、build/bindディレクトリを環境変数PATHに、buildディレクトリを環境変数CMAKE_PREFIX_PATHに追加してください。
これでOpenCVの環境設定は終了です。

CMake

CMakeはこちらで配布されています。

Download | CMake

OSにあったものをダウンロードしインストールしてください。OSによってはパッケージマネージャーからインストール可能かもしれません。

ソースコードはGitで管理、Githubで共有

ソースコードの管理にはGitを利用します。また作成したGitリポジトリはGithubにアップします。URLはこちら。

github.com

私はGitを一人でしか使ったことがないのでコミットがかなり適当（雑）です。。。

画像処理開始

まずは二値化

白と黒でしか構成されていない本でもスキャナーから生成した画像は正確に白と黒ではありません。白っぽい色と黒っぽい色で構成されています。
カラー画像データは基本的に各ピクセルはRGBの3チャンネルで構成され、RGBそれぞれは0～255の値をとります。これは符号なし8bitのunsigned charに相当します。
またグレースケール画像のデータは白の1チャンネルで構成され、同じく0～255の値を取ります。0は黒、255は白になります。

正確に白と黒ではない、というのは白=255、黒=0という値をとらず、0～255の値をとる、ということです。
本来文字のないところでも白（255）にならず、また文字のある所でも黒（0）にならない、ゆえに文字のない領域が正確に求められません。

このままだと都合が悪いので、画像を白（255）と黒（0）の二つの値だけをとるように加工します。この処理は二値化と呼ばれます。名前のままですね。
二値化は画像処理では基礎中の基礎の処理。もちろんOpenCVにも用意されています。
Miscellaneous Image Transformations — OpenCV 2.4.13.0 documentation

double threshold(InputArray src, OutputArray dst, double thresh, double maxval, int type)

第1引数は処理対象の画像、第2引数は二値化の結果です。 第3引数が二値化の閾値、第4引数が割り当てる値、第5引数が二値化時の値の割り当て方の設定です。 今回は第5引数にTHRESH_BINARY_INVを利用し、閾値以下の画素が255、閾値より大きい画素が0になるようにします。見た目的には白黒を反転させたような画像になります。つまり、文字が白に、何もないところが黒になります。 cv::thresholdの第1引数に与えているimageはグレースケール画像で型はunsigned charの1チャンネル（CV_8UC1）です。

cv::Mat binary;
int binaryMax = 255;
int binaryThreshold = 128;
cv::threshold(image, binary, binaryThreshold, binaryMax, cv::THRESH_BINARY_INV);

なぜ白黒を反転させたのかというと、二値化の後に積分画像を生成し、文字のない部分を調べるときに文字のない領域で積分画像の画素値が変化しないようにするためです。文字のないところが黒（0）になっていれば積分画像では変化がないわけなので都合がいいのです。

積分画像を作る

積分画像の説明は先に説明したので省きます。積分画像も二値化と同様に画像処理の基礎技術なのでOpenCVに実装されています。
Miscellaneous Image Transformations — OpenCV 2.4.13.0 documentation

void integral(InputArray src, OutputArray sum, int sdepth=-1 )

第1引数は原画像、第2引数は処理結果です。第3引数は処理結果の型を指定します。

先ほどのプログラムを少し修正してから積分画像を生成します。二値化時の最大値（binaryMax）を1に変更します。 これは積分画像の生成時に白だったのか黒だったのかがわかればよいので255という値を必要としないからです。

cv::Mat binary;
int binaryMax = 1;//二値化時の最大値は1に。積分するときに白だったところか黒だったところかがわかればいい。
int binaryThreshold = 128;
cv::threshold(image, binary, binaryThreshold, binaryMax, cv::THRESH_BINARY_INV);

cv::Mat integral;
cv::integral(binary, integral);

お、なんとなくグラデーションになって良さげです。ただし、この画像はプログラムとしては間違っていないのですが、見た目が間違っています。どういうことかというと、ほとんどが白になっていますが、実際には白（255）より大きな値をとっているピクセルもあり、値としてはもっと違いがあるはずなのです。
ではなぜほとんど白になっているかというと一定より大きい値は白（255）として表示する、というOpenCVの仕様です。一定という値はcv::Matの型がunsigned charかintかによって異なります。また画像を保存するメソッドcv::imwriteか画像を表示するメソッドcv::imshowかでも異なるのでよくドキュメントを読みましょう。
Reading and Writing Images and Video — OpenCV 2.4.13.0 documentation
User Interface — OpenCV 2.4.13.0 documentation

このままでも問題は無いのですが、積分画像が実際にどんな値をとっているのか視覚的にわかるよう変換することで、積分画像の中身を確認しましょう。

変換にはcv::Matのメソッドを利用します。
Basic Structures — OpenCV 2.4.13.0 documentation

void Mat::convertTo(OutputArray m, int rtype, double alpha, double beta)

第1引数が処理結果、第2引数は処理結果の型、第3、4引数はそれぞれ値のスケールとシフトする量となります。 このメソッドは白（255）より大きな値を視覚的にわかるようにするために、値の大小関係を崩さずに0～255の値をとるようにするために使います。
またこのメソッドを使うには最大値が必要です。これもよく使うものなのでOpenCVに用意されています。
Operations on Arrays — OpenCV 2.4.13.0 documentation

void minMaxLoc(InputArray src, double* minVal, double* maxVal, Point* minLoc, Point* maxLoc, InputArray mask)

第1引数は原画像、第2引数は最小値を格納する変数のポインタ。第3引数は第2引数と同様に最大値を格納する変数のポインタ。第4、第5引数は最大最小値の値の場所を格納する変数のポインタ、第6引数は第1引数に与える原画像と同じサイズ（同じ行数、列数）の行列で0以外の値の座標に対応する原画像のピクセルを利用します。これはマスク画像と呼ばれます。
今回は最大値を知りたいので第3引数まで使います。最小値は0とわかっていますが、本当に0になっているのか確認するために使いましょう。

cv::Mat integralVisible;
double max;
double min;
cv::minMaxLoc(integral, &min, &max);//最大値だけほしいので第3引数まで。最小値は0のはずだが本当に0か確認するために使う
CV_Assert(min == 0.0);//本当に最小値が0になっているか確認

integral.convertTo(integralVisible, CV_8UC1, 255.0 / max); //betaは使わない。0-255の値をとるようにalphaを与える。

CV_AssertはOpenCVで定義されているマクロで、引数に与えた条件文が成立していない場合、プログラムが終了します。Assertは日本語で「断言する」なので、引数に与えた条件が成り立つとプログラムで断言しているわけです。

先ほどの積分画像よりも黒の部分が多くなりました。この画像だと先ほどは白かった部分にも実は変化があることがわかります。
画像処理はとにかくデータが多いので値を一つ一つ確認するには無理があります。なので、ちょっと面倒ではありますが、今回のように変換して視覚的にわかりやすくすることで確認しやすくすることはとても重要です。

処理内容から脱線するのですが、この画像の下の方の色が白→グレーを繰り返しているように見えると思いますが、実際には左から右まで黒（0）→白（255）に増加しながら変化しています。詳しくはマッハバンドで検索してみてください。

さて、もう少しこの画像を詳しく見てみましょう。色の変化が帯状に分かれていることがわかるかと思います。

縦線を引いてみました。位置はともかくとして文字の並びに沿って変化してる感じがしますね。この後の処理を工夫すれば文字のある領域とない領域がわかりそうです！
やった。なんとか目的のものは作れそう。

2日目まとめ

今回は文字のある領域（もしくはない領域）を判別する処理について考え、実際に画像処理をするところまで書きました。
画像処理はOpenCVの関数を使ったとても簡単なものですが、二値化と積分画像を使うことで文字のある領域（もしくはない領域）が見つけられそうだな、というところまで作成しました。

プログラムで主に役割を果たしているのは二値化と積分画像を行う2つの関数だけですが、組み合わせ次第で簡単に画像について調べることができました。 実際にプログラムを書いて動かすまで、考えていた処理で思っていた通りのものが得られるのかわからないのでこうやって”それっぽい”画像が得られたことは大きな一歩です。

成果物はこちら

GitHub - kyokushin/EBookChecker at c++_day_02

予告

次回は作成した積分画像から実際に文字のある領域と文字のない領域を判別してみます。
さて、毎週更新できるかな。。。