Bug Summary

File:ccv_swt.c
Warning:line 29, column 15
The right operand of '>' is a garbage value

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name ccv_swt.c -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -mrelocation-model static -mthread-model posix -menable-no-infs -menable-no-nans -menable-unsafe-fp-math -fno-signed-zeros -mreassociate -freciprocal-math -fno-trapping-math -ffp-contract=fast -ffast-math -ffinite-math-only -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -target-feature +sse2 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -resource-dir /usr/local/lib/clang/8.0.0 -I . -I /usr/local/cuda/include -D HAVE_CBLAS -D HAVE_LIBPNG -D HAVE_LIBJPEG -D HAVE_FFTW3 -D HAVE_PTHREAD -D HAVE_UCONTEXT -D HAVE_LIBLINEAR -D HAVE_TESSERACT -D HAVE_AVCODEC -D HAVE_AVFORMAT -D HAVE_AVUTIL -D HAVE_SWSCALE -D USE_DISPATCH -D HAVE_SSE2 -D HAVE_GSL -D HAVE_CUDA -D HAVE_CUDNN -D HAVE_NCCL -I /usr/local/include -internal-isystem /usr/local/include -internal-isystem /usr/local/lib/clang/8.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O3 -fdebug-compilation-dir /home/liu/buildslave/linux-x64-runtests/build/lib -ferror-limit 19 -fmessage-length 0 -fblocks -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -o /home/liu/buildslave/public_html/analyze/2019-05-04-163002-105371-1 -x c ccv_swt.c -faddrsig
1#include "ccv.h"
2#include "ccv_internal.h"
3
4const ccv_swt_param_t ccv_swt_default_params = {
5 .interval = 1,
6 .same_word_thresh = { 0.1, 0.8 },
7 .min_neighbors = 1,
8 .scale_invariant = 0,
9 .size = 3,
10 .low_thresh = 124,
11 .high_thresh = 204,
12 .max_height = 300,
13 .min_height = 8,
14 .min_area = 38,
15 .letter_occlude_thresh = 3,
16 .aspect_ratio = 8,
17 .std_ratio = 0.83,
18 .thickness_ratio = 1.5,
19 .height_ratio = 1.7,
20 .intensity_thresh = 31,
21 .distance_ratio = 2.9,
22 .intersect_ratio = 1.3,
23 .letter_thresh = 3,
24 .elongate_ratio = 1.9,
25 .breakdown = 1,
26 .breakdown_ratio = 1.0,
27};
28
29static inline CCV_IMPLEMENT_MEDIAN(_ccv_swt_median, int)int _ccv_swt_median(int* buf, int low, int high) { int w; int
middle, ll, hh; int median = (low + high) / 2; for (;;) { if
(high <= low) return buf[median]; if (high == low + 1) { if
(buf[low] > buf[high]) ((w) = (buf[low]), (buf[low]) = (buf
[high]), (buf[high]) = (w)); return buf[median]; } middle = (
low + high) / 2; if (buf[middle] > buf[high]) ((w) = (buf[
middle]), (buf[middle]) = (buf[high]), (buf[high]) = (w)); if
(buf[low] > buf[high]) ((w) = (buf[low]), (buf[low]) = (buf
[high]), (buf[high]) = (w)); if (buf[middle] > buf[low]) (
(w) = (buf[middle]), (buf[middle]) = (buf[low]), (buf[low]) =
(w)); ((w) = (buf[middle]), (buf[middle]) = (buf[low + 1]), (
buf[low + 1]) = (w)); ll = low + 1; hh = high; for (;;) { do ll
++; while (buf[low] > buf[ll]); do hh--; while (buf[hh] >
buf[low]); if (hh < ll) break; ((w) = (buf[ll]), (buf[ll]
) = (buf[hh]), (buf[hh]) = (w)); } ((w) = (buf[low]), (buf[low
]) = (buf[hh]), (buf[hh]) = (w)); if (hh <= median) low = ll
; else if (hh >= median) high = hh - 1; } }
32
Loop condition is true. Entering loop body
33
Taking false branch
34
Taking false branch
35
Assuming the condition is false
36
Taking false branch
37
Assuming the condition is true
38
Taking true branch
39
Taking false branch
40
Loop condition is true. Entering loop body
41
Assuming the condition is true
42
Loop condition is true. Execution continues on line 29
43
The right operand of '>' is a garbage value
30
31typedef struct {
32 int x0, x1, y0, y1;
33 int w;
34} ccv_swt_stroke_t;
35
36#define less_than(s1, s2, aux) ((s1).w < (s2).w)
37static CCV_IMPLEMENT_QSORT(_ccv_swt_stroke_qsort, ccv_swt_stroke_t, less_than)void _ccv_swt_stroke_qsort(ccv_swt_stroke_t *array, size_t total
, int aux) { int isort_thresh = 7; ccv_swt_stroke_t t; int sp
= 0; struct { ccv_swt_stroke_t *lb; ccv_swt_stroke_t *ub; } stack
[48]; if( total <= 1 ) return; stack[0].lb = array; stack[
0].ub = array + (total - 1); while( sp >= 0 ) { ccv_swt_stroke_t
* left = stack[sp].lb; ccv_swt_stroke_t* right = stack[sp--].
ub; for(;;) { int i, n = (int)(right - left) + 1, m; ccv_swt_stroke_t
* ptr; ccv_swt_stroke_t* ptr2; if( n <= isort_thresh ) { insert_sort
: for( ptr = left + 1; ptr <= right; ptr++ ) { for( ptr2 =
ptr; ptr2 > left && less_than(ptr2[0],ptr2[-1], aux
); ptr2--) (((t)) = ((ptr2[0])), ((ptr2[0])) = ((ptr2[-1])), (
(ptr2[-1])) = ((t))); } break; } else { ccv_swt_stroke_t* left0
; ccv_swt_stroke_t* left1; ccv_swt_stroke_t* right0; ccv_swt_stroke_t
* right1; ccv_swt_stroke_t* pivot; ccv_swt_stroke_t* a; ccv_swt_stroke_t
* b; ccv_swt_stroke_t* c; int swap_cnt = 0; left0 = left; right0
= right; pivot = left + (n/2); if( n > 40 ) { int d = n /
8; a = left, b = left + d, c = left + 2*d; left = less_than(
*a, *b, aux) ? (less_than(*b, *c, aux) ? b : (less_than(*a, *
c, aux) ? c : a)) : (less_than(*c, *b, aux) ? b : (less_than(
*a, *c, aux) ? a : c)); a = pivot - d, b = pivot, c = pivot +
d; pivot = less_than(*a, *b, aux) ? (less_than(*b, *c, aux) ?
b : (less_than(*a, *c, aux) ? c : a)) : (less_than(*c, *b, aux
) ? b : (less_than(*a, *c, aux) ? a : c)); a = right - 2*d, b
= right - d, c = right; right = less_than(*a, *b, aux) ? (less_than
(*b, *c, aux) ? b : (less_than(*a, *c, aux) ? c : a)) : (less_than
(*c, *b, aux) ? b : (less_than(*a, *c, aux) ? a : c)); } a = left
, b = pivot, c = right; pivot = less_than(*a, *b, aux) ? (less_than
(*b, *c, aux) ? b : (less_than(*a, *c, aux) ? c : a)) : (less_than
(*c, *b, aux) ? b : (less_than(*a, *c, aux) ? a : c)); if( pivot
!= left0 ) { (((t)) = ((*pivot)), ((*pivot)) = ((*left0)), (
(*left0)) = ((t))); pivot = left0; } left = left1 = left0 + 1
; right = right1 = right0; for(;;) { while( left <= right &&
!less_than(*pivot, *left, aux) ) { if( !less_than(*left, *pivot
, aux) ) { if( left > left1 ) (((t)) = ((*left1)), ((*left1
)) = ((*left)), ((*left)) = ((t))); swap_cnt = 1; left1++; } left
++; } while( left <= right && !less_than(*right, *
pivot, aux) ) { if( !less_than(*pivot, *right, aux) ) { if( right
< right1 ) (((t)) = ((*right1)), ((*right1)) = ((*right))
, ((*right)) = ((t))); swap_cnt = 1; right1--; } right--; } if
( left > right ) break; (((t)) = ((*left)), ((*left)) = ((
*right)), ((*right)) = ((t))); swap_cnt = 1; left++; right--;
} if( swap_cnt == 0 ) { left = left0, right = right0; goto insert_sort
; } n = ({ typeof ((int)(left1 - left0)) _a = ((int)(left1 - left0
)); typeof ((int)(left - left1)) _b = ((int)(left - left1)); (
_a < _b) ? _a : _b; }); for( i = 0; i < n; i++ ) (((t))
= ((left0[i])), ((left0[i])) = ((left[i-n])), ((left[i-n])) =
((t))); n = ({ typeof ((int)(right0 - right1)) _a = ((int)(right0
- right1)); typeof ((int)(right1 - right)) _b = ((int)(right1
- right)); (_a < _b) ? _a : _b; }); for( i = 0; i < n;
i++ ) (((t)) = ((left[i])), ((left[i])) = ((right0[i-n+1])),
((right0[i-n+1])) = ((t))); n = (int)(left - left1); m = (int
)(right1 - right); if( n > 1 ) { if( m > 1 ) { if( n >
m ) { stack[++sp].lb = left0; stack[sp].ub = left0 + n - 1; left
= right0 - m + 1, right = right0; } else { stack[++sp].lb = right0
- m + 1; stack[sp].ub = right0; left = left0, right = left0 +
n - 1; } } else left = left0, right = left0 + n - 1; } else if
( m > 1 ) left = right0 - m + 1, right = right0; else break
; } } } }
38#undef less_than
39
40/* ccv_swt is only the method to generate stroke width map */
41static void _ccv_swt(ccv_dense_matrix_t* a, ccv_dense_matrix_t** b, int type, ccv_swt_param_t params, ccv_dense_matrix_t* const _c, ccv_dense_matrix_t* const _dx, ccv_dense_matrix_t* const _dy)
42{
43 assert(a->type & CCV_C1)((void) sizeof ((a->type & CCV_C1) ? 1 : 0), __extension__
({ if (a->type & CCV_C1) ; else __assert_fail ("a->type & CCV_C1"
, "ccv_swt.c", 43, __extension__ __PRETTY_FUNCTION__); }))
;
44 ccv_declare_derived_signature(sig, a->sig != 0, ccv_sign_with_format(64, "ccv_swt(%d,%d,%d,%d)", params.direction, params.size, params.low_thresh, params.high_thresh), a->sig, CCV_EOF_SIGN)char _ccv_identifier_44[(64)]; memset(_ccv_identifier_44, 0, (
64)); snprintf(_ccv_identifier_44, (64), ("ccv_swt(%d,%d,%d,%d)"
), params.direction, params.size, params.low_thresh, params.high_thresh
); size_t _ccv_string_size_44 = (64);; uint64_t sig = (a->
sig != 0) ? ccv_cache_generate_signature(_ccv_identifier_44, _ccv_string_size_44
, a->sig, ((uint64_t)0)) : 0;
;
45 type = (type == 0) ? CCV_32S | CCV_C1 : CCV_GET_DATA_TYPE(type)((type) & 0xFF000) | CCV_C1;
46 ccv_dense_matrix_t* db = *b = ccv_dense_matrix_renew(*b, a->rows, a->cols, CCV_C1 | CCV_ALL_DATA_TYPE(CCV_8U | CCV_32S | CCV_32F | CCV_64S | CCV_64F), type, sig);
47 ccv_object_return_if_cached(, db){ if ((!(db) || (((int*)(db))[0] & CCV_GARBAGE)) &&
(!(0) || (((int*)(0))[0] & CCV_GARBAGE)) && (!(0
) || (((int*)(0))[0] & CCV_GARBAGE)) && (!(0) || (
((int*)(0))[0] & CCV_GARBAGE)) && (!(0) || (((int
*)(0))[0] & CCV_GARBAGE)) && (!(0) || (((int*)(0)
)[0] & CCV_GARBAGE)) && (!(0) || (((int*)(0))[0] &
CCV_GARBAGE)) && (!(0) || (((int*)(0))[0] & CCV_GARBAGE
)) && (!(0) || (((int*)(0))[0] & CCV_GARBAGE)) &&
(!(0) || (((int*)(0))[0] & CCV_GARBAGE)) && (!(0
) || (((int*)(0))[0] & CCV_GARBAGE)) && (!(0) || (
((int*)(0))[0] & CCV_GARBAGE)) && (!(0) || (((int
*)(0))[0] & CCV_GARBAGE)) && (!(0) || (((int*)(0)
)[0] & CCV_GARBAGE)) && (!(0) || (((int*)(0))[0] &
CCV_GARBAGE)) && (!(0) || (((int*)(0))[0] & CCV_GARBAGE
)) && (!(0) || (((int*)(0))[0] & CCV_GARBAGE)) &&
(!(0) || (((int*)(0))[0] & CCV_GARBAGE)) && (!(0
) || (((int*)(0))[0] & CCV_GARBAGE)) && (!(0) || (
((int*)(0))[0] & CCV_GARBAGE)) && (!(0) || (((int
*)(0))[0] & CCV_GARBAGE)) && (!(0) || (((int*)(0)
)[0] & CCV_GARBAGE)) && (!(0) || (((int*)(0))[0] &
CCV_GARBAGE)) && (!(0) || (((int*)(0))[0] & CCV_GARBAGE
)) && (!(0) || (((int*)(0))[0] & CCV_GARBAGE)) &&
(!(0) || (((int*)(0))[0] & CCV_GARBAGE)) && (!(0
) || (((int*)(0))[0] & CCV_GARBAGE)) && (!(0) || (
((int*)(0))[0] & CCV_GARBAGE)) && (!(0) || (((int
*)(0))[0] & CCV_GARBAGE)) && (!(0) || (((int*)(0)
)[0] & CCV_GARBAGE)) && (!(0) || (((int*)(0))[0] &
CCV_GARBAGE)) && (!(0) || (((int*)(0))[0] & CCV_GARBAGE
)) && (!(0) || (((int*)(0))[0] & CCV_GARBAGE)) &&
(!(0) || (((int*)(0))[0] & CCV_GARBAGE)) && (!(0
) || (((int*)(0))[0] & CCV_GARBAGE)) && (!(0) || (
((int*)(0))[0] & CCV_GARBAGE)) && (!(0) || (((int
*)(0))[0] & CCV_GARBAGE)) && (!(0) || (((int*)(0)
)[0] & CCV_GARBAGE)) && (!(0) || (((int*)(0))[0] &
CCV_GARBAGE)) && (!(0) || (((int*)(0))[0] & CCV_GARBAGE
)) && (!(0) || (((int*)(0))[0] & CCV_GARBAGE)) &&
(!(0) || (((int*)(0))[0] & CCV_GARBAGE)) && (!(0
) || (((int*)(0))[0] & CCV_GARBAGE)) && (!(0) || (
((int*)(0))[0] & CCV_GARBAGE)) && (!(0) || (((int
*)(0))[0] & CCV_GARBAGE)) && (!(0) || (((int*)(0)
)[0] & CCV_GARBAGE)) && (!(0) || (((int*)(0))[0] &
CCV_GARBAGE)) && (!(0) || (((int*)(0))[0] & CCV_GARBAGE
)) && (!(0) || (((int*)(0))[0] & CCV_GARBAGE)) &&
(!(0) || (((int*)(0))[0] & CCV_GARBAGE)) && (!(0
) || (((int*)(0))[0] & CCV_GARBAGE)) && (!(0) || (
((int*)(0))[0] & CCV_GARBAGE)) && (!(0) || (((int
*)(0))[0] & CCV_GARBAGE)) && (!(0) || (((int*)(0)
)[0] & CCV_GARBAGE)) && (!(0) || (((int*)(0))[0] &
CCV_GARBAGE)) && (!(0) || (((int*)(0))[0] & CCV_GARBAGE
)) && (!(0) || (((int*)(0))[0] & CCV_GARBAGE)) &&
(!(0) || (((int*)(0))[0] & CCV_GARBAGE)) && (!(0
) || (((int*)(0))[0] & CCV_GARBAGE)) && (!(0) || (
((int*)(0))[0] & CCV_GARBAGE)) && (!(0) || (((int
*)(0))[0] & CCV_GARBAGE)) && (!(0) || (((int*)(0)
)[0] & CCV_GARBAGE)) && (!(0) || (((int*)(0))[0] &
CCV_GARBAGE))) { (void)((db) && (((int*)(db))[0] &=
~CCV_GARBAGE));(void)((0) && (((int*)(0))[0] &= ~
CCV_GARBAGE));(void)((0) && (((int*)(0))[0] &= ~CCV_GARBAGE
));(void)((0) && (((int*)(0))[0] &= ~CCV_GARBAGE)
);(void)((0) && (((int*)(0))[0] &= ~CCV_GARBAGE))
;(void)((0) && (((int*)(0))[0] &= ~CCV_GARBAGE));
(void)((0) && (((int*)(0))[0] &= ~CCV_GARBAGE));(
void)((0) && (((int*)(0))[0] &= ~CCV_GARBAGE));(void
)((0) && (((int*)(0))[0] &= ~CCV_GARBAGE));(void)
((0) && (((int*)(0))[0] &= ~CCV_GARBAGE));(void)(
(0) && (((int*)(0))[0] &= ~CCV_GARBAGE));(void)((
0) && (((int*)(0))[0] &= ~CCV_GARBAGE));(void)((0
) && (((int*)(0))[0] &= ~CCV_GARBAGE));(void)((0)
&& (((int*)(0))[0] &= ~CCV_GARBAGE));(void)((0) &&
(((int*)(0))[0] &= ~CCV_GARBAGE));(void)((0) && (
((int*)(0))[0] &= ~CCV_GARBAGE));(void)((0) && ((
(int*)(0))[0] &= ~CCV_GARBAGE));(void)((0) && (((
int*)(0))[0] &= ~CCV_GARBAGE));(void)((0) && (((int
*)(0))[0] &= ~CCV_GARBAGE));(void)((0) && (((int*
)(0))[0] &= ~CCV_GARBAGE));(void)((0) && (((int*)
(0))[0] &= ~CCV_GARBAGE));(void)((0) && (((int*)(
0))[0] &= ~CCV_GARBAGE));(void)((0) && (((int*)(0
))[0] &= ~CCV_GARBAGE));(void)((0) && (((int*)(0)
)[0] &= ~CCV_GARBAGE));(void)((0) && (((int*)(0))
[0] &= ~CCV_GARBAGE));(void)((0) && (((int*)(0))[
0] &= ~CCV_GARBAGE));(void)((0) && (((int*)(0))[0
] &= ~CCV_GARBAGE));(void)((0) && (((int*)(0))[0]
&= ~CCV_GARBAGE));(void)((0) && (((int*)(0))[0] &=
~CCV_GARBAGE));(void)((0) && (((int*)(0))[0] &= ~
CCV_GARBAGE));(void)((0) && (((int*)(0))[0] &= ~CCV_GARBAGE
));(void)((0) && (((int*)(0))[0] &= ~CCV_GARBAGE)
);(void)((0) && (((int*)(0))[0] &= ~CCV_GARBAGE))
;(void)((0) && (((int*)(0))[0] &= ~CCV_GARBAGE));
(void)((0) && (((int*)(0))[0] &= ~CCV_GARBAGE));(
void)((0) && (((int*)(0))[0] &= ~CCV_GARBAGE));(void
)((0) && (((int*)(0))[0] &= ~CCV_GARBAGE));(void)
((0) && (((int*)(0))[0] &= ~CCV_GARBAGE));(void)(
(0) && (((int*)(0))[0] &= ~CCV_GARBAGE));(void)((
0) && (((int*)(0))[0] &= ~CCV_GARBAGE));(void)((0
) && (((int*)(0))[0] &= ~CCV_GARBAGE));(void)((0)
&& (((int*)(0))[0] &= ~CCV_GARBAGE));(void)((0) &&
(((int*)(0))[0] &= ~CCV_GARBAGE));(void)((0) && (
((int*)(0))[0] &= ~CCV_GARBAGE));(void)((0) && ((
(int*)(0))[0] &= ~CCV_GARBAGE));(void)((0) && (((
int*)(0))[0] &= ~CCV_GARBAGE));(void)((0) && (((int
*)(0))[0] &= ~CCV_GARBAGE));(void)((0) && (((int*
)(0))[0] &= ~CCV_GARBAGE));(void)((0) && (((int*)
(0))[0] &= ~CCV_GARBAGE));(void)((0) && (((int*)(
0))[0] &= ~CCV_GARBAGE));(void)((0) && (((int*)(0
))[0] &= ~CCV_GARBAGE));(void)((0) && (((int*)(0)
)[0] &= ~CCV_GARBAGE));(void)((0) && (((int*)(0))
[0] &= ~CCV_GARBAGE));(void)((0) && (((int*)(0))[
0] &= ~CCV_GARBAGE));(void)((0) && (((int*)(0))[0
] &= ~CCV_GARBAGE));(void)((0) && (((int*)(0))[0]
&= ~CCV_GARBAGE));(void)((0) && (((int*)(0))[0] &=
~CCV_GARBAGE));(void)((0) && (((int*)(0))[0] &= ~
CCV_GARBAGE));(void)((0) && (((int*)(0))[0] &= ~CCV_GARBAGE
));(void)((0) && (((int*)(0))[0] &= ~CCV_GARBAGE)
);(void)((0) && (((int*)(0))[0] &= ~CCV_GARBAGE))
;(void)((0) && (((int*)(0))[0] &= ~CCV_GARBAGE));
(void)((0) && (((int*)(0))[0] &= ~CCV_GARBAGE));;
; return ; } }
;
48 ccv_dense_matrix_t* c = _c;
49 if (!c)
50 {
51 ccv_dense_matrix_t* cc = 0;
52 ccv_canny(a, &cc, 0, params.size, params.low_thresh, params.high_thresh);
53 ccv_close_outline(cc, &c, 0);
54 ccv_matrix_free(cc);
55 }
56 ccv_dense_matrix_t* dx = _dx;
57 if (!dx)
58 ccv_sobel(a, &dx, 0, params.size, 0);
59 ccv_dense_matrix_t* dy = _dy;
60 if (!dy)
61 ccv_sobel(a, &dy, 0, 0, params.size);
62 int i, j, k, w;
63 int* buf = (int*)alloca(sizeof(int) * ccv_max(a->cols, a->rows))__builtin_alloca (sizeof(int) * ({ typeof (a->cols) _a = (
a->cols); typeof (a->rows) _b = (a->rows); (_a > _b
) ? _a : _b; }))
;
64 ccv_array_t* strokes = ccv_array_new(sizeof(ccv_swt_stroke_t), 64, 0);
65 unsigned char* b_ptr = db->data.u8;
66 unsigned char* c_ptr = c->data.u8;
67 unsigned char* dx_ptr = dx->data.u8;
68 unsigned char* dy_ptr = dy->data.u8;
69 ccv_zero(db);
70 int dx5[] = {-1, 0, 1, 0, 0};
71 int dy5[] = {0, 0, 0, -1, 1};
72 int dx9[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
73 int dy9[] = {0, 0, 0, -1, -1, -1, 1, 1, 1};
74 int adx, ady, sx, sy, err, e2, x0, x1, y0, y1, kx, ky;
75#define ray_reset() \
76 err = adx - ady; e2 = 0; \
77 x0 = j; y0 = i;
78#define ray_reset_by_stroke(stroke)adx = abs(stroke->x1 - stroke->x0); ady = abs(stroke->
y1 - stroke->y0); sx = stroke->x1 > stroke->x0 ? 1
: -1; sy = stroke->y1 > stroke->y0 ? 1 : -1; err = adx
- ady; e2 = 0; x0 = stroke->x0; y0 = stroke->y0;
\
79 adx = abs(stroke->x1 - stroke->x0); \
80 ady = abs(stroke->y1 - stroke->y0); \
81 sx = stroke->x1 > stroke->x0 ? 1 : -1; \
82 sy = stroke->y1 > stroke->y0 ? 1 : -1; \
83 err = adx - ady; e2 = 0; \
84 x0 = stroke->x0; y0 = stroke->y0;
85#define ray_increment() \
86 e2 = 2 * err; \
87 if (e2 > -ady) \
88 { \
89 err -= ady; \
90 x0 += sx; \
91 } \
92 if (e2 < adx) \
93 { \
94 err += adx; \
95 y0 += sy; \
96 }
97 int rdx, rdy, flag;
98#define ray_emit(xx, xy, yx, yy, _for_get_d, _for_set_b, _for_get_b) \
99 rdx = _for_get_d(dx_ptr, j, 0) * (xx) + _for_get_d(dy_ptr, j, 0) * (xy); \
100 rdy = _for_get_d(dx_ptr, j, 0) * (yx) + _for_get_d(dy_ptr, j, 0) * (yy); \
101 adx = abs(rdx); \
102 ady = abs(rdy); \
103 sx = rdx > 0 ? -params.direction : params.direction; \
104 sy = rdy > 0 ? -params.direction : params.direction; \
105 /* Bresenham's line algorithm */ \
106 ray_reset(); \
107 flag = 0; \
108 kx = x0; \
109 ky = y0; \
110 for (w = 0; w < 70; w++) \
111 { \
112 ray_increment(); \
113 if (x0 >= a->cols - 1 || x0 < 1 || y0 >= a->rows - 1 || y0 < 1) \
114 break; \
115 if (abs(i - y0) >= 2 || abs(j - x0) >= 2) \
116 { /* ideally, I can encounter another edge directly, but in practice, we should search in a small region around it */ \
117 flag = 0; \
118 for (k = 0; k < 5; k++) \
119 { \
120 kx = x0 + dx5[k]; \
121 ky = y0 + dy5[k]; \
122 if (c_ptr[kx + (ky - i) * c->step]) \
123 { \
124 flag = 1; \
125 break; \
126 } \
127 } \
128 if (flag) \
129 break; \
130 } \
131 } \
132 if (flag && kx < a->cols - 1 && kx > 0 && ky < a->rows - 1 && ky > 0) \
133 { \
134 /* the opposite angle should be in d_p -/+ PI / 6 (otherwise discard),
135 * a faster computation should be:
136 * Tan(d_q - d_p) = (Tan(d_q) - Tan(d_p)) / (1 + Tan(d_q) * Tan(d_p))
137 * and -1 / sqrt(3) < Tan(d_q - d_p) < 1 / sqrt(3)
138 * also, we needs to check the whole 3x3 neighborhood in a hope that we don't miss one or two of them */ \
139 flag = 0; \
140 for (k = 0; k < 9; k++) \
141 { \
142 int tn = _for_get_d(dy_ptr, j, 0) * _for_get_d(dx_ptr + (ky - i + dy9[k]) * dx->step, kx + dx9[k], 0) - \
143 _for_get_d(dx_ptr, j, 0) * _for_get_d(dy_ptr + (ky - i + dy9[k]) * dy->step, kx + dx9[k], 0); \
144 int td = _for_get_d(dx_ptr, j, 0) * _for_get_d(dx_ptr + (ky - i + dy9[k]) * dx->step, kx + dx9[k], 0) + \
145 _for_get_d(dy_ptr, j, 0) * _for_get_d(dy_ptr + (ky - i + dy9[k]) * dy->step, kx + dx9[k], 0); \
146 if (tn * 7 < -td * 4 && tn * 7 > td * 4) \
147 { \
148 flag = 1; \
149 break; \
150 } \
151 } \
152 if (flag) \
153 { \
154 x1 = x0; y1 = y0; \
155 ray_reset(); \
156 w = (int)(sqrt((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0)) + 0.5); \
157 /* extend the line to be width of 1 */ \
158 for (;;) \
159 { \
160 if (_for_get_b(b_ptr + (y0 - i) * db->step, x0, 0) == 0 || _for_get_b(b_ptr + (y0 - i) * db->step, x0, 0) > w) \
161 _for_set_b(b_ptr + (y0 - i) * db->step, x0, w, 0); \
162 if (x0 == x1 && y0 == y1) \
163 break; \
164 ray_increment(); \
165 } \
166 ccv_swt_stroke_t stroke = { \
167 .x0 = j, \
168 .x1 = x1, \
169 .y0 = i, \
170 .y1 = y1, \
171 .w = w \
172 }; \
173 ccv_array_push(strokes, &stroke); \
174 } \
175 }
176#define for_block(_for_get_d, _for_set_b, _for_get_b) \
177 for (i = 0; i < a->rows; i++) \
178 { \
179 for (j = 0; j < a->cols; j++) \
180 if (c_ptr[j]) \
181 { \
182 ray_emit(1, 0, 0, 1, _for_get_d, _for_set_b, _for_get_b); \
183 ray_emit(1, -1, 1, 1, _for_get_d, _for_set_b, _for_get_b); \
184 ray_emit(1, 1, -1, 1, _for_get_d, _for_set_b, _for_get_b); \
185 } \
186 b_ptr += db->step; \
187 c_ptr += c->step; \
188 dx_ptr += dx->step; \
189 dy_ptr += dy->step; \
190 } \
191 b_ptr = db->data.u8; \
192 /* compute median width of stroke, from shortest strokes to longest */ \
193 _ccv_swt_stroke_qsort((ccv_swt_stroke_t*)ccv_array_get(strokes, 0)((void*)(((char*)((strokes)->data)) + (size_t)(strokes)->
rsize * (size_t)(0)))
, strokes->rnum, 0); \
194 for (i = 0; i < strokes->rnum; i++) \
195 { \
196 ccv_swt_stroke_t* stroke = (ccv_swt_stroke_t*)ccv_array_get(strokes, i)((void*)(((char*)((strokes)->data)) + (size_t)(strokes)->
rsize * (size_t)(i)))
; \
197 ray_reset_by_stroke(stroke)adx = abs(stroke->x1 - stroke->x0); ady = abs(stroke->
y1 - stroke->y0); sx = stroke->x1 > stroke->x0 ? 1
: -1; sy = stroke->y1 > stroke->y0 ? 1 : -1; err = adx
- ady; e2 = 0; x0 = stroke->x0; y0 = stroke->y0;
; \
198 int n = 0; \
199 for (;;) \
200 { \
201 buf[n++] = _for_get_b(b_ptr + y0 * db->step, x0, 0); \
202 if (x0 == stroke->x1 && y0 == stroke->y1) \
203 break; \
204 ray_increment(); \
205 } \
206 int nw = _ccv_swt_median(buf, 0, n - 1); \
207 if (nw != stroke->w) \
208 { \
209 ray_reset_by_stroke(stroke)adx = abs(stroke->x1 - stroke->x0); ady = abs(stroke->
y1 - stroke->y0); sx = stroke->x1 > stroke->x0 ? 1
: -1; sy = stroke->y1 > stroke->y0 ? 1 : -1; err = adx
- ady; e2 = 0; x0 = stroke->x0; y0 = stroke->y0;
; \
210 for (;;) \
211 { \
212 _for_set_b(b_ptr + y0 * db->step, x0, nw, 0); \
213 if (x0 == stroke->x1 && y0 == stroke->y1) \
214 break; \
215 ray_increment(); \
216 } \
217 } \
218 }
219 ccv_matrix_getter(dx->type, ccv_matrix_setter_getter, db->type, for_block){ switch (((dx->type) & 0xFF000)) { case CCV_32S: { { switch
(((db->type) & 0xFF000)) { case CCV_32S: { for_block(
_ccv_get_32s_value, _ccv_set_32s_value, _ccv_get_32s_value); break
; } case CCV_32F: { for_block(_ccv_get_32s_value, _ccv_set_32f_value
, _ccv_get_32f_value); break; } case CCV_64S: { for_block(_ccv_get_32s_value
, _ccv_set_64s_value, _ccv_get_64s_value); break; } case CCV_64F
: { for_block(_ccv_get_32s_value, _ccv_set_64f_value, _ccv_get_64f_value
); break; } default: { for_block(_ccv_get_32s_value, _ccv_set_8u_value
, _ccv_get_8u_value); } } }; break; } case CCV_32F: { { switch
(((db->type) & 0xFF000)) { case CCV_32S: { for_block(
_ccv_get_32f_value, _ccv_set_32s_value, _ccv_get_32s_value); break
; } case CCV_32F: { for_block(_ccv_get_32f_value, _ccv_set_32f_value
, _ccv_get_32f_value); break; } case CCV_64S: { for_block(_ccv_get_32f_value
, _ccv_set_64s_value, _ccv_get_64s_value); break; } case CCV_64F
: { for_block(_ccv_get_32f_value, _ccv_set_64f_value, _ccv_get_64f_value
); break; } default: { for_block(_ccv_get_32f_value, _ccv_set_8u_value
, _ccv_get_8u_value); } } }; break; } case CCV_64S: { { switch
(((db->type) & 0xFF000)) { case CCV_32S: { for_block(
_ccv_get_64s_value, _ccv_set_32s_value, _ccv_get_32s_value); break
; } case CCV_32F: { for_block(_ccv_get_64s_value, _ccv_set_32f_value
, _ccv_get_32f_value); break; } case CCV_64S: { for_block(_ccv_get_64s_value
, _ccv_set_64s_value, _ccv_get_64s_value); break; } case CCV_64F
: { for_block(_ccv_get_64s_value, _ccv_set_64f_value, _ccv_get_64f_value
); break; } default: { for_block(_ccv_get_64s_value, _ccv_set_8u_value
, _ccv_get_8u_value); } } }; break; } case CCV_64F: { { switch
(((db->type) & 0xFF000)) { case CCV_32S: { for_block(
_ccv_get_64f_value, _ccv_set_32s_value, _ccv_get_32s_value); break
; } case CCV_32F: { for_block(_ccv_get_64f_value, _ccv_set_32f_value
, _ccv_get_32f_value); break; } case CCV_64S: { for_block(_ccv_get_64f_value
, _ccv_set_64s_value, _ccv_get_64s_value); break; } case CCV_64F
: { for_block(_ccv_get_64f_value, _ccv_set_64f_value, _ccv_get_64f_value
); break; } default: { for_block(_ccv_get_64f_value, _ccv_set_8u_value
, _ccv_get_8u_value); } } }; break; } default: { { switch (((
db->type) & 0xFF000)) { case CCV_32S: { for_block(_ccv_get_8u_value
, _ccv_set_32s_value, _ccv_get_32s_value); break; } case CCV_32F
: { for_block(_ccv_get_8u_value, _ccv_set_32f_value, _ccv_get_32f_value
); break; } case CCV_64S: { for_block(_ccv_get_8u_value, _ccv_set_64s_value
, _ccv_get_64s_value); break; } case CCV_64F: { for_block(_ccv_get_8u_value
, _ccv_set_64f_value, _ccv_get_64f_value); break; } default: {
for_block(_ccv_get_8u_value, _ccv_set_8u_value, _ccv_get_8u_value
); } } }; } } }
;
220#undef for_block
221#undef ray_emit
222#undef ray_reset
223#undef ray_increment
224 ccv_array_free(strokes);
225 if (c != _c)
226 ccv_matrix_free(c);
227 if (dx != _dx)
228 ccv_matrix_free(dx);
229 if (dy != _dy)
230 ccv_matrix_free(dy);
231}
232
233void ccv_swt(ccv_dense_matrix_t* a, ccv_dense_matrix_t** b, int type, ccv_swt_param_t params)
234{
235 _ccv_swt(a, b, type, params, 0, 0, 0);
236}
237
238static ccv_array_t* _ccv_swt_connected_component(ccv_dense_matrix_t* a, int ratio, int min_height, int max_height, int min_area)
239{
240 int i, j, k;
241 int* a_ptr = a->data.i32;
242 int dx8[] = {-1, 1, -1, 0, 1, -1, 0, 1};
243 int dy8[] = {0, 0, -1, -1, -1, 1, 1, 1};
244 int* marker = (int*)ccmallocmalloc(sizeof(int) * a->rows * a->cols);
245 memset(marker, 0, sizeof(int) * a->rows * a->cols);
246 int* m_ptr = marker;
247 ccv_point_t* buffer = (ccv_point_t*)ccmallocmalloc(sizeof(ccv_point_t) * a->rows * a->cols);
248 ccv_array_t* contours = ccv_array_new(sizeof(ccv_contour_t*), 5, 0);
249 for (i = 0; i < a->rows; i++)
250 {
251 for (j = 0; j < a->cols; j++)
252 if (a_ptr[j] != 0 && !m_ptr[j])
253 {
254 m_ptr[j] = 1;
255 ccv_contour_t* contour = ccv_contour_new(1);
256 ccv_point_t* closed = buffer;
257 closed->x = j;
258 closed->y = i;
259 ccv_point_t* open = buffer + 1;
260 for (; closed < open; closed++)
261 {
262 ccv_contour_push(contour, *closed);
263 double w = a_ptr[closed->x + (closed->y - i) * a->cols];
264 for (k = 0; k < 8; k++)
265 {
266 int nx = closed->x + dx8[k];
267 int ny = closed->y + dy8[k];
268 if (nx >= 0 && nx < a->cols && ny >= 0 && ny < a->rows &&
269 a_ptr[nx + (ny - i) * a->cols] != 0 &&
270 !m_ptr[nx + (ny - i) * a->cols] &&
271 (a_ptr[nx + (ny - i) * a->cols] <= ratio * w && a_ptr[nx + (ny - i) * a->cols] * ratio >= w))
272 {
273 m_ptr[nx + (ny - i) * a->cols] = 1;
274 // compute new average w
275 w = (w * (int)(open - closed + 1) + a_ptr[nx + (ny - i) * a->cols]) / (double)(open - closed + 2);
276 open->x = nx;
277 open->y = ny;
278 open++;
279 }
280 }
281 }
282 if (contour->rect.height < min_height || contour->rect.height > max_height || contour->size < min_area)
283 ccv_contour_free(contour);
284 else
285 ccv_array_push(contours, &contour);
286 }
287 a_ptr += a->cols;
288 m_ptr += a->cols;
289 }
290 ccfreefree(marker);
291 ccfreefree(buffer);
292 return contours;
293}
294
295typedef struct {
296 ccv_rect_t rect;
297 ccv_point_t center;
298 int thickness;
299 int intensity;
300 double std;
301 double mean;
302 ccv_contour_t* contour;
303} ccv_letter_t;
304
305static ccv_array_t* _ccv_swt_connected_letters(ccv_dense_matrix_t* a, ccv_dense_matrix_t* swt, ccv_swt_param_t params)
306{
307 ccv_array_t* contours = _ccv_swt_connected_component(swt, 3, params.min_height, params.max_height, params.min_area);
308 ccv_array_t* letters = ccv_array_new(sizeof(ccv_letter_t), 5, 0);
309 int i, j, x, y;
310 // merge contours that inside other contours
311 int* buffer = (int*)ccmallocmalloc(sizeof(int) * swt->rows * swt->cols);
11
Storing uninitialized value
312 double aspect_ratio_inv = 1.0 / params.aspect_ratio;
313 for (i = 0; i < contours->rnum; i++)
12
Assuming the condition is true
13
Loop condition is true. Entering loop body
314 {
315 ccv_contour_t* contour = *(ccv_contour_t**)ccv_array_get(contours, i)((void*)(((char*)((contours)->data)) + (size_t)(contours)->
rsize * (size_t)(i)))
;
316 assert(contour->rect.height <= params.max_height && contour->rect.height >= params.min_height)((void) sizeof ((contour->rect.height <= params.max_height
&& contour->rect.height >= params.min_height) ?
1 : 0), __extension__ ({ if (contour->rect.height <= params
.max_height && contour->rect.height >= params.min_height
) ; else __assert_fail ("contour->rect.height <= params.max_height && contour->rect.height >= params.min_height"
, "ccv_swt.c", 316, __extension__ __PRETTY_FUNCTION__); }))
;
14
Assuming the condition is true
15
Assuming the condition is true
16
Taking true branch
317 double ratio = (double)contour->rect.width / (double)contour->rect.height;
318 if (ratio < aspect_ratio_inv || ratio > params.aspect_ratio)
17
Taking false branch
319 {
320 ccv_contour_free(contour);
321 continue;
322 }
323 double xc = (double)contour->m10 / contour->size;
324 double yc = (double)contour->m01 / contour->size;
325 double af = (double)contour->m20 / contour->size - xc * xc;
326 double bf = 2 * ((double)contour->m11 / contour->size - xc * yc);
327 double cf = (double)contour->m02 / contour->size - yc * yc;
328 double delta = sqrt(bf * bf + (af - cf) * (af - cf));
329 ratio = sqrt((af + cf + delta) / (af + cf - delta));
330 if (ratio < aspect_ratio_inv || ratio > params.aspect_ratio)
18
Taking false branch
331 {
332 ccv_contour_free(contour);
333 continue;
334 }
335 double mean = 0;
336 for (j = 0; j < contour->size; j++)
19
Assuming the condition is true
20
Loop condition is true. Entering loop body
21
Assuming the condition is true
22
Loop condition is true. Entering loop body
23
Assuming the condition is true
24
Loop condition is true. Entering loop body
25
Assuming the condition is false
26
Loop condition is false. Execution continues on line 341
337 {
338 ccv_point_t* point = (ccv_point_t*)ccv_array_get(contour->set, j)((void*)(((char*)((contour->set)->data)) + (size_t)(contour
->set)->rsize * (size_t)(j)))
;
339 mean += buffer[j] = swt->data.i32[point->x + point->y * swt->cols];
340 }
341 mean = mean / contour->size;
342 double variance = 0;
343 for (j = 0; j < contour->size; j++)
27
Loop condition is true. Entering loop body
28
Loop condition is true. Entering loop body
29
Loop condition is true. Entering loop body
30
Loop condition is false. Execution continues on line 345
344 variance += (mean - buffer[j]) * (mean - buffer[j]);
345 variance = variance / contour->size;
346 ccv_letter_t letter;
347 letter.std = sqrt(variance);
348 letter.mean = mean;
349 letter.thickness = _ccv_swt_median(buffer, 0, contour->size - 1);
31
Calling '_ccv_swt_median'
350 letter.rect = contour->rect;
351 letter.center.x = letter.rect.x + letter.rect.width / 2;
352 letter.center.y = letter.rect.y + letter.rect.height / 2;
353 letter.intensity = 0;
354 letter.contour = contour;
355 ccv_array_push(letters, &letter);
356 }
357 ccv_array_free(contours);
358 memset(buffer, 0, sizeof(int) * swt->rows * swt->cols);
359 ccv_array_t* new_letters = ccv_array_new(sizeof(ccv_letter_t), 5, 0);
360 for (i = 0; i < letters->rnum; i++)
361 {
362 ccv_letter_t* letter = (ccv_letter_t*)ccv_array_get(letters, i)((void*)(((char*)((letters)->data)) + (size_t)(letters)->
rsize * (size_t)(i)))
;
363 for (j = 0; j < letter->contour->size; j++)
364 {
365 ccv_point_t* point = (ccv_point_t*)ccv_array_get(letter->contour->set, j)((void*)(((char*)((letter->contour->set)->data)) + (
size_t)(letter->contour->set)->rsize * (size_t)(j)))
;
366 buffer[point->x + point->y * swt->cols] = i + 1;
367 }
368 }
369 // filter out letters that intersects more than 2 other letters
370 int* another = params.letter_occlude_thresh ? (int*)alloca(sizeof(int) * params.letter_occlude_thresh)__builtin_alloca (sizeof(int) * params.letter_occlude_thresh) : 0;
371 for (i = 0; i < letters->rnum; i++)
372 {
373 ccv_letter_t* letter = (ccv_letter_t*)ccv_array_get(letters, i)((void*)(((char*)((letters)->data)) + (size_t)(letters)->
rsize * (size_t)(i)))
;
374 if (letter->std > letter->mean * params.std_ratio)
375 {
376 ccv_contour_free(letter->contour);
377 continue;
378 }
379 int more = 0;
380 if (another)
381 {
382 // one letter cannot occlude with more than params.letter_occlude_thresh other letters
383 memset(another, 0, sizeof(int) * params.letter_occlude_thresh);
384 for (x = letter->rect.x; x < letter->rect.x + letter->rect.width; x++)
385 {
386 for (y = letter->rect.y; y < letter->rect.y + letter->rect.height; y++)
387 {
388 int group = buffer[x + swt->cols * y];
389 if (group && group != i + 1)
390 {
391 more = 1;
392 for (j = 0; j < params.letter_occlude_thresh; j++)
393 if (!another[j] || another[j] == group)
394 {
395 another[j] = group;
396 more = 0;
397 break;
398 }
399 if (more)
400 break;
401 }
402 }
403 if (more)
404 break;
405 }
406 }
407 if (more)
408 {
409 ccv_contour_free(letter->contour);
410 continue;
411 }
412 for (j = 0; j < letter->contour->set->rnum; j++)
413 {
414 ccv_point_t* point = (ccv_point_t*)ccv_array_get(letter->contour->set, j)((void*)(((char*)((letter->contour->set)->data)) + (
size_t)(letter->contour->set)->rsize * (size_t)(j)))
;
415 letter->intensity += a->data.u8[point->x + point->y * a->step];
416 }
417 letter->intensity /= letter->contour->size;
418 ccv_contour_free(letter->contour);
419 letter->contour = 0;
420 ccv_array_push(new_letters, letter);
421 }
422 ccv_array_free(letters);
423 ccfreefree(buffer);
424 return new_letters;
425}
426
427typedef struct {
428 ccv_letter_t* left;
429 ccv_letter_t* right;
430 int dx;
431 int dy;
432} ccv_letter_pair_t;
433
434typedef struct {
435 ccv_rect_t rect;
436 int neighbors;
437 ccv_letter_t** letters;
438} ccv_textline_t;
439
440static int _ccv_in_textline(const void* a, const void* b, void* data)
441{
442 ccv_letter_pair_t* pair1 = (ccv_letter_pair_t*)a;
443 ccv_letter_pair_t* pair2 = (ccv_letter_pair_t*)b;
444 if (pair1->left == pair2->left || pair1->right == pair2->right)
445 {
446 int tn = pair1->dy * pair2->dx - pair1->dx * pair2->dy;
447 int td = pair1->dx * pair2->dx + pair1->dy * pair2->dy;
448 // share the same end, opposite direction
449 if (tn * 7 < -td * 4 && tn * 7 > td * 4)
450 return 1;
451 } else if (pair1->left == pair2->right || pair1->right == pair2->left) {
452 int tn = pair1->dy * pair2->dx - pair1->dx * pair2->dy;
453 int td = pair1->dx * pair2->dx + pair1->dy * pair2->dy;
454 // share the other end, same direction
455 if (tn * 7 < td * 4 && tn * 7 > -td * 4)
456 return 1;
457 }
458 return 0;
459}
460
461static void _ccv_swt_add_letter(ccv_textline_t* textline, ccv_letter_t* letter)
462{
463 if (textline->neighbors == 0)
464 {
465 textline->rect = letter->rect;
466 textline->neighbors = 1;
467 textline->letters = (ccv_letter_t**)ccmallocmalloc(sizeof(ccv_letter_t*) * textline->neighbors);
468 textline->letters[0] = letter;
469 } else {
470 int i, flag = 0;
471 for (i = 0; i < textline->neighbors; i++)
472 if (textline->letters[i] == letter)
473 {
474 flag = 1;
475 break;
476 }
477 if (flag)
478 return;
479 if (letter->rect.x < textline->rect.x)
480 {
481 textline->rect.width += textline->rect.x - letter->rect.x;
482 textline->rect.x = letter->rect.x;
483 }
484 if (letter->rect.x + letter->rect.width > textline->rect.x + textline->rect.width)
485 textline->rect.width = letter->rect.x + letter->rect.width - textline->rect.x;
486 if (letter->rect.y < textline->rect.y)
487 {
488 textline->rect.height += textline->rect.y - letter->rect.y;
489 textline->rect.y = letter->rect.y;
490 }
491 if (letter->rect.y + letter->rect.height > textline->rect.y + textline->rect.height)
492 textline->rect.height = letter->rect.y + letter->rect.height - textline->rect.y;
493 textline->neighbors++;
494 textline->letters = (ccv_letter_t**)ccreallocrealloc(textline->letters, sizeof(ccv_letter_t*) * textline->neighbors);
495 textline->letters[textline->neighbors - 1] = letter;
496 }
497}
498
499static ccv_array_t* _ccv_swt_merge_textline(ccv_array_t* letters, ccv_swt_param_t params)
500{
501 int i, j;
502 ccv_array_t* pairs = ccv_array_new(sizeof(ccv_letter_pair_t), letters->rnum, 0);
503 double thickness_ratio_inv = 1.0 / params.thickness_ratio;
504 double height_ratio_inv = 1.0 / params.height_ratio;
505 for (i = 0; i < letters->rnum - 1; i++)
506 {
507 ccv_letter_t* li = (ccv_letter_t*)ccv_array_get(letters, i)((void*)(((char*)((letters)->data)) + (size_t)(letters)->
rsize * (size_t)(i)))
;
508 for (j = i + 1; j < letters->rnum; j++)
509 {
510 ccv_letter_t* lj = (ccv_letter_t*)ccv_array_get(letters, j)((void*)(((char*)((letters)->data)) + (size_t)(letters)->
rsize * (size_t)(j)))
;
511 double ratio = (double)li->thickness / lj->thickness;
512 if (ratio > params.thickness_ratio || ratio < thickness_ratio_inv)
513 continue;
514 ratio = (double)li->rect.height / lj->rect.height;
515 if (ratio > params.height_ratio || ratio < height_ratio_inv)
516 continue;
517 if (abs(li->intensity - lj->intensity) > params.intensity_thresh)
518 continue;
519 int dx = li->rect.x - lj->rect.x + (li->rect.width - lj->rect.width) / 2;
520 int dy = li->rect.y - lj->rect.y + (li->rect.height - lj->rect.height) / 2;
521 if (abs(dx) > params.distance_ratio * ccv_max(li->rect.width, lj->rect.width)({ typeof (li->rect.width) _a = (li->rect.width); typeof
(lj->rect.width) _b = (lj->rect.width); (_a > _b) ?
_a : _b; })
)
522 continue;
523 int oy = ccv_min(li->rect.y + li->rect.height, lj->rect.y + lj->rect.height)({ typeof (li->rect.y + li->rect.height) _a = (li->rect
.y + li->rect.height); typeof (lj->rect.y + lj->rect
.height) _b = (lj->rect.y + lj->rect.height); (_a < _b
) ? _a : _b; })
- ccv_max(li->rect.y, lj->rect.y)({ typeof (li->rect.y) _a = (li->rect.y); typeof (lj->
rect.y) _b = (lj->rect.y); (_a > _b) ? _a : _b; })
;
524 if (oy * params.intersect_ratio < ccv_min(li->rect.height, lj->rect.height)({ typeof (li->rect.height) _a = (li->rect.height); typeof
(lj->rect.height) _b = (lj->rect.height); (_a < _b)
? _a : _b; })
)
525 continue;
526 ccv_letter_pair_t pair = { .left = li, .right = lj, .dx = dx, .dy = dy };
527 ccv_array_push(pairs, &pair);
528 }
529 }
530 ccv_array_t* idx = 0;
531 int nchains = ccv_array_group(pairs, &idx, _ccv_in_textline, 0);
532 ccv_textline_t* chain = (ccv_textline_t*)ccmallocmalloc(nchains * sizeof(ccv_textline_t));
533 for (i = 0; i < nchains; i++)
534 chain[i].neighbors = 0;
535 for (i = 0; i < pairs->rnum; i++)
536 {
537 j = *(int*)ccv_array_get(idx, i)((void*)(((char*)((idx)->data)) + (size_t)(idx)->rsize *
(size_t)(i)))
;
538 _ccv_swt_add_letter(chain + j,((ccv_letter_pair_t*)ccv_array_get(pairs, i)((void*)(((char*)((pairs)->data)) + (size_t)(pairs)->rsize
* (size_t)(i)))
)->left);
539 _ccv_swt_add_letter(chain + j, ((ccv_letter_pair_t*)ccv_array_get(pairs, i)((void*)(((char*)((pairs)->data)) + (size_t)(pairs)->rsize
* (size_t)(i)))
)->right);
540 }
541 ccv_array_free(idx);
542 ccv_array_free(pairs);
543 ccv_array_t* regions = ccv_array_new(sizeof(ccv_textline_t), 5, 0);
544 for (i = 0; i < nchains; i++)
545 if (chain[i].neighbors >= params.letter_thresh && chain[i].rect.width > chain[i].rect.height * params.elongate_ratio)
546 ccv_array_push(regions, chain + i);
547 else if (chain[i].neighbors > 0)
548 ccfreefree(chain[i].letters);
549 ccfreefree(chain);
550 return regions;
551}
552
553#define less_than(a, b, aux) ((a)->center.x < (b)->center.x)
554static CCV_IMPLEMENT_QSORT(_ccv_sort_letters, ccv_letter_t*, less_than)void _ccv_sort_letters(ccv_letter_t* *array, size_t total, int
aux) { int isort_thresh = 7; ccv_letter_t* t; int sp = 0; struct
{ ccv_letter_t* *lb; ccv_letter_t* *ub; } stack[48]; if( total
<= 1 ) return; stack[0].lb = array; stack[0].ub = array +
(total - 1); while( sp >= 0 ) { ccv_letter_t** left = stack
[sp].lb; ccv_letter_t** right = stack[sp--].ub; for(;;) { int
i, n = (int)(right - left) + 1, m; ccv_letter_t** ptr; ccv_letter_t
** ptr2; if( n <= isort_thresh ) { insert_sort: for( ptr =
left + 1; ptr <= right; ptr++ ) { for( ptr2 = ptr; ptr2 >
left && less_than(ptr2[0],ptr2[-1], aux); ptr2--) ((
(t)) = ((ptr2[0])), ((ptr2[0])) = ((ptr2[-1])), ((ptr2[-1])) =
((t))); } break; } else { ccv_letter_t** left0; ccv_letter_t
** left1; ccv_letter_t** right0; ccv_letter_t** right1; ccv_letter_t
** pivot; ccv_letter_t** a; ccv_letter_t** b; ccv_letter_t** c
; int swap_cnt = 0; left0 = left; right0 = right; pivot = left
+ (n/2); if( n > 40 ) { int d = n / 8; a = left, b = left
+ d, c = left + 2*d; left = less_than(*a, *b, aux) ? (less_than
(*b, *c, aux) ? b : (less_than(*a, *c, aux) ? c : a)) : (less_than
(*c, *b, aux) ? b : (less_than(*a, *c, aux) ? a : c)); a = pivot
- d, b = pivot, c = pivot + d; pivot = less_than(*a, *b, aux
) ? (less_than(*b, *c, aux) ? b : (less_than(*a, *c, aux) ? c
: a)) : (less_than(*c, *b, aux) ? b : (less_than(*a, *c, aux
) ? a : c)); a = right - 2*d, b = right - d, c = right; right
= less_than(*a, *b, aux) ? (less_than(*b, *c, aux) ? b : (less_than
(*a, *c, aux) ? c : a)) : (less_than(*c, *b, aux) ? b : (less_than
(*a, *c, aux) ? a : c)); } a = left, b = pivot, c = right; pivot
= less_than(*a, *b, aux) ? (less_than(*b, *c, aux) ? b : (less_than
(*a, *c, aux) ? c : a)) : (less_than(*c, *b, aux) ? b : (less_than
(*a, *c, aux) ? a : c)); if( pivot != left0 ) { (((t)) = ((*pivot
)), ((*pivot)) = ((*left0)), ((*left0)) = ((t))); pivot = left0
; } left = left1 = left0 + 1; right = right1 = right0; for(;;
) { while( left <= right && !less_than(*pivot, *left
, aux) ) { if( !less_than(*left, *pivot, aux) ) { if( left >
left1 ) (((t)) = ((*left1)), ((*left1)) = ((*left)), ((*left
)) = ((t))); swap_cnt = 1; left1++; } left++; } while( left <=
right && !less_than(*right, *pivot, aux) ) { if( !less_than
(*pivot, *right, aux) ) { if( right < right1 ) (((t)) = ((
*right1)), ((*right1)) = ((*right)), ((*right)) = ((t))); swap_cnt
= 1; right1--; } right--; } if( left > right ) break; (((
t)) = ((*left)), ((*left)) = ((*right)), ((*right)) = ((t)));
swap_cnt = 1; left++; right--; } if( swap_cnt == 0 ) { left =
left0, right = right0; goto insert_sort; } n = ({ typeof ((int
)(left1 - left0)) _a = ((int)(left1 - left0)); typeof ((int)(
left - left1)) _b = ((int)(left - left1)); (_a < _b) ? _a :
_b; }); for( i = 0; i < n; i++ ) (((t)) = ((left0[i])), (
(left0[i])) = ((left[i-n])), ((left[i-n])) = ((t))); n = ({ typeof
((int)(right0 - right1)) _a = ((int)(right0 - right1)); typeof
((int)(right1 - right)) _b = ((int)(right1 - right)); (_a <
_b) ? _a : _b; }); for( i = 0; i < n; i++ ) (((t)) = ((left
[i])), ((left[i])) = ((right0[i-n+1])), ((right0[i-n+1])) = (
(t))); n = (int)(left - left1); m = (int)(right1 - right); if
( n > 1 ) { if( m > 1 ) { if( n > m ) { stack[++sp].
lb = left0; stack[sp].ub = left0 + n - 1; left = right0 - m +
1, right = right0; } else { stack[++sp].lb = right0 - m + 1;
stack[sp].ub = right0; left = left0, right = left0 + n - 1; }
} else left = left0, right = left0 + n - 1; } else if( m >
1 ) left = right0 - m + 1, right = right0; else break; } } }
}
555#undef less_than
556
557static ccv_array_t* _ccv_swt_break_words(ccv_array_t* textline, ccv_swt_param_t params)
558{
559 int i, j, n = 0;
560 for (i = 0; i < textline->rnum; i++)
561 {
562 ccv_textline_t* t = (ccv_textline_t*)ccv_array_get(textline, i)((void*)(((char*)((textline)->data)) + (size_t)(textline)->
rsize * (size_t)(i)))
;
563 if (t->neighbors - 1 > n)
564 n = t->neighbors - 1;
565 }
566 assert(n > 0)((void) sizeof ((n > 0) ? 1 : 0), __extension__ ({ if (n >
0) ; else __assert_fail ("n > 0", "ccv_swt.c", 566, __extension__
__PRETTY_FUNCTION__); }))
;
567 int* buffer = (int*)alloca(n * sizeof(int))__builtin_alloca (n * sizeof(int));
568 ccv_array_t* words = ccv_array_new(sizeof(ccv_rect_t), textline->rnum, 0);
569 for (i = 0; i < textline->rnum; i++)
570 {
571 ccv_textline_t* t = (ccv_textline_t*)ccv_array_get(textline, i)((void*)(((char*)((textline)->data)) + (size_t)(textline)->
rsize * (size_t)(i)))
;
572 _ccv_sort_letters(t->letters, t->neighbors, 0);
573 int range = 0;
574 double mean = 0;
575 for (j = 0; j < t->neighbors - 1; j++)
576 {
577 buffer[j] = ccv_max(0, t->letters[j + 1]->rect.x - (t->letters[j]->rect.x + t->letters[j]->rect.width))({ typeof (0) _a = (0); typeof (t->letters[j + 1]->rect
.x - (t->letters[j]->rect.x + t->letters[j]->rect
.width)) _b = (t->letters[j + 1]->rect.x - (t->letters
[j]->rect.x + t->letters[j]->rect.width)); (_a > _b
) ? _a : _b; })
;
578 if (buffer[j] >= range)
579 range = buffer[j] + 1;
580 mean += buffer[j];
581 }
582 ccv_dense_matrix_t otsu = ccv_dense_matrix(1, t->neighbors - 1, CCV_32S | CCV_C1, buffer, 0);
583 double var;
584 int threshold = ccv_otsu(&otsu, &var, range);
585 mean = mean / (t->neighbors - 1);
586 if (sqrt(var) > mean * params.breakdown_ratio)
587 {
588 ccv_textline_t nt = { .neighbors = 0, .letters = 0 };
589 _ccv_swt_add_letter(&nt, t->letters[0]);
590 for (j = 0; j < t->neighbors - 1; j++)
591 {
592 if (buffer[j] > threshold)
593 {
594 ccv_array_push(words, &nt.rect);
595 if (nt.letters)
596 ccfreefree(nt.letters);
597 nt.letters = 0;
598 nt.neighbors = 0;
599 }
600 _ccv_swt_add_letter(&nt, t->letters[j + 1]);
601 }
602 ccv_array_push(words, &nt.rect);
603 if (nt.letters)
604 ccfreefree(nt.letters);
605 } else {
606 ccv_array_push(words, &(t->rect));
607 }
608 }
609 return words;
610}
611
612static int _ccv_is_same_textline(const void* a, const void* b, void* data)
613{
614 ccv_textline_t* t1 = (ccv_textline_t*)a;
615 ccv_textline_t* t2 = (ccv_textline_t*)b;
616 int width = ccv_min(t1->rect.x + t1->rect.width, t2->rect.x + t2->rect.width)({ typeof (t1->rect.x + t1->rect.width) _a = (t1->rect
.x + t1->rect.width); typeof (t2->rect.x + t2->rect.
width) _b = (t2->rect.x + t2->rect.width); (_a < _b)
? _a : _b; })
- ccv_max(t1->rect.x, t2->rect.x)({ typeof (t1->rect.x) _a = (t1->rect.x); typeof (t2->
rect.x) _b = (t2->rect.x); (_a > _b) ? _a : _b; })
;
617 int height = ccv_min(t1->rect.y + t1->rect.height, t2->rect.y + t2->rect.height)({ typeof (t1->rect.y + t1->rect.height) _a = (t1->rect
.y + t1->rect.height); typeof (t2->rect.y + t2->rect
.height) _b = (t2->rect.y + t2->rect.height); (_a < _b
) ? _a : _b; })
- ccv_max(t1->rect.y, t2->rect.y)({ typeof (t1->rect.y) _a = (t1->rect.y); typeof (t2->
rect.y) _b = (t2->rect.y); (_a > _b) ? _a : _b; })
;
618 /* overlapped 10% */
619 double* thresh = (double*)data;
620 return (width > 0 && height > 0 &&
621 width * height > thresh[0] * ccv_max(t1->rect.width * t1->rect.height, t2->rect.width * t2->rect.height)({ typeof (t1->rect.width * t1->rect.height) _a = (t1->
rect.width * t1->rect.height); typeof (t2->rect.width *
t2->rect.height) _b = (t2->rect.width * t2->rect.height
); (_a > _b) ? _a : _b; })
&&
622 width * height > thresh[1] * ccv_min(t1->rect.width * t1->rect.height, t2->rect.width * t2->rect.height)({ typeof (t1->rect.width * t1->rect.height) _a = (t1->
rect.width * t1->rect.height); typeof (t2->rect.width *
t2->rect.height) _b = (t2->rect.width * t2->rect.height
); (_a < _b) ? _a : _b; })
);
623}
624
625ccv_array_t* ccv_swt_detect_words(ccv_dense_matrix_t* a, ccv_swt_param_t params)
626{
627 int hr = a->rows * 2 / (params.min_height + params.max_height);
628 int wr = a->cols * 2 / (params.min_height + params.max_height);
629 double scale = pow(2., 1. / (params.interval + 1.));
630 int next = params.interval + 1;
631 int scale_upto = params.scale_invariant ? (int)(log((double)ccv_min(hr, wr)({ typeof (hr) _a = (hr); typeof (wr) _b = (wr); (_a < _b)
? _a : _b; })
) / log(scale)) : 1;
1
Assuming the condition is false
2
'?' condition is false
632 int i, k;
633 ccv_array_t* all_words = params.scale_invariant ? ccv_array_new(sizeof(ccv_rect_t), 2, 0) : 0;
3
'?' condition is false
634 ccv_dense_matrix_t* phx = a;
635 ccv_dense_matrix_t* pyr = a;
636 double cscale = 1.0;
637 for (k = 0; k < scale_upto; k++)
4
Loop condition is true. Entering loop body
638 {
639 // create down-sampled image on-demand because swt itself is very memory intensive
640 if (k % next)
5
Assuming the condition is false
6
Taking false branch
641 {
642 pyr = 0;
643 int j = k % next;
644 ccv_resample(phx, &pyr, 0, (int)(phx->rows / pow(scale, j)), (int)(phx->cols / pow(scale, j)), CCV_INTER_AREA);
645 } else if (k > 0) {
7
Taking false branch
646 ccv_dense_matrix_t* pha = phx;
647 phx = 0;
648 ccv_sample_down(pha, &phx, 0, 0, 0);
649 if (pha != a)
650 ccv_matrix_free(pha);
651 pyr = phx;
652 }
653 // Assumes if it is in the cache, then we can fetch these out of cache easily.
654 // (If the assumption is not true, worst case, we have the result cached for
655 // ccv_swt, but we don't for ccv_canny / ccv_close_outline / ccv_sobel, we will
656 // waste computation on these intermediate results.
657 ccv_dense_matrix_t* cc = 0;
658 ccv_canny(pyr, &cc, 0, params.size, params.low_thresh, params.high_thresh);
659 ccv_dense_matrix_t* c = 0;
660 ccv_close_outline(cc, &c, 0);
661 ccv_matrix_free(cc);
662 ccv_dense_matrix_t* dx = 0;
663 ccv_sobel(pyr, &dx, 0, params.size, 0);
664 ccv_dense_matrix_t* dy = 0;
665 ccv_sobel(pyr, &dy, 0, 0, params.size);
666 ccv_array_t* letters_a[2];
667 ccv_array_t* textline_a[2];
668 parallel_for(i, 2){ int i; for ((i) = 0; (i) < (2); (i)++) { {
8
Loop condition is true. Entering loop body
669 ccv_dense_matrix_t* swt = 0;
670 params.direction = (i == 0) ? CCV_DARK_TO_BRIGHT : CCV_BRIGHT_TO_DARK;
9
'?' condition is true
671 _ccv_swt(pyr, &swt, 0, params, c, dx, dy);
672 /* perform connected component analysis */
673 letters_a[i] = _ccv_swt_connected_letters(pyr, swt, params);
10
Calling '_ccv_swt_connected_letters'
674 ccv_matrix_free(swt);
675 textline_a[i] = _ccv_swt_merge_textline(letters_a[i], params);
676 } parallel_endfor} }
677 ccv_matrix_free(c);
678 ccv_matrix_free(dx);
679 ccv_matrix_free(dy);
680 if (pyr != phx)
681 ccv_matrix_free(pyr);
682 ccv_array_t* textline = textline_a[0];
683 for (i = 0; i < textline_a[1]->rnum; i++)
684 ccv_array_push(textline, ccv_array_get(textline_a[1], i)((void*)(((char*)((textline_a[1])->data)) + (size_t)(textline_a
[1])->rsize * (size_t)(i)))
);
685 ccv_array_free(textline_a[1]);
686 ccv_array_t* idx = 0;
687 int ntl = ccv_array_group(textline, &idx, _ccv_is_same_textline, params.same_word_thresh);
688 ccv_array_t* words;
689 if (params.breakdown && ntl > 0)
690 {
691 ccv_array_t* const textline2 = ccv_array_new(sizeof(ccv_textline_t), ntl, 0);
692 ccv_array_zero(textline2);
693 textline2->rnum = ntl;
694 for (i = 0; i < textline->rnum; i++)
695 {
696 ccv_textline_t* r = (ccv_textline_t*)ccv_array_get(textline, i)((void*)(((char*)((textline)->data)) + (size_t)(textline)->
rsize * (size_t)(i)))
;
697 int k = *(int*)ccv_array_get(idx, i)((void*)(((char*)((idx)->data)) + (size_t)(idx)->rsize *
(size_t)(i)))
;
698 ccv_textline_t* r2 = (ccv_textline_t*)ccv_array_get(textline2, k)((void*)(((char*)((textline2)->data)) + (size_t)(textline2
)->rsize * (size_t)(k)))
;
699 if (r2->rect.width < r->rect.width)
700 {
701 if (r2->letters)
702 ccfreefree(r2->letters);
703 *r2 = *r;
704 } else if (r->letters) {
705 ccfreefree(r->letters);
706 }
707 }
708 ccv_array_free(idx);
709 ccv_array_free(textline);
710 words = _ccv_swt_break_words(textline2, params);
711 for (i = 0; i < textline2->rnum; i++)
712 ccfreefree(((ccv_textline_t*)ccv_array_get(textline2, i)((void*)(((char*)((textline2)->data)) + (size_t)(textline2
)->rsize * (size_t)(i)))
)->letters);
713 ccv_array_free(textline2);
714 ccv_array_free(letters_a[0]);
715 ccv_array_free(letters_a[1]);
716 } else {
717 ccv_array_free(letters_a[0]);
718 ccv_array_free(letters_a[1]);
719 words = ccv_array_new(sizeof(ccv_rect_t), ntl, 0);
720 ccv_array_zero(words);
721 words->rnum = ntl;
722 for (i = 0; i < textline->rnum; i++)
723 {
724 ccv_textline_t* r = (ccv_textline_t*)ccv_array_get(textline, i)((void*)(((char*)((textline)->data)) + (size_t)(textline)->
rsize * (size_t)(i)))
;
725 if (r->letters)
726 ccfreefree(r->letters);
727 int k = *(int*)ccv_array_get(idx, i)((void*)(((char*)((idx)->data)) + (size_t)(idx)->rsize *
(size_t)(i)))
;
728 ccv_rect_t* r2 = (ccv_rect_t*)ccv_array_get(words, k)((void*)(((char*)((words)->data)) + (size_t)(words)->rsize
* (size_t)(k)))
;
729 if (r2->width * r2->height < r->rect.width * r->rect.height)
730 *r2 = r->rect;
731 }
732 ccv_array_free(idx);
733 ccv_array_free(textline);
734 }
735 if (params.scale_invariant)
736 {
737 for (i = 0; i < words->rnum; i++)
738 {
739 ccv_rect_t* rect = (ccv_rect_t*)ccv_array_get(words, i)((void*)(((char*)((words)->data)) + (size_t)(words)->rsize
* (size_t)(i)))
;
740 rect->x = (int)(rect->x * cscale + 0.5);
741 rect->y = (int)(rect->y * cscale + 0.5);
742 rect->width = (int)(rect->width * cscale + 0.5);
743 rect->height = (int)(rect->height * cscale + 0.5);
744 ccv_array_push(all_words, rect);
745 }
746 ccv_array_free(words);
747 cscale *= scale;
748 } else
749 all_words = words;
750 }
751 if (params.scale_invariant && params.min_neighbors)
752 {
753 assert(all_words)((void) sizeof ((all_words) ? 1 : 0), __extension__ ({ if (all_words
) ; else __assert_fail ("all_words", "ccv_swt.c", 753, __extension__
__PRETTY_FUNCTION__); }))
;
754 // de-dup logic, similar to what BBF / DPM have
755 ccv_array_t* idx = 0;
756 int ntl = ccv_array_group(all_words, &idx, _ccv_is_same_textline, params.same_word_thresh);
757 ccv_array_t* new_words = ccv_array_new(sizeof(ccv_comp_t), ntl, 0);
758 ccv_array_zero(new_words);
759 new_words->rnum = ntl;
760 for (i = 0; i < all_words->rnum; i++)
761 {
762 ccv_rect_t* r1 = (ccv_rect_t*)ccv_array_get(all_words, i)((void*)(((char*)((all_words)->data)) + (size_t)(all_words
)->rsize * (size_t)(i)))
;
763 int k = *(int*)ccv_array_get(idx, i)((void*)(((char*)((idx)->data)) + (size_t)(idx)->rsize *
(size_t)(i)))
;
764 ccv_comp_t* r2 = (ccv_comp_t*)ccv_array_get(new_words, k)((void*)(((char*)((new_words)->data)) + (size_t)(new_words
)->rsize * (size_t)(k)))
;
765 if (r2->neighbors)
766 {
767 ++r2->neighbors;
768 // simply pick the biggest
769 if (r1->width * r1->height > r2->rect.width * r2->rect.height)
770 r2->rect = *r1;
771 } else {
772 r2->rect = *r1;
773 r2->neighbors = 1;
774 }
775 }
776 ccv_array_free(idx);
777 ccv_array_free(all_words);
778 if (params.min_neighbors > 1)
779 {
780 // filter out min_neighbors
781 all_words = ccv_array_new(sizeof(ccv_comp_t), new_words->rnum / 2, 0);
782 for (i = 0; i < new_words->rnum; i++)
783 {
784 ccv_comp_t* comp = (ccv_comp_t*)ccv_array_get(new_words, i)((void*)(((char*)((new_words)->data)) + (size_t)(new_words
)->rsize * (size_t)(i)))
;
785 int n = comp->neighbors;
786 if (n >= params.min_neighbors)
787 ccv_array_push(all_words, comp);
788 }
789 ccv_array_free(new_words);
790 } else
791 // just copy the pointer for min_neighbors == 1
792 all_words = new_words;
793 }
794 if (phx != a)
795 ccv_matrix_free(phx);
796 return all_words;
797}