1 /******************************************************************************
2 ** Filename: MergeNF.c
3 ** Purpose: Program for merging similar nano-feature protos
4 ** Author: Dan Johnson
5 ** History: Wed Nov 21 09:55:23 1990, DSJ, Created.
6 **
7 ** (c) Copyright Hewlett-Packard Company, 1988.
8 ** Licensed under the Apache License, Version 2.0 (the "License");
9 ** you may not use this file except in compliance with the License.
10 ** You may obtain a copy of the License at
11 ** http://www.apache.org/licenses/LICENSE-2.0
12 ** Unless required by applicable law or agreed to in writing, software
13 ** distributed under the License is distributed on an "AS IS" BASIS,
14 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 ** See the License for the specific language governing permissions and
16 ** limitations under the License.
17 ******************************************************************************/
18 /**----------------------------------------------------------------------------
19 Include Files and Type Defines
20 ----------------------------------------------------------------------------**/
21 #include "mergenf.h"
22 #include "general.h"
23 #include "efio.h"
24 #include "clusttool.h"
25 #include "cluster.h"
26 #include "oldlist.h"
27 #include "protos.h"
28 #include "ndminx.h"
29 #include "ocrfeatures.h"
30 #include "const.h"
31 #include "featdefs.h"
32 #include "intproto.h"
33 #include "varable.h"
34
35 #include <stdio.h>
36 #include <string.h>
37 #include <math.h>
38
39
40 /**----------------------------------------------------------------------------
41 Variables
42 -----------------------------------------------------------------------------**/
43 /*-------------------once in subfeat---------------------------------*/
44 double_VAR(training_angle_match_scale, 1.0, "Angle Match Scale ...");
45
46 double_VAR(training_similarity_midpoint, 0.0075, "Similarity Midpoint ...");
47
48 double_VAR(training_similarity_curl, 2.0, "Similarity Curl ...");
49
50 /*-----------------------------once in fasttrain----------------------------------*/
51 double_VAR(training_tangent_bbox_pad, 0.5, "Tangent bounding box pad ...");
52
53 double_VAR(training_orthogonal_bbox_pad, 2.5, "Orthogonal bounding box pad ...");
54
55 double_VAR(training_angle_pad, 45.0, "Angle pad ...");
56
57 /**----------------------------------------------------------------------------
58 Global Data Definitions and Declarations
59 ----------------------------------------------------------------------------**/
60 //int row_number; /* kludge due to linking problems */
61
62 /**----------------------------------------------------------------------------
63 Public Code
64 ----------------------------------------------------------------------------**/
65 /*---------------------------------------------------------------------------*/
CompareProtos(PROTO p1,PROTO p2)66 FLOAT32 CompareProtos(PROTO p1, PROTO p2) {
67 /*
68 ** Parameters:
69 ** p1, p2 protos to be compared
70 ** Globals: none
71 ** Operation: Compare protos p1 and p2 and return an estimate of the
72 ** worst evidence rating that will result for any part of p1
73 ** that is compared to p2. In other words, if p1 were broken
74 ** into pico-features and each pico-feature was matched to p2,
75 ** what is the worst evidence rating that will be achieved for
76 ** any pico-feature.
77 ** Return: Worst possible result when matching p1 to p2.
78 ** Exceptions: none
79 ** History: Mon Nov 26 08:27:53 1990, DSJ, Created.
80 */
81 FEATURE Feature;
82 FLOAT32 WorstEvidence = WORST_EVIDENCE;
83 FLOAT32 Evidence;
84 FLOAT32 Angle, Length;
85
86 /* if p1 and p2 are not close in length, don't let them match */
87 Length = fabs (p1->Length - p2->Length);
88 if (Length > MAX_LENGTH_MISMATCH)
89 return (0.0);
90
91 /* create a dummy pico-feature to be used for comparisons */
92 Feature = NewFeature (&PicoFeatDesc);
93 Feature->Params[PicoFeatDir] = p1->Angle;
94
95 /* convert angle to radians */
96 Angle = p1->Angle * 2.0 * PI;
97
98 /* find distance from center of p1 to 1/2 picofeat from end */
99 Length = p1->Length / 2.0 - GetPicoFeatureLength () / 2.0;
100 if (Length < 0) Length = 0;
101
102 /* set the dummy pico-feature at one end of p1 and match it to p2 */
103 Feature->Params[PicoFeatX] = p1->X + cos (Angle) * Length;
104 Feature->Params[PicoFeatY] = p1->Y + sin (Angle) * Length;
105 if (DummyFastMatch (Feature, p2)) {
106 Evidence = SubfeatureEvidence (Feature, p2);
107 if (Evidence < WorstEvidence)
108 WorstEvidence = Evidence;
109 } else {
110 FreeFeature (Feature);
111 return 0.0;
112 }
113
114 /* set the dummy pico-feature at the other end of p1 and match it to p2 */
115 Feature->Params[PicoFeatX] = p1->X - cos (Angle) * Length;
116 Feature->Params[PicoFeatY] = p1->Y - sin (Angle) * Length;
117 if (DummyFastMatch (Feature, p2)) {
118 Evidence = SubfeatureEvidence (Feature, p2);
119 if (Evidence < WorstEvidence)
120 WorstEvidence = Evidence;
121 } else {
122 FreeFeature (Feature);
123 return 0.0;
124 }
125
126 FreeFeature (Feature);
127 return (WorstEvidence);
128
129 } /* CompareProtos */
130
131 /*---------------------------------------------------------------------------*/
ComputeMergedProto(PROTO p1,PROTO p2,FLOAT32 w1,FLOAT32 w2,PROTO MergedProto)132 void ComputeMergedProto (
133 PROTO p1,
134 PROTO p2,
135 FLOAT32 w1,
136 FLOAT32 w2,
137 PROTO MergedProto)
138
139 /*
140 ** Parameters:
141 ** p1, p2 protos to be merged
142 ** w1, w2 weight of each proto
143 ** MergedProto place to put resulting merged proto
144 ** Globals: none
145 ** Operation: This routine computes a proto which is the weighted
146 ** average of protos p1 and p2. The new proto is returned
147 ** in MergedProto.
148 ** Return: none (results are returned in MergedProto)
149 ** Exceptions: none
150 ** History: Mon Nov 26 08:15:08 1990, DSJ, Created.
151 */
152
153 {
154 FLOAT32 TotalWeight;
155
156 TotalWeight = w1 + w2;
157 w1 /= TotalWeight;
158 w2 /= TotalWeight;
159
160 MergedProto->X = p1->X * w1 + p2->X * w2;
161 MergedProto->Y = p1->Y * w1 + p2->Y * w2;
162 MergedProto->Length = p1->Length * w1 + p2->Length * w2;
163 MergedProto->Angle = p1->Angle * w1 + p2->Angle * w2;
164 FillABC (MergedProto);
165 } /* ComputeMergedProto */
166
167 /*---------------------------------------------------------------------------*/
FindClosestExistingProto(CLASS_TYPE Class,int NumMerged[],PROTOTYPE * Prototype)168 int FindClosestExistingProto(CLASS_TYPE Class, int NumMerged[],
169 PROTOTYPE *Prototype) {
170 /*
171 ** Parameters:
172 ** Class class to search for matching old proto in
173 ** NumMerged[] # of protos merged into each proto of Class
174 ** Prototype new proto to find match for
175 ** Globals: none
176 ** Operation: This routine searches thru all of the prototypes in
177 ** Class and returns the id of the proto which would provide
178 ** the best approximation of Prototype. If no close
179 ** approximation can be found, NO_PROTO is returned.
180 ** Return: Id of closest proto in Class or NO_PROTO.
181 ** Exceptions: none
182 ** History: Sat Nov 24 11:42:58 1990, DSJ, Created.
183 */
184 PROTO_STRUCT NewProto;
185 PROTO_STRUCT MergedProto;
186 int Pid;
187 PROTO Proto;
188 int BestProto;
189 FLOAT32 BestMatch;
190 FLOAT32 Match, OldMatch, NewMatch;
191
192 MakeNewFromOld (&NewProto, Prototype);
193
194 BestProto = NO_PROTO;
195 BestMatch = WORST_MATCH_ALLOWED;
196 for (Pid = 0; Pid < Class->NumProtos; Pid++) {
197 Proto = ProtoIn (Class, Pid);
198 ComputeMergedProto (Proto, &NewProto,
199 (FLOAT32) NumMerged[Pid], 1.0, &MergedProto);
200 OldMatch = CompareProtos (Proto, &MergedProto);
201 NewMatch = CompareProtos (&NewProto, &MergedProto);
202 Match = MIN (OldMatch, NewMatch);
203 if (Match > BestMatch) {
204 BestProto = Pid;
205 BestMatch = Match;
206 }
207 }
208 return BestProto;
209 } /* FindClosestExistingProto */
210
211 /*---------------------------------------------------------------------------*/
MakeNewFromOld(PROTO New,PROTOTYPE * Old)212 void MakeNewFromOld(PROTO New, PROTOTYPE *Old) {
213 /*
214 ** Parameters:
215 ** New new proto to be filled in
216 ** Old old proto to be converted
217 ** Globals: none
218 ** Operation: This fills in the fields of the New proto based on the
219 ** fields of the Old proto.
220 ** Return: none
221 ** Exceptions: none
222 ** History: Mon Nov 26 09:45:39 1990, DSJ, Created.
223 */
224 New->X = CenterX(Old->Mean);
225 New->Y = CenterY(Old->Mean);
226 New->Length = LengthOf(Old->Mean);
227 New->Angle = OrientationOf(Old->Mean);
228 FillABC (New);
229 } /* MakeNewFromOld */
230
231 /*-------------------once in subfeat---------------------------------*/
232
233 /**********************************************************************
234 * SubfeatureEvidence
235 *
236 * Compare a feature to a prototype. Print the result.
237 **********************************************************************/
SubfeatureEvidence(FEATURE Feature,PROTO Proto)238 FLOAT32 SubfeatureEvidence(FEATURE Feature, PROTO Proto) {
239 float Distance;
240 float Dangle;
241
242 Dangle = Proto->Angle - Feature->Params[PicoFeatDir];
243 if (Dangle < -0.5) Dangle += 1.0;
244 if (Dangle > 0.5) Dangle -= 1.0;
245 Dangle *= training_angle_match_scale;
246
247 Distance = Proto->A * Feature->Params[PicoFeatX] +
248 Proto->B * Feature->Params[PicoFeatY] +
249 Proto->C;
250
251 return (EvidenceOf (Distance * Distance + Dangle * Dangle));
252 }
253
254 /**********************************************************************
255 * EvidenceOf
256 *
257 * Return the new type of evidence number corresponding to this
258 * distance value. This number is no longer based on the chi squared
259 * approximation. The equation that represents the transform is:
260 * 1 / (1 + (sim / midpoint) ^ curl)
261 **********************************************************************/
EvidenceOf(register FLOAT32 Similarity)262 FLOAT32 EvidenceOf (
263 register FLOAT32 Similarity)
264 {
265
266 Similarity /= training_similarity_midpoint;
267
268 if (training_similarity_curl == 3)
269 Similarity = Similarity * Similarity * Similarity;
270 else if (training_similarity_curl == 2)
271 Similarity = Similarity * Similarity;
272 else
273 Similarity = static_cast<float>(pow(static_cast<double>(Similarity),
274 training_similarity_curl));
275
276 return (1.0 / (1.0 + Similarity));
277 }
278
279 /*---------------------------------------------------------------------------*/
DummyFastMatch(FEATURE Feature,PROTO Proto)280 BOOL8 DummyFastMatch (
281 FEATURE Feature,
282 PROTO Proto)
283
284 /*
285 ** Parameters:
286 ** Feature feature to be "fast matched" to proto
287 ** Proto proto being "fast matched" against
288 ** Globals:
289 ** training_tangent_bbox_pad bounding box pad tangent to proto
290 ** training_orthogonal_bbox_pad bounding box pad orthogonal to proto
291 ** Operation: This routine returns TRUE if Feature would be matched
292 ** by a fast match table built from Proto.
293 ** Return: TRUE if feature could match Proto.
294 ** Exceptions: none
295 ** History: Wed Nov 14 17:19:58 1990, DSJ, Created.
296 */
297
298 {
299 FRECT BoundingBox;
300 FLOAT32 MaxAngleError;
301 FLOAT32 AngleError;
302
303 MaxAngleError = training_angle_pad / 360.0;
304 AngleError = fabs (Proto->Angle - Feature->Params[PicoFeatDir]);
305 if (AngleError > 0.5)
306 AngleError = 1.0 - AngleError;
307
308 if (AngleError > MaxAngleError)
309 return (FALSE);
310
311 ComputePaddedBoundingBox (Proto,
312 training_tangent_bbox_pad * GetPicoFeatureLength (),
313 training_orthogonal_bbox_pad * GetPicoFeatureLength (),
314 &BoundingBox);
315
316 return PointInside(&BoundingBox, Feature->Params[PicoFeatX],
317 Feature->Params[PicoFeatY]);
318 } /* DummyFastMatch */
319
320 /*----------------------------------------------------------------------------*/
ComputePaddedBoundingBox(PROTO Proto,FLOAT32 TangentPad,FLOAT32 OrthogonalPad,FRECT * BoundingBox)321 void ComputePaddedBoundingBox (PROTO Proto, FLOAT32 TangentPad,
322 FLOAT32 OrthogonalPad, FRECT *BoundingBox) {
323 /*
324 ** Parameters:
325 ** Proto proto to compute bounding box for
326 ** TangentPad amount of pad to add in direction of segment
327 ** OrthogonalPad amount of pad to add orthogonal to segment
328 ** BoundingBox place to put results
329 ** Globals: none
330 ** Operation: This routine computes a bounding box that encloses the
331 ** specified proto along with some padding. The
332 ** amount of padding is specified as separate distances
333 ** in the tangential and orthogonal directions.
334 ** Return: none (results are returned in BoundingBox)
335 ** Exceptions: none
336 ** History: Wed Nov 14 14:55:30 1990, DSJ, Created.
337 */
338 FLOAT32 Pad, Length, Angle;
339 FLOAT32 CosOfAngle, SinOfAngle;
340
341 Length = Proto->Length / 2.0 + TangentPad;
342 Angle = Proto->Angle * 2.0 * PI;
343 CosOfAngle = fabs (cos (Angle));
344 SinOfAngle = fabs (sin (Angle));
345
346 Pad = MAX (CosOfAngle * Length, SinOfAngle * OrthogonalPad);
347 BoundingBox->MinX = Proto->X - Pad;
348 BoundingBox->MaxX = Proto->X + Pad;
349
350 Pad = MAX (SinOfAngle * Length, CosOfAngle * OrthogonalPad);
351 BoundingBox->MinY = Proto->Y - Pad;
352 BoundingBox->MaxY = Proto->Y + Pad;
353
354 } /* ComputePaddedBoundingBox */
355
356 /*--------------------------------------------------------------------------*/
PointInside(FRECT * Rectangle,FLOAT32 X,FLOAT32 Y)357 BOOL8 PointInside(FRECT *Rectangle, FLOAT32 X, FLOAT32 Y) {
358 /*
359 ** Parameters:
360 ** Globals: none
361 ** Operation: Return TRUE if point (X,Y) is inside of Rectangle.
362 ** Return: Return TRUE if point (X,Y) is inside of Rectangle.
363 ** Exceptions: none
364 ** History: Wed Nov 14 17:26:35 1990, DSJ, Created.
365 */
366 if (X < Rectangle->MinX) return (FALSE);
367 if (X > Rectangle->MaxX) return (FALSE);
368 if (Y < Rectangle->MinY) return (FALSE);
369 if (Y > Rectangle->MaxY) return (FALSE);
370 return (TRUE);
371
372 } /* PointInside */
373