git.maemo.org Git - him-cellwriter/blob - src/averages.c

   1
   2 /*
   3
   4 cellwriter -- a character recognition input method
   5 Copyright (C) 2007 Michael Levin <risujin@risujin.org>
   6
   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.
  11
  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.
  16
  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.
  20
  21 */
  22
  23 #include "config.h"
  24 #include "common.h"
  25 #include "recognize.h"
  26 #include <stdlib.h>
  27 #include <string.h>
  28
  29 /*
  30         Average distance engine
  31 */
  32
  33 /* Maximum measures */
  34 #define MEASURE_DIST  (MAX_DIST)
  35 #define MEASURE_ANGLE (ANGLE_PI / 4)
  36
  37 int num_disqualified;
  38
  39 float measure_distance(const Stroke *a, int i, const Stroke *b, int j,
  40                        const Vec2 *offset)
  41 /* Measure the offset Euclidean distance between two points */
  42 {
  43         Vec2 v;
  44
  45         vec2_set(&v, a->points[i].x + offset->x - b->points[j].x,
  46                  a->points[i].y + offset->y - b->points[j].y);
  47         return vec2_square(&v);
  48 }
  49
  50 static float measure_angle(const Stroke *a, int i, const Stroke *b, int j)
  51 /* Measure the lesser angular difference between two segments */
  52 {
  53         float diff;
  54
  55         diff = (ANGLE)(a->points[i].angle - b->points[j].angle);
  56         return diff >= 0 ? diff : -diff;
  57 }
  58
  59 float measure_strokes(Stroke *a, Stroke *b, MeasureFunc func,
  60                       void *extra, int points, int elasticity)
  61 /* Find optimal match between A points and B points for lowest distance via
  62    dynamic programming */
  63 {
  64         int i, j, j_to;
  65         float table[(points + 1) * (points + 1) + 1];
  66
  67         /* Coordinates are counted from 1 because of buffer areas */
  68         points++;
  69
  70         /* Fill out the buffer row */
  71         j_to = elasticity + 2;
  72         if (points < j_to)
  73                 j_to = points;
  74         for (j = 1; j < j_to; j++)
  75                 table[j] = G_MAXFLOAT;
  76
  77         /* The first table entry is given */
  78         table[points + 1] = 2 * func(a, 0, b, 0, extra);
  79
  80         for (i = 1; i < points; i++) {
  81                 float value;
  82
  83                 /* Starting position */
  84                 j = i - elasticity;
  85                 if (j < 1)
  86                         j = 1;
  87
  88                 /* Buffer column entry */
  89                 table[i * points + j - 1] = G_MAXFLOAT;
  90
  91                 /* Start from the 2nd cell on the first row */
  92                 j += i == 1;
  93
  94                 /* End limit */
  95                 j_to = i + elasticity + 1;
  96                 if (j_to > points)
  97                         j_to = points;
  98
  99                 /* Start with up-left */
 100                 value = table[(i - 1) * points + j - 1];
 101
 102                 /* Dynamically program the row segment */
 103                 for (; j < j_to; j++) {
 104                         float low_value, measure;
 105
 106                         measure = func(a, i - 1, b, j - 1, extra);
 107                         low_value = value + measure * 2;
 108
 109                         /* Check if left is lower */
 110                         value = table[i * points + j - 1] + measure;
 111                         if (value <= low_value)
 112                                 low_value = value;
 113
 114                         /* Check if up is lower */
 115                         value = table[(i - 1) * points + j];
 116                         if (value + measure <= low_value)
 117                                 low_value = value + measure;
 118
 119                         table[i * points + j] = low_value;
 120                 }
 121
 122                 /* End of the row buffer */
 123                 table[i * points + j_to] = G_MAXFLOAT;
 124         }
 125
 126         /* Return final lowest progression */
 127         return table[points * points - 1] / ((points - 1) * 2);
 128 }
 129
 130 static void stroke_average(Stroke *a, Stroke *b, float *pdist, float *pangle,
 131                            Vec2 *ac_to_bc)
 132 /* Compute the average measures for A vs B */
 133 {
 134         Stroke *a_sampled, *b_sampled;
 135
 136         /* Sample strokes to equal lengths */
 137         if (a->len < 1 || b->len < 1) {
 138                 g_warning("Attempted to measure zero-length stroke");
 139                 return;
 140         }
 141         sample_strokes(a, b, &a_sampled, &b_sampled);
 142
 143         /* Average the distance between the corresponding points */
 144         *pdist = 0.f;
 145         if (engines[ENGINE_AVGDIST].range)
 146                 *pdist = measure_strokes(a_sampled, b_sampled,
 147                                          (MeasureFunc)measure_distance,
 148                                          ac_to_bc, a_sampled->len,
 149                                          FINE_ELASTICITY);
 150
 151         /* We cannot run angle averages if one of the two strokes has no
 152            segments */
 153         *pangle = 0.f;
 154         if (a->spread < DOT_SPREAD)
 155                 goto cleanup;
 156         else if (b->spread < DOT_SPREAD) {
 157                 *pangle = ANGLE_PI;
 158                 goto cleanup;
 159         }
 160
 161         /* Average the angle differences between the points */
 162         if (engines[ENGINE_AVGANGLE].range)
 163                 *pangle = measure_strokes(a_sampled, b_sampled,
 164                                           (MeasureFunc)measure_angle, NULL,
 165                                           a_sampled->len - 1, FINE_ELASTICITY);
 166
 167 cleanup:
 168         /* Free stroke data */
 169         stroke_free(a_sampled);
 170         stroke_free(b_sampled);
 171 }
 172
 173 static void sample_average(Sample *sample)
 174 /* Take the distance between the input and the sample, enumerating the best
 175    match assignment between input and sample strokes
 176    TODO scale the measures by stroke distance */
 177 {
 178         Vec2 ic_to_sc;
 179         Sample *smaller;
 180         float distance, m_dist, m_angle;
 181         int i;
 182
 183         /* Ignore disqualified samples */
 184         if ((i = sample_disqualified(sample))) {
 185                 if (i == 2)
 186                         num_disqualified++;
 187                 return;
 188         }
 189
 190         /* Adjust for the difference between sample centers */
 191         center_samples(&ic_to_sc, input, sample);
 192
 193         /* Run the averages */
 194         smaller = input->len < sample->len ? input : sample;
 195         for (i = 0, distance = 0.f, m_dist = 0.f, m_angle = 0.f;
 196              i < smaller->len; i++) {
 197                 Stroke *input_stroke, *sample_stroke;
 198                 float weight, s_dist = MAX_DIST, s_angle = ANGLE_PI;
 199
 200                 /* Transform strokes, mapping the larger sample onto the
 201                    smaller one */
 202                 if (input->len >= sample->len) {
 203                         input_stroke = transform_stroke(input,
 204                                                         &sample->transform, i);
 205                         sample_stroke = sample->strokes[i];
 206                 } else {
 207                         input_stroke = input->strokes[i];
 208                         sample_stroke = transform_stroke(sample,
 209                                                          &sample->transform, i);
 210                 }
 211
 212                 weight = smaller->strokes[i]->spread < DOT_SPREAD ?
 213                          DOT_SPREAD : smaller->strokes[i]->distance;
 214                 stroke_average(input_stroke, sample_stroke,
 215                                &s_dist, &s_angle, &ic_to_sc);
 216                 m_dist += s_dist * weight;
 217                 m_angle += s_angle * weight;
 218                 distance += weight;
 219
 220                 /* Clear the created stroke */
 221                 stroke_free(input->len >= sample->len ?
 222                             input_stroke : sample_stroke);
 223         }
 224
 225         /* Undo square distortion and account for multiple strokes */
 226         m_dist = sqrtf(m_dist) / distance;
 227         m_angle /= distance;
 228
 229         /* Check limits */
 230         if (m_dist > MAX_DIST)
 231                 m_dist = MAX_DIST;
 232         if (m_angle > ANGLE_PI)
 233                 m_angle = ANGLE_PI;
 234
 235         /* Assign the ratings */
 236         sample->ratings[ENGINE_AVGDIST] = RATING_MAX -
 237                                           RATING_MAX * m_dist / MEASURE_DIST;
 238         sample->ratings[ENGINE_AVGANGLE] = RATING_MAX -
 239                                            RATING_MAX * m_angle / MEASURE_ANGLE;
 240 }
 241
 242 void engine_average(void)
 243 /* Computes average distance and angle differences */
 244 {
 245         Sample *sample;
 246         int i;
 247
 248         num_disqualified = 0;
 249         if (!engines[ENGINE_AVGDIST].range &&
 250             !engines[ENGINE_AVGANGLE].range)
 251                 return;
 252
 253         /* Average angle engine needs to be discounted when the input
 254            contains segments too short to produce meaningful angles */
 255         engines[ENGINE_AVGANGLE].scale = 0;
 256         for (i = 0; i < input->len; i++)
 257                 if (input->strokes[i]->spread >= DOT_SPREAD)
 258                         engines[ENGINE_AVGANGLE].scale++;
 259         engines[ENGINE_AVGANGLE].scale = engines[ENGINE_AVGANGLE].scale *
 260                                          ENGINE_SCALE / input->len;
 261
 262         /* Run the averaging engine on every sample */
 263         sampleiter_reset();
 264         while ((sample = sampleiter_next()))
 265                 if (sample->ch)
 266                         sample_average(sample);
 267 }
 268