Tesseract 3.02

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

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
38 BlobMatchTable::BlobMatchTable()
39 : been_initialized_(false), match_table_(NULL) {
40 init_match_table();
41 }
42
43 BlobMatchTable::~BlobMatchTable() {
44 end_match_table();
45 }
46
47 /**********************************************************************
48 * init_match_table
49 *
50 * Create and clear a match table to be used to speed up the splitter.
51 **********************************************************************/
52 void BlobMatchTable::init_match_table() {
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
71 void BlobMatchTable::end_match_table() {
72 if (been_initialized_) {
73 init_match_table();
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