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
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
27 ConComp::ConComp() {
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
40 ConComp::~ConComp() {
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