Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
matchtab.cpp
Go to the documentation of this file.
1 /* -*-C-*-
2  ********************************************************************************
3  *
4  * File: matchtab.c (Formerly matchtab.c)
5  * Description: Match table to retain blobs that were matched.
6  * Author: Mark Seaman, OCR Technology
7  * Created: Mon Jan 29 09:00:56 1990
8  * Modified: Tue Mar 19 15:09:06 1991 (Mark Seaman) marks@hpgrlt
9  * Language: C
10  * Package: N/A
11  * Status: Experimental (Do Not Distribute)
12  *
13  * (c) Copyright 1990, Hewlett-Packard Company.
14  ** Licensed under the Apache License, Version 2.0 (the "License");
15  ** you may not use this file except in compliance with the License.
16  ** You may obtain a copy of the License at
17  ** http://www.apache.org/licenses/LICENSE-2.0
18  ** Unless required by applicable law or agreed to in writing, software
19  ** distributed under the License is distributed on an "AS IS" BASIS,
20  ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
21  ** See the License for the specific language governing permissions and
22  ** limitations under the License.
23  *
24  *********************************************************************************/
25 #include "matchtab.h"
26 
27 #include "blobs.h"
28 #include "callcpp.h"
29 #include "elst.h"
30 #include "freelist.h"
31 #include "helpers.h"
32 #include "ratngs.h"
33 
34 #define NUM_MATCH_ENTRIES 500 /* Entries in match_table */
35 
36 namespace tesseract {
37 
39  : been_initialized_(false), match_table_(NULL) {
41 }
42 
45 }
46 
47 /**********************************************************************
48  * init_match_table
49  *
50  * Create and clear a match table to be used to speed up the splitter.
51  **********************************************************************/
53  if (been_initialized_) {
54  /* Reclaim old choices */
55  for (int x = 0; x < NUM_MATCH_ENTRIES; x++) {
56  if (!IsEmpty(x)) {
57  match_table_[x].rating->clear();
58  delete match_table_[x].rating;
59  // Reinitialize the entry.
60  match_table_[x].box = TBOX();
61  match_table_[x].rating = NULL;
62  }
63  }
64  } else {
65  /* Allocate memory once */
66  match_table_ = new MATCH[NUM_MATCH_ENTRIES];
67  been_initialized_ = true;
68  }
69 }
70 
72  if (been_initialized_) {
74  delete[] match_table_;
75  match_table_ = NULL;
76  been_initialized_ = false;
77  }
78 }
79 
80 
81 /**********************************************************************
82  * put_match
83  *
84  * Put a new blob and its corresponding match ratings into the match
85  * table.
86  **********************************************************************/
87 void BlobMatchTable::put_match(TBLOB *blob, BLOB_CHOICE_LIST *ratings) {
88  if (!blob) return;
89  /* Hash into table */
90  TBOX bbox(blob->bounding_box());
91  int start = Hash(bbox);
92 
93  /* Look for empty */
94  int x = start;
95  do {
96  if (IsEmpty(x)) {
97  /* Add this entry */
98  match_table_[x].box = bbox;
99  // Copy ratings to match_table_[x].rating
100  match_table_[x].rating = new BLOB_CHOICE_LIST();
101  match_table_[x].rating->deep_copy(ratings, &BLOB_CHOICE::deep_copy);
102  return;
103  }
104  if (++x >= NUM_MATCH_ENTRIES)
105  x = 0;
106  } while (x != start);
107 
108  cprintf ("error: Match table is full\n");
109 }
110 
111 
112 /**********************************************************************
113  * get_match
114  *
115  * Look up this blob in the match table to see if it needs to be
116  * matched. If it is not present then NULL is returned.
117  **********************************************************************/
118 BLOB_CHOICE_LIST *BlobMatchTable::get_match(TBLOB *blob) {
119  return get_match_by_box(blob->bounding_box());
120 }
121 
122 /**********************************************************************
123  * Hash
124  *
125  * The hash function we use to translate a bounding box to a starting
126  * hash position in our array.
127  **********************************************************************/
128 int BlobMatchTable::Hash(const TBOX &box) const {
129  int topleft = (box.top() << 16) + box.left();
130  int botright = (box.bottom() << 16) + box.right();
131  return Modulo(topleft + botright, NUM_MATCH_ENTRIES);
132 }
133 
134 /**********************************************************************
135  * IsEmpty
136  *
137  * Returns whether the idx entry in the array is still empty.
138  **********************************************************************/
139 bool BlobMatchTable::IsEmpty(int idx) const {
140  return TBOX() == match_table_[idx].box &&
141  NULL == match_table_[idx].rating;
142 }
143 
144 /**********************************************************************
145  * get_match_by_box
146  *
147  * Look up this blob in the match table to see if it needs to be
148  * matched. If it is not present then NULL is returned.
149  **********************************************************************/
150 BLOB_CHOICE_LIST *BlobMatchTable::get_match_by_box(const TBOX &box) {
151  int start = Hash(box);
152  int x = start;
153  /* Search for match */
154  do {
155  /* Not found when blank */
156  if (IsEmpty(x))
157  break;
158  /* Is this the match ? */
159  if (match_table_[x].box == box) {
160  BLOB_CHOICE_LIST *blist = new BLOB_CHOICE_LIST();
161  blist->deep_copy(match_table_[x].rating, &BLOB_CHOICE::deep_copy);
162  return blist;
163  }
164  if (++x >= NUM_MATCH_ENTRIES)
165  x = 0;
166  } while (x != start);
167  return NULL;
168 }
169 
170 /**********************************************************************
171  * add_to_match
172  *
173  * Update ratings list in the match_table corresponding to the given
174  * blob. The function assumes that:
175  * -- the match table contains the initial non-NULL list with choices
176  * for the given blob
177  * -- the new ratings list is a superset of the corresponding list in
178  * the match_table and the unichar ids of the blob choices in the
179  * list are unique.
180  * The entries that appear in the new ratings list and not in the
181  * old one are added to the old ratings list in the match_table.
182  **********************************************************************/
183 void BlobMatchTable::add_to_match(TBLOB *blob, BLOB_CHOICE_LIST *ratings) {
184  TBOX bbox = blob->bounding_box();
185  int start = Hash(bbox);
186  int x = start;
187  do {
188  if (IsEmpty(x)) {
189  fprintf(stderr, "Can not update uninitialized entry in match_table\n");
190  ASSERT_HOST(!IsEmpty(x));
191  }
192  if (match_table_[x].box == bbox) {
193  // Copy new ratings to match_table_[x].rating.
194  BLOB_CHOICE_IT it;
195  it.set_to_list(match_table_[x].rating);
196  BLOB_CHOICE_IT new_it;
197  new_it.set_to_list(ratings);
198  assert(it.length() <= new_it.length());
199  for (it.mark_cycle_pt(), new_it.mark_cycle_pt();
200  !it.cycled_list() && !new_it.cycled_list(); new_it.forward()) {
201  if (it.data()->unichar_id() == new_it.data()->unichar_id()) {
202  it.forward();
203  } else {
204  it.add_before_stay_put(new BLOB_CHOICE(*(new_it.data())));
205  }
206  }
207  return;
208  }
209  if (++x >= NUM_MATCH_ENTRIES)
210  x = 0;
211  } while (x != start);
212 }
213 
214 } // namespace tesseract