31:T9f6,fillReservoirWithReservoirSampling = { // From https://en.wikipedia.org/wiki/Reservoir_sampling // // (* S has items to sample, R will contain the result *) // ReservoirSample(S[1..n], R[1..k]) // // fill the reservoir array // for i = 1 to k // R[i] := S[i] // (* random() generates a uniform (0,1) random number *) // W := exp(log(random())/k) // while i <= n // i := i + floor(log(random())/log(1-W)) + 1 // if i <= n // (* replace a random item of the reservoir with item i *) // R[randomInteger(1,k)] := S[i] // random index between 1 and k, inclusive // W := W * exp(log(random())/k) function fillReservoir({ video, k = 10, n, resolve, invalidation }) { // TODO: give a framerate, in order to avoid considering the same frame several times // if the animation frames are more frequent than the video frames // TODO: do an independent reservoir sorting per pixel, instead of per image? const reservoir = []; let frameIdx = 0; let i = 0; let lastRequest; video.currentTime = 0; let W = Math.exp(Math.log(Math.random()) / k); function end() { cancelAnimationFrame(lastRequest); video.removeEventListener('play', iterate); video.removeEventListener('pause', end); video.pause(); resolve(reservoir); } function iterate() { console.log(i, n, reservoir); if (n && frameIdx >= n) { end(); } else { if (frameIdx < k) { // Initialize const canvas = html`

`; canvas.getContext('2d').drawImage(video, 0, 0); reservoir[frameIdx] = canvas; lastRequest = requestAnimationFrame(iterate); } else { if (frameIdx >= i) { // process const randomInteger = Math.floor(Math.random() * k); reservoir[randomInteger].getContext('2d').drawImage(video, 0, 0); W *= Math.exp(Math.log(Math.random()) / k); // next i i += Math.floor(Math.log(Math.random()) / Math.log(1 - W)) + 1; } lastRequest = requestAnimationFrame(iterate); } frameIdx += 1; } } video.addEventListener('play', iterate); video.addEventListener('pause', end); invalidation.then(() => end); video.play(); } return ({ video, k }) => new Promise(resolve => fillReservoir({ video, k, resolve, invalidation })); }32:[{"id":"ba1f6be562219f0613bdb27a96a5032ebecceadd6c42996809f75723f2b64863f742e1e56f6b8ff86feee71f70073015a418370698303b6bf2e286d7e94077cd","href":"https://static.observableusercontent.com/files/ba1f6be562219f0613bdb27a96a5032ebecceadd6c42996809f75723f2b64863f742e1e56f6b8ff86feee71f70073015a418370698303b6bf2e286d7e94077cd","name":"road.mp4","type":"video/mp4","lastModified":1607541042647.727,"size":1976377}] 2f:{"title":"Compute the approximate median image of a video","cells":[{"id":0,"value":"md`# Compute the approximate median image of a video\n\n\nInstall with\n\n~~~js\nimport {videoMedian} from '@severo/compute-the-approximate-median-image-of-a-video'\n~~~\n\nUsage\n\n~~~js\nmedianImage = videoMedian(videoUrl)\nmedianImage = videoMedian(videoUrl, {k: 10, crossOrigin=\"anonymous\"})\n~~~\n\nThe options are:\n\n- \\`k\\`: number of frames to sample in the video. Defaults to ${defaultK}.\n- \\`crossOrigin\\`: [CORS setting](https://developer.mozilla.org/en-US/docs/Web/API/HTMLMediaElement/crossOrigin) to retrieve the video. Defaults to undefined.\n\n## Try it\n\nSelect a video:\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":48,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":15,"value":"viewof videoUrl = text({\n value: await FileAttachment(\"road.mp4\").url(),\n submit: true,\n description: \"Enter a video URL\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":152,"value":"md`We sample k frames from the n frames in the original video in order to reduce the memory footprint and to keep the computation time low.\n\nNote: we previously used a [reservoir sampling](https://en.wikipedia.org/wiki/Reservoir_sampling) to get the k frames, but this only is useful in case the length of the video is not known (ie streaming). Here we sample must faster by jumping directly to the next frame.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":12,"value":"viewof k = number({\n description: 'select the size of the reservoir',\n format: d => `k = ${d}`,\n step: 1,\n min: 1,\n max: 50,\n value: 10\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":166,"value":"md`The median value of every pixel is:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":70,"value":"{\n const c = await videoMedian(videoUrl, { k, crossOrigin: \"anonymous\" });\n c.style.setProperty('max-width', `${width}px`);\n return c;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":126,"value":"md`---\n\n### Credits\n\n_Developed for the [LIRIS M2i project](https://projet.liris.cnrs.fr/mi2/) by Sylvain Lesage._\n\nThanks a lot to [@altocumulus](https://observablehq.com/@altocumulus) for its optimization that makes the code usable. They replace d3.median() with a custom function that avoids type conversions between Uint8Clamped and Float64 values, and directly compute the median instead of a generic quantile. See their [good answer on Stack Overflow](https://stackoverflow.com/a/65255365/7351594).\n\n---\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":177,"value":"md`### CHANGELOG\n\n- 2020/12/11: provide a single importable function\n- 2020/12/11: replace reservoir sampling by a simple sampling, jumping directly to the required frames instead of playing the video\n- 2020/12/11: optimization by @altocumulus: replace d3.median by a custom median function that remove unnecessary type casts and avoid generic quantile code\n- 2020/12/09: creation\n\n### TODO\n\n- do an independent reservoir sampling per pixel, instead of per image. Not sure if it would change much\n- provide a seed to allow reproductibility\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":240,"value":"md`### Data`","pinned":false,"hidden":false,"mode":"ojs"},{"id":244,"value":"defaultK = 20","pinned":false,"hidden":false,"mode":"ojs"},{"id":333,"value":"defaultCrossOrigin = undefined","pinned":false,"hidden":false,"mode":"ojs"},{"id":131,"value":"md`### Code`","pinned":false,"hidden":false,"mode":"ojs"},{"id":33,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":197,"value":"async function fillReservoir(videoUrl, { k, crossOrigin }) {\n const duration = (await vidvid.info(videoUrl, { crossOrigin })).duration;\n const times = Array.from({ length: k })\n .map(_ => Math.random() * duration)\n .sort();\n return Promise.all(times.map(t => frameAt(videoUrl, t, { crossOrigin })));\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":115,"value":"// Code by @altocumulus - https://stackoverflow.com/a/65255365/7351594\nfunction median(values) {\n if (!(n = values.length)) return;\n if (n < 2) return d3.min(values);\n var n,\n i = (n - 1) * 0.5,\n i0 = Math.floor(i),\n value0 = d3.max(d3.quickselect(values, i0).subarray(0, i0 + 1)),\n value1 = d3.min(values.subarray(i0 + 1));\n return value0 + (value1 - value0) * (i - i0);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":68,"value":"function canvasMedian(canvases) {\n const width = canvases[0].width;\n const height = canvases[0].height;\n const imageDatas = canvases.map(\n canvas => canvas.getContext('2d').getImageData(0, 0, width, height).data\n );\n const medianImageData = new ImageData(width, height);\n const arr = new Uint8ClampedArray(imageDatas.length);\n\n for (let i = 0; i < medianImageData.data.length; i += 1) {\n for (let j = 0; j < imageDatas.length; j += 1) {\n arr[j] = imageDatas[j][i];\n }\n // Optimized remplacing d3.median with custom median function. See https://stackoverflow.com/questions/65224990/efficient-way-to-compute-the-median-of-an-array-of-canvas-in-javascript\n medianImageData.data[i] = median(arr);\n }\n\n const medianCanvas = html`

`;\n medianCanvas.getContext('2d').putImageData(medianImageData, 0, 0);\n return medianCanvas;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":233,"value":"async function videoMedian(\n videoUrl,\n { k = defaultK, crossOrigin = defaultCrossOrigin } = {}\n) {\n const reservoir = await fillReservoir(videoUrl, { k, crossOrigin });\n return canvasMedian(reservoir);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":138,"value":"md`### Dependencies`","pinned":false,"hidden":false,"mode":"ojs"},{"id":207,"value":"import { frameAt } from \"@severo/frameat\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":263,"value":"vidvid = import('https://unpkg.com/vidvid-info?module')","pinned":false,"hidden":false,"mode":"ojs"},{"id":9,"value":"import { number, text } from '@jashkenas/inputs'","pinned":false,"hidden":false,"mode":"ojs"},{"id":75,"value":"d3=require('d3@6')","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}