1 /* GNU Ocrad - Optical Character Recognition program
2 Copyright (C) 2003-2019 Antonio Diaz Diaz.
3
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 2 of the License, or
7 (at your option) any later version.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18 #include <algorithm>
19 #include <cstdio>
20 #include <cstdlib>
21 #include <vector>
22
23 #include "common.h"
24 #include "rectangle.h"
25 #include "track.h"
26
27
28 namespace {
29
error(const char * const msg)30 void error( const char * const msg )
31 { Ocrad::internal_error( msg ); }
32
33
good_reference(const Rectangle & r1,const Rectangle & r2,int & val,const int mean_height,const int mean_width)34 int good_reference( const Rectangle & r1, const Rectangle & r2, int & val,
35 const int mean_height, const int mean_width )
36 {
37 if( 4 * r1.height() >= 3 * mean_height &&
38 4 * r2.height() >= 3 * mean_height &&
39 ( r1.width() >= mean_width || r2.width() >= mean_width ) && val > 0 )
40 {
41 if( 4 * r1.height() <= 5 * mean_height &&
42 4 * r2.height() <= 5 * mean_height )
43 {
44 if( 9 * r1.height() <= 10 * mean_height &&
45 9 * r2.height() <= 10 * mean_height &&
46 10 * std::abs( r1.bottom() - r2.bottom() ) <= mean_height )
47 { val = 0; return ( r1.height() <= r2.height() ) ? 0 : 1; }
48 if( val > 1 && 10 * std::abs( r1.vcenter() - r2.vcenter() ) <= mean_height )
49 { val = 1; return ( r1.bottom() <= r2.bottom() ) ? 0 : 1; }
50 }
51 if( val > 2 && 10 * std::abs( r1.vcenter() - r2.vcenter() ) <= mean_height )
52 { val = 2; return ( r1.bottom() <= r2.bottom() ) ? 0 : 1; }
53 }
54 return -1;
55 }
56
57
set_l(const std::vector<Rectangle> & rectangle_vector,const int mean_height,const int mean_width)58 int set_l( const std::vector< Rectangle > & rectangle_vector,
59 const int mean_height, const int mean_width )
60 {
61 const int rectangles = rectangle_vector.size();
62 const int imax = rectangles / 4;
63 int ibest = -1, val = 3;
64 for( int i1 = 0; i1 < imax && val > 0; ++i1 )
65 for( int i2 = i1 + 1; i2 <= imax && i2 <= i1 + 2; ++i2 )
66 {
67 int i = good_reference( rectangle_vector[i1], rectangle_vector[i2],
68 val, mean_height, mean_width );
69 if( i >= 0 ) { ibest = (i == 0) ? i1 : i2; if( val == 0 ) break; }
70 }
71 return ibest;
72 }
73
74
set_r(const std::vector<Rectangle> & rectangle_vector,const int mean_height,const int mean_width)75 int set_r( const std::vector< Rectangle > & rectangle_vector,
76 const int mean_height, const int mean_width )
77 {
78 const int rectangles = rectangle_vector.size();
79 const int imin = rectangles - 1 - ( rectangles / 4 );
80 int ibest = -1, val = 3;
81 for( int i1 = rectangles - 1; i1 > imin && val > 0; --i1 )
82 for( int i2 = i1 - 1; i2 >= imin && i2 >= i1 - 2; --i2 )
83 {
84 int i = good_reference( rectangle_vector[i1], rectangle_vector[i2],
85 val, mean_height, mean_width );
86 if( i >= 0 ) { ibest = (i == 0) ? i1 : i2; if( val == 0 ) break; }
87 }
88 return ibest;
89 }
90
91
set_partial_track(const std::vector<Rectangle> & rectangle_vector)92 Vrhomboid set_partial_track( const std::vector< Rectangle > & rectangle_vector )
93 {
94 const int rectangles = rectangle_vector.size();
95 int mean_vcenter = 0, mean_height = 0, mean_width = 0;
96
97 for( int i = 0; i < rectangles; ++i )
98 {
99 mean_vcenter += rectangle_vector[i].vcenter();
100 mean_height += rectangle_vector[i].height();
101 mean_width += rectangle_vector[i].width();
102 }
103 if( rectangles )
104 { mean_vcenter /= rectangles; mean_height /= rectangles; mean_width /= rectangles; }
105
106 // short line
107 if( rectangles < 8 )
108 return Vrhomboid( rectangle_vector.front().left(), mean_vcenter,
109 rectangle_vector.back().right(), mean_vcenter,
110 mean_height );
111
112 // look for reference rectangles (characters)
113 int l = set_l( rectangle_vector, mean_height, mean_width );
114 int r = set_r( rectangle_vector, mean_height, mean_width );
115
116 int lcol, lvc, rcol, rvc;
117 if( l >= 0 )
118 {
119 lcol = rectangle_vector[l].hcenter();
120 lvc = rectangle_vector[l].bottom() - ( mean_height / 2 );
121 }
122 else { lcol = rectangle_vector.front().hcenter(); lvc = mean_vcenter; }
123 if( r >= 0 )
124 {
125 rcol = rectangle_vector[r].hcenter();
126 rvc = rectangle_vector[r].bottom() - ( mean_height / 2 );
127 }
128 else { rcol = rectangle_vector.back().hcenter(); rvc = mean_vcenter; }
129 Vrhomboid tmp( lcol, lvc, rcol, rvc, mean_height );
130 tmp.extend_left( rectangle_vector.front().left() );
131 tmp.extend_right( rectangle_vector.back().right() );
132 return tmp;
133 }
134
135 } // end namespace
136
137
Vrhomboid(const int l,const int lc,const int r,const int rc,const int h)138 Vrhomboid::Vrhomboid( const int l, const int lc, const int r, const int rc,
139 const int h )
140 {
141 if( r < l || h <= 0 )
142 {
143 if( verbosity >= 0 )
144 std::fprintf( stderr, "l = %d, lc = %d, r = %d, rc = %d, h = %d\n",
145 l, lc, r, rc, h );
146 error( "bad parameter building a Vrhomboid." );
147 }
148 left_ = l; lvcenter_ = lc; right_ = r; rvcenter_ = rc; height_ = h;
149 }
150
151
left(const int l)152 void Vrhomboid::left( const int l )
153 {
154 if( l > right_ ) error( "left, bad parameter resizing a Vrhomboid." );
155 left_ = l;
156 }
157
158
right(const int r)159 void Vrhomboid::right( const int r )
160 {
161 if( r < left_ ) error( "right, bad parameter resizing a Vrhomboid." );
162 right_ = r;
163 }
164
165
height(const int h)166 void Vrhomboid::height( const int h )
167 {
168 if( h <= 0 ) error( "height, bad parameter resizing a Vrhomboid." );
169 height_ = h;
170 }
171
172
extend_left(const int l)173 void Vrhomboid::extend_left( const int l )
174 {
175 if( l > right_ )
176 error( "extend_left, bad parameter resizing a Vrhomboid." );
177 lvcenter_ = vcenter( l ); left_ = l;
178 }
179
180
extend_right(const int r)181 void Vrhomboid::extend_right( const int r )
182 {
183 if( r < left_ )
184 error( "extend_right, bad parameter resizing a Vrhomboid." );
185 rvcenter_ = vcenter( r ); right_ = r;
186 }
187
188
vcenter(const int col) const189 int Vrhomboid::vcenter( const int col ) const
190 {
191 const int dx = right_ - left_, dy = rvcenter_ - lvcenter_;
192 int vc = lvcenter_;
193 if( dx && dy ) vc += ( dy * ( col - left_ ) ) / dx;
194 return vc;
195 }
196
197
includes(const Rectangle & r) const198 bool Vrhomboid::includes( const Rectangle & r ) const
199 {
200 if( r.left() < left_ || r.right() > right_ ) return false;
201 const int tl = top( r.left() ), bl = bottom( r.left() );
202 const int tr = top( r.right() ), br = bottom( r.left() );
203 const int t = std::max( tl, tr ), b = std::min( bl, br );
204 return ( t <= r.top() && b >= r.bottom() );
205 }
206
207
includes(const int row,const int col) const208 bool Vrhomboid::includes( const int row, const int col ) const
209 {
210 if( col < left_ || col > right_ ) return false;
211 const int t = top( col ), b = bottom( col );
212 return ( t <= row && b >= row );
213 }
214
215
216 // rectangle_vector must be ordered by increasing hcenter().
217 //
set_track(const std::vector<Rectangle> & rectangle_vector)218 void Track::set_track( const std::vector< Rectangle > & rectangle_vector )
219 {
220 data.clear();
221 if( rectangle_vector.empty() ) return;
222 std::vector< Rectangle > tmp;
223 int max_gap = 0;
224 bool last = false;
225
226 {
227 int s1 = rectangle_vector[0].width(), s2 = 0;
228 for( unsigned i = 1; i < rectangle_vector.size(); ++i )
229 {
230 s1 += rectangle_vector[i].width();
231 s2 += ( rectangle_vector[i].left() - rectangle_vector[i-1].right() );
232 }
233 max_gap = ( 5 * std::max( s1, s2 ) ) / rectangle_vector.size();
234 }
235
236 for( unsigned i = 0; i < rectangle_vector.size(); ++i )
237 {
238 const Rectangle & r1 = rectangle_vector[i];
239 tmp.push_back( r1 );
240 if( i + 1 >= rectangle_vector.size() ) last = true;
241 else
242 {
243 const Rectangle & r2 = rectangle_vector[i+1];
244 if( r2.left() - r1.right() >= max_gap ) last = true;
245 }
246 if( last )
247 { last = false; data.push_back( set_partial_track( tmp ) ); tmp.clear(); }
248 }
249
250 for( unsigned i = 0; i + 1 < data.size(); ++i )
251 {
252 const Vrhomboid & v1 = data[i];
253 const Vrhomboid & v2 = data[i+1];
254 if( v1.right() + 1 < v2.left() )
255 {
256 Vrhomboid v( v1.right() + 1, v1.rvcenter(), v2.left() - 1, v2.lvcenter(),
257 ( v1.height() + v2.height() ) / 2 );
258 ++i; data.insert( data.begin() + i, v );
259 }
260 }
261 }
262
263
bottom(const int col) const264 int Track::bottom( const int col ) const
265 {
266 for( unsigned i = 0; i < data.size(); ++i )
267 {
268 const Vrhomboid & vr = data[i];
269 if( col <= vr.right() || i + 1 >= data.size() ) return vr.bottom( col );
270 }
271 return 0;
272 }
273
274
top(const int col) const275 int Track::top( const int col ) const
276 {
277 for( unsigned i = 0; i < data.size(); ++i )
278 {
279 const Vrhomboid & vr = data[i];
280 if( col <= vr.right() || i + 1 >= data.size() ) return vr.top( col );
281 }
282 return 0;
283 }
284
285
vcenter(const int col) const286 int Track::vcenter( const int col ) const
287 {
288 for( unsigned i = 0; i < data.size(); ++i )
289 {
290 const Vrhomboid & vr = data[i];
291 if( col <= vr.right() || i + 1 >= data.size() ) return vr.vcenter( col );
292 }
293 return 0;
294 }
295
296 /*
297 bool Track::includes( const Rectangle & r ) const
298 {
299 for( unsigned i = 0; i < data.size(); ++i )
300 if( data[i].includes( r ) ) return true;
301 if( data.empty() ) return false;
302 if( r.right() > data.back().right() )
303 {
304 Vrhomboid tmp = data.back();
305 tmp.extend_right( r.right() );
306 return tmp.includes( r );
307 }
308 if( r.left() < data.front().left() )
309 {
310 Vrhomboid tmp = data.front();
311 tmp.extend_left( r.left() );
312 return tmp.includes( r );
313 }
314 return false;
315 }
316
317
318 bool Track::includes( const int row, const int col ) const
319 {
320 for( unsigned i = 0; i < data.size(); ++i )
321 if( data[i].includes( row, col ) ) return true;
322 if( data.empty() ) return false;
323 if( col > data.back().right() )
324 {
325 Vrhomboid tmp = data.back();
326 tmp.extend_right( col );
327 return tmp.includes( row, col );
328 }
329 if( col < data.front().left() )
330 {
331 Vrhomboid tmp = data.front();
332 tmp.extend_left( col );
333 return tmp.includes( row, col );
334 }
335 return false;
336 }*/
337