fuba/cut detection using canvas+video

## cut detection using canvas+video
<!DOCTYPE html>
<html>
	<head>
		<title>cut detection using canvas+video</title>
<style>
#v {
    position:fixed;
    left: 3px;
    top: 3px;
}

#list {
    position:absolute;
    left: 490px;
    top: 510px;
    padding: 0;
    margin: 0;
}

#list li {
    font-size: 1em;
    display: inline-block;
    padding: 0;
    margin: 0.2em;
}

#graph-wrapper {
    position:absolute;
    left: 490px;
    top: 3px;
}
</style>
<!-- http://bluff.jcoglan.com/ -->
<script language="javascript" src="js/js-class.js" type="text/javascript"></script>
<script language="javascript" src="js/bluff-min.js" type="text/javascript"></script>
<script language="javascript" src="js/excanvas.js" type="text/javascript"></script>


<script type="text/javascript">
// parameters of algorithm
scaleFactor = 0.3; // captured images are scaled by this parameter.
colorWindow = 5; // image vector is expanded by this parameter, see digestCanvas().
samplingInterval = 1/30; // image is captured from video#v once every [samplingInterval] seconds.
windowLength = 8; // relatibity window

// settings of interfaces
graphInterval = 3000;
graphWidth = 1000;
cutJump = 1;
firstOffset = 0.01;
//firstOffset = 177.55; // for madoka

// global variants
previousTime = 0;
previousGraphTime = 0;
snapshot_id = 0;

histgrams = new Array();
digestJobs = new Array();

function cosine (vec1, vec2) {
    var numera = 0;
    var denomis = [1, 1];
    var n, n1, n2, i;

    var len = (vec1.length < vec2.length) ? vec1.length : vec2.length;

    for (i=0; i<len; i++) {
        n1 = (vec1[i]) ? vec1[i] : 0;
        n2 = (vec2[i]) ? vec2[i] : 0;
        numera += n1 * n2;
    }

    var j = 0;
    [vec1, vec2].forEach(function(vec){
        for (i=0; i<vec.length; i++) {
            n = (vec[i]) ? vec[i] : 0;
            denomis[j] += n * n;
        }
        j++;
    });

    return numera / (Math.sqrt(denomis[0]) * Math.sqrt(denomis[1]));
}

function detectGaps (seq, average, averageGradient) {
    var gaps = [ 0 ];

    for (var i = 1; i<seq.length-1; i++) {
        if (seq[i] > 0.980) continue;
        if (seq[i] > average) continue;
        if (seq[i-1] - seq[i] < averageGradient / windowLength) continue;
        if (seq[i+1] - seq[i] < averageGradient) continue;

        gaps.push(i);
    }

    return gaps.map(function(index){return histgrams[index]});
}

function getAverage (seq) {
    if (seq.length == 0) return 0;

    var sum = 0;
    for (var i = 0; i<seq.length; i++) {
        sum += seq[i];
    }
    return sum / seq.length;
}

function getAverageGradient (seq) {
    if (seq.length == 0) return 0;

    var sum = 0;
    var prev = seq[0];
    for (var i = 1; i<seq.length; i++) {
        sum += Math.abs(seq[i] - prev);
        prev = seq[i];
    }
    return sum / (seq.length - 1);
}

function getCosines (histgrams) {
    var cosines = [];
    var localCosines;
    for (var i=0; i<histgrams.length-1; i++) {
        var windowOffset;

        if (!cosines[i]) cosines[i] = 0;

        localCosines = new Array();
        for (windowOffset = 1; windowOffset<windowLength; windowOffset++) {
            if (histgrams[i+windowOffset]) {
                localCosines[localCosines.length] = cosine(
                    histgrams[i].histgram,
                    histgrams[i+windowOffset].histgram
                );
            }
        }

        localCosines = localCosines.sort(function(a,b){return b - a});
        cosines[i] = localCosines.reduce(function(a,b){return a + b}) / localCosines.length;
    }

    return cosines;
}

function showGaps (gaps) {
    var list = document.getElementById('list');
    list.innerHTML = '';

    var result = [];

    for (var i=0; i<gaps.length; i++) {
        var gap = gaps[i];
        var jumpTime = histgrams[gap.id].time;
        if (histgrams[gap.id + cutJump]) {
            jumpTime = histgrams[gap.id + cutJump].time;
        }
        var thumbnailId = (gaps[i+1])
            ? parseInt((gap.id + gaps[i+1].id) / 2)
            : gap.id + cutJump;
        if (!histgrams[thumbnailId]) {
            thumbnailId = gap.id + cutJump;
        }
        thumbnailId = gap.id + cutJump;

        result.push({
            jumpTime: jumpTime,
            thumbnailId: thumbnailId
        });
    }

    result.forEach(
        function(r) {
            var li = document.createElement('li');
            var thumbnailId = r.thumbnailId;
            var histgram = histgrams[thumbnailId];
            while(!histgram) {
                thumbnailId--;
                if (thumbnailId < 0) return;
                histgram = histgrams[thumbnailId];
            }
            var button = histgram.canvas;
            var prevEvent = histgram.event;
            var newEvent = function () {
                document.getElementById('v').currentTime = r.jumpTime + firstOffset;
            };

            histgrams[thumbnailId].event = newEvent;
            if (prevEvent) {
                button.removeEventListener('click', prevEvent);
            }
            button.addEventListener('click', newEvent);
            li.appendChild(button);
            list.appendChild(li);
        }
    );
}


function showGraph () {
    var vEle = document.getElementById('v');
    if (previousGraphTime >= vEle.currentTime) {
        window.setTimeout(arguments.callee, graphInterval);
        return;
    }
    previousGraphTime = vEle.currentTime;

    var cosines = getCosines(histgrams);
    var average = getAverage(cosines);
    var averageGradient = getAverageGradient(cosines);
    var gaps = detectGaps(cosines, average, averageGradient);

    var width = graphWidth;
    document.getElementById('graph').width = width;

    if (typeof(Bluff) != 'undefined') {
        var g = new Bluff.Line('graph', ''+width+'x'+(width/2));
        g.theme_greyscale();
        g.title = 'cosines';
        g.hide_title = true;
        g.hide_legend = true;
        g.data("score", cosines);
        g.data("average", cosines.map(function(){return average}));
        g.draw();
    }
    showGaps(gaps);
    window.setTimeout(arguments.callee, graphInterval);
}

function worker () {
    if (digestJobs.length > 0) {
        var job = digestJobs.shift();
        job[0](job[1]);
    }

    window.setTimeout(arguments.callee, 1);
    return;
}

function digestCanvas (args) {
    var imageData = args.imageData;
    var id = args.id;
    var time = args.time;
    var canvas = args.canvas;

    var data = imageData.data;
    var samplePointNum = parseInt(data.length / 4);
    var gr = parseInt((data.length / 4) / samplePointNum);

    var histgram = [];
    for (var i=0;i<data.length;i+=4) {
        if (i % (gr * 4) != 0) continue;

        // 32(R) + 32(G) + 32(B) + 32(K) -d vector
        var rgbOffset = parseInt(256 / 8);
        var R = parseInt(data[i] / 8);
        var G = parseInt(data[i+1] / 8);
        var B = parseInt(data[i+2] / 8);
        var K = (77 * data[i] + 150 * data[i+1] + 29 * data[i+2]) >> 11;

        var rgb = [R, G, B, K];

        for (var rgbi = 0; rgbi < 4; rgbi++) {
            var gray = rgb[rgbi] + rgbi * rgbOffset;
            for (var grayOffset=-colorWindow; grayOffset <= colorWindow; grayOffset++) {
                if ((gray+grayOffset < 0) || (gray+grayOffset > rgbOffset)) continue;
                if (!histgram[gray+grayOffset]) histgram[gray+grayOffset] = 0;
                if (rgbi == 3) {
                    // grayscale features must have big value
                    histgram[gray+grayOffset] += 2;
                }
                else {
                    histgram[gray+grayOffset]++;
                }
            }
        }
    }

    histgrams[id] = {
        id: id,
        time: time,
        histgram: histgram,
        canvas: canvas,
        event: null,
    };
}

function snapshot (video, div) {
    var canvas = document.createElement('canvas');
    div.appendChild(canvas);

    canvas.width = parseInt(video.videoWidth * scaleFactor);
    canvas.height = parseInt(video.videoHeight * scaleFactor);

    var context = canvas.getContext('2d');
    context.drawImage(video, 0, 0, canvas.width, canvas.height);
    var currentTime = video.currentTime;

    var imageData = context.getImageData(0, 0, canvas.width, canvas.height);

    digestJobs.push(
        [
            digestCanvas,
            {
                imageData: imageData,
                id: snapshot_id++,
                time: currentTime - firstOffset,
                canvas: canvas,
            }
        ]
    );
    context.font = '';
    context.fillStyle = '#fff';
    context.textAlign = 'center';
    context.textBaseline = 'middle';
    currentTime.toString().replace(/^(\d+\.\d{3})/);
    context.fillText(RegExp.$1, canvas.width / 2, canvas.height / 2);

    div.removeChild(canvas);
}

function copyFrame() {
    var thumbs = document.getElementById('thumbs');
    var vEle = document.getElementById('v');

    if (previousTime == 0) {
        vEle.currentTime = firstOffset;
    }

    if (previousTime >= vEle.currentTime) {
        window.setTimeout(arguments.callee, 1000 * samplingInterval);
        return;
    }
    previousTime = vEle.currentTime;

    window.setTimeout(arguments.callee, 1000 * samplingInterval);
    snapshot(vEle, thumbs);
}

</script>
</head>
	<body onload="copyFrame(0);worker();showGraph();">
        <!-- this video must be on the same server -->
        <video src="./kairiimino_gu.mp4" controls width="480" id="v" autoplay></video>

		<ol id="list"></ol>
		<div id="thumbs"></div>
        <div id="graph-wrapper">
        <canvas id="graph" width="300" height="225"></canvas>
        </div>
	</body>
</html>
	<!DOCTYPE html>
	<html>
	<head>
	<title>cut detection using canvas+video</title>
	<style>
	#v {
	position:fixed;
	left: 3px;
	top: 3px;
	}

	#list {
	position:absolute;
	left: 490px;
	top: 510px;
	padding: 0;
	margin: 0;
	}

	#list li {
	font-size: 1em;
	display: inline-block;
	padding: 0;
	margin: 0.2em;
	}

	#graph-wrapper {
	position:absolute;
	left: 490px;
	top: 3px;
	}
	</style>
	<!-- http://bluff.jcoglan.com/ -->
	<script language="javascript" src="js/js-class.js" type="text/javascript"></script>
	<script language="javascript" src="js/bluff-min.js" type="text/javascript"></script>
	<script language="javascript" src="js/excanvas.js" type="text/javascript"></script>


	<script type="text/javascript">
	// parameters of algorithm
	scaleFactor = 0.3; // captured images are scaled by this parameter.
	colorWindow = 5; // image vector is expanded by this parameter, see digestCanvas().
	samplingInterval = 1/30; // image is captured from video#v once every [samplingInterval] seconds.
	windowLength = 8; // relatibity window

	// settings of interfaces
	graphInterval = 3000;
	graphWidth = 1000;
	cutJump = 1;
	firstOffset = 0.01;
	//firstOffset = 177.55; // for madoka

	// global variants
	previousTime = 0;
	previousGraphTime = 0;
	snapshot_id = 0;

	histgrams = new Array();
	digestJobs = new Array();

	function cosine (vec1, vec2) {
	var numera = 0;
	var denomis = [1, 1];
	var n, n1, n2, i;

	var len = (vec1.length < vec2.length) ? vec1.length : vec2.length;

	for (i=0; i<len; i++) {
	n1 = (vec1[i]) ? vec1[i] : 0;
	n2 = (vec2[i]) ? vec2[i] : 0;
	numera += n1 * n2;
	}

	var j = 0;
	[vec1, vec2].forEach(function(vec){
	for (i=0; i<vec.length; i++) {
	n = (vec[i]) ? vec[i] : 0;
	denomis[j] += n * n;
	}
	j++;
	});

	return numera / (Math.sqrt(denomis[0]) * Math.sqrt(denomis[1]));
	}

	function detectGaps (seq, average, averageGradient) {
	var gaps = [ 0 ];

	for (var i = 1; i<seq.length-1; i++) {
	if (seq[i] > 0.980) continue;
	if (seq[i] > average) continue;
	if (seq[i-1] - seq[i] < averageGradient / windowLength) continue;
	if (seq[i+1] - seq[i] < averageGradient) continue;

	gaps.push(i);
	}

	return gaps.map(function(index){return histgrams[index]});
	}

	function getAverage (seq) {
	if (seq.length == 0) return 0;

	var sum = 0;
	for (var i = 0; i<seq.length; i++) {
	sum += seq[i];
	}
	return sum / seq.length;
	}

	function getAverageGradient (seq) {
	if (seq.length == 0) return 0;

	var sum = 0;
	var prev = seq[0];
	for (var i = 1; i<seq.length; i++) {
	sum += Math.abs(seq[i] - prev);
	prev = seq[i];
	}
	return sum / (seq.length - 1);
	}

	function getCosines (histgrams) {
	var cosines = [];
	var localCosines;
	for (var i=0; i<histgrams.length-1; i++) {
	var windowOffset;

	if (!cosines[i]) cosines[i] = 0;

	localCosines = new Array();
	for (windowOffset = 1; windowOffset<windowLength; windowOffset++) {
	if (histgrams[i+windowOffset]) {
	localCosines[localCosines.length] = cosine(
	histgrams[i].histgram,
	histgrams[i+windowOffset].histgram
	);
	}
	}

	localCosines = localCosines.sort(function(a,b){return b - a});
	cosines[i] = localCosines.reduce(function(a,b){return a + b}) / localCosines.length;
	}

	return cosines;
	}

	function showGaps (gaps) {
	var list = document.getElementById('list');
	list.innerHTML = '';

	var result = [];

	for (var i=0; i<gaps.length; i++) {
	var gap = gaps[i];
	var jumpTime = histgrams[gap.id].time;
	if (histgrams[gap.id + cutJump]) {
	jumpTime = histgrams[gap.id + cutJump].time;
	}
	var thumbnailId = (gaps[i+1])
	? parseInt((gap.id + gaps[i+1].id) / 2)
	: gap.id + cutJump;
	if (!histgrams[thumbnailId]) {
	thumbnailId = gap.id + cutJump;
	}
	thumbnailId = gap.id + cutJump;

	result.push({
	jumpTime: jumpTime,
	thumbnailId: thumbnailId
	});
	}

	result.forEach(
	function(r) {
	var li = document.createElement('li');
	var thumbnailId = r.thumbnailId;
	var histgram = histgrams[thumbnailId];
	while(!histgram) {
	thumbnailId--;
	if (thumbnailId < 0) return;
	histgram = histgrams[thumbnailId];
	}
	var button = histgram.canvas;
	var prevEvent = histgram.event;
	var newEvent = function () {
	document.getElementById('v').currentTime = r.jumpTime + firstOffset;
	};

	histgrams[thumbnailId].event = newEvent;
	if (prevEvent) {
	button.removeEventListener('click', prevEvent);
	}
	button.addEventListener('click', newEvent);
	li.appendChild(button);
	list.appendChild(li);
	}
	);
	}


	function showGraph () {
	var vEle = document.getElementById('v');
	if (previousGraphTime >= vEle.currentTime) {
	window.setTimeout(arguments.callee, graphInterval);
	return;
	}
	previousGraphTime = vEle.currentTime;

	var cosines = getCosines(histgrams);
	var average = getAverage(cosines);
	var averageGradient = getAverageGradient(cosines);
	var gaps = detectGaps(cosines, average, averageGradient);

	var width = graphWidth;
	document.getElementById('graph').width = width;

	if (typeof(Bluff) != 'undefined') {
	var g = new Bluff.Line('graph', ''+width+'x'+(width/2));
	g.theme_greyscale();
	g.title = 'cosines';
	g.hide_title = true;
	g.hide_legend = true;
	g.data("score", cosines);
	g.data("average", cosines.map(function(){return average}));
	g.draw();
	}
	showGaps(gaps);
	window.setTimeout(arguments.callee, graphInterval);
	}

	function worker () {
	if (digestJobs.length > 0) {
	var job = digestJobs.shift();
	job[0](job[1]);
	}

	window.setTimeout(arguments.callee, 1);
	return;
	}

	function digestCanvas (args) {
	var imageData = args.imageData;
	var id = args.id;
	var time = args.time;
	var canvas = args.canvas;

	var data = imageData.data;
	var samplePointNum = parseInt(data.length / 4);
	var gr = parseInt((data.length / 4) / samplePointNum);

	var histgram = [];
	for (var i=0;i<data.length;i+=4) {
	if (i % (gr * 4) != 0) continue;

	// 32(R) + 32(G) + 32(B) + 32(K) -d vector
	var rgbOffset = parseInt(256 / 8);
	var R = parseInt(data[i] / 8);
	var G = parseInt(data[i+1] / 8);
	var B = parseInt(data[i+2] / 8);
	var K = (77 * data[i] + 150 * data[i+1] + 29 * data[i+2]) >> 11;

	var rgb = [R, G, B, K];

	for (var rgbi = 0; rgbi < 4; rgbi++) {
	var gray = rgb[rgbi] + rgbi * rgbOffset;
	for (var grayOffset=-colorWindow; grayOffset <= colorWindow; grayOffset++) {
	if ((gray+grayOffset < 0) \|\| (gray+grayOffset > rgbOffset)) continue;
	if (!histgram[gray+grayOffset]) histgram[gray+grayOffset] = 0;
	if (rgbi == 3) {
	// grayscale features must have big value
	histgram[gray+grayOffset] += 2;
	}
	else {
	histgram[gray+grayOffset]++;
	}
	}
	}
	}

	histgrams[id] = {
	id: id,
	time: time,
	histgram: histgram,
	canvas: canvas,
	event: null,
	};
	}

	function snapshot (video, div) {
	var canvas = document.createElement('canvas');
	div.appendChild(canvas);

	canvas.width = parseInt(video.videoWidth * scaleFactor);
	canvas.height = parseInt(video.videoHeight * scaleFactor);

	var context = canvas.getContext('2d');
	context.drawImage(video, 0, 0, canvas.width, canvas.height);
	var currentTime = video.currentTime;

	var imageData = context.getImageData(0, 0, canvas.width, canvas.height);

	digestJobs.push(
	[
	digestCanvas,
	{
	imageData: imageData,
	id: snapshot_id++,
	time: currentTime - firstOffset,
	canvas: canvas,
	}
	]
	);
	context.font = '';
	context.fillStyle = '#fff';
	context.textAlign = 'center';
	context.textBaseline = 'middle';
	currentTime.toString().replace(/^(\d+\.\d{3})/);
	context.fillText(RegExp.$1, canvas.width / 2, canvas.height / 2);

	div.removeChild(canvas);
	}

	function copyFrame() {
	var thumbs = document.getElementById('thumbs');
	var vEle = document.getElementById('v');

	if (previousTime == 0) {
	vEle.currentTime = firstOffset;
	}

	if (previousTime >= vEle.currentTime) {
	window.setTimeout(arguments.callee, 1000 * samplingInterval);
	return;
	}
	previousTime = vEle.currentTime;

	window.setTimeout(arguments.callee, 1000 * samplingInterval);
	snapshot(vEle, thumbs);
	}

	</script>
	</head>
	<body onload="copyFrame(0);worker();showGraph();">
	<!-- this video must be on the same server -->
	<video src="./kairiimino_gu.mp4" controls width="480" id="v" autoplay></video>

	<ol id="list"></ol>
	<div id="thumbs"></div>
	<div id="graph-wrapper">
	<canvas id="graph" width="300" height="225"></canvas>
	</div>
	</body>
	</html>