检索设备和检索方法

摘要

根据实施例，提供一种检索设备和检索方法。设备包括获取部、分割部、提取部、计算部和检索部。获取部被配置成获取多个第一点序列。分割部被配置成将多个第一点序列的每一个分割成多个第二点序列。提取部被配置成提取多个第二点序列中的每一个的特征向量。计算部被配置成基于多个第二点序列之间的最佳路径，计算多个第一点序列之间的距离，多个第二点序列属于多个第一点序列中的每一个。检索部被配置成使用距离来检索与多个第一点序列相对应的数据。

权利要求

1.一种检索设备，其特征在于，所述设备包含：获取部，所述获取部被配置成获取多个第一点序列；

分割部，所述分割部被配置成将所述多个第一点序列中的每一个分割成多个第二点序列；

提取部，所述提取部被配置成提取所述多个第二点序列中的每一个的特征向量；

计算部，所述计算部被配置成基于所述多个第二点序列之中的最佳路径，来计算所述多个第一点序列之间的距离，所述多个第二点序列属于所述多个第一点序列中的每一个，和检索部，所述检索部被配置成使用所述距离来检索与所述多个第一点序列相对应的数据。

2.如权利要求1所述的检索设备，其特征在于，所述分割部被配置成将所述多个第一点序列中的每一个分割成所述多个第二点序列，以使所述多个第二点序列中的每一个的曲率变成等于或小于阈值。

3.如权利要求1所述的检索设备，其特征在于，所述分割部被配置成将所述多个第一点序列中的每一个分割成所述多个第二点序列，以使所述多个第二点序列中的每一个的长度变成等于或小于阈值。

4.如权利要求1所述的检索设备，其特征在于，所述分割部被配置成将所述多个第一点序列中的每一个分割成所述多个第二点序列，以使所述多个第二点序列的数目变成第一数目。

5.如权利要求1所述的检索设备，其特征在于，进一步包含显示控制器，所述显示控制器被配置成在显示单元上显示检索的数据。

6.如权利要求5所述的检索设备，其特征在于，所述多个第一点序列构成由用户手写的字符串的笔划组，所述多个第二点序列中的每一个与所述笔划组的笔划的副笔划相对应，所述数据是指示字符串的字符串数据，所述获取部被配置成通过顺序地获取构成所述笔划组的笔划，来获取所述笔划组，所述分割部被配置成将构成所述笔划组的每个所述笔划分割成多个副笔划，所述计算部被配置成基于属于构成所述笔划组的每个所述笔划的所述副笔划之间的最佳路径，来计算构成所述笔划组的所述笔划之间的距离，所述检索部被配置成使用所述距离，来检索与所述笔划组相对应的所述字符串数据，并且所述显示控制器被配置成在所述显示单元上显示检索的所述字符串数据。

7.如权利要求1所述的检索设备，其特征在于，所述获取部被配置成获取由用户指定的所述多个第一点序列。

8.一种检索方法，其特征在于，包含：

获取多个第一点序列；

将所述多个第一点序列中的每一个分割成多个第二点序列；

提取所述多个第二点序列中的每一个的特征向量；

基于属于所述第一点序列中的每一个的所述多个第二点序列之间的最佳路径，来计算所述多个第一点序列之间的距离；并且使用所述距离来检索与所述多个第一点序列相对应的数据。

说明书

检索设备和检索方法

[0001] 相关申请的交叉引用

[0002] 本申请是基于并且要求2013年5月31日提交的第2013-116419号日本专利申请的优先权；其全部内容通过引用而结合在本文中。

技术领域

[0003] 这里所述的实施例一般与检索设备和检索方法有关。

背景技术

[0004] 已知一种从数据库检索与由点序列组成的查询相匹配或类似的数据的技术。

发明内容

[0005] 实施例的目的在于提供一种检索设备，该检索设备能够在提高检索精确度的同时抑制检索速度的减少。

[0006] 根据实施例，设备包括获取部、分割部、提取部、计算部和检索部。获取部被配置成获取多个第一点序列。分割部被配置成将多个第一点序列的每一个分割成多个第二点序
列。提取部被配置成提取多个第二点序列中的每一个的特征向量。计算部被配置成基于多
个第二点序列之间的最佳路径来计算多个第一点序列之间的距离，该多个第二点序列属于
多个第一点序列中的每一个。检索部被配置成使用距离来检索与多个第一点序列相对应的
数据。

[0007] 根据如上所述的设备，检索速度的减少能够被抑制并且检索精确度能够被提高。

附图说明

[0008] 图1是图解实施例的典型检索设备的配置图；

[0009] 图2是图解实施例中的笔划的实例的图；

[0010] 图3是图解实施例中的笔划的实例的图；

[0011] 图4是图解实施例中的墨水数据（ink data）的数据结构的实例的图；

[0012] 图5是图解表示实施例中的副笔划的数据的数据结构的实例的图；

[0013] 图6是图解实施例中的DP匹配的实例的图；

[0014] 图7是图解实施例的检索实例的图；

[0015] 图8是图解实施例的显示实例的图；

[0016] 图9是图解实施例的处理实例的流程图；

[0017] 图10是图解实施例的检索设备的典型硬件配置的图；

[0018] 图11是图解实施例的检索设备的实例的图。

具体实施方式

[0019] 下面参照附图将给出实施例的详细描述。

[0020] 在实施例中，将给出以下情况的描述：由用户手写的手写字符串被用作从预先书写的（例如，大量的）手写文档进行检索的查询。这里，在实施例中，主要地，例如，将给出字符串的描述。但是，查询可以是自由手写的，由用户绘画的诸如线或者标记的字符码没有被
分割给自由手写。任何方法可以被用作用于通过用户指定手写字符串的方法。例如，用户可
以实际上手写字符串以指定查询。用户可以从现存的手写文档选择要被用作查询的部分。
用户可以从用于查询的模板中选择要被用作查询的部分。可以使用这些方法的结合。

[0021] 图1是图解实施例的典型检索设备10的配置图。如图1所示，检索设备10包括输入单元11、获取单元13、墨水数据存储单元15、分割单元17、提取单元19、特征向量存储单元
21、计算部23、检索单元25、显示控制单元27和显示单元29。

[0022] 输入单元11能够通过例如输入装置来实现，输入装置允许手写输入，输入装置诸如是触摸屏、触摸板、电子笔或者计算机鼠标。获取单元13、分割单元17、提取单元19、计算
部23、检索单元25和显示控制单元27可以通过例如由诸如中央处理单元（CPU）的处理单元
执行程序来实现，即，通过软件来实现，或者可以通过诸如集成电路（IC）的硬件来实现。换
句话说，这些单元可以通过结合软件和硬件来实现。墨水数据存储单元15和特征向量存储
单元21可以通过例如存储装置来实现，该存储装置允许磁的、光的或电的存储，例如可以是
硬盘驱动器（HDD）、固态驱动器（SSD）、存储卡、光盘或者随机存取存储器（RAM）。显示单元29可以通过例如诸如触摸显示器和液晶显示器的显示装置来实现。

[0023] 输入单元11将多个第一点序列输入到检索设备10。在实施例中，输入单元11将多个笔划（多个第一点序列的一个实例）输入到检索设备10，笔划是用户以字符和类似的内容
为意图而手写（绘画）或指定的。但是，不应该以限定意义来解释。在实施例中，输入单元11
是触摸屏。假定用户使用用于在触摸屏上手写的记录笔或者手指，以便输入多个笔划。但
是，不应该以限定意义来解释。输入单元11可以通过例如触摸板、电子笔或者计算机鼠标来
实现。

[0024] 笔划意思是通过用户手写的一个笔划，即，从记录笔或者手指与触摸屏的输入表面开始接触的时间直到记录笔或者手指举起离开输入表面（从笔向下状态直到笔向上状
态）的轨迹。例如，表示笔划的数据包括在记录笔或者手指相对于触摸屏的输入表面的轨迹
上的采样点（时间序列坐标值）、轨迹的外接矩形和轨迹的笔压力。

[0025] 具体地，当记录笔或者手指相对于触摸屏的输入表面变成笔向下状态时，触摸屏对记录笔或者手指相对于输入表面的轨迹上点、轨迹的笔压力和从开始输入轨迹的时间所
经过的时间进行周期性采样。当记录笔或者手指变成笔向上状态时，触摸屏提取轨迹的外
接矩形，以便生成表示笔划的数据，并且将该数据输入到检索设备10。

[0026] 图2和图3是图解实施例中的笔划的实例的图。在图2所示的实例中，图解笔划的采样点。在图3所示的实例中，图解在图2中所示的采样点按时间顺序经过线性插值的笔划。在
图2和图3所示的实例中，周期性地执行采样（以固定周期）。但是，由于用户的书写速度而改
变了采样点之间的坐标距离。这里，笔划中的采样点的数目对于每个笔划是不同的。

[0027] 获取单元13获取多个第一点序列。在实施例中，获取单元13从输入单元11顺序地获取笔划输入，以便获取多个笔划。当笔划的获得完成时，即，当从输入单元11完成笔划的
输入时，获取单元13将墨水数据存储在墨水数据存储单元15中，该墨水数据为表示获取的
笔划的一组数据。这里，从输入单元11输入笔划的完成包括用户结束书写手写字符串的情
况，进行手写字符串的保存操作的情况，以及类似的情况。即，墨水数据起到表示对于每个
页面（文档）的笔划组的数据。

[0028] 在获取单元13将多个笔划组存储在墨水数据存储单元15中的情况下，墨水数据能够与页面（文档）ID相关联，以便识别个别笔划组。换句话说，获取单元13能够使表示笔划的
数据与笔划ID相关联，以便识别个别笔划。

[0029] 图4是图解实施例中的墨水数据的数据结构的实例的图，并且图解通过获取单元13在墨水数据存储单元15中存储的墨水数据的数据结构。在实施例中，墨水数据通过三层
数据结构被表示，该三层数据结构包括墨水数据结构，笔划结构和点结构。但是，不应该以
限定意义来解释。

[0030] 墨水数据结构是包括构成笔划组的笔划的总数和构成笔划组的各个笔划的笔划结构的结构。笔划结构是包括以下的结构：构成笔划的采样点的总数、开始输入笔划的开始
时间（笔向下状态开始的时间）、笔划的外接矩形、和构成笔划的各个采样点的点结构。在实
施例中，笔划的外接矩形具有包含笔划的最小面积的矩形形状。但是，不应该以限定意义来
解释。点结构是包括x坐标、y坐标、笔压力和距离采样点的开始时间的时间差的结构。这里，
包括x坐标和y坐标的坐标系统能够是这样的坐标系统，原点在触摸屏的输入表面上的左上
角（角度），x坐标的值朝着触摸屏的右侧变得更大，并且y坐标的值朝着触摸屏的下侧变得
更大。

[0031] 在触摸屏不能对笔压力进行采样的情况下，或者在笔压力不被用于随后的处理的情况下，点结构中的压力可以被省略或者指示无效的值可以被设定成点结构中的笔压力。
在触摸屏不能对诸如开始时间和距离开始时间的时间差的时间进行采样的情况下，或者在
时间不被用于随后的处理的情况下，指示点结构的次序可以被设定成点结构中的时间差，
点结构中的时间差可以被省略，或者指示无效的值可以被设定成点结构中的时间差。

[0032] 在笔划结构的每个项目中，可以书写实际数据。为了分别管理来自彼此的墨水数据结构的数据和笔划结构的数据，对应笔划结构的链接信息可以被写入墨水数据结构中的
笔划结构的区域中。类似地，在点结构的每个项目中，可以书写实际数据。为了分别管理来
自彼此的笔划结构的数据和点结构的数据，对应点结构的链接信息可以被写入笔划结构中
的点结构的区域中。

[0033] 分割单元17将通过获取单元13获取的多个第一点序列中的每一个分割成多个第二点序列。在实施例中，分割单元17将构成笔划组（多个笔划）的每个笔划分割成多个副笔
划，笔划组由存储在墨水数据存储单元15中的墨水数据指示。分割单元17将表示各个副笔
划的数据和指示哪个数据表示这个数据所属于的笔划的链接信息添加到墨水数据存储单
元15中存储的墨水数据。

[0034] 图5是图解表示实施例中的副笔划的数据的数据结构的实例的图，并且图解通过分割单元17添加到墨水数据存储单元15中的数据的数据结构。在实施例中，表示副笔划的
数据通过两层数据结构被表示，两层数据结构包括副笔划结构和点结构。但是，不应该以限
定意义来解释。

[0035] 副笔划结构是包括以下的结构：构成副笔划的采样点的总数、开始输入副笔划的开始时间、对于副笔划所属于的笔划的笔划结构的指针、副笔划的外接矩形、和构成副笔划
的各个采样点的点结构。

[0036] 分割单元17将笔划分割成多个副笔划，因此例如多个副笔划的各个曲率变成等于或小于阈值。这里，笔划的曲率可以在每个采样点被计算。但是，采样点的数目依赖于笔划
的尺寸和采样率而改变。因此，在这样的情形下，允许计算曲率的点对于每个笔划改变。

[0037] 因此，分割单元17通过固定数量的采样点来近似笔划，并且进行重新采样，以便确保采样点之间的恒定距离。分割单元17例如通过线性插值计算重新采样点的坐标值，以便
确保采样点之间的恒定距离。在这种情况下，在分割单元17减少重新采样点的数目时，笔划
被近似成直线。

[0038] 例如，在作为分割目标的笔划S中从重新采样点Sbase到重新采样点Si的曲率CS（base，i）由方程式（1）来表示。

[0039]

[0040] 这里，dist（Sj，Sj+1）表示采样点Sj到采样点Sj+1的距离。在曲率CS（base，i）的值变得更接近于1时，笔划S变成直线。在曲率C（S base，i）的值变得更接近于0时，笔划S变成曲线。

[0041] 分割单元17对于每个重新采样的笔划，从开始点顺序地计算曲率，并且就在具有等于或小于阈值的曲率的采样点之前，将笔划分割成副笔划。然后，分割单元17执行类似的
处理直到结束点。

[0042] 用于分割笔划的方法不局限于这种。分割单元17将笔划分割成多个副笔划，因此例如多个副笔划的各个长度变成等于或小于阈值。换句话说，分割单元17可以将笔划分割
成多个副笔划，从而多个副笔划的数目变成预定数目。

[0043] 假如在获取单元13完成笔划组的获取之后，分割单元17分割各个笔划，已经描述了实施例。但是，可以同时处理通过获取单元13获取笔划和通过分割单元17来分割笔划。

[0044] 提取单元19提取通过分割单元17分割的多个第二点序列的各个特征向量。在实施例中，提取单元19从这些副笔划中提取多个副笔划的各个独特的特征向量。

[0045] 这里，分割单元17对笔划重新采样。因此，每个笔划在点结构中具有相同的数目。但是，由于副笔划中的点结构的数目依赖于分割笔划的方法，因此所有副笔划在点结构中
未必具有相同的数目。

[0046] 因此，提取单元19通过用于重新采样的采样点的固定数目来近似副笔划。例如，提取单元19以固定数目（例如，N=128）的采样点以恒定间隔对副笔划长度重新采样，并且基于
原始副笔划的采样点的接近处的两个点来进行线性插值，以便计算重新采样点的坐标值。

[0047] 提取单元19使用以下方法计算表示副笔划的独特的特征向量。但是，提取特征向量的方法不局限于这种。

[0048] 首先，提取单元19设定正方形副笔划区域，该正方形副笔划区域在一侧的长度为关于重新采样的副笔划的副笔划的外接矩形的长边。此时，提取单元19设定副笔划区域，因
此该笔划的外接矩形的中心被定位在副笔划的中心。这里，副笔划区域的中心例如为副笔
划区域中的多个点的坐标的平均位置。

[0049] 接下来，提取单元19使用方程式（2）以使重新采样的副笔划的两个采样点之间的向量的角度（方向）量子化，并且计算用于选举直方图（voting histogram）的直方（bin）。这里，副笔划的书写方向具有意义。因此，角度的值的范围被设定成从-π到π。

[0050]

[0051] 这里，devx和devy表示与副笔划的不同值相对应的两个采样点之间的向量分量，“direction”表示方向上的量子化的数目。

[0052] 不是从整个副笔划区域计算方向直方图，而是从通过将副笔划区域分成块而获得的每个块区域来计算方向直方图的，并且各个方向直方图被结合在一起。这就提高了特征
向量的表达。因此，在实施例中，提取单元19将副笔划区域分成块。由于副笔划可以是不具
有固定纵横比并且平行于x轴或者y轴的直线，因此分成块以便保存如方程式（3）和方程式
（4）所表示的纵横比。

[0053]

[0054]

[0055] 这里，xi和yi表示第i个重新采样点的各个坐标值，xmin和ymin表示副笔划中的各个最小坐标值，lengthx和lengthy表示坐标系中的值的范围的各个尺寸，并且split表示分割
次数。

[0056] 即，提取单元19计算每个采样点所属于的块区域，并且使用每个块区域中的方程式（2）计算用于选举直方图的直方。

[0057] 例如，在块区域中，假定x轴线方向上的量子化值为x，y轴线方向上的量子化值为y，方向分量的量子化值为d，并且选举目的地的直方为bin（x，y，d）。提取单元19进行选举，例如bin（x，y，d）=9，bin（x，y，d'）=6，bin（x'，y，d）=4，bin（x'，y，d'）=3，bin（x，y'，d）=4，bin（x，y'，d'）=3，bin（x'，y'，d）=3，和bin（x'，y'，d'）=2。

[0058] 这里，x’、y’和d’表示各个最近的量子化值。

[0059] 这里，当从副笔划提取特征时，方向被量子化（quantizaed）。由于即使书写的稍微模糊，从而可以改变量子化目的地。因此，以权重来选举与目标直方具有邻接关系的直方。
这就允许逆着书写抖动的坚固特征提取。例如，在八个方向上的量子化的情况下，提取单元
19预先执行16个方向上的量子化，然后利用如方程式（5）所表示的高斯滤波器在八个方向
上来进行平滑。

[0060]

[0061] 这里，di表示要被计算的“i”方向上的频率，di’表示以加倍的解量子化的频率。在i=0的情况下，由于方向具有周期性，因此使用如方程式（6）所表示的高斯滤波器来执行平
滑。在这种情况下，初步量子化的数目可以为“2direction”。

[0062]

[0063] 不仅在方向上进行平滑处理，而且在块区域之间进行平滑处理，以便逆着书写抖动来进行坚固特征提取。在这种情况下，与方向不同，在块区域之间不具有周期性。因此，提
取单元19将副笔划区域分成（2split+1）x（2split+1），于是使具有如方程式（7）所表示的高斯滤波器的每个split x split区域平滑化。

[0064]

[0065] 这里，coord（x，y）表示提取目标区域的直方图，coord’（x，y）表示区域被分成预先计算的（2split+1）x（2split+1）的直方图，并且|W|表示高斯滤波器。

[0066] 如上所述，提取单元19最后提取split x split方向的尺寸上的特征向量。提取单元19将提取的多个副笔划的各个特征向量和相关联的信息存储在特征向量存储单元21中。
关联信息使副笔划的特征向量与该副笔划所属于的笔划相关联。

[0067] 例如，在获取单元13将笔划ID分配给笔划的情况下，该笔划ID能够被用作关联信息。例如，对于副笔划所属于的笔划的笔划结构的链接信息能够被用作关联信息。墨水数据
存储单元15和特征向量存储单元21可以被集成为一个数据库，并且特征向量可以在副笔划
结构内被书写。

[0068] 假如在分割单元17完成笔划组的分割之后，提取单元19提取副笔划的各个特征向量，已经描述了实施例。但是，可以同时处理通过获取单元13的笔划的获取，通过分割单元
17的笔划的分割，并且通过提取单元19的副笔划的特征向量的提取。

[0069] 计算部23基于多个第二点序列之间的最佳路径来计算多个第一点序列之间的距离，该多个第二点序列属于多个第一点序列中的每一个。在实施例中，计算部23基于属于每
个笔划组（多个笔划）的多个各个副笔划之间的最佳路径来计算构成笔划组的笔划之间的
距离。

[0070] 具体地，计算部23通过基于这些笔划所属于的多个副笔划的各个特征向量，使用距离进行动态规划（DP）匹配（在广义上的弹性匹配）以便获得最佳组合（最佳路径），并且通过获得这种最佳组合的平均距离，来获得笔划之间的距离。

[0071] 即，计算部23使用通过提取单元19提取的副笔划的特征向量来计算笔划之间的距离。在实施例中，通过使用DP匹配对于每个单元的副笔划执行匹配计算笔划之间的距离。通
过副笔划的各个特征向量之间的距离指定副笔划之间的距离。因此，仅需要使用与特征向
量相对应的最佳度量（Metric）。例如，副笔划之间的距离可以为L2标准或者L1标准（norm），或者可以是通过使用例如正规化相关系数从值1减去计算的向量之间的可能性而获得的值
（由距离准则统一）。

[0072] 这里，如果在所有副笔划上执行DP匹配，则计算量增加。例如，假如笔划的平均分割比为R，R关于检索目标的笔划组（具有笔划数N）和要被查询的笔划组（笔划数M），则副笔
划的数目变成高于每个笔划的R倍。因此，搜索范围从N x M增加到NR x MR。这里，要被查询
的笔划组为通过用户手写或者指定的笔划组并且对应于通过获取单元13获得的笔划组。

[0073] 因此，在实施例中，计算部23执行两个阶段的DP匹配以便减少与笔划的分割相关联的搜索范围的增加。具体地，计算部23首先执行笔划之间的第一阶段DP匹配，然后执行副
笔划序列之间的第二阶段DP匹配，副笔划序列属于通过第一阶段的DP匹配而匹配的每个笔
划。

[0074] 因此，在第一阶段DP匹配中，根据用于笔划的笔划数执行搜索。这就将搜索范围减少到N x M（参见图6）。

[0075] 例如，假定通过以“i”笔划分割笔划xp形成的副笔划序列为xp’，通过以“j”笔划分割笔划yp形成的副笔划序列为yp’，副笔划序列xp’的笔划数为Ip’笔划，副笔划序列yp’的笔划数为Jp’笔划。在这种情况下，根据副笔划序列xp’和副笔划序列yp’之间的距离d（xp’，yp’）计算笔划xp和笔划yp之间的距离d（xp，yp）。这里，根据以副笔划为单位的DP匹配（第二阶段DP匹配）的路径的总成本g’（Ip’，Jp’）计算副笔划序列之间的距离d（xp’，yp’）。即，满足d（xp，yp）=d（xp’，yp’）=g’（Ip’，Jp’）。

[0076] 这里，使用方程式（8）到方程式（11）的递推方程能够计算g’（Ip’，Jp’）（参见图6）。

[0077] g(0,0)=0  (9)

[0078] g(i’,0)=∞(i’=1,...,Ip’)  (10)

[0079] g(0,j’)=∞(j’=1,...,Jp’)  (11)

[0080] 这里，g’（i’，j’）为直到（i’，j’）的最佳路径的累计成本，d（x’i’-k，i’，y’j’-l，j’）为当从x’的第（i’-k）个要素到第i’个要素的副笔划序列x’i’-k，…，x’i匹配从y’的第（j’-k）个要素到第j’个要素的副笔划序列y’j’-l，…，y’j时的成本（局部距离）。

[0081] 检索单元25使用通过计算部23计算的距离，来检索与多个第一点序列相对应的数据。在实施例中，检索单元25使用通过计算部23计算的距离来检索与通过获取单元13获取
的笔划组相对应的字符串数据。即，检索单元25使用获取单元13获取的笔划组作为查询，并
且使用构成笔划组的笔划之间的距离来检索通过计算部23计算的字符串数据。具体地，检
索单元25通过副笔划之间的DP匹配获得各个副笔划之中的最佳对应，并且使用各个对应的
副笔划之间特征向量的平均距离来进行DP匹配作为笔划之间的原始距离。即，在笔划内以
及笔划之间的两个阶段执行DP匹配。

[0082] 检索单元25的检索目标，即，存储字符串数据的数据库可以被设置在检索设备10中，或者可以被设置在外部（例如，在内部网、因特网上，或者外部联结到检索设备10的存储
介质）。另外，较佳的是，上述特征向量与检索目标的字符串数据相关联。

[0083] 例如，检索单元25进行笔划匹配，从而通过计算部23计算的两个笔划序列之间的距离的总和变成最小值。具体地，检索单元25使用方程式（12）到方程式（14）的递推方程利
用DP匹配执行路径搜索处理（参见图7）。

[0084]

[0085] g(i,0)=∞(i=0,...,I)  (13)

[0086] g(0,j)=∞(j=1,...,J)  (14)

[0087] 这里，g（i，j）为直到（i，j）的最佳路径的累计成本，d（xi-k，i，yj-l，j）为当具有从笔划x的第（i-k）个要素到第i个要素的“k”笔划的笔划序列xp匹配具有从笔划y的第（j-k）个要素到第j个要素的“1”笔划的笔划序列yp时的成本（局部距离）。

[0088] 假定笔划组X为检索目标，则笔划组Y为查询，并且各个笔划数为I和J。包括在通过方程式（15）表示的路径中的笔划组Y的笔划序列变成检索单元25的检索结果（参见图7）。

[0089] g(i,J)(1≤i≤l)≤thresholdvalue  (15)

[0090] 显示控制单元27在显示单元29上显示通过检索单元25检索到的数据。在实施例中，显示控制单元27在显示单元29上显示通过检索单元25检索到的字符串数据。例如，显示
控制单元27可以将显示单元29的屏幕分成如图8所示的平铺图案，以在各个平铺显示中显
示文档的缩小的缩略图。此时，显示控制单元27可以布置文档的缩略图，例如，按照与包括
在文档中的笔划序列的检索结果较高类似度的顺序作为显示顺序。换句话说，检索结果的
笔划序列可以在缩略图中被突出显示。

[0091] 图9是图解实施例的检索设备10中进行的处理的典型程序流的流程图。

[0092] 首先，获取单元13顺序获取通过输入单元11输入的笔划，以便获得笔划组（步骤S101）。

[0093] 接着，分割单元17将构成通过获取单元13获取的笔划组的各个笔划分成多个副笔划（步骤S103）。

[0094] 接着，提取单元19从这些副笔划中提取多个副笔划中每一个的独特特征向量（步骤S105）。

[0095] 接着，计算部23基于属于笔划组的多个各个副笔划之间的最佳路径，计算构成笔划组的笔划之间的距离（步骤S107）。

[0096] 接着，检索单元25使用通过计算部23计算的距离，检索与通过获取单元13获取的笔划组相对应的字符串数据（步骤S109）。

[0097] 接着，显示控制单元27在显示单元29上显示通过检索单元25检索到的字符串数据（步骤S111）。

[0098] 在上述处理中，步骤S101到S105也能够并列进行。

[0099] 如上所述，根据实施例，构成笔划组的笔划被分成多个副笔划作为用于检索的查询。即使在构成笔划组的笔划的数目很小的情况下，这样也能够认为增加笔划的数目，从而
抑制检索精确度的降低。在检索过程中，基于副笔划序列之间的最佳路径来进行检索。这样
在检索过程中就减少处理成本，从而抑制检索速度的减少。

[0100] 硬件配置

[0101] 图10是图解实施例的检索设备10的典型硬件配置的图。如图10所示，检索设备10包括CPU201、输入装置202、输出装置203、RAM204、ROM205、外部存储接口206和通信接口
207。例如，在触摸屏被用作输入装置202和输出装置203的情况下，可以使用液晶面板、笔、
设置在液晶面板上的笔划检测装置和类似装置（参见附图标号208）。

[0102] 在实施例的检索设备10中执行的程序被预先嵌入提供的ROM或者类似的存储器中。可以设置在实施例的检索设备10中执行的程序作为可安装文件格式或者可执行文件格
式的文件，该文件被存储在计算器能够从其读出程序的存储介质上，存储介质例如为CD-
ROM、CD-R、存储卡、DVD和软磁盘（FD）。在实施例的检索设备10中执行的程序也可以被存储
在连接到诸如因特网的网络的计算机上以便通过网络下载而提供该程序。

[0103] 实施例的检索设备10中执行的程序具有模块构造以实现计算机上的上述各个单元。作为实际硬件，例如，CPU201从ROM205读出程序到RAM204上并且执行该程序以实现计算
机上的上述各个单元。

[0104] 实施例中的检索设备10可以被配置为独立装置或者以被分散为能够通过网络彼此通信的多个节点的形式。实施例的检索设备可以通过各种装置被实现，装置例如是台式
计算机或者一般用途的笔记本计算机、一般用途的便携式计算机、其它便携式信息装置、具
有触摸屏的信息装置、智能手机及其它信息装置。

[0105] 例如，图11图解服务器301存在于诸如内部网和/或因特网的网络302上并且各个客户机303和304通过网络302与服务器301通信以便实现检索设备10的情况的实例。

[0106] 图解了客户机303通过无线通信被连接到网络302，同时客户机304通过有线通信被连接到网络302的情况。客户机303和304通常为用户装置。服务器301可以例如被设置在
诸如公司内部局域网（intra-company LAN）的局域网上，或者可以通过因特网服务提供者
或者类似的提供者被运行。另外，服务器301可以是允许用户向另一个用户提供功能的用户
装置。

[0107] 当基于图1的构造进行说明时，输入单元11、获取单元13、显示控制单元27和显示单元29可以被设置在客户机侧上，而其它构造被设置在服务器侧上。另外，计算部23和检索
单元25可以被设置在服务器侧上，而其它配置可以被设置在客户机侧上。

[0108] 这里，可以实现包括除了输入单元11、获取单元13、显示控制单元27和显示单元29之外的构造的设备，或者可以实现包括显示控制单元27和显示单元29的设备。在这种情况
下，该设备具有用于从副笔划提取特征向量的功能。

[0109] 如图1所示，输入单元11、获取单元13、显示控制单元27和显示单元29可以被包括在客户机侧中，计算部23和检索单元25可以被包括在第一服务器中，并且墨水数据存储单
元15、分割单元17、提取单元19和特征向量存储单元21可以被包括在第二服务器中。

[0110] 除了这些以外的分散方法也是可以的。

[0111] 第一变化例

[0112] 在检索设备10中，通过获取单元13获得的笔划可以是声音波形数据。在这种情况下，获取单元13对从诸如扩音器的输入装置输入的声音进行模拟/数字转换，以便获得数字
信号。例如，声音以16KHz被采样并且被转换为16位量子化的数字信号。

[0113] 接着，获取单元13通过相对于数字信号的振幅值的阈值将声音信号分成音频段和无声段，并且将完整的音频段顺序输出到分割单元17。分割方法并不局限于上述方法。例
如，通过某个时间段的分割的结果可以在没有分成音频段和无声段的情况下被输出。作为
输出，音频段和无声段都可以被输出到分割单元17。

[0114] 分割单元17以预定某个间隔分割从获取单元13输出的一个完整的声音段，并且将分割结果顺序地输出到特征提取单元。该分割并不局限于以某个间隔分割。例如，当邻近框
架的频谱的差值超过某个水平时的分割的处理可以使用光谱分析和类似的方法来执行。

[0115] 提取单元19对从分割单元17输出的一个分割的声音段，从而样本的数目变成预定数据，类似于实施例。接着，傅里叶变换和24维梅尔滤波器组分析（Mel-filter bank 
analysis）被用于计算具有24维对数梅尔频谱的要素的向量作为特征向量。

[0116] 使用的特征向量不局限于对数梅尔频谱。例如，诸如梅尔频率倒谱系数（MFCC）的声音特征向量也是可以的。

[0117] 第二变化例

[0118] 在检索设备10中，通过获取单元13获得的笔划可以是位置信息的轨迹数据。在这种情况下，获取单元13从诸如全球定位系统（GPS）的位置测量装置获取位置信息。获取单元
13保存获得的位置信息作为轨迹的笔划。类似于实施例，作为位置信息的笔划被保存作为
二维空间中的一组坐标值。在这种情况下，用于结合值作为一个笔划的一些标准也是可以
的。例如，仅仅移动量大于或等于某个时间段内的阈值的段被保存为笔划。

[0119] 如上所述，根据上述实施例和各个变化例，检索速度的减少被抑制，同时检索精确度被提高。

[0120] 例如，上述实施例的程序图中的各个步骤可以按修改的执行次序被执行，同时被执行，或者在执行与各个步骤一致的范围内对于每个执行以不同的执行次序被执行。

[0121] 根据如上所述的至少一个实施例的检索设备，检索设备包括获取部、分割部、提起部、计算部和检索部。获取部被配置成获得多个第一点序列。分割部被配置成将每个第一点
序列分割成多个第二点序列。提取部被配置成提取每个第二点序列的特征向量。计算部被
配置成基于第二点序列之间的最佳路径来计算第一点序列之间的距离，该第二点序列属于
每个第一点序列。检索部被配置成使用距离来检索与第一点序列相对应的数据。因此，检索
速度的减少能够被抑制，并且检索精确度能够被提高。

[0122] 虽然已经描述了确定的实施例，但是这些实施例仅仅用于举例说明，并不是对发明的范围进行限制。实际上，在这里描述的新颖的实施例可以用各种其它形式来具体表现；
此外，在不背离发明的精神的范围内，可以进行以这里描述的实施例的形式的各种省略、替
换和改变。所附的权利要求及其等价物用于覆盖将落入发明的范围和精神内的这种形式或
者变形例。