旅行好きなソフトエンジニアの備忘録

プログラミングや技術関連のメモを始めました

【アイトラッキング】 I-DTアルゴリズムの実装

Salvucci & Goldberg著 "Identifying Fixations and Saccades in Eye-Tracking Protocols"に記述されているI-DTアルゴリズムの実装メモになります。

まずは視線データを保存するためのクラスを定義します。

public class GazePoint
{
    public double X; // 視線X座標
    public double Y; // 視線Y座標
    public long TimeStamp; // タイムスタンプ
    public int? FixationId; // 固視ID
    public uint FixationDuration_msec; // 固視時間

    public static double operator- (GazePoint p1, GazePoint p2)
    {
        return Math.Sqrt(Math.Pow(p1.X - p2.X, 2) + Math.Pow(p1.Y - p2.Y, 2));
    }

    public GazePoint Clone()
    {
        return new GazePoint() { X = X, Y = Y, TimeStamp = TimeStamp, FixationId = FixationId, FixationDuration_msec = FixationDuration_msec };
    }
}


次にI-DTアルゴリズムをIDTAlgorithmクラスとして実装します。AnalyzeメソッドがI-DTアルゴリズムを適用している箇所であり、論文に書かれている疑似コードと対比できるよう、論文から疑似コードのコメントを引用しています。

public class IDTAlgorithm
{
    private readonly double _dispersionThreshold;
    private readonly uint _durationThreshold_msec;

    public IDTAlgorithm(double dispersionThreshold, uint durationThreshold_msec)
    {
        _dispersionThreshold = dispersionThreshold;
        _durationThreshold_msec = durationThreshold_msec;
    }

    /// <summary>
    /// IDTアルゴリズムで視線データを分析し、固視/それ以外を判別するメソッド
    /// </summary>
    /// <param name="points">視線データ</param>
    /// <returns>固視フラグが付加された視線データ</returns>
    public GazePoint[] Analyze(IList<GazePoint> points)
    {
        GazePoint[] filteredPoints = Enumerable.Repeat<GazePoint>(null, points.Count).ToArray();

        int fixationId = 0;
        for (int i = 0; i < points.Count; ++i)
        {
            // Initialize window over first points to cover the duration threshold
            int endIndex;
            List<GazePoint> window = InitializeWindow(points, i, _durationThreshold_msec, out endIndex);

            // If dispersion of window points <= threshold
            double dispersion = ComputeDispersion(window);
            if (dispersion <= _dispersionThreshold)
            {
                // Add additional points to the window until dispersion > threshold
                AddAdditionalPoints(points, _dispersionThreshold, ref window, ref endIndex);

                // Note a fixation at the centroid of the window points
                GazePoint[] filteredFixations = ComputeAverageFixation(window);
                ++fixationId;
                uint fixationDuration_msec = (uint)(window.Last().TimeStamp - window.First().TimeStamp);
                for (int j = 0; j < filteredFixations.Length; ++j)
                {
                    filteredPoints[i + j] = filteredFixations[j];
                    filteredPoints[i + j].FixationId = fixationId;
                    filteredPoints[i + j].FixationDuration_msec = fixationDuration_msec;
                }

                // Remove window points from points
                i = endIndex;
            }
        }

        // 固視以外の視線データをセットする
        for (int i = 0; i < points.Count; ++i)
        {
            if (filteredPoints[i] == null)
            {
                filteredPoints[i] = points[i];
                filteredPoints[i].FixationId = -1;
            }
        }

        return filteredPoints;
    }

    private List<GazePoint> InitializeWindow(IList<GazePoint> points, int startIndex, uint durationThreshold_msec, out int endIndex)
    {
        var window = new List<GazePoint>();
        long start = points[startIndex].TimeStamp;
        long end = start + durationThreshold_msec;
        int index = 0;
        while ((startIndex + index < points.Count) && (points[startIndex + index].TimeStamp <= end))
        {
            window.Add(points[startIndex + index]);
            ++index;
        }
        endIndex = startIndex + index - 1;
        return window;
    }

    private void AddAdditionalPoints(IList<GazePoint> points, double dispersionThreshold, ref List<GazePoint> window, ref int endIndex)
    {
        double dispersion;
        int i = 0;
        bool outOfIndex = false;
        do
        {
            ++i;
            if (endIndex + i >= points.Count)
            {
                outOfIndex = true;
                break;
            }
            window.Add(points[endIndex + i]);
            dispersion = ComputeDispersion(window);
        } while (dispersion <= dispersionThreshold);
        if (!outOfIndex) window.RemoveAt(window.Count - 1);
        endIndex += i - 1;
    }

    private double ComputeDispersion(List<GazePoint> window)
    {
        IEnumerable<double> xs = window.Select(p => p.X);
        IEnumerable<double> ys = window.Select(p => p.Y);
        return xs.Max() - xs.Min() + ys.Max() - ys.Min();
    }

    private GazePoint[] ComputeAverageFixation(IEnumerable<GazePoint> fixations)
    {
        double x = fixations.Average(i => i.X);
        double y = fixations.Average(i => i.Y);
        var filteredFixations = new GazePoint[fixations.Count()];
        for (int i = 0; i < filteredFixations.Length; ++i)
        {
            filteredFixations[i] = new GazePoint
            {
                X = x,
                Y = y,
                TimeStamp = fixations.ElementAt(i).TimeStamp
            };
        }
        return filteredFixations;
    }
}


最後にIDTAlgorithmクラスの使い方を記述します。

var points = new List<GazePoint>();
points.Add(new GazePoint() { X = 630.0, Y = 0.0, TimeStamp = 0 });
points.Add(new GazePoint() { X = 635.0, Y = 0.0, TimeStamp = 33 });
points.Add(new GazePoint() { X = 645.0, Y = 0.0, TimeStamp = 66 });
points.Add(new GazePoint() { X = 650.0, Y = 0.0, TimeStamp = 100 });
points.Add(new GazePoint() { X = 635.0, Y = 0.0, TimeStamp = 133 });
points.Add(new GazePoint() { X = 640.0, Y = 0.0, TimeStamp = 166 });
points.Add(new GazePoint() { X = 635.0, Y = 0.0, TimeStamp = 200 });
points.Add(new GazePoint() { X = 650.0, Y = 0.0, TimeStamp = 233 });
points.Add(new GazePoint() { X = 640.0, Y = 0.0, TimeStamp = 266 });
points.Add(new GazePoint() { X = 638.0, Y = 0.0, TimeStamp = 300 });
points.Add(new GazePoint() { X = 650.0, Y = 0.0, TimeStamp = 333 });
points.Add(new GazePoint() { X = 640.0, Y = 0.0, TimeStamp = 366 });
points.Add(new GazePoint() { X = 660.0, Y = 0.0, TimeStamp = 400 });
points.Add(new GazePoint() { X = 645.0, Y = 0.0, TimeStamp = 433 });
points.Add(new GazePoint() { X = 650.0, Y = 0.0, TimeStamp = 466 });
points.Add(new GazePoint() { X = 645.0, Y = 0.0, TimeStamp = 500 });
points.Add(new GazePoint() { X = 650.0, Y = 0.0, TimeStamp = 533 });
points.Add(new GazePoint() { X = 640.0, Y = 0.0, TimeStamp = 566 });
points.Add(new GazePoint() { X = 640.0, Y = 0.0, TimeStamp = 600 });
points.Add(new GazePoint() { X = 750.0, Y = 0.0, TimeStamp = 633 });
points.Add(new GazePoint() { X = 760.0, Y = 0.0, TimeStamp = 666 });
points.Add(new GazePoint() { X = 740.0, Y = 0.0, TimeStamp = 700 });
points.Add(new GazePoint() { X = 745.0, Y = 0.0, TimeStamp = 733 });
points.Add(new GazePoint() { X = 745.0, Y = 0.0, TimeStamp = 766 });
points.Add(new GazePoint() { X = 750.0, Y = 0.0, TimeStamp = 800 });
points.Add(new GazePoint() { X = 745.0, Y = 0.0, TimeStamp = 833 });
points.Add(new GazePoint() { X = 750.0, Y = 0.0, TimeStamp = 866 });
points.Add(new GazePoint() { X = 745.0, Y = 0.0, TimeStamp = 900 });
points.Add(new GazePoint() { X = 710.0, Y = 0.0, TimeStamp = 933 });
points.Add(new GazePoint() { X = 720.0, Y = 0.0, TimeStamp = 966 });
points.Add(new GazePoint() { X = 715.0, Y = 0.0, TimeStamp = 1000 });
points.Add(new GazePoint() { X = 600.0, Y = 0.0, TimeStamp = 1033 });
points.Add(new GazePoint() { X = 730.0, Y = 0.0, TimeStamp = 1066 });
points.Add(new GazePoint() { X = 740.0, Y = 0.0, TimeStamp = 1100 });
points.Add(new GazePoint() { X = 730.0, Y = 0.0, TimeStamp = 1133 });
points.Add(new GazePoint() { X = 735.0, Y = 0.0, TimeStamp = 1166 });
points.Add(new GazePoint() { X = 730.0, Y = 0.0, TimeStamp = 1200 });
points.Add(new GazePoint() { X = 735.0, Y = 0.0, TimeStamp = 1233 });
points.Add(new GazePoint() { X = 650.0, Y = 0.0, TimeStamp = 1266 });
points.Add(new GazePoint() { X = 645.0, Y = 0.0, TimeStamp = 1300 });
points.Add(new GazePoint() { X = 650.0, Y = 0.0, TimeStamp = 1333 });
points.Add(new GazePoint() { X = 640.0, Y = 0.0, TimeStamp = 1366 });
points.Add(new GazePoint() { X = 635.0, Y = 0.0, TimeStamp = 1400 });

const double dispersionThreshold = 30.0;
// 固視時間閾値(通常100~200msecあたりを指定)
const uint durationThreshold_msec = 150;
var algorithm = new IDTAlgorithm(dispersionThreshold, durationThreshold_msec);
GazePoint[] analyzedPoints = algorithm.Analyze(points);


Analyzeメソッドの出力をグラフ化して元のデータと比較すると以下のようになります。GazePointクラスのFixationIdが1から4まで割り当てられているため、固視回数は4回と分かります(グラフからも明らか)。 f:id:ni4muraano:20170628211212p:plain