4 cellwriter -- a character recognition input method
5 Copyright (C) 2007 Michael Levin <risujin@risujin.org>
7 This program is free software; you can redistribute it and/or
8 modify it under the terms of the GNU General Public License
9 as published by the Free Software Foundation; either version 2
10 of the License, or (at your option) any later version.
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
25 #include "recognize.h"
32 /* Maximum and variable versions of the number of samples to prepare for
33 thorough examination */
34 #define PREP_MAX (SAMPLES_MAX * 4)
35 #define PREP_SAMPLES (samples_max * 4)
38 #define VALUE_MAX 2048.f
39 #define VALUE_MIN 1024.f
41 /* Penalties (proportion of final score deducted) */
42 #define VERTICAL_PENALTY 16.00f
43 #define GLUABLE_PENALTY 0.08f
44 #define GLUE_PENALTY 0.02f
46 int ignore_stroke_dir = TRUE, ignore_stroke_num = TRUE, prep_examined;
48 static float measure_partial(Stroke *as, Stroke *b, Vec2 *offset, float scale_b)
54 b_len = b->distance * scale_b / ROUGH_RESOLUTION + 0.5;
57 min_len = as->len >= b_len ? b_len : as->len;
58 bs = sample_stroke(NULL, b, b_len, min_len);
59 value = measure_strokes(as, bs, (MeasureFunc)measure_distance, offset,
60 min_len, ROUGH_ELASTICITY);
65 static float greedy_map(Sample *larger, Sample *smaller, Transform *ptfm,
72 unmapped_len = larger->len;
74 /* Prepare transform structure */
75 memset(&tfm, 0, sizeof (tfm));
79 for (i = 0, total = 0.f; i < smaller->len; i++) {
80 float best, best_reach = G_MAXFLOAT, best_value = G_MAXFLOAT,
81 value, penalty = G_MAXFLOAT, seg_dist = 0.f;
82 int j, last_j = 0, best_j = 0, glue = 0;
85 for (j = 0, best = G_MAXFLOAT; j < larger->len; j++) {
88 unsigned char gluable;
92 tfm.reverse[j] = FALSE;
94 /* Do not glue on oversize segments */
96 larger->strokes[j]->distance / 2 >
97 smaller->strokes[i]->distance &&
98 (larger->strokes[j]->spread > DOT_SPREAD ||
99 smaller->strokes[i]->spread > DOT_SPREAD))
102 tfm.order[j] = i + 1;
111 unsigned char gluable2;
113 /* Can we glue these strokes together? */
114 if (!tfm.reverse[j]) {
115 gluable = larger->strokes[j]->
116 gluable_start[last_j];
117 gluable2 = larger->strokes[last_j]->
119 if (gluable2 < gluable)
121 if (gluable >= GLUABLE_MAX) {
122 if (!ignore_stroke_dir)
124 tfm.reverse[j] = TRUE;
127 if (tfm.reverse[j]) {
128 gluable = larger->strokes[j]->
130 gluable2 = larger->strokes[last_j]->
132 if (gluable2 < gluable)
134 if (gluable >= GLUABLE_MAX)
138 /* Get the inter-stroke (reach) distance */
139 p1 = larger->strokes[last_j]->points +
140 (tfm.reverse[last_j] ? 0 :
141 larger->strokes[last_j]->len - 1);
142 p2 = larger->strokes[j]->points +
143 (!tfm.reverse[j] ? 0 :
144 larger->strokes[j]->len - 1);
145 vec2_set(&v, p2->x - p1->x,
147 reach = vec2_mag(&v);
150 /* Transform and measure the distance */
151 stroke = transform_stroke(larger, &tfm, i);
152 scale = smaller->distance /
153 (reach + ptfm->reach + larger->distance);
154 value = measure_partial(smaller->roughs[i], stroke,
158 /* Keep track of the best result */
159 if (value < best && value < VALUE_MAX) {
165 /* Penalize glue and reach distance */
166 penalty = glue * GLUE_PENALTY +
167 gluable * GLUABLE_PENALTY /
171 /* Bail if we have a really good match */
172 if (value < VALUE_MIN)
175 /* Glue on with reversed direction */
176 if (ignore_stroke_dir && !tfm.reverse[j] &&
177 larger->strokes[j]->spread > DOT_SPREAD) {
178 tfm.reverse[j] = TRUE;
182 tfm.reverse[j] = FALSE;
185 if (best < G_MAXFLOAT) {
187 larger->penalty += penalty;
188 smaller->penalty += penalty;
189 seg_dist += best_reach +
190 larger->strokes[best_j]->distance;
191 ptfm->reach += best_reach;
194 /* If we still have strokes and we didn't just add on
195 a dot, try gluing them on */
197 if (unmapped_len >= smaller->len - i &&
198 larger->strokes[best_j]->spread >
206 /* Didn't map a target stroke? */
215 /* Didn't assign all of the strokes? */
221 return total / smaller->len;
224 static int prep_sample(Sample *sample)
229 /* Structural disqualification */
230 if (!sample->used || !sample->enabled ||
231 (!ignore_stroke_num && sample->len != input->len))
235 sample->penalty = 0.f;
237 /* Account for displacement */
238 center_samples(&offset, sample, input);
240 /* Compare each input stroke to every stroke in the sample and
241 generate the stroke order information which will be used by other
243 if (input->len >= sample->len)
244 dist = greedy_map(input, sample, &sample->transform, &offset);
246 vec2_set(&offset, -offset.x, -offset.y);
247 dist = greedy_map(sample, input, &sample->transform, &offset);
249 if (!sample->transform.valid)
252 /* Undo square distortion */
257 /* Penalize vertical displacement */
258 sample->penalty += VERTICAL_PENALTY *
259 offset.y * offset.y / SCALE / SCALE;
261 sample->ratings[ENGINE_PREP] = RATING_MAX -
262 RATING_MAX * dist / MAX_DIST;
266 void engine_prep(void)
268 Sample *sample, *list[PREP_MAX];
271 /* Rate every sample in every possible configuration */
275 while ((sample = sampleiter_next())) {
276 sample->disqualified = TRUE;
277 if (!sample->used || !sample->ch || !prep_sample(sample))
280 /* Bubble-sort sample into the list */
281 for (i = 0; i < PREP_SAMPLES; i++)
284 if (i < PREP_MAX - 1)
287 } else if (list[i]->ratings[ENGINE_PREP] <
288 sample->ratings[ENGINE_PREP]) {
289 memmove(list + i + 1, list + i,
290 (PREP_MAX - i - 1) * sizeof (*list));
296 /* Qualify the best samples */
297 for (i = 0; i < PREP_SAMPLES && list[i]; i++)
298 list[i]->disqualified = FALSE;