1 /******************************************************************************
2 ** Filename: intmatcher.c
3 ** Purpose: Generic high level classification routines.
4 ** Author: Robert Moss
5 ** History: Wed Feb 13 17:35:28 MST 1991, RWM, Created.
6 ** Mon Mar 11 16:33:02 MST 1991, RWM, Modified to add
7 ** support for adaptive matching.
8 ** (c) Copyright Hewlett-Packard Company, 1988.
9 ** Licensed under the Apache License, Version 2.0 (the "License");
10 ** you may not use this file except in compliance with the License.
11 ** You may obtain a copy of the License at
12 ** http://www.apache.org/licenses/LICENSE-2.0
13 ** Unless required by applicable law or agreed to in writing, software
14 ** distributed under the License is distributed on an "AS IS" BASIS,
15 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16 ** See the License for the specific language governing permissions and
17 ** limitations under the License.
18 ******************************************************************************/
19 /**----------------------------------------------------------------------------
20 Include Files and Type Defines
21 ----------------------------------------------------------------------------**/
22 #include "intmatcher.h"
23 #include "intproto.h"
24 #include "tordvars.h"
25 #include "callcpp.h"
26 #include "scrollview.h"
27 #include "globals.h"
28 #include "classify.h"
29 #include <math.h>
30
31 #define CLASS_MASK_SIZE ((MAX_NUM_CLASSES*NUM_BITS_PER_CLASS \
32 +BITS_PER_WERD-1)/BITS_PER_WERD)
33
34 /**----------------------------------------------------------------------------
35 Global Data Definitions and Declarations
36 ----------------------------------------------------------------------------**/
37 #define SE_TABLE_BITS 9
38 #define SE_TABLE_SIZE 512
39 #define TEMPLATE_CACHE 2
40 static uinT8 SimilarityEvidenceTable[SE_TABLE_SIZE];
41 static uinT8 offset_table[256] = {
42 255, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
43 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
44 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
45 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
46 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
47 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
48 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
49 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
50 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
51 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
52 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
53 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
54 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
55 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
56 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
57 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
58 };
59 static uinT8 next_table[256] = {
60 0, 0, 0, 0x2, 0, 0x4, 0x4, 0x6, 0, 0x8, 0x8, 0x0a, 0x08, 0x0c, 0x0c, 0x0e,
61 0, 0x10, 0x10, 0x12, 0x10, 0x14, 0x14, 0x16, 0x10, 0x18, 0x18, 0x1a, 0x18,
62 0x1c, 0x1c, 0x1e,
63 0, 0x20, 0x20, 0x22, 0x20, 0x24, 0x24, 0x26, 0x20, 0x28, 0x28, 0x2a, 0x28,
64 0x2c, 0x2c, 0x2e,
65 0x20, 0x30, 0x30, 0x32, 0x30, 0x34, 0x34, 0x36, 0x30, 0x38, 0x38, 0x3a,
66 0x38, 0x3c, 0x3c, 0x3e,
67 0, 0x40, 0x40, 0x42, 0x40, 0x44, 0x44, 0x46, 0x40, 0x48, 0x48, 0x4a, 0x48,
68 0x4c, 0x4c, 0x4e,
69 0x40, 0x50, 0x50, 0x52, 0x50, 0x54, 0x54, 0x56, 0x50, 0x58, 0x58, 0x5a,
70 0x58, 0x5c, 0x5c, 0x5e,
71 0x40, 0x60, 0x60, 0x62, 0x60, 0x64, 0x64, 0x66, 0x60, 0x68, 0x68, 0x6a,
72 0x68, 0x6c, 0x6c, 0x6e,
73 0x60, 0x70, 0x70, 0x72, 0x70, 0x74, 0x74, 0x76, 0x70, 0x78, 0x78, 0x7a,
74 0x78, 0x7c, 0x7c, 0x7e,
75 0, 0x80, 0x80, 0x82, 0x80, 0x84, 0x84, 0x86, 0x80, 0x88, 0x88, 0x8a, 0x88,
76 0x8c, 0x8c, 0x8e,
77 0x80, 0x90, 0x90, 0x92, 0x90, 0x94, 0x94, 0x96, 0x90, 0x98, 0x98, 0x9a,
78 0x98, 0x9c, 0x9c, 0x9e,
79 0x80, 0xa0, 0xa0, 0xa2, 0xa0, 0xa4, 0xa4, 0xa6, 0xa0, 0xa8, 0xa8, 0xaa,
80 0xa8, 0xac, 0xac, 0xae,
81 0xa0, 0xb0, 0xb0, 0xb2, 0xb0, 0xb4, 0xb4, 0xb6, 0xb0, 0xb8, 0xb8, 0xba,
82 0xb8, 0xbc, 0xbc, 0xbe,
83 0x80, 0xc0, 0xc0, 0xc2, 0xc0, 0xc4, 0xc4, 0xc6, 0xc0, 0xc8, 0xc8, 0xca,
84 0xc8, 0xcc, 0xcc, 0xce,
85 0xc0, 0xd0, 0xd0, 0xd2, 0xd0, 0xd4, 0xd4, 0xd6, 0xd0, 0xd8, 0xd8, 0xda,
86 0xd8, 0xdc, 0xdc, 0xde,
87 0xc0, 0xe0, 0xe0, 0xe2, 0xe0, 0xe4, 0xe4, 0xe6, 0xe0, 0xe8, 0xe8, 0xea,
88 0xe8, 0xec, 0xec, 0xee,
89 0xe0, 0xf0, 0xf0, 0xf2, 0xf0, 0xf4, 0xf4, 0xf6, 0xf0, 0xf8, 0xf8, 0xfa,
90 0xf8, 0xfc, 0xfc, 0xfe
91 };
92
93 static uinT32 EvidenceTableMask;
94
95 static uinT32 MultTruncShiftBits;
96
97 static uinT32 TableTruncShiftBits;
98
99 uinT32 EvidenceMultMask;
100
101 static inT16 LocalMatcherMultiplier;
102
103 INT_VAR(classify_class_pruner_threshold, 229,
104 "Class Pruner Threshold 0-255: ");
105
106 INT_VAR(classify_class_pruner_multiplier, 30,
107 "Class Pruner Multiplier 0-255: ");
108
109 INT_VAR(classify_integer_matcher_multiplier, 14,
110 "Integer Matcher Multiplier 0-255: ");
111
112 INT_VAR(classify_int_theta_fudge, 128,
113 "Integer Matcher Theta Fudge 0-255: ");
114
115 INT_VAR(classify_cp_cutoff_strength, 7,
116 "Class Pruner CutoffStrength: ");
117
118 INT_VAR(classify_evidence_table_bits, 9,
119 "Bits in Similarity to Evidence Lookup 8-9: ");
120
121 INT_VAR(classify_int_evidence_trunc_bits, 14,
122 "Integer Evidence Truncation Bits (Distance) 8-14: ");
123
124 double_VAR(classify_se_exponential_multiplier, 0,
125 "Similarity to Evidence Table Exponential Multiplier: ");
126
127 double_VAR(classify_similarity_center, 0.0075,
128 "Center of Similarity Curve: ");
129
130 INT_VAR(classify_adapt_proto_thresh, 230,
131 "Threshold for good protos during adaptive 0-255: ");
132
133 INT_VAR(classify_adapt_feature_thresh, 230,
134 "Threshold for good features during adaptive 0-255: ");
135
136 BOOL_VAR(disable_character_fragments, FALSE,
137 "Do not include character fragments in the"
138 " results of the classifier");
139
140 BOOL_VAR(matcher_debug_separate_windows, FALSE,
141 "Use two different windows for debugging the matching: "
142 "One for the protos and one for the features.");
143
144 int protoword_lookups;
145 int zero_protowords;
146 int proto_shifts;
147 int set_proto_bits;
148 int config_shifts;
149 int set_config_bits;
150
151 /**----------------------------------------------------------------------------
152 Public Code
153 ----------------------------------------------------------------------------**/
154 /*---------------------------------------------------------------------------*/
155 namespace tesseract {
ClassPruner(INT_TEMPLATES IntTemplates,inT16 NumFeatures,INT_FEATURE_ARRAY Features,CLASS_NORMALIZATION_ARRAY NormalizationFactors,CLASS_CUTOFF_ARRAY ExpectedNumFeatures,CLASS_PRUNER_RESULTS Results,int Debug)156 int Classify::ClassPruner(INT_TEMPLATES IntTemplates,
157 inT16 NumFeatures,
158 INT_FEATURE_ARRAY Features,
159 CLASS_NORMALIZATION_ARRAY NormalizationFactors,
160 CLASS_CUTOFF_ARRAY ExpectedNumFeatures,
161 CLASS_PRUNER_RESULTS Results,
162 int Debug) {
163 /*
164 ** Parameters:
165 ** IntTemplates Class pruner tables
166 ** NumFeatures Number of features in blob
167 ** Features Array of features
168 ** NormalizationFactors Array of fudge factors from blob
169 ** normalization process
170 ** (by CLASS_INDEX)
171 ** ExpectedNumFeatures Array of expected number of features
172 ** for each class
173 ** (by CLASS_INDEX)
174 ** Results Sorted Array of pruned classes
175 ** (by CLASS_ID)
176 ** Debug Debugger flag: 1=debugger on
177 ** Globals:
178 ** classify_class_pruner_threshold Cutoff threshold
179 ** classify_class_pruner_multiplier Normalization factor multiplier
180 ** Operation:
181 ** Prune the classes using a modified fast match table.
182 ** Return a sorted list of classes along with the number
183 ** of pruned classes in that list.
184 ** Return: Number of pruned classes.
185 ** Exceptions: none
186 ** History: Tue Feb 19 10:24:24 MST 1991, RWM, Created.
187 */
188 uinT32 PrunerWord;
189 inT32 class_index; //index to class
190 int Word;
191 uinT32 *BasePrunerAddress;
192 uinT32 feature_address; //current feature index
193 INT_FEATURE feature; //current feature
194 CLASS_PRUNER *ClassPruner;
195 int PrunerSet;
196 int NumPruners;
197 inT32 feature_index; //current feature
198
199 static int ClassCount[MAX_NUM_CLASSES];
200 static int NormCount[MAX_NUM_CLASSES];
201 static int SortKey[MAX_NUM_CLASSES + 1];
202 static int SortIndex[MAX_NUM_CLASSES + 1];
203 int out_class;
204 int MaxNumClasses;
205 int MaxCount;
206 int NumClasses;
207 FLOAT32 max_rating; //max allowed rating
208 int *ClassCountPtr;
209 CLASS_ID class_id;
210
211 MaxNumClasses = IntTemplates->NumClasses;
212
213 /* Clear Class Counts */
214 ClassCountPtr = &(ClassCount[0]);
215 for (class_id = 0; class_id < MaxNumClasses; class_id++) {
216 *ClassCountPtr++ = 0;
217 }
218
219 /* Update Class Counts */
220 NumPruners = IntTemplates->NumClassPruners;
221 for (feature_index = 0; feature_index < NumFeatures; feature_index++) {
222 feature = &Features[feature_index];
223 feature_address = (((feature->X * NUM_CP_BUCKETS >> 8) * NUM_CP_BUCKETS +
224 (feature->Y * NUM_CP_BUCKETS >> 8)) * NUM_CP_BUCKETS +
225 (feature->Theta * NUM_CP_BUCKETS >> 8)) << 1;
226 ClassPruner = IntTemplates->ClassPruner;
227 class_index = 0;
228
229 for (PrunerSet = 0; PrunerSet < NumPruners; PrunerSet++, ClassPruner++) {
230 BasePrunerAddress = (uinT32 *) (*ClassPruner) + feature_address;
231
232 for (Word = 0; Word < WERDS_PER_CP_VECTOR; Word++) {
233 PrunerWord = *BasePrunerAddress++;
234 // This inner loop is unrolled to speed up the ClassPruner.
235 // Currently gcc would not unroll it unless it is set to O3
236 // level of optimization or -funroll-loops is specified.
237 /*
238 uinT32 class_mask = (1 << NUM_BITS_PER_CLASS) - 1;
239 for (int bit = 0; bit < BITS_PER_WERD/NUM_BITS_PER_CLASS; bit++) {
240 ClassCount[class_index++] += PrunerWord & class_mask;
241 PrunerWord >>= NUM_BITS_PER_CLASS;
242 }
243 */
244 ClassCount[class_index++] += cp_maps[PrunerWord & 3];
245 PrunerWord >>= 2;
246 ClassCount[class_index++] += cp_maps[PrunerWord & 3];
247 PrunerWord >>= 2;
248 ClassCount[class_index++] += cp_maps[PrunerWord & 3];
249 PrunerWord >>= 2;
250 ClassCount[class_index++] += cp_maps[PrunerWord & 3];
251 PrunerWord >>= 2;
252 ClassCount[class_index++] += cp_maps[PrunerWord & 3];
253 PrunerWord >>= 2;
254 ClassCount[class_index++] += cp_maps[PrunerWord & 3];
255 PrunerWord >>= 2;
256 ClassCount[class_index++] += cp_maps[PrunerWord & 3];
257 PrunerWord >>= 2;
258 ClassCount[class_index++] += cp_maps[PrunerWord & 3];
259 PrunerWord >>= 2;
260 ClassCount[class_index++] += cp_maps[PrunerWord & 3];
261 PrunerWord >>= 2;
262 ClassCount[class_index++] += cp_maps[PrunerWord & 3];
263 PrunerWord >>= 2;
264 ClassCount[class_index++] += cp_maps[PrunerWord & 3];
265 PrunerWord >>= 2;
266 ClassCount[class_index++] += cp_maps[PrunerWord & 3];
267 PrunerWord >>= 2;
268 ClassCount[class_index++] += cp_maps[PrunerWord & 3];
269 PrunerWord >>= 2;
270 ClassCount[class_index++] += cp_maps[PrunerWord & 3];
271 PrunerWord >>= 2;
272 ClassCount[class_index++] += cp_maps[PrunerWord & 3];
273 PrunerWord >>= 2;
274 ClassCount[class_index++] += cp_maps[PrunerWord & 3];
275 }
276 }
277 }
278
279 /* Adjust Class Counts for Number of Expected Features */
280 for (class_id = 0; class_id < MaxNumClasses; class_id++) {
281 if (NumFeatures < ExpectedNumFeatures[class_id]) {
282 int deficit = ExpectedNumFeatures[class_id] - NumFeatures;
283 ClassCount[class_id] -= ClassCount[class_id] * deficit /
284 (NumFeatures*classify_cp_cutoff_strength + deficit);
285 }
286 if (!unicharset.get_enabled(class_id))
287 ClassCount[class_id] = 0; // This char is disabled!
288
289 // Do not include character fragments in the class pruner
290 // results if disable_character_fragments is true.
291 if (disable_character_fragments && unicharset.get_fragment(class_id)) {
292 ClassCount[class_id] = 0;
293 }
294 }
295
296 /* Adjust Class Counts for Normalization Factors */
297 MaxCount = 0;
298 for (class_id = 0; class_id < MaxNumClasses; class_id++) {
299 NormCount[class_id] = ClassCount[class_id]
300 - ((classify_class_pruner_multiplier * NormalizationFactors[class_id]) >> 8)
301 * cp_maps[3] / 3;
302 if (NormCount[class_id] > MaxCount &&
303 // This additional check is added in order to ensure that
304 // the classifier will return at least one non-fragmented
305 // character match.
306 // TODO(daria): verify that this helps accuracy and does not
307 // hurt performance.
308 !unicharset.get_fragment(class_id)) {
309 MaxCount = NormCount[class_id];
310 }
311 }
312
313 /* Prune Classes */
314 MaxCount *= classify_class_pruner_threshold;
315 MaxCount >>= 8;
316 /* Select Classes */
317 if (MaxCount < 1)
318 MaxCount = 1;
319 NumClasses = 0;
320 for (class_id = 0; class_id < MaxNumClasses; class_id++) {
321 if (NormCount[class_id] >= MaxCount) {
322 NumClasses++;
323 SortIndex[NumClasses] = class_id;
324 SortKey[NumClasses] = NormCount[class_id];
325 }
326 }
327
328 /* Sort Classes using Heapsort Algorithm */
329 if (NumClasses > 1)
330 HeapSort(NumClasses, SortKey, SortIndex);
331
332 if (tord_display_ratings > 1) {
333 cprintf ("CP:%d classes, %d features:\n", NumClasses, NumFeatures);
334 for (class_id = 0; class_id < NumClasses; class_id++) {
335 cprintf ("%s:C=%d, E=%d, N=%d, Rat=%d\n",
336 unicharset.debug_str(SortIndex[NumClasses - class_id]).string(),
337 ClassCount[SortIndex[NumClasses - class_id]],
338 ExpectedNumFeatures[SortIndex[NumClasses - class_id]],
339 SortKey[NumClasses - class_id],
340 1010 - 1000 * SortKey[NumClasses - class_id] /
341 (cp_maps[3] * NumFeatures));
342 }
343 if (tord_display_ratings > 2) {
344 NumPruners = IntTemplates->NumClassPruners;
345 for (feature_index = 0; feature_index < NumFeatures;
346 feature_index++) {
347 cprintf ("F=%3d,", feature_index);
348 feature = &Features[feature_index];
349 feature_address =
350 (((feature->X * NUM_CP_BUCKETS >> 8) * NUM_CP_BUCKETS +
351 (feature->Y * NUM_CP_BUCKETS >> 8)) * NUM_CP_BUCKETS +
352 (feature->Theta * NUM_CP_BUCKETS >> 8)) << 1;
353 ClassPruner = IntTemplates->ClassPruner;
354 class_index = 0;
355 for (PrunerSet = 0; PrunerSet < NumPruners;
356 PrunerSet++, ClassPruner++) {
357 BasePrunerAddress = (uinT32 *) (*ClassPruner)
358 + feature_address;
359
360 for (Word = 0; Word < WERDS_PER_CP_VECTOR; Word++) {
361 PrunerWord = *BasePrunerAddress++;
362 for (class_id = 0; class_id < 16; class_id++, class_index++) {
363 if (NormCount[class_index] >= MaxCount)
364 cprintf (" %s=%d,",
365 unicharset.id_to_unichar(class_index),
366 PrunerWord & 3);
367 PrunerWord >>= 2;
368 }
369 }
370 }
371 cprintf ("\n");
372 }
373 cprintf ("Adjustments:");
374 for (class_id = 0; class_id < MaxNumClasses; class_id++) {
375 if (NormCount[class_id] > MaxCount)
376 cprintf (" %s=%d,",
377 unicharset.id_to_unichar(class_id),
378 -((classify_class_pruner_multiplier *
379 NormalizationFactors[class_id]) >> 8) * cp_maps[3] / 3);
380 }
381 cprintf ("\n");
382 }
383 }
384
385 /* Set Up Results */
386 max_rating = 0.0f;
387 for (class_id = 0, out_class = 0; class_id < NumClasses; class_id++) {
388 Results[out_class].Class = SortIndex[NumClasses - class_id];
389 Results[out_class].Rating =
390 1.0 - SortKey[NumClasses -
391 class_id] / ((float) cp_maps[3] * NumFeatures);
392 out_class++;
393 }
394 NumClasses = out_class;
395 return NumClasses;
396
397 }
398 } // namespace tesseract
399
400 /*---------------------------------------------------------------------------*/
IntegerMatcher(INT_CLASS ClassTemplate,BIT_VECTOR ProtoMask,BIT_VECTOR ConfigMask,uinT16 BlobLength,inT16 NumFeatures,INT_FEATURE_ARRAY Features,uinT8 NormalizationFactor,INT_RESULT Result,int Debug)401 void IntegerMatcher(INT_CLASS ClassTemplate,
402 BIT_VECTOR ProtoMask,
403 BIT_VECTOR ConfigMask,
404 uinT16 BlobLength,
405 inT16 NumFeatures,
406 INT_FEATURE_ARRAY Features,
407 uinT8 NormalizationFactor,
408 INT_RESULT Result,
409 int Debug) {
410 /*
411 ** Parameters:
412 ** ClassTemplate Prototypes & tables for a class
413 ** BlobLength Length of unormalized blob
414 ** NumFeatures Number of features in blob
415 ** Features Array of features
416 ** NormalizationFactor Fudge factor from blob
417 ** normalization process
418 ** Result Class rating & configuration:
419 ** (0.0 -> 1.0), 0=good, 1=bad
420 ** Debug Debugger flag: 1=debugger on
421 ** Globals:
422 ** LocalMatcherMultiplier Normalization factor multiplier
423 ** classify_int_theta_fudge Theta fudge factor used for
424 ** evidence calculation
425 ** Operation:
426 ** IntegerMatcher returns the best configuration and rating
427 ** for a single class. The class matched against is determined
428 ** by the uniqueness of the ClassTemplate parameter. The
429 ** best rating and its associated configuration are returned.
430 ** Return:
431 ** Exceptions: none
432 ** History: Tue Feb 19 16:36:23 MST 1991, RWM, Created.
433 */
434 static uinT8 FeatureEvidence[MAX_NUM_CONFIGS];
435 static int SumOfFeatureEvidence[MAX_NUM_CONFIGS];
436 static uinT8 ProtoEvidence[MAX_NUM_PROTOS][MAX_PROTO_INDEX];
437 int Feature;
438 int BestMatch;
439
440 if (MatchDebuggingOn (Debug))
441 cprintf ("Integer Matcher -------------------------------------------\n");
442
443 IMClearTables(ClassTemplate, SumOfFeatureEvidence, ProtoEvidence);
444 Result->FeatureMisses = 0;
445
446 for (Feature = 0; Feature < NumFeatures; Feature++) {
447 int csum = IMUpdateTablesForFeature(ClassTemplate, ProtoMask, ConfigMask,
448 Feature, &(Features[Feature]),
449 FeatureEvidence, SumOfFeatureEvidence,
450 ProtoEvidence, Debug);
451 // Count features that were missed over all configs.
452 if (csum == 0)
453 Result->FeatureMisses++;
454 }
455
456 #ifndef GRAPHICS_DISABLED
457 if (PrintProtoMatchesOn (Debug) || PrintMatchSummaryOn (Debug))
458 IMDebugFeatureProtoError(ClassTemplate,
459 ProtoMask,
460 ConfigMask,
461 SumOfFeatureEvidence,
462 ProtoEvidence,
463 NumFeatures,
464 Debug);
465
466 if (DisplayProtoMatchesOn (Debug))
467 IMDisplayProtoDebugInfo(ClassTemplate,
468 ProtoMask,
469 ConfigMask,
470 ProtoEvidence,
471 Debug);
472
473 if (DisplayFeatureMatchesOn (Debug))
474 IMDisplayFeatureDebugInfo(ClassTemplate,
475 ProtoMask,
476 ConfigMask,
477 NumFeatures,
478 Features,
479 Debug);
480 #endif
481
482 IMUpdateSumOfProtoEvidences(ClassTemplate,
483 ConfigMask,
484 SumOfFeatureEvidence,
485 ProtoEvidence,
486 NumFeatures);
487
488 IMNormalizeSumOfEvidences(ClassTemplate,
489 SumOfFeatureEvidence,
490 NumFeatures,
491 NumFeatures);
492
493 BestMatch =
494 IMFindBestMatch(ClassTemplate,
495 SumOfFeatureEvidence,
496 BlobLength,
497 NormalizationFactor,
498 Result);
499
500 #ifndef GRAPHICS_DISABLED
501 if (PrintMatchSummaryOn (Debug))
502 IMDebugBestMatch(BestMatch, Result, BlobLength, NormalizationFactor);
503
504 if (MatchDebuggingOn (Debug))
505 cprintf ("Match Complete --------------------------------------------\n");
506 #endif
507
508 }
509
510
511 /*---------------------------------------------------------------------------*/
FindGoodProtos(INT_CLASS ClassTemplate,BIT_VECTOR ProtoMask,BIT_VECTOR ConfigMask,uinT16 BlobLength,inT16 NumFeatures,INT_FEATURE_ARRAY Features,PROTO_ID * ProtoArray,int Debug)512 int FindGoodProtos(INT_CLASS ClassTemplate,
513 BIT_VECTOR ProtoMask,
514 BIT_VECTOR ConfigMask,
515 uinT16 BlobLength,
516 inT16 NumFeatures,
517 INT_FEATURE_ARRAY Features,
518 PROTO_ID *ProtoArray,
519 int Debug) {
520 /*
521 ** Parameters:
522 ** ClassTemplate Prototypes & tables for a class
523 ** ProtoMask AND Mask for proto word
524 ** ConfigMask AND Mask for config word
525 ** BlobLength Length of unormalized blob
526 ** NumFeatures Number of features in blob
527 ** Features Array of features
528 ** ProtoArray Array of good protos
529 ** Debug Debugger flag: 1=debugger on
530 ** Globals:
531 ** LocalMatcherMultiplier Normalization factor multiplier
532 ** classify_int_theta_fudge Theta fudge factor used for
533 ** evidence calculation
534 ** classify_adapt_proto_thresh Threshold for good protos
535 ** Operation:
536 ** FindGoodProtos finds all protos whose normalized proto-evidence
537 ** exceed classify_adapt_proto_thresh. The list is ordered by increasing
538 ** proto id number.
539 ** Return:
540 ** Number of good protos in ProtoArray.
541 ** Exceptions: none
542 ** History: Tue Mar 12 17:09:26 MST 1991, RWM, Created
543 */
544 static uinT8 FeatureEvidence[MAX_NUM_CONFIGS];
545 static int SumOfFeatureEvidence[MAX_NUM_CONFIGS];
546 static uinT8 ProtoEvidence[MAX_NUM_PROTOS][MAX_PROTO_INDEX];
547 int Feature;
548 register uinT8 *UINT8Pointer;
549 register int ProtoIndex;
550 int NumProtos;
551 int NumGoodProtos;
552 uinT16 ActualProtoNum;
553 register int Temp;
554
555 /* DEBUG opening heading */
556 if (MatchDebuggingOn (Debug))
557 cprintf
558 ("Find Good Protos -------------------------------------------\n");
559
560 IMClearTables(ClassTemplate, SumOfFeatureEvidence, ProtoEvidence);
561
562 for (Feature = 0; Feature < NumFeatures; Feature++)
563 IMUpdateTablesForFeature (ClassTemplate, ProtoMask, ConfigMask, Feature,
564 &(Features[Feature]), FeatureEvidence,
565 SumOfFeatureEvidence, ProtoEvidence, Debug);
566
567 #ifndef GRAPHICS_DISABLED
568 if (PrintProtoMatchesOn (Debug) || PrintMatchSummaryOn (Debug))
569 IMDebugFeatureProtoError(ClassTemplate,
570 ProtoMask,
571 ConfigMask,
572 SumOfFeatureEvidence,
573 ProtoEvidence,
574 NumFeatures,
575 Debug);
576 #endif
577
578 /* Average Proto Evidences & Find Good Protos */
579 NumProtos = ClassTemplate->NumProtos;
580 NumGoodProtos = 0;
581 for (ActualProtoNum = 0; ActualProtoNum < NumProtos; ActualProtoNum++) {
582 /* Compute Average for Actual Proto */
583 Temp = 0;
584 UINT8Pointer = &(ProtoEvidence[ActualProtoNum][0]);
585 for (ProtoIndex = ClassTemplate->ProtoLengths[ActualProtoNum];
586 ProtoIndex > 0; ProtoIndex--, UINT8Pointer++)
587 Temp += *UINT8Pointer;
588
589 Temp /= ClassTemplate->ProtoLengths[ActualProtoNum];
590
591 /* Find Good Protos */
592 if (Temp >= classify_adapt_proto_thresh) {
593 *ProtoArray = ActualProtoNum;
594 ProtoArray++;
595 NumGoodProtos++;
596 }
597 }
598
599 if (MatchDebuggingOn (Debug))
600 cprintf ("Match Complete --------------------------------------------\n");
601 return NumGoodProtos;
602
603 }
604
605
606 /*---------------------------------------------------------------------------*/
FindBadFeatures(INT_CLASS ClassTemplate,BIT_VECTOR ProtoMask,BIT_VECTOR ConfigMask,uinT16 BlobLength,inT16 NumFeatures,INT_FEATURE_ARRAY Features,FEATURE_ID * FeatureArray,int Debug)607 int FindBadFeatures(INT_CLASS ClassTemplate,
608 BIT_VECTOR ProtoMask,
609 BIT_VECTOR ConfigMask,
610 uinT16 BlobLength,
611 inT16 NumFeatures,
612 INT_FEATURE_ARRAY Features,
613 FEATURE_ID *FeatureArray,
614 int Debug) {
615 /*
616 ** Parameters:
617 ** ClassTemplate Prototypes & tables for a class
618 ** ProtoMask AND Mask for proto word
619 ** ConfigMask AND Mask for config word
620 ** BlobLength Length of unormalized blob
621 ** NumFeatures Number of features in blob
622 ** Features Array of features
623 ** FeatureArray Array of bad features
624 ** Debug Debugger flag: 1=debugger on
625 ** Globals:
626 ** LocalMatcherMultiplier Normalization factor multiplier
627 ** classify_int_theta_fudge Theta fudge factor used for
628 ** evidence calculation
629 ** classify_adapt_feature_thresh Threshold for bad features
630 ** Operation:
631 ** FindBadFeatures finds all features whose maximum feature-evidence
632 ** was less than classify_adapt_feature_thresh. The list is ordered by increasing
633 ** feature number.
634 ** Return:
635 ** Number of bad features in FeatureArray.
636 ** Exceptions: none
637 ** History: Tue Mar 12 17:09:26 MST 1991, RWM, Created
638 */
639 static uinT8 FeatureEvidence[MAX_NUM_CONFIGS];
640 static int SumOfFeatureEvidence[MAX_NUM_CONFIGS];
641 static uinT8 ProtoEvidence[MAX_NUM_PROTOS][MAX_PROTO_INDEX];
642 int Feature;
643 register uinT8 *UINT8Pointer;
644 register int ConfigNum;
645 int NumConfigs;
646 int NumBadFeatures;
647 register int Temp;
648
649 /* DEBUG opening heading */
650 if (MatchDebuggingOn (Debug))
651 cprintf
652 ("Find Bad Features -------------------------------------------\n");
653
654 IMClearTables(ClassTemplate, SumOfFeatureEvidence, ProtoEvidence);
655
656 NumBadFeatures = 0;
657 NumConfigs = ClassTemplate->NumConfigs;
658 for (Feature = 0; Feature < NumFeatures; Feature++) {
659 IMUpdateTablesForFeature (ClassTemplate, ProtoMask, ConfigMask, Feature,
660 &(Features[Feature]), FeatureEvidence,
661 SumOfFeatureEvidence, ProtoEvidence, Debug);
662
663 /* Find Best Evidence for Current Feature */
664 Temp = 0;
665 UINT8Pointer = FeatureEvidence;
666 for (ConfigNum = 0; ConfigNum < NumConfigs; ConfigNum++, UINT8Pointer++)
667 if (*UINT8Pointer > Temp)
668 Temp = *UINT8Pointer;
669
670 /* Find Bad Features */
671 if (Temp < classify_adapt_feature_thresh) {
672 *FeatureArray = Feature;
673 FeatureArray++;
674 NumBadFeatures++;
675 }
676 }
677
678 #ifndef GRAPHICS_DISABLED
679 if (PrintProtoMatchesOn (Debug) || PrintMatchSummaryOn (Debug))
680 IMDebugFeatureProtoError(ClassTemplate,
681 ProtoMask,
682 ConfigMask,
683 SumOfFeatureEvidence,
684 ProtoEvidence,
685 NumFeatures,
686 Debug);
687 #endif
688
689 if (MatchDebuggingOn (Debug))
690 cprintf ("Match Complete --------------------------------------------\n");
691
692 return NumBadFeatures;
693
694 }
695
696
697 /*---------------------------------------------------------------------------*/
InitIntegerMatcher()698 void InitIntegerMatcher() {
699 int i;
700 uinT32 IntSimilarity;
701 double Similarity;
702 double Evidence;
703 double ScaleFactor;
704
705 /* Set default mode of operation of IntegerMatcher */
706 SetCharNormMatch();
707
708 /* Initialize table for evidence to similarity lookup */
709 for (i = 0; i < SE_TABLE_SIZE; i++) {
710 IntSimilarity = i << (27 - SE_TABLE_BITS);
711 Similarity = ((double) IntSimilarity) / 65536.0 / 65536.0;
712 Evidence = Similarity / classify_similarity_center;
713 Evidence *= Evidence;
714 Evidence += 1.0;
715 Evidence = 1.0 / Evidence;
716 Evidence *= 255.0;
717
718 if (classify_se_exponential_multiplier > 0.0) {
719 ScaleFactor = 1.0 - exp (-classify_se_exponential_multiplier) *
720 exp (classify_se_exponential_multiplier * ((double) i / SE_TABLE_SIZE));
721 if (ScaleFactor > 1.0)
722 ScaleFactor = 1.0;
723 if (ScaleFactor < 0.0)
724 ScaleFactor = 0.0;
725 Evidence *= ScaleFactor;
726 }
727
728 SimilarityEvidenceTable[i] = (uinT8) (Evidence + 0.5);
729 }
730
731 /* Initialize evidence computation variables */
732 EvidenceTableMask =
733 ((1 << classify_evidence_table_bits) - 1) << (9 - classify_evidence_table_bits);
734 MultTruncShiftBits = (14 - classify_int_evidence_trunc_bits);
735 TableTruncShiftBits = (27 - SE_TABLE_BITS - (MultTruncShiftBits << 1));
736 EvidenceMultMask = ((1 << classify_int_evidence_trunc_bits) - 1);
737
738 }
739
740 /*-------------------------------------------------------------------------*/
PrintIntMatcherStats(FILE * f)741 void PrintIntMatcherStats(FILE *f) {
742 fprintf (f, "protoword_lookups=%d, zero_protowords=%d, proto_shifts=%d\n",
743 protoword_lookups, zero_protowords, proto_shifts);
744 fprintf (f, "set_proto_bits=%d, config_shifts=%d, set_config_bits=%d\n",
745 set_proto_bits, config_shifts, set_config_bits);
746 }
747
748
749 /*-------------------------------------------------------------------------*/
SetProtoThresh(FLOAT32 Threshold)750 void SetProtoThresh(FLOAT32 Threshold) {
751 classify_adapt_proto_thresh.set_value(255 * Threshold);
752 if (classify_adapt_proto_thresh < 0)
753 classify_adapt_proto_thresh.set_value(0);
754 if (classify_adapt_proto_thresh > 255)
755 classify_adapt_proto_thresh.set_value(255);
756 }
757
758
759 /*---------------------------------------------------------------------------*/
SetFeatureThresh(FLOAT32 Threshold)760 void SetFeatureThresh(FLOAT32 Threshold) {
761 classify_adapt_feature_thresh.set_value(255 * Threshold);
762 if (classify_adapt_feature_thresh < 0)
763 classify_adapt_feature_thresh.set_value(0);
764 if (classify_adapt_feature_thresh > 255)
765 classify_adapt_feature_thresh.set_value(255);
766 }
767
768
769 /*--------------------------------------------------------------------------*/
SetBaseLineMatch()770 void SetBaseLineMatch() {
771 LocalMatcherMultiplier = 0;
772 }
773
774
775 /*--------------------------------------------------------------------------*/
SetCharNormMatch()776 void SetCharNormMatch() {
777 LocalMatcherMultiplier = classify_integer_matcher_multiplier;
778 }
779
780
781 /**----------------------------------------------------------------------------
782 Private Code
783 ----------------------------------------------------------------------------**/
784 /*---------------------------------------------------------------------------*/
785 void
IMClearTables(INT_CLASS ClassTemplate,int SumOfFeatureEvidence[MAX_NUM_CONFIGS],uinT8 ProtoEvidence[MAX_NUM_PROTOS][MAX_PROTO_INDEX])786 IMClearTables (INT_CLASS ClassTemplate,
787 int SumOfFeatureEvidence[MAX_NUM_CONFIGS],
788 uinT8 ProtoEvidence[MAX_NUM_PROTOS][MAX_PROTO_INDEX]) {
789 /*
790 ** Parameters:
791 ** SumOfFeatureEvidence Sum of Feature Evidence Table
792 ** NumConfigs Number of Configurations
793 ** ProtoEvidence Prototype Evidence Table
794 ** NumProtos Number of Prototypes
795 ** Globals:
796 ** Operation:
797 ** Clear SumOfFeatureEvidence and ProtoEvidence tables.
798 ** Return:
799 ** Exceptions: none
800 ** History: Wed Feb 27 14:12:28 MST 1991, RWM, Created.
801 */
802 int NumProtos = ClassTemplate->NumProtos;
803 int NumConfigs = ClassTemplate->NumConfigs;
804
805 memset(SumOfFeatureEvidence, 0,
806 NumConfigs * sizeof(SumOfFeatureEvidence[0]));
807 memset(ProtoEvidence, 0,
808 NumProtos * sizeof(ProtoEvidence[0]));
809 }
810
811
812 /*---------------------------------------------------------------------------*/
813 void
IMClearFeatureEvidenceTable(uinT8 FeatureEvidence[MAX_NUM_CONFIGS],int NumConfigs)814 IMClearFeatureEvidenceTable (uinT8 FeatureEvidence[MAX_NUM_CONFIGS],
815 int NumConfigs) {
816 /*
817 ** Parameters:
818 ** FeatureEvidence Feature Evidence Table
819 ** NumConfigs Number of Configurations
820 ** Globals:
821 ** Operation:
822 ** Clear FeatureEvidence table.
823 ** Return:
824 ** Exceptions: none
825 ** History: Wed Feb 27 14:12:28 MST 1991, RWM, Created.
826 */
827 memset(FeatureEvidence, 0, NumConfigs * sizeof(*FeatureEvidence));
828 }
829
830
831 /*---------------------------------------------------------------------------*/
IMDebugConfiguration(int FeatureNum,uinT16 ActualProtoNum,uinT8 Evidence,BIT_VECTOR ConfigMask,uinT32 ConfigWord)832 void IMDebugConfiguration(int FeatureNum,
833 uinT16 ActualProtoNum,
834 uinT8 Evidence,
835 BIT_VECTOR ConfigMask,
836 uinT32 ConfigWord) {
837 /*
838 ** Parameters:
839 ** Globals:
840 ** Operation:
841 ** Print debugging information for Configuations
842 ** Return:
843 ** Exceptions: none
844 ** History: Wed Feb 27 14:12:28 MST 1991, RWM, Created.
845 */
846 cprintf ("F = %3d, P = %3d, E = %3d, Configs = ",
847 FeatureNum, (int) ActualProtoNum, (int) Evidence);
848 while (ConfigWord) {
849 if (ConfigWord & 1)
850 cprintf ("1");
851 else
852 cprintf ("0");
853 ConfigWord >>= 1;
854 }
855 cprintf ("\n");
856 }
857
858
859 /*---------------------------------------------------------------------------*/
IMDebugConfigurationSum(int FeatureNum,uinT8 * FeatureEvidence,inT32 ConfigCount)860 void IMDebugConfigurationSum(int FeatureNum,
861 uinT8 *FeatureEvidence,
862 inT32 ConfigCount) {
863 /*
864 ** Parameters:
865 ** Globals:
866 ** Operation:
867 ** Print debugging information for Configuations
868 ** Return:
869 ** Exceptions: none
870 ** History: Wed Feb 27 14:12:28 MST 1991, RWM, Created.
871 */
872 int ConfigNum;
873
874 cprintf ("F=%3d, C=", (int) FeatureNum);
875
876 for (ConfigNum = 0; ConfigNum < ConfigCount; ConfigNum++) {
877 cprintf ("%4d", FeatureEvidence[ConfigNum]);
878 }
879 cprintf ("\n");
880
881 }
882
883
884
885 /*---------------------------------------------------------------------------*/
886 int
IMUpdateTablesForFeature(INT_CLASS ClassTemplate,BIT_VECTOR ProtoMask,BIT_VECTOR ConfigMask,int FeatureNum,INT_FEATURE Feature,uinT8 FeatureEvidence[MAX_NUM_CONFIGS],int SumOfFeatureEvidence[MAX_NUM_CONFIGS],uinT8 ProtoEvidence[MAX_NUM_PROTOS][MAX_PROTO_INDEX],int Debug)887 IMUpdateTablesForFeature (INT_CLASS ClassTemplate,
888 BIT_VECTOR ProtoMask,
889 BIT_VECTOR ConfigMask,
890 int FeatureNum,
891 INT_FEATURE Feature,
892 uinT8 FeatureEvidence[MAX_NUM_CONFIGS],
893 int SumOfFeatureEvidence[MAX_NUM_CONFIGS],
894 uinT8
895 ProtoEvidence[MAX_NUM_PROTOS][MAX_PROTO_INDEX],
896 int Debug) {
897 /*
898 ** Parameters:
899 ** ClassTemplate Prototypes & tables for a class
900 ** FeatureNum Current feature number (for DEBUG only)
901 ** Feature Pointer to a feature struct
902 ** FeatureEvidence Feature Evidence Table
903 ** SumOfFeatureEvidence Sum of Feature Evidence Table
904 ** ProtoEvidence Prototype Evidence Table
905 ** Debug Debugger flag: 1=debugger on
906 ** Globals:
907 ** Operation:
908 ** For the given feature: prune protos, compute evidence, update Feature Evidence,
909 ** Proto Evidence, and Sum of Feature Evidence tables.
910 ** Return:
911 ** Exceptions: none
912 ** History: Wed Feb 27 14:12:28 MST 1991, RWM, Created.
913 */
914 register uinT32 ConfigWord;
915 register uinT32 ProtoWord;
916 register uinT32 ProtoNum;
917 register uinT32 ActualProtoNum;
918 uinT8 proto_byte;
919 inT32 proto_word_offset;
920 inT32 proto_offset;
921 uinT8 config_byte;
922 inT32 config_offset;
923 PROTO_SET ProtoSet;
924 uinT32 *ProtoPrunerPtr;
925 INT_PROTO Proto;
926 int ProtoSetIndex;
927 uinT8 Evidence;
928 uinT32 XFeatureAddress;
929 uinT32 YFeatureAddress;
930 uinT32 ThetaFeatureAddress;
931 register uinT8 *UINT8Pointer;
932 register int ProtoIndex;
933 uinT8 Temp;
934 register int *IntPointer;
935 int ConfigNum;
936 register inT32 M3;
937 register inT32 A3;
938 register uinT32 A4;
939
940 IMClearFeatureEvidenceTable(FeatureEvidence, ClassTemplate->NumConfigs);
941
942 /* Precompute Feature Address offset for Proto Pruning */
943 XFeatureAddress = ((Feature->X >> 2) << 1);
944 YFeatureAddress = (NUM_PP_BUCKETS << 1) + ((Feature->Y >> 2) << 1);
945 ThetaFeatureAddress = (NUM_PP_BUCKETS << 2) + ((Feature->Theta >> 2) << 1);
946
947 for (ProtoSetIndex = 0, ActualProtoNum = 0;
948 ProtoSetIndex < ClassTemplate->NumProtoSets; ProtoSetIndex++) {
949 ProtoSet = ClassTemplate->ProtoSets[ProtoSetIndex];
950 ProtoPrunerPtr = (uinT32 *) ((*ProtoSet).ProtoPruner);
951 for (ProtoNum = 0; ProtoNum < PROTOS_PER_PROTO_SET;
952 ProtoNum += (PROTOS_PER_PROTO_SET >> 1), ActualProtoNum +=
953 (PROTOS_PER_PROTO_SET >> 1), ProtoMask++, ProtoPrunerPtr++) {
954 /* Prune Protos of current Proto Set */
955 ProtoWord = *(ProtoPrunerPtr + XFeatureAddress);
956 ProtoWord &= *(ProtoPrunerPtr + YFeatureAddress);
957 ProtoWord &= *(ProtoPrunerPtr + ThetaFeatureAddress);
958 ProtoWord &= *ProtoMask;
959
960 if (ProtoWord != 0) {
961 proto_byte = ProtoWord & 0xff;
962 ProtoWord >>= 8;
963 proto_word_offset = 0;
964 while (ProtoWord != 0 || proto_byte != 0) {
965 while (proto_byte == 0) {
966 proto_byte = ProtoWord & 0xff;
967 ProtoWord >>= 8;
968 proto_word_offset += 8;
969 }
970 proto_offset = offset_table[proto_byte] + proto_word_offset;
971 proto_byte = next_table[proto_byte];
972 Proto = &(ProtoSet->Protos[ProtoNum + proto_offset]);
973 ConfigWord = Proto->Configs[0];
974 A3 = (((Proto->A * (Feature->X - 128)) << 1)
975 - (Proto->B * (Feature->Y - 128)) + (Proto->C << 9));
976 M3 =
977 (((inT8) (Feature->Theta - Proto->Angle)) *
978 classify_int_theta_fudge) << 1;
979
980 if (A3 < 0)
981 A3 = ~A3;
982 if (M3 < 0)
983 M3 = ~M3;
984 A3 >>= MultTruncShiftBits;
985 M3 >>= MultTruncShiftBits;
986 if (A3 > EvidenceMultMask)
987 A3 = EvidenceMultMask;
988 if (M3 > EvidenceMultMask)
989 M3 = EvidenceMultMask;
990
991 A4 = (A3 * A3) + (M3 * M3);
992 A4 >>= TableTruncShiftBits;
993 if (A4 > EvidenceTableMask)
994 Evidence = 0;
995 else
996 Evidence = SimilarityEvidenceTable[A4];
997
998 if (PrintFeatureMatchesOn (Debug))
999 IMDebugConfiguration (FeatureNum,
1000 ActualProtoNum + proto_offset,
1001 Evidence, ConfigMask, ConfigWord);
1002
1003 ConfigWord &= *ConfigMask;
1004
1005 UINT8Pointer = FeatureEvidence - 8;
1006 config_byte = 0;
1007 while (ConfigWord != 0 || config_byte != 0) {
1008 while (config_byte == 0) {
1009 config_byte = ConfigWord & 0xff;
1010 ConfigWord >>= 8;
1011 UINT8Pointer += 8;
1012 // config_shifts++;
1013 }
1014 config_offset = offset_table[config_byte];
1015 config_byte = next_table[config_byte];
1016 if (Evidence > UINT8Pointer[config_offset])
1017 UINT8Pointer[config_offset] = Evidence;
1018 }
1019
1020 UINT8Pointer =
1021 &(ProtoEvidence[ActualProtoNum + proto_offset][0]);
1022 for (ProtoIndex =
1023 ClassTemplate->ProtoLengths[ActualProtoNum + proto_offset];
1024 ProtoIndex > 0; ProtoIndex--, UINT8Pointer++) {
1025 if (Evidence > *UINT8Pointer) {
1026 Temp = *UINT8Pointer;
1027 *UINT8Pointer = Evidence;
1028 Evidence = Temp;
1029 }
1030 else if (Evidence == 0)
1031 break;
1032 }
1033 }
1034 }
1035 }
1036 }
1037
1038 if (PrintFeatureMatchesOn (Debug))
1039 IMDebugConfigurationSum (FeatureNum, FeatureEvidence,
1040 ClassTemplate->NumConfigs);
1041 IntPointer = SumOfFeatureEvidence;
1042 UINT8Pointer = FeatureEvidence;
1043 int SumOverConfigs = 0;
1044 for (ConfigNum = ClassTemplate->NumConfigs; ConfigNum > 0; ConfigNum--) {
1045 int evidence = *UINT8Pointer++;
1046 SumOverConfigs += evidence;
1047 *IntPointer++ += evidence;
1048 }
1049 return SumOverConfigs;
1050 }
1051
1052
1053 /*---------------------------------------------------------------------------*/
1054 #ifndef GRAPHICS_DISABLED
1055 void
IMDebugFeatureProtoError(INT_CLASS ClassTemplate,BIT_VECTOR ProtoMask,BIT_VECTOR ConfigMask,int SumOfFeatureEvidence[MAX_NUM_CONFIGS],uinT8 ProtoEvidence[MAX_NUM_PROTOS][MAX_PROTO_INDEX],inT16 NumFeatures,int Debug)1056 IMDebugFeatureProtoError (INT_CLASS ClassTemplate,
1057 BIT_VECTOR ProtoMask,
1058 BIT_VECTOR ConfigMask,
1059 int SumOfFeatureEvidence[MAX_NUM_CONFIGS],
1060 uinT8
1061 ProtoEvidence[MAX_NUM_PROTOS][MAX_PROTO_INDEX],
1062 inT16 NumFeatures, int Debug) {
1063 /*
1064 ** Parameters:
1065 ** Globals:
1066 ** Operation:
1067 ** Print debugging information for Configuations
1068 ** Return:
1069 ** Exceptions: none
1070 ** History: Wed Feb 27 14:12:28 MST 1991, RWM, Created.
1071 */
1072 uinT8 *UINT8Pointer;
1073 int *IntPointer;
1074 FLOAT32 ProtoConfigs[MAX_NUM_CONFIGS];
1075 int ConfigNum;
1076 uinT32 ConfigWord;
1077 int ProtoSetIndex;
1078 uinT16 ProtoNum;
1079 uinT8 ProtoWordNum;
1080 PROTO_SET ProtoSet;
1081 int ProtoIndex;
1082 int NumProtos;
1083 uinT16 ActualProtoNum;
1084 int Temp;
1085 int NumConfigs;
1086
1087 NumProtos = ClassTemplate->NumProtos;
1088 NumConfigs = ClassTemplate->NumConfigs;
1089
1090 if (PrintMatchSummaryOn (Debug)) {
1091 cprintf ("Configuration Mask:\n");
1092 for (ConfigNum = 0; ConfigNum < NumConfigs; ConfigNum++)
1093 cprintf ("%1d", (((*ConfigMask) >> ConfigNum) & 1));
1094 cprintf ("\n");
1095
1096 cprintf ("Feature Error for Configurations:\n");
1097 for (ConfigNum = 0; ConfigNum < NumConfigs; ConfigNum++)
1098 cprintf (" %5.1f",
1099 100.0 * (1.0 -
1100 (FLOAT32) SumOfFeatureEvidence[ConfigNum] /
1101 NumFeatures / 256.0));
1102 cprintf ("\n\n\n");
1103 }
1104
1105 if (PrintMatchSummaryOn (Debug)) {
1106 cprintf ("Proto Mask:\n");
1107 for (ProtoSetIndex = 0; ProtoSetIndex < ClassTemplate->NumProtoSets;
1108 ProtoSetIndex++) {
1109 ActualProtoNum = (ProtoSetIndex * PROTOS_PER_PROTO_SET);
1110 for (ProtoWordNum = 0; ProtoWordNum < 2;
1111 ProtoWordNum++, ProtoMask++) {
1112 ActualProtoNum = (ProtoSetIndex * PROTOS_PER_PROTO_SET);
1113 for (ProtoNum = 0;
1114 ((ProtoNum < (PROTOS_PER_PROTO_SET >> 1))
1115 && (ActualProtoNum < NumProtos));
1116 ProtoNum++, ActualProtoNum++)
1117 cprintf ("%1d", (((*ProtoMask) >> ProtoNum) & 1));
1118 cprintf ("\n");
1119 }
1120 }
1121 cprintf ("\n");
1122 }
1123
1124 for (ConfigNum = 0; ConfigNum < NumConfigs; ConfigNum++)
1125 ProtoConfigs[ConfigNum] = 0;
1126
1127 if (PrintProtoMatchesOn (Debug)) {
1128 cprintf ("Proto Evidence:\n");
1129 for (ProtoSetIndex = 0; ProtoSetIndex < ClassTemplate->NumProtoSets;
1130 ProtoSetIndex++) {
1131 ProtoSet = ClassTemplate->ProtoSets[ProtoSetIndex];
1132 ActualProtoNum = (ProtoSetIndex * PROTOS_PER_PROTO_SET);
1133 for (ProtoNum = 0;
1134 ((ProtoNum < PROTOS_PER_PROTO_SET)
1135 && (ActualProtoNum < NumProtos));
1136 ProtoNum++, ActualProtoNum++) {
1137 cprintf ("P %3d =", ActualProtoNum);
1138 Temp = 0;
1139 UINT8Pointer = &(ProtoEvidence[ActualProtoNum][0]);
1140 for (ProtoIndex = 0;
1141 ProtoIndex < ClassTemplate->ProtoLengths[ActualProtoNum];
1142 ProtoIndex++, UINT8Pointer++) {
1143 cprintf (" %d", *UINT8Pointer);
1144 Temp += *UINT8Pointer;
1145 }
1146
1147 cprintf (" = %6.4f%%\n", Temp /
1148 256.0 / ClassTemplate->ProtoLengths[ActualProtoNum]);
1149
1150 ConfigWord = (ProtoSet->Protos[ProtoNum]).Configs[0];
1151 IntPointer = SumOfFeatureEvidence;
1152 ConfigNum = 0;
1153 while (ConfigWord) {
1154 cprintf ("%5d", ConfigWord & 1 ? Temp : 0);
1155 if (ConfigWord & 1)
1156 ProtoConfigs[ConfigNum] += Temp;
1157 IntPointer++;
1158 ConfigNum++;
1159 ConfigWord >>= 1;
1160 }
1161 cprintf ("\n");
1162 }
1163 }
1164 }
1165
1166 if (PrintMatchSummaryOn (Debug)) {
1167 cprintf ("Proto Error for Configurations:\n");
1168 for (ConfigNum = 0; ConfigNum < NumConfigs; ConfigNum++)
1169 cprintf (" %5.1f",
1170 100.0 * (1.0 -
1171 ProtoConfigs[ConfigNum] /
1172 ClassTemplate->ConfigLengths[ConfigNum] / 256.0));
1173 cprintf ("\n\n");
1174 }
1175
1176 if (PrintProtoMatchesOn (Debug)) {
1177 cprintf ("Proto Sum for Configurations:\n");
1178 for (ConfigNum = 0; ConfigNum < NumConfigs; ConfigNum++)
1179 cprintf (" %4.1f", ProtoConfigs[ConfigNum] / 256.0);
1180 cprintf ("\n\n");
1181
1182 cprintf ("Proto Length for Configurations:\n");
1183 for (ConfigNum = 0; ConfigNum < NumConfigs; ConfigNum++)
1184 cprintf (" %4.1f",
1185 (float) ClassTemplate->ConfigLengths[ConfigNum]);
1186 cprintf ("\n\n");
1187 }
1188
1189 }
1190
1191
1192 /*---------------------------------------------------------------------------*/
1193 void
IMDisplayProtoDebugInfo(INT_CLASS ClassTemplate,BIT_VECTOR ProtoMask,BIT_VECTOR ConfigMask,uinT8 ProtoEvidence[MAX_NUM_PROTOS][MAX_PROTO_INDEX],int Debug)1194 IMDisplayProtoDebugInfo (INT_CLASS ClassTemplate,
1195 BIT_VECTOR ProtoMask,
1196 BIT_VECTOR ConfigMask,
1197 uinT8 ProtoEvidence[MAX_NUM_PROTOS][MAX_PROTO_INDEX],
1198 int Debug) {
1199 register uinT8 *UINT8Pointer;
1200 register uinT32 ConfigWord;
1201 register uinT16 ProtoNum;
1202 register uinT16 ActualProtoNum;
1203 PROTO_SET ProtoSet;
1204 int ProtoSetIndex;
1205 int ProtoIndex;
1206 int NumProtos;
1207 register int Temp;
1208
1209 InitIntMatchWindowIfReqd();
1210 if (matcher_debug_separate_windows) {
1211 InitFeatureDisplayWindowIfReqd();
1212 InitProtoDisplayWindowIfReqd();
1213 }
1214
1215 NumProtos = ClassTemplate->NumProtos;
1216
1217 for (ProtoSetIndex = 0; ProtoSetIndex < ClassTemplate->NumProtoSets;
1218 ProtoSetIndex++) {
1219 ProtoSet = ClassTemplate->ProtoSets[ProtoSetIndex];
1220 ActualProtoNum = (ProtoSetIndex * PROTOS_PER_PROTO_SET);
1221 for (ProtoNum = 0;
1222 ((ProtoNum < PROTOS_PER_PROTO_SET)
1223 && (ActualProtoNum < NumProtos)); ProtoNum++, ActualProtoNum++) {
1224 /* Compute Average for Actual Proto */
1225 Temp = 0;
1226 UINT8Pointer = &(ProtoEvidence[ActualProtoNum][0]);
1227 for (ProtoIndex = ClassTemplate->ProtoLengths[ActualProtoNum];
1228 ProtoIndex > 0; ProtoIndex--, UINT8Pointer++)
1229 Temp += *UINT8Pointer;
1230
1231 Temp /= ClassTemplate->ProtoLengths[ActualProtoNum];
1232
1233 ConfigWord = (ProtoSet->Protos[ProtoNum]).Configs[0];
1234 ConfigWord &= *ConfigMask;
1235 if (ConfigWord) {
1236 /* Update display for current proto */
1237 if (ClipMatchEvidenceOn (Debug)) {
1238 if (Temp < classify_adapt_proto_thresh)
1239 DisplayIntProto (ClassTemplate, ActualProtoNum,
1240 (Temp / 255.0));
1241 else
1242 DisplayIntProto (ClassTemplate, ActualProtoNum,
1243 (Temp / 255.0));
1244 }
1245 else {
1246 DisplayIntProto (ClassTemplate, ActualProtoNum,
1247 (Temp / 255.0));
1248 }
1249 }
1250 }
1251 }
1252 }
1253
1254
1255 /*---------------------------------------------------------------------------*/
IMDisplayFeatureDebugInfo(INT_CLASS ClassTemplate,BIT_VECTOR ProtoMask,BIT_VECTOR ConfigMask,inT16 NumFeatures,INT_FEATURE_ARRAY Features,int Debug)1256 void IMDisplayFeatureDebugInfo(INT_CLASS ClassTemplate,
1257 BIT_VECTOR ProtoMask,
1258 BIT_VECTOR ConfigMask,
1259 inT16 NumFeatures,
1260 INT_FEATURE_ARRAY Features,
1261 int Debug) {
1262 static uinT8 FeatureEvidence[MAX_NUM_CONFIGS];
1263 static int SumOfFeatureEvidence[MAX_NUM_CONFIGS];
1264 static uinT8 ProtoEvidence[MAX_NUM_PROTOS][MAX_PROTO_INDEX];
1265 int Feature;
1266 register uinT8 *UINT8Pointer;
1267 register int ConfigNum;
1268 int NumConfigs;
1269 register int Temp;
1270
1271 IMClearTables(ClassTemplate, SumOfFeatureEvidence, ProtoEvidence);
1272
1273 InitIntMatchWindowIfReqd();
1274 if (matcher_debug_separate_windows) {
1275 InitFeatureDisplayWindowIfReqd();
1276 InitProtoDisplayWindowIfReqd();
1277 }
1278
1279 NumConfigs = ClassTemplate->NumConfigs;
1280 for (Feature = 0; Feature < NumFeatures; Feature++) {
1281 IMUpdateTablesForFeature (ClassTemplate, ProtoMask, ConfigMask, Feature,
1282 &(Features[Feature]), FeatureEvidence,
1283 SumOfFeatureEvidence, ProtoEvidence, 0);
1284
1285 /* Find Best Evidence for Current Feature */
1286 Temp = 0;
1287 UINT8Pointer = FeatureEvidence;
1288 for (ConfigNum = 0; ConfigNum < NumConfigs; ConfigNum++, UINT8Pointer++)
1289 if (*UINT8Pointer > Temp)
1290 Temp = *UINT8Pointer;
1291
1292 /* Update display for current feature */
1293 if (ClipMatchEvidenceOn (Debug)) {
1294 if (Temp < classify_adapt_feature_thresh)
1295 DisplayIntFeature (&(Features[Feature]), 0.0);
1296 else
1297 DisplayIntFeature (&(Features[Feature]), 1.0);
1298 }
1299 else {
1300 DisplayIntFeature (&(Features[Feature]), (Temp / 255.0));
1301 }
1302 }
1303 }
1304 #endif
1305
1306 /*---------------------------------------------------------------------------*/
1307 void
IMUpdateSumOfProtoEvidences(INT_CLASS ClassTemplate,BIT_VECTOR ConfigMask,int SumOfFeatureEvidence[MAX_NUM_CONFIGS],uinT8 ProtoEvidence[MAX_NUM_PROTOS][MAX_PROTO_INDEX],inT16 NumFeatures)1308 IMUpdateSumOfProtoEvidences (INT_CLASS ClassTemplate,
1309 BIT_VECTOR ConfigMask,
1310 int SumOfFeatureEvidence[MAX_NUM_CONFIGS],
1311 uinT8
1312 ProtoEvidence[MAX_NUM_PROTOS][MAX_PROTO_INDEX],
1313 inT16 NumFeatures) {
1314 /*
1315 ** Parameters:
1316 ** Globals:
1317 ** Operation:
1318 ** Add sum of Proto Evidences into Sum Of Feature Evidence Array
1319 ** Return:
1320 ** Exceptions: none
1321 ** History: Wed Feb 27 14:12:28 MST 1991, RWM, Created.
1322 */
1323 register uinT8 *UINT8Pointer;
1324 register int *IntPointer;
1325 register uinT32 ConfigWord;
1326 int ProtoSetIndex;
1327 register uinT16 ProtoNum;
1328 PROTO_SET ProtoSet;
1329 register int ProtoIndex;
1330 int NumProtos;
1331 uinT16 ActualProtoNum;
1332 int Temp;
1333
1334 NumProtos = ClassTemplate->NumProtos;
1335
1336 for (ProtoSetIndex = 0; ProtoSetIndex < ClassTemplate->NumProtoSets;
1337 ProtoSetIndex++) {
1338 ProtoSet = ClassTemplate->ProtoSets[ProtoSetIndex];
1339 ActualProtoNum = (ProtoSetIndex * PROTOS_PER_PROTO_SET);
1340 for (ProtoNum = 0;
1341 ((ProtoNum < PROTOS_PER_PROTO_SET)
1342 && (ActualProtoNum < NumProtos)); ProtoNum++, ActualProtoNum++) {
1343 Temp = 0;
1344 UINT8Pointer = &(ProtoEvidence[ActualProtoNum][0]);
1345 for (ProtoIndex = ClassTemplate->ProtoLengths[ActualProtoNum];
1346 ProtoIndex > 0; ProtoIndex--, UINT8Pointer++)
1347 Temp += *UINT8Pointer;
1348
1349 ConfigWord = (ProtoSet->Protos[ProtoNum]).Configs[0];
1350 ConfigWord &= *ConfigMask;
1351 IntPointer = SumOfFeatureEvidence;
1352 while (ConfigWord) {
1353 if (ConfigWord & 1)
1354 *IntPointer += Temp;
1355 IntPointer++;
1356 ConfigWord >>= 1;
1357 }
1358 }
1359 }
1360 }
1361
1362
1363
1364 /*---------------------------------------------------------------------------*/
1365 void
IMNormalizeSumOfEvidences(INT_CLASS ClassTemplate,int SumOfFeatureEvidence[MAX_NUM_CONFIGS],inT16 NumFeatures,inT32 used_features)1366 IMNormalizeSumOfEvidences (INT_CLASS ClassTemplate,
1367 int SumOfFeatureEvidence[MAX_NUM_CONFIGS],
1368 inT16 NumFeatures, inT32 used_features) {
1369 /*
1370 ** Parameters:
1371 ** Globals:
1372 ** Operation:
1373 ** Normalize Sum of Proto and Feature Evidence by dividing by
1374 ** the sum of the Feature Lengths and the Proto Lengths for each
1375 ** configuration.
1376 ** Return:
1377 ** Exceptions: none
1378 ** History: Wed Feb 27 14:12:28 MST 1991, RWM, Created.
1379 */
1380 register int *IntPointer;
1381 register int ConfigNum;
1382 int NumConfigs;
1383
1384 NumConfigs = ClassTemplate->NumConfigs;
1385
1386 IntPointer = SumOfFeatureEvidence;
1387 for (ConfigNum = 0; ConfigNum < NumConfigs; ConfigNum++, IntPointer++)
1388 *IntPointer = (*IntPointer << 8) /
1389 (NumFeatures + ClassTemplate->ConfigLengths[ConfigNum]);
1390 }
1391
1392
1393 /*---------------------------------------------------------------------------*/
1394 int
IMFindBestMatch(INT_CLASS ClassTemplate,int SumOfFeatureEvidence[MAX_NUM_CONFIGS],uinT16 BlobLength,uinT8 NormalizationFactor,INT_RESULT Result)1395 IMFindBestMatch (INT_CLASS ClassTemplate,
1396 int SumOfFeatureEvidence[MAX_NUM_CONFIGS],
1397 uinT16 BlobLength,
1398 uinT8 NormalizationFactor, INT_RESULT Result) {
1399 /*
1400 ** Parameters:
1401 ** Globals:
1402 ** Operation:
1403 ** Find the best match for the current class and update the Result
1404 ** with the configuration and match rating.
1405 ** Return:
1406 ** The best normalized sum of evidences
1407 ** Exceptions: none
1408 ** History: Wed Feb 27 14:12:28 MST 1991, RWM, Created.
1409 */
1410 register int *IntPointer;
1411 register int ConfigNum;
1412 register int NumConfigs;
1413 register int BestMatch;
1414 register int Best2Match;
1415
1416 NumConfigs = ClassTemplate->NumConfigs;
1417
1418 /* Find best match */
1419 BestMatch = 0;
1420 Best2Match = 0;
1421 IntPointer = SumOfFeatureEvidence;
1422 for (ConfigNum = 0; ConfigNum < NumConfigs; ConfigNum++, IntPointer++) {
1423 if (tord_display_ratings > 1)
1424 cprintf ("Config %d, rating=%d\n", ConfigNum, *IntPointer);
1425 if (*IntPointer > BestMatch) {
1426 if (BestMatch > 0) {
1427 Result->Config2 = Result->Config;
1428 Best2Match = BestMatch;
1429 }
1430 else
1431 Result->Config2 = ConfigNum;
1432 Result->Config = ConfigNum;
1433 BestMatch = *IntPointer;
1434 }
1435 else if (*IntPointer > Best2Match) {
1436 Result->Config2 = ConfigNum;
1437 Best2Match = *IntPointer;
1438 }
1439 }
1440
1441 /* Compute Certainty Rating */
1442 (*Result).Rating = ((65536.0 - BestMatch) / 65536.0 * BlobLength +
1443 LocalMatcherMultiplier * NormalizationFactor / 256.0) /
1444 (BlobLength + LocalMatcherMultiplier);
1445
1446 return BestMatch;
1447 }
1448
1449
1450 /*---------------------------------------------------------------------------*/
1451 #ifndef GRAPHICS_DISABLED
IMDebugBestMatch(int BestMatch,INT_RESULT Result,uinT16 BlobLength,uinT8 NormalizationFactor)1452 void IMDebugBestMatch(int BestMatch,
1453 INT_RESULT Result,
1454 uinT16 BlobLength,
1455 uinT8 NormalizationFactor) {
1456 /*
1457 ** Parameters:
1458 ** Globals:
1459 ** Operation:
1460 ** Find the best match for the current class and update the Result
1461 ** Return:
1462 ** Exceptions: none
1463 ** History: Wed Feb 27 14:12:28 MST 1991, RWM, Created.
1464 */
1465 cprintf ("Rating = %5.1f%% Best Config = %3d\n",
1466 100.0 * ((*Result).Rating), (int) ((*Result).Config));
1467 cprintf
1468 ("Matcher Error = %5.1f%% Blob Length = %3d Weight = %4.1f%%\n",
1469 100.0 * (65536.0 - BestMatch) / 65536.0, (int) BlobLength,
1470 100.0 * BlobLength / (BlobLength + LocalMatcherMultiplier));
1471 cprintf
1472 ("Char Norm Error = %5.1f%% Norm Strength = %3d Weight = %4.1f%%\n",
1473 100.0 * NormalizationFactor / 256.0, LocalMatcherMultiplier,
1474 100.0 * LocalMatcherMultiplier / (BlobLength + LocalMatcherMultiplier));
1475 }
1476 #endif
1477
1478 /*---------------------------------------------------------------------------*/
1479 void
HeapSort(int n,register int ra[],register int rb[])1480 HeapSort (int n, register int ra[], register int rb[]) {
1481 /*
1482 ** Parameters:
1483 ** n Number of elements to sort
1484 ** ra Key array [1..n]
1485 ** rb Index array [1..n]
1486 ** Globals:
1487 ** Operation:
1488 ** Sort Key array in ascending order using heap sort
1489 ** algorithm. Also sort Index array that is tied to
1490 ** the key array.
1491 ** Return:
1492 ** Exceptions: none
1493 ** History: Tue Feb 19 10:24:24 MST 1991, RWM, Created.
1494 */
1495 register int i, rra, rrb;
1496 int l, j, ir;
1497
1498 l = (n >> 1) + 1;
1499 ir = n;
1500 for (;;) {
1501 if (l > 1) {
1502 rra = ra[--l];
1503 rrb = rb[l];
1504 }
1505 else {
1506 rra = ra[ir];
1507 rrb = rb[ir];
1508 ra[ir] = ra[1];
1509 rb[ir] = rb[1];
1510 if (--ir == 1) {
1511 ra[1] = rra;
1512 rb[1] = rrb;
1513 return;
1514 }
1515 }
1516 i = l;
1517 j = l << 1;
1518 while (j <= ir) {
1519 if (j < ir && ra[j] < ra[j + 1])
1520 ++j;
1521 if (rra < ra[j]) {
1522 ra[i] = ra[j];
1523 rb[i] = rb[j];
1524 j += (i = j);
1525 }
1526 else
1527 j = ir + 1;
1528 }
1529 ra[i] = rra;
1530 rb[i] = rrb;
1531 }
1532 }
1533