(57)【要約】【課題】採点者の採点誤りや採点のばらつきを低減して採点の効率を高めることが可能なクラスタリング装置等を提供すること。【解決手段】クラスタリング装置は、手書き数式パターンから、方向特徴と、シンボルの出現個数に関する特徴と、シンボル間の位置関係の出現個数に関する特徴と、シンボルの出現位置に関する特徴のうち、方向特徴を含む少なくとも２つの特徴を抽出する特徴抽出部と、複数の手書き数式パターンのそれぞれから抽出した少なくとも２つの特徴に基づいて、複数の手書き数式パターンを類似度に応じて複数のグループに分類する分類部とを含む。【選択図】図１
2019191815.tif 000002
【特許請求の範囲】
【請求項１】
手書き入力された複数の手書き数式パターンを分類するためのプログラムであって、
前記手書き数式パターンから、方向特徴と、シンボルの出現個数に関する特徴と、シンボル間の位置関係の出現個数に関する特徴と、シンボルの出現位置に関する特徴のうち、前記方向特徴を含む少なくとも２つの特徴を抽出する特徴抽出部と、
複数の前記手書き数式パターンのそれぞれから抽出した前記少なくとも２つの特徴に基づいて、複数の前記手書き数式パターンを類似度に応じて複数のグループに分類する分類部としてコンピュータを機能させることを特徴とするプログラム。
【請求項２】
請求項１において、
前記特徴抽出部は、
シンボルの出現位置に関する特徴として、位置毎のシンボルの出現個数に関する特徴を抽出することを特徴とするプログラム。
【請求項３】
請求項１又は２において、
前記特徴抽出部は、
シンボルの出現位置に関する特徴として、位置毎の前記位置関係の出現個数に関する特徴を抽出することを特徴とするプログラム。
【請求項４】
請求項１乃至３のいずれか１項において、
前記特徴抽出部は、
前記手書き数式パターンから数式認識エンジンにより数式を認識し、認識結果に基づいて、シンボルの出現個数に関する特徴と、シンボル間の位置関係の出現個数に関する特徴と、シンボルの出現位置に関する特徴とを抽出することを特徴とするプログラム。
【請求項５】
手書き入力された複数の手書き数式パターンを分類するクラスタリング装置であって、
前記手書き数式パターンから、方向特徴と、シンボルの出現個数に関する特徴と、シンボル間の位置関係の出現個数に関する特徴と、シンボルの出現位置に関する特徴のうち、前記方向特徴を含む少なくとも２つの特徴を抽出する特徴抽出部と、
複数の前記手書き数式パターンのそれぞれから抽出した前記少なくとも２つの特徴に基づいて、複数の前記手書き数式パターンを類似度に応じて複数のグループに分類する分類部とを含むことを特徴とするクラスタリング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム、情報記憶媒体及びクラスタリング装置に関する。
【背景技術】
【０００２】
受験者（解答者）の考える力を育て、それを測るために、選択式の問題だけでなく記述式の問題を課す必要性が社会的に認識されてきている。記述式問題を課す場合、短期間で信頼性の高い採点を行うことが求められる。手書き認識の技術を用いれば、人による採点を支援する採点支援や自動採点を行うことが可能となる。記述式解答の必要性が高い算数・数学において、手書き解答の認識を採用した学習システムのプロトタイプが発表されている（例えば、非特許文献１〜３）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】鈴木雅人  他、「手書き数式解析に基づく基礎数学学習支援システムの開発」、電子情報通信学会、信学技法、ＥＴ２００９−１２９、ｐ.１４７−１５２（２０１０）
【非特許文献２】千葉智史  他、「手書き数式認識を利用したタブレットＰＣ上での数学ｅラーニングシステムの試作」、情報処理学会研究報告、Ｖｏｌ.２０１４−ＣＥ−１２７、Ｎｏ.１０、ｐ.１−５（２０１４）
【非特許文献３】小西渉  他、「手書き数式認識を用いた算数・数学自動採点システム」、情報処理学会研究報告、コンピュータと教育研究会報告、２０１６−ＣＥ−１３３（７）、１−７（２０１６）
【発明の概要】
【発明が解決しようとする課題】
【０００４】
人による採点を行う際に、解答がランダムに採点者に提示されると、採点がぶれる（ばらつく）ことがよく起こる。大規模な試験では、複数人で採点し、採点の点差が一定以上だと第三者が採点する必要が生じ、第三者を使うコストと時間がかさむ。一方、自動採点では、受験者が採点結果を確認し、採点誤りを指摘できる環境が不可欠であるが、それを前提としても、認識の確信度が高いものだけを自動採点し、確信度が低いものは棄却して人による採点に回す方式が現実的である。従って、採点支援か自動採点かによらず、採点者による採点のばらつきを抑えることが重要である。
【０００５】
本発明は、以上のような課題に鑑みてなされたものであり、その目的とするところは、採点者の採点誤りや採点のばらつきを低減して採点の効率を高めることが可能なプログラム、情報記憶媒体及びクラスタリング装置を提供することにある。
【課題を解決するための手段】
【０００６】
（１）本発明は、手書き入力された複数の手書き数式パターンを分類するためのプログラムであって、前記手書き数式パターンから、方向特徴と、シンボルの出現個数に関する特徴と、シンボル間の位置関係の出現個数に関する特徴と、シンボルの出現位置に関する特徴のうち、前記方向特徴を含む少なくとも２つの特徴を抽出する特徴抽出部と、複数の前記手書き数式パターンのそれぞれから抽出した前記少なくとも２つの特徴に基づいて、複数の前記手書き数式パターンを類似度に応じて複数のグループに分類する分類部としてコンピュータを機能させることを特徴とするプログラムに関する。また、本発明は、コンピュータ読み取り可能な情報記憶媒体であって、上記各部としてコンピュータを機能させるためのプログラムを記憶した情報記憶媒体に関係する。また、本発明は、上記各部を含
むクラスタリング装置に関係する。
【０００７】
本発明によれば、手書き数式パターンから、複数の特徴として、方向特徴と、シンボルの出現個数に関する特徴と、シンボル間の位置関係の出現個数に関する特徴と、シンボルの出現位置に関する特徴のうち、方向特徴を含む少なくとも２つの特徴を抽出し、抽出した少なくとも２つの特徴に基づいて複数の手書き数式パターンを類似度に応じて複数のグループに分類することで、手書き数式パターンを似通ったものごとに精度良くまとめる（クラスタリングする）ことができ、採点者の採点誤りや採点のばらつきを低減して採点の効率を高めることができる。
【０００８】
（２）また本発明に係るプログラム、情報記憶媒体及びクラスタリング装置では、前記特徴抽出部は、シンボルの出現位置に関する特徴として、位置毎のシンボルの出現個数に関する特徴を抽出してもよい。
【０００９】
本発明によれば、手書き数式パターンを精度良くクラスタリングすることができる。
【００１０】
（３）また本発明に係るプログラム、情報記憶媒体及びクラスタリング装置では、前記特徴抽出部は、シンボルの出現位置に関する特徴として、位置毎の前記位置関係の出現個数に関する特徴を抽出してもよい。
【００１１】
本発明によれば、手書き数式パターンを精度良くクラスタリングすることができる。
【００１２】
（４）また本発明に係るプログラム、情報記憶媒体及びクラスタリング装置では、前記特徴抽出部は、前記手書き数式パターンから数式認識エンジンにより数式を認識し、認識結果に基づいて、シンボルの出現個数に関する特徴と、シンボル間の位置関係の出現個数に関する特徴と、シンボルの出現位置に関する特徴とを抽出してもよい。
【００１３】
本発明によれば、手書き数式パターンを精度良くクラスタリングすることができる。
【図面の簡単な説明】
【００１４】
【図１】本実施形態のクラスタリング装置の機能ブロック図の一例。
【図２】外接矩形内のオフラインパターンを非線形正規化し、８方向特徴を抽出する一例を示す図。
【図３】オンラインパターンから抽出したシンボル集合特徴の一例を示す図。
【図４】オンラインパターンから抽出した関係集合特徴の一例を示す図。
【図５】オンラインパターンから抽出した位置集合特徴の一例を示す図。
【図６】オンラインパターンから抽出した位置集合特徴の一例を示す図。
【図７】３×３のガウスフィルタの一例を示す図。
【図８】オンラインパターンから抽出した位置依存シンボル集合特徴、位置依存関係集合特徴の一例を示す図。
【図９】オンラインパターンから抽出した数式候補特徴の一例を示す図。
【図１０】オフラインパターンから抽出したシンボル集合特徴の一例を示す図。
【図１１】オフラインパターンからの関係集合特徴の抽出について説明するための図。
【図１２】オフラインパターンからの関係集合特徴の抽出について説明するための図。
【図１３】オフラインパターンから抽出した関係集合特徴の一例を示す図。
【図１４】オフラインパターンからの位置集合特徴の抽出について説明するための図。
【発明を実施するための形態】
【００１５】
以下、本実施形態について説明する。なお、以下に説明する本実施形態は、特許請求の範囲に記載された本発明の内容を不当に限定するものではない。また本実施形態で説明される構成の全てが、本発明の必須構成要件であるとは限らない。
【００１６】
１．構成
図１に本実施形態のクラスタリング装置の機能ブロック図の一例を示す。なお本実施形態のクラスタリング装置は図１の構成要素（各部）の一部を省略した構成としてもよい。
【００１７】
入力部１６０は、ユーザが筆記媒体（ペン、指先等）で手書き数式パターン（手書き数式の解答）を入力するためのものであり、その機能は、タブレット、タッチパネル等の筆記面などにより実現できる（オンライン方式の場合）。入力部１６０は、筆記媒体が筆記面に触れてから離れるまでの筆記媒体の位置（筆点）を表す座標データを一定時間間隔で検出し、検出された座標データ列（座標点系列、オンラインパターンと呼ぶ）をストローク（筆画）のデータとして処理部１００に出力する。なお、ストロークの終点から次のストロークの始点までのベクトルをオフストローク（運筆ベクトル）と呼び、ストロークとオフストロークの連続する系列をストローク列と呼ぶ。なお、オフライン方式では、入力部１６０は、紙等に筆記された手書き数式パターン（オフラインパターンと呼ぶ）を、スキャナー等で白黒画像或いは濃淡画像として読み取る。
【００１８】
記憶部１７０は、処理部１００の各部としてコンピュータを機能させるためのプログラムや各種データを記憶するとともに、処理部１００のワーク領域として機能し、その機能はハードディスク、ＲＡＭなどにより実現できる。
【００１９】
表示部１９０は、処理部１００で生成された画像を出力するものであり、その機能は、入力部１６０としても機能するタッチパネル、ＬＣＤ或いはＣＲＴなどのディスプレイにより実現できる。
【００２０】
処理部１００（プロセッサ）は、入力部１６０からのデータ（座標データ、画像データ）やプログラムなどに基づいて、特徴抽出処理、分類処理、表示制御などの処理を行う。この処理部１００は記憶部１７０内の主記憶部をワーク領域として各種処理を行う。処理部１００の機能は各種プロセッサ（ＣＰＵ、ＤＳＰ等）、ＡＳＩＣ（ゲートアレイ等）などのハードウェアや、プログラムにより実現できる。処理部１００は、特徴抽出部１１０、分類部１１２、表示制御部１２０を含む。
【００２１】
特徴抽出部１１０は、手書き入力された手書き数式パターンから、方向特徴と、シンボルの出現個数（どのシンボルが何個出現するか）に関する特徴と、シンボル間の位置関係の出現個数（どの位置関係が何個出現するか）に関する特徴と、シンボルの出現位置（どの位置にシンボルが出現するか）に関する特徴のうち、方向特徴を含む少なくとも２つの特徴を抽出する。また、特徴抽出部１１０は、シンボルの出現位置に関する特徴として、位置毎のシンボルの出現個数（どの位置にどのシンボルが何個出現するか）に関する特徴を抽出してもよいし、位置毎の前記位置関係の出現個数（どの位置にどの位置関係が何個出現するか）に関する特徴を抽出してもよい。また、特徴抽出部１１０は、前記手書き数式パターンから数式認識エンジンにより数式を認識し、認識結果に基づいて、シンボルの出現個数に関する特徴と、シンボル間の位置関係の出現個数に関する特徴と、シンボルの出現位置に関する特徴とを抽出してもよい。なお、シンボルとは、数式に現れる数字、文字（英文字、ギリシャ文字）、演算子（算術演算子、論理演算子、集合演算子、関係演算子）、記号(加算記号、演算記号、積算記号、積分記号、極限記号（lim）、特殊記号（∞等）)、関数（log、sin、cos、tan等）、括弧（大、中、小）である。
【００２２】
分類部１１２は、複数の前記手書き数式パターンのそれぞれから抽出した複数の特徴に基づいて、複数の前記手書き数式パターンを類似度に応じて複数のグループに分類する。
【００２３】
表示制御部１２０は、分類部１１２によって複数のグループに分類された複数の手書き数式パターンをグループ毎に表示部１９０に表示させる制御を行う。
【００２４】
２．本実施形態の手法
本実施形態の手法では、手書き数式パターンから、低レベル特徴（方向特徴）、シンボル集合特徴（シンボルの出現個数に関する特徴）、関係集合特徴（シンボル間の位置関係の出現個数に関する特徴）、位置集合特徴（シンボルの出現位置に関する特徴）のうち、方向特徴を含む少なくとも２つの特徴を抽出し、抽出した複数の特徴に基づいて、複数の手書き数式パターンを似通ったものごとに複数のグループ（クラスタ）に分類（クラスタリング）する。オンライン方式の場合は、更に、位置依存シンボル集合特徴（位置毎のシンボルの出現個数に関する特徴）と、位置依存関係集合特徴（位置毎の位置関係の出現個数に関する特徴）を抽出することができる。低レベル特徴は、シンボルの認識や抽出を行わずに得られる特徴であり、シンボル集合特徴、関係集合特徴、位置集合特徴、位置依存シンボル集合特徴、及び、位置依存関係集合特徴は、シンボルの認識や抽出を行うことで得られる特徴である。以下では、１つから最大６つまでの特徴を抽出する例について説明する。
【００２５】
２．１．低レベル特徴（方向特徴）
低レベル特徴としては、手書き数式パターン（オンラインパターン、オフラインパターン）全体をＭ×Ｎの区画に分割し、その区画の中での４方向或いは８方向の方向特徴を抽出する。このとき、位置ずれへの耐性を高めるために、各区間にガウスフィルタをかけてぼかしてもよい。
【００２６】
具体的には、まず、入力された手書き数式パターンの外接矩形を抽出する。オンラインパターンの場合は、筆点のＸ座標、Ｙ座標の最大値、最小値から抽出できる。オフラインパターンの場合は、Ｘ軸、Ｙ軸への射影の最大値、最小値から抽出できる。次に、非線形正規化を行う。非線形正規化は、手書き数式パターンにおいて、密度が疎なところは圧縮し、密なところは拡大して、パターンの２次元空間密度を一様化する処理である。
【００２７】
次に、方向特徴を抽出する。オンラインパターンの場合は、ストローク列から端点や屈曲点などの特徴点を抽出し、特徴点毎にその位置と方向（４方向、８方向、１６方向、或いは、それ以上の方向に量子化した方向）の特徴値を抽出する。オフラインパターンの場合は、次の文献に記載の方法などを用いて方向特徴を抽出する：孫 寧，安倍正人，根本義章：改良型方向線素特徴量および部分空間法を用いた高精度な手書き文字認識システム，電子情報通信学会論文誌，D-2, 78 (6), pp922-930 (1995)。図２に、外接矩形内のオフラインパターンを非線形正規化し、８方向の方向特徴を抽出する一例を示す。
【００２８】
次に、方向特徴をＭ×Ｎの区画に分割し、ガウスフィルタをかける。例えば、ガウスフィルタＧ（Ｘ，μ，σ）は、平均をμ、標準偏差をσ、Ｘ方向のマスク幅をｔとして、次式（１）で表される。
【００２９】
【数１】
2019191815.tif 000003
方向特徴など、シンボルの認識や抽出に影響されない低レベル特徴の利点は、数式認識やシンボル認識などの失敗に影響されないことである。しかし、数式の書き方の違いには影響を受ける。そこで、本実施形態の手法では、シンボルの認識や抽出を伴う特徴抽出（シンボル集合特徴、関係集合特徴、位置集合特徴の抽出）と併用する。
【００３０】
２．２．オンラインパターンからの特徴抽出
オンラインパターンの場合、数式認識エンジンにより数式を認識し、認識結果に基づいて、シンボル集合特徴、関係集合特徴、位置集合特徴を抽出する。数式認識では、シンボルの切出し、シンボルの認識、及び、構造（構文）解析を行う。
【００３１】
２．２．１．シンボル集合特徴（シンボルの出現個数に関する特徴）
シンボル集合特徴（ＢｏＳ：Bag of Symbols）は、数式認識の結果に現れるシンボル毎の出現個数を並べた特徴ベクトル（シンボル出現ベクトル）である。ここでは、シンボルの種類を１０１種類としており、シンボル出現ベクトルは、１０１次元のベクトルとなる。
【００３２】
図３に、シンボル集合特徴の一例を示す。図３には、手書き数式パターン「１／２＋２／３」の認識結果から抽出したシンボル集合特徴（シンボル出現ベクトル）が示されている。図３に示すシンボル出現ベクトル（表の２行目）は、数式中に、シンボル「１」が１個、シンボル「２」が２個、シンボル「３」が１個、シンボル「＋」が１個、シンボル「fraction bar（分数罫）」が２個出現していることを示している。シンボル集合特徴は、異なった数式であっても、出現するシンボルとその個数が同じであれば、同一の特徴ベクトルで表される。例えば、数式「１／２＋２／３」と「２／３＋１／２」は同一の特徴ベクトルで表現される。
【００３３】
なお、数式認識エンジンから複数の認識結果（認識候補）が出力される場合、第１位の認識結果（スコアが最も高い認識結果）だけでなく、第２位以降の認識結果からシンボルを計数し、それらを加算してシンボル出現ベクトルを算出してもよい。また、第１位の認識結果から計数した結果には１、第２位の認識結果から計数した結果には１／２、第３位の認識結果から計数した結果には１／４などの重みを付けて加算してもよい。また、それぞれのシンボルである確率（認識の確からしさ）を加味してもよい。
【００３４】
２．２．２．関係集合特徴（シンボル間の位置関係の出現個数に関する特徴）
関係集合特徴（ＢｏＲ：Bag of Relations）は、数式認識の結果に現れるシンボル間の位置関係毎の出現個数を並べた特徴ベクトル（関係出現ベクトル）である。ここでは、シンボル間の位置関係として、６つの位置関係（horizontal（水平）、superscript（上付き）、subscript（下付き）、upper（上方）、lower（下方）、inside（内側））を考えるが、シンボル間の位置関係はこれに限られない。この位置関係を計数するために、手書き数式パターンの認識結果から、シンボルとシンボル間の関係を表現したシンボル関係木を構築し、構築したシンボル関係木から、位置関係毎の出現回数を計測する。
【００３５】
図４に、関係集合特徴の一例を示す。図４には、手書き数式パターン「１／２＋２／３」の認識結果から構築したシンボル関係木と、シンボル関係木から得た関係集合特徴（関
係出現ベクトル）が示されている。図４に示す関係出現ベクトルは、数式中に、位置関係「horizontal」が２個、位置関係「upper」が２個、位置関係「lower」が２個出現していることを示している。関係集合特徴は、異なった数式であっても、出現する位置関係とその個数が同じであれば、同一の特徴ベクトルで表される。例えば、数式「１／２＋２／３」と「４／３−３／２」は同一の特徴ベクトルで表現される。
【００３６】
シンボル集合特徴と同様に、数式認識エンジンから複数の認識結果が出力される場合、第１位の認識結果だけでなく、第２位以降の認識結果から位置関係を計数し、それらを加算して関係出現ベクトルを算出してもよい。また、第１位の認識結果から計数した結果には１、第２位の認識結果から計数した結果には１／２、第３位の認識結果から計数した結果には１／４などの重みを付けて加算してもよい。また、それぞれのシンボルである確率を加味してもよい。
【００３７】
２．２．３．位置集合特徴（シンボルの出現位置に関する特徴）
位置集合特徴（ＢｏＰ：Bag of Positions）は、数式認識の結果に現れるシンボルの出現位置を表す特徴ベクトルである。シンボルの出現位置を求めるために、まず、認識結果から構築したシンボル関係木をＭ×Ｎの区画に分割する。各区画は、多くとも１つのシンボルを含むか、シンボルを含まない。分割数（Ｍ×Ｎ）は、シンボル関係木のサイズ、上下の関係（upper、lower、superscript、subscript）の数、左右の関係（horizontal、superscript、subscript）の数から決める。分割数は、正答の数式のシンボル関係木から求めてもよい。そして、ｉ行ｊ列の区画Ｐｉｊのうち、シンボルを含む区画には１、シンボルを含まない区画には０を与えて、行列Ｐ＝（Ｐｉｊ）で表現する。シンボル関係木のＭ×Ｎの分割数は数式ごとに異なるため、最も多い分割数に整合するために、左上に揃え、右及び下のシンボルを含まない区画には０を与える。そして、区画Ｐｉｊの要素（０又は１）を行ごとに連結し、更に列ごとに連結して特徴ベクトルとする。これにより、異なる大きさのシンボル関係木を持つ複数の数式から同じ大きさの特徴ベクトルを抽出することができる。
【００３８】
図５、図６に、位置集合特徴の例を示す。図５には、認識結果「ｘ２／２＋２／３」から構築したシンボル関係木と、Ｍ×Ｎに分割したシンボル関係木と、分割したシンボル関係木から得た位置集合特徴が示されており、図６には、認識結果「１／２＋２／３」から構築したシンボル関係木と、Ｍ×Ｎに分割したシンボル関係木と、分割したシンボル関係木から得た位置集合特徴が示されている。図５に示す例では、３つの左右の関係（２つのhorizontal、１つのsuperscript）と、３つの上下の関係（２つの縦に並列なupperとlower、１つのsuperscript）があることから、シンボル関係木を４×４の区画に分割している。図６に示す例では、２つの左右の関係（２つのhorizontal）と、２つの上下の関係（２つの縦に並列なupperとlower）があることから、シンボル関係木を３×３の区画に分割しているが、図５に示す例と比較できるように、４×４の区画において左上に揃えて、余白の区画には０を与えている。図５に示す位置集合特徴（ガウスフィルタ適用前）は、４×４の区画において、区間Ｐ１２、Ｐ２１、Ｐ２４、Ｐ３１、Ｐ３３、Ｐ３４、Ｐ４１、Ｐ４４にシンボルが現れることを示しており、図６に示す位置集合特徴（ガウスフィルタ適用前）は、４×４の区画において、区間Ｐ１１、Ｐ１３、Ｐ２１、Ｐ２２、Ｐ２３、Ｐ３１、Ｐ３３にシンボルが現れることを示している。
【００３９】
なお、位置ずれへの耐性を高めるために、各区画に図７に示す３×３のガウスフィルタをかけてもよい。この場合、隣がない区画には値を配分しない。各区間にガウスフィルタを適用した結果の要素を行ごとに連結し、更に列ごとに連結して特徴ベクトルとする。図５、図６には、ガウスフィルタ適用後の位置集合特徴が示されている。
【００４０】
位置集合特徴に、シンボル集合特徴を組み合わせて、分割したそれぞれの区画からシン
ボル集合特徴を抽出してもよい。この特徴を、位置依存シンボル集合特徴（Ｐｂ＿ＢｏＳ：Position based Bag of Symbols）と呼ぶ。位置依存シンボル集合特徴は、位置（区画）毎のシンボルの出現個数に関する特徴である。また、位置集合特徴に、関係集合特徴を組み合わせて、分割したそれぞれの区画から関係集合特徴を抽出してもよい。この特徴を、位置依存関係集合特徴（Ｐｂ＿ＢｏＲ：Position based Bag of Relations）と呼ぶ。位置依存関係集合特徴は、位置毎の位置関係の出現個数に関する特徴である。シンボル集合特徴と関係集合特徴が、数式全体から抽出するのに対して、位置依存シンボル集合特徴と位置依存関係集合特徴は、シンボル関係木を分割した各区画から抽出する。各区画に含まれるシンボルは１個、各区画に含まれる位置関係も数個になる。位置集合特徴と同様に、位置ずれへの耐性を高めるために、各区間にガウスフィルタをかけてぼかしてもよい。この結果、各区画にはシンボルが１個しか含まれなくても、ガウスフィルタのぼかしの結果、複数のシンボルで特徴値が生起する。
【００４１】
図８に、位置依存シンボル集合特徴と、位置依存関係集合特徴の一例を示す。図８には、認識結果「１／２＋２／３」から構築したシンボル関係木と、Ｍ×Ｎ（ここでは、３×３）に分割したシンボル関係木と、分割された各区画へのガウスフィルタの適用と、各区画Ｐｉｊのシンボル出現ベクトルからなる位置依存シンボル集合特徴（Ｐｂ＿ＢｏＳ）と、各区画Ｐｉｊの関係出現ベクトルからなる位置依存関係集合特徴（Ｐｂ＿ＢｏＲ）が示されている。
【００４２】
これらの特徴に加えて、認識結果の候補から特徴を抽出することもできる。これを数式候補特徴と呼ぶ。まず、手書き数式パターンから数式を認識して複数の認識候補を得る。全ての認識候補のシンボル関係木をＭ×Ｎの区画に分割する。分割数が少ない認識候補については、図６に示すように最大の分割数に合わせて左上に揃える。各区画にガウスフィルタを適用しても適用しなくてもよいが、上述した位置集合特徴、位置依存シンボル集合特徴、位置依存関係集合特徴でガウスフィルタを適用しているので、ここでは適用しない。そして、最大のＭ×Ｎの各区間に現れるシンボルのインデックスを得る。これを行ごとに連結し、更に列ごとに連結して特徴ベクトルを得る。
【００４３】
図９に、数式候補特徴の一例を示す。図９には、認識結果「ｘ２／２＋２／３」から構築してＭ×Ｎ（ここでは、４×４）に分割したシンボル関係木と、各区画のシンボルのインデックスと、それを連結して得た数式候補特徴が示されている。
【００４４】
２．３．オフラインパターンからの特徴抽出
オフラインパターンの場合、シンボルの切出し等がオンラインパターンより多少難しいことから、ここでは、数式認識を利用せずにシンボル集合特徴、関係集合特徴、位置集合特徴を抽出する方法について説明する。もちろん、数式認識を利用して特徴抽出を行うこともできる。
【００４５】
２．３．１．シンボル集合特徴（シンボルの出現個数に関する特徴）
シンボル集合特徴を抽出する場合、オフラインパターンから連結要素（背景が白画素の場合、黒画素の連結成分）を抽出し、抽出した連結要素に対してシンボル認識（単文字認識）を適用して、認識結果（上位の認識候補）とその確率値（認識スコア）を出力する。そして、シンボル毎の確率値を並べてシンボル出現ベクトル（１０１次元のベクトル）とする。オフライン方式の場合、シンボルが分離してしまうことがある。例えば、シンボル「＝」などである。これを防止するために、分離して認識されたシンボルを統合して再認識するルールを導入する。「＝」の場合は、「−」が２つ連続する場合は、「＝」として再認識し、その確率が閾値より高い場合は、それぞれの連結要素を更に連結し、「＝」に再認識する。
【００４６】
次式（２）に示すように、シンボル集合特徴Ｓは、それぞれの連結要素Ｃに対する認識結果から得たシンボル出現ベクトルＳ（Ｃ）の和をとって求める。
【００４７】
【数２】
2019191815.tif 000004
図１０に、オフラインパターンから抽出したシンボル集合特徴の一例を示す。図１０には、手書き数式パターン「＝ａ／８」の各連結要素に対する認識結果（認識スコア）から得たシンボル出現ベクトルと、これらシンボル出現ベクトルの和をとって求めたシンボル集合特徴が示されている。図１０に示すシンボル集合特徴は、数式中に、シンボル「ａ」が「０．９」個、シンボル「＝」が「０．８」個、シンボル「fraction bar（分数罫）」が「０．７」個、シンボル「８」が「０．９」個出現していることを示しており、実際のシンボルの出現個数と概ね一致している。この例では、確率値を有限個の候補で打ち切っているが、確率値以外にも順位をもとに、第１位には１、第２位には１／２、第３位には１／４などの重みをつけて加算することもできる。このとき、第１位の結果のみを用いることも可能である。
【００４８】
２．３．２．関係集合特徴（シンボル間の位置関係の出現個数に関する特徴）
関係集合特徴を抽出する場合、オフラインパターンから連結要素を抽出し、抽出した連結要素（シンボル）の周囲の領域を図１１に示すように９分割し、番号付けする。例えば、領域「０」に他の連結要素があれば（例えば、シンボル「√」の場合）、オンライン方式での位置関係「inside」が存在することになる。また、領域「１」に他の連結要素があれば位置関係「upper」が存在し、領域「５」に他の連結要素があれば位置関係「lower」が存在し、領域「２」に他の連結要素があれば位置関係「superscript」が存在し、領域「４」に他の連結要素があれば位置関係「subscript」が存在し、領域「３」或いは「７」に他の連結要素があれば位置関係「horizontal」が存在することになる。ある連結要素とその周囲の連結要素との位置関係は射影などの方法によって求める。図１２に示すように、各連結要素の外接矩形を求め、２つの外接矩形の間に遮る他の連結要素がなければ（例えば、２つの連結要素のそれぞれの外接矩形の中点を結ぶ線に、他の連結要素の外接矩形が交差しないならば）、それらは近隣する連結要素として、図１１のいずれかの位置関係を与える。例えば、図１２において、シンボル「ｘ」に相当する連結要素に近隣する連結要素は、シンボル「＝」に相当する連結要素と、シンボル「＋」に相当する連結要素と、シンボル「fraction bar」に相当する連結要素である。そして、位置関係（領域の番号）毎の出現回数（他の連結要素の個数）を並べて関係出現ベクトルとする。
【００４９】
次式（３）に示すように、関係集合特徴Ｒは、それぞれの連結要素Ｃの関係出現ベクトルＲ（Ｃ）の和をとって求める。この例では、９つのいずれかの関係にある他の連結要素の個数を関係集合特徴としているが、連結要素間の距離や連結要素の大きさを反映した特徴値としてもよい。
【００５０】
【数３】
2019191815.tif 000005
図１３に、オフラインパターンから抽出した関係集合特徴の一例を示す。図１３には、手書き数式パターン「＝ａ／８」の各連結要素の関係出現ベクトルと、これら関係出現ベクトルの和をとって求めた関係集合特徴が示されている。例えば、シンボル「a」に相当する連結要素の関係出現ベクトルは、領域「５」の位置関係にある他の連結要素が１個、領域「６」の位置関係にある他の連結要素が１個存在することを示している。また、図１
３に示す関係集合特徴は、数式中に、領域「１」、「５」の位置関係がそれぞれ２つ、領域「２」、「３」、「４」、「６」、「７」、「８」の位置関係がそれぞれ１つ出現していることを示している。
【００５１】
２．３．３．位置集合特徴（シンボルの出現位置に関する特徴）
位置集合特徴を抽出する場合、シンボルの出現位置を求めるため、オフラインパターンをＭ×Ｎに分割する。この分割数は、手書き数式内の上下の関係（図１１の領域８、１、２、６、４、５、６の関係）の数、左右の関係（図１１の領域２、３、４、８、７、６の関係）の数から決める。分割数は、正答の数式から求めてもよい。図１４に示す例では、左右の関係が、「＝」と「fraction bar」、「ｘ」と「＋」、「＋」と「１」（分子では、「＋」と「５」）の３つあり、また、等号の後に空白を入れることが多いことから横に５分割し、上下の関係が、分母と「fraction bar」、分子と「fraction bar」の２つあることから縦に３分割して、５×３の区画に分割している。
【００５２】
そして、オフラインパターンから連結要素を抽出し、それぞれの連結要素Ｃの区画Ｇへの寄与Ｐ（Ｇ，Ｃ）を次式（４）により求める。
【００５３】
【数４】
2019191815.tif 000006
それぞれの区画にガウスフィルタを適用し、次式（５）に示すように、連結要素で和をとって、連結要素の各区画への寄与を並べて特徴ベクトルとする。なお、式（５）において、Ｇｎｍ（１≦ｎ≦Ｎ，１≦ｍ≦Ｍ）は、ｎ行ｍ列の区画を示す。
【００５４】
【数５】
2019191815.tif 000007
以上述べたように、オフラインパターンから抽出する特徴は、オフラインの手書き数式パターンをシンボル関係木として認識しなくても抽出することができる。つまり、オフラインパターンから抽出する特徴は、オンラインパターンから抽出した特徴とは若干異なっている。オフラインパターン用の上記特徴は、オンラインパターンから抽出することもできる。この場合、オンラインパターンから時系列情報を除いて画像に変換し、その画像から特徴抽出を行う。
【００５５】
２．４．クラスタリング
手書き数式パターンのクラスタリングでは、まず、各手書き数式パターンのそれぞれから抽出した複数の特徴（シンボルの認識や抽出に影響されない低レベル特徴（方向特徴）、シンボルの認識や抽出を経て得られるシンボル集合特徴、関係集合特徴、位置集合特徴（或いは、位置集合特徴に代えて、位置依存集合特徴、位置依存関係集合特徴）など）に基づいて、手書き数式パターン間の距離（類似度）を求める。第１の方法（加重和法）は、各特徴間の距離の加重和をとる方法である。各特徴は違った意味や分散を持つので、それらを公平に扱うためである。加重和法による２つの手書き数式パターンＨＭＥ１、ＨＭＥ２間の距離ＤｉｓＷ（ＨＭＥ１，ＨＭＥ２）は、次式（６）により表される。
【００５６】
【数６】
2019191815.tif 000008
ここで、ｆｉは、手書き数式パターンからｉ番目の特徴ベクトルを抽出する関数であり、Ｉは、特徴の総数である。例えば、Ｉ＝４とした場合、１番目の特徴を方向特徴、２番目の特徴をシンボル集合特徴、３番目の特徴を関係集合特徴、４番目の特徴を位置集合特徴とすることができる。ｄ（ν１，ν２）は、ユークリッド距離やマハラノビス距離などの、距離関数による２つのベクトルν１とν２の距離である。αｉは、ｉ番目の特徴間の距離に与える重みであり、全ての重みの合計が１になるように、列挙法で決定する。
【００５７】
第２の方法（正規化法）は、個々の特徴間の距離をその距離の平均で割ることで正規化する方法である。正規化法による２つの手書き数式パターンＨＭＥ１、ＨＭＥ２間の距離ＤｉｓＮ（ＨＭＥ１，ＨＭＥ２）は、次式（７）により表される。
【００５８】
【数７】
2019191815.tif 000009
ここで、μｉは、任意の２つの手書き数式パターンについてそれらのｉ番目の特徴ベクトル間の距離を求め、その平均をとったものである。
【００５９】
第３の方法（正規化加重和法）は、加重和法と正規化法を統合した方法である。この方法では、加重和法で個々の特徴間の距離が大小ばらばらになることを防ぐために、ｉ番目の特徴ベクトルをその平均で除してから加重和法を適用する。正規化加重和法による２つの手書き数式パターンＨＭＥ１、ＨＭＥ２間の距離ＤｉｓＮＷ（ＨＭＥ１，ＨＭＥ２）は、次式（８）により表される。
【００６０】
【数８】
2019191815.tif 000010
これらの方法により、２つの手書き数式パターン間の距離を、クラスタリングの対象とする手書き数式パターンの全ての組み合わせについて求め、類似する手書き数式パターン毎にクラスタにクラスタリングする。クラスタリングには、Ｋ−ｍｅａｎｓ法、階層化クラスタリング、ＤＢＳＣＡＮなどの方法が利用できる。以上の手法により、複数の手書き数式パターンを似通ったものごとに精度良くまとめることができ、採点者の採点誤りや採点のばらつきを低減して採点の効率を高めることができる。
【００６１】
なお、全ての解答（手書き数式パターン）をクラスタリングして手動採点（採点者による採点）に回すようにしてもよいし、全ての解答を数式認識エンジンにより認識し、認識結果が信頼できるか否かを判定し、信頼できると判定された認識結果については自動採点（認識結果が正答であるか誤答であるかを判定）し、信頼できないと判定された認識結果については当該認識結果に対応する解答をクラスタリングして手動採点に回すようしてもよい。また、全ての解答をクラスタリングし、クラスタごとに全ての解答を数式認識エンジンにより認識し、正答が１つでも（或いは、一定比率以上）含まれるクラスタについて
は当該クラスタに含まれる解答を手動採点に回し、正答が１つも（或いは、一定比率未満しか）含まれず、正答を含むクラスタとの距離が一定値以上のクラスタについては当該クラスタに含まれる解答を誤答として判定するようにしてもよい。なお、クラスタ間の距離は、クラスタのセントロイドを求め、セントロイド間の重み付きユークリッド距離を使うことで簡単に計算できる。
【００６２】
３．評価実験
本実施形態のクラスタリング手法を評価する実験を行った。クラスタリングの評価指標として、次式（９）に示すＰｕｒｉｔｙ（各クラスタに含まれる本来同じクラスに属する要素数を全クラスタに渡って加えた総和を、全要素数で除した値）を用いた。クラスタごとに採点することを考えると、一つ一つのクラスタに違いものが少ない（すなわち、Ｐｕｒｉｔｙが１に近い）方が良い。
【００６３】
【数９】
2019191815.tif 000011
ここで、Ｗ＝{Ｗ１，Ｗ２，…，ＷＫ}は、クラスタの集合であり、Ｃ＝{Ｃ１，Ｃ２，…，ＣＪ}は、クラスの集合であり、Ｋは、クラスタの数であり、Ｊは、クラスの数であり、Ｎは、全要素数である。
【００６４】
３．１．オンライン方式についての実験
本実験においては、２１名の被験者に、それぞれ５０種類の数式を３つのインターフェース（ガイドラインなし、枠の中央に水平なガイドラインあり、枠の上端、中央、下端のそれぞれに水平なガイドラインあり）で筆記してもらったオンライン手書き数式パターン（合計３，１５０のパターンが５０のクラスに属する）を収集した。パターンに出現するシンボルの種類は１０１種類である。収集したデータセットをＤｓｅｔ＿５０と呼ぶ。
【００６５】
クラスタリング手法としては、ユークリッド距離に基づくｋ−ｍｅａｎｓ法を基本とするが、ｋ−ｍｅａｎｓ法はセントロイドの初期値に依存し、極小解に陥り易いので、ｋ−ｍｅａｎｓ法（初期セントロイドはランダムに初期化する）と、ｋ−ｍｅａｎｓ＋＋法（初期セントロイドをなるべく分散させる。方法は次の文献による：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.）と、理想法（初期セントロイドを正しいクラスの中から選ぶ）の３通りの初期化手法を試みた。理想法は現実には利用できないが、クラスタリングの上限を求めることができる。
【００６６】
本実験では、クラスタの数はクラスの数とし、評価指標として式（９）に示すＰｕｒｉｔｙを用いた。クラスタリングに利用する特徴として、上述した個々の特徴とそれらの統合を評価した。特徴の統合では重み（αｉ）の学習が必要なため、データベースを５つに分け、４つ（学習セット）で学習し、残り１つ（テストパターン）で評価することを、役割を変えて５回実験し、結果の平均値を求めた（５重クロスバリデーション）。表１に、個々の特徴の全てとそれらの統合に対するクラスタリング性能の評価結果を示す。
【００６７】
【表１】
2019191815.tif 000012
個々の特徴では、方向特徴（実験番号１）は安定している。特に、ランダムに初期化するｋ−ｍｅａｎｓ法で性能が一番高い。シンボル集合特徴（実験番号２）は、僅差ではあるが、ｋ−ｍｅａｎｓ＋＋法と理想法で最良の性能を示した。関係集合特徴（実験番号３２）、位置集合特徴（実験番号４）、位置依存シンボル集合特徴（実験番号５）、位置依存関係集合特徴（実験番号６）、数式候補特徴（実験番号７）は、単独では高い性能を示さなかった。なお、数式認識特徴では、認識候補のうち第１位の候補から抽出した特徴を用いた。
【００６８】
特徴の統合（加重和法、正規化法、正規化加重和法）の実験では、個々の特徴よりも高い性能を示し、特に、加重和法が優れていた。まず、低レベル特徴である方向特徴と、数式認識を適用して得られる特徴であるシンボル集合特徴、関係集合特徴、位置集合特徴の統合が効果的であることが分かった（実験番号８、９に対して実験番号１０以降）。次に、位置集合特徴の代わりに、位置依存シンボル集合特徴、位置依存関係集合特徴を統合する実験では、クラスタリング手法の違いによって優劣が異なる結果となるが、同様に効果的であることが分かった（実験番号１０に対して実験番号１１）。更に、数式候補特徴を
追加すると、若干性能が低下し（実験番号１１に対して実験番号１２）、また、方向特徴と数式候補特徴を統合した場合では、更に性能が低下した（実験番号１３）。このことから、シンボル集合特徴、関係集合特徴、位置集合特徴の３つの統合が数式候補特徴より優れている可能性が高い。また、方向特徴とシンボル集合特徴、関係集合特徴に、更に、位置集合特徴と位置依存シンボル集合特徴、位置依存関係集合特徴を統合する実験（実験番号１４）では、位置集合特徴、或いは、位置依存シンボル集合特徴、位置依存関係集合特徴のどちらか１つの統合で効果を示すが、両方の統合（位置集合特徴と位置依存シンボル集合特徴の統合、位置集合特徴と位置依存関係集合特徴の統合）は効果的でないことが分かった。
【００６９】
特徴の統合が効果的であることは確認できたが、一方で、抽出する特徴の数が多くなるほど計算量は大きくなる。そこで、計算量が限られる場合に、低レベル特徴である方向特徴と、シンボルの認識や抽出を経て得られるシンボル集合特徴、関係集合特徴、位置集合特徴のいずれか１つとを統合する方法も考えられる。この場合の評価結果を表２に示す。
【００７０】
【表２】
2019191815.tif 000013
シンボル集合特徴、関係集合特徴、位置集合特徴のいずれか１つよりも、これらに方向特徴を統合した方が効果的であること、及び、方向特徴単独よりも、方向特徴とシンボル集合特徴とを統合した場合が優位であることが分かった。
【００７１】
３．２．オフライン方式についての実験
本実験においては、２３名の被験者に、それぞれ２３問の問題に対する正しい解答と２つのパターンの誤った解答を指定して筆記してもらったオフライン手書き数式パターン（合計１，５１８パターン）を収集した。収集したデータセットをＤｓｅｔ＿２２Ｑｓと呼ぶ。本実験では、問題ごとに特徴抽出を行い、クラスタリングの実験を行った。従って、問題ごとに正答のクラスが１つと誤答のクラスが２つあることになる。評価結果は２２問の解答に対するクラスタリング性能の平均で示す。この場合、クラス数は３である。Ｄｓｅｔ＿２２Ｑｓに加えて、Ｄｓｅｔ＿５０をオフライン化（時系列の筆点間を直線で結び、一定の太さで肉付け）したものも利用した。この場合のクラス数は５０である。
【００７２】
まず、特徴ごとのクラスタリング性能を評価した。クラスタリング手法として、ｋ−ｍｅａｎｓ＋＋を用いた。式（９）におけるパラメータｋの値をクラス数に設定した。つまり、Ｄｓｅｔ＿２２Ｑｓではｋ＝３、Ｄｓｅｔ＿５０ではｋ＝５０とした。Ｄｓｅｔ＿２２Ｑｓは、問題ごとに実験しており、それぞれにＰｕｒｉｔｙが求まるため、それらの平均と標準偏差を求めた。一方、Ｄｓｅｔ＿５０は、ひとまとめに実験しているので、データ全体に対するＰｕｒｉｔｙが求まる。表３に、個々の特徴に対するクラスタリング性能の評価結果を示す。
【００７３】
【表３】
2019191815.tif 000014
個々の特徴では、シンボル集合特徴（実験番号２）が最も高い性能を示した。一方、方向特徴（実験番号１）、関係集合特徴（実験番号３）、位置集合特徴（実験番号４、５）はシンボル集合特徴に及ばなかった。
【００７４】
次に、特徴を統合した場合のクラスタリング性能を評価した。加重和法と正規化加重和法は、最適な重みを設定する必要があるため、５重のクロスバリデーションを行った。但し、Ｄｓｅｔ＿２２Ｑｓでは問題ごとにクラスタリングするため、問題ごとのデータ数が少なく、また、重みの最適値が異なることから、クロスバリデーションには適さない。そこで、Ｄｓｅｔ＿２２Ｑｓについては加重和法と正規化加重和法の実験は行わなかった。表４に、特徴の統合に対するクラスタリング性能の評価結果を示す。
【００７５】
【表４】
2019191815.tif 000015
加重和法で統合した場合（実験番号６〜９）は、シンボル集合特徴と統合することで、関係集合特徴や位置集合特徴の単独の場合よりも性能は向上したが、シンボル集合特徴単独からの性能向上は見られなかった。正規化法の場合は、統合の効果は見られなかった。
正規化加重和では、若干ではあるが、シンボル集合特徴単独より高い性能が見られた。
【００７６】
オンラインの方式の場合と同様に、計算量が限られる場合に、低レベル特徴である方向特徴と、シンボルの認識や抽出を経て得られるシンボル集合特徴、関係集合特徴、位置集合特徴のいずれか１つとを統合する方法も考えられる。この場合の評価結果を表５に示す。
【００７７】
【表５】
2019191815.tif 000016
オンライン方式の場合と同様に、シンボル集合特徴、関係集合特徴、位置集合特徴のいずれか１つよりも、これらに方向特徴を統合した方が効果的であること、及び、方向特徴単独よりも、方向特徴とシンボル集合特徴とを統合した場合が優位であることが分かった。また、方向特徴とシンボル集合特徴とを統合した場合、表４の実験番号１１に迫る性能となることが分かった。
【００７８】
オフライン方式では、シンボルの抽出に連結要素に基づく抽出を採用しているために、オンライン方式ほどの性能が出ていない可能性がある。最近の手法である深層ニューラルネットワークによるシンボルや関係、位置の抽出を行うことで、個々の性能が上がり、特徴を統合する効果がオンライン方式に近づくことが期待できる。その場合、オフライン方式にも本発明が一層効果を発揮することが期待できる。
【００７９】
なお、本発明は、上述の実施の形態に限定されるものではなく、種々の変更が可能である。本発明は、実施の形態で説明した構成と実質的に同一の構成（例えば、機能、方法及び結果が同一の構成、あるいは目的及び効果が同一の構成）を含む。また、本発明は、実施の形態で説明した構成の本質的でない部分を置き換えた構成を含む。また、本発明は、実施の形態で説明した構成と同一の作用効果を奏する構成又は同一の目的を達成することができる構成を含む。また、本発明は、実施の形態で説明した構成に公知技術を付加した構成を含む。
【符号の説明】
【００８０】
１００…処理部、１１０…特徴抽出部、１１２…分類部、１２０…表示制御部、１６０…入力部、１７０…記憶部、１９０…表示部
【図１】
2019191815.tif 000017
【図２】
2019191815.tif 000018
【図３】
2019191815.tif 000019
【図４】
2019191815.tif 000020
【図５】
2019191815.tif 000021
【図６】
2019191815.tif 000022
【図７】
2019191815.tif 000023
【図８】
2019191815.tif 000024
【図９】
2019191815.tif 000025
【図１０】
2019191815.tif 000026
【図１１】
2019191815.tif 000027
【図１２】
2019191815.tif 000028
【図１３】
2019191815.tif 000029
【図１４】
2019191815.tif 000030