00001
00020 #include "mfcpch.h"
00021 #include <stdio.h>
00022 #include <ctype.h>
00023 #include <math.h>
00024 #ifdef __UNIX__
00025 #include <assert.h>
00026 #include <unistd.h>
00027 #endif
00028 #include "memry.h"
00029 #include "tessvars.h"
00030 #include "statistc.h"
00031 #include "charsample.h"
00032 #include "paircmp.h"
00033 #include "matmatch.h"
00034 #include "adaptions.h"
00035 #include "secname.h"
00036 #include "notdll.h"
00037
00039 extern INT32 demo_word;
00040
00041 ELISTIZE (CHAR_SAMPLE)
00042 ELISTIZE (CHAR_SAMPLES)
00043
00044 CHAR_SAMPLE::CHAR_SAMPLE () {
00045 sample_blob = NULL;
00046 sample_denorm = NULL;
00047 sample_image = NULL;
00048 ch = '\0';
00049 n_samples_matched = 0;
00050 total_match_scores = 0.0;
00051 sumsq_match_scores = 0.0;
00052 }
00053
00054
00055 CHAR_SAMPLE::CHAR_SAMPLE(PBLOB *blob, DENORM *denorm, char c) {
00056 sample_blob = blob;
00057 sample_denorm = denorm;
00058 sample_image = NULL;
00059 ch = c;
00060 n_samples_matched = 0;
00061 total_match_scores = 0.0;
00062 sumsq_match_scores = 0.0;
00063 }
00064
00065
00066 CHAR_SAMPLE::CHAR_SAMPLE(IMAGE *image, char c) {
00067 sample_blob = NULL;
00068 sample_denorm = NULL;
00069 sample_image = image;
00070 ch = c;
00071 n_samples_matched = 0;
00072 total_match_scores = 0.0;
00073 sumsq_match_scores = 0.0;
00074 }
00075
00076
00085 float CHAR_SAMPLE::match_sample(
00086 CHAR_SAMPLE *test_sample,
00087 BOOL8 updating) {
00088 float score1;
00089 float score2;
00090 IMAGE *image = test_sample->image ();
00091
00092 if (sample_blob != NULL && test_sample->blob () != NULL) {
00093 PBLOB *blob = test_sample->blob ();
00094 DENORM *denorm = test_sample->denorm ();
00095
00096 score1 = compare_bln_blobs (sample_blob, sample_denorm, blob, denorm);
00097 score2 = compare_bln_blobs (blob, denorm, sample_blob, sample_denorm);
00098
00099 score1 = (score1 > score2) ? score1 : score2;
00100 }
00101 else if (sample_image != NULL && image != NULL) {
00102 CHAR_PROTO *sample = new CHAR_PROTO (this);
00103
00104 score1 = matrix_match (sample_image, image);
00105 delete sample;
00106 }
00107 else
00108 return BAD_SCORE;
00109
00110 if ((tessedit_use_best_sample || tessedit_cluster_debug) && updating) {
00111 n_samples_matched++;
00112 total_match_scores += score1;
00113 sumsq_match_scores += score1 * score1;
00114 }
00115 return score1;
00116 }
00117
00118
00126 double CHAR_SAMPLE::mean_score() {
00127 if (n_samples_matched > 0)
00128 return (total_match_scores / n_samples_matched);
00129 else
00130 return BAD_SCORE;
00131 }
00132
00133
00136 double CHAR_SAMPLE::variance() {
00137 double mean = mean_score ();
00138
00139 if (n_samples_matched > 0) {
00140 return (sumsq_match_scores / n_samples_matched) - mean * mean;
00141 }
00142 else
00143 return BAD_SCORE;
00144 }
00145
00146
00149 void CHAR_SAMPLE::print(FILE *f) {
00150 if (!tessedit_cluster_debug)
00151 return;
00152
00153 if (n_samples_matched > 0)
00154 fprintf (f,
00155 "%c - sample matched against " INT32FORMAT
00156 " blobs, mean: %f, var: %f\n", ch, n_samples_matched,
00157 mean_score (), variance ());
00158 else
00159 fprintf (f, "No matches for this sample (%c)\n", ch);
00160 }
00161
00162
00165 void CHAR_SAMPLE::reset_match_statistics() {
00166 n_samples_matched = 0;
00167 total_match_scores = 0.0;
00168 sumsq_match_scores = 0.0;
00169 }
00170
00171
00174 CHAR_SAMPLES::CHAR_SAMPLES() {
00175 type = UNKNOWN;
00176 samples.clear ();
00177 ch = '\0';
00178 best_sample = NULL;
00179 proto = NULL;
00180 }
00181
00182
00185 CHAR_SAMPLES::CHAR_SAMPLES(CHAR_SAMPLE *sample) {
00186 CHAR_SAMPLE_IT sample_it = &samples;
00187
00188 ASSERT_HOST (sample->image () != NULL || sample->blob () != NULL);
00189
00190 if (sample->image () != NULL)
00191 type = IMAGE_CLUSTER;
00192 else if (sample->blob () != NULL)
00193 type = BLOB_CLUSTER;
00194
00195 samples.clear ();
00196 sample_it.add_to_end (sample);
00197 if (tessedit_mm_only_match_same_char)
00198 ch = sample->character ();
00199 else
00200 ch = '\0';
00201 best_sample = NULL;
00202 proto = NULL;
00203 }
00204
00205
00208 void CHAR_SAMPLES::add_sample(CHAR_SAMPLE *sample) {
00209 CHAR_SAMPLE_IT sample_it = &samples;
00210
00211 if (tessedit_use_best_sample || tessedit_cluster_debug)
00212 for (sample_it.mark_cycle_pt ();
00213 !sample_it.cycled_list (); sample_it.forward ()) {
00214 sample_it.data ()->match_sample (sample, TRUE);
00215 sample->match_sample (sample_it.data (), TRUE);
00216 }
00217
00218 sample_it.add_to_end (sample);
00219
00220 if (tessedit_mm_use_prototypes && type == IMAGE_CLUSTER)
00221 if (samples.length () == tessedit_mm_prototype_min_size)
00222 this->build_prototype ();
00223 else if (samples.length () > tessedit_mm_prototype_min_size)
00224 this->add_sample_to_prototype (sample);
00225 }
00226
00227
00230 void CHAR_SAMPLES::add_sample_to_prototype(CHAR_SAMPLE *sample) {
00231 BOOL8 rebuild = FALSE;
00232 INT32 new_xsize = proto->x_size ();
00233 INT32 new_ysize = proto->y_size ();
00234 INT32 sample_xsize = sample->image ()->get_xsize ();
00235 INT32 sample_ysize = sample->image ()->get_ysize ();
00236
00237 if (sample_xsize > new_xsize) {
00238 new_xsize = sample_xsize;
00239 rebuild = TRUE;
00240 }
00241 if (sample_ysize > new_ysize) {
00242 new_ysize = sample_ysize;
00243 rebuild = TRUE;
00244 }
00245
00246 if (rebuild)
00247 proto->enlarge_prototype (new_xsize, new_ysize);
00248
00249 proto->add_sample (sample);
00250 }
00251
00252
00256 void CHAR_SAMPLES::build_prototype() {
00257 CHAR_SAMPLE_IT sample_it = &samples;
00258 CHAR_SAMPLE *sample;
00259 INT32 proto_xsize = 0;
00260 INT32 proto_ysize = 0;
00261
00262 if (type != IMAGE_CLUSTER
00263 || samples.length () < tessedit_mm_prototype_min_size)
00264 return;
00265
00266
00267 for (sample_it.mark_cycle_pt ();
00268 !sample_it.cycled_list (); sample_it.forward ()) {
00269 sample = sample_it.data ();
00270 if (sample->image ()->get_xsize () > proto_xsize)
00271 proto_xsize = sample->image ()->get_xsize ();
00272 if (sample->image ()->get_ysize () > proto_ysize)
00273 proto_ysize = sample->image ()->get_ysize ();
00274 }
00275
00276 proto = new CHAR_PROTO (proto_xsize, proto_ysize, 0, 0, '\0');
00277
00278
00279 for (sample_it.mark_cycle_pt ();
00280 !sample_it.cycled_list (); sample_it.forward ())
00281 this->add_sample_to_prototype (sample_it.data ());
00282 }
00283
00284
00287 void CHAR_SAMPLES::find_best_sample() {
00288 CHAR_SAMPLE_IT sample_it = &samples;
00289 double score;
00290 double best_score = MAX_INT32;
00291
00292 if (ch == '\0' || samples.length () < tessedit_mm_prototype_min_size)
00293 return;
00294
00295 for (sample_it.mark_cycle_pt ();
00296 !sample_it.cycled_list (); sample_it.forward ()) {
00297 score = sample_it.data ()->mean_score ();
00298 if (score < best_score) {
00299 best_score = score;
00300 best_sample = sample_it.data ();
00301 }
00302 }
00303 #ifndef SECURE_NAMES
00304 if (tessedit_cluster_debug) {
00305 tprintf ("Best sample for this %c cluster:\n", ch);
00306 best_sample->print (debug_fp);
00307 }
00308 #endif
00309 }
00310
00311
00314 float CHAR_SAMPLES::match_score(CHAR_SAMPLE *sample) {
00315 if (tessedit_mm_only_match_same_char && sample->character () != ch)
00316 return BAD_SCORE;
00317
00318 if (tessedit_use_best_sample && best_sample != NULL)
00319 return best_sample->match_sample (sample, FALSE);
00320 else if ((tessedit_mm_use_prototypes
00321 || tessedit_mm_adapt_using_prototypes) && proto != NULL)
00322 return proto->match_sample (sample);
00323 else
00324 return this->nn_match_score (sample);
00325 }
00326
00327
00330 float CHAR_SAMPLES::nn_match_score(CHAR_SAMPLE *sample) {
00331 CHAR_SAMPLE_IT sample_it = &samples;
00332 float score;
00333 float min_score = MAX_INT32;
00334
00335 for (sample_it.mark_cycle_pt ();
00336 !sample_it.cycled_list (); sample_it.forward ()) {
00337 score = sample_it.data ()->match_sample (sample, FALSE);
00338 if (score < min_score)
00339 min_score = score;
00340 }
00341
00342 return min_score;
00343 }
00344
00345
00348 void CHAR_SAMPLES::assign_to_char() {
00349 STATS char_frequency(FIRST_CHAR, LAST_CHAR);
00350 CHAR_SAMPLE_IT sample_it = &samples;
00351 INT32 i;
00352 INT32 max_index = 0;
00353 INT32 max_freq = 0;
00354
00355 if (samples.length () == 0 || tessedit_mm_only_match_same_char)
00356 return;
00357
00358 for (sample_it.mark_cycle_pt ();
00359 !sample_it.cycled_list (); sample_it.forward ())
00360 char_frequency.add ((INT32) sample_it.data ()->character (), 1);
00361
00362 for (i = FIRST_CHAR; i <= LAST_CHAR; i++)
00363 if (char_frequency.pile_count (i) > max_freq) {
00364 max_index = i;
00365 max_freq = char_frequency.pile_count (i);
00366 }
00367
00368 if (samples.length () >= tessedit_cluster_min_size
00369 && max_freq > samples.length () * tessedit_cluster_accept_fraction)
00370 ch = (char) max_index;
00371 }
00372
00373
00376 void CHAR_SAMPLES::print(FILE *f) {
00377 CHAR_SAMPLE_IT sample_it = &samples;
00378
00379 fprintf (f, "Collected " INT32FORMAT " samples\n", samples.length ());
00380
00381 #ifndef SECURE_NAMES
00382 if (tessedit_cluster_debug)
00383 for (sample_it.mark_cycle_pt ();
00384 !sample_it.cycled_list (); sample_it.forward ())
00385 sample_it.data ()->print (f);
00386
00387 if (ch == '\0')
00388 fprintf (f, "\nCluster not used for adaption\n");
00389 else
00390 fprintf (f, "\nCluster used to adapt to '%c's\n", ch);
00391 #endif
00392 }
00393
00396 CHAR_PROTO::CHAR_PROTO() {
00397 xsize = 0;
00398 ysize = 0;
00399 ch = '\0';
00400 nsamples = 0;
00401 proto_data = NULL;
00402 proto = NULL;
00403 }
00404
00407 CHAR_PROTO::CHAR_PROTO(INT32 x_size,
00408 INT32 y_size,
00409 INT32 n_samples,
00410 float initial_value,
00411 char c) {
00412 INT32 x;
00413 INT32 y;
00414
00415 xsize = x_size;
00416 ysize = y_size;
00417 ch = c;
00418 nsamples = n_samples;
00419
00420 ALLOC_2D_ARRAY(xsize, ysize, proto_data, proto, float);
00421
00422 for (y = 0; y < ysize; y++)
00423 for (x = 0; x < xsize; x++)
00424 proto[x][y] = initial_value;
00425 }
00426
00427
00430 CHAR_PROTO::CHAR_PROTO(CHAR_SAMPLE *sample) {
00431 INT32 x;
00432 INT32 y;
00433 IMAGELINE imline_s;
00434
00435 if (sample->image () == NULL) {
00436 xsize = 0;
00437 ysize = 0;
00438 ch = '\0';
00439 nsamples = 0;
00440 proto_data = NULL;
00441 proto = NULL;
00442 }
00443 else {
00444 ch = sample->character ();
00445 xsize = sample->image ()->get_xsize ();
00446 ysize = sample->image ()->get_ysize ();
00447 nsamples = 1;
00448
00449 ALLOC_2D_ARRAY(xsize, ysize, proto_data, proto, float);
00450
00451 for (y = 0; y < ysize; y++) {
00452 sample->image ()->fast_get_line (0, y, xsize, &imline_s);
00453 for (x = 0; x < xsize; x++)
00454 if (imline_s.pixels[x] == BINIM_WHITE)
00455 proto[x][y] = 1.0;
00456 else
00457 proto[x][y] = -1.0;
00458 }
00459 }
00460 }
00461
00462
00466 CHAR_PROTO::~CHAR_PROTO () {
00467 if (proto_data != NULL)
00468 FREE_2D_ARRAY(proto_data, proto);
00469 }
00470
00471
00474 float CHAR_PROTO::match_sample(CHAR_SAMPLE *test_sample) {
00475 CHAR_PROTO *test_proto;
00476 float score;
00477
00478 if (test_sample->image () != NULL) {
00479 test_proto = new CHAR_PROTO (test_sample);
00480 if (xsize > test_proto->x_size ())
00481 score = this->match (test_proto);
00482 else {
00483 demo_word = -demo_word;
00484 score = test_proto->match (this);
00485 }
00486 }
00487 else
00488 return BAD_SCORE;
00489
00490 delete test_proto;
00491
00492 return score;
00493 }
00494
00495
00498 float CHAR_PROTO::match(CHAR_PROTO *test_proto) {
00499 INT32 xsize2 = test_proto->x_size ();
00500 INT32 y_size;
00501 INT32 y_size2;
00502 INT32 x_offset;
00503 INT32 y_offset;
00504 INT32 x;
00505 INT32 y;
00506 CHAR_PROTO *match_proto;
00507 float score;
00508 float sum = 0.0;
00509
00510 ASSERT_HOST (xsize >= xsize2);
00511
00512 x_offset = (xsize - xsize2) / 2;
00513
00514 if (ysize < test_proto->y_size ()) {
00515 y_size = test_proto->y_size ();
00516 y_size2 = ysize;
00517 y_offset = (y_size - y_size2) / 2;
00518
00519 match_proto = new CHAR_PROTO (xsize,
00520 y_size,
00521 nsamples * test_proto->n_samples (),
00522 0, '\0');
00523
00524 for (y = 0; y < y_offset; y++) {
00525 for (x = 0; x < xsize2; x++) {
00526 match_proto->data ()[x + x_offset][y] =
00527 test_proto->data ()[x][y] * nsamples;
00528 sum += match_proto->data ()[x + x_offset][y];
00529 }
00530 }
00531
00532 for (y = y_offset + y_size2; y < y_size; y++) {
00533 for (x = 0; x < xsize2; x++) {
00534 match_proto->data ()[x + x_offset][y] =
00535 test_proto->data ()[x][y] * nsamples;
00536 sum += match_proto->data ()[x + x_offset][y];
00537 }
00538 }
00539
00540 for (y = y_offset; y < y_offset + y_size2; y++) {
00541 for (x = 0; x < x_offset; x++) {
00542 match_proto->data ()[x][y] = proto[x][y - y_offset] *
00543 test_proto->n_samples ();
00544 sum += match_proto->data ()[x][y];
00545 }
00546
00547 for (x = x_offset + xsize2; x < xsize; x++) {
00548 match_proto->data ()[x][y] = proto[x][y - y_offset] *
00549 test_proto->n_samples ();
00550 sum += match_proto->data ()[x][y];
00551 }
00552
00553 for (x = x_offset; x < x_offset + xsize2; x++) {
00554 match_proto->data ()[x][y] =
00555 proto[x][y - y_offset] * test_proto->data ()[x - x_offset][y];
00556 sum += match_proto->data ()[x][y];
00557 }
00558 }
00559 }
00560 else {
00561 y_size = ysize;
00562 y_size2 = test_proto->y_size ();
00563 y_offset = (y_size - y_size2) / 2;
00564
00565 match_proto = new CHAR_PROTO (xsize,
00566 y_size,
00567 nsamples * test_proto->n_samples (),
00568 0, '\0');
00569
00570 for (y = 0; y < y_offset; y++)
00571 for (x = 0; x < xsize; x++) {
00572 match_proto->data ()[x][y] =
00573 proto[x][y] * test_proto->n_samples ();
00574 sum += match_proto->data ()[x][y];
00575 }
00576
00577 for (y = y_offset + y_size2; y < y_size; y++)
00578 for (x = 0; x < xsize; x++) {
00579 match_proto->data ()[x][y] =
00580 proto[x][y] * test_proto->n_samples ();
00581 sum += match_proto->data ()[x][y];
00582 }
00583
00584 for (y = y_offset; y < y_offset + y_size2; y++) {
00585 for (x = 0; x < x_offset; x++) {
00586 match_proto->data ()[x][y] =
00587 proto[x][y] * test_proto->n_samples ();
00588 sum += match_proto->data ()[x][y];
00589 }
00590
00591 for (x = x_offset + xsize2; x < xsize; x++) {
00592 match_proto->data ()[x][y] =
00593 proto[x][y] * test_proto->n_samples ();
00594 sum += match_proto->data ()[x][y];
00595 }
00596
00597 for (x = x_offset; x < x_offset + xsize2; x++) {
00598 match_proto->data ()[x][y] = proto[x][y] *
00599 test_proto->data ()[x - x_offset][y - y_offset];
00600 sum += match_proto->data ()[x][y];
00601 }
00602 }
00603 }
00604
00605 score = (1.0 - sum /
00606 (xsize * y_size * nsamples * test_proto->n_samples ()));
00607
00608 if (tessedit_mm_debug) {
00609 if (score < 0) {
00610 tprintf ("Match score %f\n", score);
00611 tprintf ("x: %d, y: %d, ns: %d, nt: %d, dx %d, dy: %d\n",
00612 xsize, y_size, nsamples, test_proto->n_samples (),
00613 x_offset, y_offset);
00614 for (y = 0; y < y_size; y++) {
00615 tprintf ("\n%d", y);
00616 for (x = 0; x < xsize; x++)
00617 tprintf ("\t%d", match_proto->data ()[x][y]);
00618
00619 }
00620 tprintf ("\n");
00621 fflush(debug_fp);
00622 }
00623 }
00624
00625 #ifndef GRAPHICS_DISABLED
00626 if (tessedit_display_mm) {
00627 tprintf ("Match score %f\n", score);
00628 display_images (this->make_image (),
00629 test_proto->make_image (), match_proto->make_image ());
00630 }
00631 else if (demo_word != 0) {
00632 if (demo_word > 0)
00633 display_image (test_proto->make_image (), "Test sample",
00634 300, 400, FALSE);
00635 else
00636 display_image (this->make_image (), "Test sample", 300, 400, FALSE);
00637
00638 display_image (match_proto->make_image (), "Best match",
00639 700, 400, TRUE);
00640 }
00641 #endif
00642
00643 delete match_proto;
00644
00645 return score;
00646 }
00647
00648
00651 void CHAR_PROTO::enlarge_prototype(INT32 new_xsize, INT32 new_ysize) {
00652 float *old_proto_data = proto_data;
00653 float **old_proto = proto;
00654 INT32 old_xsize = xsize;
00655 INT32 old_ysize = ysize;
00656 INT32 x_offset;
00657 INT32 y_offset;
00658 INT32 x;
00659 INT32 y;
00660
00661 ASSERT_HOST (new_xsize >= xsize && new_ysize >= ysize);
00662
00663 xsize = new_xsize;
00664 ysize = new_ysize;
00665 ALLOC_2D_ARRAY(xsize, ysize, proto_data, proto, float);
00666 x_offset = (xsize - old_xsize) / 2;
00667 y_offset = (ysize - old_ysize) / 2;
00668
00669 for (y = 0; y < y_offset; y++)
00670 for (x = 0; x < xsize; x++)
00671 proto[x][y] = nsamples;
00672
00673 for (y = y_offset + old_ysize; y < ysize; y++)
00674 for (x = 0; x < xsize; x++)
00675 proto[x][y] = nsamples;
00676
00677 for (y = y_offset; y < y_offset + old_ysize; y++) {
00678 for (x = 0; x < x_offset; x++)
00679 proto[x][y] = nsamples;
00680
00681 for (x = x_offset + old_xsize; x < xsize; x++)
00682 proto[x][y] = nsamples;
00683
00684 for (x = x_offset; x < x_offset + old_xsize; x++)
00685 proto[x][y] = old_proto[x - x_offset][y - y_offset];
00686 }
00687
00688 FREE_2D_ARRAY(old_proto_data, old_proto);
00689 }
00690
00691
00694 void CHAR_PROTO::add_sample(CHAR_SAMPLE *sample) {
00695 INT32 x_offset;
00696 INT32 y_offset;
00697 INT32 x;
00698 INT32 y;
00699 IMAGELINE imline_s;
00700 INT32 sample_xsize = sample->image ()->get_xsize ();
00701 INT32 sample_ysize = sample->image ()->get_ysize ();
00702
00703 x_offset = (xsize - sample_xsize) / 2;
00704 y_offset = (ysize - sample_ysize) / 2;
00705
00706 ASSERT_HOST (x_offset >= 0 && y_offset >= 0);
00707
00708 for (y = 0; y < y_offset; y++)
00709 for (x = 0; x < xsize; x++)
00710 proto[x][y]++;
00711 for (y = y_offset + sample_ysize; y < ysize; y++)
00712 for (x = 0; x < xsize; x++)
00713 proto[x][y]++;
00714
00715 for (y = y_offset; y < y_offset + sample_ysize; y++) {
00716 sample->image ()->fast_get_line (0,
00717 y - y_offset, sample_xsize, &imline_s);
00718 for (x = x_offset; x < x_offset + sample_xsize; x++) {
00719 if (imline_s.pixels[x - x_offset] == BINIM_WHITE)
00720 proto[x][y]++;
00721 else
00722 proto[x][y]--;
00723 }
00724
00725 for (x = 0; x < x_offset; x++)
00726 proto[x][y]++;
00727
00728 for (x = x_offset + sample_xsize; x < xsize; x++)
00729 proto[x][y]++;
00730 }
00731
00732 nsamples++;
00733 }
00734
00735
00738 IMAGE *CHAR_PROTO::make_image() {
00739 IMAGE *image;
00740 IMAGELINE imline_p;
00741 INT32 x;
00742 INT32 y;
00743
00744 ASSERT_HOST (nsamples != 0);
00745
00746 image = new (IMAGE);
00747 image->create (xsize, ysize, 8);
00748
00749 for (y = 0; y < ysize; y++) {
00750 image->fast_get_line (0, y, xsize, &imline_p);
00751
00752 for (x = 0; x < xsize; x++) {
00753 imline_p.pixels[x] = 128 +
00754 (UINT8) ((proto[x][y] * 128.0) / (0.00001 + nsamples));
00755 }
00756
00757 image->fast_put_line (0, y, xsize, &imline_p);
00758 }
00759 return image;
00760 }