Analysis of Chinese pen sequence animation technology

Author: vigorously intelligent client team circle

background

Chinese character stroke sequence animation is a common Chinese language education demand, we imported online open source Hanzi Writter and deployed the editor, and applied in vigorously intelligent work light. On the basis of the original front-end implementation, we have expanded the Android and iOS side implementation to provide more optimized stroke order animation performance. Enhance the ability to control the stroke order rendering, realize the specified stroke order/stroke section rendering, support the ability to correct the stroke order and trace red.

The key technology

1. Glyph data extraction

A glyph is the appearance shape of a single character, while a font is a collection of glyphs with the same appearance style and typographic size. Based on the glyph data, we can render each text and animate the stroke sequence. So how do you get the glyphs data? TTF is a good choice. TTF (TrueTypeFont) is a curved stroke font file format, launched by Apple and Microsoft, with a.ttf file extension. It supports a variety of fonts, such as the common regular script in Chinese textbooks. The TTF file consists of a series of tables, including the Glyf table, which contains glyph data, that is, the outline definition and adjustment instructions for the glyph. The glyphs data can be extracted according to the following process:

The adaptation of the different fonts of the boundary, all converted to 1024*1024, and fine tuning the upper, lower and left.
Extract contours and path data of all glyph contours.

After the glyph data is extracted, the corresponding text is drawn using SVG.

2. The Stroke Extraction was carried out on the brush

In the first section, we realize the extraction of the glyph data, which includes the contours and path (a) of the glyph. However, stroke sequence animation cannot be realized solely by relying on these data, because they only have contour information, without stroke information. As long as there is crossover and overlap, the same individual will be identified (b). Therefore, in order to achieve stroke sequence animation, it is necessary to remove all the contour data of the strokes from the source data, namely, stroke removal.

2.1 Solution

Because of the overlap (c) between the strokes, to realize the disassembly of the strokes, it is necessary to connect the concave points at the intersection of the strokes. These special corners at the intersection are called corners, connecting the two corners to form a bridge, indicating that they belong to the same stroke.

When tracking the endpoint clockwise:

Before connection: according to the order of contour points.
After connection: the corresponding corner will be directly connected according to the bridge, so as to realize the split of strokes.

Therefore, the stroke removal work is mainly divided into the following four steps:

2.2 EndPoint Parsing Corner detection

In Hanzi Writter open source library, the stroke removal algorithm is mainly developed around corner. So what is the corner? In detail, a corner is a special end point located at the junction of two stroke contours, which is usually matched by another corner, such as C1 and C2. C1 and C2 are adjacent and on the same side of the contour of stroke A. If C1 and C2 are connected, stroke A and stroke B can be separated to obtain the contour data of stroke A. These corners have a significant local feature. They are the concave points of the glyph, through which the path will curve sharply clockwise. By calculating the angles and distances of all the endpoints and determining whether they have this feature, we can detect which endpoints are 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; }Copy the code

2.3 Corner Match Scoring Scores the Corner matching degree through NN

After detecting a set of corner data, one-to-one matching is required for these corners, but before matching, it is also necessary to judge which corners are more likely to be connected. The open source library uses neural network algorithm to calculate the matching degree between corners, which will become the weight value in the matching algorithm and make the matching result more close to the reality.

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); }});Copy the code

2.4 Corner Matching Corner Matching is performed using the Hungarian algorithm

In section 2.3, the weights have been generated through the neural network. Next, the simplest Hungarian algorithm can be used to realize corner matching.

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)); }} 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; }Copy the code

Paired endpoints split strokes

A set of Bridges, each containing two corners, is returned based on the matching results in section 2.4. While tracking the contour and connecting the corner, the contour data of each stroke can be extracted and stroke splitting can be realized. It is worth noting that when multiple Bridges are encountered, the bridge that forms the largest Angle to the current path is selected.

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]));
Copy the code

3. Medians midpoint generation

In the second section, we split the strokes and get the contour data of each stroke. The midpoint skeleton of the stroke can be further generated from the contour data. The outline determines the range to which a single stroke should be drawn, while the midpoint determines the order and direction in which it should be drawn. Combining the contour and midpoint data, a single stroke can be animated. Let’s look at how to generate midpoints from contour data.

3.1 Polygon Approximation endpoint encryption

Firstly, in order to improve the reliability of the midpoint generation results, the polygon approximation method of vector graphics is used to encrypt the contour points. TrueType fonts use quadratic Bezier curves and straight lines to describe the contours of glyphs, so the encryption formula is as follows:

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;
}
Copy the code

Generate the midpoint from a Vonronoy diagram (tyson Polygon)

After obtaining the encrypted contour point data, the midpoint can be generated using tyson polygons. So what is a Tyson polygon?

First, do the following for a set of scattered control points:

Connect three adjacent control points into a triangle
Make perpendicular bisectors on each side of the triangle
These perpendicular bisectors form continuous polygons

These continuous polygons are called tyson polygons, also known as the Voronoi Diagram, after Georgy Voronoi. In IS and geographic analysis, tyson polygon IS often used for fast interpolation to analyze the influence area of geographic entities, which IS another common tool to solve the problem of adjacancy.

According to the principle, each vertex of a Tyson polygon is the center of the circumcircle of the corresponding triangle, so it is equidistant from these control points.

  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.
Copy the code

Following this idea, you can use the outline points of the stroke as control points to generate a Tyson polygon. Extract the vertex of the Tyson polygon as the center point of the stroke.

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}.`); }}... }Copy the code

4. Stroke order

The third section implements the drawing animation of a single stroke, but still needs to solve the order between the strokes. The key to solve the problem is to continuously disassemble the target Chinese characters into characters of known order according to the structure of Chinese characters.

The Chinese character decomposition database is provided in the open source library, and the key fields are as follows:

Take [Hu] for example, ⿰ indicates that hu is left and right structure, the left is ancient, and the right is moon.

Taking [Hu] as an example, the disassembly process is as follows:

After dissolving the stroke order, it is necessary to match all the scattered midpoint data with the current midpoint again through the Hungarian algorithm. Finally, a relatively correct stroke order result can be obtained and a JSON file is generated. The following is the result file of the stroke order of the Chinese character “d”.

{"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]]}Copy the code

5. Reference

This paper focuses on the analysis of the key technologies of stroke sequence animation in the open source library. The relevant reference materials are as follows:

hanziwriter.org/
www.skishore.me/makemeahanz…
Github.com/skishore/ma…