1 /******************************************************************************
2 ** Filename: mfx.c
3 ** Purpose: Micro feature extraction routines
4 ** Author: Dan Johnson
5 ** History: 7/21/89, 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 "mfdefs.h"
22 #include "mfoutline.h"
23 #include "clusttool.h" //NEEDED
24 #include "const.h"
25 #include "intfx.h"
26 #include "varable.h"
27
28 #include <math.h>
29
30 /**----------------------------------------------------------------------------
31 Variables
32 ----------------------------------------------------------------------------**/
33
34 /* old numbers corresponded to 10.0 degrees and 80.0 degrees */
35 double_VAR(classify_min_slope, 0.414213562,
36 "Slope below which lines are called horizontal");
37 double_VAR(classify_max_slope, 2.414213562,
38 "Slope above which lines are called vertical");
39 double_VAR(classify_noise_segment_length, 0.00,
40 "Length below which outline segments are treated as noise");
41
42 /**----------------------------------------------------------------------------
43 Macros
44 ----------------------------------------------------------------------------**/
45 /* miscellaneous macros */
46 #define NormalizeAngle(A) ( (((A)<0)?((A)+2*PI):(A)) / (2*PI) )
47
48 /*----------------------------------------------------------------------------
49 Private Function Prototypes
50 -----------------------------------------------------------------------------*/
51 void ComputeBulges(MFOUTLINE Start, MFOUTLINE End, MICROFEATURE MicroFeature);
52
53 FLOAT32 ComputeOrientation(MFEDGEPT *Start, MFEDGEPT *End);
54
55 MICROFEATURES ConvertToMicroFeatures(MFOUTLINE Outline,
56 MICROFEATURES MicroFeatures);
57
58 MICROFEATURE ExtractMicroFeature(MFOUTLINE Start, MFOUTLINE End);
59
60 void SmearBulges(MICROFEATURES MicroFeatures, FLOAT32 XScale, FLOAT32 YScale);
61
62 /**----------------------------------------------------------------------------
63 Public Code
64 ----------------------------------------------------------------------------**/
65
66 /*---------------------------------------------------------------------------*/
BlobMicroFeatures(TBLOB * Blob,LINE_STATS * LineStats)67 CHAR_FEATURES BlobMicroFeatures(TBLOB *Blob, LINE_STATS *LineStats) {
68 /*
69 ** Parameters:
70 ** Blob blob to extract micro-features from
71 ** LineStats statistics for text line normalization
72 ** Operation:
73 ** This routine extracts micro-features from the specified
74 ** blob and returns a list of the micro-features. All
75 ** micro-features are normalized according to the specified
76 ** line statistics.
77 ** Return: List of micro-features extracted from the blob.
78 ** Exceptions: none
79 ** History: 7/21/89, DSJ, Created.
80 */
81 MICROFEATURES MicroFeatures = NIL;
82 FLOAT32 XScale, YScale;
83 LIST Outlines;
84 LIST RemainingOutlines;
85 MFOUTLINE Outline;
86 INT_FEATURE_ARRAY blfeatures;
87 INT_FEATURE_ARRAY cnfeatures;
88 INT_FX_RESULT_STRUCT results;
89
90 if (Blob != NULL) {
91 Outlines = ConvertBlob (Blob);
92 // NormalizeOutlines(Outlines, LineStats, &XScale, &YScale);
93 if (!ExtractIntFeat(Blob, blfeatures, cnfeatures, &results))
94 return NULL;
95 XScale = 0.2f / results.Ry;
96 YScale = 0.2f / results.Rx;
97
98 RemainingOutlines = Outlines;
99 iterate(RemainingOutlines) {
100 Outline = (MFOUTLINE) first_node (RemainingOutlines);
101 CharNormalizeOutline (Outline,
102 results.Xmean, results.Ymean,
103 XScale, YScale);
104 }
105
106 RemainingOutlines = Outlines;
107 iterate(RemainingOutlines) {
108 Outline = (MFOUTLINE) first_node (RemainingOutlines);
109 FindDirectionChanges(Outline, classify_min_slope, classify_max_slope);
110 FilterEdgeNoise(Outline, classify_noise_segment_length);
111 MarkDirectionChanges(Outline);
112 SmearExtremities(Outline, XScale, YScale);
113 MicroFeatures = ConvertToMicroFeatures (Outline, MicroFeatures);
114 }
115 SmearBulges(MicroFeatures, XScale, YScale);
116 FreeOutlines(Outlines);
117 }
118 return ((CHAR_FEATURES) MicroFeatures);
119 } /* BlobMicroFeatures */
120
121
122 /**----------------------------------------------------------------------------
123 Private Macros
124 ----------------------------------------------------------------------------**/
125 /**********************************************************************
126 * angle_of
127 *
128 * Return the angle of the line between two points.
129 **********************************************************************/
130 #define angle_of(x1,y1,x2,y2) \
131 ((x2-x1) ? \
132 (atan2 (y2-y1, x2-x1)) : \
133 ((y2<y1) ? (- PI / 2.0) : (PI / 2.0))) \
134
135
136 /**********************************************************************
137 * scale_angle
138 *
139 * Make sure that the angle is non-negative. Scale it to the right
140 * amount.
141 **********************************************************************/
142
143 #define scale_angle(x) \
144 (((x<0) ? (2.0 * PI + x) : (x)) * 0.5 / PI) \
145
146 /*---------------------------------------------------------------------------
147 Private Code
148 ---------------------------------------------------------------------------*/
149 /*---------------------------------------------------------------------------*/
ComputeBulges(MFOUTLINE Start,MFOUTLINE End,MICROFEATURE MicroFeature)150 void ComputeBulges(MFOUTLINE Start, MFOUTLINE End, MICROFEATURE MicroFeature) {
151 /*
152 ** Parameters:
153 ** Start starting point of micro-feature
154 ** End ending point of micro-feature
155 ** MicroFeature micro-feature whose bulges are to be computed
156 ** Globals: none
157 ** Operation:
158 ** This routine computes the size of the "bulges" of the
159 ** specified micro-feature. The bulges are the deviations
160 ** of the micro-features from a straight line at the 1/3
161 ** and 2/3 points along the straight line approximation of
162 ** the micro-feature. The size of each bulge is normalized
163 ** to the range -0.5 to 0.5. A positive bulge indicates a
164 ** deviation in the counterclockwise direction and vice versa.
165 ** A size of 0.5 (+ or -) corresponds to the largest bulge that
166 ** could ever occur for the given feature independent of
167 ** orientation. This routine assumes that Start
168 ** and End are not the same point. It also assumes that the
169 ** orientation and length parameters of the micro-feature
170 ** have already been computed.
171 ** Return: none
172 ** Exceptions: none
173 ** History: 7/27/89, DSJ, Created.
174 */
175 MATRIX_2D Matrix;
176 MFEDGEPT *Origin;
177 MFOUTLINE SegmentStart, SegmentEnd;
178 FPOINT CurrentPoint, LastPoint;
179 FLOAT32 BulgePosition;
180
181 /* check for simple case */
182 if (End == NextPointAfter (Start))
183 MicroFeature[FIRSTBULGE] = MicroFeature[SECONDBULGE] = 0;
184 else {
185 Origin = PointAt (Start);
186
187 InitMatrix(&Matrix);
188 RotateMatrix (&Matrix, MicroFeature[ORIENTATION] * -2.0 * PI);
189 TranslateMatrix (&Matrix, -Origin->Point.x, -Origin->Point.y);
190
191 SegmentEnd = Start;
192 CurrentPoint.x = 0.0f;
193 CurrentPoint.y = 0.0f;
194 BulgePosition = MicroFeature[MFLENGTH] / 3;
195 LastPoint = CurrentPoint;
196 while (CurrentPoint.x < BulgePosition) {
197 SegmentStart = SegmentEnd;
198 SegmentEnd = NextPointAfter (SegmentStart);
199 LastPoint = CurrentPoint;
200
201 MapPoint(&Matrix, PointAt(SegmentEnd)->Point, &CurrentPoint);
202 }
203 MicroFeature[FIRSTBULGE] =
204 XIntersectionOf(LastPoint, CurrentPoint, BulgePosition);
205
206 BulgePosition *= 2;
207
208 // Prevents from copying the points before computing the bulge if
209 // CurrentPoint will not change. (Which would cause to output nan
210 // for the SecondBulge.)
211 if (CurrentPoint.x < BulgePosition)
212 LastPoint = CurrentPoint;
213 while (CurrentPoint.x < BulgePosition) {
214 SegmentStart = SegmentEnd;
215 SegmentEnd = NextPointAfter (SegmentStart);
216 LastPoint = CurrentPoint;
217 MapPoint(&Matrix, PointAt(SegmentEnd)->Point, &CurrentPoint);
218 }
219 MicroFeature[SECONDBULGE] =
220 XIntersectionOf(LastPoint, CurrentPoint, BulgePosition);
221
222 MicroFeature[FIRSTBULGE] /= BULGENORMALIZER * MicroFeature[MFLENGTH];
223 MicroFeature[SECONDBULGE] /= BULGENORMALIZER * MicroFeature[MFLENGTH];
224 }
225 } /* ComputeBulges */
226
227
228 /*---------------------------------------------------------------------------*/
ComputeOrientation(MFEDGEPT * Start,MFEDGEPT * End)229 FLOAT32 ComputeOrientation(MFEDGEPT *Start, MFEDGEPT *End) {
230 /*
231 ** Parameters:
232 ** Start starting edge point of micro-feature
233 ** End ending edge point of micro-feature
234 ** Globals: none
235 ** Operation:
236 ** This routine computes the orientation parameter of the
237 ** specified micro-feature. The orientation is the angle of
238 ** the vector from Start to End. It is normalized to a number
239 ** between 0 and 1 where 0 corresponds to 0 degrees and 1
240 ** corresponds to 360 degrees. The actual range is [0,1), i.e.
241 ** 1 is excluded from the range (since it is actual the
242 ** same orientation as 0). This routine assumes that Start
243 ** and End are not the same point.
244 ** Return: Orientation parameter for the specified micro-feature.
245 ** Exceptions: none
246 ** History: 7/27/89, DSJ, Created.
247 */
248 FLOAT32 Orientation;
249
250 Orientation = NormalizeAngle (AngleFrom (Start->Point, End->Point));
251
252 /* ensure that round-off errors do not put circular param out of range */
253 if ((Orientation < 0) || (Orientation >= 1))
254 Orientation = 0;
255 return (Orientation);
256 } /* ComputeOrientation */
257
258
259 /*---------------------------------------------------------------------------*/
ConvertToMicroFeatures(MFOUTLINE Outline,MICROFEATURES MicroFeatures)260 MICROFEATURES ConvertToMicroFeatures(MFOUTLINE Outline,
261 MICROFEATURES MicroFeatures) {
262 /*
263 ** Parameters:
264 ** Outline outline to extract micro-features from
265 ** MicroFeatures list of micro-features to add to
266 ** Globals: none
267 ** Operation:
268 ** This routine
269 ** Return: List of micro-features with new features added to front.
270 ** Exceptions: none
271 ** History: 7/26/89, DSJ, Created.
272 */
273 MFOUTLINE Current;
274 MFOUTLINE Last;
275 MFOUTLINE First;
276 MICROFEATURE NewFeature;
277
278 if (DegenerateOutline (Outline))
279 return (MicroFeatures);
280
281 First = NextExtremity (Outline);
282 Last = First;
283 do {
284 Current = NextExtremity (Last);
285 NewFeature = ExtractMicroFeature (Last, Current);
286 if (NewFeature != NULL)
287 MicroFeatures = push (MicroFeatures, NewFeature);
288 Last = Current;
289 }
290 while (Last != First);
291
292 return (MicroFeatures);
293 } /* ConvertToMicroFeatures */
294
295
296 /*---------------------------------------------------------------------------*/
ExtractMicroFeature(MFOUTLINE Start,MFOUTLINE End)297 MICROFEATURE ExtractMicroFeature(MFOUTLINE Start, MFOUTLINE End) {
298 /*
299 ** Parameters:
300 ** Start starting point of micro-feature
301 ** End ending point of micro-feature
302 ** Globals: none
303 ** Operation:
304 ** This routine computes the feature parameters which describe
305 ** the micro-feature that starts and Start and ends at End.
306 ** A new micro-feature is allocated, filled with the feature
307 ** parameters, and returned. The routine assumes that
308 ** Start and End are not the same point. If they are the
309 ** same point, NULL is returned, a warning message is
310 ** printed, and the current outline is dumped to stdout.
311 ** Return: New micro-feature or NULL if the feature was rejected.
312 ** Exceptions: none
313 ** History: 7/26/89, DSJ, Created.
314 ** 11/17/89, DSJ, Added handling for Start and End same point.
315 */
316 MICROFEATURE NewFeature;
317 MFEDGEPT *P1, *P2;
318
319 P1 = PointAt (Start);
320 P2 = PointAt (End);
321
322 NewFeature = NewMicroFeature ();
323 NewFeature[XPOSITION] = AverageOf (P1->Point.x, P2->Point.x);
324 NewFeature[YPOSITION] = AverageOf (P1->Point.y, P2->Point.y);
325 NewFeature[MFLENGTH] = DistanceBetween (P1->Point, P2->Point);
326 NewFeature[ORIENTATION] = NormalizedAngleFrom(&P1->Point, &P2->Point, 1.0);
327 ComputeBulges(Start, End, NewFeature);
328 return (NewFeature);
329 } /* ExtractMicroFeature */
330
331
332 /*---------------------------------------------------------------------------*/
SmearBulges(MICROFEATURES MicroFeatures,FLOAT32 XScale,FLOAT32 YScale)333 void SmearBulges(MICROFEATURES MicroFeatures, FLOAT32 XScale, FLOAT32 YScale) {
334 /*
335 ** Parameters:
336 ** MicroFeatures features to be smeared
337 ** XScale # of normalized units per pixel in x dir
338 ** YScale # of normalized units per pixel in y dir
339 ** Globals: none
340 ** Operation: Add a random amount to each bulge parameter of each
341 ** feature. The amount added is between -0.5 pixels and
342 ** 0.5 pixels. This is done to prevent the prototypes
343 ** generated in training from being unrealistically tight.
344 ** Return: none
345 ** Exceptions: none
346 ** History: Thu Jun 28 18:03:38 1990, DSJ, Created.
347 */
348 MICROFEATURE MicroFeature;
349 FLOAT32 MinSmear;
350 FLOAT32 MaxSmear;
351 FLOAT32 Cos, Sin;
352 FLOAT32 Scale;
353
354 iterate(MicroFeatures) {
355 MicroFeature = NextFeatureOf (MicroFeatures);
356
357 Cos = fabs(cos(2.0 * PI * MicroFeature[ORIENTATION]));
358 Sin = fabs(sin(2.0 * PI * MicroFeature[ORIENTATION]));
359 Scale = YScale * Cos + XScale * Sin;
360
361 MinSmear = -0.5 * Scale / (BULGENORMALIZER * MicroFeature[MFLENGTH]);
362 MaxSmear = 0.5 * Scale / (BULGENORMALIZER * MicroFeature[MFLENGTH]);
363
364 MicroFeature[FIRSTBULGE] += UniformRandomNumber (MinSmear, MaxSmear);
365 MicroFeature[SECONDBULGE] += UniformRandomNumber (MinSmear, MaxSmear);
366 }
367 } /* SmearBulges */
368