1 // Copyright (c) 2013 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "chrome/browser/thumbnails/content_analysis.h" 6 7 #include <algorithm> 8 #include <cmath> 9 #include <deque> 10 #include <functional> 11 #include <limits> 12 #include <numeric> 13 #include <vector> 14 15 #include "base/logging.h" 16 #include "skia/ext/convolver.h" 17 #include "skia/ext/recursive_gaussian_convolution.h" 18 #include "third_party/skia/include/core/SkBitmap.h" 19 #include "third_party/skia/include/core/SkSize.h" 20 #include "ui/gfx/color_analysis.h" 21 22 namespace { 23 24 const float kSigmaThresholdForRecursive = 1.5f; 25 const float kAspectRatioToleranceFactor = 1.02f; 26 27 template<class InputIterator, class OutputIterator, class Compare> 28 void SlidingWindowMinMax(InputIterator first, 29 InputIterator last, 30 OutputIterator output, 31 int window_size, 32 Compare cmp) { 33 typedef std::deque< 34 std::pair<typename std::iterator_traits<InputIterator>::value_type, int> > 35 deque_type; 36 deque_type slider; 37 int front_tail_length = window_size / 2; 38 int i = 0; 39 DCHECK_LT(front_tail_length, last - first); 40 // This min-max filter functions the way image filters do. The min/max we 41 // compute is placed in the center of the window. Thus, first we need to 42 // 'pre-load' the window with the slider with right-tail of the filter. 43 for (; first < last && i < front_tail_length; ++i, ++first) 44 slider.push_back(std::make_pair(*first, i)); 45 46 for (; first < last; ++i, ++first, ++output) { 47 while (!slider.empty() && !cmp(slider.back().first, *first)) 48 slider.pop_back(); 49 slider.push_back(std::make_pair(*first, i)); 50 51 while (slider.front().second <= i - window_size) 52 slider.pop_front(); 53 *output = slider.front().first; 54 } 55 56 // Now at the tail-end we will simply need to use whatever value is left of 57 // the filter to compute the remaining front_tail_length taps in the output. 58 59 // If input shorter than window, remainder length needs to be adjusted. 60 front_tail_length = std::min(front_tail_length, i); 61 for (; front_tail_length >= 0; --front_tail_length, ++i) { 62 while (slider.front().second <= i - window_size) 63 slider.pop_front(); 64 *output = slider.front().first; 65 } 66 } 67 68 size_t FindOtsuThresholdingIndex(const std::vector<int>& histogram) { 69 // Otsu's method seeks to maximize variance between two classes of pixels 70 // correspondng to valleys and peaks of the profile. 71 double w1 = histogram[0]; // Total weight of the first class. 72 double t1 = 0.5 * w1; 73 double w2 = 0.0; 74 double t2 = 0.0; 75 for (size_t i = 1; i < histogram.size(); ++i) { 76 w2 += histogram[i]; 77 t2 += (0.5 + i) * histogram[i]; 78 } 79 80 size_t max_index = 0; 81 double m1 = t1 / w1; 82 double m2 = t2 / w2; 83 double max_variance_score = w1 * w2 * (m1 - m2) * (m1 - m2); 84 // Iterate through all possible ways of splitting the histogram. 85 for (size_t i = 1; i < histogram.size() - 1; i++) { 86 double bin_volume = (0.5 + i) * histogram[i]; 87 w1 += histogram[i]; 88 w2 -= histogram[i]; 89 t2 -= bin_volume; 90 t1 += bin_volume; 91 m1 = t1 / w1; 92 m2 = t2 / w2; 93 double variance_score = w1 * w2 * (m1 - m2) * (m1 - m2); 94 if (variance_score >= max_variance_score) { 95 max_variance_score = variance_score; 96 max_index = i; 97 } 98 } 99 100 return max_index; 101 } 102 103 bool ComputeScaledHistogram(const std::vector<float>& source, 104 std::vector<int>* histogram, 105 std::pair<float, float>* minmax) { 106 DCHECK(histogram); 107 DCHECK(minmax); 108 histogram->clear(); 109 histogram->resize(256); 110 float value_min = std::numeric_limits<float>::max(); 111 float value_max = 0.0f; 112 113 std::vector<float>::const_iterator it; 114 for (it = source.begin(); it < source.end(); ++it) { 115 value_min = std::min(value_min, *it); 116 value_max = std::max(value_max, *it); 117 } 118 119 *minmax = std::make_pair(value_min, value_max); 120 121 if (value_max - value_min <= std::numeric_limits<float>::epsilon() * 100.0f) { 122 // Scaling won't work and there is nothing really to segment anyway. 123 return false; 124 } 125 126 float value_span = value_max - value_min; 127 float scale = 255.0f / value_span; 128 for (it = source.begin(); it < source.end(); ++it) { 129 float scaled_value = (*it - value_min) * scale; 130 (*histogram)[static_cast<int>(scaled_value)] += 1; 131 } 132 return true; 133 } 134 135 void ConstrainedProfileThresholding(const std::vector<float>& profile, 136 const std::vector<int>& histogram, 137 int current_clip_index, 138 float current_threshold, 139 const std::pair<float, float>& range, 140 int size_for_threshold, 141 int target_size, 142 std::vector<bool>* result) { 143 DCHECK(!profile.empty()); 144 DCHECK_EQ(histogram.size(), 256U); 145 DCHECK(result); 146 147 // A subroutine performing thresholding on the |profile|. 148 if (size_for_threshold != target_size) { 149 // Find a cut-off point (on the histogram) closest to the desired size. 150 int candidate_size = profile.size(); 151 int candidate_clip_index = 0; 152 for (std::vector<int>::const_iterator it = histogram.begin(); 153 it != histogram.end(); ++it, ++candidate_clip_index) { 154 if (std::abs(candidate_size - target_size) < 155 std::abs(candidate_size - *it - target_size)) { 156 break; 157 } 158 candidate_size -= *it; 159 } 160 161 if (std::abs(candidate_size - target_size) < 162 std::abs(candidate_size -size_for_threshold)) { 163 current_clip_index = candidate_clip_index; 164 current_threshold = (range.second - range.first) * 165 current_clip_index / 255.0f + range.first; 166 // Recount, rather than assume. One-offs due to rounding can be very 167 // harmful when eroding / dilating the result. 168 size_for_threshold = std::count_if( 169 profile.begin(), profile.end(), 170 std::bind2nd(std::greater<float>(), current_threshold)); 171 } 172 } 173 174 result->resize(profile.size()); 175 for (size_t i = 0; i < profile.size(); ++i) 176 (*result)[i] = profile[i] > current_threshold; 177 178 while (size_for_threshold > target_size) { 179 // If the current size is larger than target size, erode exactly as needed. 180 std::vector<bool>::iterator mod_it = result->begin(); 181 std::vector<bool>::const_iterator lead_it = result->begin(); 182 bool prev_value = true; 183 for (++lead_it; 184 lead_it < result->end() && size_for_threshold > target_size; 185 ++lead_it, ++mod_it) { 186 bool value = *mod_it; 187 // If any neighbour is false, switch the element off. 188 if (!prev_value || !*lead_it) { 189 *mod_it = false; 190 --size_for_threshold; 191 } 192 prev_value = value; 193 } 194 195 if (lead_it == result->end() && !prev_value) { 196 *mod_it = false; 197 --size_for_threshold; 198 } 199 } 200 201 while (size_for_threshold < target_size) { 202 std::vector<bool>::iterator mod_it = result->begin(); 203 std::vector<bool>::const_iterator lead_it = result->begin(); 204 bool prev_value = false; 205 for (++lead_it; 206 lead_it < result->end() && size_for_threshold < target_size; 207 ++lead_it, ++mod_it) { 208 bool value = *mod_it; 209 // If any neighbour is false, switch the element off. 210 if (!prev_value || !*lead_it) { 211 *mod_it = true; 212 ++size_for_threshold; 213 } 214 prev_value = value; 215 } 216 217 if (lead_it == result->end() && !prev_value) { 218 *mod_it = true; 219 ++size_for_threshold; 220 } 221 } 222 } 223 224 } // namespace 225 226 namespace thumbnailing_utils { 227 228 void ApplyGaussianGradientMagnitudeFilter(SkBitmap* input_bitmap, 229 float kernel_sigma) { 230 // The purpose of this function is to highlight salient 231 // (attention-attracting?) features of the image for use in image 232 // retargeting. 233 SkAutoLockPixels source_lock(*input_bitmap); 234 DCHECK(input_bitmap); 235 DCHECK(input_bitmap->getPixels()); 236 DCHECK_EQ(kAlpha_8_SkColorType, input_bitmap->colorType()); 237 238 // To perform computations we will need one intermediate buffer. It can 239 // very well be just another bitmap. 240 const SkISize image_size = SkISize::Make(input_bitmap->width(), 241 input_bitmap->height()); 242 SkBitmap intermediate; 243 intermediate.allocPixels(input_bitmap->info().makeWH(image_size.width(), 244 image_size.height())); 245 246 SkBitmap intermediate2; 247 intermediate2.allocPixels(input_bitmap->info().makeWH(image_size.width(), 248 image_size.height())); 249 250 if (kernel_sigma <= kSigmaThresholdForRecursive) { 251 // For small kernels classic implementation is faster. 252 skia::ConvolutionFilter1D smoothing_filter; 253 skia::SetUpGaussianConvolutionKernel( 254 &smoothing_filter, kernel_sigma, false); 255 skia::SingleChannelConvolveX1D( 256 input_bitmap->getAddr8(0, 0), 257 static_cast<int>(input_bitmap->rowBytes()), 258 0, input_bitmap->bytesPerPixel(), 259 smoothing_filter, 260 image_size, 261 intermediate.getAddr8(0, 0), 262 static_cast<int>(intermediate.rowBytes()), 263 0, intermediate.bytesPerPixel(), false); 264 skia::SingleChannelConvolveY1D( 265 intermediate.getAddr8(0, 0), 266 static_cast<int>(intermediate.rowBytes()), 267 0, intermediate.bytesPerPixel(), 268 smoothing_filter, 269 image_size, 270 input_bitmap->getAddr8(0, 0), 271 static_cast<int>(input_bitmap->rowBytes()), 272 0, input_bitmap->bytesPerPixel(), false); 273 274 skia::ConvolutionFilter1D gradient_filter; 275 skia::SetUpGaussianConvolutionKernel(&gradient_filter, kernel_sigma, true); 276 skia::SingleChannelConvolveX1D( 277 input_bitmap->getAddr8(0, 0), 278 static_cast<int>(input_bitmap->rowBytes()), 279 0, input_bitmap->bytesPerPixel(), 280 gradient_filter, 281 image_size, 282 intermediate.getAddr8(0, 0), 283 static_cast<int>(intermediate.rowBytes()), 284 0, intermediate.bytesPerPixel(), true); 285 skia::SingleChannelConvolveY1D( 286 input_bitmap->getAddr8(0, 0), 287 static_cast<int>(input_bitmap->rowBytes()), 288 0, input_bitmap->bytesPerPixel(), 289 gradient_filter, 290 image_size, 291 intermediate2.getAddr8(0, 0), 292 static_cast<int>(intermediate2.rowBytes()), 293 0, intermediate2.bytesPerPixel(), true); 294 } else { 295 // For larger sigma values use the recursive filter. 296 skia::RecursiveFilter smoothing_filter(kernel_sigma, 297 skia::RecursiveFilter::FUNCTION); 298 skia::SingleChannelRecursiveGaussianX( 299 input_bitmap->getAddr8(0, 0), 300 static_cast<int>(input_bitmap->rowBytes()), 301 0, input_bitmap->bytesPerPixel(), 302 smoothing_filter, 303 image_size, 304 intermediate.getAddr8(0, 0), 305 static_cast<int>(intermediate.rowBytes()), 306 0, intermediate.bytesPerPixel(), false); 307 unsigned char smoothed_max = skia::SingleChannelRecursiveGaussianY( 308 intermediate.getAddr8(0, 0), 309 static_cast<int>(intermediate.rowBytes()), 310 0, intermediate.bytesPerPixel(), 311 smoothing_filter, 312 image_size, 313 input_bitmap->getAddr8(0, 0), 314 static_cast<int>(input_bitmap->rowBytes()), 315 0, input_bitmap->bytesPerPixel(), false); 316 if (smoothed_max < 127) { 317 int bit_shift = 8 - static_cast<int>( 318 std::log10(static_cast<float>(smoothed_max)) / std::log10(2.0f)); 319 for (int r = 0; r < image_size.height(); ++r) { 320 uint8* row = input_bitmap->getAddr8(0, r); 321 for (int c = 0; c < image_size.width(); ++c, ++row) { 322 *row <<= bit_shift; 323 } 324 } 325 } 326 327 skia::RecursiveFilter gradient_filter( 328 kernel_sigma, skia::RecursiveFilter::FIRST_DERIVATIVE); 329 skia::SingleChannelRecursiveGaussianX( 330 input_bitmap->getAddr8(0, 0), 331 static_cast<int>(input_bitmap->rowBytes()), 332 0, input_bitmap->bytesPerPixel(), 333 gradient_filter, 334 image_size, 335 intermediate.getAddr8(0, 0), 336 static_cast<int>(intermediate.rowBytes()), 337 0, intermediate.bytesPerPixel(), true); 338 skia::SingleChannelRecursiveGaussianY( 339 input_bitmap->getAddr8(0, 0), 340 static_cast<int>(input_bitmap->rowBytes()), 341 0, input_bitmap->bytesPerPixel(), 342 gradient_filter, 343 image_size, 344 intermediate2.getAddr8(0, 0), 345 static_cast<int>(intermediate2.rowBytes()), 346 0, intermediate2.bytesPerPixel(), true); 347 } 348 349 unsigned grad_max = 0; 350 for (int r = 0; r < image_size.height(); ++r) { 351 const uint8* grad_x_row = intermediate.getAddr8(0, r); 352 const uint8* grad_y_row = intermediate2.getAddr8(0, r); 353 for (int c = 0; c < image_size.width(); ++c) { 354 unsigned grad_x = grad_x_row[c]; 355 unsigned grad_y = grad_y_row[c]; 356 grad_max = std::max(grad_max, grad_x * grad_x + grad_y * grad_y); 357 } 358 } 359 360 int bit_shift = 0; 361 if (grad_max > 255) 362 bit_shift = static_cast<int>( 363 std::log10(static_cast<float>(grad_max)) / std::log10(2.0f)) - 7; 364 for (int r = 0; r < image_size.height(); ++r) { 365 const uint8* grad_x_row = intermediate.getAddr8(0, r); 366 const uint8* grad_y_row = intermediate2.getAddr8(0, r); 367 uint8* target_row = input_bitmap->getAddr8(0, r); 368 for (int c = 0; c < image_size.width(); ++c) { 369 unsigned grad_x = grad_x_row[c]; 370 unsigned grad_y = grad_y_row[c]; 371 target_row[c] = (grad_x * grad_x + grad_y * grad_y) >> bit_shift; 372 } 373 } 374 } 375 376 void ExtractImageProfileInformation(const SkBitmap& input_bitmap, 377 const gfx::Rect& area, 378 const gfx::Size& target_size, 379 bool apply_log, 380 std::vector<float>* rows, 381 std::vector<float>* columns) { 382 SkAutoLockPixels source_lock(input_bitmap); 383 DCHECK(rows); 384 DCHECK(columns); 385 DCHECK(input_bitmap.getPixels()); 386 DCHECK_EQ(kAlpha_8_SkColorType, input_bitmap.colorType()); 387 DCHECK_GE(area.x(), 0); 388 DCHECK_GE(area.y(), 0); 389 DCHECK_LE(area.right(), input_bitmap.width()); 390 DCHECK_LE(area.bottom(), input_bitmap.height()); 391 392 // Make sure rows and columns are allocated and initialized to 0. 393 rows->clear(); 394 columns->clear(); 395 rows->resize(area.height(), 0); 396 columns->resize(area.width(), 0); 397 398 for (int r = 0; r < area.height(); ++r) { 399 // Points to the first byte of the row in the rectangle. 400 const uint8* image_row = input_bitmap.getAddr8(area.x(), r + area.y()); 401 unsigned row_sum = 0; 402 for (int c = 0; c < area.width(); ++c, ++image_row) { 403 row_sum += *image_row; 404 (*columns)[c] += *image_row; 405 } 406 (*rows)[r] = row_sum; 407 } 408 409 if (apply_log) { 410 // Generally for processing we will need to take logarithm of this data. 411 // The option not to apply it is left principally as a test seam. 412 std::vector<float>::iterator it; 413 for (it = columns->begin(); it < columns->end(); ++it) 414 *it = std::log(1.0f + *it); 415 416 for (it = rows->begin(); it < rows->end(); ++it) 417 *it = std::log(1.0f + *it); 418 } 419 420 if (!target_size.IsEmpty()) { 421 // If the target size is given, profiles should be further processed through 422 // morphological closing. The idea is to close valleys smaller than what 423 // can be seen after scaling down to avoid deforming noticable features 424 // when profiles are used. 425 // Morphological closing is defined as dilation followed by errosion. In 426 // normal-speak: sliding-window maximum followed by minimum. 427 int column_window_size = 1 + 2 * 428 static_cast<int>(0.5f * area.width() / target_size.width() + 0.5f); 429 int row_window_size = 1 + 2 * 430 static_cast<int>(0.5f * area.height() / target_size.height() + 0.5f); 431 432 // Dilate and erode each profile with the given window size. 433 if (column_window_size >= 3) { 434 SlidingWindowMinMax(columns->begin(), 435 columns->end(), 436 columns->begin(), 437 column_window_size, 438 std::greater<float>()); 439 SlidingWindowMinMax(columns->begin(), 440 columns->end(), 441 columns->begin(), 442 column_window_size, 443 std::less<float>()); 444 } 445 446 if (row_window_size >= 3) { 447 SlidingWindowMinMax(rows->begin(), 448 rows->end(), 449 rows->begin(), 450 row_window_size, 451 std::greater<float>()); 452 SlidingWindowMinMax(rows->begin(), 453 rows->end(), 454 rows->begin(), 455 row_window_size, 456 std::less<float>()); 457 } 458 } 459 } 460 461 float AutoSegmentPeaks(const std::vector<float>& input) { 462 // This is a thresholding operation based on Otsu's method. 463 std::vector<int> histogram; 464 std::pair<float, float> minmax; 465 if (!ComputeScaledHistogram(input, &histogram, &minmax)) 466 return minmax.first; 467 468 // max_index refers to the bin *after* which we need to split. The sought 469 // threshold is the centre of this bin, scaled back to the original range. 470 size_t max_index = FindOtsuThresholdingIndex(histogram); 471 return (minmax.second - minmax.first) * (max_index + 0.5f) / 255.0f + 472 minmax.first; 473 } 474 475 gfx::Size AdjustClippingSizeToAspectRatio(const gfx::Size& target_size, 476 const gfx::Size& image_size, 477 const gfx::Size& computed_size) { 478 DCHECK_GT(target_size.width(), 0); 479 DCHECK_GT(target_size.height(), 0); 480 // If the computed thumbnail would be too wide or to tall, we shall attempt 481 // to fix it. Generally the idea is to re-add content to the part which has 482 // been more aggressively shrunk unless there is nothing to add there or if 483 // adding there won't fix anything. Should that be the case, we will 484 // (reluctantly) take away more from the other dimension. 485 float desired_aspect = 486 static_cast<float>(target_size.width()) / target_size.height(); 487 int computed_width = std::max(computed_size.width(), target_size.width()); 488 int computed_height = std::max(computed_size.height(), target_size.height()); 489 float computed_aspect = static_cast<float>(computed_width) / computed_height; 490 float aspect_change_delta = std::abs(computed_aspect - desired_aspect); 491 float prev_aspect_change_delta = 1000.0f; 492 const float kAspectChangeEps = 0.01f; 493 const float kLargeEffect = 2.0f; 494 495 while ((prev_aspect_change_delta - aspect_change_delta > kAspectChangeEps) && 496 (computed_aspect / desired_aspect > kAspectRatioToleranceFactor || 497 desired_aspect / computed_aspect > kAspectRatioToleranceFactor)) { 498 int new_computed_width = computed_width; 499 int new_computed_height = computed_height; 500 float row_dimension_shrink = 501 static_cast<float>(image_size.height()) / computed_height; 502 float column_dimension_shrink = 503 static_cast<float>(image_size.width()) / computed_width; 504 505 if (computed_aspect / desired_aspect > kAspectRatioToleranceFactor) { 506 // Too wide. 507 if (row_dimension_shrink > column_dimension_shrink) { 508 // Bring the computed_height to the least of: 509 // (1) image height (2) the number of lines that would 510 // make up the desired aspect or (3) number of lines we would get 511 // at the same 'aggressivity' level as width or. 512 new_computed_height = std::min( 513 static_cast<int>(image_size.height()), 514 static_cast<int>(computed_width / desired_aspect + 0.5f)); 515 new_computed_height = std::min( 516 new_computed_height, 517 static_cast<int>( 518 image_size.height() / column_dimension_shrink + 0.5f)); 519 } else if (row_dimension_shrink >= kLargeEffect || 520 new_computed_width <= target_size.width()) { 521 // Even though rows were resized less, we will generally rather add than 522 // remove (or there is nothing to remove in x already). 523 new_computed_height = std::min( 524 static_cast<int>(image_size.height()), 525 static_cast<int>(computed_width / desired_aspect + 0.5f)); 526 } else { 527 // Rows were already shrunk less aggressively. This means there is 528 // simply no room left too expand. Cut columns to get the desired 529 // aspect ratio. 530 new_computed_width = desired_aspect * computed_height + 0.5f; 531 } 532 } else { 533 // Too tall. 534 if (column_dimension_shrink > row_dimension_shrink) { 535 // Columns were shrunk more aggressively. Try to relax the same way as 536 // above. 537 new_computed_width = std::min( 538 static_cast<int>(image_size.width()), 539 static_cast<int>(desired_aspect * computed_height + 0.5f)); 540 new_computed_width = std::min( 541 new_computed_width, 542 static_cast<int>( 543 image_size.width() / row_dimension_shrink + 0.5f)); 544 } else if (column_dimension_shrink >= kLargeEffect || 545 new_computed_height <= target_size.height()) { 546 new_computed_width = std::min( 547 static_cast<int>(image_size.width()), 548 static_cast<int>(desired_aspect * computed_height + 0.5f)); 549 } else { 550 new_computed_height = computed_width / desired_aspect + 0.5f; 551 } 552 } 553 554 new_computed_width = std::max(new_computed_width, target_size.width()); 555 new_computed_height = std::max(new_computed_height, target_size.height()); 556 557 // Update loop control variables. 558 float new_computed_aspect = 559 static_cast<float>(new_computed_width) / new_computed_height; 560 561 if (std::abs(new_computed_aspect - desired_aspect) > 562 std::abs(computed_aspect - desired_aspect)) { 563 // Do not take inferior results. 564 break; 565 } 566 567 computed_width = new_computed_width; 568 computed_height = new_computed_height; 569 computed_aspect = new_computed_aspect; 570 prev_aspect_change_delta = aspect_change_delta; 571 aspect_change_delta = std::abs(new_computed_aspect - desired_aspect); 572 } 573 574 return gfx::Size(computed_width, computed_height); 575 } 576 577 void ConstrainedProfileSegmentation(const std::vector<float>& row_profile, 578 const std::vector<float>& column_profile, 579 const gfx::Size& target_size, 580 std::vector<bool>* included_rows, 581 std::vector<bool>* included_columns) { 582 DCHECK(included_rows); 583 DCHECK(included_columns); 584 585 std::vector<int> histogram_rows; 586 std::pair<float, float> minmax_rows; 587 bool rows_well_behaved = ComputeScaledHistogram( 588 row_profile, &histogram_rows, &minmax_rows); 589 590 float row_threshold = minmax_rows.first; 591 size_t clip_index_rows = 0; 592 593 if (rows_well_behaved) { 594 clip_index_rows = FindOtsuThresholdingIndex(histogram_rows); 595 row_threshold = (minmax_rows.second - minmax_rows.first) * 596 (clip_index_rows + 0.5f) / 255.0f + minmax_rows.first; 597 } 598 599 std::vector<int> histogram_columns; 600 std::pair<float, float> minmax_columns; 601 bool columns_well_behaved = ComputeScaledHistogram(column_profile, 602 &histogram_columns, 603 &minmax_columns); 604 float column_threshold = minmax_columns.first; 605 size_t clip_index_columns = 0; 606 607 if (columns_well_behaved) { 608 clip_index_columns = FindOtsuThresholdingIndex(histogram_columns); 609 column_threshold = (minmax_columns.second - minmax_columns.first) * 610 (clip_index_columns + 0.5f) / 255.0f + minmax_columns.first; 611 } 612 613 int auto_segmented_width = count_if( 614 column_profile.begin(), column_profile.end(), 615 std::bind2nd(std::greater<float>(), column_threshold)); 616 int auto_segmented_height = count_if( 617 row_profile.begin(), row_profile.end(), 618 std::bind2nd(std::greater<float>(), row_threshold)); 619 620 gfx::Size computed_size = AdjustClippingSizeToAspectRatio( 621 target_size, 622 gfx::Size(column_profile.size(), row_profile.size()), 623 gfx::Size(auto_segmented_width, auto_segmented_height)); 624 625 // Apply thresholding. 626 if (rows_well_behaved) { 627 ConstrainedProfileThresholding(row_profile, 628 histogram_rows, 629 clip_index_rows, 630 row_threshold, 631 minmax_rows, 632 auto_segmented_height, 633 computed_size.height(), 634 included_rows); 635 } else { 636 // This is essentially an error condition, invoked when no segmentation was 637 // possible. This will result in applying a very low threshold and likely 638 // in producing a thumbnail which should get rejected. 639 included_rows->resize(row_profile.size()); 640 for (size_t i = 0; i < row_profile.size(); ++i) 641 (*included_rows)[i] = row_profile[i] > row_threshold; 642 } 643 644 if (columns_well_behaved) { 645 ConstrainedProfileThresholding(column_profile, 646 histogram_columns, 647 clip_index_columns, 648 column_threshold, 649 minmax_columns, 650 auto_segmented_width, 651 computed_size.width(), 652 included_columns); 653 } else { 654 included_columns->resize(column_profile.size()); 655 for (size_t i = 0; i < column_profile.size(); ++i) 656 (*included_columns)[i] = column_profile[i] > column_threshold; 657 } 658 } 659 660 SkBitmap ComputeDecimatedImage(const SkBitmap& bitmap, 661 const std::vector<bool>& rows, 662 const std::vector<bool>& columns) { 663 SkAutoLockPixels source_lock(bitmap); 664 DCHECK(bitmap.getPixels()); 665 DCHECK_GT(bitmap.bytesPerPixel(), 0); 666 DCHECK_EQ(bitmap.width(), static_cast<int>(columns.size())); 667 DCHECK_EQ(bitmap.height(), static_cast<int>(rows.size())); 668 669 unsigned target_row_count = std::count(rows.begin(), rows.end(), true); 670 unsigned target_column_count = std::count( 671 columns.begin(), columns.end(), true); 672 673 if (target_row_count == 0 || target_column_count == 0) 674 return SkBitmap(); // Not quite an error, so no DCHECK. Just return empty. 675 676 if (target_row_count == rows.size() && target_column_count == columns.size()) 677 return SkBitmap(); // Equivalent of the situation above (empty target). 678 679 // Allocate the target image. 680 SkBitmap target; 681 target.allocPixels(bitmap.info().makeWH(target_column_count, 682 target_row_count)); 683 684 int target_row = 0; 685 for (int r = 0; r < bitmap.height(); ++r) { 686 if (!rows[r]) 687 continue; // We can just skip this one. 688 uint8* src_row = 689 static_cast<uint8*>(bitmap.getPixels()) + r * bitmap.rowBytes(); 690 uint8* insertion_target = static_cast<uint8*>(target.getPixels()) + 691 target_row * target.rowBytes(); 692 int left_copy_pixel = -1; 693 for (int c = 0; c < bitmap.width(); ++c) { 694 if (left_copy_pixel < 0 && columns[c]) { 695 left_copy_pixel = c; // Next time we will start copying from here. 696 } else if (left_copy_pixel >= 0 && !columns[c]) { 697 // This closes a fragment we want to copy. We do it now. 698 size_t bytes_to_copy = (c - left_copy_pixel) * bitmap.bytesPerPixel(); 699 memcpy(insertion_target, 700 src_row + left_copy_pixel * bitmap.bytesPerPixel(), 701 bytes_to_copy); 702 left_copy_pixel = -1; 703 insertion_target += bytes_to_copy; 704 } 705 } 706 // We can still have the tail end to process here. 707 if (left_copy_pixel >= 0) { 708 size_t bytes_to_copy = 709 (bitmap.width() - left_copy_pixel) * bitmap.bytesPerPixel(); 710 memcpy(insertion_target, 711 src_row + left_copy_pixel * bitmap.bytesPerPixel(), 712 bytes_to_copy); 713 } 714 target_row++; 715 } 716 717 return target; 718 } 719 720 SkBitmap CreateRetargetedThumbnailImage( 721 const SkBitmap& source_bitmap, 722 const gfx::Size& target_size, 723 float kernel_sigma) { 724 // First thing we need for this method is to color-reduce the source_bitmap. 725 SkBitmap reduced_color; 726 reduced_color.allocPixels(SkImageInfo::MakeA8(source_bitmap.width(), 727 source_bitmap.height())); 728 729 if (!color_utils::ComputePrincipalComponentImage(source_bitmap, 730 &reduced_color)) { 731 // CCIR601 luminance conversion vector. 732 gfx::Vector3dF transform(0.299f, 0.587f, 0.114f); 733 if (!color_utils::ApplyColorReduction( 734 source_bitmap, transform, true, &reduced_color)) { 735 DLOG(WARNING) << "Failed to compute luminance image from a screenshot. " 736 << "Cannot compute retargeted thumbnail."; 737 return SkBitmap(); 738 } 739 DLOG(WARNING) << "Could not compute principal color image for a thumbnail. " 740 << "Using luminance instead."; 741 } 742 743 // Turn 'color-reduced' image into the 'energy' image. 744 ApplyGaussianGradientMagnitudeFilter(&reduced_color, kernel_sigma); 745 746 // Extract vertical and horizontal projection of image features. 747 std::vector<float> row_profile; 748 std::vector<float> column_profile; 749 ExtractImageProfileInformation(reduced_color, 750 gfx::Rect(reduced_color.width(), 751 reduced_color.height()), 752 target_size, 753 true, 754 &row_profile, 755 &column_profile); 756 757 std::vector<bool> included_rows, included_columns; 758 ConstrainedProfileSegmentation(row_profile, 759 column_profile, 760 target_size, 761 &included_rows, 762 &included_columns); 763 764 // Use the original image and computed inclusion vectors to create a resized 765 // image. 766 return ComputeDecimatedImage(source_bitmap, included_rows, included_columns); 767 } 768 769 } // thumbnailing_utils 770
