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
cube_search_object.cpp
Go to the documentation of this file.
1 /**********************************************************************
2 * File: cube_search_object.cpp
3 * Description: Implementation of the Cube Search Object Class
4 * Author: Ahmad Abdulkader
5 * Created: 2007
6 *
7 * (C) Copyright 2008, Google Inc.
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
20 #include "cube_search_object.h"
21 #include "cube_utils.h"
22 #include "ndminx.h"
23
24 namespace tesseract {
25
26 const bool CubeSearchObject::kUseCroppedChars = true;
27
28 CubeSearchObject::CubeSearchObject(CubeRecoContext *cntxt, CharSamp *samp)
29 : SearchObject(cntxt) {
30 init_ = false;
31 reco_cache_ = NULL;
32 samp_cache_ = NULL;
33 segments_ = NULL;
34 segment_cnt_ = 0;
35 samp_ = samp;
36 left_ = 0;
37 itop_ = 0;
38 space_cost_ = NULL;
39 no_space_cost_ = NULL;
40 wid_ = samp_->Width();
41 hgt_ = samp_->Height();
42 max_seg_per_char_ = cntxt_->Params()->MaxSegPerChar();
43 rtl_ = (cntxt_->ReadingOrder() == CubeRecoContext::R2L);
44 min_spc_gap_ =
45 static_cast<int>(hgt_ * cntxt_->Params()->MinSpaceHeightRatio());
46 max_spc_gap_ =
47 static_cast<int>(hgt_ * cntxt_->Params()->MaxSpaceHeightRatio());
48 }
49
50 CubeSearchObject::~CubeSearchObject() {
51 Cleanup();
52 }
53
54 // Cleanup
55 void CubeSearchObject::Cleanup() {
56 // delete Recognition Cache
57 if (reco_cache_) {
58 for (int strt_seg = 0; strt_seg < segment_cnt_; strt_seg++) {
59 if (reco_cache_[strt_seg]) {
60 for (int end_seg = 0; end_seg < segment_cnt_; end_seg++) {
61 if (reco_cache_[strt_seg][end_seg]) {
62 delete reco_cache_[strt_seg][end_seg];
63 }
64 }
65 delete []reco_cache_[strt_seg];
66 }
67 }
68 delete []reco_cache_;
69 reco_cache_ = NULL;
70 }
71
72 // delete CharSamp Cache
73 if (samp_cache_) {
74 for (int strt_seg = 0; strt_seg < segment_cnt_; strt_seg++) {
75 if (samp_cache_[strt_seg]) {
76 for (int end_seg = 0; end_seg < segment_cnt_; end_seg++) {
77 if (samp_cache_[strt_seg][end_seg]) {
78 delete samp_cache_[strt_seg][end_seg];
79 }
80 }
81 delete []samp_cache_[strt_seg];
82 }
83 }
84 delete []samp_cache_;
85 samp_cache_ = NULL;
86 }
87
88 // delete segment list
89 if (segments_) {
90 for (int seg = 0; seg < segment_cnt_; seg++) {
91 if (segments_[seg]) {
92 delete segments_[seg];
93 }
94 }
95 delete []segments_;
96 segments_ = NULL;
97 }
98
99 if (space_cost_) {
100 delete []space_cost_;
101 space_cost_ = NULL;
102 }
103
104 if (no_space_cost_) {
105 delete []no_space_cost_;
106 no_space_cost_ = NULL;
107 }
108
109 segment_cnt_ = 0;
110 init_ = false;
111 }
112
113 // # of segmentation points. One less than the count of segments
114 int CubeSearchObject::SegPtCnt() {
115 if (!init_ && !Init())
116 return -1;
117 return segment_cnt_ - 1;
118 }
119
120 // init and allocate variables, perform segmentation
121 bool CubeSearchObject::Init() {
122 if (init_)
123 return true;
124 if (!Segment()) {
125 return false;
126 }
127
128 // init cache
129 reco_cache_ = new CharAltList **[segment_cnt_];
130 if (reco_cache_ == NULL) {
131 fprintf(stderr, "Cube ERROR (CubeSearchObject::Init): could not "
132 "allocate CharAltList array\n");
133 return false;
134 }
135
136 samp_cache_ = new CharSamp **[segment_cnt_];
137 if (samp_cache_ == NULL) {
138 fprintf(stderr, "Cube ERROR (CubeSearchObject::Init): could not "
139 "allocate CharSamp array\n");
140 return false;
141 }
142
143 for (int seg = 0; seg < segment_cnt_; seg++) {
144 reco_cache_[seg] = new CharAltList *[segment_cnt_];
145 if (reco_cache_[seg] == NULL) {
146 fprintf(stderr, "Cube ERROR (CubeSearchObject::Init): could not "
147 "allocate a single segment's CharAltList array\n");
148 return false;
149 }
150
151 memset(reco_cache_[seg], 0, segment_cnt_ * sizeof(*reco_cache_[seg]));
152
153 samp_cache_[seg] = new CharSamp *[segment_cnt_];
154 if (samp_cache_[seg] == NULL) {
155 fprintf(stderr, "Cube ERROR (CubeSearchObject::Init): could not "
156 "allocate a single segment's CharSamp array\n");
157 return false;
158 }
159
160 memset(samp_cache_[seg], 0, segment_cnt_ * sizeof(*samp_cache_[seg]));
161 }
162
163 init_ = true;
164 return true;
165 }
166
167 // returns a char sample corresponding to the bitmap between 2 seg pts
168 CharSamp *CubeSearchObject::CharSample(int start_pt, int end_pt) {
169 // init if necessary
170 if (!init_ && !Init())
171 return NULL;
172 // validate segment range
173 if (!IsValidSegmentRange(start_pt, end_pt))
174 return NULL;
175
176 // look for the samp in the cache
177 if (samp_cache_ && samp_cache_[start_pt + 1] &&
178 samp_cache_[start_pt + 1][end_pt]) {
179 return samp_cache_[start_pt + 1][end_pt];
180 }
181 // create a char samp object from the specified range of segments
182 bool left_most;
183 bool right_most;
184 CharSamp *samp = CharSamp::FromConComps(segments_, start_pt + 1,
185 end_pt - start_pt, NULL,
186 &left_most, &right_most, hgt_);
187 if (!samp)
188 return NULL;
189
190 if (kUseCroppedChars) {
191 CharSamp *cropped_samp = samp->Crop();
192 // we no longer need the orig sample
193 delete samp;
194 if (!cropped_samp)
195 return NULL;
196 samp = cropped_samp;
197 }
198
199 // get the dimensions of the new cropped sample
200 int char_top = samp->Top();
201 int char_wid = samp->Width();
202 int char_hgt = samp->Height();
203
204 // for cursive languages, these features correspond to whether
205 // the charsamp is at the beginning or end of conncomp
206 if (cntxt_->Cursive() == true) {
207 // first and last char flags depend on reading order
208 bool first_char = rtl_ ? right_most : left_most;
209 bool last_char = rtl_ ? left_most : right_most;
210
211 samp->SetFirstChar(first_char ? 255 : 0);
212 samp->SetLastChar(last_char ? 255 : 0);
213 } else {
214 // for non cursive languages, these features correspond
215 // to whether the charsamp is at the begining or end of the word
216 samp->SetFirstChar((start_pt == -1) ? 255 : 0);
217 samp->SetLastChar((end_pt == (segment_cnt_ - 1)) ? 255 : 0);
218 }
219 samp->SetNormTop(255 * char_top / hgt_);
220 samp->SetNormBottom(255 * (char_top + char_hgt) / hgt_);
221 samp->SetNormAspectRatio(255 * char_wid / (char_wid + char_hgt));
222
223 // add to cache & return
224 samp_cache_[start_pt + 1][end_pt] = samp;
225 return samp;
226 }
227
228 Box *CubeSearchObject::CharBox(int start_pt, int end_pt) {
229 if (!init_ && !Init())
230 return NULL;
231 if (!IsValidSegmentRange(start_pt, end_pt)) {
232 fprintf(stderr, "Cube ERROR (CubeSearchObject::CharBox): invalid "
233 "segment range (%d, %d)\n", start_pt, end_pt);
234 return NULL;
235 }
236
237 // create a char samp object from the specified range of segments,
238 // extract its dimensions into a leptonica box, and delete it
239 bool left_most;
240 bool right_most;
241 CharSamp *samp = CharSamp::FromConComps(segments_, start_pt + 1,
242 end_pt - start_pt, NULL,
243 &left_most, &right_most, hgt_);
244 if (!samp)
245 return NULL;
246 if (kUseCroppedChars) {
247 CharSamp *cropped_samp = samp->Crop();
248 delete samp;
249 if (!cropped_samp) {
250 return NULL;
251 }
252 samp = cropped_samp;
253 }
254 Box *box = boxCreate(samp->Left(), samp->Top(),
255 samp->Width(), samp->Height());
256 delete samp;
257 return box;
258 }
259
260 // call from Beam Search to return the alt list corresponding to
261 // recognizing the bitmap between two segmentation pts
262 CharAltList * CubeSearchObject::RecognizeSegment(int start_pt, int end_pt) {
263 // init if necessary
264 if (!init_ && !Init()) {
265 fprintf(stderr, "Cube ERROR (CubeSearchObject::RecognizeSegment): could "
266 "not initialize CubeSearchObject\n");
267 return NULL;
268 }
269
270 // validate segment range
271 if (!IsValidSegmentRange(start_pt, end_pt)) {
272 fprintf(stderr, "Cube ERROR (CubeSearchObject::RecognizeSegment): invalid "
273 "segment range (%d, %d)\n", start_pt, end_pt);
274 return NULL;
275 }
276
277 // look for the recognition results in cache in the cache
278 if (reco_cache_ && reco_cache_[start_pt + 1] &&
279 reco_cache_[start_pt + 1][end_pt]) {
280 return reco_cache_[start_pt + 1][end_pt];
281 }
282
283 // create the char sample corresponding to the blob
284 CharSamp *samp = CharSample(start_pt, end_pt);
285 if (!samp) {
286 fprintf(stderr, "Cube ERROR (CubeSearchObject::RecognizeSegment): could "
287 "not construct CharSamp\n");
288 return NULL;
289 }
290
291 // recognize the char sample
292 CharClassifier *char_classifier = cntxt_->Classifier();
293 if (char_classifier) {
294 reco_cache_[start_pt + 1][end_pt] = char_classifier->Classify(samp);
295 } else {
296 // no classifer: all characters are equally probable; add a penalty
297 // that favors 2-segment characters and aspect ratios (w/h) > 1
298 fprintf(stderr, "Cube WARNING (CubeSearchObject::RecognizeSegment): cube "
299 "context has no character classifier!! Inventing a probability "
300 "distribution.\n");
301 int class_cnt = cntxt_->CharacterSet()->ClassCount();
302 CharAltList *alt_list = new CharAltList(cntxt_->CharacterSet(), class_cnt);
303 int seg_cnt = end_pt - start_pt;
304 double prob_val = (1.0 / class_cnt) *
305 exp(-abs(seg_cnt - 2.0)) *
306 exp(-samp->Width() / static_cast<double>(samp->Height()));
307
308 if (alt_list) {
309 for (int class_idx = 0; class_idx < class_cnt; class_idx++) {
310 alt_list->Insert(class_idx, CubeUtils::Prob2Cost(prob_val));
311 }
312 reco_cache_[start_pt + 1][end_pt] = alt_list;
313 }
314 }
315
316 return reco_cache_[start_pt + 1][end_pt];
317 }
318
319 // Perform segmentation of the bitmap by detecting connected components,
320 // segmenting each connected component using windowed vertical pixel density
321 // histogram and sorting the resulting segments in reading order
322 bool CubeSearchObject::Segment() {
323 if (!samp_)
324 return false;
325 segment_cnt_ = 0;
326 segments_ = samp_->Segment(&segment_cnt_, rtl_,
327 cntxt_->Params()->HistWindWid(),
328 cntxt_->Params()->MinConCompSize());
329 if (!segments_ || segment_cnt_ <= 0) {
330 return false;
331 }
332 if (segment_cnt_ >= kMaxSegmentCnt) {
333 return false;
334 }
335 return true;
336 }
337
338 // computes the space and no space costs at gaps between segments
339 bool CubeSearchObject::ComputeSpaceCosts() {
340 // init if necessary
341 if (!init_ && !Init())
342 return false;
343
344 // Already computed
345 if (space_cost_)
346 return true;
347
348 // No segmentation points
349 if (segment_cnt_ < 2)
350 return false;
351
352 // Compute the maximum x to the left of and minimum x to the right of each
353 // segmentation point
354 int *max_left_x = new int[segment_cnt_ - 1];
355 int *min_right_x = new int[segment_cnt_ - 1];
356 if (!max_left_x || !min_right_x) {
357 delete []min_right_x;
358 delete []max_left_x;
359 return false;
360 }
361 if (rtl_) {
362 min_right_x[0] = segments_[0]->Left();
363 max_left_x[segment_cnt_ - 2] = segments_[segment_cnt_ - 1]->Right();
364 for (int pt_idx = 1; pt_idx < (segment_cnt_ - 1); pt_idx++) {
365 min_right_x[pt_idx] =
366 MIN(min_right_x[pt_idx - 1], segments_[pt_idx]->Left());
367 max_left_x[segment_cnt_ - pt_idx - 2] =
368 MAX(max_left_x[segment_cnt_ - pt_idx - 1],
369 segments_[segment_cnt_ - pt_idx - 1]->Right());
370 }
371 } else {
372 min_right_x[segment_cnt_ - 2] = segments_[segment_cnt_ - 1]->Left();
373 max_left_x[0] = segments_[0]->Right();
374 for (int pt_idx = 1; pt_idx < (segment_cnt_ - 1); pt_idx++) {
375 min_right_x[segment_cnt_ - pt_idx - 2] =
376 MIN(min_right_x[segment_cnt_ - pt_idx - 1],
377 segments_[segment_cnt_ - pt_idx - 1]->Left());
378 max_left_x[pt_idx] =
379 MAX(max_left_x[pt_idx - 1], segments_[pt_idx]->Right());
380 }
381 }
382
383 // Allocate memory for space and no space costs
384 // trivial cases
385 space_cost_ = new int[segment_cnt_ - 1];
386 no_space_cost_ = new int[segment_cnt_ - 1];
387 if (!space_cost_ || !no_space_cost_) {
388 delete []min_right_x;
389 delete []max_left_x;
390 return false;
391 }
392
393 // go through all segmentation points determining the horizontal gap between
394 // the images on both sides of each break points. Use the gap to estimate
395 // the probability of a space. The probability is modeled a linear function
396 // of the gap width
397 for (int pt_idx = 0; pt_idx < (segment_cnt_ - 1); pt_idx++) {
398 // determine the gap at the segmentation point
399 int gap = min_right_x[pt_idx] - max_left_x[pt_idx];
400 float prob = 0.0;
401
402 // gap is too small => no space
403 if (gap < min_spc_gap_) {
404 prob = 0.0;
405 } else if (gap > max_spc_gap_) {
406 // gap is too big => definite space
407 prob = 1.0;
408 } else {
409 // gap is somewhere in between, compute probability
410 prob = (gap - min_spc_gap_) /
411 static_cast<double>(max_spc_gap_ - min_spc_gap_);
412 }
413
414 // compute cost of space and non-space
415 space_cost_[pt_idx] = CubeUtils::Prob2Cost(prob) +
416 CubeUtils::Prob2Cost(0.1);
417 no_space_cost_[pt_idx] = CubeUtils::Prob2Cost(1.0 - prob);
418 }
419
420 delete []min_right_x;
421 delete []max_left_x;
422
423 return true;
424 }
425
426 // Returns the cost of having a space before the specified segmentation point
427 int CubeSearchObject::SpaceCost(int pt_idx) {
428 if (!space_cost_ && !ComputeSpaceCosts()) {
429 // Failed to compute costs return a zero prob
430 return CubeUtils::Prob2Cost(0.0);
431 }
432 return space_cost_[pt_idx];
433 }
434
435 // Returns the cost of not having a space before the specified
436 // segmentation point
437 int CubeSearchObject::NoSpaceCost(int pt_idx) {
438 // If failed to compute costs, return a 1.0 prob
439 if (!space_cost_ && !ComputeSpaceCosts())
440 return CubeUtils::Prob2Cost(0.0);
441 return no_space_cost_[pt_idx];
442 }
443
444 // Returns the cost of not having any spaces within the specified range
445 // of segmentation points
446 int CubeSearchObject::NoSpaceCost(int st_pt, int end_pt) {
447 // If fail to compute costs, return a 1.0 prob
448 if (!space_cost_ && !ComputeSpaceCosts())
449 return CubeUtils::Prob2Cost(1.0);
450 int no_spc_cost = 0;
451 for (int pt_idx = st_pt + 1; pt_idx < end_pt; pt_idx++)
452 no_spc_cost += NoSpaceCost(pt_idx);
453 return no_spc_cost;
454 }
455 }