わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

系図における線分交差判定の試み

大阪市立大学にて開催の,じんもんこん2017にて,「系図からのデータ自動取得の試み」と題して,研究室の学生が口頭発表をしました.
どんな研究だったのかを説明するにあたり,前提が2つあります.一つは対象とする系図のことで,清盛尊氏秀吉などの人物の親子関係が記された『将軍家譜』や,僧侶の師弟関係などが書かれた「血脈(けちみゃく)」について,まとめて「系図」と呼び,本研究の対象とします.婚姻関係は記載されておらず,人間関係は,グラフ理論で言うforest(tree*1の集まり)として表現できます.
もう一つの前提は,使用する情報です.系図画像に出現する字句について,事前に専用のOCRソフトウェアを用いて,何と書かれた文字列が,画像上のどの領域に出現しているかを,学外の,今回の論文の第3著者の方に,取り出していただきました.XML文書になっていることもあり,これを「位置情報付きテキスト」と呼ぶことにします.
系図画像と,位置情報付きテキストを用意した上で,テキスト処理と画像処理をするプログラムを書きました.文字列が人物名かそうでない(人物の付随情報である)かの判別や,親子関係・兄弟関係の導出を,機械的に,極めて高い成功率で,行えることを確認し,3種類の系図に適用した結果などを報告しました.
発表時間は発表25分+質疑5分で,しっかり準備をしていたのですが,発表した学生は,会場に圧倒されたようにも見えました.質問は1人だけで,セッションが終わってからの意見交換により,互いに,対象とする系図の認識が違っていたのを知りました.
質問をいただいた方も,系図を対象とした成果を,ポスターで発表されていました.そこには婚姻関係がふんだんに入っており,違う種類の系図,そして違うゴールで,我々の何歩も先を進む研究を進めていました.
ただ,既存の系図を,木構造で表示し直すのは,素朴な発想ながら非実用的であるという認識は共通しており,それを打破するために,それぞれで独自の要素を加えようとしていることを,知ることにもなりました.
ところで,論文集に掲載され,情報処理学会・情報学広場よりダウンロードできる*2,「系図からのデータ自動取得の試み」の論文について,図6が黒塗りになっています.これは最終版投稿時のミスで,著者側の責任です.そこに載せたかった図は,以下のものです.

ただこれも,分かりやすいとは言えません.何をしたかったかについて,破線を除いた状況から,話を始めます.

縦線と横線の「交差」の判定を試みます.いや,上のような状況であれば,これは交差していません.座標を文字で表すと,縦線の座標は,上端を(x1,y11),下端を(x1,y12)とします.事前の線分検出により,系図画像に出現する縦線と横線の座標を取得していまして,縦線の上端と下端のX座標は一致し,この例ではx1と書いています.上下端のY座標の値はもちろん異なっており,y11<y12です.画像処理ですので,下向きがY座標の大きくなる方向である点にも注意してください.
同様に横線の座標は,左端を(x21,y2),右端を(x22,y2)と表します.2つの点のY座標は同一で,X座標についてはx21<x22です.
視覚的には,この縦線と横線はつながっていませんが,もし縦線・横線の長さがそれぞれ数百ピクセルあって,かつ,縦線の下端と横線の左端の距離が3ピクセルくらいなら,これはつながっていると見なすべきでしょう.線分検出の際のカスレや,数ピクセルの幅を持った線を1つの座標(x1やy2)にした際のズレなどのため,取得した座標のままでは,ぎりぎり,つながっていない場合が該当します.
それと縦線と横線の「つながり」には,この図(がつながっているものとして)のような「L字型」のほか,枝分かれする「T字型」,そして「十字型」も,考えられます.いずれの場合でも,つながっているのなら「交差している」と判定したかった*3ので,判定対象の線分の両端を,定数τだけ伸ばすことにしました*4
拡張した縦線の座標については,上端を(x1,y'11),下端を(x1,y'12)と表します.ここでy'11=y11−τ,y'12=y12+τです.拡張した横線の座標について,左端は(x'21,y2),右端は(x'22,y2)です.同様に,x'21=x21−τ,x'22=x22+τとなります.
そうして得られるのが,この記事で先に貼り付けた画像の状況となります.「交差」の必要十分条件を,日本語で書くと,「縦線のX座標が,拡張した横線のX座標の範囲内にあり,かつ,横線のY座標が,拡張した縦線のY座標の範囲内にある」で,式にすると,x'21≦x1≦x'22およびy'11≦y2≦y'12となります.
論文および発表では,L字型(でつながっていると認識したい)状況と定式化を述べ,上記の手続きにより,T字型も十字型も,つながっている判定できるとしましたが,考えてみると,線分を伸ばした上で,十字型で交差しているかどうかの判定に,帰着しているのでした.そうするのなら,「交差」の判定ですが,L字型やT字型も含むとすると,「交差」ではなく「(縦線と横線の)連結」と表記すべきでした.

*1:親または師匠は0人以上任意の人数の子または弟子を持ち,逆にどの人にとっても,親または師匠は高々1人だからです.と言いたいのですが,今回の発表で使用した『真言宗付法血脈』では,例外的に1件だけ,1人の僧侶に2人の師匠がついています.

*2:http://id.nii.ac.jp/1001/00184631/ 研究会登録の有無によっては有料となります.著者の収入にはならず,学会の収益となります.ご了承ください.

*3:十字型の交差の場合に,「つながっている」とみなしてよいのかどうかは,検討しておかないといけません.『将軍家譜』で位置情報付きテキストを作った系図画像には,十字型はありませんでした.『真言宗付法血脈』には数か所あり,うち2箇所はつながっていると解釈すべきで,他は描画の都合上,十字型に交差しているものの,つながってはいないのでした.この系図においては,十字型で交差する横線の両端が,それぞれ他の縦線の上端とL字型でつながっている(いわばフォークのように,師弟関係が上から下に伸びている)場合のみ,つながっていると判断すればよいこと,他の系図でもこのルールで判断できるかどうかは不明であることも,論文に記載しました.

*4:定数τを大きくすれば,より離れていても交差していると見なします.小さくすれば,数ピクセル程度,離れていても,交差していないと判定することになります.系図画像に応じて設定するパラメータの一つですが,今回の適用対象では,幅または高さが2000ピクセルほどの系図画像に対し,『将軍家譜』も『真言宗付法血脈』もτ=20としました.