低解像度折れ線グラフの実線と点鎖線の認識の試み

ウェブ・ページに埋め込まれた棒グラフや折れ線グラフからデータを読み取りたいときがたまにあります。 例えば、 東北沖大地震の年の夏、 東京電力管内で電気の使用制限が求められた当初、 東京電力がウェブ・ページに棒グラフを掲載して電力使用量をアナウンスし始めました。 そのとき、 棒グラフの画像から使用量の数値へ変換する処理を書いて公開された方が現れ、 電力使用量 API 登場のニュースになりました。 それからまもなく数値データ表を東京電力のウェブ・ページからダウンロードできるようになり、 様々な電力使用量表示アプリケーションが生まれたものでした。

あの夏の経験から、 ウェブ・ページの作成者は棒グラフや折れ線グラフに合わせて元になる数値データ表をウェブ・ページから提供することはもちろんですが、 過渡期や数値データの提供が期待できないとき棒グラフや折れ線グラフから数値データ表を求める自動処理をウェブ・ページの購読者が欲しくなることがあるとわかります。

ところで、 棒グラフは画像処理のモルフォロジック・フィルタを利用することで数値データ読み取りのための前処理を組み立てることができます。 一方、 折れ線グラフでは、 同一色の一点鎖線と破線を実線から区別したいときがあり棒グラフに比べて難易度が上がります。 折れ線ごとに色分けを最初からしてあれば簡単に数値化できるのですが、 そのようなグラフは相変わらず少数です。 点線の認識へ高解像度画像用に複数の手法が発見されているので、 ウェブ・ページ用の低解像度画像の点線認識に利用できないものかと、 試行錯誤していたのですが、 どうしてもうまくいかず諦めることにしました。 低解像度では点と線の重なりが増え、 繰り返しパターンが壊れがちです。 局所的に点線・一点鎖線・二点鎖線を区別するのが難しくなります。 それどころか、 線の向きの認識が困難になり、 傾きを利用する手法が使えなくなります。 点線認識に傾きを利用する適応性モルフォロジック・フィルタが使いにくいだけでなく、 線と点をベクトル化してから傾きと距離を頼りに点線を組み立て直す手法もうまく動かせないようです。 低解像度画像には別の切り口が必要なようです。

そこで、 妥協して、 線と点の長さと出現パターンを問わず 1 ないし 2 ピクセルの隙間を開けてつながる点鎖線をひっくるめて認識することにしてみました。 実線の折れ線の認識と点鎖線のそれは隙間を考慮するかどうかの違いしかなく、 同じ方式が利用できます。 これで、 実線・点鎖線・破線を区別することがかろうじてできるようになりました。 折れ線同士の重なりがあるので、 最初に実線の折れ線を認識しておき、 認識できなかった残りから点鎖線を認識します。 最後に破線の重なっていない部分が残ります。

認識を試すために使った画像は、 google 画像検索結果から認識が難しそうと感じた白黒のものを拾い、 画像サイズと解像度を変更せず、 目盛や凡例を塗りつぶしたものを使いました。 認識した実線の折れ線を赤色で、 点鎖線を緑色で上書きしたのが上の画像です。 残念ながら、 破線のピークの重なり位置 2 ヶ所に誤認識が生じています。

低解像度の実線の折れ線は、 Y 軸に平行な縦方向に伸びる幅 1 ピクセルの線分が連なっているものとして認識を左から右へとおこないます。 線分の一方に頭があるものとみなします。 例えるなら、 マッチ棒を縦向きに置いて、 横に並べていったようなものを考えます。 実線の折れ線グラフはペンを使って一筆書きして描きます。 それを考慮するために、 頭が上のときはペンを上へ動かしていることを表し、 下のときはペンを下へ動かしているものとします。 折れ線が重なっているときは、 途中に分岐が生じます。 そのため、 折れ線は右方向への伸び優先で探索していき、 分岐した先の長さを分岐ごとに求め、 最長のものを選ぶことにします。 伸び優先で分岐をそれぞれ辿るため、 試行錯誤が発生します。 そこで、 分岐した箇所からの伸びの長さをメモ化して動的計画法で計算量を抑えることにします。 最長が複数あるときは、 頭に近い方を選ぶことにします。

#include <cstdlib>
#include <iostream>
#include <vector>
#include <array>
#include <opencv2/opencv.hpp>

// 頭付き縦棒 (上の比喩のマッチ棒) を表します。
struct vline_value_type {
    int x, y, rows;     // (x,y) から (x,y+rows-1) までの線分を表します。
    int seg;            // 折れ線認識後の折れ線の種類を表します。
    int head;           // 負なら頭は上側、 正なら頭は下側、 ゼロは頭なしです。
    int len;            // メモ化のための長さの一時記録に使います。
};
// 縦棒をベクタに並べ、 ベクタの添字をマッチ棒の識別子にします。
typedef std::vector<vline_value_type> vline_type;
// x 座標の縦棒の探索のため、 x 座標の先頭の縦棒の位置の索引を作っておきます。
typedef std::vector<int> vcol_type;

// 分岐の開始マッチ棒の識別子と、 そこからの伸びの長さを表します。
// 実線折れ線では一本、 点鎖線では縦の連なりの数本で分岐します。
struct score_value_type {
    int first, second;  // 分岐位置です。 first から second までのマッチ棒の添字。
    int len;            // 伸びの長さです。
};
typedef std::array<score_value_type,6> score_type;

// 伸びのベクタ要素です。
struct path_value_type {
    int offset;         // 
    int head;
};
typedef std::vector<path_value_type> path_type;

void separate_vlines (cv::Mat& img, vcol_type& vcol, vline_type& vlines);
void detect_plot (vcol_type const& vcol, vline_type& vlines, int const gap, int const seg);

void digitize (int first, vcol_type const& vcol, vline_type& vlines, int const gap,
    path_type& path);
void path_append (int const first, int const second, int const head, path_type& path);
int combine_vgap (int& j, vline_type const& vlines, int const gap);
bool fill_score (int const x, int const itop, int const ibot,
    vcol_type const& vcol, vline_type const& vlines, int const gap,
    score_type& score);
void fill_score_len (vcol_type const& vcol, vline_type& vlines, int const gap,
    score_type& score);
void swap_score (score_type& score);
int index_score (score_type const& score);

プログラムのコマンドライン引数に指定した画像を読み取り二値化したら、 縦棒に分解し、 実線の折れ線、 点鎖線の折れ線を認識します。 認識の終わった縦棒を色分けして表示をします。 ここでは、 点鎖線の隙間を 3 ピクセルよりも少ないものとしてハードコードしています。

int
main (int argc, char* argv[])
{
    enum {
        SOLID_GAP = 0, SOLID_SEG = 1,
        DOTTED_GAP = 3, DOTTED_SEG = 2
    };

    if (argc != 2) {
        std::cerr << "usage: " << argv[0] << " IMAGE" << std::endl;
        return EXIT_FAILURE;
    }
    cv::Mat img_original = cv::imread (argv[1], cv::IMREAD_UNCHANGED);
    if (! img_original.data) {
        std::cerr << "error:imread:main:" << argv[1] << std::endl;
        return EXIT_FAILURE;
    }
    cv::Mat img_bin;
    cv::Mat img_gray;
    cv::cvtColor (img_original, img_gray, CV_BGR2GRAY);
    cv::threshold (img_gray, img_bin, 0, 255, cv::THRESH_BINARY|cv::THRESH_OTSU);
    img_bin = ~img_bin;

    vcol_type vcol;
    vline_type vlines;
    separate_vlines (img_bin, vcol, vlines);
    detect_plot (vcol, vlines, SOLID_GAP, SOLID_SEG);
    detect_plot (vcol, vlines, DOTTED_GAP, DOTTED_SEG);

    // 実線を赤色、 点鎖線を緑色に色分けして二値化画像に重ね書きします。
    cv::Mat img_output;
    cv::cvtColor (img_bin, img_output, CV_GRAY2BGR);
    for (int i = 0; i < vlines.size (); ++i) {
        if (vlines[i].seg == 0)
            continue;
        cv::Scalar line_color (0, 0, 255);
        if (vlines[i].seg == DOTTED_SEG) {
            line_color = {0, 255, 0};
        }
        cv::line (img_output, cv::Point (vlines[i].x, vlines[i].y),
            cv::Point (vlines[i].x, vlines[i].y + vlines[i].rows - 1),
            line_color);
    }
    cv::imshow ("IMAGE", img_output);
    cv::waitKey ();

    return EXIT_SUCCESS;
}

縦棒への分解は、 二値化画像を左から右へそれぞれの列ごと調べていき、 列ごとに上から下へと見ていき、 一繋がりの前面色のピクセルをまとめていきます。 一連のピクセルをまとめるやりかたは、 文字列の行から単語を認識するのと同じ方法で記述します。

void
separate_vlines (cv::Mat& img, vcol_type& vcol, vline_type& vlines)
{
    enum { LINEOUT, LINEIN };
    typedef unsigned char U8_T;
    for (int x = 0; x < img.cols; ++x) {
        vcol.push_back (vlines.size ());
        int top;
        for (int y = 0, state = LINEOUT; y <= img.rows; ++y) {
            U8_T const intensity = y >= img.rows ? 0 : img.at<U8_T> (y, x);
            if (intensity != 0) {
                if (state == LINEOUT) {
                    top = y;
                    state = LINEIN;
                }
            }
            else {
                if (state == LINEIN) {
                    vlines.push_back (vline_value_type {x, top, y - top, 0, 0, 0});
                    state = LINEOUT;
                }
            }
        }
    }
}

折れ線を一本認識します。 縦棒を左上から下向きに見ていき折れ線の伸びを digitize 関数で求めます。 長い折れ線の伸び path へ求まったら、 縦棒の seg メンバと head メンバに書き込みます。 digitize では縦棒の len メンバを破壊書き込みするので、 終わりに全縦棒の len メンバをゼロに戻します。

void
detect_plot (vcol_type const& vcol, vline_type& vlines, int const gap, int const seg)
{
    enum { THRESHOLD = 16 };
    path_type path;
    bool got = false;
    for (int x = vlines[0].x; ! got && x < vcol.size () - 1; ++x) {
        for (int i = vcol.at (x); i < vlines.size () && x == vlines.at (i).x; ++i) {
            path.clear ();
            digitize (i, vcol, vlines, gap, path);
            if (path.size () > THRESHOLD) {
                for (path_value_type const& item : path) {
                    vlines[item.offset].seg = seg;
                    vlines[item.offset].head = item.head;
                }
                got = true;
                break;
            }
        }
    }
    for (int i = 0; i < vlines.size (); ++i)
        vlines[i].len = 0;
}

添字が i の縦棒から、 折れ線を右へと伸ばせるだけ伸ばします。 現在の折れ線上の縦棒は添字が itop から ibot まで、 現在の縦棒の頭が上か下かは head 変数で追跡します。 head がゼロのときは頭が決まっていないことを示します。 分岐は 2 段階で求めます。 fill_score は右に隣接する縦棒を調べ、 分岐の起点を score 配列に求めます。 現在の縦棒の頭の上下から score を再配列し、 今度は分岐ごとに fill_score_len で右へ伸ばせる長さを求めます。 最も長く伸ばせる分岐を選んで、 折れ線のパスに追加して、 次の分岐を求めます。

void
digitize (int first, vcol_type const& vcol, vline_type& vlines, int const gap,
    path_type& path)
{
    int const limit = gap ? gap : 2;
    score_type score;
    int second = first;
    int itop = vlines.at (first).y;
    int ibot = combine_vgap (second, vlines, gap);
    int head = 0;
    while (first < vlines.size ()) {
        bool got = false;
        for (int dx = 1; ! got && dx < limit; ++dx) {
            int const x = vlines.at (first).x + dx;
            got = fill_score (x, itop, ibot, vcol, vlines, gap, score);
        }
        if (! got)
            break;
        if (+1 == head)
            swap_score (score);
        fill_score_len (vcol, vlines, gap, score);
        int weight = index_score (score);
        if (weight == score.size ())
            break;
        if (0 == head)
            head = -1;
        path_append (first, second, head, path);
        first = score[weight].first;
        second = score[weight].second;
        if (2 == weight || 3 == weight || 5 == weight)
            head = -head;
        itop = vlines.at (first).y;
        ibot = vlines.at (second).y + vlines.at (second).rows;
    }
    if (path.empty () || path.back ().offset != first) {
        path_append (first, second, head, path);
    }
}

折れ線の経路を記録します。 点鎖線のときは、 上下に複数の縦棒が並ぶときがあります。 そのとき、 頭の位置は端の縦棒だけに記録するようにしています。

void
path_append (int const first, int const second, int const head, path_type& path)
{
    if (head <= 0) {
        path.push_back (path_value_type {first, head});
        for (int k = first + 1; k <= second; ++k) {
            path.push_back (path_value_type {k, 0});
        }
    }
    else {
        for (int k = first; k <= second - 1; ++k) {
            path.push_back (path_value_type {k, 0});
        }
        path.push_back (path_value_type {second, head});
    }
}

点鎖線の隙間を挟んで上下に繋がる一連の縦棒を求めます。 縦棒を並べたベクタの添字 j から始めて、 同じ列で下へと隙間の許容量で飛び越えながら縦棒から縦棒へと移っていきます。 途中、 既に実線の印がついた縦棒があると、 飛び越えをストップします。

int
combine_vgap (int& j, vline_type const& vlines, int const gap)
{
    int const limit = gap ? gap - 1 : 0;
    int const x = vlines.at (j).x;
    int jbot = vlines.at (j).y + vlines.at (j).rows;
    if (limit) {
        for (int k = j + 1; k < vlines.size () && x == vlines.at (k).x; ++k) {
            int dist = vlines.at (k).y - vlines.at (k - 1).y - vlines.at (k - 1).rows;
            if (vlines.at (k).seg || dist > limit)
                break;
            j = k;
            jbot = vlines.at (k).y + vlines.at (k).rows;
        }
    }
    return jbot;
}

縦棒を並べたベクタの添字 itop から ibot の間の縦棒の右に隣接するカラム位置 x の jtop から jbot までの縦棒を求めて、 位置関係から score 配列へ割り振ります。 スコア 0 は、 縦棒の頭の右に隣接する場合、 1 は途中の分岐で最も頭側に隣接する場合、 2 は途中の分岐で最も尾側に隣接する場合、 3 は尾に隣接する場合とします。 スコア配列の先頭側の方が頭に近く隣接していることになります。 頭だけでなく尾側を考慮しなければならないのは、 ペンが折り返す縦棒があるためです。 スコア 4 と 5 は、 例えば頭が上側のとき、 頭の斜め上、尾の斜め下に接する場合で、 隣接の方を優先するため、 別扱いしています。

bool
fill_score (int const x, int const itop, int const ibot,
    vcol_type const& vcol, vline_type const& vlines, int const gap, score_type& score)
{
    bool filled = false;
    score.fill (score_value_type {0, 0, 0});
    for (int j = vcol.at (x); j < vlines.size () && x == vlines.at (j).x; ++j) {
        int const first = j;
        if (vlines.at (first).seg)
            continue;
        int const jtop = vlines.at (first).y;
        int const jbot = combine_vgap (j, vlines, gap);
        if (jbot < itop - gap)
            continue;
        if (ibot + gap < jtop)
            break;

        bool touch = true;
        if (jtop <= itop && itop < jbot)
            score[0] = score_value_type {first, j};
        else if (! score[1].first && itop - gap < jtop && jbot < ibot + gap)
            score[1] = score_value_type {first, j};
        else if (itop - gap < jtop && jbot < ibot + gap)
            score[2] = score_value_type {first, j};
        else if (jtop <= ibot - 1 && ibot - 1 < jbot)
            score[3] = score_value_type {first, j};
        else if (itop - gap <= jbot && jbot <= itop)
            score[4] = score_value_type {first, j};
        else if (ibot <= jtop && jtop <= ibot + gap)
            score[5] = score_value_type {first, j};
        else
            touch = false;

        if (touch)
            filled = true;
    }
    return filled;
}

動的計画法で、 分岐ごとに右へ折れ線を伸ばせる長さを求めます。 既に長さが記録してあるときは、 それを返します。

void
fill_score_len (vcol_type const& vcol, vline_type& vlines, int const gap,
    score_type& score)
{
    for (int w = 0; w < score.size (); ++w) {
        if (score[w].first) {
            if (! vlines[score[w].first].len) {
                path_type tail;
                digitize (score[w].first, vcol, vlines, gap, tail);
                vlines[score[w].first].len = tail.size ();
            }
            score[w].len = vlines[score[w].first].len;
        }
    }
}

頭が下側のとき、 スコア配列の上下関係はひっくり返します。

void
swap_score (score_type& score)
{
    std::swap (score[0], score[3]);
    std::swap (score[1], score[2]);
    std::swap (score[4], score[5]);
}

スコア配列から適切と思われる分岐を一つ選びます。 右へ最も長く伸ばせる分岐であること、 同じ長さに伸ばせるときは頭に近い方であること、 が判定基準です。

int
index_score (score_type const& score)
{
    int max_len = 0;
    int max_len_at = score.size ();
    for (int k = 0; k < score.size (); ++k) {
        if (score[k].first != 0) {
            if (max_len < score[k].len) {
                max_len = score[k].len;
                max_len_at = k;
            }
        }
    }
    return max_len_at;
}