Melody Matching

結合了隱藏式馬可夫模型 (Hidden Markov Model, HMM) 和動態規劃 (Dynamic Programming, DP)，並使用漸進式過濾 (Progressive Filtering)，以提高效率和準確性。

以下是 Proposed melody matching 的內容與解釋：

1. 特徵選取
   • 音高 (Pitch)：
     • 使用 MIDI 音符編號 (MIDI number) 的差分 (difference) 來處理移調 (key transposition) 的問題。
     • 不直接將頻率 (frequency) 轉換為 MIDI 音符編號，而是透過微調 (shifting) 的方式，以找到誤差最小的 MIDI 序列。
   • 節奏 (Tempo)：
     • 使用音符間隔時間比率 (Inter-Onset-Intervals ratio, IOIs) 來處理不同人唱歌速度不同的問題。
     • 將 IOI 比率轉換為三個類別：
       • 快 (Faster)。
       • 中等 (Moderate)。
       • 慢 (Slower)。
     • 將此分類後的節奏資訊稱為 mapping beat。
2. 旋律匹配系統架構
   • 使用音高間隔 (pitch interval) 和 mapping beat 作為特徵。
   • 結合 HMM 和 DP：
     • HMM (第一階段)：用於快速過濾資料庫中不可能匹配的歌曲。
       • 擴散式 HMM (Diffused HMM)：對傳統 HMM 進行改進，考慮到演唱者可能出現的音高誤差。
       • 在 HMM 模型中加入擴散機率矩陣，使得目標中每次發生的轉移都能被考慮到。
     • DP (第二階段)：用於更精確的匹配，在 HMM 過濾後的歌曲中尋找最佳匹配。
       • 不直接構建 alignment score matrix，而是構建 pitch interval matrix。
       • 考慮到使用者在音高上的準確度通常比節奏好，匹配過程主要基於音高。
3. 改良式 HMM (Diffused HMM)
   • 傳統 HMM 的缺點：
     • 對插入、刪除和音高錯誤不具備強韌性。
   • 改良方法：
     • 擴散機率矩陣 (Diffusion Matrix)：
       • 在 HMM 模型中加入擴散機率矩陣。
       • 保證擴散矩陣滿足特定條件：每個轉移發生的機率總和為 1。
     • Mapping Beat 應用：
       • 將 MIDI 音符差分 (MIDI number difference) 分成三個狀態：bi =1, 2 或 3。
       • 使用 mapping beat 序列建立 HMM 模型。
4. 改良式動態規劃 (Modified Dynamic Programming)
   • 不構建 alignment score matrix，而是構建 pitch interval matrix 和 mapping beat difference matrix。
   • 比較核心 (Comparing Kernel)：
     • 使用比較核心來評估匹配程度。
     • 給予沒有跳過的單元格 (cell) 更高的優先權。
   • 跳過懲罰 (Skip Penalty)：
     • 對於跳過的單元格給予懲罰，以調整匹配分數。
   • 匹配分數計算 (Matching Score Calculation)：
     • 使用以下公式計算匹配分數：
       • MatchingScore = ∑ (𝑃(𝑛) − 𝑤𝑏 ∗ 𝐵(𝑛))
         • P(n) 是匹配音高間隔序列 (matching pitch interval sequence)。
         • B(n) 是匹配 mapping beat 差分序列 (matching mapping beat difference sequence)。
         • wb 是給予節奏項的權重 (weighting)，論文中設定為 0.8。
5. 音樂索引 (Music Indexing)
   • 標記歌曲中使用者可能開始唱歌的位置。
   • 縮短 DP 的計算時間，提高系統效率。
6. 漸進式過濾 (Progressive Filtering)
   • 使用一系列分類器 (classifiers)，每個分類器選擇一個較小的集合，其中可能包含正確的歌曲。
   • HMM 作為第一階段，DP 作為第二階段。
7. 分數層級融合 (Score Level Fusion)
   • 結合多個階段的結果，以提高系統效能。
   • 使用加權總和 (Weighted SUM) 方式：
     • FinalScore = 0.2 * HMMScore + 0.8 * DPScore
     • HMM 的權重較小，因為其效果不如 DP。

馬可夫模型 (Markov Model)

隱藏式馬可夫模型（Hidden Markov Model, HMM）是一種馬可夫模型的擴展，用於描述一個系統隨著時間推移在一系列離散狀態之間轉換的過程。與傳統馬可夫模型不同的是，HMM 中的狀態並不能直接觀察到，只能透過與每個狀態相關聯的機率分佈來間接推斷。

• HMM 是馬可夫模型的擴展。
• 馬可夫模型是一個機率轉移循環，由一系列特定狀態組成，這些狀態以音高為特徵。
• 每個狀態都有轉換到其他狀態的轉移機率。
• 代表一個經過一系列離散狀態的過程。
• 三個基本要素組成馬可夫模型：
  • 狀態集合：= {𝑠1, 𝑠2, … , 𝑠𝑁}，N 是狀態的數量。
  • 轉移機率集合：T，其中 𝑡𝑖,𝑗 代表從狀態 𝑠𝑖 到 𝑠𝑗 的轉移機率。轉移機率可以形成為 NxN 轉移矩陣 A。
  • 初始機率分佈：π，其中 𝜋 是序列在狀態 𝑠𝑖 中開始的機率。
• 資料庫中的每首歌曲都有自己的馬可夫模型，該模型由歌曲本身的特徵建立。

隱藏馬可夫模型 (HMM) 的要素

• 狀態集合 (S)：系統可能處於的所有狀態的集合。在旋律匹配中，每個音符可以被視為一個狀態。