1. (*) 中位數的證明: 對於一組已知的純量 {x1, ... xn}，請證明此組純量的中位數能夠達到下列目標函數的最小值：
    J(u) = S|xi-u|
  2. (*) 平均值的證明: 對於一組已知的純量 {x1, ... xn}，請證明此組純量的平均值能夠達到下列目標函數的最小值：
    J(u) = S(xi-u)2
  3. (**) 切音符的函數: 請寫一個能夠執行音符切割的函數 myNoteSegment.m，其使用方法如下：
    note = myNoteSegment(pitchVec, timeUnit, pitchTh, minNoteDuration)
    其中
    • pitchVec: 輸入的音高向量
    • timeUnit：每一個音高點所對應的時間
    • pitchTh：音高差異門檻值，用於切出一個音符
    • minNoteDuration：音符的最小長度，以秒為單位。
    • note: 切出的音符，以「音高, 音長, 音高, 音長...」的格式來儲存，其中音高的單位是 Semitone，音長的單位是 1/64 秒。
    除了使用音高差異來切音外，若碰到休止部分（pitchVec中元素值為零的點），請務必將休止符切出來，因為休止符也是音符的一種。特別要注意的是，休止符的長度可以小於 minNoteDuration。如何測試此函數：
    1. 請使用「生日快樂」的音高向量來進行音符切割，你可以聽看看原來的 wave 檔案以及 midi 檔案。請使用 pvPlay.m 來播放原始音高向量，並用 notePlay 來播放切出來的音符，聽看看結果是否正確。
    2. 請將你的函數用在最後一題的程式競賽，並只用一次的音高平移，看看辨識率有多高。
    3. 請將你的函數用在最後一題的程式競賽，並用五次的音高平移（使用試誤法），看看辨識率有多高。
    提示：可以參考 SAP Toolbox 中的 pv2note.m，請注意，此函數並未對休止符進行處理。
  4. (**) LinearScaling的函數: 請寫一個能夠執行線性伸縮的函數 mylinearScaling.m，其使用方法如下：
    [minDist, bestVec1, allDist] = myLinearScaling4mr(pitchVec1, pitchVec2, lowerRatio, upperRatio, resolution, distanceType)
    其中
    • pitchVec1: 使用者輸入的音高向量，也是被伸縮及平移的向量
    • pitchVec2: 資料庫中的音高向量
    • lowerRatio: 最低伸縮比例
    • upperRatio: 最高伸縮比例
    • resolution: 伸縮總次數
    • distanceType: 所用的距離函數，1 代表 L1 norm，2 代表 L2 norm。
    • minDist: 線性伸縮的最短距離
    • bestVec1: 對應於最短距離、伸縮及平移後的 pitchVec1
    • allDist: 線性伸縮的所有距離
    請注意：
    • 若 vec1 被拉長後的長度大於 vec2，則不再計算距離。
    • 不同的距離計算方式，要進行不同的音高校正。
    • 要進行距離的正規化。
    • 可以假定輸入的向量不包含休止符。
    如何測試你寫的函數：
    • 請執行此範例，但將 linScalingMex 改成 myLinearScaling，看看是否得到同樣的效果。
    • 請用你的程式碼來測試哼唱選歌的辨識率。
    提示：可用 interp1 指令來進行內差，median 指令來計算中位數，mean 指令來計算平均值，norm 指令來計算 Lp norm。若對 interp1.m 的使用有疑問，請見下列範例：

    Example 1: interpDemo01.mn=10; x=1:n; y=rand(1,n); % Original vector (原始向量) ratio=1.75; % The vector interpolation should have a length equal to 1.8 times the original vector m=round(n*ratio); % Length of the scaled vector x2=linspace(1, n, m); y2=interp1(x, y, x2); % Vector after interpolation subplot(2,1,1), plot(x, y, 'o-', x2, y2, 'o:'); legend('Original vector', 'Interpolated vector', 'location', 'northOutside', 'orientation', 'horizontal'); subplot(2,1,2), plot(1:length(y), y, 'o-', 1:length(y2), y2, 'o:'); legend('Original vector', 'Scaled vector', 'location', 'northOutside', 'orientation', 'horizontal'); fprintf('Desired length ratio = %f\n', ratio); fprintf('Actual length ratio = %f\n', length(y2)/length(y));Desired length ratio = 1.750000 Actual length ratio = 1.800000

  5. (***) editDistance程式碼: 請寫一個 MATLAB 函數 editDistance.m 來實做 Edit Distance，使用格式如下：
    [minDist, edPath, edTable] = editDistance(str1, str2)
  6. (***) DTW3程式碼: 請寫一個 MATLAB 函數 myDtw3.m 來實做 type-3 DTW，使用格式如下：
    [minDist, dtwPath, dtwTable] = myDtw3(vec1, vec2)
    可由下列半成品進行修改：

    原始檔（dtw3skeleton.m）：（灰色區域按兩下即可拷貝）
    function [minDistance, dtwPath, dtwTable]=dtw3(vec1, vec2, beginCorner, endCorner)
% dtw3: Dynamic time warping with local paths of 0 and 45 degrees
%	Usage: [minDistance, dtwPath, dtwTable]=dtw3(vec1, vec2, beginCorner, endCorner, plotOpt)
%		vec1: testing vector, which should be a pitch vector
%		vec2: reference vector, which should be a vector of note pitch
%		minDistance: minimun distance of DTW
%		dtwPath: optimal path of dynamical programming through the DTW table
%			(Its size is 2xk, where k is the path length.)
%		dtwTable: DTW table

if nargin<3, beginCorner=1; end
if nargin<4, endCorner=1; end

% If input is vector, make it row vector
if size(vec1,1)==1 | size(vec1,2)==1, vec1 = vec1(:)'; end
if size(vec2,1)==1 | size(vec2,2)==1, vec2 = vec2(:)'; end

size1=length(vec1);
size2=length(vec2);

% ====== Construct DTW table
dtwTable=inf*ones(size1,size2);
% ====== Construct the first element of the DTW table
dtwTable(1,1)=vecDist(vec1(:,1), vec2(:,1));
% ====== Construct the first row of the DTW table (xy view)
for i=2:size1
	dtwTable(i,1)=dtwTable(i-1,1)+vecDist(vec1(:,i), vec2(:,1));
	prevPos(i,1).i=i-1;
	prevPos(i,1).j=1;
end
% ====== Construct the first column of the DTW table (xy view)
if beginCorner==0
	for j=2:size2
		dtwTable(1,j)=vecDist(vec1(:,1), vec2(:,j));
		prevPos(1,j).i=[];
		prevPos(1,j).j=[];
	end
end

% ====== Construct all the other rows of DTW table
for i=2:size1
	for j=2:size2
		pointDist=vecDist(vec1(:,i), vec2(:,j));
		% ====== Check 45-degree predecessor
		...
		% ====== Check 0-degree predecessor
		...
	end
end

% ====== Find the overall optimum path
[minDistance, dtwPath]=dtwBackTrack(dtwTable, prevPos, beginCorner, endCorner);

% ========== Sub function ===========
function distance=vecDist(x, y)
distance=sum(abs(x-y));

    1. 請將此範例內之 dtw3mex 改成 myDtw3，並確認所畫出來的圖形和原範例的圖形一樣。
    2. 請將你的函數用在最後一題的程式競賽，並只用一次的音高平移，看看辨識率有多高。
    3. 請將你的函數用在最後一題的程式競賽，並用五次的音高平移（使用二元搜尋法），看看辨識率有多高。
  7. (***) DTW3程式碼：改進方案: 請寫一個 MATLAB 函數來重複上一題，但是必須逐次滿足下列三個條件：
    1. 限制每一個音符所能分配的音框個數：例如每個音符所對應的音框總長度，不得小於音符長度的一半，也不得大於音符長度的兩倍。此規則的加入，使我們可以同時用到音符的音高及音長資訊。
    2. 使用休止符：在使用者哼唱的音高向量中，除了頭尾的休止符不算外，只要遇到一個休止區間，就代表一個舊音符的結束及新音符的開始，此規則可以適用到一般的哼唱選歌輸入。
    3. 同時使用上述兩項規則。
    請測試此函數：
    1. 請將你的函數用在最後一題的程式競賽，並只用一次的音高平移，看看辨識率有多高。
    2. 請將你的函數用在最後一題的程式競賽，並用五次的音高平移（使用二元搜尋法），看看辨識率有多高。
    總共有三種 DTW 變形及兩種音調平移的方法，所以你應該共得到六個辨識率。
  8. (***) 旋律辨識的效能測試之一: 請先閱讀本節的最後一個習題，充分瞭解如何改變參數來進行辨識率的測試後，然後進行下列計算及作圖：
    1. 使用 LS，請畫出辨識率對辨識時間的作圖，並使用 resolution 為可變參數，使其從 5 增加到 12。畫出的圖應該類似下圖：
    2. 使用 type-1 DTW，請畫出辨識率對辨識時間的作圖，並使用二元搜尋法的音調移位次數為可變參數（此參數也是每次比對一首 wav 檔案時，所必須執行 DTW 的個數），請使值為 1, 3, 5, 7, 9。畫出的圖應該類似下圖：
    3. 請將上述兩圖同時畫出來，以進行 LS 和 DTW 在辨識效能（含辨識率及辨識時間）的比較。由此圖形，你可以得到什麼結論？
    （若計算時間過於冗長，請採用 waveData 的前 100 筆資料來進行本作業即可。）

    Hint
    請將最後一題範例程式中所提供的辨識率測試主程式改寫為一個函式，才比較容易進行本題的計算和作圖。

  9. (***) 旋律辨識的效能測試之二: 請先閱讀本節的最後一個習題，充分瞭解如何改變參數來進行辨識率的測試後，然後再進行本題。我們標示的音高向量，每一點的持續時間都是 1/31.25 ( = 256/8000) 秒，也就是說，每秒會有 31.25 個音高點。如果旋律辨識的計算時間太長，一個改進的方向，就是逐次降低音高向量在時間軸的解析度，換句話說，如果我們在原始的音高向量中，每 pvrr 點中只取用一點，則每秒的音高解析度降低至 31.25/pvrr 點。本題的目的，即是要探討 pvrr (pitch vector reduction ratio) 對辨識率及辨識時間的影響。請使用四種方法（LS, DTW1, DTW2, DTW3），畫出四條辨識率對辨識時間的曲線，並使用 pvrr 為可變參數。畫出的圖應該類似下圖：
    （若計算時間過於冗長，請採用 waveData 的前 100 筆資料來進行本作業即可。）

    Hint
    請將最後一題範例程式中所提供的辨識率測試主程式改寫為一個函式，才比較容易進行本題的計算和作圖。

  10. (***) 程式競賽：使用各種方法進行旋律辨識: 請見此連結。
Audio Signal Processing and Recognition (音訊處理與辨識)