功能

実信号での編集距離

ペ，ジ内をすべて折りたたむ

構文

Dist = edr(x,y,tol)

[dist,ix,iy] = edr(x,y,tol)

［___= edr(x,y,maxsamp)

［___= edr(___、指标)

edr (___）

説明

例

经销= edr (x,y,托尔）は，シ，ケンスxおよびy間の実信号での編集距離を返します。功能は,x、y，またはxとyの両方から削除する必要がある要素の最小数を返して,残りの信号要素間のユークリッド距離の合計が指定許容誤差托尔内に収まるようにします。

［经销,第九,iy= edr(x,y,托尔）は,x（9)およびy（iy)間の经销が可能な限り最小となるワ，ピングパスを返します。xとyが行列の場合，9とiyはx(第九:)とyiy (:,)の分離間隔が最小限となる値になります。

例

［___= edr(x,y,maxsamp）は，ワ，ピングパスがxとy間の直線近似のmaxsampのサンプル数内に入るように挿入操作を制限します。この構文は，前述の構文の出力引数のいずれかを返します。

［___= edr(___,度规）は，前述の構文の任意の入力引数に加えて使用する距離計量を指定します。度规は,“欧几里得”、“绝对”、“方”，または“symmkl”のいずれかになります。

例

出力引数を指定しないedr (___）は，元の信号と整列後の信号をプロットします。

信号が実数ベクトルの場合,関数は元の2つの信号を1つのサブプロットに表示し,整列後の信号をその下のサブプロットに表示します。
信号が複素数ベクトルの場合，関数は元の信号と整列後の信号を3次元プロットに表示します。
信号が実数行列の場合，関数は显示亮度图像を使用して元の信号と整列後の信号を表示します。
信号が複素行列の場合，関数は実数部と虚数部を各。

例

すべて折りたたむ

外れ値があるチャ，プおよび正弦波の間の編集距離

ラ@ @ブスクリプトを開く

チャプと正弦波の2の実信号を生成します。それぞれの信号に明らかに値が外れているセクションを追加します。

X = cos(2* *(3*(1:1000)/1000).^2);Y = cos(2* *9*(1:399)/400);X (400:410) = 7;Y (100:115) = 7;

信号間の編集距離が最小となるように信号を歪めます。許容誤差には0.1を指定します。整列された信号をワピングの前と後の両方にいてプロットし，その間の距離を出力します。

Tol = 0.1;edr (x, y, tol)

图中包含2个轴对象。标题为Original Signals的Axes对象1包含2个类型为line的对象。标题为Aligned Signals(编辑距离:617)的Axes对象2包含2个line类型的对象。

Ans = 617

正弦波周波数を初期値の2倍に変更します。計算を繰り返します。

Y = cos(2* *18*(1:39 99)/400);Y (100:115) = 7;edr (x, y, tol);

图中包含2个轴对象。标题为Original Signals的Axes对象1包含2个类型为line的对象。标题为Aligned Signals(编辑距离:774)的Axes对象2包含2个line类型的对象。

各信号に虚数部を追加します。初期の正弦波周波数に戻します。ユ，クリッド距離の二乗和を最小化することによって信号を整列します。

X = exp(2i*pi*(3*(1:1000)/1000).^2);Y = exp(2i*pi*9*(1:399)/400);X (400:405) = 5+3j;X (405:410) = 7;Y (100:107) = 3j;Y (108:115) = 7-3j;edr (x, y,托尔,“方”）;

图中包含2个轴对象。标题为Original Signals的Axes对象1包含2个类型为line的对象。标题为Aligned Signals(编辑距离:617)的Axes对象2包含2个line类型的对象。

編集距離とワ，ピングパス

ラ@ @ブスクリプトを開く

異なる長さの谷で隔てられた2の明確なピクから構成される信号を2生成します。信号をプロットします。

X1 = [0 1 0 1 0]*.95;X2 = [0 1 0 0 0 0 0 0 0 0 0 1 0]*.95;Subplot (2,1,1) plot(x1) xlim([0 12]) Subplot (2,1,2) plot(x2) xlim([0 12])

图中包含2个轴对象。Axes对象1包含一个line类型的对象。坐标轴对象2包含一个line类型的对象。

信号間の編集距離を計算します。等しいサンプルどうしのみが一致するように許容誤差に小さな値を設定します。

Tol = 0.1;图edr (x1, x2, tol);

图中包含2个轴对象。标题为Original Signals的Axes对象1包含2个类型为line的对象。标题为Aligned Signals(编辑距离:7)的Axes对象2包含2个line类型的对象。

信号間の距離は7です。これらを揃えるには，x2の中央にある7のゼロを削除するか，x1に7のゼロを追加する必要があります。

D行列を計算します。右の一番下の要素は，編集距離に対応します。Dの定義にいては，実信号での編集距離を参照してください。

CND = (abs(x1'-x2))>tol;D = 0(长度(x1)+1，长度(x2)+1);D(1,2:结束)= 1:长度(x2);D(2:结束，1)= 1:长度(x1);为H = 2:长度(x1)+1为k = 2:length(x2)+1 D(h,k) = min([D(h-1,k)+1).．.D (h, k - 1) + 1.．.D (h - k - 1) + cnd (h - k - 1)));结束结束D

D =6×130 1 2 3 4 5 6 7 8 9 10 11 12 1 0 1 2 3 4 5 6 7 8 9 10 11 2 1 0 1 2 3 4 5 6 7 8 9 10 3 2 1 0 1 2 3 4 5 6 7 8 9 4 3 2 1 1 2 3 4 5 6 7 7 8 5 4 3 2 1 1 2 3 4 5 6 7 7

信号を揃えるワ，ピングパスを計算および表示します。

[d,i1,i2] = edr(x1,x2,tol);E = 0(长度(x1)，长度(x2));为k = 1:长度(i1) E(i1(k)，i2(k)) = NaN;结束E

E =5×12南0 0 0 0 0 0 0 0 0 0 0 0 0 0 0南0 0 0 0 0 0 0南0 0 0 0南0 0 0 0 0 0南0 0 0 0 0 0 0 0 0 0 0南0 0 0 0 0 0 0 0 0

計算を繰り返しますが,今度は,対角線から逸脱する要素が2つまでになるようにワーピングパスに制約を付けます。引き伸ばした信号とワ，ピングパスをプロットします。2番目のプロットで，x軸に沿って実行する行列の列を設定します。

[dc,i1c,i2c] = edr(x1,x2,tol,2);次要情节(2,1,1)情节((x1 (i1c); x2 (i2c)”,“。”)标题(的距离:Num2str (dc)]) subplot(2,1,2) plot(i2c,i1c，“啊——”，[i2(1) i2(end)]，[i1(1) i1(end)])轴ij标题(“扭曲的道路”）

图中包含2个轴对象。标题为Distance: 5的坐标轴对象1包含2个类型为line的对象。带有标题“扭曲路径”的坐标轴对象2包含2个类型为line的对象。

この制約により，編集距離は小さくなりますが，信号が歪みます。制約を満たすことができない場合，功能は，距離に対して南を返します。対角線からの逸脱が最大でも1要素になるようにワ，ピングパスが強制されていることがわかります。

[dc,i1c,i2c] = edr(x1,x2,tol,1);次要情节(2,1,1)情节((x1 (i1c); x2 (i2c)”,“。”)标题(的距离:Num2str (dc)]) subplot(2,1,2) plot(i2c,i1c，“啊——”，[i2(1) i2(end)]，[i1(1) i1(end)])轴ij标题(“扭曲的道路”）

图中包含2个轴对象。带有标题Distance的Axes对象1:NaN包含2个类型为line的对象。带有标题“扭曲路径”的坐标轴对象2包含2个类型为line的对象。

汚れた手書き文字サンプルの位置合わせ

ラ@ @ブスクリプトを開く

ファereplicationルMATLAB1.gifとMATLAB2.gifには，“matlab®”という単語の2の手書き文字のサンプルが含まれています。ファ@ @ルを読み込みます。デ，タに汚れを付けて外れ値を追加します。

samp1 =“MATLAB1.gif”；samp2 =“MATLAB2.gif”；X = double(imread(samp1));Y = double(imread(samp2));X (15:20,54:60) = 4000;Y (15:20,84:96) = 4000;

編集距離を使用してx軸に沿って手書きサンプルの位置を合わせます。許容誤差には450を指定します。

edr (x, y, 450);

图中包含6个轴对象。标题为“重叠对齐信号”的Axes对象1包含一个图像类型的对象。标题为Aligned Signal (Y)的坐标轴对象2包含一个图像类型的对象。标题为Aligned Signal (X)的坐标轴对象3包含一个图像类型的对象。标题为“覆盖原始信号”的Axes对象4包含一个图像类型的对象。标题为原始信号(Y)的坐标轴对象5包含一个图像类型的对象。标题为原始信号(X)的坐标轴对象6包含一个图像类型的对象。

入力引数

すべて折りたたむ

`x`- - - - - -入力信号
ベクトル|行列

実数または複素数のベクトルまたは行列として指定される入力信号。

デ，タ型:单|双
複素数のサポ，ト:あり

`y`- - - - - -入力信号
ベクトル|行列

実数または複素数のベクトルまたは行列として指定される入力信号。

デ，タ型:单|双
複素数のサポ，ト:あり

`托尔`- - - - - -許容誤差
正のスカラ

許容誤差。正のスカラ，で指定します。

デ，タ型:单|双

`maxsamp`- - - - - -調整ウィンドウの幅
`正`(既定値) |正の整数

調整ウィンドウの幅。正の整数で指定します。

デ，タ型:单|双

`度规`- - - - - -距離計量
`“欧几里得”`(既定値) |`“绝对”`|`“方”`|`“symmkl”`

距離計量。“欧几里得”、“绝对”、“方”，または“symmkl”で指定します。XとYが両方ともk次元の信号である場合，度规はXのm番目のサンプルとYのn番目のサンプルの間の距離d_锰（X,Y)を規定します。

“欧几里得”-距離の二乗和根。ユ，クリッド計量またはℓ₂計量とも呼ばれます。

$d_{米 n} （ X, Y ）＝ \sqrt{\sum_{k ＝ 1}^{K} {（ x_{k, 米} - y_{k, n} ）}^{＊} （ x_{k, 米} - y_{k, n} ）}$
“绝对”-差の絶対値の総和。マンハッタン計量，街区計量，タクシ，計量またはℓ₁計量とも呼ばれます。

$d_{米 n} （ X, Y ）＝ \sum_{k ＝ 1}^{K} | x_{k, 米} - y_{k, n} | ＝ \sum_{k ＝ 1}^{K} \sqrt{{（ x_{k, 米} - y_{k, n} ）}^{＊} （ x_{k, 米} - y_{k, n} ）}$
“方”—ユクリッド計量の2乗。距離の二乗和で構成されます。

$d_{米 n} （ X, Y ）＝ \sum_{k ＝ 1}^{K} {（ x_{k, 米} - y_{k, n} ）}^{＊} （ x_{k, 米} - y_{k, n} ）$
“symmkl”-対称カルバック·ラブラ距離。この計量は，正の実数のXとYに対してのみ有効です。

$d_{米 n} （ X, Y ）＝ \sum_{k ＝ 1}^{K} （ x_{k, 米} - y_{k, n} ）（日志 x_{k, 米} - 日志 y_{k, n} ）$

出力引数

すべて折りたたむ

`经销`-最小距離
正の実数のスカラ

信号間の最小距離。正の実数のスカラとして返されます。

`第九,iy`—ワピングパス
ンデックスのベクトル

ワ，ピングパス。ンデックスのベクトルとして返されます。9とiyは同じ長さです。各ベクトルは単調増加数列を含み，その数列に基づいて，対応する信号xまたはyの要素に対する@ @ンデックスが必要な回数だけ繰り返されます。

詳細

すべて折りたたむ

実信号での編集距離

同じ順序に並んだ同等の特徴をもつ2つの信号が,セクションの持続時間の違いによって大きく異なって見える場合があります。功能はこれらの持続時間を歪ませて,対応する特徴が共通の時間軸上の同じ位置に現れるようにさせ,信号間の類似点を強調します。歪みを実行するために使用される基準は，外れ値に対してロバストになるように設計されています。

次の2のk次元信号を考えます。

$X ＝［ \begin{matrix} x_{1, 1} & x_{1, 2} & \dots & x_{1, 米} \\ x_{2, 1} & x_{2, 2} & \dots & x_{2, 米} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ x_{K, 1} & x_{K, 2} & \dots & x_{K, 米} \end{matrix} ］$

および

$Y ＝［ \begin{matrix} y_{1, 1} & y_{1, 2} & \dots & y_{1, N} \\ y_{2, 1} & y_{2, 2} & \dots & y_{2, N} \\ ⋮ & ⋮ & ⋱ & ⋮ \\ y_{K, 1} & y_{K, 2} & \dots & y_{K, N} \end{matrix} ］,$

これらの信号には，それぞれm個とn個のサンプルがあります。度规で指定されたXのm番目のサンプルとYのn番目のサンプルの間の距離d_锰（X,Y)が与えられた場合，関数功能はXとYを，信号間の“編集距離”が最小となる時点の共通集合上で引き伸ばします。

托尔に指定された許容誤差である実数εが与えられたとき，d_锰（X,Y) < εの場合にXのm番目のサンプルとYのn番目のサンプルが“一致する”ことを宣言します。2つのサンプルの m と n が一致しない場合には、次の 3 つの方法のいずれかでそれらを一致させることができます。

次のサンプルがnに一致する場合などは，最初の信号からmを削除します。この削除は，mを2目の信号に追加して，2の連続一致を得ることと等価です。
nに一致するサンプルを適切な位置に追加し,残りのサンプルの位置を1つ移動することにより,最初の信号の長さを引き伸ばします。この追加は、一致しないnを2目の信号から削除することと等価です。
最初の信号でmにnを代入します。または、同等の操作として、m と n の両方を削除します。

編集距離は，2の信号を一致させるために必要なこれらの操作の合計数です。この数値は一意ではありません。XとY間の編集距離ができるだけ小さくなるように計算するには，次の事実に基づいて開始します。

2 .の空の信号間の距離は，ゼロです。
空の信号とl個のサンプルをも信号間の距離はlです。これは，他の信号を復元するために，空の信号に追加する必要があるサンプル数であるためです。これはすなわちLはLサンプル信号を空にするために削除しなければならないサンプルの数ということです。

次のように(m + 1)行(n + 1)列の行列Dを作成します。

D_{1, - 1}= 0．
D_{m, 1}= m - 1（m = 2，…，m + 1）
D_{1, n}= n - 1（n = 2，…，n + 1）
M, n > 1の場合，

$D_{米, n} ＝最小值｛ \begin{matrix} D_{米 - 1, n} + 1 \\ D_{米, n - 1} + 1 \\ D_{米 - 1, n - 1} + ｛ \begin{matrix} 0 \Leftarrow d_{米, n} （ X, Y ） \leq ε \\ 1 \Leftarrow d_{米, n} （ X, Y ） > ε \end{matrix} \end{matrix}} ．$

したがって，XとY間の最小の編集距離は，D_{M + 1, N + 1}となります。

この編集距離が最小となるD経由の“ワ，ピングパス”は，次のように，同じ長さの2のシ，ケンス9およびiyによってパラメ，タ，化され，“チェスのキング”の動きの組み合わせになります。

垂直方向の動き:(m,n)→(m + 1,n)は,Xからのサンプルの削除，またはYへのサンプルの追加に対応します。それぞれの移動では，編集距離が1増えます。
水平方向の動き:(m,n)→(m,n + 1)は,Yからのサンプルの削除，またはXへのサンプルの追加に対応します。それぞれの移動では，編集距離が1増えます。
対角方向の動き:(m,n)→(m + 1,n + 1)は,d_{m, n}（X,Y)≤εの場合は一致に対応，d_{m, n}（X,Y) > εの場合は各信号からの1サンプル削除に対応します。一致による距離の増加はありません。削除では1増えます。

この構造では,条件に合うパスがいずれも,サンプルをスキップしたり,信号の特徴を反復したりせず,すべての信号を揃えることが確保されます。さらに，望ましいパスは，d_{1, - 1}（X,Y)とd_{M, N}（X,Y)の間に伸びる対角方向のラleiンの近くを通ります。maxsamp引数で調整されるこの追加の制約により,長さが類似するセクションのワーピングによる比較が必ず行われます。

2 .のサンプルを一致させるためのペナルティは，サンプル間の値の違いとは無関係です。許容誤差をわずかに超える差がある 2 つのサンプルが、その差が著しい 2 つのサンプルと同じペナルティを受けます。そのため、編集距離は外れ値の影響を受けません。一方、2 つの信号を揃えるためにサンプルを繰り返すことにはコストがかかります。これは動的タイムワーピングの場合は該当しません。

参照

[1]陈，雷，M. Tamer Özsu和文森特·奥里亚。运动物体轨迹的鲁棒快速相似搜索第24届ACM数据管理国际会议论文集(SIGMOD ' 05)。2005，第491-502页。

[2] Paliwal, k.k.， Anant Agarwal, Sarvajit S. Sinha。Sakoe和Chiba的动态时间扭曲算法在孤立词识别中的改进。信号处理。第4卷，1982，第329-333页。

[3] Sakoe, Hiroaki和Seibi千叶。语音识别的动态规划算法优化IEEE^®声学、语音与信号处理汇刊。Vol. ASSP-26, No. 1, 1978, pp. 43-49。

拡張機能

C/ c++コ，ド生成
MATLAB®Coder™を使用してCおよびc++コドを生成します。

バ，ジョン履歴

R2016bで導入

参考

alignsignals|dtw|finddelay|findsignal|xcorr

功能

構文

説明

例

外れ値があるチャ，プおよび正弦波の間の編集距離

編集距離とワ，ピングパス

汚れた手書き文字サンプルの位置合わせ

入力引数

x- - - - - -入力信号ベクトル|行列

y- - - - - -入力信号ベクトル|行列

托尔- - - - - -許容誤差正のスカラ

maxsamp- - - - - -調整ウィンドウの幅正(既定値) |正の整数

度规- - - - - -距離計量“欧几里得”(既定値) |“绝对”|“方”|“symmkl”

出力引数

经销-最小距離正の実数のスカラ

第九,iy—ワピングパスンデックスのベクトル

詳細

実信号での編集距離

参照

拡張機能

C/ c++コ，ド生成MATLAB®Coder™を使用してCおよびc++コドを生成します。

バ，ジョン履歴

参考

`x`- - - - - -入力信号
ベクトル|行列

`y`- - - - - -入力信号
ベクトル|行列

`托尔`- - - - - -許容誤差
正のスカラ

`maxsamp`- - - - - -調整ウィンドウの幅
`正`(既定値) |正の整数

`度规`- - - - - -距離計量
`“欧几里得”`(既定値) |`“绝对”`|`“方”`|`“symmkl”`

`经销`-最小距離
正の実数のスカラ

`第九,iy`—ワピングパス
ンデックスのベクトル

C/ c++コ，ド生成
MATLAB®Coder™を使用してCおよびc++コドを生成します。