从算法流程看QQ手机输入法的滑动输入
泡泡网软件频道12月31日 当今触屏智能手机越来越流行，用户在触屏输入中也有了按键易错、触感较差等诸多困扰，不少企业都在探索如何在触屏手机上提高输入体验。最近，QQ手机输入法就使用了一种滑动输入技术，力图改善用户在触屏手机上的输入体验。其基本操作方法是用手指(或笔)在触摸屏上的虚拟键盘通过滑动来选择字母, 其滑动顺序为要输入的单词（拼音组合）的先后顺序，手指抬起时代表输入完毕。例如用户输入friend，则可以下面两种方式输入：
1、在虚拟键盘中，按照如下顺序滑动f-r-i-e-n-d. 如下图所示，‘f’为滑动的起始点，‘d’为滑动的结束点（滑动的位置不需要非常精确，只需要大致走向正确就可以）：
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_c690df3e731033f59c7ddda74869f4f1.jpg
2、依次点击f-r-i-e-n-d，在点击输入各个字母的时候可以不用非常准确的输入，只要能在想输入的字母周围击中就可以，从而不必再担心全键盘按钮太小不容易点中的问题啦。
简单介绍完滑动输入的操作方法后，大家一定想知道滑动输入技术上是如何实现的呢？下面就详细介绍下滑动输入的实现算法。
滑动输入的核心算法思想就是把用户输入的滑动轨迹提取一定特征，然后跟词库中的单词轨迹进行比对识别，最后输出候选识别结果。下面我们看看滑动输入滑动算法框架流程图，大致分为三个处理模块：
第一，生成特征和模板；
第二：计算相似度；
第三：融合词频和相似度结果，返回最优列表。
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_4938ef1569ced59ea05cf18cd785c9b5.jpg
接下来，我们从上面的算法流程来逐一介绍滑动输入实现技术。
1. 滑动轨迹的数据表示
滑动轨迹数据是一个等时间间隔的数据流，其具体采样频率随手机触摸屏的参数差异而不同，一般来说都在50-200Hz之间。每一个时间点上包含三维数据：（x，y，sw）。其中x, y分别是当前轨迹点的横坐标和纵坐标，而sw则为一个反映压力的二值信号，用来标识当前手指（手写笔）处在落下或是抬起的状态。
2. 滑动轨迹数据的预处理
采集得到的原始滑动轨迹数据要进行预处理，使得数据更适于提取特征并具有可比性。QQ手写输入法中主要的预处理环节包括：重采样、大小归一化、点距均一化、平滑滤波（表1），得到预处理后的轨迹序列：
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_71cfa2c3162d2458e95a3257ee1d64e8.jpg
N为预处理后的轨迹点数：
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_2767cca9d84ee95ccb1e170e8f770d10.jpg
3. 特征和匹配模版生成
1） 对词库中的单词生成词库特征
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_0cc57fd169b6b4ea9232f215d40c6e6d.jpg
和匹配模板
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_0cc57fd169b6b4ea9232f215d40c6e6d.jpg
。
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_0cc57fd169b6b4ea9232f215d40c6e6d.jpg
为一个二维坐标点，具体做法如下：
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_c13f7eaaf818758e0f0a8f5f0a93eb9b.jpg
生成词库特征序列
例如红线为单词“dog”在软键盘全键盘上的滑动轨迹，灰线为用户的实际滑动轨迹。根据我们红线所示的轨迹，我们采样生成词库中单词的特征
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_0cc57fd169b6b4ea9232f215d40c6e6d.jpg
，即为图3中绿点的集合，
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_0cc57fd169b6b4ea9232f215d40c6e6d.jpg
中特征点的距离间隔相同，建立模板
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_0cc57fd169b6b4ea9232f215d40c6e6d.jpg
。
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_0173e1e3c97573bcfc7fec4e91aa0edf.jpg
为字符所处的位置是
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_fa44f5a103bcbef0ccfe162b5a1e29c1.jpg
2）建立模板
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_49d7e2038fd1bf1e78ce74ba11ef38e5.jpg
。滑动输入的过程中，一般来说，用户对于滑动输入开始段和结尾段较容易按准确，而对于中间部分则较差，因此构建
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_49d7e2038fd1bf1e78ce74ba11ef38e5.jpg
模板为二次曲线，如下图所示：
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_dd922f720448f11cb9519e876d7b515f.jpg
a,b为常数权值。
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_49d7e2038fd1bf1e78ce74ba11ef38e5.jpg
模板意味着特征头尾所占的权值较大，中间较小，点的权值从中间相两端非线性增长，一般来说可以通过大量数据的训练得到。
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_c7918395bd146eba6e252ea2af53b65a.jpg
4. 相似度的计算
根据上一步得到的特征和模板，计算相似度公式如下
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_b238fb7792ec912f6a4be5afaf611f02.jpg
N是采样特征点的个数。
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_136cf714d7793985e6994e0f1e602b47.jpg
越低，则意味着两个特征越接近。
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_85c2dd19080cf4cb0f7b86927fc6b2cb.jpg
，
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_6fe9641041930daba2711cb76668deb6.jpg
分别为匹配过程中一维模板。
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_2684738777aa3f5bb6e6a73967c1a1dd.jpg
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_704fab4cddd6f1f62d8ce9fcd5e508f4.jpg
radius为软键盘的按键半径. r为比对范围值。
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_c1126098ba92e1189860ee6e72f494ad.jpg
这里采用弹性匹配机制，
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_240cadb118d81936ebb8623b8ced1287.jpg
与
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_1b213ceb6bd77d02120634ce976fa741.jpg
中 的特征点进行匹配，寻找距离最小的匹配值判定为
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_240cadb118d81936ebb8623b8ced1287.jpg
和
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_1b213ceb6bd77d02120634ce976fa741.jpg
的距离。当
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_0b8cc4ca1c63d7d85416fd1e47745ad4.jpg
为零可以判定两特征在相似度上十分接近。可以近似为零，即Xs等于0。
这里对
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_cbe079252e53dd85959f076b302b1a2a.jpg
同样采取一个弹性匹配机制, 即
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_cbe079252e53dd85959f076b302b1a2a.jpg
=1的时候其和
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_1b213ceb6bd77d02120634ce976fa741.jpg
的乘积也是一个范围内的计算取最小值，通过弹性匹配可以放大关键点位置的特征所占的重要性。
5.特征融合
滑动输入反馈给UI的结果为一个按匹配分值从高到低排列的匹配单词序列。匹配分值由单词频率和相似度融合而成。最终匹配分值为：
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_fed18061b27b655b27be5d886f31a87e.jpg
a,b为常数权值，通过大量样本数据训练获得,Xo为相似度的结果，Yo为词频的值。S为最终匹配分值，作为返回列表排序的依据。
6.滑动输入测试结果
取总数为718的测试样本，样本为10名不同的用户使用滑动输入输入的轨迹。用户群的组成为年龄从23岁到35岁的男、女性。测试平台为HTC G3 Android平台手机。
http://res.tech.ifeng.com/attachments/2010/12/31/rd_or_9ed32a75d3b00f1293b05ffe6c1ddb19.jpg
上面我们对QQ手机输入法中的滑动输入技术做了详细介绍， 滑动输入目前的版本还暂且不支持拼音的滑动输入，但从上面的技术分析看来，支持汉语拼音中的全拼，仅仅就是替换其中的词库，换句话说就是把汉语拼音中的全拼发音序列当成一个词库，那么就可以轻松支持汉语拼音的全拼输入了，相信后续的版本一定会支持。
面对众多的无线终端上的输入法应用的激烈竞争，相信QQ手机输入法后续在改善输入体验方面会推出更多亮点，从而在无线终端上更具有竞争力。■
页:
[1]