DPマッチングを試してみる

はじめに

DPマッチングが便利らしいので試してみました。身近に使っている人が何人もいたので、私も知っておいた方が良いかなと。

DPマッチング

二つのパターン間の類似度を計算できます。パターンは多少伸び縮みしても大丈夫で、音声のパターンマッチングに使用できるようです。音声ですと長くなったり、短くなったりするので伸び縮みに頑健なことは必須です。

アルゴリズム

この式を評価します。

元ネタは中部大学藤吉研のこちらの論文(pdf)です。「輪郭線に着目したオプティカルフローの算出」

やりたいこと

パターンAからパターンBを見つけ出します。パターンAがマイク音声で、パターンBが事前に録音した単語の音だとしたら、マイク音声から録音した単語を見つけ出すことができます。最も類似している箇所を図示します。
早速ですが動かした例がこちらです。

右が結果で一番似ている領域を見つけています。
多少伸び縮みしても大丈夫です。

マイク音声で音声認識したかったんですが、うまくいかなかったので、なんかの変換してからマッチングしないといけないんですかね。
何かに使えて便利そうなので、以上メモでしたー

using System;
using System.Collections.Generic;
using System.Linq;

namespace Microphone
{
    class DP
    {
        private readonly List<double> _data1 = new List<double>();
        private readonly List<double> _data2 = new List<double>();

        enum DPLabel
        {
            A, B, C, NON,
        };
        private DPLabel[,] _dplabel;
        private double[,] _dpmap;
        private double[,] _acumDistance;
        private int _sourceLength;
        private int _targetLength;

        public int MatchedIndexBegin { private set; get; }
        public int MatchedIndexEnd { private set; get; }

        public IEnumerable<double> GetData1()
        {
            return _data1.Skip(1); // 1つめは0なので飛ばす
        }

        public IEnumerable<double> GetData2()
        {
            return _data2.Skip(1); // 1つめは0なので飛ばす
        }

        public void LoadData(List<float> source, List<float> target)
        {
            _data1.Clear();
            _data2.Clear();
            _data1.Add(0.0);
            _data2.Add(0.0);
            _data1.AddRange(source.Select(v => (double)v).ToList());
            _data2.AddRange(target.Select(v => (double)v).ToList());
            _sourceLength = source.Count;
            _targetLength = target.Count;
        }

        private double LocalDistance(int i, int j) 
        {
            return (_data1[i] - _data2[j]) * (_data1[i] - _data2[j]);
        }

        public void StartDP()
        {
            // mapの大きさを設定
            _dpmap = new double[_sourceLength + 1, _targetLength + 1];
            _dplabel = new DPLabel[_sourceLength + 1, _targetLength + 1];
            _acumDistance = new double[_sourceLength + 1, _targetLength + 1];

            // 初期化
            // 端点フリーDPなので0
            for (var i = 0; i < _dpmap.GetLength(0); i++)
            {
                _dpmap[i, 0] = 0.0;
            }

            for (var j = 1; j < _dpmap.GetLength(1); j++)
            {
                _dpmap[0, j] = double.MaxValue;
            }

            for (var i = 0; i < _dplabel.GetLength(0); i++)
            {
                for (var j = 0; j < _dplabel.GetLength(1); j++)
                {
                    _dplabel[i, j] = DPLabel.NON;
                }
            }

            for (var i = 1; i < _dpmap.GetLength(0); i++)
            {
                for (var j = 1; j < _dpmap.GetLength(1); j++)
                {
                    double a, b, c;

                    if (i - 2 < 0 || j - 2 < 0)
                    {
                        a = double.MaxValue;
                        b = _dpmap[i - 1, j - 1] + LocalDistance(i, j);
                        c = double.MaxValue;
                    }
                    else
                    {
                        a = _dpmap[i - 1, j - 2] + 2.0 * LocalDistance(i, j - 1);
                        b = _dpmap[i - 1, j - 1] + LocalDistance(i, j);
                        c = _dpmap[i - 2, j - 1] + 2.0 * LocalDistance(i - 1, j);
                    }

                    var min = Math.Min(a, Math.Min(b, c));
                    if (a == min)
                    {
                        _dplabel[i, j] = DPLabel.A;
                        _acumDistance[i, j] = _acumDistance[i - 1, j - 2] + 3;
                    }
                    else if (b == min)
                    {
                        _dplabel[i, j] = DPLabel.B;
                        _acumDistance[i, j] = _acumDistance[i - 1, j - 1] + 2;
                    }
                    else if (c == min)
                    {
                        _dplabel[i, j] = DPLabel.C;
                        _acumDistance[i, j] = _acumDistance[i - 2, j - 1] + 3;
                    }

                    _dpmap[i, j] = min + LocalDistance(i, j);
                }
            }
        }

        private double _minDistance;
        public void BackTrace()
        {
            _minDistance = double.MaxValue;
            int index = _targetLength / 2 + 1;
            for (int i = index; i < _dpmap.GetLength(0); i++)
            {
                var normalizedDistance = _dpmap[i, _targetLength] / _acumDistance[i, _targetLength];
                if (normalizedDistance < _minDistance)
                {
                    _minDistance = normalizedDistance;
                    index = i;
                }
            }

            MatchedIndexEnd = index - 1;
            //Console.WriteLine(string.Format("距離:{0}", _minDistance));

            var ii = index;
            var jj = _targetLength;
            while (jj > 0)
            {
                switch (_dplabel[ii, jj])
                {
                    case DPLabel.A:
                        ii -= 1;
                        jj -= 2;
                        break;
                    case DPLabel.B:
                        ii -= 1;
                        jj -= 1;
                        break;
                    case DPLabel.C:
                        ii -= 2;
                        jj -= 1;
                        break;
                }
            }

            MatchedIndexBegin = ii;
        }
    }
}