Eye tracking fixation algorithm

This page contains JavaScript implementations of some common algorithms for handling raw eye-tracking data, such as generating fixations and managing vertical drifting, which served for the tracking part of autocomplete research. For example, IDT, attach, K-cluster.js. It also includes some data visualization script we used in internal testing. All codescripts designed to be run under NodeJs.

Fixation

IDT

One of the most common algorithms for detecting fixations is the Identification by Dispersion-Threshold (IDT) algorithm. According to Salvucci and Goldberg (2000), it is based on the data reduction algorithm by Widdel (1984). The IDT algorithm works with x- and y data, and two fixed thresholds: the maximum fixation dispersion threshold and the minimum fixation duration threshold. To be a fixation, data samples constituting at least enough time to fulfill the duration threshold has to be within a spatial area not exceeding the dispersion threshold. The samples fulfilling these criteria are marked as belonging to a fixation. One particular detail of this specific implementation is that it is part of a package that also merges short nearby fixations, and also paired with a saccade detector (Komogortsev, Gobert, Jayarathna, Koh, & Gowda, 2010).

// possible time error of using this: 20ms

export class Point {
    curLine = -41;
    /**
     * 
     * @param {Number} x 
     * @param {Number} y 
     * @param {Number} time 
     * @param {Number} curBox y axis location of autocompletion box associate with this points
     */
    constructor(x, y, time, curBox) {
        this.x = x;
        this.y = y;
        this.time = time;
        this.curBox = curBox;
    }

    toString() {
        return "(" + this.x + "," + this.y + "," + this.time + "," + this.curBox + ")";
    }
}

export class Fixation {
    points = [];
    x = 0;
    y = 0;
    time = 0;
    duration = 0;
    line = -1;
    lineAns = -40;
}

class IDT {
    constructor(duration, dispersion) {
        this.duration = duration;
        this.dispersion = dispersion;
    }

    maxBy = (comparator, array) =>
        array.reduce((acc, val) => comparator(acc, val) > 0 ? acc : val);
    minBy = (comparator, array) =>
        array.reduce((acc, val) => comparator(acc, val) < 0 ? acc : val);

    compareX = (a, b) => a.x - b.x;
    compareY = (a, b) => a.y - b.y;

    computeGazeDifference(points) {
        if (points.length == 0) return 0;
        let xmax = this.maxBy(this.compareX, points).x;
        let xmin = this.minBy(this.compareX, points).x;
        let ymax = this.maxBy(this.compareY, points).y;
        let ymin = this.minBy(this.compareY, points).y;
        // console.log(xmax, xmin, ymax, ymin);
        return ((xmax - xmin) + (ymax - ymin));
    }// Not a real dispersion: why not using square root: Pythagorean theorem a^2 + b^2 = c^2 to measure the difference: Most of available code online is using this

    // guessing original step 1 is check whether the point is valid

    calculateTime(points) {
        return points[points.length - 1].time - points[0].time;
    }

    generateFixation(points) {
        let fixation = [];// array of Fixation
        let window = [];//array of points for each run
        let i = 0;
        let tmpDuration = 0;
        while (tmpDuration < this.duration && i < points.length) {
            window.push(points[i]);
            tmpDuration += points[i].time;
            i++;
        }

        while (i < points.length) {
            if ((this.computeGazeDifference(window) <= this.dispersion) && (this.calculateTime(window) >= this.duration)) {
                while (this.computeGazeDifference(window) <= this.dispersion) {
                    if (i < points.length - 1) {
                        window.push(points[i]);
                        ++i;
                    }
                    else { break; }
                }
                fixation.push(this.computeEstimate(window));
                window = [];
                window.push(points[i]);
                i++;
            } else if (this.calculateTime(window) < this.duration) {
                window.push(points[i]);
                i++;
            }
            else {
                window.shift();
                if (this.calculateTime(window) < this.duration) {
                    window.push(points[i]);
                    i++;
                }
            }
        }

        return fixation;
    }

    computeEstimate(points) {
        let fixation = new Fixation();
        let x = 0, y = 0;
        for (let i of points) {
            x += i.x;
            y += i.y;
            fixation.points.push(i);
        }
        fixation.x = (x / fixation.points.length);
        fixation.y = (y / fixation.points.length);
        fixation.time = fixation.points[0].time;
        fixation.duration = this.calculateTime(fixation.points);
        if (fixation.points[0].curLine != -41) {
            let occurrences = fixation.points.reduce(function (acc, curr) {
                return acc[curr.curLine] ? ++acc[curr.curLine] : acc[curr.curLine] = 1, acc
            }, {});
            fixation.lineAns = Object.keys(occurrences).reduce((a, b) => occurrences[a] > occurrences[b] ? a : b);
        }
        return fixation;
    }

    getSetting() {
        return this.duration + "," + this.dispersion;
    }
}

/**
 * 
 * @param {Point[]} data 
 * @param {Number} dur 
 * @param {Number} dis 
 * @returns {Fixation[]}
 */
export function generateIDT(data, dur, dis) {
    let fix = new IDT(dur, dis);
    return fix.generateFixation(data);// fixation in type Fixation
}

Vertical drift

K-cluster.js

This is a script to handle vertical drift by categorize all points to K-clusters.

import { Point } from './IDT.js'


// Should be used to guess lines instead of generating fixation pattern

const kMeans = (data, k = 1) => {
    const centroids = data.slice(0, k);
    const distances = Array.from({ length: data.length }, () =>
        Array.from({ length: k }, () => 0)
    );
    const classes = Array.from({ length: data.length }, () => -1);
    let itr = true;

    while (itr) {
        itr = false;

        for (let d in data) {
            for (let c = 0; c < k; c++) {
                distances[d][c] = Math.hypot(
                    ...Object.keys(data[0]).map(key => data[d][key] - centroids[c][key])
                );
            }
            const m = distances[d].indexOf(Math.min(...distances[d]));
            if (classes[d] !== m) itr = true;
            classes[d] = m;
        }

        for (let c = 0; c < k; c++) {
            centroids[c] = Array.from({ length: data[0].length }, () => 0);
            const size = data.reduce((acc, _, d) => {
                if (classes[d] === c) {
                    acc++;
                    for (let i in data[0]) centroids[c][i] += data[d][i];
                }
                return acc;
            }, 0);
            for (let i in data[0]) {
                centroids[c][i] = parseFloat(Number(centroids[c][i] / size).toFixed(2));
            }
        }
    }
    console.log(data)

    return classes;
};

console.log(kMeans([[0, 0], [0, 1], [1, 3], [2, 0]], 4))

export function KCluster(points, screenSizeVec, autocompleteLoc) {
    // TODO: not necessary now
}

attach.js

This is the baseline algorithm for fixing the vertical drift for eye-tracker. Previous research use this as a baseline while also have a good performance.

import { Point, Fixation } from './IDT.js'

/**
 * 
 * @param {Fixation[]} fixations 
 * @returns 
 */
export function attachFixation(fixations) {
    // set lines, actually, only fix negative offset and outofrange offset 
    // 303px with 30px per line, so 10 lines in total
    // 0-1 stands for the first line.
    for (let i of fixations) {
        if (i.y < 1) {
            i.line = 1;
        } else if (i.y >= 9) {
            i.line = 10;
        } else {
            i.line = (i.y | 0) + 1;
        }
    }
    return fixations;
}

Internal test script

import * as IDT from './IDT.js';
import * as IDTM from './IDT-proposed.js';
import { attachFixation } from './attach.js';
import { generatePattern, fixit } from './autoFix.js';
import { convertFile } from './readData.js';

let screenY = 864;
let dataFile = "./testData.txt"
async function simpleAttach() {
    let sourceSession = await convertFile(dataFile);
    let source = [];// array of result fixations 
    for (let j of Object.keys(sourceSession)) {
        if (j.localeCompare("screenY") != 0) {
            for (let k of Object.keys(sourceSession[j])) {
                let tmpPoints = [];
                for (let i of sourceSession[j][k]) { // in format: x,y,time,curBoxloc,curLine : For fixation, curline is determined by majority point
                    let newP = new IDT.Point(i[0], i[1] * 30, i[2], i[3]);
                    newP.curLine = i[4]; // line number start from 1
                    tmpPoints.push(newP);
                }
                source = source.concat(tmpPoints);
            }
        }
    }
    let newSource = [];
    for (let i of source) {
        i.y = i.y / 30;// divide by 30 to return to previous format
        if (i.y > -400) newSource.push(i);
    }
    source = newSource;
    source = attachFixation(source);

    let tempResult = { "correct": 0, "incorrect": 0 }
    for (let i of source) {
        if (i.line == i.curLine) {
            tempResult["correct"]++;
        } else {
            tempResult["incorrect"]++;
        }
    }

    console.log("result:" + tempResult["correct"] + " " + tempResult["incorrect"]);
    console.log(tempResult["correct"] / (tempResult["correct"] + tempResult["incorrect"]))
    return tempResult["correct"] / (tempResult["correct"] + tempResult["incorrect"])
}

async function IDT_perline_Attach(dur, dis) {
    // Need to get the best fixation working pair
    // fixation should be done on each session of data, categorize by autocompletion box position
    let sourceSession = await convertFile(dataFile);
    // in format {"boxY":{"line":[data]}, "screenY": 864}
    screenY = parseInt(sourceSession["screenY"])
    let source = [];// array of result fixations 
    for (let j of Object.keys(sourceSession)) {
        if (j.localeCompare("screenY") != 0) {
            for (let k of Object.keys(sourceSession[j])) {
                let tmpPoints = [];
                for (let i of sourceSession[j][k]) { // in format: x,y,time,curBoxloc,curLine : For fixation, curline is determined by majority point
                    let newP = new IDT.Point(i[0], i[1] * 30, i[2], i[3]);
                    newP.curLine = i[4]; 
                    tmpPoints.push(newP);
                }
                source = source.concat(IDT.generateIDT(tmpPoints, dur, dis));
            }
        }
    }
    let newSource = [];
    for (let i of source) {
        i.y = i.y / 30;// divide by 30 to return to previous format
        if (i.y > -400) newSource.push(i);
    }
    source = newSource;
    // let pattern = generatePattern(source, screenY);
    // source = fixit(source, pattern, screenY);
    source = attachFixation(source);
    let tempResult = { "correct": 0, "incorrect": 0 }
    for (let i of source) {
        for (let j of i.points) {
            if (i.line == j.curLine) {
                tempResult["correct"]++;
            } else {
                tempResult["incorrect"]++;
            }
        }
    }
    console.log("dur:" + dur + "dis:" + dis + "result:" + tempResult["correct"] / (tempResult["correct"] + tempResult["incorrect"]));
    console.log("Points: " + source.reduce((a, b) => a += b.points.length, 0))
    // return source.reduce((a, b) => a += b.points.length, 0);
    return [tempResult["correct"] / (tempResult["correct"] + tempResult["incorrect"]), source.reduce((a, b) => a += b.points.length, 0)];
}


async function IDT_persession_Attach(dur, dis) {
    let sourceSession = await convertFile(dataFile);
    // in format {"boxY":{"line":[data]}, "screenY": 864}
    screenY = parseInt(sourceSession["screenY"])
    let source = [];// array of result fixations 
    for (let j of Object.keys(sourceSession)) {
        if (j.localeCompare("screenY") != 0) {
            let tmpPoints = [];
            for (let k of Object.keys(sourceSession[j])) {
                for (let i of sourceSession[j][k]) { // in format: x,y,time,curBoxloc,curLine : For fixation, curline is determined by majority point
                    let newP = new IDT.Point(i[0], i[1] * 30, i[2], i[3]);
                    newP.curLine = i[4]; // line number start from 1
                    tmpPoints.push(newP);
                }
            }
            source = source.concat(IDT.generateIDT(tmpPoints, dur, dis));
        }
    }
    let newSource = [];
    for (let i of source) {
        i.y = i.y / 30;// divide by 30 to return to previous format
        if (i.y > -400) newSource.push(i);
    }
    source = newSource;
    // let pattern = generatePattern(source, screenY);
    // source = fixit(source, pattern, screenY);
    source = attachFixation(source);
    let tempResult = { "correct": 0, "incorrect": 0 }
    for (let i of source) {
        for (let j of i.points) {
            if (i.line == j.curLine) {
                tempResult["correct"]++;
            } else {
                tempResult["incorrect"]++;
            }
        }
    }
    console.log("dur:" + dur + "dis:" + dis + "result:" + tempResult["correct"] / (tempResult["correct"] + tempResult["incorrect"]));
    console.log("Points: " + source.reduce((a, b) => a += b.points.length, 0))
    // return source.reduce((a, b) => a += b.points.length, 0);
    return [tempResult["correct"] / (tempResult["correct"] + tempResult["incorrect"]), source.reduce((a, b) => a += b.points.length, 0)];
}


async function IDTM_perline_Attach(dur, dis) {
    let sourceSession = await convertFile(dataFile);
    // in format {"boxY":{"line":[data]}, "screenY": 864}
    screenY = parseInt(sourceSession["screenY"])
    let source = [];// array of result fixations 
    for (let j of Object.keys(sourceSession)) {
        if (j.localeCompare("screenY") != 0) {
            for (let k of Object.keys(sourceSession[j])) {
                let tmpPoints = [];
                for (let i of sourceSession[j][k]) { // in format: x,y,time,curBoxloc,curLine : For fixation, curline is determined by majority point
                    let newP = new IDT.Point(i[0], i[1] * 30, i[2], i[3]);
                    newP.curLine = i[4]; // line number start from 1
                    tmpPoints.push(newP);
                }
                source = source.concat(IDTM.generateIDTM(tmpPoints, dur, dis));
            }
        }
    }
    let newSource = [];
    for (let i of source) {
        i.y = i.y / 30;// divide by 30 to return to previous format
        if (i.y > -400) newSource.push(i);
    }
    source = newSource;
    // let pattern = generatePattern(source, screenY);
    // source = fixit(source, pattern, screenY);
    source = attachFixation(source);
    let tempResult = { "correct": 0, "incorrect": 0 }
    for (let i of source) {
        for (let j of i.points) {
            if (i.line == j.curLine) {
                tempResult["correct"]++;
            } else {
                tempResult["incorrect"]++;
            }
        }
    }
    console.log("dur:" + dur + "dis:" + dis + "result:" + tempResult["correct"] / (tempResult["correct"] + tempResult["incorrect"]));
    console.log("Points: " + source.reduce((a, b) => a += b.points.length, 0))
    return [tempResult["correct"] / (tempResult["correct"] + tempResult["incorrect"]), source.reduce((a, b) => a += b.points.length, 0)];
}


async function IDTM_persession_Attach(dur, dis) {
    let sourceSession = await convertFile(dataFile);
    screenY = parseInt(sourceSession["screenY"])
    let source = [];// array of result fixations 
    for (let j of Object.keys(sourceSession)) {
        if (j.localeCompare("screenY") != 0) {
            let tmpPoints = [];
            for (let k of Object.keys(sourceSession[j])) {
                for (let i of sourceSession[j][k]) { // in format: x,y,time,curBoxloc,curLine : For fixation, curline is determined by majority point
                    let newP = new IDT.Point(i[0], i[1] * 30, i[2], i[3]);
                    newP.curLine = i[4]; // line number start from 1
                    tmpPoints.push(newP);
                }
            }
            source = source.concat(IDTM.generateIDTM(tmpPoints, dur, dis));
        }
    }
    let newSource = [];
    for (let i of source) {
        i.y = i.y / 30;
        if (i.y > -400) newSource.push(i);
    }
    source = newSource;
    source = attachFixation(source);
    let tempResult = { "correct": 0, "incorrect": 0 }
    for (let i of source) {
        for (let j of i.points) {
            if (i.line == j.curLine) {
                tempResult["correct"]++;
            } else {
                tempResult["incorrect"]++;
            }
        }
    }
    console.log("dur:" + dur + "dis:" + dis + "result:" + tempResult["correct"] / (tempResult["correct"] + tempResult["incorrect"]));
    console.log("Points: " + source.reduce((a, b) => a += b.points.length, 0))
    // return source.reduce((a, b) => a += b.points.length, 0);
    return [tempResult["correct"] / (tempResult["correct"] + tempResult["incorrect"]), source.reduce((a, b) => a += b.points.length, 0)];
}

async function getBestFixation(dur, dis) {// do pattern
    let sourceSession = await convertFile(dataFile);
    // in format {"boxY":{"line":[data]}, "screenY": 864}
    screenY = parseInt(sourceSession["screenY"])
    let source = [];// array of result fixations 
    for (let j of Object.keys(sourceSession)) {
        if (j.localeCompare("screenY") != 0) {
            for (let k of Object.keys(sourceSession[j])) {
                let tmpPoints = [];
                for (let i of sourceSession[j][k]) { // in format: x,y,time,curBoxloc,curLine : For fixation, curline is determined by majority point
                    let newP = new IDT.Point(i[0], i[1] * 30, i[2], i[3]);
                    newP.curLine = i[4]; // line number start from 1
                    tmpPoints.push(newP);
                }
                source = source.concat(IDT.generateIDT(tmpPoints, dur, dis));
            }
        }
    }

    let newSource = [];
    for (let i of source) {
        i.y = i.y / 30;// divide by 30 to return to previous format
        if (i.y > -400) newSource.push(i);
    }
    source = newSource;

    source = attachFixation(source);

    let pattern = generatePattern(source, screenY);
    source = fixit(source, pattern, screenY);

    source = attachFixation(source);
    let tempResult = { "correct": 0, "incorrect": 0 }
    for (let i of source) {
        for (let j of i.points) {
            if (i.line == j.curLine) {
                tempResult["correct"]++;
            } else {
                tempResult["incorrect"]++;
            }
        }
    }
    console.log("dur:" + dur + "dis:" + dis + "result:" + tempResult["correct"] / (tempResult["correct"] + tempResult["incorrect"]));
    // return source.reduce((a, b) => a += b.points.length, 0);
    return [tempResult["correct"] / (tempResult["correct"] + tempResult["incorrect"]), source.reduce((a, b) => a += b.points.length, 0)];
}

async function report() {
    // duration starts from 2500 with 500 increment
    let bestPossible = [];
    for (let dur = 500; dur < 2000; dur += 50) {
        for (let dis = 2; dis < 80; dis += 2) {
            let resultRatio = await IDT_perline_Attach(dur, dis);
            bestPossible.push({ "dur": dur, "dis": dis, "result": resultRatio[0] * 100, "points": resultRatio[1] })
        }
    }
    bestPossible.sort((a, b) => {
        return b["result"] - a["result"];
    })
    console.log(bestPossible);
}

IDTM_persession_Attach(550, 30)

function calculateCorrect(result) {
    for (let i of Object.keys(result)) {
        result[i]["ratio"] = parseFloat(((result[i]["correct"] / (result[i]["correct"] + result[i]["incorrect"])) * 100).toFixed(2));
    }
    return result;
}

IDT visualization script contains some sensitive information. I can provide if requested.

Reference

Andersson, Richard, et al. “One algorithm to rule them all? An evaluation and discussion of ten eye movement event-detection algorithms.” Behavior research methods 49 (2017): 616-637.

Kliegl, Reinhold, and Richard K. Olson. “Reduction and calibration of eye monitor data.” Behavior Research Methods & Instrumentation 13.2 (1981): 107-111.

Carr, Jon W., et al. “Algorithms for the automated correction of vertical drift in eye-tracking data.” Behavior Research Methods 54.1 (2022): 287-310.