1 /*---------------------------------------------------------------------------*
2 Project: TwlSDK - PRC -
3 File: prc_algo_superfine.c
4
5 Copyright 2003-2008 Nintendo. All rights reserved.
6
7 These coded instructions, statements, and computer programs contain
8 proprietary information of Nintendo of America Inc. and/or Nintendo
9 Company Ltd., and are protected by Federal copyright law. They may
10 not be disclosed to third parties or copied or duplicated in any form,
11 in whole or in part, without the prior written consent of Nintendo.
12
13 $Date:: 2008-09-18#$
14 $Rev: 8573 $
15 $Author: okubata_ryoma $
16 *---------------------------------------------------------------------------*/
17
18 #include <nitro.h>
19 #include <nitro/prc/algo_superfine.h>
20
21 /*===========================================================================*
22 Prototype Declarations
23 *===========================================================================*/
24
25 static inline u32 PRCi_GetPatternLocalBufferSize_Superfine(void);
26
27 static void
28 PRCi_CalcStrokeDistance_Superfine(fx32 *score,
29 fx32 *weight,
30 const PRCiPatternData_Common *inputData,
31 const PRCiPatternData_Common *protoData,
32 int normalizeSize,
33 int lengthFilterThreshold,
34 int lengthFilterRatio, int iStroke, void *buffer);
35
36 /*===========================================================================*
37 Variable Definitions
38 *===========================================================================*/
39
40 /*===========================================================================*
41 Functions
42 *===========================================================================*/
43
44 /*---------------------------------------------------------------------------*
45 Name: PRC_GetRecognitionBufferSizeEx_Superfine
46
47 Description: Calculates the work area size required for recognition algorithm.
48
49
50 Arguments: maxPointCount: Upper limit of number of input points (includes pen up marker)
51 maxStrokeCount: Upper limit of stroke count
52 protoDB: Sample DB
53 param: Parameters for recognition processing
54
55 Returns: The memory capacity required for the recognition algorithm.
56 *---------------------------------------------------------------------------*/
57 u32
PRC_GetRecognitionBufferSizeEx_Superfine(int maxPointCount,int maxStrokeCount,const PRCPrototypeDB_Superfine * protoDB,const PRCRecognizeParam_Superfine * param)58 PRC_GetRecognitionBufferSizeEx_Superfine(int maxPointCount,
59 int maxStrokeCount,
60 const PRCPrototypeDB_Superfine *protoDB,
61 const PRCRecognizeParam_Superfine *param)
62 {
63 u32 size = 0;
64
65 (void)maxStrokeCount;
66 (void)param;
67
68 if (maxPointCount < protoDB->maxPointCount)
69 {
70 maxPointCount = protoDB->maxPointCount;
71 }
72
73 size += PRCi_ARRAY_SIZE(int, maxPointCount * maxPointCount,);
74 size += PRCi_ARRAY_SIZE(int, maxPointCount * maxPointCount,);
75 size += PRCi_ARRAY_SIZE(int, maxPointCount * maxPointCount,);
76 size += PRCi_ARRAY_SIZE(int, ((maxPointCount + 1) * (maxPointCount + 1)),);
77 size += PRCi_ARRAY_SIZE(int, maxPointCount,);
78 size += PRCi_ARRAY_SIZE(int, maxPointCount,);
79 size += PRCi_ARRAY_SIZE(int, maxPointCount,);
80 size += PRCi_ARRAY_SIZE(int, maxPointCount,);
81 size += PRCi_ARRAY_SIZE(int, maxPointCount + 2,);
82 size += PRCi_ARRAY_SIZE(int, maxPointCount + 2,);
83 return size;
84 }
85
86 /*---------------------------------------------------------------------------*
87 Name: PRC_GetRecognizedEntriesEx_Superfine
88
89 Description: Compares and recognizes a specific kind entry and input pattern to return the top numRanking ranking of the result.
90
91
92 Arguments: resultEntries Pointer to array that holds pointer to recognition result.
93 If less than the requested number could be recognized, fill in remainder with NULL.
94
95 resultScores pointer to recognition result score array
96 numRanking Number of returns to result*
97 buffer Pointer to memory region used by recognition algorithm
98 (Region size >= return value of PRC_GetRecognitionBufferSize)
99 input Input pattern
100 protoDB Sample DB
101 kindMask Carry out logical multiplication of kind value for each sample DB entry, with any non-zero values considered valid.
102
103 param Parameters for recognition processing
104
105 Returns: Number of patterns in the compared sample DBs.
106 *---------------------------------------------------------------------------*/
107 int
PRC_GetRecognizedEntriesEx_Superfine(PRCPrototypeEntry ** resultEntries,fx32 * resultScores,int numRanking,void * buffer,const PRCInputPattern_Superfine * input,const PRCPrototypeDB_Superfine * protoDB,u32 kindMask,const PRCRecognizeParam_Superfine * param)108 PRC_GetRecognizedEntriesEx_Superfine(PRCPrototypeEntry **resultEntries,
109 fx32 *resultScores,
110 int numRanking,
111 void *buffer,
112 const PRCInputPattern_Superfine *input,
113 const PRCPrototypeDB_Superfine *protoDB,
114 u32 kindMask, const PRCRecognizeParam_Superfine *param)
115 {
116 int i;
117 const PRCiPatternData_Common *inputData;
118 int numCompared;
119 int normalizeSize;
120 int lengthFilterThreshold, lengthFilterRatio;
121
122 SDK_ASSERT(resultEntries);
123 SDK_ASSERT(resultScores);
124 SDK_ASSERT(input);
125 SDK_ASSERT(protoDB);
126 SDK_ASSERT(numRanking > 0);
127
128 for (i = 0; i < numRanking; i++)
129 {
130 resultEntries[i] = NULL;
131 resultScores[i] = 0;
132 }
133
134 normalizeSize = protoDB->normalizeSize;
135 if (normalizeSize < input->normalizeSize)
136 {
137 normalizeSize = input->normalizeSize;
138 }
139
140 if (param == NULL)
141 {
142 lengthFilterThreshold = PRC_LENGTH_FILTER_DEFAULT_THRESHOLD_SUPERFINE;
143 lengthFilterRatio = PRC_LENGTH_FILTER_DEFAULT_RATIO_SUPERFINE;
144 }
145 else
146 {
147 lengthFilterThreshold = param->lengthFilterThreshold;
148 lengthFilterRatio = param->lengthFilterRatio;
149 }
150
151 inputData = &input->data;
152 numCompared = 0;
153
154 {
155 const PRCiPrototypeEntry_Common *proto;
156 int iPattern;
157
158 proto = protoDB->patterns;
159
160 for (iPattern = 0; iPattern < protoDB->patternCount; iPattern++, proto++)
161 {
162 const PRCiPatternData_Common *protoData;
163 int iStroke;
164 fx32 wholeScore, wholeWeight;
165
166 if (!proto->entry->enabled || !(proto->entry->kind & kindMask))
167 continue;
168
169 protoData = &proto->data;
170
171 if (inputData->strokeCount != protoData->strokeCount)
172 continue;
173
174 numCompared++;
175 wholeScore = 0;
176 wholeWeight = 0;
177
178 for (iStroke = 0; iStroke < inputData->strokeCount; iStroke++)
179 {
180 fx32 score, weight;
181
182 score = 0;
183
184 PRCi_CalcStrokeDistance_Superfine(&score, &weight, inputData, protoData,
185 normalizeSize, lengthFilterThreshold,
186 lengthFilterRatio, iStroke, buffer);
187
188 wholeScore += score;
189 wholeWeight += weight;
190 }
191
192 wholeScore = FX_Div(wholeScore, wholeWeight * normalizeSize * 2); // normalizeSize*2 == doubleWidth
193
194 if (wholeScore < 0)
195 wholeScore = 0;
196 if (wholeScore >= FX32_ONE)
197 wholeScore = FX32_ONE;
198 if (proto->entry->correction != 0)
199 {
200 wholeScore = FX_Mul(wholeScore, FX32_ONE - proto->entry->correction)
201 + proto->entry->correction;
202 }
203
204 if (resultScores[numRanking - 1] < wholeScore)
205 {
206 resultScores[numRanking - 1] = wholeScore;
207 resultEntries[numRanking - 1] = (PRCPrototypeEntry *)proto->entry;
208 for (i = numRanking - 2; i >= 0; i--)
209 {
210 if (resultScores[i] < resultScores[i + 1])
211 {
212 fx32 tmpScore;
213 PRCPrototypeEntry *tmpEntry;
214 tmpScore = resultScores[i];
215 resultScores[i] = resultScores[i + 1];
216 resultScores[i + 1] = tmpScore;
217 tmpEntry = resultEntries[i];
218 resultEntries[i] = resultEntries[i + 1];
219 resultEntries[i + 1] = tmpEntry;
220 }
221 }
222 }
223 }
224 }
225
226 return numCompared;
227 }
228
229 /*===========================================================================*
230 Static Functions
231 *===========================================================================*/
232 #define PRCi_SINGLE_ANGLE_SCORE 128
233
CityBlockDistance(const PRCPoint * p1,const PRCPoint * p2)234 static inline int CityBlockDistance(const PRCPoint *p1, const PRCPoint *p2)
235 {
236 int x = p1->x - p2->x;
237 int y = p1->y - p2->y;
238 if (x < 0)
239 x = -x;
240 if (y < 0)
241 y = -y;
242 return (x + y);
243 }
244
245 static inline void
GetMixedPoint(PRCPoint * p,const PRCPoint * p1,int w1,const PRCPoint * p2,int w2)246 GetMixedPoint(PRCPoint *p, const PRCPoint *p1, int w1, const PRCPoint *p2, int w2)
247 {
248 int a, w;
249 a = (p1->x * w1 + p2->x * w2);
250 SDK_ASSERTMSG(a >= 0, "a < 0: (%d, %d)*%d-(%d, %d)*%d", p1->x, p1->y, w1, p2->x, p2->y, w2);
251 w = w1 + w2;
252 SDK_ASSERTMSG(w > 0, "w <= 0: (%d, %d)*%d-(%d, %d)*%d", p1->x, p1->y, w1, p2->x, p2->y, w2);
253 {
254 OSIntrMode enabled;
255 enabled = OS_DisableInterrupts();
256
257 CP_SetDiv32_32((u32)a, (u32)w);
258 a = (p1->y * w1 + p2->y * w2);
259 p->x = CP_GetDivResult16();
260 CP_SetDiv32_32((u32)a, (u32)w);
261 p->y = CP_GetDivResult16();
262
263 (void)OS_RestoreInterrupts(enabled);
264 }
265 }
266
267 #define PRCi_ABS(x) (((x)>=0)?(x):-(x))
268 //#define PRCi_ANGLE_SCORE(input, proto) ((32768-PRCi_ABS((s16)(protoAngles[(proto)]-inputAngles[(input)])))/128)
269 //#define PRCi_ANGLE_SCORE(input, proto) ((32768*32768-((s16)(protoAngles[(proto)]-inputAngles[(input)]))*((s16)(protoAngles[(proto)]-inputAngles[(input)])))/(128*32768))
270 // See the above. The further up it goes, the faster it becomes. Precision does not drop that much.
271 #define PRCi_ANGLE_SCORE(input, proto) ((FX_CosIdx((u16)(protoAngles[(proto)]-inputAngles[(input)]))+FX32_ONE)/(FX32_ONE*2/256))
272
273 static void
PRCi_CalcStrokeDistance_Superfine(fx32 * score,fx32 * weight,const PRCiPatternData_Common * inputData,const PRCiPatternData_Common * protoData,int normalizeSize,int lengthFilterThreshold,int lengthFilterRatio,int iStroke,void * buffer)274 PRCi_CalcStrokeDistance_Superfine(fx32 *score,
275 fx32 *weight,
276 const PRCiPatternData_Common *inputData,
277 const PRCiPatternData_Common *protoData,
278 int normalizeSize,
279 int lengthFilterThreshold,
280 int lengthFilterRatio, int iStroke, void *buffer)
281 {
282 #define nMatches_(x,y) (*(nMatches + (x) * maxPointCount + (y)))
283 #define sumScore_(x,y) (*(sumScore + (x) * maxPointCount + (y)))
284 #define direction_(x,y) (*(direction + (x) * maxPointCount + (y)))
285 #define angleScores_(x,y) (*(angleScores + (x) * (maxPointCount+1) + (y)))
286
287 // Calculate the degree of similarity between strokes, with DP matching
288 int iInput, iProto;
289 int *nMatches; //[STROKE_PACKED_POINT_MAX][STROKE_PACKED_POINT_MAX];
290 int *sumScore; //[STROKE_PACKED_POINT_MAX][STROKE_PACKED_POINT_MAX];
291 int *direction; //[STROKE_PACKED_POINT_MAX][STROKE_PACKED_POINT_MAX];
292 int *angleScores; //[STROKE_PACKED_POINT_MAX+1][STROKE_PACKED_POINT_MAX+1];
293
294 int *inputPair; //[STROKE_PACKED_POINT_MAX];
295 int *inputMaxScore; //[STROKE_PACKED_POINT_MAX];
296 int *protoPair; //[STROKE_PACKED_POINT_MAX];
297 int *protoMaxScore; //[STROKE_PACKED_POINT_MAX];
298 int *inputMatch; //[STROKE_PACKED_POINT_MAX+2];
299 int *protoMatch; //[STROKE_PACKED_POINT_MAX+2];
300
301 int protoStrokeIndex, inputStrokeIndex;
302 int protoSize, inputSize;
303 const PRCPoint *protoPoints;
304 const PRCPoint *inputPoints;
305 const u16 *protoAngles;
306 const u16 *inputAngles;
307 const fx16 *protoRatios;
308 const fx16 *inputRatios;
309 const fx32 *protoLengths;
310 const fx32 *inputLengths;
311 fx32 protoStrokeLength, inputStrokeLength;
312 fx32 protoStrokeRatio, inputStrokeRatio;
313 int maxPointCount;
314 int doubleWidth;
315
316 maxPointCount = inputData->pointCount;
317 if (maxPointCount < protoData->pointCount)
318 maxPointCount = protoData->pointCount;
319
320 #ifdef SDK_DEBUG
321 {
322 int width, tmp;
323
324 width = inputData->wholeBoundingBox.x2 - inputData->wholeBoundingBox.x1;
325 tmp = inputData->wholeBoundingBox.y2 - inputData->wholeBoundingBox.y1;
326 if (tmp > width)
327 width = tmp;
328 tmp = protoData->wholeBoundingBox.x2 - protoData->wholeBoundingBox.x1;
329 if (tmp > width)
330 width = tmp;
331 tmp = protoData->wholeBoundingBox.y2 - protoData->wholeBoundingBox.y1;
332 if (tmp > width)
333 width = tmp;
334
335 width++;
336 if (width > normalizeSize)
337 {
338 OS_Warning
339 ("too small normalizeSize. PRCPrototypeList.normalizeSize seems too smaller than actual data.");
340 }
341 }
342 #endif
343 doubleWidth = normalizeSize * 2;
344
345 // Allocate the buffer
346 {
347 int addr;
348 addr = 0;
349 PRCi_ALLOC_ARRAY(nMatches, int, maxPointCount * maxPointCount, buffer, addr);
350 PRCi_ALLOC_ARRAY(sumScore, int, maxPointCount * maxPointCount, buffer, addr);
351 PRCi_ALLOC_ARRAY(direction, int, maxPointCount * maxPointCount, buffer, addr);
352 PRCi_ALLOC_ARRAY(angleScores,
353 int, ((maxPointCount + 1) * (maxPointCount + 1)), buffer, addr);
354 PRCi_ALLOC_ARRAY(inputPair, int, maxPointCount, buffer, addr);
355 PRCi_ALLOC_ARRAY(inputMaxScore, int, maxPointCount, buffer, addr);
356 PRCi_ALLOC_ARRAY(protoPair, int, maxPointCount, buffer, addr);
357 PRCi_ALLOC_ARRAY(protoMaxScore, int, maxPointCount, buffer, addr);
358 PRCi_ALLOC_ARRAY(inputMatch, int, maxPointCount + 2, buffer, addr);
359 PRCi_ALLOC_ARRAY(protoMatch, int, maxPointCount + 2, buffer, addr);
360 }
361
362 protoStrokeIndex = protoData->strokes[iStroke];
363 inputStrokeIndex = inputData->strokes[iStroke];
364 protoSize = protoData->strokeSizes[iStroke];
365 inputSize = inputData->strokeSizes[iStroke];
366 protoPoints = &protoData->pointArray[protoStrokeIndex];
367 inputPoints = &inputData->pointArray[inputStrokeIndex];
368 protoAngles = &protoData->lineSegmentAngleArray[protoStrokeIndex];
369 inputAngles = &inputData->lineSegmentAngleArray[inputStrokeIndex];
370 protoRatios = &protoData->lineSegmentRatioToStrokeArray[protoStrokeIndex];
371 inputRatios = &inputData->lineSegmentRatioToStrokeArray[inputStrokeIndex];
372 protoLengths = &protoData->lineSegmentLengthArray[protoStrokeIndex];
373 inputLengths = &inputData->lineSegmentLengthArray[inputStrokeIndex];
374 protoStrokeLength = protoData->strokeLengths[iStroke];
375 inputStrokeLength = inputData->strokeLengths[iStroke];
376 protoStrokeRatio = protoData->strokeRatios[iStroke];
377 inputStrokeRatio = inputData->strokeRatios[iStroke];
378
379 *weight = FX32_ONE;
380 *score = 0;
381
382 if (protoSize == 0 || inputSize == 0)
383 return;
384
385 // Line segments whose length are too different will have their similarity set at 0, and no further calculation will be done
386 if (inputStrokeLength > lengthFilterThreshold || protoStrokeLength > lengthFilterThreshold)
387 {
388 if (inputStrokeLength * lengthFilterRatio < protoStrokeLength
389 || protoStrokeLength * lengthFilterRatio < inputStrokeLength)
390 {
391 #ifdef PRC_DEBUG_RECOGNIZE_DEEPLY
392 OS_Printf("Skipped because of length filter %d <=> %d\n", FX_Whole(inputStrokeLength),
393 FX_Whole(protoStrokeLength));
394 #endif
395 return;
396 }
397 }
398
399 // Calculates angleScores[][] in advance, which is scores relating to angles
400 if (protoSize == 1 || inputSize == 1)
401 {
402 for (iInput = 0; iInput < inputSize; iInput++)
403 {
404 for (iProto = 0; iProto < protoSize; iProto++)
405 {
406 angleScores_(iInput, iProto) = PRCi_SINGLE_ANGLE_SCORE;
407 }
408 }
409 }
410 else
411 {
412 angleScores_(0, 0) = PRCi_ANGLE_SCORE(1, 1);
413 angleScores_(inputSize, 0) = PRCi_ANGLE_SCORE(inputSize - 1, 1);
414 angleScores_(0, protoSize) = PRCi_ANGLE_SCORE(1, protoSize - 1);
415 angleScores_(inputSize, protoSize) = PRCi_ANGLE_SCORE(inputSize - 1, protoSize - 1);
416
417 for (iInput = 1; iInput < inputSize; iInput++)
418 {
419 angleScores_(iInput, 0) = PRCi_ANGLE_SCORE(iInput, 1);
420 angleScores_(iInput, protoSize) = PRCi_ANGLE_SCORE(iInput, protoSize - 1);
421 }
422 for (iProto = 1; iProto < protoSize; iProto++)
423 {
424 angleScores_(0, iProto) = PRCi_ANGLE_SCORE(1, iProto);
425 angleScores_(inputSize, iProto) = PRCi_ANGLE_SCORE(inputSize - 1, iProto);
426 }
427
428 for (iInput = 1; iInput < inputSize; iInput++)
429 {
430 for (iProto = 1; iProto < protoSize; iProto++)
431 {
432 angleScores_(iInput, iProto) = PRCi_ANGLE_SCORE(iInput, iProto);
433 }
434 }
435 }
436
437 // Use DP matching to find corresponding points between strokes
438 sumScore_(0, 0) =
439 (doubleWidth - CityBlockDistance(&inputPoints[0], &protoPoints[0])) * angleScores_(0,
440 0) * 2;
441 nMatches_(0, 0) = 1;
442 for (iInput = 1; iInput < inputSize; iInput++)
443 {
444 sumScore_(iInput, 0) =
445 (doubleWidth -
446 CityBlockDistance(&inputPoints[iInput], &protoPoints[0])) * (angleScores_(iInput,
447 0) +
448 angleScores_(iInput + 1,
449 1)) +
450 sumScore_(iInput - 1, 0);
451 nMatches_(iInput, 0) = nMatches_(iInput - 1, 0) + 1;
452 direction_(iInput, 0) = 2;
453 }
454 for (iProto = 1; iProto < protoSize; iProto++)
455 {
456 sumScore_(0, iProto) =
457 (doubleWidth -
458 CityBlockDistance(&inputPoints[0], &protoPoints[iProto])) * (angleScores_(0,
459 iProto) +
460 angleScores_(1,
461 iProto +
462 1)) +
463 sumScore_(0, iProto - 1);
464 nMatches_(0, iProto) = nMatches_(0, iProto - 1) + 1;
465 direction_(0, iProto) = 1;
466 }
467
468 for (iInput = 1; iInput < inputSize; iInput++)
469 {
470 for (iProto = 1; iProto < protoSize; iProto++)
471 {
472 int sum, n, localScore;
473 int sumMax, nMax, dirMax;
474
475 localScore =
476 (doubleWidth
477 - CityBlockDistance(&inputPoints[iInput], &protoPoints[iProto]))
478 * (angleScores_(iInput, iProto) + angleScores_(iInput + 1, iProto + 1));
479
480 dirMax = 0;
481 sumMax = localScore + sumScore_(iInput - 1, iProto - 1);
482 nMax = nMatches_(iInput - 1, iProto - 1) + 1;
483
484 sum = localScore + sumScore_(iInput, iProto - 1);
485 n = nMatches_(iInput, iProto - 1) + 1;
486 if (sum * nMax > sumMax * n)
487 {
488 sumMax = sum;
489 nMax = n;
490 dirMax = 1;
491 }
492
493 sum = localScore + sumScore_(iInput - 1, iProto);
494 n = nMatches_(iInput - 1, iProto) + 1;
495 if (sum * nMax > sumMax * n)
496 {
497 sumMax = sum;
498 nMax = n;
499 dirMax = 2;
500 }
501
502 sumScore_(iInput, iProto) = sumMax;
503 nMatches_(iInput, iProto) = nMax;
504 direction_(iInput, iProto) = dirMax;
505 }
506 }
507
508 #ifdef PRC_DEBUG_RECOGNIZE
509 {
510 int localScore, angleScore;
511 iInput = inputSize - 1;
512 iProto = protoSize - 1;
513 while (!(iInput == 0 && iProto == 0))
514 {
515 int dx, dy;
516 dx = -1 + (direction_(iInput, iProto) & 1);
517 dy = -1 + ((direction_(iInput, iProto) & 2) >> 1);
518 localScore = sumScore_(iInput, iProto) - sumScore_(iInput + dx, iProto + dy);
519 angleScore = angleScores_(iInput, iProto) + angleScores_(iInput + 1, iProto + 1);
520
521 OS_Printf(" %2d <-> %2d : 0.%03d = 0.%03d * 0.%03d, average from begin: 0.%03d\n",
522 iInput, iProto, localScore / normalizeSize,
523 localScore * 512 / angleScore / normalizeSize, angleScore * 2,
524 sumScore_(iInput, iProto) / nMatches_(iInput, iProto) / normalizeSize);
525
526 iInput += dx;
527 iProto += dy;
528 }
529 localScore = sumScore_(iInput, iProto);
530 angleScore = angleScores_(iInput, iProto) + angleScores_(iInput + 1, iProto + 1);
531 OS_Printf(" %2d <-> %2d : 0.%03d = 0.%03d * 0.%03d\n", iInput, iProto,
532 localScore / normalizeSize, localScore * 512 / angleScore / normalizeSize,
533 angleScore * 2);
534 }
535
536 OS_Printf("total: %d, matches: %d\n", sumScore_(inputSize - 1, protoSize - 1),
537 nMatches_(inputSize - 1, protoSize - 1));
538 #endif
539
540 // Similarity calculation phase
541 {
542 int iMatch;
543 int localScore;
544 int nMatches;
545 fx32 weightedScore, totalWeight;
546
547 // First, extract a pair that matches for certain
548 for (iInput = 0; iInput < inputSize; iInput++)
549 {
550 inputPair[iInput] = -1;
551 inputMaxScore[iInput] = -1;
552 }
553
554 for (iProto = 0; iProto < protoSize; iProto++)
555 {
556 protoPair[iProto] = -1;
557 protoMaxScore[iProto] = -1;
558 }
559
560 iInput = inputSize - 1;
561 iProto = protoSize - 1;
562 while (!(iInput == 0 && iProto == 0))
563 {
564 int dx, dy;
565 dx = -1 + (direction_(iInput, iProto) & 1);
566 dy = -1 + ((direction_(iInput, iProto) & 2) >> 1);
567 localScore = sumScore_(iInput, iProto) - sumScore_(iInput + dx, iProto + dy);
568
569 if (inputMaxScore[iInput] < localScore)
570 {
571 inputPair[iInput] = iProto;
572 inputMaxScore[iInput] = localScore;
573 }
574
575 if (protoMaxScore[iProto] < localScore)
576 {
577 protoPair[iProto] = iInput;
578 protoMaxScore[iProto] = localScore;
579 }
580
581 iInput += dx;
582 iProto += dy;
583 }
584 // Processing of iInput==0 && iProto==0
585 localScore = sumScore_(iInput, iProto);
586 if (inputMaxScore[iInput] < localScore)
587 {
588 inputPair[iInput] = iProto;
589 inputMaxScore[iInput] = localScore;
590 }
591
592 if (protoMaxScore[iProto] < localScore)
593 {
594 protoPair[iProto] = iInput;
595 protoMaxScore[iProto] = localScore;
596 }
597
598
599 // One-way matches are eliminated
600 for (iInput = 0; iInput < inputSize; iInput++)
601 {
602 int pair = inputPair[iInput];
603 if (pair >= 0)
604 {
605 // Is this one (the self) the ideal pairing for the other one?
606 if (protoPair[pair] != iInput)
607 {
608 inputPair[iInput] = -1;
609 }
610 }
611 }
612
613 nMatches = 0;
614 inputMatch[nMatches] = 0;
615 protoMatch[nMatches] = 0;
616 nMatches++;
617 for (iInput = 0; iInput < inputSize; iInput++)
618 {
619 if (inputPair[iInput] >= 0)
620 {
621 inputMatch[nMatches] = iInput;
622 protoMatch[nMatches] = inputPair[iInput];
623 nMatches++;
624 }
625 }
626 inputMatch[nMatches] = inputSize - 1;
627 protoMatch[nMatches] = protoSize - 1;
628 nMatches++;
629
630 #ifdef PRC_DEBUG_RECOGNIZE
631 OS_Printf("-----\n");
632 for (iMatch = 0; iMatch < nMatches; iMatch++)
633 {
634 OS_Printf(" <%d> v <%d>\n", inputMatch[iMatch], protoMatch[iMatch]);
635 }
636 #endif
637 //#define PRC_DEBUG_RECOGNIZE_DEEPLY
638 weightedScore = 0;
639 totalWeight = 0;
640 for (iMatch = 0; iMatch < nMatches - 1; iMatch++)
641 {
642 fx32 inputLocalLength, protoLocalLength;
643 fx32 inputCurrentLength, protoCurrentLength;
644 fx32 inputPrevSumRatio, protoPrevSumRatio;
645 fx32 localScore;
646 fx32 weight, tmp;
647 fx32 inputNextRatio, protoNextRatio;
648 fx32 inputOrigNextRatio, protoOrigNextRatio;
649 int loopEnd, i;
650 #ifdef PRC_DEBUG_RECOGNIZE_DEEPLY
651 OS_Printf(" [%d, %d] - [%d, %d]\n", inputMatch[iMatch], protoMatch[iMatch],
652 inputMatch[iMatch + 1], protoMatch[iMatch + 1]);
653 #endif
654 inputLocalLength = 0;
655 protoLocalLength = 0;
656 for (iInput = inputMatch[iMatch] + 1; iInput <= inputMatch[iMatch + 1]; iInput++)
657 {
658 inputLocalLength += inputLengths[iInput];
659 }
660 for (iProto = protoMatch[iMatch] + 1; iProto <= protoMatch[iMatch + 1]; iProto++)
661 {
662 protoLocalLength += protoLengths[iProto];
663 }
664 if (inputLocalLength == 0 && protoLocalLength == 0)
665 {
666 // The corresponding points [0, 0] [0, 0] can only have duplicates in the beginning
667 continue;
668 }
669 iInput = inputMatch[iMatch] + 1;
670 iProto = protoMatch[iMatch] + 1;
671 inputCurrentLength = inputLengths[iInput];
672 protoCurrentLength = protoLengths[iProto];
673 if (inputLocalLength == 0)
674 {
675 inputLocalLength = inputCurrentLength = 1;
676 iInput = inputMatch[iMatch + 1];
677 }
678 if (protoLocalLength == 0)
679 {
680 protoLocalLength = protoCurrentLength = 1;
681 iProto = protoMatch[iMatch + 1];
682 }
683 inputPrevSumRatio = inputOrigNextRatio = inputNextRatio =
684 FX_Div(inputCurrentLength, inputLocalLength);
685 protoPrevSumRatio = protoOrigNextRatio = protoNextRatio =
686 FX_Div(protoCurrentLength, protoLocalLength);
687 localScore = 0;
688 loopEnd = (inputMatch[iMatch + 1] - iInput) + (protoMatch[iMatch + 1] - iProto) + 1;
689 #ifdef PRC_DEBUG_RECOGNIZE_DEEPLY
690 OS_Printf("length: %d, %d\n", inputLocalLength, protoLocalLength);
691 #endif
692 for (i = 0; i < loopEnd; i++)
693 {
694 #ifdef PRC_DEBUG_RECOGNIZE_DEEPLY
695 OS_Printf(" [%d, %d]", iInput, iProto);
696 OS_Printf(" Ratio: %3d %3d\n", FX_Whole(inputNextRatio * 100),
697 FX_Whole(protoNextRatio * 100));
698 #endif
699 SDK_ASSERTMSG(iInput <= inputMatch[iMatch + 1],
700 "iInput(%d) > inputMatch[iMatch+1](%d)\n", iInput,
701 inputMatch[iMatch + 1]);
702 SDK_ASSERTMSG(iProto <= protoMatch[iMatch + 1],
703 "iProto(%d) > protoMatch[iMatch+1](%d)\n", iProto,
704 protoMatch[iMatch + 1]);
705 if (inputNextRatio <= protoNextRatio)
706 {
707 fx32 ratio;
708 PRCPoint protoPoint;
709 #ifdef PRC_DEBUG_RECOGNIZE_DEEPLY
710 OS_Printf(" inc iInput: score=%d, ratio=%d\n",
711 FX_Whole(inputNextRatio * (angleScores_(iInput, iProto))),
712 FX_Whole(100 * inputNextRatio));
713 #endif
714 protoNextRatio -= inputNextRatio;
715 if (iProto > 0)
716 {
717 GetMixedPoint(&protoPoint, &protoPoints[iProto - 1], protoNextRatio,
718 &protoPoints[iProto], protoOrigNextRatio - protoNextRatio);
719 }
720 else
721 {
722 protoPoint = protoPoints[iProto];
723 }
724
725 inputCurrentLength += inputLengths[iInput + 1];
726 FX_DivAsync(inputCurrentLength, inputLocalLength);
727
728 #ifdef PRC_DEBUG_CHECK_OVERFLOW
729 {
730 fx32 prevScore = localScore;
731 #endif
732 localScore += inputNextRatio * (angleScores_(iInput, iProto))
733 * (doubleWidth - CityBlockDistance(&inputPoints[iInput], &protoPoint));
734 #ifdef PRC_DEBUG_CHECK_OVERFLOW
735 if (prevScore > localScore)
736 OS_Warning("Internal Error: score overflow\n");
737 }
738 #endif
739
740 iInput++;
741 ratio = FX_GetDivResult();
742 inputOrigNextRatio = inputNextRatio = ratio - inputPrevSumRatio;
743 inputPrevSumRatio = ratio;
744 }
745 else
746 {
747 fx32 ratio;
748 PRCPoint inputPoint;
749 #ifdef PRC_DEBUG_RECOGNIZE_DEEPLY
750 OS_Printf(" inc iProto: score=%d, length=%d\n",
751 FX_Whole(protoNextRatio * (angleScores_(iInput, iProto))),
752 FX_Whole(100 * protoNextRatio));
753 #endif
754 inputNextRatio -= protoNextRatio;
755 if (iInput > 0)
756 {
757 GetMixedPoint(&inputPoint, &inputPoints[iInput - 1], inputNextRatio,
758 &inputPoints[iInput], inputOrigNextRatio - inputNextRatio);
759 }
760 else
761 {
762 inputPoint = inputPoints[iInput];
763 }
764
765 protoCurrentLength += protoLengths[iProto + 1];
766 FX_DivAsync(protoCurrentLength, protoLocalLength);
767
768 #ifdef PRC_DEBUG_CHECK_OVERFLOW
769 {
770 fx32 prevScore = localScore;
771 #endif
772 localScore += protoNextRatio * (angleScores_(iInput, iProto))
773 * (doubleWidth - CityBlockDistance(&protoPoints[iProto], &inputPoint));
774 #ifdef PRC_DEBUG_CHECK_OVERFLOW
775 if (prevScore > localScore)
776 OS_Warning("Internal Error: score overflow\n");
777 }
778 #endif
779
780 iProto++;
781 ratio = FX_GetDivResult();
782 protoOrigNextRatio = protoNextRatio = ratio - protoPrevSumRatio;
783 protoPrevSumRatio = ratio;
784 }
785 }
786
787 weight = FX_Div(inputLocalLength, inputStrokeLength);
788 tmp = FX_Div(protoLocalLength, protoStrokeLength);
789 if (weight < tmp)
790 {
791 weight = tmp;
792 }
793 weightedScore += FX_Mul(localScore / 256, weight);
794 SDK_ASSERTMSG(weight != 0,
795 "inputStrokeLength: %d, inputLocalLength: %d, protoStrokeLength: %d, protoLocalLength: %d\n",
796 inputStrokeLength, inputLocalLength, protoStrokeLength, protoLocalLength);
797 totalWeight += weight;
798 }
799 SDK_ASSERTMSG(totalWeight != 0, "nMatches: %d", nMatches);
800 {
801 fx32 ratio;
802 ratio = (inputStrokeRatio >= protoStrokeRatio) ? inputStrokeRatio : protoStrokeRatio;
803 *score = FX_Mul(weightedScore, ratio);
804 *weight = FX_Mul(totalWeight, ratio);
805 }
806 }
807 }
808
809
810 /*---------------------------------------------------------------------------*
811 End of file
812 *---------------------------------------------------------------------------*/
813