TOP > 国内特許検索 > プログラム、情報記憶媒体及びクラスタリング装置 > 明細書

明細書 :プログラム、情報記憶媒体及びクラスタリング装置

発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2019-191815 (P2019-191815A)
公開日 令和元年10月31日(2019.10.31)
発明の名称または考案の名称 プログラム、情報記憶媒体及びクラスタリング装置
国際特許分類 G06K   9/00        (2006.01)
FI G06K 9/00 P
請求項の数または発明の数 5
出願形態 OL
全頁数 21
出願番号 特願2018-082354 (P2018-082354)
出願日 平成30年4月23日(2018.4.23)
発明者または考案者 【氏名】中川 正樹
【氏名】ヴ・トラン・ミン・クオン
【氏名】ウン・コアン・フィ
出願人 【識別番号】504132881
【氏名又は名称】国立大学法人東京農工大学
個別代理人の代理人 【識別番号】100090398、【弁理士】、【氏名又は名称】大渕 美千栄
【識別番号】100090387、【弁理士】、【氏名又は名称】布施 行夫
審査請求 未請求
テーマコード 5B064
Fターム 5B064AB03
5B064AB04
5B064AB13
5B064AB17
5B064BA01
5B064BA06
5B064CA13
5B064DC07
5B064DC10
5B064DD06
5B064DD11
5B064EA08
要約 【課題】採点者の採点誤りや採点のばらつきを低減して採点の効率を高めることが可能なクラスタリング装置等を提供すること。
【解決手段】クラスタリング装置は、手書き数式パターンから、方向特徴と、シンボルの出現個数に関する特徴と、シンボル間の位置関係の出現個数に関する特徴と、シンボルの出現位置に関する特徴のうち、方向特徴を含む少なくとも2つの特徴を抽出する特徴抽出部と、複数の手書き数式パターンのそれぞれから抽出した少なくとも2つの特徴に基づいて、複数の手書き数式パターンを類似度に応じて複数のグループに分類する分類部とを含む。
【選択図】図1
特許請求の範囲 【請求項1】
手書き入力された複数の手書き数式パターンを分類するためのプログラムであって、
前記手書き数式パターンから、方向特徴と、シンボルの出現個数に関する特徴と、シンボル間の位置関係の出現個数に関する特徴と、シンボルの出現位置に関する特徴のうち、前記方向特徴を含む少なくとも2つの特徴を抽出する特徴抽出部と、
複数の前記手書き数式パターンのそれぞれから抽出した前記少なくとも2つの特徴に基づいて、複数の前記手書き数式パターンを類似度に応じて複数のグループに分類する分類部としてコンピュータを機能させることを特徴とするプログラム。
【請求項2】
請求項1において、
前記特徴抽出部は、
シンボルの出現位置に関する特徴として、位置毎のシンボルの出現個数に関する特徴を抽出することを特徴とするプログラム。
【請求項3】
請求項1又は2において、
前記特徴抽出部は、
シンボルの出現位置に関する特徴として、位置毎の前記位置関係の出現個数に関する特徴を抽出することを特徴とするプログラム。
【請求項4】
請求項1乃至3のいずれか1項において、
前記特徴抽出部は、
前記手書き数式パターンから数式認識エンジンにより数式を認識し、認識結果に基づいて、シンボルの出現個数に関する特徴と、シンボル間の位置関係の出現個数に関する特徴と、シンボルの出現位置に関する特徴とを抽出することを特徴とするプログラム。
【請求項5】
手書き入力された複数の手書き数式パターンを分類するクラスタリング装置であって、
前記手書き数式パターンから、方向特徴と、シンボルの出現個数に関する特徴と、シンボル間の位置関係の出現個数に関する特徴と、シンボルの出現位置に関する特徴のうち、前記方向特徴を含む少なくとも2つの特徴を抽出する特徴抽出部と、
複数の前記手書き数式パターンのそれぞれから抽出した前記少なくとも2つの特徴に基づいて、複数の前記手書き数式パターンを類似度に応じて複数のグループに分類する分類部とを含むことを特徴とするクラスタリング装置。
発明の詳細な説明 【技術分野】
【0001】
本発明は、プログラム、情報記憶媒体及びクラスタリング装置に関する。
【背景技術】
【0002】
受験者(解答者)の考える力を育て、それを測るために、選択式の問題だけでなく記述式の問題を課す必要性が社会的に認識されてきている。記述式問題を課す場合、短期間で信頼性の高い採点を行うことが求められる。手書き認識の技術を用いれば、人による採点を支援する採点支援や自動採点を行うことが可能となる。記述式解答の必要性が高い算数・数学において、手書き解答の認識を採用した学習システムのプロトタイプが発表されている(例えば、非特許文献1~3)。
【先行技術文献】
【0003】

【非特許文献1】鈴木雅人 他、「手書き数式解析に基づく基礎数学学習支援システムの開発」、電子情報通信学会、信学技法、ET2009-129、p.147-152(2010)
【非特許文献2】千葉智史 他、「手書き数式認識を利用したタブレットPC上での数学eラーニングシステムの試作」、情報処理学会研究報告、Vol.2014-CE-127、No.10、p.1-5(2014)
【非特許文献3】小西渉 他、「手書き数式認識を用いた算数・数学自動採点システム」、情報処理学会研究報告、コンピュータと教育研究会報告、2016-CE-133(7)、1-7(2016)
【発明の概要】
【発明が解決しようとする課題】
【0004】
人による採点を行う際に、解答がランダムに採点者に提示されると、採点がぶれる(ばらつく)ことがよく起こる。大規模な試験では、複数人で採点し、採点の点差が一定以上だと第三者が採点する必要が生じ、第三者を使うコストと時間がかさむ。一方、自動採点では、受験者が採点結果を確認し、採点誤りを指摘できる環境が不可欠であるが、それを前提としても、認識の確信度が高いものだけを自動採点し、確信度が低いものは棄却して人による採点に回す方式が現実的である。従って、採点支援か自動採点かによらず、採点者による採点のばらつきを抑えることが重要である。
【0005】
本発明は、以上のような課題に鑑みてなされたものであり、その目的とするところは、採点者の採点誤りや採点のばらつきを低減して採点の効率を高めることが可能なプログラム、情報記憶媒体及びクラスタリング装置を提供することにある。
【課題を解決するための手段】
【0006】
(1)本発明は、手書き入力された複数の手書き数式パターンを分類するためのプログラムであって、前記手書き数式パターンから、方向特徴と、シンボルの出現個数に関する特徴と、シンボル間の位置関係の出現個数に関する特徴と、シンボルの出現位置に関する特徴のうち、前記方向特徴を含む少なくとも2つの特徴を抽出する特徴抽出部と、複数の前記手書き数式パターンのそれぞれから抽出した前記少なくとも2つの特徴に基づいて、複数の前記手書き数式パターンを類似度に応じて複数のグループに分類する分類部としてコンピュータを機能させることを特徴とするプログラムに関する。また、本発明は、コンピュータ読み取り可能な情報記憶媒体であって、上記各部としてコンピュータを機能させるためのプログラムを記憶した情報記憶媒体に関係する。また、本発明は、上記各部を含
むクラスタリング装置に関係する。
【0007】
本発明によれば、手書き数式パターンから、複数の特徴として、方向特徴と、シンボルの出現個数に関する特徴と、シンボル間の位置関係の出現個数に関する特徴と、シンボルの出現位置に関する特徴のうち、方向特徴を含む少なくとも2つの特徴を抽出し、抽出した少なくとも2つの特徴に基づいて複数の手書き数式パターンを類似度に応じて複数のグループに分類することで、手書き数式パターンを似通ったものごとに精度良くまとめる(クラスタリングする)ことができ、採点者の採点誤りや採点のばらつきを低減して採点の効率を高めることができる。
【0008】
(2)また本発明に係るプログラム、情報記憶媒体及びクラスタリング装置では、前記特徴抽出部は、シンボルの出現位置に関する特徴として、位置毎のシンボルの出現個数に関する特徴を抽出してもよい。
【0009】
本発明によれば、手書き数式パターンを精度良くクラスタリングすることができる。
【0010】
(3)また本発明に係るプログラム、情報記憶媒体及びクラスタリング装置では、前記特徴抽出部は、シンボルの出現位置に関する特徴として、位置毎の前記位置関係の出現個数に関する特徴を抽出してもよい。
【0011】
本発明によれば、手書き数式パターンを精度良くクラスタリングすることができる。
【0012】
(4)また本発明に係るプログラム、情報記憶媒体及びクラスタリング装置では、前記特徴抽出部は、前記手書き数式パターンから数式認識エンジンにより数式を認識し、認識結果に基づいて、シンボルの出現個数に関する特徴と、シンボル間の位置関係の出現個数に関する特徴と、シンボルの出現位置に関する特徴とを抽出してもよい。
【0013】
本発明によれば、手書き数式パターンを精度良くクラスタリングすることができる。
【図面の簡単な説明】
【0014】
【図1】本実施形態のクラスタリング装置の機能ブロック図の一例。
【図2】外接矩形内のオフラインパターンを非線形正規化し、8方向特徴を抽出する一例を示す図。
【図3】オンラインパターンから抽出したシンボル集合特徴の一例を示す図。
【図4】オンラインパターンから抽出した関係集合特徴の一例を示す図。
【図5】オンラインパターンから抽出した位置集合特徴の一例を示す図。
【図6】オンラインパターンから抽出した位置集合特徴の一例を示す図。
【図7】3×3のガウスフィルタの一例を示す図。
【図8】オンラインパターンから抽出した位置依存シンボル集合特徴、位置依存関係集合特徴の一例を示す図。
【図9】オンラインパターンから抽出した数式候補特徴の一例を示す図。
【図10】オフラインパターンから抽出したシンボル集合特徴の一例を示す図。
【図11】オフラインパターンからの関係集合特徴の抽出について説明するための図。
【図12】オフラインパターンからの関係集合特徴の抽出について説明するための図。
【図13】オフラインパターンから抽出した関係集合特徴の一例を示す図。
【図14】オフラインパターンからの位置集合特徴の抽出について説明するための図。
【発明を実施するための形態】
【0015】
以下、本実施形態について説明する。なお、以下に説明する本実施形態は、特許請求の範囲に記載された本発明の内容を不当に限定するものではない。また本実施形態で説明される構成の全てが、本発明の必須構成要件であるとは限らない。

【0016】
1.構成
図1に本実施形態のクラスタリング装置の機能ブロック図の一例を示す。なお本実施形態のクラスタリング装置は図1の構成要素(各部)の一部を省略した構成としてもよい。

【0017】
入力部160は、ユーザが筆記媒体(ペン、指先等)で手書き数式パターン(手書き数式の解答)を入力するためのものであり、その機能は、タブレット、タッチパネル等の筆記面などにより実現できる(オンライン方式の場合)。入力部160は、筆記媒体が筆記面に触れてから離れるまでの筆記媒体の位置(筆点)を表す座標データを一定時間間隔で検出し、検出された座標データ列(座標点系列、オンラインパターンと呼ぶ)をストローク(筆画)のデータとして処理部100に出力する。なお、ストロークの終点から次のストロークの始点までのベクトルをオフストローク(運筆ベクトル)と呼び、ストロークとオフストロークの連続する系列をストローク列と呼ぶ。なお、オフライン方式では、入力部160は、紙等に筆記された手書き数式パターン(オフラインパターンと呼ぶ)を、スキャナー等で白黒画像或いは濃淡画像として読み取る。

【0018】
記憶部170は、処理部100の各部としてコンピュータを機能させるためのプログラムや各種データを記憶するとともに、処理部100のワーク領域として機能し、その機能はハードディスク、RAMなどにより実現できる。

【0019】
表示部190は、処理部100で生成された画像を出力するものであり、その機能は、入力部160としても機能するタッチパネル、LCD或いはCRTなどのディスプレイにより実現できる。

【0020】
処理部100(プロセッサ)は、入力部160からのデータ(座標データ、画像データ)やプログラムなどに基づいて、特徴抽出処理、分類処理、表示制御などの処理を行う。この処理部100は記憶部170内の主記憶部をワーク領域として各種処理を行う。処理部100の機能は各種プロセッサ(CPU、DSP等)、ASIC(ゲートアレイ等)などのハードウェアや、プログラムにより実現できる。処理部100は、特徴抽出部110、分類部112、表示制御部120を含む。

【0021】
特徴抽出部110は、手書き入力された手書き数式パターンから、方向特徴と、シンボルの出現個数(どのシンボルが何個出現するか)に関する特徴と、シンボル間の位置関係の出現個数(どの位置関係が何個出現するか)に関する特徴と、シンボルの出現位置(どの位置にシンボルが出現するか)に関する特徴のうち、方向特徴を含む少なくとも2つの特徴を抽出する。また、特徴抽出部110は、シンボルの出現位置に関する特徴として、位置毎のシンボルの出現個数(どの位置にどのシンボルが何個出現するか)に関する特徴を抽出してもよいし、位置毎の前記位置関係の出現個数(どの位置にどの位置関係が何個出現するか)に関する特徴を抽出してもよい。また、特徴抽出部110は、前記手書き数式パターンから数式認識エンジンにより数式を認識し、認識結果に基づいて、シンボルの出現個数に関する特徴と、シンボル間の位置関係の出現個数に関する特徴と、シンボルの出現位置に関する特徴とを抽出してもよい。なお、シンボルとは、数式に現れる数字、文字(英文字、ギリシャ文字)、演算子(算術演算子、論理演算子、集合演算子、関係演算子)、記号(加算記号、演算記号、積算記号、積分記号、極限記号(lim)、特殊記号(∞等))、関数(log、sin、cos、tan等)、括弧(大、中、小)である。

【0022】
分類部112は、複数の前記手書き数式パターンのそれぞれから抽出した複数の特徴に基づいて、複数の前記手書き数式パターンを類似度に応じて複数のグループに分類する。

【0023】
表示制御部120は、分類部112によって複数のグループに分類された複数の手書き数式パターンをグループ毎に表示部190に表示させる制御を行う。

【0024】
2.本実施形態の手法
本実施形態の手法では、手書き数式パターンから、低レベル特徴(方向特徴)、シンボル集合特徴(シンボルの出現個数に関する特徴)、関係集合特徴(シンボル間の位置関係の出現個数に関する特徴)、位置集合特徴(シンボルの出現位置に関する特徴)のうち、方向特徴を含む少なくとも2つの特徴を抽出し、抽出した複数の特徴に基づいて、複数の手書き数式パターンを似通ったものごとに複数のグループ(クラスタ)に分類(クラスタリング)する。オンライン方式の場合は、更に、位置依存シンボル集合特徴(位置毎のシンボルの出現個数に関する特徴)と、位置依存関係集合特徴(位置毎の位置関係の出現個数に関する特徴)を抽出することができる。低レベル特徴は、シンボルの認識や抽出を行わずに得られる特徴であり、シンボル集合特徴、関係集合特徴、位置集合特徴、位置依存シンボル集合特徴、及び、位置依存関係集合特徴は、シンボルの認識や抽出を行うことで得られる特徴である。以下では、1つから最大6つまでの特徴を抽出する例について説明する。

【0025】
2.1.低レベル特徴(方向特徴)
低レベル特徴としては、手書き数式パターン(オンラインパターン、オフラインパターン)全体をM×Nの区画に分割し、その区画の中での4方向或いは8方向の方向特徴を抽出する。このとき、位置ずれへの耐性を高めるために、各区間にガウスフィルタをかけてぼかしてもよい。

【0026】
具体的には、まず、入力された手書き数式パターンの外接矩形を抽出する。オンラインパターンの場合は、筆点のX座標、Y座標の最大値、最小値から抽出できる。オフラインパターンの場合は、X軸、Y軸への射影の最大値、最小値から抽出できる。次に、非線形正規化を行う。非線形正規化は、手書き数式パターンにおいて、密度が疎なところは圧縮し、密なところは拡大して、パターンの2次元空間密度を一様化する処理である。

【0027】
次に、方向特徴を抽出する。オンラインパターンの場合は、ストローク列から端点や屈曲点などの特徴点を抽出し、特徴点毎にその位置と方向(4方向、8方向、16方向、或いは、それ以上の方向に量子化した方向)の特徴値を抽出する。オフラインパターンの場合は、次の文献に記載の方法などを用いて方向特徴を抽出する:孫 寧,安倍正人,根本義章:改良型方向線素特徴量および部分空間法を用いた高精度な手書き文字認識システム,電子情報通信学会論文誌,D-2, 78 (6), pp922-930 (1995)。図2に、外接矩形内のオフラインパターンを非線形正規化し、8方向の方向特徴を抽出する一例を示す。

【0028】
次に、方向特徴をM×Nの区画に分割し、ガウスフィルタをかける。例えば、ガウスフィルタG(X,μ,σ)は、平均をμ、標準偏差をσ、X方向のマスク幅をtとして、次式(1)で表される。

【0029】
【数1】
JP2019191815A_000003t.gif
方向特徴など、シンボルの認識や抽出に影響されない低レベル特徴の利点は、数式認識やシンボル認識などの失敗に影響されないことである。しかし、数式の書き方の違いには影響を受ける。そこで、本実施形態の手法では、シンボルの認識や抽出を伴う特徴抽出(シンボル集合特徴、関係集合特徴、位置集合特徴の抽出)と併用する。

【0030】
2.2.オンラインパターンからの特徴抽出
オンラインパターンの場合、数式認識エンジンにより数式を認識し、認識結果に基づいて、シンボル集合特徴、関係集合特徴、位置集合特徴を抽出する。数式認識では、シンボルの切出し、シンボルの認識、及び、構造(構文)解析を行う。

【0031】
2.2.1.シンボル集合特徴(シンボルの出現個数に関する特徴)
シンボル集合特徴(BoS:Bag of Symbols)は、数式認識の結果に現れるシンボル毎の出現個数を並べた特徴ベクトル(シンボル出現ベクトル)である。ここでは、シンボルの種類を101種類としており、シンボル出現ベクトルは、101次元のベクトルとなる。

【0032】
図3に、シンボル集合特徴の一例を示す。図3には、手書き数式パターン「1/2+2/3」の認識結果から抽出したシンボル集合特徴(シンボル出現ベクトル)が示されている。図3に示すシンボル出現ベクトル(表の2行目)は、数式中に、シンボル「1」が1個、シンボル「2」が2個、シンボル「3」が1個、シンボル「+」が1個、シンボル「fraction bar(分数罫)」が2個出現していることを示している。シンボル集合特徴は、異なった数式であっても、出現するシンボルとその個数が同じであれば、同一の特徴ベクトルで表される。例えば、数式「1/2+2/3」と「2/3+1/2」は同一の特徴ベクトルで表現される。

【0033】
なお、数式認識エンジンから複数の認識結果(認識候補)が出力される場合、第1位の認識結果(スコアが最も高い認識結果)だけでなく、第2位以降の認識結果からシンボルを計数し、それらを加算してシンボル出現ベクトルを算出してもよい。また、第1位の認識結果から計数した結果には1、第2位の認識結果から計数した結果には1/2、第3位の認識結果から計数した結果には1/4などの重みを付けて加算してもよい。また、それぞれのシンボルである確率(認識の確からしさ)を加味してもよい。

【0034】
2.2.2.関係集合特徴(シンボル間の位置関係の出現個数に関する特徴)
関係集合特徴(BoR:Bag of Relations)は、数式認識の結果に現れるシンボル間の位置関係毎の出現個数を並べた特徴ベクトル(関係出現ベクトル)である。ここでは、シンボル間の位置関係として、6つの位置関係(horizontal(水平)、superscript(上付き)、subscript(下付き)、upper(上方)、lower(下方)、inside(内側))を考えるが、シンボル間の位置関係はこれに限られない。この位置関係を計数するために、手書き数式パターンの認識結果から、シンボルとシンボル間の関係を表現したシンボル関係木を構築し、構築したシンボル関係木から、位置関係毎の出現回数を計測する。

【0035】
図4に、関係集合特徴の一例を示す。図4には、手書き数式パターン「1/2+2/3」の認識結果から構築したシンボル関係木と、シンボル関係木から得た関係集合特徴(関
係出現ベクトル)が示されている。図4に示す関係出現ベクトルは、数式中に、位置関係「horizontal」が2個、位置関係「upper」が2個、位置関係「lower」が2個出現していることを示している。関係集合特徴は、異なった数式であっても、出現する位置関係とその個数が同じであれば、同一の特徴ベクトルで表される。例えば、数式「1/2+2/3」と「4/3-3/2」は同一の特徴ベクトルで表現される。

【0036】
シンボル集合特徴と同様に、数式認識エンジンから複数の認識結果が出力される場合、第1位の認識結果だけでなく、第2位以降の認識結果から位置関係を計数し、それらを加算して関係出現ベクトルを算出してもよい。また、第1位の認識結果から計数した結果には1、第2位の認識結果から計数した結果には1/2、第3位の認識結果から計数した結果には1/4などの重みを付けて加算してもよい。また、それぞれのシンボルである確率を加味してもよい。

【0037】
2.2.3.位置集合特徴(シンボルの出現位置に関する特徴)
位置集合特徴(BoP:Bag of Positions)は、数式認識の結果に現れるシンボルの出現位置を表す特徴ベクトルである。シンボルの出現位置を求めるために、まず、認識結果から構築したシンボル関係木をM×Nの区画に分割する。各区画は、多くとも1つのシンボルを含むか、シンボルを含まない。分割数(M×N)は、シンボル関係木のサイズ、上下の関係(upper、lower、superscript、subscript)の数、左右の関係(horizontal、superscript、subscript)の数から決める。分割数は、正答の数式のシンボル関係木から求めてもよい。そして、i行j列の区画Pijのうち、シンボルを含む区画には1、シンボルを含まない区画には0を与えて、行列P=(Pij)で表現する。シンボル関係木のM×Nの分割数は数式ごとに異なるため、最も多い分割数に整合するために、左上に揃え、右及び下のシンボルを含まない区画には0を与える。そして、区画Pijの要素(0又は1)を行ごとに連結し、更に列ごとに連結して特徴ベクトルとする。これにより、異なる大きさのシンボル関係木を持つ複数の数式から同じ大きさの特徴ベクトルを抽出することができる。

【0038】
図5、図6に、位置集合特徴の例を示す。図5には、認識結果「x/2+2/3」から構築したシンボル関係木と、M×Nに分割したシンボル関係木と、分割したシンボル関係木から得た位置集合特徴が示されており、図6には、認識結果「1/2+2/3」から構築したシンボル関係木と、M×Nに分割したシンボル関係木と、分割したシンボル関係木から得た位置集合特徴が示されている。図5に示す例では、3つの左右の関係(2つのhorizontal、1つのsuperscript)と、3つの上下の関係(2つの縦に並列なupperとlower、1つのsuperscript)があることから、シンボル関係木を4×4の区画に分割している。図6に示す例では、2つの左右の関係(2つのhorizontal)と、2つの上下の関係(2つの縦に並列なupperとlower)があることから、シンボル関係木を3×3の区画に分割しているが、図5に示す例と比較できるように、4×4の区画において左上に揃えて、余白の区画には0を与えている。図5に示す位置集合特徴(ガウスフィルタ適用前)は、4×4の区画において、区間P12、P21、P24、P31、P33、P34、P41、P44にシンボルが現れることを示しており、図6に示す位置集合特徴(ガウスフィルタ適用前)は、4×4の区画において、区間P11、P13、P21、P22、P23、P31、P33にシンボルが現れることを示している。

【0039】
なお、位置ずれへの耐性を高めるために、各区画に図7に示す3×3のガウスフィルタをかけてもよい。この場合、隣がない区画には値を配分しない。各区間にガウスフィルタを適用した結果の要素を行ごとに連結し、更に列ごとに連結して特徴ベクトルとする。図5、図6には、ガウスフィルタ適用後の位置集合特徴が示されている。

【0040】
位置集合特徴に、シンボル集合特徴を組み合わせて、分割したそれぞれの区画からシン
ボル集合特徴を抽出してもよい。この特徴を、位置依存シンボル集合特徴(Pb_BoS:Position based Bag of Symbols)と呼ぶ。位置依存シンボル集合特徴は、位置(区画)毎のシンボルの出現個数に関する特徴である。また、位置集合特徴に、関係集合特徴を組み合わせて、分割したそれぞれの区画から関係集合特徴を抽出してもよい。この特徴を、位置依存関係集合特徴(Pb_BoR:Position based Bag of Relations)と呼ぶ。位置依存関係集合特徴は、位置毎の位置関係の出現個数に関する特徴である。シンボル集合特徴と関係集合特徴が、数式全体から抽出するのに対して、位置依存シンボル集合特徴と位置依存関係集合特徴は、シンボル関係木を分割した各区画から抽出する。各区画に含まれるシンボルは1個、各区画に含まれる位置関係も数個になる。位置集合特徴と同様に、位置ずれへの耐性を高めるために、各区間にガウスフィルタをかけてぼかしてもよい。この結果、各区画にはシンボルが1個しか含まれなくても、ガウスフィルタのぼかしの結果、複数のシンボルで特徴値が生起する。

【0041】
図8に、位置依存シンボル集合特徴と、位置依存関係集合特徴の一例を示す。図8には、認識結果「1/2+2/3」から構築したシンボル関係木と、M×N(ここでは、3×3)に分割したシンボル関係木と、分割された各区画へのガウスフィルタの適用と、各区画Pijのシンボル出現ベクトルからなる位置依存シンボル集合特徴(Pb_BoS)と、各区画Pijの関係出現ベクトルからなる位置依存関係集合特徴(Pb_BoR)が示されている。

【0042】
これらの特徴に加えて、認識結果の候補から特徴を抽出することもできる。これを数式候補特徴と呼ぶ。まず、手書き数式パターンから数式を認識して複数の認識候補を得る。全ての認識候補のシンボル関係木をM×Nの区画に分割する。分割数が少ない認識候補については、図6に示すように最大の分割数に合わせて左上に揃える。各区画にガウスフィルタを適用しても適用しなくてもよいが、上述した位置集合特徴、位置依存シンボル集合特徴、位置依存関係集合特徴でガウスフィルタを適用しているので、ここでは適用しない。そして、最大のM×Nの各区間に現れるシンボルのインデックスを得る。これを行ごとに連結し、更に列ごとに連結して特徴ベクトルを得る。

【0043】
図9に、数式候補特徴の一例を示す。図9には、認識結果「x/2+2/3」から構築してM×N(ここでは、4×4)に分割したシンボル関係木と、各区画のシンボルのインデックスと、それを連結して得た数式候補特徴が示されている。

【0044】
2.3.オフラインパターンからの特徴抽出
オフラインパターンの場合、シンボルの切出し等がオンラインパターンより多少難しいことから、ここでは、数式認識を利用せずにシンボル集合特徴、関係集合特徴、位置集合特徴を抽出する方法について説明する。もちろん、数式認識を利用して特徴抽出を行うこともできる。

【0045】
2.3.1.シンボル集合特徴(シンボルの出現個数に関する特徴)
シンボル集合特徴を抽出する場合、オフラインパターンから連結要素(背景が白画素の場合、黒画素の連結成分)を抽出し、抽出した連結要素に対してシンボル認識(単文字認識)を適用して、認識結果(上位の認識候補)とその確率値(認識スコア)を出力する。そして、シンボル毎の確率値を並べてシンボル出現ベクトル(101次元のベクトル)とする。オフライン方式の場合、シンボルが分離してしまうことがある。例えば、シンボル「=」などである。これを防止するために、分離して認識されたシンボルを統合して再認識するルールを導入する。「=」の場合は、「-」が2つ連続する場合は、「=」として再認識し、その確率が閾値より高い場合は、それぞれの連結要素を更に連結し、「=」に再認識する。

【0046】
次式(2)に示すように、シンボル集合特徴Sは、それぞれの連結要素Cに対する認識結果から得たシンボル出現ベクトルS(C)の和をとって求める。

【0047】
【数2】
JP2019191815A_000004t.gif
図10に、オフラインパターンから抽出したシンボル集合特徴の一例を示す。図10には、手書き数式パターン「=a/8」の各連結要素に対する認識結果(認識スコア)から得たシンボル出現ベクトルと、これらシンボル出現ベクトルの和をとって求めたシンボル集合特徴が示されている。図10に示すシンボル集合特徴は、数式中に、シンボル「a」が「0.9」個、シンボル「=」が「0.8」個、シンボル「fraction bar(分数罫)」が「0.7」個、シンボル「8」が「0.9」個出現していることを示しており、実際のシンボルの出現個数と概ね一致している。この例では、確率値を有限個の候補で打ち切っているが、確率値以外にも順位をもとに、第1位には1、第2位には1/2、第3位には1/4などの重みをつけて加算することもできる。このとき、第1位の結果のみを用いることも可能である。

【0048】
2.3.2.関係集合特徴(シンボル間の位置関係の出現個数に関する特徴)
関係集合特徴を抽出する場合、オフラインパターンから連結要素を抽出し、抽出した連結要素(シンボル)の周囲の領域を図11に示すように9分割し、番号付けする。例えば、領域「0」に他の連結要素があれば(例えば、シンボル「√」の場合)、オンライン方式での位置関係「inside」が存在することになる。また、領域「1」に他の連結要素があれば位置関係「upper」が存在し、領域「5」に他の連結要素があれば位置関係「lower」が存在し、領域「2」に他の連結要素があれば位置関係「superscript」が存在し、領域「4」に他の連結要素があれば位置関係「subscript」が存在し、領域「3」或いは「7」に他の連結要素があれば位置関係「horizontal」が存在することになる。ある連結要素とその周囲の連結要素との位置関係は射影などの方法によって求める。図12に示すように、各連結要素の外接矩形を求め、2つの外接矩形の間に遮る他の連結要素がなければ(例えば、2つの連結要素のそれぞれの外接矩形の中点を結ぶ線に、他の連結要素の外接矩形が交差しないならば)、それらは近隣する連結要素として、図11のいずれかの位置関係を与える。例えば、図12において、シンボル「x」に相当する連結要素に近隣する連結要素は、シンボル「=」に相当する連結要素と、シンボル「+」に相当する連結要素と、シンボル「fraction bar」に相当する連結要素である。そして、位置関係(領域の番号)毎の出現回数(他の連結要素の個数)を並べて関係出現ベクトルとする。

【0049】
次式(3)に示すように、関係集合特徴Rは、それぞれの連結要素Cの関係出現ベクトルR(C)の和をとって求める。この例では、9つのいずれかの関係にある他の連結要素の個数を関係集合特徴としているが、連結要素間の距離や連結要素の大きさを反映した特徴値としてもよい。

【0050】
【数3】
JP2019191815A_000005t.gif
図13に、オフラインパターンから抽出した関係集合特徴の一例を示す。図13には、手書き数式パターン「=a/8」の各連結要素の関係出現ベクトルと、これら関係出現ベクトルの和をとって求めた関係集合特徴が示されている。例えば、シンボル「a」に相当する連結要素の関係出現ベクトルは、領域「5」の位置関係にある他の連結要素が1個、領域「6」の位置関係にある他の連結要素が1個存在することを示している。また、図1
3に示す関係集合特徴は、数式中に、領域「1」、「5」の位置関係がそれぞれ2つ、領域「2」、「3」、「4」、「6」、「7」、「8」の位置関係がそれぞれ1つ出現していることを示している。

【0051】
2.3.3.位置集合特徴(シンボルの出現位置に関する特徴)
位置集合特徴を抽出する場合、シンボルの出現位置を求めるため、オフラインパターンをM×Nに分割する。この分割数は、手書き数式内の上下の関係(図11の領域8、1、2、6、4、5、6の関係)の数、左右の関係(図11の領域2、3、4、8、7、6の関係)の数から決める。分割数は、正答の数式から求めてもよい。図14に示す例では、左右の関係が、「=」と「fraction bar」、「x」と「+」、「+」と「1」(分子では、「+」と「5」)の3つあり、また、等号の後に空白を入れることが多いことから横に5分割し、上下の関係が、分母と「fraction bar」、分子と「fraction bar」の2つあることから縦に3分割して、5×3の区画に分割している。

【0052】
そして、オフラインパターンから連結要素を抽出し、それぞれの連結要素Cの区画Gへの寄与P(G,C)を次式(4)により求める。

【0053】
【数4】
JP2019191815A_000006t.gif
それぞれの区画にガウスフィルタを適用し、次式(5)に示すように、連結要素で和をとって、連結要素の各区画への寄与を並べて特徴ベクトルとする。なお、式(5)において、Gnm(1≦n≦N,1≦m≦M)は、n行m列の区画を示す。

【0054】
【数5】
JP2019191815A_000007t.gif
以上述べたように、オフラインパターンから抽出する特徴は、オフラインの手書き数式パターンをシンボル関係木として認識しなくても抽出することができる。つまり、オフラインパターンから抽出する特徴は、オンラインパターンから抽出した特徴とは若干異なっている。オフラインパターン用の上記特徴は、オンラインパターンから抽出することもできる。この場合、オンラインパターンから時系列情報を除いて画像に変換し、その画像から特徴抽出を行う。

【0055】
2.4.クラスタリング
手書き数式パターンのクラスタリングでは、まず、各手書き数式パターンのそれぞれから抽出した複数の特徴(シンボルの認識や抽出に影響されない低レベル特徴(方向特徴)、シンボルの認識や抽出を経て得られるシンボル集合特徴、関係集合特徴、位置集合特徴(或いは、位置集合特徴に代えて、位置依存集合特徴、位置依存関係集合特徴)など)に基づいて、手書き数式パターン間の距離(類似度)を求める。第1の方法(加重和法)は、各特徴間の距離の加重和をとる方法である。各特徴は違った意味や分散を持つので、それらを公平に扱うためである。加重和法による2つの手書き数式パターンHME、HME間の距離Dis(HME,HME)は、次式(6)により表される。

【0056】
【数6】
JP2019191815A_000008t.gif
ここで、fは、手書き数式パターンからi番目の特徴ベクトルを抽出する関数であり、Iは、特徴の総数である。例えば、I=4とした場合、1番目の特徴を方向特徴、2番目の特徴をシンボル集合特徴、3番目の特徴を関係集合特徴、4番目の特徴を位置集合特徴とすることができる。d(ν,ν)は、ユークリッド距離やマハラノビス距離などの、距離関数による2つのベクトルνとνの距離である。αは、i番目の特徴間の距離に与える重みであり、全ての重みの合計が1になるように、列挙法で決定する。

【0057】
第2の方法(正規化法)は、個々の特徴間の距離をその距離の平均で割ることで正規化する方法である。正規化法による2つの手書き数式パターンHME、HME間の距離Dis(HME,HME)は、次式(7)により表される。

【0058】
【数7】
JP2019191815A_000009t.gif
ここで、μは、任意の2つの手書き数式パターンについてそれらのi番目の特徴ベクトル間の距離を求め、その平均をとったものである。

【0059】
第3の方法(正規化加重和法)は、加重和法と正規化法を統合した方法である。この方法では、加重和法で個々の特徴間の距離が大小ばらばらになることを防ぐために、i番目の特徴ベクトルをその平均で除してから加重和法を適用する。正規化加重和法による2つの手書き数式パターンHME、HME間の距離DisNW(HME,HME)は、次式(8)により表される。

【0060】
【数8】
JP2019191815A_000010t.gif
これらの方法により、2つの手書き数式パターン間の距離を、クラスタリングの対象とする手書き数式パターンの全ての組み合わせについて求め、類似する手書き数式パターン毎にクラスタにクラスタリングする。クラスタリングには、K-means法、階層化クラスタリング、DBSCANなどの方法が利用できる。以上の手法により、複数の手書き数式パターンを似通ったものごとに精度良くまとめることができ、採点者の採点誤りや採点のばらつきを低減して採点の効率を高めることができる。

【0061】
なお、全ての解答(手書き数式パターン)をクラスタリングして手動採点(採点者による採点)に回すようにしてもよいし、全ての解答を数式認識エンジンにより認識し、認識結果が信頼できるか否かを判定し、信頼できると判定された認識結果については自動採点(認識結果が正答であるか誤答であるかを判定)し、信頼できないと判定された認識結果については当該認識結果に対応する解答をクラスタリングして手動採点に回すようしてもよい。また、全ての解答をクラスタリングし、クラスタごとに全ての解答を数式認識エンジンにより認識し、正答が1つでも(或いは、一定比率以上)含まれるクラスタについて
は当該クラスタに含まれる解答を手動採点に回し、正答が1つも(或いは、一定比率未満しか)含まれず、正答を含むクラスタとの距離が一定値以上のクラスタについては当該クラスタに含まれる解答を誤答として判定するようにしてもよい。なお、クラスタ間の距離は、クラスタのセントロイドを求め、セントロイド間の重み付きユークリッド距離を使うことで簡単に計算できる。

【0062】
3.評価実験
本実施形態のクラスタリング手法を評価する実験を行った。クラスタリングの評価指標として、次式(9)に示すPurity(各クラスタに含まれる本来同じクラスに属する要素数を全クラスタに渡って加えた総和を、全要素数で除した値)を用いた。クラスタごとに採点することを考えると、一つ一つのクラスタに違いものが少ない(すなわち、Purityが1に近い)方が良い。

【0063】
【数9】
JP2019191815A_000011t.gif
ここで、W={W,W,…,W}は、クラスタの集合であり、C={C,C,…,C}は、クラスの集合であり、Kは、クラスタの数であり、Jは、クラスの数であり、Nは、全要素数である。

【0064】
3.1.オンライン方式についての実験
本実験においては、21名の被験者に、それぞれ50種類の数式を3つのインターフェース(ガイドラインなし、枠の中央に水平なガイドラインあり、枠の上端、中央、下端のそれぞれに水平なガイドラインあり)で筆記してもらったオンライン手書き数式パターン(合計3,150のパターンが50のクラスに属する)を収集した。パターンに出現するシンボルの種類は101種類である。収集したデータセットをDset_50と呼ぶ。

【0065】
クラスタリング手法としては、ユークリッド距離に基づくk-means法を基本とするが、k-means法はセントロイドの初期値に依存し、極小解に陥り易いので、k-means法(初期セントロイドはランダムに初期化する)と、k-means++法(初期セントロイドをなるべく分散させる。方法は次の文献による:D. Arthur and S. Vassilvitskii, “k-means++: The Advantages of Careful Seeding,” in Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, New Orleans, 2007.)と、理想法(初期セントロイドを正しいクラスの中から選ぶ)の3通りの初期化手法を試みた。理想法は現実には利用できないが、クラスタリングの上限を求めることができる。

【0066】
本実験では、クラスタの数はクラスの数とし、評価指標として式(9)に示すPurityを用いた。クラスタリングに利用する特徴として、上述した個々の特徴とそれらの統合を評価した。特徴の統合では重み(α)の学習が必要なため、データベースを5つに分け、4つ(学習セット)で学習し、残り1つ(テストパターン)で評価することを、役割を変えて5回実験し、結果の平均値を求めた(5重クロスバリデーション)。表1に、個々の特徴の全てとそれらの統合に対するクラスタリング性能の評価結果を示す。

【0067】
【表1】
JP2019191815A_000012t.gif
個々の特徴では、方向特徴(実験番号1)は安定している。特に、ランダムに初期化するk-means法で性能が一番高い。シンボル集合特徴(実験番号2)は、僅差ではあるが、k-means++法と理想法で最良の性能を示した。関係集合特徴(実験番号32)、位置集合特徴(実験番号4)、位置依存シンボル集合特徴(実験番号5)、位置依存関係集合特徴(実験番号6)、数式候補特徴(実験番号7)は、単独では高い性能を示さなかった。なお、数式認識特徴では、認識候補のうち第1位の候補から抽出した特徴を用いた。

【0068】
特徴の統合(加重和法、正規化法、正規化加重和法)の実験では、個々の特徴よりも高い性能を示し、特に、加重和法が優れていた。まず、低レベル特徴である方向特徴と、数式認識を適用して得られる特徴であるシンボル集合特徴、関係集合特徴、位置集合特徴の統合が効果的であることが分かった(実験番号8、9に対して実験番号10以降)。次に、位置集合特徴の代わりに、位置依存シンボル集合特徴、位置依存関係集合特徴を統合する実験では、クラスタリング手法の違いによって優劣が異なる結果となるが、同様に効果的であることが分かった(実験番号10に対して実験番号11)。更に、数式候補特徴を
追加すると、若干性能が低下し(実験番号11に対して実験番号12)、また、方向特徴と数式候補特徴を統合した場合では、更に性能が低下した(実験番号13)。このことから、シンボル集合特徴、関係集合特徴、位置集合特徴の3つの統合が数式候補特徴より優れている可能性が高い。また、方向特徴とシンボル集合特徴、関係集合特徴に、更に、位置集合特徴と位置依存シンボル集合特徴、位置依存関係集合特徴を統合する実験(実験番号14)では、位置集合特徴、或いは、位置依存シンボル集合特徴、位置依存関係集合特徴のどちらか1つの統合で効果を示すが、両方の統合(位置集合特徴と位置依存シンボル集合特徴の統合、位置集合特徴と位置依存関係集合特徴の統合)は効果的でないことが分かった。

【0069】
特徴の統合が効果的であることは確認できたが、一方で、抽出する特徴の数が多くなるほど計算量は大きくなる。そこで、計算量が限られる場合に、低レベル特徴である方向特徴と、シンボルの認識や抽出を経て得られるシンボル集合特徴、関係集合特徴、位置集合特徴のいずれか1つとを統合する方法も考えられる。この場合の評価結果を表2に示す。

【0070】
【表2】
JP2019191815A_000013t.gif
シンボル集合特徴、関係集合特徴、位置集合特徴のいずれか1つよりも、これらに方向特徴を統合した方が効果的であること、及び、方向特徴単独よりも、方向特徴とシンボル集合特徴とを統合した場合が優位であることが分かった。

【0071】
3.2.オフライン方式についての実験
本実験においては、23名の被験者に、それぞれ23問の問題に対する正しい解答と2つのパターンの誤った解答を指定して筆記してもらったオフライン手書き数式パターン(合計1,518パターン)を収集した。収集したデータセットをDset_22Qsと呼ぶ。本実験では、問題ごとに特徴抽出を行い、クラスタリングの実験を行った。従って、問題ごとに正答のクラスが1つと誤答のクラスが2つあることになる。評価結果は22問の解答に対するクラスタリング性能の平均で示す。この場合、クラス数は3である。Dset_22Qsに加えて、Dset_50をオフライン化(時系列の筆点間を直線で結び、一定の太さで肉付け)したものも利用した。この場合のクラス数は50である。

【0072】
まず、特徴ごとのクラスタリング性能を評価した。クラスタリング手法として、k-means++を用いた。式(9)におけるパラメータkの値をクラス数に設定した。つまり、Dset_22Qsではk=3、Dset_50ではk=50とした。Dset_22Qsは、問題ごとに実験しており、それぞれにPurityが求まるため、それらの平均と標準偏差を求めた。一方、Dset_50は、ひとまとめに実験しているので、データ全体に対するPurityが求まる。表3に、個々の特徴に対するクラスタリング性能の評価結果を示す。

【0073】
【表3】
JP2019191815A_000014t.gif
個々の特徴では、シンボル集合特徴(実験番号2)が最も高い性能を示した。一方、方向特徴(実験番号1)、関係集合特徴(実験番号3)、位置集合特徴(実験番号4、5)はシンボル集合特徴に及ばなかった。

【0074】
次に、特徴を統合した場合のクラスタリング性能を評価した。加重和法と正規化加重和法は、最適な重みを設定する必要があるため、5重のクロスバリデーションを行った。但し、Dset_22Qsでは問題ごとにクラスタリングするため、問題ごとのデータ数が少なく、また、重みの最適値が異なることから、クロスバリデーションには適さない。そこで、Dset_22Qsについては加重和法と正規化加重和法の実験は行わなかった。表4に、特徴の統合に対するクラスタリング性能の評価結果を示す。

【0075】
【表4】
JP2019191815A_000015t.gif
加重和法で統合した場合(実験番号6~9)は、シンボル集合特徴と統合することで、関係集合特徴や位置集合特徴の単独の場合よりも性能は向上したが、シンボル集合特徴単独からの性能向上は見られなかった。正規化法の場合は、統合の効果は見られなかった。
正規化加重和では、若干ではあるが、シンボル集合特徴単独より高い性能が見られた。

【0076】
オンラインの方式の場合と同様に、計算量が限られる場合に、低レベル特徴である方向特徴と、シンボルの認識や抽出を経て得られるシンボル集合特徴、関係集合特徴、位置集合特徴のいずれか1つとを統合する方法も考えられる。この場合の評価結果を表5に示す。

【0077】
【表5】
JP2019191815A_000016t.gif
オンライン方式の場合と同様に、シンボル集合特徴、関係集合特徴、位置集合特徴のいずれか1つよりも、これらに方向特徴を統合した方が効果的であること、及び、方向特徴単独よりも、方向特徴とシンボル集合特徴とを統合した場合が優位であることが分かった。また、方向特徴とシンボル集合特徴とを統合した場合、表4の実験番号11に迫る性能となることが分かった。

【0078】
オフライン方式では、シンボルの抽出に連結要素に基づく抽出を採用しているために、オンライン方式ほどの性能が出ていない可能性がある。最近の手法である深層ニューラルネットワークによるシンボルや関係、位置の抽出を行うことで、個々の性能が上がり、特徴を統合する効果がオンライン方式に近づくことが期待できる。その場合、オフライン方式にも本発明が一層効果を発揮することが期待できる。

【0079】
なお、本発明は、上述の実施の形態に限定されるものではなく、種々の変更が可能である。本発明は、実施の形態で説明した構成と実質的に同一の構成(例えば、機能、方法及び結果が同一の構成、あるいは目的及び効果が同一の構成)を含む。また、本発明は、実施の形態で説明した構成の本質的でない部分を置き換えた構成を含む。また、本発明は、実施の形態で説明した構成と同一の作用効果を奏する構成又は同一の目的を達成することができる構成を含む。また、本発明は、実施の形態で説明した構成に公知技術を付加した構成を含む。
【符号の説明】
【0080】
100…処理部、110…特徴抽出部、112…分類部、120…表示制御部、160…入力部、170…記憶部、190…表示部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13