Tesseract  3.02
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
con_comp.cpp
Go to the documentation of this file.
1 /**********************************************************************
2  * File: con_comp.cpp
3  * Description: Implementation of a Connected Component 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 <stdlib.h>
21 #include <string.h>
22 #include "con_comp.h"
23 #include "cube_const.h"
24 
25 namespace tesseract {
26 
28  head_ = NULL;
29  tail_ = NULL;
30  left_ = 0;
31  top_ = 0;
32  right_ = 0;
33  bottom_ = 0;
34  left_most_ = false;
35  right_most_ = false;
36  id_ = -1;
37  pt_cnt_ = 0;
38 }
39 
41  if (head_ != NULL) {
42  ConCompPt *pt_ptr = head_;
43  while (pt_ptr != NULL) {
44  ConCompPt *pptNext = pt_ptr->Next();
45  delete pt_ptr;
46  pt_ptr = pptNext;
47  }
48  head_ = NULL;
49  }
50 }
51 
52 // adds a pt to the conn comp and updates its boundaries
53 bool ConComp::Add(int x, int y) {
54  ConCompPt *pt_ptr = new ConCompPt(x, y);
55  if (pt_ptr == NULL) {
56  return false;
57  }
58 
59  if (head_ == NULL) {
60  left_ = x;
61  right_ = x;
62  top_ = y;
63  bottom_ = y;
64 
65  head_ = pt_ptr;
66  } else {
67  left_ = left_ <= x ? left_ : x;
68  top_ = top_ <= y ? top_ : y;
69  right_ = right_ >= x ? right_ : x;
70  bottom_ = bottom_ >= y ? bottom_ : y;
71  }
72 
73  if (tail_ != NULL) {
74  tail_->SetNext(pt_ptr);
75  }
76 
77  tail_ = pt_ptr;
78  pt_cnt_++;
79  return true;
80 }
81 
82 // merges two connected components
83 bool ConComp::Merge(ConComp *concomp) {
84  if (head_ == NULL || tail_ == NULL ||
85  concomp->head_ == NULL || concomp->tail_ == NULL) {
86  return false;
87  }
88 
89  tail_->SetNext(concomp->head_);
90  tail_ = concomp->tail_;
91  left_ = left_ <= concomp->left_ ? left_ : concomp->left_;
92  top_ = top_ <= concomp->top_ ? top_ : concomp->top_;
93  right_ = right_ >= concomp->right_ ? right_ : concomp->right_;
94  bottom_ = bottom_ >= concomp->bottom_ ? bottom_ : concomp->bottom_;
95  pt_cnt_ += concomp->pt_cnt_;
96 
97  concomp->head_ = NULL;
98  concomp->tail_ = NULL;
99 
100  return true;
101 }
102 
103 // Creates the x-coord density histogram after spreading
104 // each x-coord position by the HIST_WND_RATIO fraction of the
105 // height of the ConComp, but limited to max_hist_wnd
106 int *ConComp::CreateHistogram(int max_hist_wnd) {
107  int wid = right_ - left_ + 1,
108  hgt = bottom_ - top_ + 1,
109  hist_wnd = static_cast<int>(hgt * HIST_WND_RATIO);
110 
111  if (hist_wnd > max_hist_wnd) {
112  hist_wnd = max_hist_wnd;
113  }
114 
115  // alloc memo for histogram
116  int *hist_array = new int[wid];
117  if (hist_array == NULL) {
118  return NULL;
119  }
120 
121  memset(hist_array, 0, wid * sizeof(*hist_array));
122 
123  // compute windowed histogram
124  ConCompPt *pt_ptr = head_;
125 
126  while (pt_ptr != NULL) {
127  int x = pt_ptr->x() - left_,
128  xw = x - hist_wnd;
129 
130  for (int xdel = -hist_wnd; xdel <= hist_wnd; xdel++, xw++) {
131  if (xw >= 0 && xw < wid) {
132  hist_array[xw]++;
133  }
134  }
135 
136  pt_ptr = pt_ptr->Next();
137  }
138 
139  return hist_array;
140 }
141 
142 // find out the seg pts by looking for local minima in the histogram
143 int *ConComp::SegmentHistogram(int *hist_array, int *seg_pt_cnt) {
144  // init
145  (*seg_pt_cnt) = 0;
146 
147  int wid = right_ - left_ + 1,
148  hgt = bottom_ - top_ + 1;
149 
150  int *x_seg_pt = new int[wid];
151  if (x_seg_pt == NULL) {
152  return NULL;
153  }
154 
155  int seg_pt_wnd = static_cast<int>(hgt * SEG_PT_WND_RATIO);
156 
157  if (seg_pt_wnd > 1) {
158  seg_pt_wnd = 1;
159  }
160 
161  for (int x = 2; x < (wid - 2); x++) {
162  if (hist_array[x] < hist_array[x - 1] &&
163  hist_array[x] < hist_array[x - 2] &&
164  hist_array[x] <= hist_array[x + 1] &&
165  hist_array[x] <= hist_array[x + 2]) {
166  x_seg_pt[(*seg_pt_cnt)++] = x;
167  x += seg_pt_wnd;
168  } else if (hist_array[x] <= hist_array[x - 1] &&
169  hist_array[x] <= hist_array[x - 2] &&
170  hist_array[x] < hist_array[x + 1] &&
171  hist_array[x] < hist_array[x + 2]) {
172  x_seg_pt[(*seg_pt_cnt)++] = x;
173  x += seg_pt_wnd;
174  }
175  }
176 
177  // no segments, nothing to do
178  if ((*seg_pt_cnt) == 0) {
179  delete []x_seg_pt;
180  return NULL;
181  }
182 
183  return x_seg_pt;
184 }
185 
186 // segments a concomp based on pixel density histogram local minima
187 // if there were none found, it returns NULL
188 // this is more useful than creating a clone of itself
189 ConComp **ConComp::Segment(int max_hist_wnd, int *concomp_cnt) {
190  // init
191  (*concomp_cnt) = 0;
192 
193  // No pts
194  if (head_ == NULL) {
195  return NULL;
196  }
197 
198  int seg_pt_cnt = 0;
199 
200  // create the histogram
201  int *hist_array = CreateHistogram(max_hist_wnd);
202  if (hist_array == NULL) {
203  return NULL;
204  }
205 
206  int *x_seg_pt = SegmentHistogram(hist_array, &seg_pt_cnt);
207 
208  // free histogram
209  delete []hist_array;
210 
211  // no segments, nothing to do
212  if (seg_pt_cnt == 0) {
213  return NULL;
214  }
215 
216  // create concomp array
217  ConComp **concomp_array = new ConComp *[seg_pt_cnt + 1];
218  if (concomp_array == NULL) {
219  delete []x_seg_pt;
220  return NULL;
221  }
222 
223  for (int concomp = 0; concomp <= seg_pt_cnt; concomp++) {
224  concomp_array[concomp] = new ConComp();
225  if (concomp_array[concomp] == NULL) {
226  delete []x_seg_pt;
227  delete []concomp_array;
228  return NULL;
229  }
230 
231  // split concomps inherit the ID this concomp
232  concomp_array[concomp]->SetID(id_);
233  }
234 
235  // set the left and right most attributes of the
236  // appropriate concomps
237  concomp_array[0]->left_most_ = true;
238  concomp_array[seg_pt_cnt]->right_most_ = true;
239 
240  // assign pts to concomps
241  ConCompPt *pt_ptr = head_;
242  while (pt_ptr != NULL) {
243  int seg_pt;
244 
245  // find the first seg-pt that exceeds the x value
246  // of the pt
247  for (seg_pt = 0; seg_pt < seg_pt_cnt; seg_pt++) {
248  if ((x_seg_pt[seg_pt] + left_) > pt_ptr->x()) {
249  break;
250  }
251  }
252 
253  // add the pt to the proper concomp
254  if (concomp_array[seg_pt]->Add(pt_ptr->x(), pt_ptr->y()) == false) {
255  delete []x_seg_pt;
256  delete []concomp_array;
257  return NULL;
258  }
259 
260  pt_ptr = pt_ptr->Next();
261  }
262 
263  delete []x_seg_pt;
264 
265  (*concomp_cnt) = (seg_pt_cnt + 1);
266 
267  return concomp_array;
268 }
269 
270 // Shifts the co-ordinates of all points by the specified x & y deltas
271 void ConComp::Shift(int dx, int dy) {
272  ConCompPt *pt_ptr = head_;
273 
274  while (pt_ptr != NULL) {
275  pt_ptr->Shift(dx, dy);
276  pt_ptr = pt_ptr->Next();
277  }
278 
279  left_ += dx;
280  right_ += dx;
281  top_ += dy;
282  bottom_ += dy;
283 }
284 
285 } // namespace tesseract