2d:null 2e:["$","title",null,{"children":"Compute the approximate median image of a video | altocumulus | Observable"}] 33:T705,fillReservoir = { function fillReservoir({ video, k = 10, n, resolve }) { // TODO: give a framerate, in order to avoid considering the same frame several times // TODO: do an independent reservoir sorting per pixel, instead of per image? // // if the animation frames are more frequent than the video frames 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() { 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); video.play(); } return ({ video, k, n }) => new Promise(resolve => fillReservoir({ video, k, n, resolve })); }34:[{"id":"ba1f6be562219f0613bdb27a96a5032ebecceadd6c42996809f75723f2b64863f742e1e56f6b8ff86feee71f70073015a418370698303b6bf2e286d7e94077cd","href":"https://static.observableusercontent.com/files/ba1f6be562219f0613bdb27a96a5032ebecceadd6c42996809f75723f2b64863f742e1e56f6b8ff86feee71f70073015a418370698303b6bf2e286d7e94077cd","name":"road.mp4","type":"video/mp4","lastModified":1607704764972.15,"size":1976377}] 31:{"id":"0ab3c75dee7d2a82","slug":"compute-the-approximate-median-image-of-a-video","title":"Compute the approximate median image of a video","thumbnail":"7faec4efe79f18764476f4cd6ebf604eca597ee77b54995671cd1f7345a7a8e0","access_level":"public","create_time":"$D2020-12-11T16:39:24.972Z","update_time":"$D2020-12-12T13:29:24.097Z","view_time":null,"first_public_time":"$D2020-12-11T16:46:50.260Z","has_unpublished_edits":null,"fork":{"id":"3f2bbe12cc2dcdaf","slug":"compute-the-approximate-median-image-of-a-video","title":"Compute the approximate median image of a video","owner":{"id":"5c7b4ebed88da11a","login":"severo","name":"Sylvain Lesage"}},"stars":0,"starred":false,"owner":{"type":"team","id":"6a229820e7579a62","login":"altocumulus","name":"","avatar_url":"https://avatars-next.observableusercontent.com/532e117eb4113ec43ce66faa7411ece2d816938addb1f31e7b78876c58ad43e7","tier":"starter_2024","bio":""},"version":118,"publish_version":118,"role":null,"authored":false,"authors":[{"type":"individual","id":"4800ef41a3463eab","login":"altocumulus","name":"","avatar_url":"https://avatars-next.observableusercontent.com/532e117eb4113ec43ce66faa7411ece2d816938addb1f31e7b78876c58ad43e7","tier":null,"bio":""}],"members":[{"type":"individual","id":"4800ef41a3463eab","login":"altocumulus","name":"","avatar_url":"https://avatars-next.observableusercontent.com/532e117eb4113ec43ce66faa7411ece2d816938addb1f31e7b78876c58ad43e7","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Compute the approximate median image of a video","cells":[{"id":0,"value":"md`# Compute the approximate median image of a video\n\nWe use a [reservoir sampling](https://en.wikipedia.org/wiki/Reservoir_sampling) to keep the number of data in memory low (k frames, instead of n frames in the original video).\n\nOnce the sampling is done (after a sufficient number of video frames have been played), the median value of every pixel is computed.\n\n`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"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: 20,\n value: 4\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"viewof video = videoInput({\n crossOrigin: \"anonymous\",\n initialUrl: await FileAttachment(\"road.mp4\").url() \n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"// (* S has items to sample, R will contain the result *)\n// ReservoirSample(S[1..n], R[1..k])\n// // fill the reservoir array\n// for i = 1 to k\n// R[i] := S[i]\n// (* random() generates a uniform (0,1) random number *)\n// W := exp(log(random())/k)\n// while i <= n\n// i := i + floor(log(random())/log(1-W)) + 1\n// if i <= n\n// (* replace a random item of the reservoir with item i *)\n// R[randomInteger(1,k)] := S[i] // random index between 1 and k, inclusive\n// W := W * exp(log(random())/k)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":48,"value":"video","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":35,"value":"reservoir = await fillReservoir({ video, k })","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":33,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":114,"value":"function 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":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":68,"value":"function canvasMedian(canvases) {\n // TODO: optimize - see https://stackoverflow.com/questions/65224990/efficient-way-to-compute-the-median-of-an-array-of-canvas-in-javascript\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 medianImageData.data[i] = median(arr);\n }\n\n const medianCanvas = html`

`;\n medianCanvas.getContext('2d').putImageData(medianImageData, 0, 0);\n return medianCanvas;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":70,"value":"canvasMedian(reservoir)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":97,"value":"reservoir[0]\n .getContext('2d')\n .getImageData(0, 0, video.videoWidth, video.videoHeight).data","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":9,"value":"import { number } from '@jashkenas/inputs'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":16,"value":"import { videoInput } from '@den1k/file-input'","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":75,"value":"d3=require('d3@6')","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W34","stdlib":"1"}} 32:"$31:body"