ccv_swt.c

#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;
}