Press "Enter" to skip to content

汉字笔顺动画技术剖析

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

背景

 

汉字笔顺动画是常见的语文教育需求,我们导入网上开源的 Hanzi Writter 并部署编辑器,应用在大力智能作业灯上。在原版前端实现基础上我们扩展了 Android 和 iOS 端实现,提供更优化的笔顺动画性能。增强对笔顺绘制的控制能力,实现了指定笔顺/笔段渲染,支持笔顺批改和描红能力。

 

 

关键技术

 

1. 字形数据提取

 

字形是单个字符的外观形状,而字体是具有相同外观样式和排版尺寸的字形集合。基于字形数据,我们可以实现每个文字的渲染和笔顺动画。那幺该如何拿到字形数据呢?TTF就是不错的选择。TTF(TrueTypeFont)是一种曲线描边字体文件格式,由Apple公司和Microsoft公司共同推出,其文件扩展名为.ttf。它支持多种字体,如语文课本中常见的楷体。TTF文件由一系列表组成,其中glyf表就包括了字形数据,即字形的轮廓定义和调整指令。依据下述流程可以提取字形数据:

 

 

    1. 对不同字体的boundary进行适配,全部转换成1024*1024,并对上下左右进行微调。

 

    1. 提取所有字形glyph的轮廓点contours和path数据。

 

 

 

提取出字形数据后,使用SVG将对应文字绘制出来。

 

 

2. Stroke Extraction 笔画拆取

 

在第一节中实现了字形数据的提取,它包括字形的轮廓点contours及path(a)。但是仅依靠这些数据无法实现笔顺动画,因为它们只有轮廓信息,没有笔画信息,只要有交叉重叠,都会识别成同一个体(b)。因此,要实现笔顺动画,就必须从源数据中拆取出所有笔画的轮廓数据,即笔画拆取。

 

 

2.1 解决思路

 

由于笔画之间存在交叉重叠(c),若要实现笔画拆取,就需要将笔画交接处的凹点连通起来。这些处于交叉处特殊的拐角点称为corner,连通两个corner形成bridge,表明他们同属于一个笔画。

 

当顺时针跟踪端点:

 

连通前:依据轮廓点顺序。

 

连通后:会依据bridge直接联通对应corner,从而实现笔画的拆分。

 

 

因此,笔画拆取工作主要分为以下四步:

 

 

2.2 EndPoint Parsing Corner检测

 

在Hanzi Writter开源库中,笔画拆取算法主要围绕corner展开。那corner是什幺呢?详细来说,corner是位于两个笔画轮廓交界的特殊端点,通常情况下,他会有另一个corner与之匹配,如C1和C2。C1和C2相邻且处于笔画A的轮廓同侧,连通C1和C2就可以将笔画A和笔画B拆分开来,得到笔画A自己的轮廓数据。这些corner具有显着的局部特征,它们是字形的凹点,经过该点处的path会沿着顺时针急剧弯曲。计算出所有端点的角度和距离,判断是否拥有该特征,就可以检测哪些端点为corner。

 

 

function Endpoint(paths, index) {
  this.index = index; 
  const path = paths[index[0]];
  const n = path.length;
  this.indices = [[index[0], (index[1] + n - 1) % n], index];
  this.segments = [path[(index[1] + n - 1) % n], path[index[1]]];
  this.point = this.segments[0].end;
  assert(Point.valid(this.point), this.apoint);
  assert(Point.equal(this.point, this.segments[1].start), path);
  this.tangents = [
    Point.subtract(this.segments[0].end, this.segments[0].start),
    Point.subtract(this.segments[1].end, this.segments[1].start),
  ];
  const threshold = Math.pow(MIN_CORNER_TANGENT_DISTANCE, 2);
  if (this.segments[0].control !== undefined &&
      Point.distance2(this.point, this.segments[0].control) > threshold) {
    this.tangents[0] = Point.subtract(this.point, this.segments[0].control);
  }
  if (this.segments[1].control !== undefined &&
      Point.distance2(this.point, this.segments[1].control) > threshold) {
    this.tangents[1] = Point.subtract(this.segments[1].control, this.point);
  }
  this.angles = this.tangents.map(Point.angle);
  const diff = Angle.subtract(this.angles[1], this.angles[0]);
  this.corner = diff < -MIN_CORNER_ANGLE;
  return this;
}

 

2.3 Corner Match Scoring 通过NN评分Corner匹配度

 

检测出一组corner数据后,就要对这些corner进行一对一匹配,但在匹配前还需要评判哪些corner更有可能连接起来。开源库采用神经网络算法计算corner间的匹配度,它将成为匹配算法中的权重值,使匹配结果更贴近现实情况。

 

const scoreCorners = (ins, out, classifier) => {
  return classifier(getFeatures(ins, out));
}

import {NEURAL_NET_TRAINED_FOR_STROKE_EXTRACTION} from '/lib/net';
import {stroke_extractor} from '/lib/stroke_extractor';
Meteor.startup(() => {
  const input = new convnetjs.Vol(1, 1, 8 /* feature vector dimensions */);
  const net = new convnetjs.Net();
  net.fromJSON(NEURAL_NET_TRAINED_FOR_STROKE_EXTRACTION);
  const weight = 0.8;
  const trainedClassifier = (features) => {
    input.w = features;
    const softmax = net.forward(input).w;
    return softmax[1] - softmax[0];
  }
  stroke_extractor.combinedClassifier = (features) => {
    return stroke_extractor.handTunedClassifier(features) +
           weight*trainedClassifier(features);
  }
});

 

2.4 Corner Matching 通过匈牙利算法进行Corner匹配

 

在2.3小节中已经通过神经网络产生了权重,接下来就可以使用最简单的匈牙利算法,实现corner匹配。

 

 

 

const matchCorners = (corners, classifier) => {
  const matrix = [];
  for (let i = 0; i < corners.length; i++) {
    matrix.push([]);
    for (let j = 0; j < corners.length; j++) {
      matrix[i].push(scoreCorners(corners[i], corners[j], classifier)); //corner之间相关性
    }
  }
  for (let i = 0; i < corners.length; i++) {
    for (let j = 0; j < corners.length; j++) {
      const reversed_score = matrix[j][i] - REVERSAL_PENALTY;
      if (reversed_score > matrix[i][j]) {
        matrix[i][j] = reversed_score;
      }
    }
  }
  return (new Hungarian(matrix)).x_match;
}

 

2.5 Make Bridges 连通配对端点拆分笔画

 

依据2.4小节的匹配结果返回一组bridge,其中每个bridge包含两个corner。跟踪轮廓的同时连通corner,就可以提取出每个笔画的轮廓数据,实现笔画拆分。值得注意的是,当遇到多个bridge时,选择与当前path构成最大角度的bridge。

 

 

const getBridges = (endpoints, classifier) => {
  const result = [];
  const corners = endpoints.filter((x) => x.corner);
  const matching = matchCorners(corners, classifier);
  for (let i = 0; i < corners.length; i++) {
    const j = matching[i];
    if (j <= i && matching[j] === i) {
      continue;
    }
    result.push([Point.clone(corners[i].point), Point.clone(corners[j].point)]);
  }
  result.map(checkBridge);
  return result;
}
const stroke_paths = extractStrokes(paths, endpoints, bridges, log);
const strokes = stroke_paths.map((x) => svg.convertPathsToSVGPath([x]));

 

3. Medians 笔画中点生成

 

在第二节中实现了笔画的拆分,得到每个笔画的轮廓数据。依据轮廓数据可以进一步生成笔画的中点骨架。轮廓决定单个笔画的绘制范围,而中点则决定了绘制的顺序和方向。结合轮廓和中点数据,就可以实现单个笔画的绘制动画。接下来就让我们一起了解,如何通过轮廓数据生成中点。

 

 

3.1 Polygon Approximation 端点加密

 

首先,为了提高中点生成结果的可靠性,需要先采用矢量图形的多边形近似方法进行轮廓点加密。TrueType字体利用二次贝赛尔曲线和直线来描述字形的轮廓,因此加密公式如下:

 

 

 

svg.getPolygonApproximation = (path, approximation_error) => {
  const result = [];
  approximation_error = approximation_error || 64;
  for (let x of path) {
    const control = x.control || Point.midpoint(x.start, x.end);
    const distance = Math.sqrt(Point.distance2(x.start, x.end));
    const num_points = Math.floor(distance/approximation_error);
    for (let i = 0; i < num_points; i++) {
      const t = (i + 1)/(num_points + 1);
      const s = 1 - t;
      result.push([s*s*x.start[0] + 2*s*t*control[0] + t*t*x.end[0],
                   s*s*x.start[1] + 2*s*t*control[1] + t*t*x.end[1]]);
    }
    result.push(x.end);
  }
  return result;
}

 

3.2 Polygon Voronoi 通过冯洛诺伊图(泰森多边形)生成中点

 

得到加密的轮廓点数据后,就可以通过泰森多边形生成中点。那什幺是泰森多边形呢?

 

首先对一组零散控制点做如下操作:

 

 

    1. 将三个相邻控制点连成一个三角形

 

    1. 对三角形的每条边做垂直平分线

 

    1. 这些垂直平分线会组成连续多边形

 

 

这些连续多边形就是泰森多边形,又叫冯洛诺伊图(Voronoi diagram),得名于Georgy Voronoi。在IS和地理分析中经常采用泰森多边形进行快速插值,分析地理实体的影响区域,是解决邻接度问题的又一常用工具。

 

 

通过原理可以了解到,泰森多边形每个顶点是对应三角形的外接圆圆心,因此它到这些控制点的距离相等。

 

var sites = [{x:300,y:300}, {x:100,y:100}, {x:200,y:500}, {x:250,y:450}, {x:600,y:150}];
  // xl, xr means x left, x right
  // yt, yb means y top, y bottom
  var bbox = {xl:0, xr:800, yt:0, yb:600};
  var voronoi = new Voronoi();
  // pass an object which exhibits xl, xr, yt, yb properties. The bounding
  // box will be used to connect unbound edges, and to close open cells
  result = voronoi.compute(sites, bbox);
  // render, further analyze, etc.

 

按照这个思路,可以将笔画的轮廓点作为控制点,生成泰森多边形。提取泰森多边形的顶点作为笔画中心点。

 

 

const findStrokeMedian = (stroke) => {
  ...
  for (let approximation of [16, 64]) {
    polygon = svg.getPolygonApproximation(paths[0], approximation);
    voronoi = voronoi || new Voronoi;
    const sites = polygon.map((point) => ({x: point[0], y: point[1]}));
    const bounding_box = {xl: -size, xr: size, yt: -size, yb: size};
    try {
      diagram = voronoi.compute(sites, bounding_box);
      break;
    } catch(error) {
      console.error(`WARNING: Voronoi computation failed at ${approximation}.`);
    }
  }
  ...
}

 

4. 笔画顺序

 

第三节实现了单个笔画的绘制动画,但还是需要解决笔画之间的顺序问题。解决问题的关键,就是依据汉字结构,将目标汉字不断拆解成已知顺序的字。

 

在开源库中提供了汉字分解数据库,关键字段如下:

 

 

以【胡】,⿰表示胡为左右结构,左边为古,右边为月。

 

 

以【湖】为例,拆解过程如下:

 

 

 

拆解完笔顺后,需要将所有零散的中点数据,与当前所拥有的中点再做一遍匈牙利算法匹配,最终可得到一个相对正确的笔画顺序结果,生成json文件。下面为汉字“丁”的笔顺结果文件。

 

{"strokes": ["M 531 651 Q 736 675 868 663 Q 893 662 899 670 Q 906 683 894 696 Q 863 724 817 744 Q 801 750 775 740 Q 712 725 483 694 Q 185 660 168 657 Q 162 658 156 657 Q 141 657 141 645 Q 140 632 160 618 Q 178 605 211 594 Q 221 590 240 599 Q 348 629 470 644 L 531 651 Z", "M 435 100 Q 407 107 373 116 Q 360 120 361 112 Q 361 103 373 94 Q 445 39 491 -5 Q 503 -15 518 2 Q 560 60 553 141 Q 541 447 548 561 Q 548 579 550 596 Q 556 624 549 635 Q 545 642 531 651 C 509 671 457 671 470 644 Q 485 629 485 573 Q 488 443 488 148 Q 487 112 477 99 Q 464 92 435 100 Z"], "medians": [[[153, 645], [177, 634], [219, 628], [416, 663], [794, 706], [823, 702], [887, 679]], [[478, 644], [518, 610], [518, 101], [495, 55], [450, 68], [369, 110]]]}

 

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注