* subsampling/integral.hh: New. Compute a subsample image and an integral image at the same time. --- scribo/ChangeLog | 7 + .../{integral_single_image.hh => integral.hh} | 215 ++++++++------------ 2 files changed, 95 insertions(+), 127 deletions(-) copy scribo/subsampling/{integral_single_image.hh => integral.hh} (65%) diff --git a/scribo/ChangeLog b/scribo/ChangeLog index 94fc34a..4626c4d 100644 --- a/scribo/ChangeLog +++ b/scribo/ChangeLog @@ -1,5 +1,12 @@ 2010-02-19 Guillaume Lazzara <z@lrde.epita.fr> + Add a subsampling algorithm. + + * subsampling/integral.hh: New. Compute a subsample image and an + integral image at the same time. + +2010-02-19 Guillaume Lazzara <z@lrde.epita.fr> + Add a first draft of a text line merging algorithm. * text/merging.hh: New. diff --git a/scribo/subsampling/integral_single_image.hh b/scribo/subsampling/integral.hh similarity index 65% copy from scribo/subsampling/integral_single_image.hh copy to scribo/subsampling/integral.hh index cd25fc1..b6e97d2 100644 --- a/scribo/subsampling/integral_single_image.hh +++ b/scribo/subsampling/integral.hh @@ -97,33 +97,39 @@ namespace scribo inline mln_concrete(I) integral_3(const Image<I>& input_, - Image<J>& integral_sum_sum_2_, + Image<J>& integral_sum_, Image<J>& integral_sum_2_, const mln_domain(I)& output_domain, unsigned border_thickness) { trace::entering("subsampling::impl::integral_3"); - const unsigned scale = 3; + const unsigned + scale = 3, + area = scale * scale; const I& input = exact(input_); - J& integral_sum_sum_2 = exact(integral_sum_sum_2_); + J& integral_sum = exact(integral_sum_); + J& integral_sum_2 = exact(integral_sum_2_); mln_precondition(input.is_valid()); mln_precondition(input.domain().pmin() == literal::origin); mln_precondition(scale > 1); typedef mln_value(I) V; - typedef mln_sum(V) S; - typedef mln_value(J) V2; + typedef mln_value(J) S; typedef mln_site(I) P; +// mlc_is(mln_value(J), S)::check(); mln_concrete(I) sub(output_domain, border_thickness); V* p_sub = sub.buffer(); - integral_sum_sum_2.init_(output_domain, border_thickness); - V2* p_integ = integral_sum_sum_2.buffer(); + integral_sum.init_(output_domain, border_thickness); + S* p_isum = integral_sum.buffer(); - const int up = sub.delta_index(dpoint2d(-1, 0)); + integral_sum_2.init_(output_domain, border_thickness); + S* p_isum_2 = integral_sum_2.buffer(); + + const unsigned up = sub.delta_index(dpoint2d(-1, 0)); const unsigned nrows = 3 * output_domain.nrows(); const unsigned ncols = 3 * output_domain.ncols(); @@ -133,7 +139,8 @@ namespace scribo unsigned b_offset = sub.delta_index(dpoint2d(border_thickness, border_thickness)); p_sub += b_offset; - p_integ += b_offset; + p_isum += b_offset; + p_isum_2 += b_offset; { S h_sum = 0, h_sum_2 = 0; const V* ptr1 = & input.at_(row, 0); @@ -141,69 +148,65 @@ namespace scribo const V* ptr3 = & input.at_(row + 2, 0); for (unsigned col = 0; col < ncols; col += scale) { - V v11 = *ptr1, v12 = *(ptr1 + 1), v13 = *(ptr1 + 2), - v21 = *ptr2, v22 = *(ptr2 + 1), v23 = *(ptr2 + 2), - v31 = *ptr3, v32 = *(ptr3 + 1), v33 = *(ptr3 + 2); + S sum; + sum = *ptr1 + *(ptr1 + 1) + *(ptr1 + 2); + sum += *ptr2 + *(ptr2 + 1) + *(ptr2 + 2); + sum += *ptr3 + *(ptr3 + 1) + *(ptr3 + 2); ptr1 += 3; ptr2 += 3; ptr3 += 3; - S local_sum = v11 + v12 + v13 - + v21 + v22 + v23 - + v31 + v32 + v33, - local_sum_2 = v11*v11 + v12*v12 + v13*v13 - + v21*v21 + v22*v22 + v23*v23 - + v31*v31 + v32*v32 + v33*v33; - *p_sub++ = local_sum / 9; - h_sum += local_sum; - h_sum_2 += local_sum_2; + *p_sub++ = sum / area; + + h_sum += sum; + h_sum_2 += sum * sum; // exception - p_integ->first() = h_sum; - p_integ->second() = h_sum_2; + *p_isum = h_sum; + *p_isum_2 = h_sum_2; - p_integ += 1; + p_isum += 1; + p_isum_2 += 1; } } unsigned b_next = 2 * border_thickness; p_sub += b_next; - p_integ += b_next; + p_isum += b_next; + p_isum_2 += b_next; for (row += scale; row < nrows; row += scale) { S h_sum = 0, h_sum_2 = 0; - const V* ptr1 = & input.at_(row, 0); + const V* ptr1 = & input.at_(row, 0); const V* ptr2 = & input.at_(row + 1, 0); const V* ptr3 = & input.at_(row + 2, 0); for (unsigned col = 0; col < ncols; col += scale) { - V v11 = *ptr1, v12 = *(ptr1 + 1), v13 = *(ptr1 + 2), - v21 = *ptr2, v22 = *(ptr2 + 1), v23 = *(ptr2 + 2), - v31 = *ptr3, v32 = *(ptr3 + 1), v33 = *(ptr3 + 2); + S sum; + sum = *ptr1 + *(ptr1 + 1) + *(ptr1 + 2); + sum += *ptr2 + *(ptr2 + 1) + *(ptr2 + 2); + sum += *ptr3 + *(ptr3 + 1) + *(ptr3 + 2); ptr1 += 3; ptr2 += 3; ptr3 += 3; - S local_sum = v11 + v12 + v13 - + v21 + v22 + v23 - + v31 + v32 + v33, - local_sum_2 = v11*v11 + v12*v12 + v13*v13 - + v21*v21 + v22*v22 + v23*v23 - + v31*v31 + v32*v32 + v33*v33; - *p_sub++ = local_sum / 9; - h_sum += local_sum; - h_sum_2 += local_sum_2; + *p_sub++ = sum / area; + + h_sum += sum; + h_sum_2 += sum * sum; - p_integ->first() = h_sum + (p_integ + up)->first(); - p_integ->second() = h_sum_2 + (p_integ + up)->second(); + *p_isum = h_sum + *(p_isum + up); + *p_isum_2 = h_sum_2 + *(p_isum_2 + up); - p_integ += 1; + p_isum += 1; + p_isum_2 += 1; } p_sub += b_next; - p_integ += b_next; + p_isum += b_next; + p_isum_2 += b_next; } trace::exiting("subsampling::impl::integral_3"); @@ -215,44 +218,52 @@ namespace scribo inline mln_concrete(I) integral_2(const Image<I>& input_, - Image<J>& integral_sum_sum_2_, + Image<J>& integral_sum_, Image<J>& integral_sum_2_, const mln_domain(I)& output_domain, unsigned border_thickness) { trace::entering("subsampling::impl::integral_2"); - const unsigned scale = 2; + const unsigned + scale = 2, + area = scale * scale; const I& input = exact(input_); - J& integral_sum_sum_2 = exact(integral_sum_sum_2_); + J& integral_sum = exact(integral_sum_); + J& integral_sum_2 = exact(integral_sum_2_); typedef mln_value(I) V; - typedef mln_sum(V) S; + typedef mln_value(J) S; typedef mln_site(I) P; - typedef mln_value(J) V2; mlc_bool(P::dim == 2)::check(); mln_precondition(input.is_valid()); mln_precondition(input.domain().pmin() == literal::origin); mln_precondition(scale > 1); +// mlc_is(mln_value(J), S)::check(); + mln_concrete(I) sub(output_domain, border_thickness); V* p_sub = sub.buffer(); - integral_sum_sum_2.init_(output_domain, border_thickness); - V2* p_integ = integral_sum_sum_2.buffer(); + integral_sum.init_(output_domain, border_thickness); + S* p_isum = integral_sum.buffer(); - const int up = sub.delta_index(dpoint2d(-1, 0)); + integral_sum_2.init_(output_domain, border_thickness); + S* p_isum_2 = integral_sum_2.buffer(); + + const unsigned up = sub.delta_index(dpoint2d(-1, 0)); const unsigned nrows = 2 * output_domain.nrows(); const unsigned ncols = 2 * output_domain.ncols(); - extension::fill(sub, 0); + extension::fill(sub, 0); unsigned b_offset = sub.delta_index(dpoint2d(border_thickness, border_thickness)); p_sub += b_offset; - p_integ += b_offset; + p_isum += b_offset; + p_isum_2 += b_offset; unsigned row = 0; { @@ -261,47 +272,31 @@ namespace scribo const V* ptr2 = & input.at_(row + 1, 0); for (unsigned col = 0; col < ncols; col += scale) { -/* S sum; sum = *ptr1 + *(ptr1 + 1); sum += *ptr2 + *(ptr2 + 1); ptr1 += 2; ptr2 += 2; - S val = sum / area; - *p_sub++ = val; - - h_sum += val; - h_sum_2 += val * val; -*/ - - // NEW: - - V v11 = *ptr1, v12 = *(ptr1 + 1), - v21 = *ptr2, v22 = *(ptr2 + 1); - ptr1 += 2; - ptr2 += 2; - S local_sum = v11 + v12 + v21 + v22, - local_sum_2 = v11*v11 + v12*v12 + v21*v21 + v22*v22; - *p_sub++ = local_sum / 4; - h_sum += local_sum; - h_sum_2 += local_sum_2; - - // end of NEW. + *p_sub++ = sum / area; + h_sum += sum; + h_sum_2 += sum * sum; // exception - p_integ->first() = h_sum; - p_integ->second() = h_sum_2; + *p_isum = h_sum; + *p_isum_2 = h_sum_2; - p_integ += 1; + p_isum += 1; + p_isum_2 += 1; } } unsigned b_next = 2 * border_thickness; p_sub += b_next; - p_integ += b_next; + p_isum += b_next; + p_isum_2 += b_next; for (row += scale; row < nrows; row += scale) { @@ -310,61 +305,27 @@ namespace scribo const V* ptr2 = & input.at_(row + 1, 0); for (unsigned col = 0; col < ncols; col += scale) { - // NEW: - - V v11 = *ptr1, v12 = *(ptr1 + 1), - v21 = *ptr2, v22 = *(ptr2 + 1); - ptr1 += 2; - ptr2 += 2; - S local_sum = v11 + v12 + v21 + v22, - local_sum_2 = v11*v11 + v12*v12 + v21*v21 + v22*v22; - *p_sub++ = local_sum / 4; - h_sum += local_sum; - h_sum_2 += local_sum_2; - - // end of NEW. - - - /* - - // To get the strict equivalent to the integral image - // computed at working scale (scale (2)), we need the code - // below. In addition, the integral_browsing shall call - // the threshold formula with (..size..) and NOT with - // (..size * s_2..). - S sum; sum = *ptr1 + *(ptr1 + 1); sum += *ptr2 + *(ptr2 + 1); ptr1 += 2; ptr2 += 2; - S val = sum / area; - *p_sub++ = val; - h_sum += val; - h_sum_2 += val * val; - - */ + *p_sub++ = sum / area; + h_sum += sum; + h_sum_2 += sum * sum; - // Never write something like this: - // *p_sub++ = sum / area; - // h_sum += sum; - // h_sum_2 += sum * sum; - // because the product 'sum * sum' is not - // equivalent to the sum of the value^2. E.g. - // we have (v1 + v2 + v3 + v4)^2 + etc. instead - // of having the correct sum_2 being v1^2 + v2^2 etc. + *p_isum = h_sum + *(p_isum + up); + *p_isum_2 = h_sum_2 + *(p_isum_2 + up); - - p_integ->first() = h_sum + (p_integ + up)->first(); - p_integ->second() = h_sum_2 + (p_integ + up)->second(); - - p_integ += 1; + p_isum += 1; + p_isum_2 += 1; } p_sub += b_next; - p_integ += b_next; + p_isum += b_next; + p_isum_2 += b_next; } trace::exiting("subsampling::impl::integral_2"); @@ -376,16 +337,16 @@ namespace scribo inline mln_concrete(I) integral(const Image<I>& input, unsigned scale, - Image<J>& integral_sum_sum_2, + Image<J>& simple, Image<J>& squared, const mln_domain(I)& output_domain, unsigned border_thickness) { // mln_precondition(input.nrows() % scale == 0); // mln_precondition(input.ncols() % scale == 0); if (scale == 3) - return integral_3(input, integral_sum_sum_2, + return integral_3(input, simple, squared, output_domain, border_thickness); else if (scale == 2) - return integral_2(input, integral_sum_sum_2, + return integral_2(input, simple, squared, output_domain, border_thickness); else std::cerr << "NYI!" << std::endl; @@ -406,7 +367,7 @@ namespace scribo inline mln_concrete(I) integral(const Image<I>& input_, unsigned scale, - Image<J>& integral_sum_sum_2, + Image<J>& integral_sum, Image<J>& integral_sum_2, const mln_domain(I)& output_domain, unsigned border_thickness) { trace::entering("subsampling::integral"); @@ -418,7 +379,7 @@ namespace scribo mln_precondition(scale > 1); mln_concrete(I) - output = impl::integral(input, scale, integral_sum_sum_2, + output = impl::integral(input, scale, integral_sum, integral_sum_2, output_domain, border_thickness); trace::exiting("subsampling::integral"); @@ -429,7 +390,7 @@ namespace scribo inline mln_concrete(I) integral(const Image<I>& input_, unsigned scale, - Image<J>& integral_sum_sum_2) + Image<J>& integral_sum, Image<J>& integral_sum_2) { trace::entering("subsampling::integral"); @@ -442,7 +403,7 @@ namespace scribo box<mln_site(I)> b = make::box2d((input.nrows() + scale - 1) / scale, (input.ncols() + scale - 1) / scale); mln_concrete(I) output; - output = integral(input_, scale, integral_sum_sum_2, + output = integral(input_, scale, integral_sum, integral_sum_2, b, mln::border::thickness); trace::exiting("subsampling::integral"); -- 1.5.6.5