1424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)// Copyright 2013 The Chromium Authors. All rights reserved. 2424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 3424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)// found in the LICENSE file. 4424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 5424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)// MSVC++ requires this to be set before any other includes to get M_PI. 6424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)#define _USE_MATH_DEFINES 7424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 8424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)#include "media/filters/wsola_internals.h" 9424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 10424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)#include <algorithm> 11424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)#include <cmath> 12424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)#include <limits> 13424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 14424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)#include "base/logging.h" 15424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)#include "base/memory/scoped_ptr.h" 16424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)#include "media/base/audio_bus.h" 17424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 18424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)namespace media { 19424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 20424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)namespace internal { 21424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 22424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)bool InInterval(int n, Interval q) { 23424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) return n >= q.first && n <= q.second; 24424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)} 25424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 26424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)float MultiChannelSimilarityMeasure(const float* dot_prod_a_b, 27424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const float* energy_a, 28424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const float* energy_b, 29424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int channels) { 30424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const float kEpsilon = 1e-12f; 31424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) float similarity_measure = 0.0f; 32424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) for (int n = 0; n < channels; ++n) { 33424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) similarity_measure += dot_prod_a_b[n] / sqrt(energy_a[n] * energy_b[n] + 34424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) kEpsilon); 35424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) } 36424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) return similarity_measure; 37424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)} 38424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 39424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)void MultiChannelDotProduct(const AudioBus* a, 40424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int frame_offset_a, 41424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const AudioBus* b, 42424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int frame_offset_b, 43424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int num_frames, 44424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) float* dot_product) { 45424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) DCHECK_EQ(a->channels(), b->channels()); 46424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) DCHECK_GE(frame_offset_a, 0); 47424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) DCHECK_GE(frame_offset_b, 0); 48424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) DCHECK_LE(frame_offset_a + num_frames, a->frames()); 49424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) DCHECK_LE(frame_offset_b + num_frames, b->frames()); 50424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 51424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) memset(dot_product, 0, sizeof(*dot_product) * a->channels()); 52424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) for (int k = 0; k < a->channels(); ++k) { 53424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const float* ch_a = a->channel(k) + frame_offset_a; 54424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const float* ch_b = b->channel(k) + frame_offset_b; 55424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) for (int n = 0; n < num_frames; ++n) { 56424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) dot_product[k] += *ch_a++ * *ch_b++; 57424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) } 58424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) } 59424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)} 60424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 61424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)void MultiChannelMovingBlockEnergies(const AudioBus* input, 62424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int frames_per_block, 63424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) float* energy) { 64424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int num_blocks = input->frames() - (frames_per_block - 1); 65424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int channels = input->channels(); 66424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 67424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) for (int k = 0; k < input->channels(); ++k) { 68424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const float* input_channel = input->channel(k); 69424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 70424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) energy[k] = 0; 71424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 72424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // First block of channel |k|. 73424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) for (int m = 0; m < frames_per_block; ++m) { 74424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) energy[k] += input_channel[m] * input_channel[m]; 75424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) } 76424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 77424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const float* slide_out = input_channel; 78424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const float* slide_in = input_channel + frames_per_block; 79424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) for (int n = 1; n < num_blocks; ++n, ++slide_in, ++slide_out) { 80424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) energy[k + n * channels] = energy[k + (n - 1) * channels] - *slide_out * 81424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) *slide_out + *slide_in * *slide_in; 82424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) } 83424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) } 84424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)} 85424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 86424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)// Fit the curve f(x) = a * x^2 + b * x + c such that 87e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch// f(-1) = y[0] 88e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch// f(0) = y[1] 89e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch// f(1) = y[2] 90e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch// and return the maximum, assuming that y[0] <= y[1] >= y[2]. 91e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdochvoid QuadraticInterpolation(const float* y_values, 92e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch float* extremum, 93e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch float* extremum_value) { 94424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) float a = 0.5f * (y_values[2] + y_values[0]) - y_values[1]; 95424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) float b = 0.5f * (y_values[2] - y_values[0]); 96424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) float c = y_values[1]; 97424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 98e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch if (a == 0.f) { 99e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch // The coordinates are colinear (within floating-point error). 100e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch *extremum = 0; 101e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch *extremum_value = y_values[1]; 102e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch } else { 103e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch *extremum = -b / (2.f * a); 104e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch *extremum_value = a * (*extremum) * (*extremum) + b * (*extremum) + c; 105e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch } 106424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)} 107424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 108424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)int DecimatedSearch(int decimation, 109424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) Interval exclude_interval, 110424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const AudioBus* target_block, 111424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const AudioBus* search_segment, 112424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const float* energy_target_block, 113424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const float* energy_candidate_blocks) { 114424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int channels = search_segment->channels(); 115424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int block_size = target_block->frames(); 116424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int num_candidate_blocks = search_segment->frames() - (block_size - 1); 117424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) scoped_ptr<float[]> dot_prod(new float[channels]); 118424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) float similarity[3]; // Three elements for cubic interpolation. 119424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 120424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int n = 0; 121424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) MultiChannelDotProduct(target_block, 0, search_segment, n, block_size, 122424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) dot_prod.get()); 123424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) similarity[0] = MultiChannelSimilarityMeasure( 124424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) dot_prod.get(), energy_target_block, 125424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) &energy_candidate_blocks[n * channels], channels); 126424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 127424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // Set the starting point as optimal point. 128424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) float best_similarity = similarity[0]; 129424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int optimal_index = 0; 130424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 131424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) n += decimation; 132424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) if (n >= num_candidate_blocks) { 133424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) return 0; 134424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) } 135424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 136424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) MultiChannelDotProduct(target_block, 0, search_segment, n, block_size, 137424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) dot_prod.get()); 138424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) similarity[1] = MultiChannelSimilarityMeasure( 139424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) dot_prod.get(), energy_target_block, 140424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) &energy_candidate_blocks[n * channels], channels); 141424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 142424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) n += decimation; 143424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) if (n >= num_candidate_blocks) { 144424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // We cannot do any more sampling. Compare these two values and return the 145424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // optimal index. 146424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) return similarity[1] > similarity[0] ? decimation : 0; 147424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) } 148424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 149424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) for (; n < num_candidate_blocks; n += decimation) { 150424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) MultiChannelDotProduct(target_block, 0, search_segment, n, block_size, 151424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) dot_prod.get()); 152424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 153424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) similarity[2] = MultiChannelSimilarityMeasure( 154424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) dot_prod.get(), energy_target_block, 155424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) &energy_candidate_blocks[n * channels], channels); 156424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 157424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) if ((similarity[1] > similarity[0] && similarity[1] >= similarity[2]) || 158424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) (similarity[1] >= similarity[0] && similarity[1] > similarity[2])) { 159424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // A local maximum is found. Do a cubic interpolation for a better 160424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // estimate of candidate maximum. 161424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) float normalized_candidate_index; 162424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) float candidate_similarity; 163e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch QuadraticInterpolation(similarity, &normalized_candidate_index, 164e5d81f57cb97b3b6b7fccc9c5610d21eb81db09dBen Murdoch &candidate_similarity); 165424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 166424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int candidate_index = n - decimation + static_cast<int>( 167424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) normalized_candidate_index * decimation + 0.5f); 168424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) if (candidate_similarity > best_similarity && 169424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) !InInterval(candidate_index, exclude_interval)) { 170424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) optimal_index = candidate_index; 171424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) best_similarity = candidate_similarity; 172424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) } 173424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) } else if (n + decimation >= num_candidate_blocks && 174424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) similarity[2] > best_similarity && 175424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) !InInterval(n, exclude_interval)) { 176424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // If this is the end-point and has a better similarity-measure than 177424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // optimal, then we accept it as optimal point. 178424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) optimal_index = n; 179424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) best_similarity = similarity[2]; 180424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) } 181424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) memmove(similarity, &similarity[1], 2 * sizeof(*similarity)); 182424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) } 183424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) return optimal_index; 184424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)} 185424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 186424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)int FullSearch(int low_limit, 187424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int high_limit, 188424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) Interval exclude_interval, 189424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const AudioBus* target_block, 190424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const AudioBus* search_block, 191424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const float* energy_target_block, 192424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const float* energy_candidate_blocks) { 193424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int channels = search_block->channels(); 194424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int block_size = target_block->frames(); 195424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) scoped_ptr<float[]> dot_prod(new float[channels]); 196424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 197424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) float best_similarity = std::numeric_limits<float>::min(); 198424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int optimal_index = 0; 199424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 200424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) for (int n = low_limit; n <= high_limit; ++n) { 201424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) if (InInterval(n, exclude_interval)) { 202424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) continue; 203424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) } 204424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) MultiChannelDotProduct(target_block, 0, search_block, n, block_size, 205424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) dot_prod.get()); 206424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 207424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) float similarity = MultiChannelSimilarityMeasure( 208424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) dot_prod.get(), energy_target_block, 209424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) &energy_candidate_blocks[n * channels], channels); 210424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 211424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) if (similarity > best_similarity) { 212424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) best_similarity = similarity; 213424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) optimal_index = n; 214424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) } 215424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) } 216424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 217424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) return optimal_index; 218424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)} 219424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 220424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)int OptimalIndex(const AudioBus* search_block, 221424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const AudioBus* target_block, 222424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) Interval exclude_interval) { 223424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int channels = search_block->channels(); 224424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) DCHECK_EQ(channels, target_block->channels()); 225424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int target_size = target_block->frames(); 226424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int num_candidate_blocks = search_block->frames() - (target_size - 1); 227424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 228424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // This is a compromise between complexity reduction and search accuracy. I 229424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // don't have a proof that down sample of order 5 is optimal. One can compute 230424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // a decimation factor that minimizes complexity given the size of 231424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // |search_block| and |target_block|. However, my experiments show the rate of 232424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // missing the optimal index is significant. This value is chosen 233424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // heuristically based on experiments. 234424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const int kSearchDecimation = 5; 235424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 236424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) scoped_ptr<float[]> energy_target_block(new float[channels]); 237424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) scoped_ptr<float[]> energy_candidate_blocks( 238424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) new float[channels * num_candidate_blocks]); 239424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 240424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // Energy of all candid frames. 241424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) MultiChannelMovingBlockEnergies(search_block, target_size, 242424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) energy_candidate_blocks.get()); 243424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 244424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) // Energy of target frame. 245424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) MultiChannelDotProduct(target_block, 0, target_block, 0, 246424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) target_size, energy_target_block.get()); 247424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 248424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int optimal_index = DecimatedSearch(kSearchDecimation, 249424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) exclude_interval, target_block, 250424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) search_block, energy_target_block.get(), 251424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) energy_candidate_blocks.get()); 252424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 253424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int lim_low = std::max(0, optimal_index - kSearchDecimation); 254424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) int lim_high = std::min(num_candidate_blocks - 1, 255424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) optimal_index + kSearchDecimation); 256424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) return FullSearch(lim_low, lim_high, exclude_interval, target_block, 257424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) search_block, energy_target_block.get(), 258424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) energy_candidate_blocks.get()); 259424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)} 260424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 261424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)void GetSymmetricHanningWindow(int window_length, float* window) { 262424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) const float scale = 2.0f * M_PI / window_length; 263424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) for (int n = 0; n < window_length; ++n) 264424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) window[n] = 0.5f * (1.0f - cosf(n * scale)); 265424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)} 266424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 267424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)} // namespace internal 268424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 269424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles)} // namespace media 270424c4d7b64af9d0d8fd9624f381f469654d5e3d2Torne (Richard Coles) 271