#include "ccv.h"
#include "ccv_internal.h"
const ccv_swt_param_t ccv_swt_default_params = {
.interval = 1,
.same_word_thresh = { 0.1, 0.8 },
.min_neighbors = 1,
.scale_invariant = 0,
.size = 3,
.low_thresh = 124,
.high_thresh = 204,
.max_height = 300,
.min_height = 8,
.min_area = 38,
.letter_occlude_thresh = 3,
.aspect_ratio = 8,
.std_ratio = 0.83,
.thickness_ratio = 1.5,
.height_ratio = 1.7,
.intensity_thresh = 31,
.distance_ratio = 2.9,
.intersect_ratio = 1.3,
.letter_thresh = 3,
.elongate_ratio = 1.9,
.breakdown = 1,
.breakdown_ratio = 1.0,
};
static inline CCV_IMPLEMENT_MEDIAN(_ccv_swt_median, int)
typedef struct {
int x0, x1, y0, y1;
int w;
} ccv_swt_stroke_t;
#define less_than(s1, s2, aux) ((s1).w < (s2).w)
static CCV_IMPLEMENT_QSORT(_ccv_swt_stroke_qsort, ccv_swt_stroke_t, less_than)
#undef less_than
/* ccv_swt is only the method to generate stroke width map */
void ccv_swt(ccv_dense_matrix_t* a, ccv_dense_matrix_t** b, int type, ccv_swt_param_t params)
{
assert(a->type & CCV_C1);
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);
type = (type == 0) ? CCV_32S | CCV_C1 : CCV_GET_DATA_TYPE(type) | CCV_C1;
ccv_dense_matrix_t* db = *b = ccv_dense_matrix_renew(*b, a->rows, a->cols, CCV_C1 | CCV_ALL_DATA_TYPE, type, sig);
ccv_object_return_if_cached(, db);
ccv_dense_matrix_t* cc = 0;
ccv_canny(a, &cc, 0, params.size, params.low_thresh, params.high_thresh);
ccv_dense_matrix_t* c = 0;
ccv_close_outline(cc, &c, 0);
ccv_matrix_free(cc);
ccv_dense_matrix_t* dx = 0;
ccv_sobel(a, &dx, 0, params.size, 0);
ccv_dense_matrix_t* dy = 0;
ccv_sobel(a, &dy, 0, 0, params.size);
int i, j, k, w;
int* buf = (int*)alloca(sizeof(int) * ccv_max(a->cols, a->rows));
ccv_array_t* strokes = ccv_array_new(sizeof(ccv_swt_stroke_t), 64, 0);
unsigned char* b_ptr = db->data.u8;
unsigned char* c_ptr = c->data.u8;
unsigned char* dx_ptr = dx->data.u8;
unsigned char* dy_ptr = dy->data.u8;
ccv_zero(db);
int dx5[] = {-1, 0, 1, 0, 0};
int dy5[] = {0, 0, 0, -1, 1};
int dx9[] = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
int dy9[] = {0, 0, 0, -1, -1, -1, 1, 1, 1};
int adx, ady, sx, sy, err, e2, x0, x1, y0, y1, kx, ky;
#define ray_reset() \
err = adx - ady; e2 = 0; \
x0 = j; y0 = i;
#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;
#define ray_increment() \
e2 = 2 * err; \
if (e2 > -ady) \
{ \
err -= ady; \
x0 += sx; \
} \
if (e2 < adx) \
{ \
err += adx; \
y0 += sy; \
}
int rdx, rdy, flag;
#define ray_emit(xx, xy, yx, yy, _for_get_d, _for_set_b, _for_get_b) \
rdx = _for_get_d(dx_ptr, j, 0) * (xx) + _for_get_d(dy_ptr, j, 0) * (xy); \
rdy = _for_get_d(dx_ptr, j, 0) * (yx) + _for_get_d(dy_ptr, j, 0) * (yy); \
adx = abs(rdx); \
ady = abs(rdy); \
sx = rdx > 0 ? -params.direction : params.direction; \
sy = rdy > 0 ? -params.direction : params.direction; \
/* Bresenham's line algorithm */ \
ray_reset(); \
flag = 0; \
kx = x0; \
ky = y0; \
for (w = 0; w < 70; w++) \
{ \
ray_increment(); \
if (x0 >= a->cols - 1 || x0 < 1 || y0 >= a->rows - 1 || y0 < 1) \
break; \
if (abs(i - y0) >= 2 || abs(j - x0) >= 2) \
{ /* ideally, I can encounter another edge directly, but in practice, we should search in a small region around it */ \
flag = 0; \
for (k = 0; k < 5; k++) \
{ \
kx = x0 + dx5[k]; \
ky = y0 + dy5[k]; \
if (c_ptr[kx + (ky - i) * c->step]) \
{ \
flag = 1; \
break; \
} \
} \
if (flag) \
break; \
} \
} \
if (flag && kx < a->cols - 1 && kx > 0 && ky < a->rows - 1 && ky > 0) \
{ \
/* the opposite angle should be in d_p -/+ PI / 6 (otherwise discard),
* a faster computation should be:
* Tan(d_q - d_p) = (Tan(d_q) - Tan(d_p)) / (1 + Tan(d_q) * Tan(d_p))
* and -1 / sqrt(3) < Tan(d_q - d_p) < 1 / sqrt(3)
* also, we needs to check the whole 3x3 neighborhood in a hope that we don't miss one or two of them */ \
flag = 0; \
for (k = 0; k < 9; k++) \
{ \
int tn = _for_get_d(dy_ptr, j, 0) * _for_get_d(dx_ptr + (ky - i + dy9[k]) * dx->step, kx + dx9[k], 0) - \
_for_get_d(dx_ptr, j, 0) * _for_get_d(dy_ptr + (ky - i + dy9[k]) * dy->step, kx + dx9[k], 0); \
int td = _for_get_d(dx_ptr, j, 0) * _for_get_d(dx_ptr + (ky - i + dy9[k]) * dx->step, kx + dx9[k], 0) + \
_for_get_d(dy_ptr, j, 0) * _for_get_d(dy_ptr + (ky - i + dy9[k]) * dy->step, kx + dx9[k], 0); \
if (tn * 7 < -td * 4 && tn * 7 > td * 4) \
{ \
flag = 1; \
break; \
} \
} \
if (flag) \
{ \
x1 = x0; y1 = y0; \
ray_reset(); \
w = (int)(sqrt((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0)) + 0.5); \
/* extend the line to be width of 1 */ \
for (;;) \
{ \
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) \
_for_set_b(b_ptr + (y0 - i) * db->step, x0, w, 0); \
if (x0 == x1 && y0 == y1) \
break; \
ray_increment(); \
} \
ccv_swt_stroke_t stroke = { \
.x0 = j, \
.x1 = x1, \
.y0 = i, \
.y1 = y1, \
.w = w \
}; \
ccv_array_push(strokes, &stroke); \
} \
}
#define for_block(_for_get_d, _for_set_b, _for_get_b) \
for (i = 0; i < a->rows; i++) \
{ \
for (j = 0; j < a->cols; j++) \
if (c_ptr[j]) \
{ \
ray_emit(1, 0, 0, 1, _for_get_d, _for_set_b, _for_get_b); \
ray_emit(1, -1, 1, 1, _for_get_d, _for_set_b, _for_get_b); \
ray_emit(1, 1, -1, 1, _for_get_d, _for_set_b, _for_get_b); \
} \
b_ptr += db->step; \
c_ptr += c->step; \
dx_ptr += dx->step; \
dy_ptr += dy->step; \
} \
b_ptr = db->data.u8; \
/* compute median width of stroke, from shortest strokes to longest */ \
_ccv_swt_stroke_qsort((ccv_swt_stroke_t*)ccv_array_get(strokes, 0), strokes->rnum, 0); \
for (i = 0; i < strokes->rnum; i++) \
{ \
ccv_swt_stroke_t* stroke = (ccv_swt_stroke_t*)ccv_array_get(strokes, i); \
ray_reset_by_stroke(stroke); \
int n = 0; \
for (;;) \
{ \
buf[n++] = _for_get_b(b_ptr + y0 * db->step, x0, 0); \
if (x0 == stroke->x1 && y0 == stroke->y1) \
break; \
ray_increment(); \
} \
int nw = _ccv_swt_median(buf, 0, n - 1); \
if (nw != stroke->w) \
{ \
ray_reset_by_stroke(stroke); \
for (;;) \
{ \
_for_set_b(b_ptr + y0 * db->step, x0, nw, 0); \
if (x0 == stroke->x1 && y0 == stroke->y1) \
break; \
ray_increment(); \
} \
} \
}
ccv_matrix_getter(dx->type, ccv_matrix_setter_getter, db->type, for_block);
#undef for_block
#undef ray_emit
#undef ray_reset
#undef ray_increment
ccv_array_free(strokes);
ccv_matrix_free(c);
ccv_matrix_free(dx);
ccv_matrix_free(dy);
}
static ccv_array_t* _ccv_swt_connected_component(ccv_dense_matrix_t* a, int ratio, int min_height, int max_height, int min_area)
{
int i, j, k;
int* a_ptr = a->data.i32;
int dx8[] = {-1, 1, -1, 0, 1, -1, 0, 1};
int dy8[] = {0, 0, -1, -1, -1, 1, 1, 1};
int* marker = (int*)ccmalloc(sizeof(int) * a->rows * a->cols);
memset(marker, 0, sizeof(int) * a->rows * a->cols);
int* m_ptr = marker;
ccv_point_t* buffer = (ccv_point_t*)ccmalloc(sizeof(ccv_point_t) * a->rows * a->cols);
ccv_array_t* contours = ccv_array_new(sizeof(ccv_contour_t*), 5, 0);
for (i = 0; i < a->rows; i++)
{
for (j = 0; j < a->cols; j++)
if (a_ptr[j] != 0 && !m_ptr[j])
{
m_ptr[j] = 1;
ccv_contour_t* contour = ccv_contour_new(1);
ccv_point_t* closed = buffer;
closed->x = j;
closed->y = i;
ccv_point_t* open = buffer + 1;
for (; closed < open; closed++)
{
ccv_contour_push(contour, *closed);
double w = a_ptr[closed->x + (closed->y - i) * a->cols];
for (k = 0; k < 8; k++)
{
int nx = closed->x + dx8[k];
int ny = closed->y + dy8[k];
if (nx >= 0 && nx < a->cols && ny >= 0 && ny < a->rows &&
a_ptr[nx + (ny - i) * a->cols] != 0 &&
!m_ptr[nx + (ny - i) * a->cols] &&
(a_ptr[nx + (ny - i) * a->cols] <= ratio * w && a_ptr[nx + (ny - i) * a->cols] * ratio >= w))
{
m_ptr[nx + (ny - i) * a->cols] = 1;
// compute new average w
w = (w * (int)(open - closed + 1) + a_ptr[nx + (ny - i) * a->cols]) / (double)(open - closed + 2);
open->x = nx;
open->y = ny;
open++;
}
}
}
if (contour->rect.height < min_height || contour->rect.height > max_height || contour->size < min_area)
ccv_contour_free(contour);
else
ccv_array_push(contours, &contour);
}
a_ptr += a->cols;
m_ptr += a->cols;
}
ccfree(marker);
ccfree(buffer);
return contours;
}
typedef struct {
ccv_rect_t rect;
ccv_point_t center;
int thickness;
int intensity;
double std;
double mean;
ccv_contour_t* contour;
} ccv_letter_t;
static ccv_array_t* _ccv_swt_connected_letters(ccv_dense_matrix_t* a, ccv_dense_matrix_t* swt, ccv_swt_param_t params)
{
ccv_array_t* contours = _ccv_swt_connected_component(swt, 3, params.min_height, params.max_height, params.min_area);
ccv_array_t* letters = ccv_array_new(sizeof(ccv_letter_t), 5, 0);
int i, j, x, y;
// merge contours that inside other contours
int* buffer = (int*)ccmalloc(sizeof(int) * swt->rows * swt->cols);
double aspect_ratio_inv = 1.0 / params.aspect_ratio;
for (i = 0; i < contours->rnum; i++)
{
ccv_contour_t* contour = *(ccv_contour_t**)ccv_array_get(contours, i);
assert(contour->rect.height <= params.max_height && contour->rect.height >= params.min_height);
double ratio = (double)contour->rect.width / (double)contour->rect.height;
if (ratio < aspect_ratio_inv || ratio > params.aspect_ratio)
{
ccv_contour_free(contour);
continue;
}
double xc = (double)contour->m10 / contour->size;
double yc = (double)contour->m01 / contour->size;
double af = (double)contour->m20 / contour->size - xc * xc;
double bf = 2 * ((double)contour->m11 / contour->size - xc * yc);
double cf = (double)contour->m02 / contour->size - yc * yc;
double delta = sqrt(bf * bf + (af - cf) * (af - cf));
ratio = sqrt((af + cf + delta) / (af + cf - delta));
if (ratio < aspect_ratio_inv || ratio > params.aspect_ratio)
{
ccv_contour_free(contour);
continue;
}
double mean = 0;
for (j = 0; j < contour->size; j++)
{
ccv_point_t* point = (ccv_point_t*)ccv_array_get(contour->set, j);
mean += buffer[j] = swt->data.i32[point->x + point->y * swt->cols];
}
mean = mean / contour->size;
double variance = 0;
for (j = 0; j < contour->size; j++)
variance += (mean - buffer[j]) * (mean - buffer[j]);
variance = variance / contour->size;
ccv_letter_t letter;
letter.std = sqrt(variance);
letter.mean = mean;
letter.thickness = _ccv_swt_median(buffer, 0, contour->size - 1);
letter.rect = contour->rect;
letter.center.x = letter.rect.x + letter.rect.width / 2;
letter.center.y = letter.rect.y + letter.rect.height / 2;
letter.intensity = 0;
letter.contour = contour;
ccv_array_push(letters, &letter);
}
ccv_array_free(contours);
memset(buffer, 0, sizeof(int) * swt->rows * swt->cols);
ccv_array_t* new_letters = ccv_array_new(sizeof(ccv_letter_t), 5, 0);
for (i = 0; i < letters->rnum; i++)
{
ccv_letter_t* letter = (ccv_letter_t*)ccv_array_get(letters, i);
for (j = 0; j < letter->contour->size; j++)
{
ccv_point_t* point = (ccv_point_t*)ccv_array_get(letter->contour->set, j);
buffer[point->x + point->y * swt->cols] = i + 1;
}
}
// filter out letters that intersects more than 2 other letters
int* another = params.letter_occlude_thresh ? (int*)alloca(sizeof(int) * params.letter_occlude_thresh) : 0;
for (i = 0; i < letters->rnum; i++)
{
ccv_letter_t* letter = (ccv_letter_t*)ccv_array_get(letters, i);
if (letter->std > letter->mean * params.std_ratio)
{
ccv_contour_free(letter->contour);
continue;
}
int more = 0;
if (another)
{
// one letter cannot occlude with more than params.letter_occlude_thresh other letters
memset(another, 0, sizeof(int) * params.letter_occlude_thresh);
for (x = letter->rect.x; x < letter->rect.x + letter->rect.width; x++)
{
for (y = letter->rect.y; y < letter->rect.y + letter->rect.height; y++)
{
int group = buffer[x + swt->cols * y];
if (group && group != i + 1)
{
more = 1;
for (j = 0; j < params.letter_occlude_thresh; j++)
if (!another[j] || another[j] == group)
{
another[j] = group;
more = 0;
break;
}
if (more)
break;
}
}
if (more)
break;
}
}
if (more)
{
ccv_contour_free(letter->contour);
continue;
}
for (j = 0; j < letter->contour->set->rnum; j++)
{
ccv_point_t* point = (ccv_point_t*)ccv_array_get(letter->contour->set, j);
letter->intensity += a->data.u8[point->x + point->y * a->step];
}
letter->intensity /= letter->contour->size;
ccv_contour_free(letter->contour);
letter->contour = 0;
ccv_array_push(new_letters, letter);
}
ccv_array_free(letters);
ccfree(buffer);
return new_letters;
}
typedef struct {
ccv_letter_t* left;
ccv_letter_t* right;
int dx;
int dy;
} ccv_letter_pair_t;
typedef struct {
ccv_rect_t rect;
int neighbors;
ccv_letter_t** letters;
} ccv_textline_t;
static int _ccv_in_textline(const void* a, const void* b, void* data)
{
ccv_letter_pair_t* pair1 = (ccv_letter_pair_t*)a;
ccv_letter_pair_t* pair2 = (ccv_letter_pair_t*)b;
if (pair1->left == pair2->left || pair1->right == pair2->right)
{
int tn = pair1->dy * pair2->dx - pair1->dx * pair2->dy;
int td = pair1->dx * pair2->dx + pair1->dy * pair2->dy;
// share the same end, opposite direction
if (tn * 7 < -td * 4 && tn * 7 > td * 4)
return 1;
} else if (pair1->left == pair2->right || pair1->right == pair2->left) {
int tn = pair1->dy * pair2->dx - pair1->dx * pair2->dy;
int td = pair1->dx * pair2->dx + pair1->dy * pair2->dy;
// share the other end, same direction
if (tn * 7 < td * 4 && tn * 7 > -td * 4)
return 1;
}
return 0;
}
static void _ccv_swt_add_letter(ccv_textline_t* textline, ccv_letter_t* letter)
{
if (textline->neighbors == 0)
{
textline->rect = letter->rect;
textline->neighbors = 1;
textline->letters = (ccv_letter_t**)ccmalloc(sizeof(ccv_letter_t*) * textline->neighbors);
textline->letters[0] = letter;
} else {
int i, flag = 0;
for (i = 0; i < textline->neighbors; i++)
if (textline->letters[i] == letter)
{
flag = 1;
break;
}
if (flag)
return;
if (letter->rect.x < textline->rect.x)
{
textline->rect.width += textline->rect.x - letter->rect.x;
textline->rect.x = letter->rect.x;
}
if (letter->rect.x + letter->rect.width > textline->rect.x + textline->rect.width)
textline->rect.width = letter->rect.x + letter->rect.width - textline->rect.x;
if (letter->rect.y < textline->rect.y)
{
textline->rect.height += textline->rect.y - letter->rect.y;
textline->rect.y = letter->rect.y;
}
if (letter->rect.y + letter->rect.height > textline->rect.y + textline->rect.height)
textline->rect.height = letter->rect.y + letter->rect.height - textline->rect.y;
textline->neighbors++;
textline->letters = (ccv_letter_t**)ccrealloc(textline->letters, sizeof(ccv_letter_t*) * textline->neighbors);
textline->letters[textline->neighbors - 1] = letter;
}
}
static ccv_array_t* _ccv_swt_merge_textline(ccv_array_t* letters, ccv_swt_param_t params)
{
int i, j;
ccv_array_t* pairs = ccv_array_new(sizeof(ccv_letter_pair_t), letters->rnum, 0);
double thickness_ratio_inv = 1.0 / params.thickness_ratio;
double height_ratio_inv = 1.0 / params.height_ratio;
for (i = 0; i < letters->rnum - 1; i++)
{
ccv_letter_t* li = (ccv_letter_t*)ccv_array_get(letters, i);
for (j = i + 1; j < letters->rnum; j++)
{
ccv_letter_t* lj = (ccv_letter_t*)ccv_array_get(letters, j);
double ratio = (double)li->thickness / lj->thickness;
if (ratio > params.thickness_ratio || ratio < thickness_ratio_inv)
continue;
ratio = (double)li->rect.height / lj->rect.height;
if (ratio > params.height_ratio || ratio < height_ratio_inv)
continue;
if (abs(li->intensity - lj->intensity) > params.intensity_thresh)
continue;
int dx = li->rect.x - lj->rect.x + (li->rect.width - lj->rect.width) / 2;
int dy = li->rect.y - lj->rect.y + (li->rect.height - lj->rect.height) / 2;
if (abs(dx) > params.distance_ratio * ccv_max(li->rect.width, lj->rect.width))
continue;
int oy = ccv_min(li->rect.y + li->rect.height, lj->rect.y + lj->rect.height) - ccv_max(li->rect.y, lj->rect.y);
if (oy * params.intersect_ratio < ccv_min(li->rect.height, lj->rect.height))
continue;
ccv_letter_pair_t pair = { .left = li, .right = lj, .dx = dx, .dy = dy };
ccv_array_push(pairs, &pair);
}
}
ccv_array_t* idx = 0;
int nchains = ccv_array_group(pairs, &idx, _ccv_in_textline, 0);
ccv_textline_t* chain = (ccv_textline_t*)ccmalloc(nchains * sizeof(ccv_textline_t));
for (i = 0; i < nchains; i++)
chain[i].neighbors = 0;
for (i = 0; i < pairs->rnum; i++)
{
j = *(int*)ccv_array_get(idx, i);
_ccv_swt_add_letter(chain + j,((ccv_letter_pair_t*)ccv_array_get(pairs, i))->left);
_ccv_swt_add_letter(chain + j, ((ccv_letter_pair_t*)ccv_array_get(pairs, i))->right);
}
ccv_array_free(idx);
ccv_array_free(pairs);
ccv_array_t* regions = ccv_array_new(sizeof(ccv_textline_t), 5, 0);
for (i = 0; i < nchains; i++)
if (chain[i].neighbors >= params.letter_thresh && chain[i].rect.width > chain[i].rect.height * params.elongate_ratio)
ccv_array_push(regions, chain + i);
else if (chain[i].neighbors > 0)
ccfree(chain[i].letters);
ccfree(chain);
return regions;
}
#define less_than(a, b, aux) ((a)->center.x < (b)->center.x)
static CCV_IMPLEMENT_QSORT(_ccv_sort_letters, ccv_letter_t*, less_than)
#undef less_than
static ccv_array_t* _ccv_swt_break_words(ccv_array_t* textline, ccv_swt_param_t params)
{
int i, j, n = 0;
for (i = 0; i < textline->rnum; i++)
{
ccv_textline_t* t = (ccv_textline_t*)ccv_array_get(textline, i);
if (t->neighbors - 1 > n)
n = t->neighbors - 1;
}
assert(n > 0);
int* buffer = (int*)alloca(n * sizeof(int));
ccv_array_t* words = ccv_array_new(sizeof(ccv_rect_t), textline->rnum, 0);
for (i = 0; i < textline->rnum; i++)
{
ccv_textline_t* t = (ccv_textline_t*)ccv_array_get(textline, i);
_ccv_sort_letters(t->letters, t->neighbors, 0);
int range = 0;
double mean = 0;
for (j = 0; j < t->neighbors - 1; j++)
{
buffer[j] = ccv_max(0, t->letters[j + 1]->rect.x - (t->letters[j]->rect.x + t->letters[j]->rect.width));
if (buffer[j] >= range)
range = buffer[j] + 1;
mean += buffer[j];
}
ccv_dense_matrix_t otsu = ccv_dense_matrix(1, t->neighbors - 1, CCV_32S | CCV_C1, buffer, 0);
double var;
int threshold = ccv_otsu(&otsu, &var, range);
mean = mean / (t->neighbors - 1);
if (sqrt(var) > mean * params.breakdown_ratio)
{
ccv_textline_t nt = { .neighbors = 0, .letters = 0 };
_ccv_swt_add_letter(&nt, t->letters[0]);
for (j = 0; j < t->neighbors - 1; j++)
{
if (buffer[j] > threshold)
{
ccv_array_push(words, &nt.rect);
if (nt.letters)
ccfree(nt.letters);
nt.letters = 0;
nt.neighbors = 0;
}
_ccv_swt_add_letter(&nt, t->letters[j + 1]);
}
ccv_array_push(words, &nt.rect);
if (nt.letters)
ccfree(nt.letters);
} else {
ccv_array_push(words, &(t->rect));
}
}
return words;
}
static int _ccv_is_same_textline(const void* a, const void* b, void* data)
{
ccv_textline_t* t1 = (ccv_textline_t*)a;
ccv_textline_t* t2 = (ccv_textline_t*)b;
int width = ccv_min(t1->rect.x + t1->rect.width, t2->rect.x + t2->rect.width) - ccv_max(t1->rect.x, t2->rect.x);
int height = ccv_min(t1->rect.y + t1->rect.height, t2->rect.y + t2->rect.height) - ccv_max(t1->rect.y, t2->rect.y);
/* overlapped 10% */
double* thresh = (double*)data;
return (width > 0 && height > 0 &&
width * height > thresh[0] * ccv_max(t1->rect.width * t1->rect.height, t2->rect.width * t2->rect.height) &&
width * height > thresh[1] * ccv_min(t1->rect.width * t1->rect.height, t2->rect.width * t2->rect.height));
}
ccv_array_t* ccv_swt_detect_words(ccv_dense_matrix_t* a, ccv_swt_param_t params)
{
int hr = a->rows * 2 / (params.min_height + params.max_height);
int wr = a->cols * 2 / (params.min_height + params.max_height);
double scale = pow(2., 1. / (params.interval + 1.));
int next = params.interval + 1;
int scale_upto = params.scale_invariant ? (int)(log((double)ccv_min(hr, wr)) / log(scale)) : 1;
int i, k;
ccv_array_t* all_words = params.scale_invariant ? ccv_array_new(sizeof(ccv_rect_t), 2, 0) : 0;
ccv_dense_matrix_t* phx = a;
ccv_dense_matrix_t* pyr = a;
double cscale = 1.0;
for (k = 0; k < scale_upto; k++)
{
// create down-sampled image on-demand because swt itself is very memory intensive
if (k % next)
{
pyr = 0;
int j = k % next;
ccv_resample(phx, &pyr, 0, (int)(phx->rows / pow(scale, j)), (int)(phx->cols / pow(scale, j)), CCV_INTER_AREA);
} else if (k > 0) {
ccv_dense_matrix_t* pha = phx;
phx = 0;
ccv_sample_down(pha, &phx, 0, 0, 0);
if (pha != a)
ccv_matrix_free(pha);
pyr = phx;
}
ccv_dense_matrix_t* swt = 0;
params.direction = CCV_DARK_TO_BRIGHT;
ccv_swt(pyr, &swt, 0, params);
/* perform connected component analysis */
ccv_array_t* lettersB = _ccv_swt_connected_letters(pyr, swt, params);
ccv_matrix_free(swt);
ccv_array_t* textline = _ccv_swt_merge_textline(lettersB, params);
swt = 0;
params.direction = CCV_BRIGHT_TO_DARK;
ccv_swt(pyr, &swt, 0, params);
ccv_array_t* lettersF = _ccv_swt_connected_letters(pyr, swt, params);
ccv_matrix_free(swt);
if (pyr != phx)
ccv_matrix_free(pyr);
ccv_array_t* textline2 = _ccv_swt_merge_textline(lettersF, params);
for (i = 0; i < textline2->rnum; i++)
ccv_array_push(textline, ccv_array_get(textline2, i));
ccv_array_free(textline2);
ccv_array_t* idx = 0;
int ntl = ccv_array_group(textline, &idx, _ccv_is_same_textline, params.same_word_thresh);
ccv_array_t* words;
if (params.breakdown && ntl > 0)
{
textline2 = ccv_array_new(sizeof(ccv_textline_t), ntl, 0);
ccv_array_zero(textline2);
textline2->rnum = ntl;
for (i = 0; i < textline->rnum; i++)
{
ccv_textline_t* r = (ccv_textline_t*)ccv_array_get(textline, i);
int k = *(int*)ccv_array_get(idx, i);
ccv_textline_t* r2 = (ccv_textline_t*)ccv_array_get(textline2, k);
if (r2->rect.width < r->rect.width)
{
if (r2->letters)
ccfree(r2->letters);
*r2 = *r;
} else if (r->letters) {
ccfree(r->letters);
}
}
ccv_array_free(idx);
ccv_array_free(textline);
words = _ccv_swt_break_words(textline2, params);
for (i = 0; i < textline2->rnum; i++)
ccfree(((ccv_textline_t*)ccv_array_get(textline2, i))->letters);
ccv_array_free(textline2);
ccv_array_free(lettersB);
ccv_array_free(lettersF);
} else {
ccv_array_free(lettersB);
ccv_array_free(lettersF);
words = ccv_array_new(sizeof(ccv_rect_t), ntl, 0);
ccv_array_zero(words);
words->rnum = ntl;
for (i = 0; i < textline->rnum; i++)
{
ccv_textline_t* r = (ccv_textline_t*)ccv_array_get(textline, i);
if (r->letters)
ccfree(r->letters);
int k = *(int*)ccv_array_get(idx, i);
ccv_rect_t* r2 = (ccv_rect_t*)ccv_array_get(words, k);
if (r2->width * r2->height < r->rect.width * r->rect.height)
*r2 = r->rect;
}
ccv_array_free(idx);
ccv_array_free(textline);
}
if (params.scale_invariant)
{
for (i = 0; i < words->rnum; i++)
{
ccv_rect_t* rect = (ccv_rect_t*)ccv_array_get(words, i);
rect->x = (int)(rect->x * cscale + 0.5);
rect->y = (int)(rect->y * cscale + 0.5);
rect->width = (int)(rect->width * cscale + 0.5);
rect->height = (int)(rect->height * cscale + 0.5);
ccv_array_push(all_words, rect);
}
ccv_array_free(words);
cscale *= scale;
} else
all_words = words;
}
if (params.scale_invariant && params.min_neighbors)
{
assert(all_words);
// de-dup logic, similar to what BBF / DPM have
ccv_array_t* idx = 0;
int ntl = ccv_array_group(all_words, &idx, _ccv_is_same_textline, params.same_word_thresh);
ccv_array_t* new_words = ccv_array_new(sizeof(ccv_comp_t), ntl, 0);
ccv_array_zero(new_words);
new_words->rnum = ntl;
for (i = 0; i < all_words->rnum; i++)
{
ccv_rect_t* r1 = (ccv_rect_t*)ccv_array_get(all_words, i);
int k = *(int*)ccv_array_get(idx, i);
ccv_comp_t* r2 = (ccv_comp_t*)ccv_array_get(new_words, k);
if (r2->neighbors)
{
++r2->neighbors;
// simply pick the biggest
if (r1->width * r1->height > r2->rect.width * r2->rect.height)
r2->rect = *r1;
} else {
r2->rect = *r1;
r2->neighbors = 1;
}
}
ccv_array_free(idx);
ccv_array_free(all_words);
if (params.min_neighbors > 1)
{
// filter out min_neighbors
all_words = ccv_array_new(sizeof(ccv_comp_t), new_words->rnum / 2, 0);
for (i = 0; i < new_words->rnum; i++)
{
ccv_comp_t* comp = (ccv_comp_t*)ccv_array_get(new_words, i);
int n = comp->neighbors;
if (n >= params.min_neighbors)
ccv_array_push(all_words, comp);
}
ccv_array_free(new_words);
} else
// just copy the pointer for min_neighbors == 1
all_words = new_words;
}
if (phx != a)
ccv_matrix_free(phx);
return all_words;
}