Bug Summary

File:ccv_swt.c
Warning:line 545, column 96
The left operand of '*' is a garbage value

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name ccv_swt.c -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 -setup-static-analyzer -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=none -menable-no-infs -menable-no-nans -fapprox-func -funsafe-math-optimizations -fno-signed-zeros -mreassociate -freciprocal-math -fdenormal-fp-math=preserve-sign,preserve-sign -ffp-contract=fast -fno-rounding-math -ffast-math -ffinite-math-only -complex-range=limited -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -target-feature +sse2 -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/home/liu/actions-runner/_work/ccv/ccv/lib -fcoverage-compilation-dir=/home/liu/actions-runner/_work/ccv/ccv/lib -resource-dir /usr/local/lib/clang/18 -I . -I /usr/local/cuda/include -D HAVE_CBLAS -D HAVE_LIBPNG -D HAVE_LIBJPEG -D HAVE_FFTW3 -D HAVE_PTHREAD -D HAVE_LIBLINEAR -D HAVE_TESSERACT -D HAVE_AVCODEC -D HAVE_AVFORMAT -D HAVE_AVUTIL -D HAVE_SWSCALE -D HAVE_SSE2 -D HAVE_GSL -D HAVE_CUDA -D HAVE_CUDNN -D HAVE_NCCL -D USE_SYSTEM_CUB -D HAVE_CUDA_SM80 -I /usr/local/include -internal-isystem /usr/local/lib/clang/18/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/12/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O3 -ferror-limit 19 -fgnuc-version=4.2.1 -fskip-odr-check-in-gmf -vectorize-loops -vectorize-slp -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/liu/actions-runner/_work/ccv/ccv/_analyze/2024-06-10-094233-222984-1 -x c ccv_swt.c
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; } }
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 | CCV_16F | CCV_QX
), 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) * (xx) + _for_get_d(dy_ptr, j) * (xy); \
100 rdy = _for_get_d(dx_ptr, j) * (yx) + _for_get_d(dy_ptr, j) * (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) * _for_get_d(dx_ptr + (ky - i + dy9[k]) * dx->step, kx + dx9[k]) - \
143 _for_get_d(dx_ptr, j) * _for_get_d(dy_ptr + (ky - i + dy9[k]) * dy->step, kx + dx9[k]); \
144 int td = _for_get_d(dx_ptr, j) * _for_get_d(dx_ptr + (ky - i + dy9[k]) * dx->step, kx + dx9[k]) + \
145 _for_get_d(dy_ptr, j) * _for_get_d(dy_ptr + (ky - i + dy9[k]) * dy->step, kx + dx9[k]); \
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 || _for_get_b(b_ptr + (y0 - i) * db->step, x0) > w) \
161 _for_set_b(b_ptr + (y0 - i) * db->step, x0, w); \
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); \
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); \
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);
312 double aspect_ratio_inv = 1.0 / params.aspect_ratio;
313 for (i = 0; i < contours->rnum; i++)
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__); }));
317 double ratio = (double)contour->rect.width / (double)contour->rect.height;
318 if (ratio < aspect_ratio_inv || ratio > params.aspect_ratio)
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)
331 {
332 ccv_contour_free(contour);
333 continue;
334 }
335 double mean = 0;
336 for (j = 0; j < contour->size; j++)
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++)
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);
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++)
10
←
Assuming the condition is false
→
11
←
Loop condition is false. Execution continues on line 530
→
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));
12
←
Uninitialized value stored to field 'height'
→
533 for (i = 0; i < nchains; i++)
13
←
Assuming 'i' is < 'nchains'
→
14
←
Loop condition is true. Entering loop body
→
15
←
Assuming 'i' is >= 'nchains'
→
16
←
Loop condition is false. Execution continues on line 535
→
534 chain[i].neighbors = 0;
535 for (i = 0; i < pairs->rnum; i++)
17
←
Assuming 'i' is >= field 'rnum'
→
18
←
Loop condition is false. Execution continues on line 541
→
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)
19
←
Assuming field 'neighbors' is >= field 'letter_thresh'
→
20
←
The left operand of '*' is a garbage value
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 field 'scale_invariant' is 0
→
2
←
'?' condition is false
→
632 int i, k;
633 ccv_array_t* all_words = params.scale_invariant
2.1
Field 'scale_invariant' is 0
 ? 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
←
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
5.1
'k' is <= 0
 > 0) {
6
←
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)++) { {
7
←
Loop condition is true. Entering loop body
→
669 ccv_dense_matrix_t* swt = 0;
670 params.direction = (i
7.1
'i' is equal to 0
 == 0) ? CCV_DARK_TO_BRIGHT : CCV_BRIGHT_TO_DARK;
8
←
'?' 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);
674 ccv_matrix_free(swt);
675 textline_a[i] = _ccv_swt_merge_textline(letters_a[i], params);
9
←
Calling '_ccv_swt_merge_textline'
→
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}