nbs/fibonaccistretch.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fibonacci Stretch: An Exploration Through Code\n",
    "\n",
    "by [David Su](http://usdivad.com/)\n",
    "\n",
    "\n",
    "This notebook and its associated code are also available on [GitHub](https://github.com/usdivad/fibonaccistretch).\n",
    "\n",
    "## Contents\n",
    "\n",
    "- [Introduction](#Introduction)\n",
    "    - [A sneak peek at the final result](#A-sneak-peek-at-the-final-result)\n",
    "- [Part 1 - Representing rhythm as symbolic data](#Part-1---Representing-rhythm-as-symbolic-data)\n",
    "    - [1.1 Rhythms as arrays](#1.1-Rhythms-as-arrays)\n",
    "    - [1.2 Rhythmic properties](#1.2-Rhythmic-properties)\n",
    "- [Part 2 - Fibonacci rhythms](#Part-2---Fibonacci-rhythms)\n",
    "    - [2.1 Fibonacci numbers](#2.1-Fibonacci-numbers)\n",
    "    - [2.2 Using Fibonacci numbers to manipulate rhythms](#2.2-Using-Fibonacci-numbers-to-manipulate-rhythms)\n",
    "- [Part 3 - Mapping rhythm to audio](#Part-3---Mapping-rhythm-to-audio)\n",
    "    - [3.1 Estimating tempo](#3.1-Estimating-tempo)\n",
    "    - [3.2 From tempo to beats](#3.2-From-tempo-to-beats)\n",
    "    - [3.3 From beats to measures](#3.3-From-beats-to-measures)\n",
    "    - [3.4 Putting it all together: mapping symbolic rhythms to audio signals](#3.4-Putting-it-all-together:-mapping-symbolic-rhythms-to-audio-signals)\n",
    "- [Part 4 - Time-stretching audio](#Part-4---Time-stretching-audio)\n",
    "    - [4.1 Target rhythms](#4.1-Target-rhythms)\n",
    "    - [4.2 Pulse ratios](#4.2-Pulse-ratios)\n",
    "    - [4.3 Modifying measures by time-stretching](#4.3-Modifying-measures-by-time-stretching)\n",
    "    - [4.4 Modifying an entire track by naively time-stretching each pulse](#4.4-Modifying-an-entire-track-by-naively-time-stretching-each-pulse)\n",
    "    - [4.5 Overlaying target rhythm clicks](#4.5-Overlaying-target-rhythm-clicks)\n",
    "- [Part 5- Euclidean stretch](#Part-5---Euclidean-stretch)\n",
    "    - [5.1 Subdividing pulses](#5.1-Subdividing-pulses)\n",
    "    - [5.2 Generating Euclidean rhythms using Bjorklund's algorithm](#5.2-Generating-Euclidean-rhythms-using-Bjorklund's-algorithm)\n",
    "    - [5.3 Using Euclidean rhythms to subdivide pulses](#5.3-Using-Euclidean-rhythms-to-subdivide-pulses)\n",
    "    - [5.4 The Euclidean stretch algorithm](#5.4-The-Euclidean-stretch-algorithm)\n",
    "- [Part 6 - Fibonacci stretch: implementation and examples](#Part-6---Fibonacci-stretch:-implementation-and-examples)\n",
    "    - [6.1 Implementation](#6.1-Implementation)\n",
    "    - [6.2 Examples: customizing stretch factors](#6.2-Examples:-customizing-stretch-factors)\n",
    "    - [6.3 Examples: customizing orginal and target rhythms](#6.3-Examples:-customizing-original-and-target-rhythms)\n",
    "    - [6.4 Examples: customizing input beats per measure](#6.4-Examples:-customizing-input-beats-per-measure)\n",
    "- [Part 7 - Final thoughts](#Part-7---Final-thoughts)\n",
    "    - [7.1 Fibonacci stretch as a creative tool](#7.1-Fibonacci-stretch-as-a-creative-tool)\n",
    "    - [7.2 Rhythm perception](#7.2-Rhythm-perception)\n",
    "    - [7.3 Implementation improvements](#7.3-Implementation-improvements)\n",
    "    - [7.4 Future directions](#7.4-Future-directions)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "\n",
    "The goal of this notebook is to investigate and explore a method of time-stretching an existing audio track such that its rhythmic pulses become expanded or contracted along the Fibonacci sequence, using Euclidean rhythms as the basis for modification. For lack of a better term, let's call it **Fibonacci stretch**.\n",
    "\n",
    "Inspiration for this came initially from Vijay Iyer's [article on Fibonacci numbers and musical rhythm](https://www.theguardian.com/music/2009/oct/15/fibonacci-golden-ratio) as well as his trio's renditions of \"Mystic Brew\" and \"Human Nature\"; we'll use original version of the latter as an example throughout. We'll also touch upon Godfried Toussaint's work on [Euclidean rhythms](http://cgm.cs.mcgill.ca/~godfried/publications/banff.pdf) and [Bjorklund's algorithm](https://ics-web.sns.ornl.gov/timing/Rep-Rate%20Tech%20Note.pdf), both of which are intimately related."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### A sneak peek at the final result\n",
    "\n",
    "This is where we'll end up:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import IPython.display as ipd\n",
    "ipd.Audio(\"../data/out_humannature_90s_stretched.mp3\", rate=44100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can also jump to [Part 6](#6.2-Examples:-customizing-stretch-factors) for more audio examples.\n",
    "\n",
    "## Part 1 - Representing rhythm as symbolic data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Rhythms as arrays\n",
    "\n",
    "The main musical element we're going to play with here is **rhythm** (in particular, rhythmic ratios and their similarities). The base rhythm that we're going to focus on is the *tresillo* (\"three\"-side) of the *son* clave pattern, which sounds like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ipd.Audio(\"../data/tresillo_rhythm.mp3\", rate=44100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "...and looks something like this in Western music notation:\n",
    "\n",
    "![Tresillo rhythm in Western music notation](../data/tresillo_rhythm_notation.png)\n",
    "\n",
    "We can convert that into a sequence of **bits**, with each `1` representing an onset, and `0` representing a rest (similar to the way a sequencer works). Doing so yields this:\n",
    "```\n",
    "[1 0 0 1 0 0 1 0]\n",
    "```\n",
    "...which we can conveniently store as a list in Python. Actually, this is a good time to start diving directly into code. First, let's import all the Python libraries we need:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import math # Standard library imports\n",
    "import IPython.display as ipd, librosa, librosa.display, numpy as np, matplotlib.pyplot as plt # External libraries\n",
    "import pardir; pardir.pardir() # Allow imports from parent directory\n",
    "import bjorklund # Fork of Brian House's implementation of Bjorklund's algorithm https://github.com/brianhouse/bjorklund"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Briefly: we're using **`IPython.display`** to do audio playback, **`librosa`** for the bulk of the audio processing and manipulation (namely time-stretching), **`numpy`** to represent data, and **`matplotlib`** to plot the data.\n",
    "\n",
    "Here's our list of bits encoding the *tresillo* sequence in Python (we'll use numpy arrays for consistency with later when when we deal with both audio signals and plotting visualizations):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "tresillo_rhythm = np.array([1, 0, 0, 1, 0, 0, 1, 0])\n",
    "print(tresillo_rhythm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that both the music notation and the array are **symbolic** representations of the rhythm; the rhythm is abstracted so that there is no information about tempo, dynamics, timbre, or other musical information. All we have is the temporal relationship between each note in the sequence (as well as the base assumption that the notes are evenly spaced).\n",
    "\n",
    "Let's hear (and visualize) an example of how this rhythm sounds in more concrete terms:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Generate tresillo clicks\n",
    "sr = 44100\n",
    "tresillo_click_interval = 0.25 # in seconds\n",
    "tresillo_click_times = np.array([i * tresillo_click_interval for i in range(len(tresillo_rhythm))\n",
    "                                 if tresillo_rhythm[i] != 0])\n",
    "tresillo_clicks = librosa.clicks(times=tresillo_click_times, click_freq=2000.0, sr=sr) # Generate clicks according to the rhythm\n",
    "\n",
    "# Plot clicks and click times\n",
    "plt.figure(figsize=(8, 2))\n",
    "librosa.display.waveplot(tresillo_clicks, sr=sr)\n",
    "plt.vlines(tresillo_click_times + 0.005, -1, 1, color=\"r\") # Add tiny offset so the first line shows up\n",
    "plt.xticks(np.arange(0, 1.75, 0.25))\n",
    "\n",
    "# Render clicks as audio\n",
    "ipd.Audio(tresillo_clicks, rate=sr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 Rhythmic properties\n",
    "\n",
    "To work with rhythm in an analytical fashion, we'll need to define some properties of a given rhythmic sequence.\n",
    "\n",
    "Let's define **pulses** as the number of onsets in a sequence (i.e. the number of `1`s as opposed to `0`s), and **steps** as the total number of elements in the sequence:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "tresillo_num_pulses = np.count_nonzero(tresillo_rhythm)\n",
    "tresillo_num_steps = len(tresillo_rhythm)\n",
    "print(\"The tresillo rhythm has {} pulses and {} steps\".format(tresillo_num_pulses, tresillo_num_steps))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can listen to the pulses and steps together:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def generate_rhythm_clicks(rhythm, click_interval=0.25, sr=44100):\n",
    "    step_length_samples = int(librosa.time_to_samples(click_interval, sr=sr))\n",
    "    rhythm_length_samples = step_length_samples * (len(rhythm))\n",
    "    \n",
    "    # Generate click times\n",
    "    pulse_click_times, step_click_times = generate_rhythm_times(rhythm, click_interval)\n",
    "    \n",
    "    # Generate pulse clicks\n",
    "    pulse_click_times = np.array([i * click_interval for i in range(len(rhythm))\n",
    "                                           if rhythm[i] != 0])\n",
    "    pulse_clicks = librosa.clicks(times=pulse_click_times, click_freq=2000.0, sr=sr, length=rhythm_length_samples)\n",
    "\n",
    "    # Generate step clicks\n",
    "    step_click_times = np.array([i * click_interval for i in range(len(rhythm))])\n",
    "    step_clicks = librosa.clicks(times=step_click_times, click_freq=1000.0, sr=sr, length=rhythm_length_samples)    \n",
    "    step_clicks = np.hstack((step_clicks, np.zeros(step_length_samples, dtype=\"int\"))) # add last step samples\n",
    "\n",
    "    # Add zeros to pulse clicks so that it's the same length as the step clicks signal\n",
    "    pulse_clicks = np.hstack((pulse_clicks, np.zeros(len(step_clicks)-len(pulse_clicks), dtype=\"int\")))\n",
    "    \n",
    "    # Ensure proper length\n",
    "    pulse_clicks = pulse_clicks[:rhythm_length_samples]\n",
    "    step_clicks = step_clicks[:rhythm_length_samples]\n",
    "    \n",
    "    return (pulse_clicks, step_clicks)\n",
    "\n",
    "def generate_rhythm_times(rhythm, interval):\n",
    "    pulse_times = np.array([float(i * interval) for i in range(len(rhythm)) if rhythm[i] != 0])\n",
    "    step_times = np.array([float(i * interval) for i in range(len(rhythm))])\n",
    "    return (pulse_times, step_times)\n",
    "\n",
    "# Generate the clicks\n",
    "tresillo_pulse_clicks, tresillo_step_clicks = generate_rhythm_clicks(tresillo_rhythm, tresillo_click_interval)\n",
    "tresillo_pulse_times, tresillo_step_times = generate_rhythm_times(tresillo_rhythm, tresillo_click_interval)\n",
    "\n",
    "# Tresillo as an array\n",
    "print(tresillo_rhythm)\n",
    "\n",
    "# Tresillo audio, plotted\n",
    "plt.figure(figsize=(8, 2))\n",
    "librosa.display.waveplot(tresillo_pulse_clicks + tresillo_step_clicks, sr=sr)\n",
    "plt.vlines(tresillo_pulse_times + 0.005, -1, 1, color=\"r\")\n",
    "plt.vlines(tresillo_step_times + 0.005, -0.5, 0.5, color=\"r\")\n",
    "\n",
    "# Tresillo as audio\n",
    "ipd.Audio(tresillo_pulse_clicks + tresillo_step_clicks, rate=44100)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can follow along with the printed array and hear that every `1` corresponds to a pulse, and every `0` to a step.\n",
    "\n",
    "In addition, let's define **pulse lengths** as the number of steps that each pulse lasts:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Function to calculate pulse lengths based on rhythm patterns\n",
    "def calculate_pulse_lengths(rhythm):\n",
    "    pulse_lengths = np.array(([i for i,p in enumerate(rhythm) if p > 0]))\n",
    "    pulse_lengths = np.hstack((pulse_lengths, len(rhythm)))\n",
    "    pulse_lengths = np.array([pulse_lengths[i+1] - pulse_lengths[i] for i in range(len(pulse_lengths) - 1)])\n",
    "    \n",
    "    return pulse_lengths\n",
    "\n",
    "tresillo_pulse_lengths = calculate_pulse_lengths(tresillo_rhythm)\n",
    "print(\"Tresillo pulse lengths: {}\".format(tresillo_pulse_lengths))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the *tresillo* rhythm's pulse lengths all fall along the **Fibonacci sequence**. This allows us do some pretty fun things, as we'll see in a bit. But first let's take a step back."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 2 - Fibonacci rhythms\n",
    "\n",
    "### 2.1 Fibonacci numbers\n",
    "\n",
    "The Fibonacci sequence is a particular sequence in which each value is the sum of the two preceding values. We can define a function in Python that gives us the `n`th Fibonacci number:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fibonacci(n):\n",
    "    if n == 0 or n == 1:\n",
    "        return n\n",
    "    else:\n",
    "        return fibonacci(n-1) + fibonacci(n-2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And the first 20 numbers in the sequence are:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "first_twenty_fibs = np.array([fibonacci(n) for n in range(20)])\n",
    "plt.figure(figsize=(16,1))\n",
    "plt.scatter(first_twenty_fibs, np.zeros(20), c=\"r\")\n",
    "plt.axis(\"off\")\n",
    "print(first_twenty_fibs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The Fibonacci sequence is closely linked to the **golden ratio** in many ways, including the fact that as we go up the sequence, the ratio between successive numbers gets closer and closer to the golden ratio. (If you're interested, Vijay Iyer's article [Strength in numbers: How Fibonacci taught us how to swing ](https://www.theguardian.com/music/2009/oct/15/fibonacci-golden-ratio) goes into this in more depth.)\n",
    "\n",
    "Below is a plot of Fibonacci number ratios in <span style=\"color:red\">red</span>, and the golden ratio as a constant in <span style=\"color:blue\">blue</span>. You can see how the Fibonacci ratios converge to the golden ratio:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Calculate and plot Fibonacci number ratios\n",
    "phi = (1 + math.sqrt(5)) / 2 # Golden ratio; 1.61803398875...\n",
    "fibs_ratios = np.array([first_twenty_fibs[i] / float(max(1, first_twenty_fibs[i-1])) for i in range(2,20)])\n",
    "plt.plot(np.arange(len(fibs_ratios)), fibs_ratios, \"r\")\n",
    "\n",
    "# Plot golden ratio as a consant\n",
    "phis = np.empty(len(fibs_ratios))\n",
    "phis.fill(phi)\n",
    "plt.xticks(np.arange(len(fibs_ratios)))\n",
    "plt.xlabel(\"Fibonacci index (denotes i for ith Fibonacci number)\")\n",
    "plt.ylabel(\"Ratio between ith and (i-1)th Fibonacci number\")\n",
    "plt.plot(np.arange(len(phis)), phis, \"b\", alpha=0.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also use the golden ratio to find the index of a Fibonacci number:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "def find_fibonacci_index(n):\n",
    "    phi = (1 + math.sqrt(5)) / 2 # Golden ratio; 1.61803398875...\n",
    "    return int(math.log((n * math.sqrt(5)) + 0.5) / math.log(phi))\n",
    "\n",
    "fib_n = 21\n",
    "fib_i = find_fibonacci_index(fib_n)\n",
    "assert(fibonacci(fib_i) == fib_n)\n",
    "print(\"{} is the {}th Fibonacci number\".format(fib_n, fib_i))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 Using Fibonacci numbers to manipulate rhythms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recall our *tresillo* rhythm:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "plt.figure(figsize=(8, 2))\n",
    "plt.vlines(tresillo_pulse_times + 0.005, -1, 1, color=\"r\")\n",
    "plt.vlines(tresillo_step_times + 0.005, -0.5, 0.5, color=\"r\", alpha=0.5)\n",
    "plt.yticks([])\n",
    "\n",
    "print(\"Tresillo rhythm sequence: {}\".format(tresillo_rhythm))\n",
    "print(\"Tresillo pulse lengths: {}\".format(tresillo_pulse_lengths))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We might classify it as a **Fibonacci rhythm**, since every one of its pulse lengths is a Fibonacci number. If we wanted to **expand** that rhythm along the Fibonacci sequence, what would that look like?\n",
    "\n",
    "An intuitive (and, as it turns out, musically satisfying) method would be to take every pulse length and simply replace it with the Fibonacci number that follows it. So in our example, the `3`s become `5`s, and the `2` becomes `3`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def fibonacci_expand_pulse_lengths(pulse_lengths):\n",
    "    new_pulse_lengths = np.array([], dtype=\"int\")\n",
    "    for pulse_length in pulse_lengths:\n",
    "        fib_i = find_fibonacci_index(pulse_length)\n",
    "        new_pulse_length = fibonacci(fib_i + 1)\n",
    "        new_pulse_lengths = np.hstack((new_pulse_lengths, new_pulse_length))\n",
    "    return new_pulse_lengths\n",
    "\n",
    "print(\"Expanded tresillo pulse lengths: {}\".format(fibonacci_expand_pulse_lengths(tresillo_pulse_lengths)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll also want to be able to **contract** rhythms along the Fibonacci sequence (i.e. choose numbers in decreasing order instead of increasing order), as well as specify how many Fibonacci numbers away we want to end up.\n",
    "\n",
    "We can generalize this expansion and contraction into a single function that can **scale** pulse lengths:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Function to scale pulse lengths along the Fibonacci sequence\n",
    "# \n",
    "# Note that `scale_amount` determines the direction and magnitude of the scaling.\n",
    "# If `scale_amount` > 0, it corresponds to a rhythmic expansion.\n",
    "# If `scale_amount` < 0, it corresponds to a rhythmic contraction.\n",
    "# If `scale_amount` == 0, the original scale is maintained and no changes are made.\n",
    "def fibonacci_scale_pulse_lengths(pulse_lengths, scale_amount=0):\n",
    "    scaled_pulse_lengths = np.array([], dtype=\"int\")\n",
    "    for pulse_length in pulse_lengths:\n",
    "        fib_i = find_fibonacci_index(pulse_length)\n",
    "        # if fib_i + scale_amount < 0:\n",
    "        #     print(\"ERROR: Scale amount out of bounds\")\n",
    "        #     return pulse_lengths\n",
    "        scaled_pulse_length = fibonacci(max(fib_i + scale_amount, 0))\n",
    "        scaled_pulse_lengths = np.hstack((scaled_pulse_lengths, scaled_pulse_length))\n",
    "    return scaled_pulse_lengths\n",
    "\n",
    "print(\"Tresillo pulse lengths:                 {}\".format(tresillo_pulse_lengths))\n",
    "print(\"Tresillo pulse lengths expanded by 1:   {}\".format(fibonacci_scale_pulse_lengths(tresillo_pulse_lengths, 1)))\n",
    "print(\"Tresillo pulse lengths expanded by 2:   {}\".format(fibonacci_scale_pulse_lengths(tresillo_pulse_lengths, 2)))\n",
    "print(\"Tresillo pulse lengths contracted by 1: {}\".format(fibonacci_scale_pulse_lengths(tresillo_pulse_lengths, -1)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course, once we have these scaled pulse lengths, we'll want to be able to convert them back into rhythms, in our original array format:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Define the functions we'll use to scale rhythms along the Fibonacci sequence\n",
    "def fibonacci_scale_rhythm(rhythm, scale_amount):\n",
    "    pulse_lengths = calculate_pulse_lengths(rhythm)\n",
    "    scaled_pulse_lengths = fibonacci_scale_pulse_lengths(pulse_lengths, scale_amount)\n",
    "    scaled_pulse_lengths = np.array([p for p in scaled_pulse_lengths if p > 0])\n",
    "\n",
    "    scaled_rhythm = pulse_lengths_to_rhythm(scaled_pulse_lengths)\n",
    "    return scaled_rhythm\n",
    "\n",
    "def pulse_lengths_to_rhythm(pulse_lengths):\n",
    "    rhythm = np.array([], dtype=\"int\")\n",
    "    for p in pulse_lengths:\n",
    "        pulse = np.zeros(p, dtype=\"int\")\n",
    "        pulse[0] = 1\n",
    "        rhythm = np.hstack((rhythm, pulse))\n",
    "    return rhythm\n",
    "\n",
    "# Scale tresillo rhythm by a variety of factors and plot the results\n",
    "for scale_factor, color in [(0, \"r\"), (1, \"g\"), (2, \"b\"), (-1, \"y\")]:\n",
    "    scaled_rhythm = fibonacci_scale_rhythm(tresillo_rhythm, scale_factor)\n",
    "    scaled_pulse_indices = np.array([p_i for p_i,x in enumerate(scaled_rhythm) if x > 0 ])\n",
    "    scaled_step_indices = np.array([s_i for s_i in range(len(scaled_rhythm))])\n",
    "    scaled_pulse_ys = np.empty(len(scaled_pulse_indices))\n",
    "    scaled_pulse_ys.fill(0)\n",
    "    scaled_step_ys = np.empty(len(scaled_step_indices))\n",
    "    scaled_step_ys.fill(0)\n",
    "    \n",
    "    # plt.figure(figsize=(len([scaled_rhythm])*0.5, 1))\n",
    "    plt.figure(figsize=(8, 1))\n",
    "    if scale_factor > 0:\n",
    "        plt.title(\"Tresillo rhythm expanded by {}: {}\".format(abs(scale_factor), scaled_rhythm), loc=\"left\")\n",
    "    elif scale_factor < 0:\n",
    "        plt.title(\"Tresillo rhythm contracted by {}: {}\".format(abs(scale_factor), scaled_rhythm), loc=\"left\")\n",
    "    else: # scale_factor == 0, which means rhythm is unaltered\n",
    "        plt.title(\"Tresillo rhythm: {}\".format(scaled_rhythm), loc=\"left\")\n",
    "    # plt.scatter(scaled_pulse_indices, scaled_pulse_ys, c=color)\n",
    "    # plt.scatter(scaled_step_indices, scaled_step_ys, c=\"k\", alpha=0.5)\n",
    "    # plt.grid(True)\n",
    "    plt.vlines(scaled_pulse_indices, -1, 1, color=color)\n",
    "    plt.vlines(scaled_step_indices, -0.5, 0.5, color=color, alpha=0.5)\n",
    "    plt.xticks(np.arange(0, plt.xlim()[1], 1))\n",
    "    plt.yticks([])\n",
    "    # plt.xticks(np.linspace(0, 10, 41))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This is exactly the kind of rhythmic expansion and contraction that the Vijay Iyer Trio explore in their renditions of \"[Mystic Brew](https://open.spotify.com/track/55Y7VrnLlG4pFDjeAkZQqy)\" and \"[Human Nature (Trio Extension)](https://open.spotify.com/track/1aj5pTKPit19Rmmby4BfmC)\".\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next up, let's begin working with some actual audio!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 3 - Mapping rhythm to audio"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Part of the beauty of working with rhythms in a symbolic fashion is that once we set things up, we can apply them to any existing audio track.\n",
    "\n",
    "To properly map the relationship between a rhythmic sequence and an audio representation of a piece of music, we'll have to do some **feature extraction**, that is, teasing out specific attributes of the music by analyzing the audio signal.\n",
    "\n",
    "Our goal is to create a musically meaningful relationship between our symbolic rhythmic data and the audio track we want to manipulate."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.1 Estimating tempo\n",
    "\n",
    "First we'll load up our source audio file. For this example we'll work with Michael Jackson's \"[Human Nature](https://open.spotify.com/track/4cgjA7B4fJBHyB9Ya2bu0t)\", off of his 1982 album *Thriller*:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Load input audio file\n",
    "filename = \"../data/humannature_30s.mp3\"\n",
    "y, sr = librosa.load(filename, sr=sr)\n",
    "\n",
    "plt.figure(figsize=(16,4))\n",
    "librosa.display.waveplot(y, sr=sr)\n",
    "\n",
    "ipd.Audio(y, rate=sr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An important feature we want to extract from the audio is **tempo** (i.e. the time interval between steps). Let's estimate that using the `librosa.beat.tempo` method (which requires us to first detect **onsets**, or []):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def estimate_tempo(y, sr, start_bpm=120.0):\n",
    "    # Estimate tempo\n",
    "    onset_env = librosa.onset.onset_strength(y, sr=sr) # TODO: Compare this with librosa.beat.beat_track\n",
    "    tempo = librosa.beat.tempo(y, sr=sr, onset_envelope=onset_env, start_bpm=start_bpm)\n",
    "    \n",
    "    return float(tempo)\n",
    "\n",
    "tempo = estimate_tempo(y, sr)\n",
    "print(\"Tempo (calculated): {}\".format(tempo))\n",
    "tempo = 93.0 # Hard-coded from prior knowledge\n",
    "print(\"Tempo (hard-coded): {}\".format(tempo))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\"color:gray\">\n",
    "(We can see that the tempo we've estimated differs by approximately 1BPM from the tempo that we've hard-coded from prior knowledge.\n",
    "\n",
    "It's often the case that such automatic feature extraction tools and algorithms require a fair bit of fine-tuning, so we can improve our results by supplying some user-defined parameters, especially when using them out of the box like we are here. The variables `hop_length` and `tempo` are two such parameters in this case.\n",
    "\n",
    "However, the more parameters we define manually, the less flexible our overall system becomes, so it's a tradeoff between accuracy and robustness.)\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.2 From tempo to beats\n",
    "\n",
    "From the tempo we can calculate the times of every **beat** in the song (assuming the tempo is consistent, which in this case it is):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# Calculate beat times\n",
    "def calculate_beat_times(y, sr, tempo):\n",
    "    # Calculate params based on input\n",
    "    T = len(y)/float(sr) # Total audio length in seconds\n",
    "    seconds_per_beat = 60.0/tempo\n",
    "\n",
    "    # Start beat at first onset rather than time 0\n",
    "    # TODO: Let this first onset also be user-supplied for more accurate results\n",
    "    beat_times = np.arange(detect_first_onset_time(y, sr), T, seconds_per_beat)\n",
    "    \n",
    "    return beat_times\n",
    "\n",
    "# Detect first onset\n",
    "def detect_first_onset_time(y, sr, hop_length=1024):\n",
    "    onset_frames = librosa.onset.onset_detect(y, sr=sr, hop_length=hop_length)\n",
    "    onset_times = librosa.frames_to_time(onset_frames)\n",
    "    return onset_times[0]\n",
    "\n",
    "beat_times = calculate_beat_times(y, sr, tempo)\n",
    "print(\"First 10 beat times (in seconds): {}\".format(beat_times[:10]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And let's listen to our extracted beats with the original audio track:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Listen to beat clicks (i.e. a metronome)\n",
    "beat_clicks = librosa.clicks(times=beat_times, sr=sr, length=len(y))\n",
    "\n",
    "# Plot waveform and beats\n",
    "plt.figure(figsize=(16,4))\n",
    "librosa.display.waveplot(y, sr=sr)\n",
    "plt.vlines(beat_times, -0.25, 0.25, color=\"r\")\n",
    "\n",
    "ipd.Audio(y + beat_clicks, rate=sr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.3 From beats to measures\n",
    "\n",
    "In order to map our *tresillo* rhythm to the audio in a musically meaningful way, we'll need to group beats into **measures**. From listening to the above example we can hear that every beat corresponds to a quarter note; thus, we'll set `beats_per_measure` to 4:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "beats_per_measure = 4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using `beats_per_measure` we can calculate the times for the start of each measure:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Calculate measure indices in samples\n",
    "def calculate_measure_samples(y, beat_samples, beats_per_measure):\n",
    "    max_samples = len(y)\n",
    "    start_sample = beat_samples[0]\n",
    "    beat_interval = beat_samples[1] - beat_samples[0]\n",
    "    measure_interval = beat_interval * beats_per_measure\n",
    "    if measure_interval >= beat_interval:\n",
    "        return np.array(beat_samples[::beats_per_measure], dtype=\"int\")\n",
    "    else:\n",
    "        beat_indices = np.indices([len(beat_samples)])[0]\n",
    "        measure_indices = np.indices([len(beat_samples)/beats_per_measure])[0]\n",
    "        return np.interp(measure_indices, beat_indices/beats_per_measure, beat_samples)\n",
    "\n",
    "# Work in samples from here on\n",
    "beat_samples = librosa.time_to_samples(beat_times, sr=sr)\n",
    "measure_samples = calculate_measure_samples(y, beat_samples, beats_per_measure)\n",
    "\n",
    "print(\"First 10 measure samples: {}\".format(measure_samples[:10]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that we're working in samples now, as this is the unit that the audio data is actually stored in; when we loaded up the audio track, we essentially read in a large array of samples. The sample *rate*, which we defined as `sr`, tells us how many samples there are per second.\n",
    "\n",
    "Thus, it's a simple matter to convert samples to times whenever we need to:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "measure_times = librosa.samples_to_time(measure_samples, sr=sr)\n",
    "print(\"First 10 measure times (in seconds): {}\".format(measure_times[:10], sr=sr))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can visualize, and listen to, the measure and beat markers along with the original waveform:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Add clicks, then plot and listen\n",
    "plt.figure(figsize=(16, 4))\n",
    "librosa.display.waveplot(y, sr=sr)\n",
    "\n",
    "plt.vlines(measure_times, -1, 1, color=\"r\")\n",
    "plt.vlines(beat_times, -0.5, 0.5, color=\"r\")\n",
    "\n",
    "measure_clicks = librosa.clicks(times=measure_times, sr=sr, click_freq=3000.0, length=len(y))\n",
    "ipd.Audio(y + measure_clicks + beat_clicks, rate=sr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 3.4 Putting it all together: mapping symbolic rhythms to audio signals\n",
    "\n",
    "With our knowledge of the song's tempo, beats, and measures, we can start bringing our symbolic rhythms into audio-land. Again, let's work with our trusty *tresillo* rhythm:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "print(\"Tresillo rhythm: {}\\n\"\n",
    "      \"{} pulses, {} steps\".format(tresillo_rhythm, tresillo_num_pulses, tresillo_num_steps))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For this example, we want the rhythm to last an entire measure as well, so we'll set `steps_per_measure` to be the number of steps in the rhythm (in this case, 8):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "steps_per_measure = tresillo_num_steps\n",
    "steps_per_measure"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With these markers in place, we can now overlay the *tresillo* rhythm onto each measure and listen to the result:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "\"\"\"Generating clicks for tresillo rhythm at the proper tempo and start time,\n",
    "   to overlay onto an audio track\"\"\"\n",
    "def generate_rhythm_overlay(rhythm, measure_samples, steps_per_measure, sr):\n",
    "    # Calculate click interval\n",
    "    measure_length = measure_samples[1]-measure_samples[0]\n",
    "    # click_tempo = tempo * (steps_per_measure/float(beats_per_measure))\n",
    "    # click_interval = 60.0/click_tempo\n",
    "    measure_length_seconds = librosa.samples_to_time(measure_length, sr=sr)\n",
    "    click_interval = measure_length_seconds / float(steps_per_measure)\n",
    "\n",
    "    # Generate click times for single measure\n",
    "    pulse_times_measure, step_times_measure = generate_rhythm_times(rhythm, click_interval)\n",
    "\n",
    "    # Generate clicks for single measure\n",
    "    pulse_clicks_measure, step_clicks_measure = generate_rhythm_clicks(rhythm, click_interval, sr=sr)\n",
    "\n",
    "    # Concatenate clicks and click times for all measures\n",
    "    pulse_times, step_times, pulse_clicks, step_clicks = np.array([]), np.array([]), np.array([]), np.array([])\n",
    "    for s in measure_samples:\n",
    "        t = float(librosa.samples_to_time(s, sr=sr))\n",
    "        pulse_clicks = np.hstack((pulse_clicks, pulse_clicks_measure))\n",
    "        step_clicks = np.hstack((step_clicks, step_clicks_measure))\n",
    "        pulse_times = np.hstack((pulse_times, pulse_times_measure + t))\n",
    "        step_times = np.hstack((step_times, step_times_measure + t))\n",
    "\n",
    "    # Offset clicks by first onset\n",
    "    pulse_clicks = np.hstack((np.zeros(measure_samples[0]), pulse_clicks))\n",
    "    step_clicks = np.hstack((np.zeros(measure_samples[0]), step_clicks))\n",
    "    \n",
    "    return (pulse_times, step_times, pulse_clicks, step_clicks)\n",
    "\n",
    "\"\"\"Visualizing and hearing the result\"\"\"\n",
    "def overlay_rhythm_onto_audio(rhythm, audio_samples, measure_samples, sr=44100, click_colors={\"measure\": \"r\",\n",
    "                                                                                              \"pulse\": \"r\",\n",
    "                                                                                              \"step\": \"r\"}):\n",
    "    \n",
    "    # Get overlay data\n",
    "    pulse_times, step_times, pulse_clicks, step_clicks = generate_rhythm_overlay(rhythm,\n",
    "                                                                                 measure_samples,\n",
    "                                                                                 len(rhythm),\n",
    "                                                                                 sr)\n",
    "    measure_times = librosa.samples_to_time(measure_samples, sr=sr)\n",
    "    measure_clicks = librosa.clicks(times=measure_times, sr=sr, click_freq=3000.0, length=len(audio_samples))\n",
    "    \n",
    "    # Calculate max length in samples\n",
    "    available_lengths = [len(audio_samples), len(measure_clicks), len(pulse_clicks), len(step_clicks)]\n",
    "    length_samples = min(available_lengths)\n",
    "    \n",
    "    # Plot original waveform\n",
    "    plt.figure(figsize=(16, 4))\n",
    "    librosa.display.waveplot(audio_samples, sr=sr, alpha=0.5)\n",
    "    \n",
    "    # Plot rhythm clicks\n",
    "    plt.vlines(measure_times, -1, 1, color=click_colors[\"measure\"])\n",
    "    plt.vlines(pulse_times, -0.5, 0.5, color=click_colors[\"pulse\"])\n",
    "    plt.vlines(step_times, -0.25, 0.25, color=click_colors[\"step\"], alpha=0.75)\n",
    "    \n",
    "    # Play both clicks together with audio track\n",
    "    concatenated_audio_samples = ((audio_samples[:length_samples]*2.0)\n",
    "                                  + (measure_clicks[:length_samples]*0.25)\n",
    "                                  + (pulse_clicks[:length_samples]*0.25)\n",
    "                                  + (step_clicks[:length_samples]*0.25))\n",
    "    audio_display = ipd.Audio(concatenated_audio_samples, rate=sr)\n",
    "    return audio_display\n",
    "\n",
    "\n",
    "overlay_rhythm_onto_audio(tresillo_rhythm, y, measure_samples, sr=sr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The clicks for measures, pulses, and steps, overlap with each other at certain points. While you can hear this based on the fact that each click is at a different frequency, it can be hard to tell visually in the above figure. We can make this more apparent by plotting each set of clicks with a different color.\n",
    "\n",
    "In the below figure, each measure is denoted by a large <span style=\"color:red\">red</span> line, each pulse by a medium <span style=\"color:green\">green</span> line, and each step by a small <span style=\"color:blue\">blue</span> line."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "overlay_rhythm_onto_audio(tresillo_rhythm, y, measure_samples, sr=sr, click_colors={\"measure\": \"r\",\n",
    "                                                                                    \"pulse\": \"g\",\n",
    "                                                                                    \"step\": \"b\"})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can hear that the *tresillo* rhythm's pulses line up with the harmonic rhythm of \"Human Nature\"; generally, we want to pick rhythms and audio tracks that have at least some kind of musical relationship.\n",
    "\n",
    "(We could actually try to estimate rhythmic patterns based on onsets and tempo, but that's for another time.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 4 - Time-stretching audio\n",
    "\n",
    "Now that we've put the symbolic rhythm and source audio together, we're ready to begin manipulating the audio and doing some actual stretching!\n",
    "\n",
    "### 4.1 Target rhythms\n",
    "\n",
    "First, we'll define the **target** rhythm that we want the audio to be mapped to:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "original_rhythm = tresillo_rhythm\n",
    "target_rhythm = fibonacci_scale_rhythm(original_rhythm, 1) # \"Fibonacci scale\" original rhythm by a factor of 1\n",
    "print(\"Original rhythm: {}\\n\"\n",
    "      \"Target rhythm:   {}\".format(original_rhythm, target_rhythm))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2 Pulse ratios\n",
    "\n",
    "Given an original rhythm and target rhythm, we can compute their **pulse ratios**, that is, the ratio between each of their pulses:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Calculate ratios between pulses for two rhythm sequences\n",
    "# NOTE: This assumes that both rhythm sequences have the same number of pulses!\n",
    "def calculate_pulse_ratios(original_rhythm, target_rhythm):\n",
    "    original_pulse_lengths = calculate_pulse_lengths(original_rhythm)\n",
    "    target_pulse_lengths = calculate_pulse_lengths(target_rhythm)\n",
    "    num_pulses = min(len(original_pulse_lengths), len(target_pulse_lengths))\n",
    "    pulse_ratios = np.array([original_pulse_lengths[i]/float(target_pulse_lengths[i]) for i in range(num_pulses)])\n",
    "    return pulse_ratios\n",
    "\n",
    "print(\"Pulse ratios: {}\".format(calculate_pulse_ratios(original_rhythm, target_rhythm)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3 Modifying measures by time-stretching\n",
    "\n",
    "Since we're treating our symbolic rhythms as having the duration of one measure, it makes sense to start by modifying a single measure.\n",
    "\n",
    "Basically what we want to do is: for each pulse, get the audio chunk that maps to that pulse, and time-stretch it based on our calculated pulse ratios.\n",
    "\n",
    "Below is an implementation of just that. It's a bit long, but that's mostly due to having to define several properties to do with rhythm and audio. The core idea, of individually stretching the pulses, remains the same:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Modify a single measure\n",
    "def modify_measure(data, original_rhythm, target_rhythm, stretch_method):\n",
    "    modified_data = np.array([])\n",
    "    \n",
    "    # Define the rhythmic properties we'll use\n",
    "    original_num_samples = len(data)\n",
    "    original_num_steps = len(original_rhythm)\n",
    "    target_num_steps = len(target_rhythm)\n",
    "    \n",
    "    # Get indices of steps for measure\n",
    "    original_step_interval = original_num_samples / float(original_num_steps)\n",
    "    original_step_indices = np.arange(0, original_num_samples, original_step_interval, dtype=\"int\")\n",
    "    \n",
    "    # Get only indices of pulses based on rhythm\n",
    "    original_pulse_indices = np.array([original_step_indices[i] for i in range(original_num_steps) if original_rhythm[i] > 0])\n",
    "    \n",
    "    # Calculate pulse ratios\n",
    "    pulse_ratios = calculate_pulse_ratios(original_rhythm, target_rhythm)\n",
    "    \n",
    "    # Calculate pulse lengths\n",
    "    original_pulse_lengths = calculate_pulse_lengths(original_rhythm)\n",
    "    target_pulse_lengths = calculate_pulse_lengths(target_rhythm)\n",
    "    \n",
    "    # Concatenate time-stretched versions of rhythm's pulses\n",
    "    for i,p in enumerate(original_pulse_indices):\n",
    "        # Get pulse sample data; samples between current and next pulse, or if it's the final pulse,\n",
    "        # samples between pulse and end of audio\n",
    "        pulse_start = p\n",
    "        pulse_stop = len(data)-1\n",
    "        if i < len(original_pulse_indices)-1:\n",
    "            pulse_stop = original_pulse_indices[i+1]        \n",
    "        pulse_samples = data[pulse_start:pulse_stop]\n",
    "\n",
    "        # Time-stretch this step based on ratio of old to new rhythm length\n",
    "        # TODO: Try out other methods of manipulation, such as using onset detection in addition to steps and pulses\n",
    "        if stretch_method == \"timestretch\":\n",
    "            pulse_samples = librosa.effects.time_stretch(pulse_samples, pulse_ratios[i])\n",
    "        elif stretch_method == \"euclidean\":\n",
    "            pulse_samples = euclidean_stretch(pulse_samples,\n",
    "                                              original_pulse_lengths[i],\n",
    "                                              target_pulse_lengths[min(i, len(target_pulse_lengths)-1)])\n",
    "        else:\n",
    "            print(\"ERROR: Invalid stretch method {}\".format(stretch_method))\n",
    "        \n",
    "        # Add the samples to our modified audio time series\n",
    "        modified_data = np.hstack((modified_data, pulse_samples))\n",
    "    \n",
    "    # Time-stretch entire measure to maintain original measure length (so that it sounds more natural)\n",
    "    stretch_multiplier = len(modified_data)/float(len(data))\n",
    "    modified_data = librosa.effects.time_stretch(modified_data, stretch_multiplier)\n",
    "    \n",
    "    return modified_data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You'll notice that in the part where we choose stretch methods, there's a function called `euclidean_stretch` that we haven't defined. We'll get to that in just a second! For now, let's just put a stub there:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Euclidean stretch STUB\n",
    "def euclidean_stretch(pulse_samples, original_pulse_length, target_pulse_length):\n",
    "    return pulse_samples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... so that we can hear what our modification method sounds like when applied to the first measure of \"Human Nature\":"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "first_measure_data = y[measure_samples[0]:measure_samples[1]]\n",
    "first_measure_modified = modify_measure(first_measure_data,\n",
    "                                        original_rhythm, target_rhythm,\n",
    "                                        stretch_method=\"timestretch\")\n",
    "ipd.Audio(first_measure_modified, rate=sr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It doesn't sound like there's much difference between the stretched version and the original, does it?\n",
    "\n",
    "### 4.4 Modifying an entire track by naively time-stretching each pulse\n",
    "\n",
    "To get a better sense, let's apply the modification to the entire audio track:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Modify an entire audio track; basically just loops through a track's measures\n",
    "# and calls modify_measure() on each measure\n",
    "def modify_track(data, measure_samples, original_rhythm, target_rhythm, stretch_method=\"timestretch\"):\n",
    "    modified_track_data = np.zeros(measure_samples[0])\n",
    "    modified_measure_samples = np.array([], dtype=\"int\")\n",
    "    for i, sample in enumerate(measure_samples[:-1]):\n",
    "        modified_measure_samples = np.hstack((modified_measure_samples, len(modified_track_data)))\n",
    "        measure_start = measure_samples[i]\n",
    "        measure_stop = measure_samples[i+1]\n",
    "        measure_data = data[measure_start:measure_stop]\n",
    "        modified_measure_data = modify_measure(measure_data, original_rhythm, target_rhythm, stretch_method)\n",
    "        modified_track_data = np.hstack((modified_track_data, modified_measure_data))\n",
    "    return (modified_track_data, modified_measure_samples)\n",
    "\n",
    "# Modify the track using naive time-stretch\n",
    "y_modified, measure_samples_modified = modify_track(y, measure_samples,\n",
    "                                                    original_rhythm, target_rhythm,\n",
    "                                                    stretch_method=\"timestretch\")\n",
    "\n",
    "plt.figure(figsize=(16,4))\n",
    "librosa.display.waveplot(y_modified, sr=sr)\n",
    "ipd.Audio(y_modified, rate=sr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Listening to the whole track, only perceptible difference is that the last two beats of each measure are *slightly* faster. If we look at the pulse ratios again:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print(calculate_pulse_ratios(original_rhythm, target_rhythm))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... we can see that this makes sense, as we're time-stretching the first two pulses by the same amount, and then time-stretching the last pulse by a different amount.\n",
    "\n",
    "(Note that while we're expanding our original rhythm along the Fibonacci sequence, this actually corresponds to a *contraction* when time-stretching. This is because we want to maintain the original tempo, so we're trying to fit more steps into the same timespan.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.5 Overlaying target rhythm clicks\n",
    "\n",
    "We can get some more insight if we sonify the target rhythm's clicks and overlay it onto our modified track:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "overlay_rhythm_onto_audio(target_rhythm, y_modified, measure_samples, sr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This gets to the heart of the problem: when we time-stretch an entire pulse this way, we retain the original pulse's internal rhythm, essentially creating a polyrhythm in the target pulse's step (i.e. metrical) structure. Even though we're time-stretching each pulse, we don't hear a difference because *everything* within the pulse gets time-stretched by the same amount."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 5 - Euclidean stretch"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Listening to the rendered track in [Part 4.5](#4.5-Overlaying-target-rhythm-clicks), you can hear that aside from the beginning of each measure and pulse, the musical onsets in the modified track don't really line up with the target rhythm's clicks at all. Thus, without the clicks, we have no way to identify the target rhythm, even though that's what we were using as the basis of our stretch method!\n",
    "\n",
    "So how do we remedy this?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.1 Subdividing pulses\n",
    "\n",
    "We dig deeper. That is, we can treat each *pulse* as a rhythm of its own, and subdivide it accordingly, since each pulse is comprised of multiple steps after all."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "print(\"Original rhythm: {}\\n\"\n",
    "      \"Target rhythm:   {}\".format(original_rhythm, target_rhythm))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Looking at the first pulses of the original rhythm and target rhythm, we want to turn\n",
    "\n",
    "`[1 0 0]`\n",
    "\n",
    "into\n",
    "\n",
    "`[1 0 0 0 0]`.\n",
    "\n",
    "To accomplish this, we'll turn to the concept of **Euclidean rhythms**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.2 Generating Euclidean rhythms using Bjorklund's algorithm\n",
    "A Euclidean rhythm is a type of rhythm that can be generated based upon the Euclidean algorithm for calculating the greatest common divisor of two numbers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def euclid(a, b):\n",
    "    m = max(a, b)\n",
    "    k = min(a, b)\n",
    "    \n",
    "    if k==0:\n",
    "        return m\n",
    "    else:\n",
    "        return euclid(k, m%k)\n",
    "\n",
    "print(\"Greatest common divisor of 8 and 12 is {}\".format(euclid(8, 12)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The concept of Euclidean rhythms was first introduced by Godfried Toussaint in his 2004 paper [The Euclidean Algorithm Generates Traditional Musical Rhythms](http://cgm.cs.mcgill.ca/~godfried/publications/banff.pdf).\n",
    "\n",
    "The algorithm for generating these rhythms is actually **Bjorklund's algorithm**, first described by E. Bjorklund in his 2003 paper [The Theory of Rep-Rate Pattern Generation in the SNS Timing System](https://ics-web.sns.ornl.gov/timing/Rep-Rate%20Tech%20Note.pdf), which deals with neutron accelerators in nuclear physics. Here we use Brian House's Python implementation of Bjorklund's algorithm; you can find the source code on [GitHub](https://github.com/brianhouse/bjorklund).\n",
    "\n",
    "It turns out that our *tresillo* rhythm is an example of a Euclidean rhythm. We can generate it by plugging in the number of pulses and steps into Bjorklund's algorithm:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "print(np.array(bjorklund.bjorklund(pulses=3, steps=8)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.3 Using Euclidean rhythms to subdivide pulses\n",
    "\n",
    "Say we want to stretch a pulse `[1 0 0]` so that it resembles another pulse `[1 0 0 0 0]`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "original_pulse = np.array([1,0,0])\n",
    "target_pulse = np.array([1,0,0,0,0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We want to know how much to stretch each subdivision. To do this, we'll convert these single pulses into rhythms of their own. First, we'll treat each step in the original pulse as an onset:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "original_pulse_rhythm = np.ones(len(original_pulse), dtype=\"int\")\n",
    "print(original_pulse_rhythm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And as mentioned before, we'll use Bjorklund's algorithm to generate the target pulse's rhythm. The trick here is to use the number of *steps* in the original pulse as the number of *pulses* for the target pulse rhythm (hence the conversion to onsets earlier):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "target_pulse_rhythm = np.array(bjorklund.bjorklund(pulses=len(original_pulse), steps=len(target_pulse)))\n",
    "print(target_pulse_rhythm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You might have noticed that this rhythm is exactly the same as the rhythm produced by contracting the *tresillo* rhythm along the Fibonacci sequence by a factor of 1:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print(fibonacci_scale_rhythm(tresillo_rhythm, -1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And it's true that there is some significant overlap between Euclidean rhythms and Fibonacci rhythms. The advantage of working with Euclidean rhythms here is that they work with any number of pulses and steps, not just ones that are Fibonacci numbers.\n",
    "\n",
    "To summarize:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "print(\"In order to stretch pulse-to-pulse {} --> {}\\n\"\n",
    "      \"we subdivide and stretch rhythms   {} --> {}\".format(original_pulse, target_pulse,\n",
    "                                                            original_pulse_rhythm, target_pulse_rhythm))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The resulting pulse ratios are:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "print(calculate_pulse_ratios(original_pulse_rhythm, target_pulse_rhythm))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "... which doesn't intuitively look like it would produce something any different from what we tried before. However, we might perceive a greater difference because:\n",
    "\n",
    "a) we're working on a more granular temporal level (subdivisions of pulses as opposed to measures), and\n",
    "\n",
    "b) we're adjusting an equally-spaced rhythm (e.g. `[1 1 1]`) to one that's not necessarily equally-spaced (e.g. `[1 0 1 0 1]`)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.4 The Euclidean stretch algorithm\n",
    "\n",
    "With all this in mind, we can now implement **Euclidean stretch**:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Euclidean stretch for modifying a single pulse (basically time-stretching subdivisions based on Euclidean rhythms)\n",
    "def euclidean_stretch(pulse_samples, original_pulse_length, target_pulse_length):\n",
    "    target_pulse_samples = np.array([])\n",
    "    \n",
    "    # Return empty samples array if target pulse length < 1\n",
    "    if target_pulse_length < 1:\n",
    "        return target_pulse_samples\n",
    "\n",
    "    # Ensure original pulse rhythm (\"opr\") has length equal to or less than target_pulse_length\n",
    "\n",
    "    # ... by using target pulse length\n",
    "    # original_pulse_length = min(original_pulse_length, target_pulse_length)\n",
    "    \n",
    "    # ... by using divisors of original pulse length\n",
    "    # if original_pulse_length > target_pulse_length:\n",
    "    #     # print(\"WARNING: original_pulse_length {} \"\n",
    "    #     #       \"is greater than target_pulse_length {}\".format(original_pulse_length,\n",
    "    #     #                                                       target_pulse_length))\n",
    "    #     for i in range(1, original_pulse_length+1):\n",
    "    #         opl_new = int(original_pulse_length / float(i))\n",
    "    #         if opl_new <= target_pulse_length:\n",
    "    #             original_pulse_length = opl_new\n",
    "    #             # print(\"original_pulse_length is now {}\".format(original_pulse_length))\n",
    "    #             break\n",
    "\n",
    "    # ... by using lowest common multiple as target pulse length\n",
    "    if original_pulse_length > target_pulse_length:\n",
    "        # print(\"Target pulse length before: {}\".format(target_pulse_length))\n",
    "        gcd = euclid(original_pulse_length, target_pulse_length)\n",
    "        lcm = (original_pulse_length*target_pulse_length) / gcd\n",
    "        target_pulse_length = lcm\n",
    "        # print(\"Target pulse length after: {}\".format(target_pulse_length))\n",
    "        # original_pulse_length = target_pulse_length\n",
    "    \n",
    "    opr = np.ones(original_pulse_length, dtype=\"int\")\n",
    "\n",
    "    # Generate target pulse rhythm (\"tpr\")\n",
    "    tpr = bjorklund.bjorklund(pulses=original_pulse_length, steps=target_pulse_length)\n",
    "    tpr_pulse_lengths = calculate_pulse_lengths(tpr)\n",
    "    tpr_pulse_ratios = calculate_pulse_ratios(opr, tpr)\n",
    "    \n",
    "    # Subdivide (i.e. segment) the pulse based on original pulse length\n",
    "    pulse_subdivision_step = int(len(pulse_samples) / float(original_pulse_length))\n",
    "    pulse_subdivision_indices = np.arange(0, len(pulse_samples), pulse_subdivision_step, dtype=\"int\")\n",
    "    pulse_subdivision_indices = pulse_subdivision_indices[:original_pulse_length]\n",
    "\n",
    "    # Time-stretch each subdivision based on ratios\n",
    "    for i,si in enumerate(pulse_subdivision_indices):\n",
    "        subdivision_start = si\n",
    "        subdivision_stop = len(pulse_samples) - 1\n",
    "        if i < len(pulse_subdivision_indices)-1:\n",
    "            subdivision_stop = pulse_subdivision_indices[i+1]        \n",
    "        pulse_subdivision_samples = pulse_samples[subdivision_start:subdivision_stop]        \n",
    "    \n",
    "        # Stretch the relevant subdivisions based on target pulse rhythm\n",
    "        pulse_subdivision_samples = librosa.effects.time_stretch(pulse_subdivision_samples, tpr_pulse_ratios[i])\n",
    "        \n",
    "        # Concatenate phrase\n",
    "        target_pulse_samples = np.hstack((target_pulse_samples, pulse_subdivision_samples))\n",
    "    \n",
    "    return target_pulse_samples"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's take a listen to how it sounds:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "# Modify the track\n",
    "y_modified, measure_samples_modified = modify_track(y, measure_samples,\n",
    "                                                    original_rhythm, target_rhythm,\n",
    "                                                    stretch_method=\"euclidean\")\n",
    "\n",
    "plt.figure(figsize=(16,4))\n",
    "librosa.display.waveplot(y_modified, sr=sr)\n",
    "ipd.Audio(y_modified, rate=sr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Much better! With clicks:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "overlay_rhythm_onto_audio(target_rhythm, y_modified, measure_samples, sr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can hear, the modified track's rhythm is in line with the clicks, and sounds noticeably different from the original song. This is a pretty good place to end up!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 6 - Fibonacci stretch: implementation and examples\n",
    "\n",
    "### 6.1 Implementation\n",
    "\n",
    "Here's an end-to-end implementation of Fibonacci stretch. A lot of the default parameters have been set to the ones we've been using in this notebook, although of course you can pass in your own:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def fibonacci_stretch_track(audio_filepath,\n",
    "                            sr=44100,\n",
    "                            original_rhythm=np.array([1,0,0,1,0,0,1,0], dtype=\"int\"),\n",
    "                            stretch_method=\"euclidean\",\n",
    "                            stretch_factor=1,\n",
    "                            target_rhythm=None,\n",
    "                            tempo=None,\n",
    "                            beats_per_measure=4,\n",
    "                            hop_length=1024,\n",
    "                            overlay_clicks=False,\n",
    "                            render_track=True):    \n",
    "    # Load input audio\n",
    "    y, sr = librosa.load(audio_filepath, sr=sr)\n",
    "    \n",
    "    # Extract rhythm features from audio\n",
    "    if tempo is None:\n",
    "        tempo = estimate_tempo(y, sr)\n",
    "    beat_times = calculate_beat_times(y, sr, tempo)\n",
    "    beat_samples = librosa.time_to_samples(beat_times, sr=sr)\n",
    "    measure_samples = calculate_measure_samples(y, beat_samples, beats_per_measure)\n",
    "    \n",
    "    # Generate target rhythm\n",
    "    if target_rhythm is None:\n",
    "        target_rhythm = fibonacci_scale_rhythm(original_rhythm, stretch_factor)\n",
    "        \n",
    "    # Modify the track\n",
    "    y_modified, measure_samples_modified = modify_track(y, measure_samples,\n",
    "                                                        original_rhythm, target_rhythm,\n",
    "                                                        stretch_method=\"euclidean\")\n",
    "\n",
    "    # Render the modified track...\n",
    "    if render_track:\n",
    "        if overlay_clicks:\n",
    "            return overlay_rhythm_onto_audio(target_rhythm, y_modified, measure_samples_modified, sr)\n",
    "        else:\n",
    "            plt.figure(figsize=(16,4))\n",
    "            librosa.display.waveplot(y_modified, sr=sr)\n",
    "            return ipd.Audio(y_modified, rate=sr)\n",
    "    # ... or return modified track and measure samples\n",
    "    else:\n",
    "        return (y_modified, measure_samples_modified)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can simply feed the function a path to an audio file (as well as any parameters we want to customize).\n",
    "\n",
    "This is the exact method that's applied to the [sneak peek at the final result](#A-sneak-peek-at-the-final-result) up top. The only difference is that we use a 90-second excerpt rather than our original 30-second one:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# \"Human Nature\" stretched by a factor of 1 using default parameters\n",
    "fibonacci_stretch_track(\"../data/humannature_90s.mp3\",\n",
    "                        stretch_factor=1,\n",
    "                        tempo=93.0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And indeed we get the exact same result."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.2 Examples: customizing stretch factors\n",
    "\n",
    "Now that we have a function to easily stretch tracks, we can begin playing around with some of the parameters.\n",
    "\n",
    "Here's the 30-second \"Human Nature\" excerpt again, only this time it's stretched by a factor of 2 instead of 1:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# \"Human Nature\" stretched by a factor of 2\n",
    "fibonacci_stretch_track(\"../data/humannature_30s.mp3\",\n",
    "                        tempo=93.0,\n",
    "                        stretch_factor=2,\n",
    "                        overlay_clicks=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As mentioned in [part 2.2](#2.2-Using-Fibonacci-numbers-to-manipulate-rhythms), we can contract rhythms as well using negative numbers as our `stretch_factor`. Let's try that with \"[Chan Chan](https://open.spotify.com/track/7DqTaelFf846rl1CHmyfOW)\" by the Buena Vista Social Club:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "# \"Chan Chan\" stretched by a factor of -1\n",
    "fibonacci_stretch_track(\"../data/chanchan_30s.mp3\",\n",
    "                        stretch_factor=-1,\n",
    "                        tempo=78.5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(Note that although we do end up with a perceptible difference (the song now sounds like it's in 7/8), it should actually sound like it's in 5/8, since `[1 0 0 1 0 0 1 0]` is getting compressed to `[1 0 1 0 1]`. This is an implementation detail with the Euclidean stretch method that I need to fix.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.3 Examples: customizing original and target rhythms\n",
    "\n",
    "In order to get musically meaningful results we generally want to supply parameters that make musical sense with our input audio (although it can certainly be interesting to try with parameters that don't!). One of the parameters that makes the most difference in results is the rhythm sequence used to represent each measure.\n",
    "\n",
    "Here's Chance the Rapper's verse from DJ Khaled's \"[I'm the One](https://www.youtube.com/watch?v=weeI1G46q0o&t=2m28s)\", with a custom `original_rhythm` that matches the bassline of the song:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# \"I'm the One\" stretched by a factor of 1\n",
    "fibonacci_stretch_track(\"../data/imtheone_cropped_chance_60s.mp3\",\n",
    "                        tempo=162,\n",
    "                        original_rhythm=np.array([1,0,0,0,0,1,0,0]),\n",
    "                        stretch_factor=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can define both a custom target rhythm as well. In addition, neither `original_rhythm` nor `target_rhythm` have to be Fibonacci rhythms for the stretch algorithm to work (although with this implementation they do both have to have the same number of pulses).\n",
    "\n",
    "Let's try that out with the same verse, going from an original rhythm with 8 steps (i.e. in 4/4 meter) to a target rhythm with 10 steps (i.e. in 5/4 meter):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# \"I'm the One\" in 5/4\n",
    "fibonacci_stretch_track(\"../data/imtheone_cropped_chance_60s.mp3\",\n",
    "                        tempo=162,\n",
    "                        original_rhythm=np.array([1,0,0,0,0,1,0,0]),\n",
    "                        target_rhythm=np.array([1,0,0,0,0,1,0,0,0,0]),\n",
    "                        overlay_clicks=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As another example, we can give a swing feel to the first movement of Mozart's \"[Eine kleine Nachtmusik](https://imslp.org/wiki/Special:ImagefromIndex/324337/hfpn)\" (K. 525), as performed by A Far Cry:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# \"Eine kleine Nachtmusik\" with a swing feel\n",
    "fibonacci_stretch_track(\"../data/einekleinenachtmusik_30s.mp3\",\n",
    "                        tempo=130,\n",
    "                        original_rhythm=np.array([1,0,1,1]),\n",
    "                        target_rhythm=np.array([1,0,0,1,0,1]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It works pretty decently until around `0:09`, at which point the assumption of a metronomically consistent tempo breaks down. (This is one of the biggest weaknesses with the current implementation, and is something I definitely hope to work on in the future.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's also hear what \"Chan Chan\" sounds like in 5/4:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# \"Chan Chan\" in 5/4\n",
    "fibonacci_stretch_track(\"../data/chanchan_30s.mp3\",\n",
    "                        tempo=78.5,\n",
    "                        original_rhythm=np.array([1,0,0,1,0,0,0,0]),\n",
    "                        target_rhythm=np.array([1,0,0,0,0,1,0,0,0,0])) # Also interesting to try with [1,0,1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 6.4 Examples: customizing input beats per measure\n",
    "\n",
    "We can also work with source audio in other meters. For example, Frank Ocean's \"[Pink + White](https://open.spotify.com/track/3xKsf9qdS1CyvXSMEid6g8)\" is in 6/8. Here I've stretched it into 4/4 using the rhythm of the bassline, but you can uncomment the other supplied parameters (or supply your own!) to hear how they sound as well:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# \"Pink + White\" stretched by a factor of 1\n",
    "fibonacci_stretch_track(\"../data/pinkandwhite_30s.mp3\",\n",
    "                        beats_per_measure=6,\n",
    "                        tempo=160,\n",
    "                        \n",
    "                        # 6/8 to 4/4 using bassline rhythm\n",
    "                        original_rhythm=np.array([1,1,1,1,0,0]),\n",
    "                        target_rhythm=np.array([1,1,1,0,1,0,0,0]),\n",
    "                        \n",
    "                        # 6/8 to 4/4 using half notes\n",
    "                        # original_rhythm=np.array([1,0,0,1,0,0]),\n",
    "                        # target_rhythm=np.array([1,0,0,0,1,0,0,0]),\n",
    "                        \n",
    "                        # 6/8 to 10/8 (5/4) using Fibonacci stretch factor of 1\n",
    "                        # original_rhythm=np.array([1,0,0,1,0,0]),\n",
    "                        # stretch_factor=1,\n",
    "                        \n",
    "                        overlay_clicks=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Part 7 - Final thoughts\n",
    "\n",
    "This notebook started out as an answer to the question \"What if we applied rhythmic expansion methods, based on the Fibonacci sequence, to actual audio tracks?\"\n",
    "\n",
    "It quickly grew into more and more, and we now have a working implementation of what I've dubbed Fibonacci stretch. Along the way I've come to a few conclusions that I'll go over:\n",
    "\n",
    "### 7.1 Fibonacci stretch as a creative tool\n",
    "\n",
    "I think there's certainly a case to be made for Fibonacci stretch as an interesting and useful means of musical transformation; it's rooted in mathematical processes that have been shown to produce interesting artistic output, and [Part 6](#6.-Fibonacci-stretch-implementation-and-examples) shows that Fibonacci itself can produce musically interesting results.\n",
    "\n",
    "However, it has its limits as well, the main one being that the Fibonacci sequence grows at an exponential rate (with the rate actually being equal to the golden ratio). This means that above a certain `stretch_factor` value, Fibonacci stretch starts to feel somewhat impractical. For example, stretching `[1 0 0 1 0 0 1 0]` by a factor of 6 gives us a target rhythm with 144 steps, which isn't something we can easily perceive when crammed into the space of our original 8 steps.\n",
    "\n",
    "One solution to this imperceptibility is to allow for the length of the modified measure to change as well. For example, a 2-second measure with 8 steps (4 steps/second) could be stretched into a 24-second measure with 144 steps (6 steps/second). The longer time span might yield more interesting results, but it might also obscure the relationship between the modified track and the original track.\n",
    "\n",
    "\n",
    "### 7.2 Rhythm perception\n",
    "\n",
    "I gleaned a lot of insight from experimenting with different parameters. As shown in [Part 2.2](#2.2-Using-Fibonacci-numbers-to-manipulate-rhythms), the greater the `stretch_factor`, the closer we get to the golden ratio; with regards to rhythm perception, I found that this made the resulting rhythm sound more and more \"natural\", in an almost uncanny valley manner. This relates back to the limitations of Fibonacci stretch as a creative tool as well. Perhaps it would be worth examining the space of results that lie between stretch factors of 1 and 3, as those seem to be where the most musically interesting rhythmic shifts occur.\n",
    "\n",
    "Similarly, plugging in different patterns for the `original_rhythm` and `target_rhythm` parameters yielded differing results, with some seeming more closely related to others. It's possible that there are some underlying rhythmic principles that more clearly explain how the relationship between the original and target rhythms affects how we perceive the stretched result.\n",
    "\n",
    "In addition, the initially disappointing results of using naive time-stretch also indicate the importance of considering different perceptual levels of rhythm. We explored a solution using subdivision of pulses, but haven't dealt with perceptual levels of rhythm in a rigorous manner at all.\n",
    "\n",
    "### 7.3 Implementation improvements\n",
    "\n",
    "The current implementation of Fibonacci stretch works well enough, but it also leaves a lot to be desired.\n",
    "\n",
    "One of the biggest issues is the handling of tempo. Firstly, the built-in tempo detection almost never gives us the correct value, which is why for the examples we've had to pass in tempo values manually. Looking into alternate tempo detection methods could mitigate this. More importantly, however, the current implementation doesn't allow for variable tempo, which is a real problem with tracks that weren't recorded to a metronome. Simply using a dynamic tempo estimate (which `librosa.beat.tempo` is capable of) would go a long way into improving the quality of the modified tracks.\n",
    "\n",
    "This implementation of Fibonacci stretch also doesn't work too well when `stretch_factor` < 0. As with the \"Chan Chan\" example in [Part 6.2](#6.2-Examples:-customizing-stretch-factors), we don't get the results we expect. It might just be a quirk in the step length conversion in `euclidean_stretch()`, but it's also possible that an adidtional level of subdivision might be needed.\n",
    "\n",
    "We might also want to explore using onset detection to improve the actual time-stretching process. Instead of choosing stretch regions purely based on where they fall in relation to the symbolic rhythm parameters, we could define regions in accordance with the sample indices of detected onsets as well, which could yield more natural sounding output.\n",
    "\n",
    "### 7.4 Future directions\n",
    "\n",
    "There are a ton of avenues to explore further, some of which we've touched upon. For example, some of the most interesting results came from stretching a track so that the performance was converted from one meter to another (e.g. 6/8 to 5/4). Sometimes this occurred as a happy coincidence of Fibonacci stretch, but most of the time we had to pass in custom `original_rhythm` and `target_rhythm` parameters. I think it would be worthwhile to explore a version of the stretch method that could convert meter A to meter B without explicitly defining the rhythm patterns.\n",
    "\n",
    "On a related note, exploring the possibilities of Euclidean rhythms, outside of their relationship to Fibonacci rhythms, could be worthwhile as well. In addition, we could allow each measure to be stretched using different parameters by passing in a list of arguments, each corresponding to a measure or group of measures. This would allow for more flexibility and creative freedom when using Fibonacci stretch.\n",
    "\n",
    "Finally, I could see this stretch method being used in the context of a digital audio workstation (DAW), with both the symbolic meter data for a project and the raw audio signal for a track being modified. If embedded directly into a DAW, this would open up possibilities for rapid experimentation of rhythm in a music production setting."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "All in all, I hope this notebook presents an insightful exploration of how the Fibonacci sequence can be applied to sample-level audio manipulation of rhythmic relationships!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}