A divide et impera algorithm for optimal pitch stylization

Antonio Origlia, Giovanni Abete, Francesco Cutugno, Iolanda Alfano, Renata Savy, Bogdan LudusanInterspeech 2011

TL;DR

This paper introduces "OpS," a novel divide-and-conquer algorithm for pitch stylization that balances curve quality with the number of control points used. By incorporating syllable prominence, OpS achieves perceptually equivalent stylizations with fewer points, making it more efficient than existing methods.

What Problem Does This Paper Address?

Pitch stylization is the process of simplifying a complex pitch contour (the fundamental frequency of speech over time) into a more manageable representation. This simplified curve should retain the essential prosodic information of the original while being more compact. The goal is to create a curve that is auditorily indistinguishable from the original but uses the fewest possible control points. Existing methods, like the widely used MOMEL algorithm, often require manual parameter tuning or may not achieve the optimal balance between quality and cost. This paper aims to address this by proposing an algorithm that automatically optimizes for both aspects and can be further enhanced by linguistic information like syllable prominence.

Methods

The core of the proposed algorithm, OpS, is a divide-and-conquer approach. It recursively breaks down the pitch curve into smaller segments, finds optimal stylizations for these segments, and then merges them. This process is framed as an optimization problem.

The authors define an objective function $F(S)$ that evaluates the quality of a stylized curve $S$. This function is a harmonic mean of a quality measure $q(S)$ and a cost measure $c(S)$.

  • Quality ($q(S)$): This is measured using the Normalized Root Mean Square Error (NRMSE) between the original pitch curve and the stylized curve. A higher $q(S)$ indicates better perceptual similarity.
  • Cost ($c(S)$): This is defined as the ratio of the number of points in the stylized curve to the number of points in a reference curve (obtained by linearly interpolating the original at a very small interval). A lower cost is desirable.

A key innovation is the introduction of a dynamic weighting factor, $\beta$, which adjusts the balance between quality and cost. $\beta$ is calculated based on the standard deviation of pitch differences in the original curve. This allows the algorithm to favor cost reduction in relatively flat regions and prioritize quality in areas with significant pitch changes.

Furthermore, the paper proposes a variant of OpS that leverages syllable prominence. The hypothesis is that non-prominent syllables can tolerate more aggressive simplification (fewer control points) without affecting perceptual quality. This is achieved by slightly modifying the cost function's steepness in these regions.

The computational complexity of the basic OpS algorithm is $O(N \log N)$, which is more efficient than the $O(KN^2)$ complexity of some dynamic programming approaches.

Datasets

  • TIMIT subset: Used for objective evaluations. This subset contains 382 files annotated for prominence, originally used for prominence detection research.
  • CLIPS corpus: A corpus of Italian semi-spontaneous speech. For this study, 20 sentences were selected, each containing a single tonal unit, and annotated by an expert linguist following the same method as the TIMIT subset. This was used for the subjective listening tests.

Key Insights and Ideas

  • Optimal Substructure Property: The authors demonstrate that an optimal pitch stylization exhibits optimal substructure, meaning that optimal stylizations of sub-curves are also optimal for those sub-sections of the original curve. This justifies the divide-and-conquer approach.
  • Balancing Quality and Cost: Framing pitch stylization as an optimization problem that simultaneously considers perceptual quality and the number of control points is crucial for achieving practical and efficient representations.
  • Dynamic Weighting ($\beta$): The adaptive weighting of quality vs. cost based on the original curve's characteristics is a significant improvement, allowing for more context-aware stylization.
  • Syllable Prominence for Efficiency: Exploiting linguistic information like syllable prominence offers a direct path to reducing the number of control points without sacrificing perceptual quality, making stylizations more compact.
  • NRMSE Limitations: The paper suggests that while NRMSE is a useful objective measure, it may not fully capture perceptual quality. This aligns with findings that statistical closeness doesn't always equate to subjective listener agreement.

Key Results

  • Subjective Evaluation: The OpS algorithm and its prominence-based variant performed comparably to the MOMEL algorithm in subjective listening tests, with no statistically significant difference in perceived equality to the original curve.
  • Point Reduction: The prominence-based OpS variant significantly reduced the number of points used compared to MOMEL (p < 0.01). The basic OpS algorithm used a similar number of points to MOMEL.
  • Efficiency: OpS achieves $O(N \log N)$ complexity, outperforming $O(KN^2)$ dynamic programming approaches.
  • NRMSE: The DP approach achieved the best NRMSE, but this did not translate to improved subjective evaluation, reinforcing the idea that objective measures alone are insufficient.

Limitations and Future Work

  • Quality Measure: The authors acknowledge that NRMSE might not be the ideal quality measure and suggest exploring more perceptually motivated functions in the future.
  • Automatic Segmentation: The current prominence-based variant relies on pre-annotated prominence. Future work will focus on introducing an automatic syllable segmentation and prominence annotation step.
  • Parameter Tuning: While OpS aims to reduce parameter tuning, the paper mentions setting an initial value for $\beta$ and its inferior limit. Further research could explore fully automatic determination of these parameters.

Summary updated

BibTeX
@inproceedings{origlia2011divide,
  author = {Antonio Origlia and Giovanni Abete and Francesco Cutugno and Iolanda Alfano and Renata Savy and Bogdan Ludusan},
  title = {{A divide et impera algorithm for optimal pitch stylization}},
  booktitle = {Interspeech},
  year = {2011},
}
Figure