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(SkBitmap::kA8_Config, input_bitmap->config()); 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.setConfig( 244 input_bitmap->config(), image_size.width(), image_size.height()); 245 intermediate.allocPixels(); 246 247 SkBitmap intermediate2; 248 intermediate2.setConfig( 249 input_bitmap->config(), image_size.width(), image_size.height()); 250 intermediate2.allocPixels(); 251 252 253 if (kernel_sigma <= kSigmaThresholdForRecursive) { 254 // For small kernels classic implementation is faster. 255 skia::ConvolutionFilter1D smoothing_filter; 256 skia::SetUpGaussianConvolutionKernel( 257 &smoothing_filter, kernel_sigma, false); 258 skia::SingleChannelConvolveX1D( 259 input_bitmap->getAddr8(0, 0), 260 static_cast<int>(input_bitmap->rowBytes()), 261 0, input_bitmap->bytesPerPixel(), 262 smoothing_filter, 263 image_size, 264 intermediate.getAddr8(0, 0), 265 static_cast<int>(intermediate.rowBytes()), 266 0, intermediate.bytesPerPixel(), false); 267 skia::SingleChannelConvolveY1D( 268 intermediate.getAddr8(0, 0), 269 static_cast<int>(intermediate.rowBytes()), 270 0, intermediate.bytesPerPixel(), 271 smoothing_filter, 272 image_size, 273 input_bitmap->getAddr8(0, 0), 274 static_cast<int>(input_bitmap->rowBytes()), 275 0, input_bitmap->bytesPerPixel(), false); 276 277 skia::ConvolutionFilter1D gradient_filter; 278 skia::SetUpGaussianConvolutionKernel(&gradient_filter, kernel_sigma, true); 279 skia::SingleChannelConvolveX1D( 280 input_bitmap->getAddr8(0, 0), 281 static_cast<int>(input_bitmap->rowBytes()), 282 0, input_bitmap->bytesPerPixel(), 283 gradient_filter, 284 image_size, 285 intermediate.getAddr8(0, 0), 286 static_cast<int>(intermediate.rowBytes()), 287 0, intermediate.bytesPerPixel(), true); 288 skia::SingleChannelConvolveY1D( 289 input_bitmap->getAddr8(0, 0), 290 static_cast<int>(input_bitmap->rowBytes()), 291 0, input_bitmap->bytesPerPixel(), 292 gradient_filter, 293 image_size, 294 intermediate2.getAddr8(0, 0), 295 static_cast<int>(intermediate2.rowBytes()), 296 0, intermediate2.bytesPerPixel(), true); 297 } else { 298 // For larger sigma values use the recursive filter. 299 skia::RecursiveFilter smoothing_filter(kernel_sigma, 300 skia::RecursiveFilter::FUNCTION); 301 skia::SingleChannelRecursiveGaussianX( 302 input_bitmap->getAddr8(0, 0), 303 static_cast<int>(input_bitmap->rowBytes()), 304 0, input_bitmap->bytesPerPixel(), 305 smoothing_filter, 306 image_size, 307 intermediate.getAddr8(0, 0), 308 static_cast<int>(intermediate.rowBytes()), 309 0, intermediate.bytesPerPixel(), false); 310 unsigned char smoothed_max = skia::SingleChannelRecursiveGaussianY( 311 intermediate.getAddr8(0, 0), 312 static_cast<int>(intermediate.rowBytes()), 313 0, intermediate.bytesPerPixel(), 314 smoothing_filter, 315 image_size, 316 input_bitmap->getAddr8(0, 0), 317 static_cast<int>(input_bitmap->rowBytes()), 318 0, input_bitmap->bytesPerPixel(), false); 319 if (smoothed_max < 127) { 320 int bit_shift = 8 - static_cast<int>( 321 std::log10(static_cast<float>(smoothed_max)) / std::log10(2.0f)); 322 for (int r = 0; r < image_size.height(); ++r) { 323 uint8* row = input_bitmap->getAddr8(0, r); 324 for (int c = 0; c < image_size.width(); ++c, ++row) { 325 *row <<= bit_shift; 326 } 327 } 328 } 329 330 skia::RecursiveFilter gradient_filter( 331 kernel_sigma, skia::RecursiveFilter::FIRST_DERIVATIVE); 332 skia::SingleChannelRecursiveGaussianX( 333 input_bitmap->getAddr8(0, 0), 334 static_cast<int>(input_bitmap->rowBytes()), 335 0, input_bitmap->bytesPerPixel(), 336 gradient_filter, 337 image_size, 338 intermediate.getAddr8(0, 0), 339 static_cast<int>(intermediate.rowBytes()), 340 0, intermediate.bytesPerPixel(), true); 341 skia::SingleChannelRecursiveGaussianY( 342 input_bitmap->getAddr8(0, 0), 343 static_cast<int>(input_bitmap->rowBytes()), 344 0, input_bitmap->bytesPerPixel(), 345 gradient_filter, 346 image_size, 347 intermediate2.getAddr8(0, 0), 348 static_cast<int>(intermediate2.rowBytes()), 349 0, intermediate2.bytesPerPixel(), true); 350 } 351 352 unsigned grad_max = 0; 353 for (int r = 0; r < image_size.height(); ++r) { 354 const uint8* grad_x_row = intermediate.getAddr8(0, r); 355 const uint8* grad_y_row = intermediate2.getAddr8(0, r); 356 for (int c = 0; c < image_size.width(); ++c) { 357 unsigned grad_x = grad_x_row[c]; 358 unsigned grad_y = grad_y_row[c]; 359 grad_max = std::max(grad_max, grad_x * grad_x + grad_y * grad_y); 360 } 361 } 362 363 int bit_shift = 0; 364 if (grad_max > 255) 365 bit_shift = static_cast<int>( 366 std::log10(static_cast<float>(grad_max)) / std::log10(2.0f)) - 7; 367 for (int r = 0; r < image_size.height(); ++r) { 368 const uint8* grad_x_row = intermediate.getAddr8(0, r); 369 const uint8* grad_y_row = intermediate2.getAddr8(0, r); 370 uint8* target_row = input_bitmap->getAddr8(0, r); 371 for (int c = 0; c < image_size.width(); ++c) { 372 unsigned grad_x = grad_x_row[c]; 373 unsigned grad_y = grad_y_row[c]; 374 target_row[c] = (grad_x * grad_x + grad_y * grad_y) >> bit_shift; 375 } 376 } 377 } 378 379 void ExtractImageProfileInformation(const SkBitmap& input_bitmap, 380 const gfx::Rect& area, 381 const gfx::Size& target_size, 382 bool apply_log, 383 std::vector<float>* rows, 384 std::vector<float>* columns) { 385 SkAutoLockPixels source_lock(input_bitmap); 386 DCHECK(rows); 387 DCHECK(columns); 388 DCHECK(input_bitmap.getPixels()); 389 DCHECK_EQ(SkBitmap::kA8_Config, input_bitmap.config()); 390 DCHECK_GE(area.x(), 0); 391 DCHECK_GE(area.y(), 0); 392 DCHECK_LE(area.right(), input_bitmap.width()); 393 DCHECK_LE(area.bottom(), input_bitmap.height()); 394 395 // Make sure rows and columns are allocated and initialized to 0. 396 rows->clear(); 397 columns->clear(); 398 rows->resize(area.height(), 0); 399 columns->resize(area.width(), 0); 400 401 for (int r = 0; r < area.height(); ++r) { 402 // Points to the first byte of the row in the rectangle. 403 const uint8* image_row = input_bitmap.getAddr8(area.x(), r + area.y()); 404 unsigned row_sum = 0; 405 for (int c = 0; c < area.width(); ++c, ++image_row) { 406 row_sum += *image_row; 407 (*columns)[c] += *image_row; 408 } 409 (*rows)[r] = row_sum; 410 } 411 412 if (apply_log) { 413 // Generally for processing we will need to take logarithm of this data. 414 // The option not to apply it is left principally as a test seam. 415 std::vector<float>::iterator it; 416 for (it = columns->begin(); it < columns->end(); ++it) 417 *it = std::log(1.0f + *it); 418 419 for (it = rows->begin(); it < rows->end(); ++it) 420 *it = std::log(1.0f + *it); 421 } 422 423 if (!target_size.IsEmpty()) { 424 // If the target size is given, profiles should be further processed through 425 // morphological closing. The idea is to close valleys smaller than what 426 // can be seen after scaling down to avoid deforming noticable features 427 // when profiles are used. 428 // Morphological closing is defined as dilation followed by errosion. In 429 // normal-speak: sliding-window maximum followed by minimum. 430 int column_window_size = 1 + 2 * 431 static_cast<int>(0.5f * area.width() / target_size.width() + 0.5f); 432 int row_window_size = 1 + 2 * 433 static_cast<int>(0.5f * area.height() / target_size.height() + 0.5f); 434 435 // Dilate and erode each profile with the given window size. 436 if (column_window_size >= 3) { 437 SlidingWindowMinMax(columns->begin(), 438 columns->end(), 439 columns->begin(), 440 column_window_size, 441 std::greater<float>()); 442 SlidingWindowMinMax(columns->begin(), 443 columns->end(), 444 columns->begin(), 445 column_window_size, 446 std::less<float>()); 447 } 448 449 if (row_window_size >= 3) { 450 SlidingWindowMinMax(rows->begin(), 451 rows->end(), 452 rows->begin(), 453 row_window_size, 454 std::greater<float>()); 455 SlidingWindowMinMax(rows->begin(), 456 rows->end(), 457 rows->begin(), 458 row_window_size, 459 std::less<float>()); 460 } 461 } 462 } 463 464 float AutoSegmentPeaks(const std::vector<float>& input) { 465 // This is a thresholding operation based on Otsu's method. 466 std::vector<int> histogram; 467 std::pair<float, float> minmax; 468 if (!ComputeScaledHistogram(input, &histogram, &minmax)) 469 return minmax.first; 470 471 // max_index refers to the bin *after* which we need to split. The sought 472 // threshold is the centre of this bin, scaled back to the original range. 473 size_t max_index = FindOtsuThresholdingIndex(histogram); 474 return (minmax.second - minmax.first) * (max_index + 0.5f) / 255.0f + 475 minmax.first; 476 } 477 478 gfx::Size AdjustClippingSizeToAspectRatio(const gfx::Size& target_size, 479 const gfx::Size& image_size, 480 const gfx::Size& computed_size) { 481 DCHECK_GT(target_size.width(), 0); 482 DCHECK_GT(target_size.height(), 0); 483 // If the computed thumbnail would be too wide or to tall, we shall attempt 484 // to fix it. Generally the idea is to re-add content to the part which has 485 // been more aggressively shrunk unless there is nothing to add there or if 486 // adding there won't fix anything. Should that be the case, we will 487 // (reluctantly) take away more from the other dimension. 488 float desired_aspect = 489 static_cast<float>(target_size.width()) / target_size.height(); 490 int computed_width = std::max(computed_size.width(), target_size.width()); 491 int computed_height = std::max(computed_size.height(), target_size.height()); 492 float computed_aspect = static_cast<float>(computed_width) / computed_height; 493 float aspect_change_delta = std::abs(computed_aspect - desired_aspect); 494 float prev_aspect_change_delta = 1000.0f; 495 const float kAspectChangeEps = 0.01f; 496 const float kLargeEffect = 2.0f; 497 498 while ((prev_aspect_change_delta - aspect_change_delta > kAspectChangeEps) && 499 (computed_aspect / desired_aspect > kAspectRatioToleranceFactor || 500 desired_aspect / computed_aspect > kAspectRatioToleranceFactor)) { 501 int new_computed_width = computed_width; 502 int new_computed_height = computed_height; 503 float row_dimension_shrink = 504 static_cast<float>(image_size.height()) / computed_height; 505 float column_dimension_shrink = 506 static_cast<float>(image_size.width()) / computed_width; 507 508 if (computed_aspect / desired_aspect > kAspectRatioToleranceFactor) { 509 // Too wide. 510 if (row_dimension_shrink > column_dimension_shrink) { 511 // Bring the computed_height to the least of: 512 // (1) image height (2) the number of lines that would 513 // make up the desired aspect or (3) number of lines we would get 514 // at the same 'aggressivity' level as width or. 515 new_computed_height = std::min( 516 static_cast<int>(image_size.height()), 517 static_cast<int>(computed_width / desired_aspect + 0.5f)); 518 new_computed_height = std::min( 519 new_computed_height, 520 static_cast<int>( 521 image_size.height() / column_dimension_shrink + 0.5f)); 522 } else if (row_dimension_shrink >= kLargeEffect || 523 new_computed_width <= target_size.width()) { 524 // Even though rows were resized less, we will generally rather add than 525 // remove (or there is nothing to remove in x already). 526 new_computed_height = std::min( 527 static_cast<int>(image_size.height()), 528 static_cast<int>(computed_width / desired_aspect + 0.5f)); 529 } else { 530 // Rows were already shrunk less aggressively. This means there is 531 // simply no room left too expand. Cut columns to get the desired 532 // aspect ratio. 533 new_computed_width = desired_aspect * computed_height + 0.5f; 534 } 535 } else { 536 // Too tall. 537 if (column_dimension_shrink > row_dimension_shrink) { 538 // Columns were shrunk more aggressively. Try to relax the same way as 539 // above. 540 new_computed_width = std::min( 541 static_cast<int>(image_size.width()), 542 static_cast<int>(desired_aspect * computed_height + 0.5f)); 543 new_computed_width = std::min( 544 new_computed_width, 545 static_cast<int>( 546 image_size.width() / row_dimension_shrink + 0.5f)); 547 } else if (column_dimension_shrink >= kLargeEffect || 548 new_computed_height <= target_size.height()) { 549 new_computed_width = std::min( 550 static_cast<int>(image_size.width()), 551 static_cast<int>(desired_aspect * computed_height + 0.5f)); 552 } else { 553 new_computed_height = computed_width / desired_aspect + 0.5f; 554 } 555 } 556 557 new_computed_width = std::max(new_computed_width, target_size.width()); 558 new_computed_height = std::max(new_computed_height, target_size.height()); 559 560 // Update loop control variables. 561 float new_computed_aspect = 562 static_cast<float>(new_computed_width) / new_computed_height; 563 564 if (std::abs(new_computed_aspect - desired_aspect) > 565 std::abs(computed_aspect - desired_aspect)) { 566 // Do not take inferior results. 567 break; 568 } 569 570 computed_width = new_computed_width; 571 computed_height = new_computed_height; 572 computed_aspect = new_computed_aspect; 573 prev_aspect_change_delta = aspect_change_delta; 574 aspect_change_delta = std::abs(new_computed_aspect - desired_aspect); 575 } 576 577 return gfx::Size(computed_width, computed_height); 578 } 579 580 void ConstrainedProfileSegmentation(const std::vector<float>& row_profile, 581 const std::vector<float>& column_profile, 582 const gfx::Size& target_size, 583 std::vector<bool>* included_rows, 584 std::vector<bool>* included_columns) { 585 DCHECK(included_rows); 586 DCHECK(included_columns); 587 588 std::vector<int> histogram_rows; 589 std::pair<float, float> minmax_rows; 590 bool rows_well_behaved = ComputeScaledHistogram( 591 row_profile, &histogram_rows, &minmax_rows); 592 593 float row_threshold = minmax_rows.first; 594 size_t clip_index_rows = 0; 595 596 if (rows_well_behaved) { 597 clip_index_rows = FindOtsuThresholdingIndex(histogram_rows); 598 row_threshold = (minmax_rows.second - minmax_rows.first) * 599 (clip_index_rows + 0.5f) / 255.0f + minmax_rows.first; 600 } 601 602 std::vector<int> histogram_columns; 603 std::pair<float, float> minmax_columns; 604 bool columns_well_behaved = ComputeScaledHistogram(column_profile, 605 &histogram_columns, 606 &minmax_columns); 607 float column_threshold = minmax_columns.first; 608 size_t clip_index_columns = 0; 609 610 if (columns_well_behaved) { 611 clip_index_columns = FindOtsuThresholdingIndex(histogram_columns); 612 column_threshold = (minmax_columns.second - minmax_columns.first) * 613 (clip_index_columns + 0.5f) / 255.0f + minmax_columns.first; 614 } 615 616 int auto_segmented_width = count_if( 617 column_profile.begin(), column_profile.end(), 618 std::bind2nd(std::greater<float>(), column_threshold)); 619 int auto_segmented_height = count_if( 620 row_profile.begin(), row_profile.end(), 621 std::bind2nd(std::greater<float>(), row_threshold)); 622 623 gfx::Size computed_size = AdjustClippingSizeToAspectRatio( 624 target_size, 625 gfx::Size(column_profile.size(), row_profile.size()), 626 gfx::Size(auto_segmented_width, auto_segmented_height)); 627 628 // Apply thresholding. 629 if (rows_well_behaved) { 630 ConstrainedProfileThresholding(row_profile, 631 histogram_rows, 632 clip_index_rows, 633 row_threshold, 634 minmax_rows, 635 auto_segmented_height, 636 computed_size.height(), 637 included_rows); 638 } else { 639 // This is essentially an error condition, invoked when no segmentation was 640 // possible. This will result in applying a very low threshold and likely 641 // in producing a thumbnail which should get rejected. 642 included_rows->resize(row_profile.size()); 643 for (size_t i = 0; i < row_profile.size(); ++i) 644 (*included_rows)[i] = row_profile[i] > row_threshold; 645 } 646 647 if (columns_well_behaved) { 648 ConstrainedProfileThresholding(column_profile, 649 histogram_columns, 650 clip_index_columns, 651 column_threshold, 652 minmax_columns, 653 auto_segmented_width, 654 computed_size.width(), 655 included_columns); 656 } else { 657 included_columns->resize(column_profile.size()); 658 for (size_t i = 0; i < column_profile.size(); ++i) 659 (*included_columns)[i] = column_profile[i] > column_threshold; 660 } 661 } 662 663 SkBitmap ComputeDecimatedImage(const SkBitmap& bitmap, 664 const std::vector<bool>& rows, 665 const std::vector<bool>& columns) { 666 SkAutoLockPixels source_lock(bitmap); 667 DCHECK(bitmap.getPixels()); 668 DCHECK_GT(bitmap.bytesPerPixel(), 0); 669 DCHECK_EQ(bitmap.width(), static_cast<int>(columns.size())); 670 DCHECK_EQ(bitmap.height(), static_cast<int>(rows.size())); 671 672 unsigned target_row_count = std::count(rows.begin(), rows.end(), true); 673 unsigned target_column_count = std::count( 674 columns.begin(), columns.end(), true); 675 676 if (target_row_count == 0 || target_column_count == 0) 677 return SkBitmap(); // Not quite an error, so no DCHECK. Just return empty. 678 679 if (target_row_count == rows.size() && target_column_count == columns.size()) 680 return SkBitmap(); // Equivalent of the situation above (empty target). 681 682 // Allocate the target image. 683 SkBitmap target; 684 target.setConfig(bitmap.config(), target_column_count, target_row_count); 685 target.allocPixels(); 686 687 int target_row = 0; 688 for (int r = 0; r < bitmap.height(); ++r) { 689 if (!rows[r]) 690 continue; // We can just skip this one. 691 uint8* src_row = 692 static_cast<uint8*>(bitmap.getPixels()) + r * bitmap.rowBytes(); 693 uint8* insertion_target = static_cast<uint8*>(target.getPixels()) + 694 target_row * target.rowBytes(); 695 int left_copy_pixel = -1; 696 for (int c = 0; c < bitmap.width(); ++c) { 697 if (left_copy_pixel < 0 && columns[c]) { 698 left_copy_pixel = c; // Next time we will start copying from here. 699 } else if (left_copy_pixel >= 0 && !columns[c]) { 700 // This closes a fragment we want to copy. We do it now. 701 size_t bytes_to_copy = (c - left_copy_pixel) * bitmap.bytesPerPixel(); 702 memcpy(insertion_target, 703 src_row + left_copy_pixel * bitmap.bytesPerPixel(), 704 bytes_to_copy); 705 left_copy_pixel = -1; 706 insertion_target += bytes_to_copy; 707 } 708 } 709 // We can still have the tail end to process here. 710 if (left_copy_pixel >= 0) { 711 size_t bytes_to_copy = 712 (bitmap.width() - left_copy_pixel) * bitmap.bytesPerPixel(); 713 memcpy(insertion_target, 714 src_row + left_copy_pixel * bitmap.bytesPerPixel(), 715 bytes_to_copy); 716 } 717 target_row++; 718 } 719 720 return target; 721 } 722 723 SkBitmap CreateRetargetedThumbnailImage( 724 const SkBitmap& source_bitmap, 725 const gfx::Size& target_size, 726 float kernel_sigma) { 727 // First thing we need for this method is to color-reduce the source_bitmap. 728 SkBitmap reduced_color; 729 reduced_color.setConfig( 730 SkBitmap::kA8_Config, source_bitmap.width(), source_bitmap.height()); 731 reduced_color.allocPixels(); 732 733 if (!color_utils::ComputePrincipalComponentImage(source_bitmap, 734 &reduced_color)) { 735 // CCIR601 luminance conversion vector. 736 gfx::Vector3dF transform(0.299f, 0.587f, 0.114f); 737 if (!color_utils::ApplyColorReduction( 738 source_bitmap, transform, true, &reduced_color)) { 739 DLOG(WARNING) << "Failed to compute luminance image from a screenshot. " 740 << "Cannot compute retargeted thumbnail."; 741 return SkBitmap(); 742 } 743 DLOG(WARNING) << "Could not compute principal color image for a thumbnail. " 744 << "Using luminance instead."; 745 } 746 747 // Turn 'color-reduced' image into the 'energy' image. 748 ApplyGaussianGradientMagnitudeFilter(&reduced_color, kernel_sigma); 749 750 // Extract vertical and horizontal projection of image features. 751 std::vector<float> row_profile; 752 std::vector<float> column_profile; 753 ExtractImageProfileInformation(reduced_color, 754 gfx::Rect(reduced_color.width(), 755 reduced_color.height()), 756 target_size, 757 true, 758 &row_profile, 759 &column_profile); 760 761 std::vector<bool> included_rows, included_columns; 762 ConstrainedProfileSegmentation(row_profile, 763 column_profile, 764 target_size, 765 &included_rows, 766 &included_columns); 767 768 // Use the original image and computed inclusion vectors to create a resized 769 // image. 770 return ComputeDecimatedImage(source_bitmap, included_rows, included_columns); 771 } 772 773 } // thumbnailing_utils 774
