28:null 29:["$","title",null,{"children":"Voronoi mosaics | Claudio Esperança | Observable"}] 2e:T44e,md`# Voronoi mosaics A sample implementation of the paper [A Method for Creating Mosaic Images Using Voronoi Diagrams](https://diglib.eg.org/handle/10.2312/egs20021036?show=full) by Yoshinori Dobashi and Toshiyuki Haga, Henry Johan, and Tomoyuki Nishita (Eurographics Short Presentations, 2002, DOI: 10.2312/egs.20021036). The idea is to start with a semi-regular Voronoi diagram, where each cell is painted with the color of the pixel at the site center. In the GUI below, jitter controls the amount of noise initially added to the site centers, whereas cellSize is the average diameter of each cell. After this, all cell centers are moved one pixel at a time in the direction that minimizes color error. This is repeated a number of times (parameter steps below). The demo picture is picked at random from Unsplash, a trick I learned in the excellent [Seam Carving sketch](https://observablehq.com/@jobleonard/seam-carving-with-forward-energy-but-we-make-a-new-image-with) by Job van der Zwan. By default, butterfly pictures are selected, but you can choose another subject in the GUI below. ` 2f:T4ec,voronoiImageGL = function (w, h, cells, getPixel = null) { let canvas = DOM.canvas(w,h); let gl = canvas.getContext('webgl', {antialias:getPixel != null, preserveDrawingBuffer: true}); let regl = createRegl (gl); let posBuffer = [], colorBuffer = []; let i = 0; for (let [center,poly] of cells) { if (!poly) continue; let [cx,cy] = center; let {r,g,b} = getPixel ? getPixel(~~cx,~~cy) : {r : i%256, g:~~(i/256), b: 255}; let [v0,v1] = [poly[0],poly[1]] for (let v2 of poly.slice(2)) { for (let [x,y] of [v0,v1,v2]) { posBuffer.push(x/w*2-1, 1-y/h*2) colorBuffer.push(r/255,g/255,b/255) } v1 = v2; } i++; } let draw = regl({ frag: ` precision mediump float; varying vec3 vcolor; void main () { gl_FragColor = vec4(vcolor,1.0); }`, vert: ` attribute vec2 position; attribute vec3 color; varying vec3 vcolor; void main () { gl_Position = vec4(position, 0, 1); vcolor = color; }`, attributes: { position: posBuffer, color: colorBuffer }, count: posBuffer.length/2 }); regl.clear({ color: [0, 0, 0, 1] }) draw() return canvas }30:T81a,optimizeCenters = function (points,imgdata,steps = 1) { let data = imgdata.data; let [w,h] = [imgdata.width,imgdata.height] //let points = voronoiCenters(w,h,cellSize,jitter) for (let step = 0; step < steps; step++) { let cells = voronoiCells(w,h,points) let vimage = voronoiImageGL(w,h,cells); let vdata = imageData(vimage).data; function index(x,y) { return (y*w+x)*4; } function center(x,y) { let i = index(x,y); return vdata[i]+vdata[i+1]*256; } function getPixel(x,y) { let i = index(~~x,~~y); return [data[i],data[i+1],data[i+1]] } function pixelError (rgb1,rgb2) { return (rgb1[0]-rgb2[0])**2+(rgb1[1]-rgb2[1])**2+(rgb1[2]-rgb2[2])**2 } let error = points.map (p => ({ rgb : getPixel(p[0],p[1]), dir : [0,0,0,0,0,0,0,0] })); let totalError = 0; let dir = [[1,0],[-1,0],[1,1],[-1,-1],[0,1],[0,-1],[1,-1],[-1,1]]; for (let x = 1; x+1 < w; x++) { for (let y = 1; y+1 < h; y++) { let c = center(x,y); let rgb = getPixel(x,y); let curError = pixelError (error[c].rgb, rgb); totalError += curError; let count = 0; for (let idir = 0; idir < 8; idir++) { let [dx,dy] = dir [idir]; let neighbor = center(x+dx,y+dy); let opposite = center(x-dx,y-dy); if (neighbor == opposite) continue; let dError = pixelError(error[opposite].rgb,rgb)-curError error[neighbor].dir[idir] += dError error[opposite].dir[idir] += dError } } } for (let i = 0; i < points.length; i++) { let bestdir = -1; let besterror = 0; let errdir = error[i].dir; for (let j = 0; j < 8; j++) { if (errdir [j] < besterror) { bestdir = j; besterror = errdir[j] } } if (bestdir >= 0) { points [i][0] = Math.min(w-1, Math.max(0, points [i][0] + dir[bestdir][0])); points [i][1] = Math.min(h-1, Math.max(0, points [i][1] + dir[bestdir][1])); } } } return points; } 31:[{"id":"470ebdb89e1749e3c9c42f9ef8d3d511afe5d7b7b4911511604658f26de6ccee465710ac139859b58c4423a54e12cc1d30ada5420b78f5d627b48464c0e0fbd7","href":"https://static.observableusercontent.com/files/470ebdb89e1749e3c9c42f9ef8d3d511afe5d7b7b4911511604658f26de6ccee465710ac139859b58c4423a54e12cc1d30ada5420b78f5d627b48464c0e0fbd7","name":"800x600.jpg","type":"image/jpeg","lastModified":1603720652280.83,"size":96454},{"id":"8ad5a29da08e5bc04af9f145fa0dfc0d73dab2b8c5339104736722fbd0f6cefcf93f07d080da84797c6102cba969a39142ee1442fbeb0f87810ef04d13a384a1","href":"https://static.observableusercontent.com/files/8ad5a29da08e5bc04af9f145fa0dfc0d73dab2b8c5339104736722fbd0f6cefcf93f07d080da84797c6102cba969a39142ee1442fbeb0f87810ef04d13a384a1","name":"1024x768.jpg","type":"image/jpeg","lastModified":1603720652277.202,"size":105702},{"id":"6633e156444dfe4259cd14c51c40795ff04cdc68784898ef8b716cc916f0247a5d80b5a714585bbd4a3f9c0224a4b6ba41f60126da41d1de67621bf8449c171a","href":"https://static.observableusercontent.com/files/6633e156444dfe4259cd14c51c40795ff04cdc68784898ef8b716cc916f0247a5d80b5a714585bbd4a3f9c0224a4b6ba41f60126da41d1de67621bf8449c171a","name":"640x480.jpg","type":"image/jpeg","lastModified":1603720649909.2,"size":55952}] 2c:{"id":"3e3320f0bf779803","slug":"voronoi-mosaics","title":"Voronoi mosaics","thumbnail":"bc3459e92c5d81be94ba323aac52bcf15be09d28eba8c9020bc6a617eb1ac82b","access_level":"public","create_time":"$D2020-10-16T19:16:19.017Z","update_time":"$D2020-11-14T13:30:43.376Z","view_time":null,"first_public_time":"$D2020-10-22T23:15:57.715Z","has_unpublished_edits":null,"fork":false,"stars":21,"starred":false,"owner":{"type":"team","id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":"starter_2024"},"version":289,"publish_version":289,"role":null,"authored":false,"authors":[{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null}],"members":[{"type":"individual","id":"591dcad3c6121253","login":"esperanc","name":"Claudio Esperança","avatar_url":"https://avatars-next.observableusercontent.com/91db65fe4bf8e490e5ff1a548612f36ccc04fa7781189e7e4dc7ba6633a66e52","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":true,"trashed":false,"lapsed":null,"subscribed":null,"forks":5,"collection":{"id":"6e2e99f12b8c9dbb","slug":"paper-implementations","title":"Paper implementations","owner":{"id":"e9fcee55f21948e0","login":"esperanc","name":"Claudio Esperança"}},"type":"notebook","body":{"title":"Voronoi mosaics","cells":[{"id":0,"value":"$2e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":30,"value":"viewof mosaicConfig = combo({\n cellSize:number({title:\"Cell size\", value:7, min:4, max:40, step: 1}),\n jitter:number({title:\"Jitter amount\", value:4, min:0, max:20, step: 1}),\n steps:number({title:\"Optimization steps\", value:10, min:1, max:100, step:1}),\n stroke: checkbox({title:\"Cell outlines?\", options:[\"Yes\"], value:\"Yes\"}),\n strokeColor: color({title: \"Outline color\", value:\"#000\"}),\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":26,"value":"mosaic = {\n let {cellSize,margin,jitter,steps,stroke,strokeColor} = mosaicConfig;\n \n let imgdata = imageData(image)\n let [w,h]= [image.width,image.height]\n let ctx = DOM.context2d(w,h,1)\n \n let data = imgdata.data;\n function getPixel (x,y) {\n let i = (y*w+x)*4;\n return {r:data[i],g:data[i+1],b:data[i+2],a:data[i+3]}\n }\n\n let points = voronoiCenters(w,h,cellSize,jitter)\n for (let i = 0; i < steps; i++) {\n points = optimizeCenters (points, imgdata, 1);\n let cells = voronoiCells(w,h,points)\n yield voronoiImage(w,h,cells,getPixel,stroke?strokeColor:null)\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":257,"value":"viewof imageConfig = combo ({\n imgSize:select({title:\"Image size\", options: [\"640x480\", \"800x600\", \"1024x768\"]}),\n subject:text({title:\"Subject\", value:\"butterfly\"}),\n reload:button({value:\"Pick new image\"})\n})\n ","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":10,"value":"image = {\n let {imgSize,subject} = imageConfig;\n let [w,h] = imgSize.split(\"x\").map(x => +x);\n let img;\n try {\n img = await loadImage(await randomImage(w, h, subject));\n }\n catch (error) {\n img = defaultImage[imgSize]\n }\n return img;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":111,"value":"voronoiCenters = function (w,h,cellSize,jitter) {\n let dx = cellSize*2, dy = cellSize/Math.sqrt(3);\n let nx = Math.ceil(w/dx), ny=Math.ceil(h/dy)\n let points = [];\n let flag = false;\n for (let y = cellSize; y < h - cellSize; y += dy) {\n let x0 = flag ? cellSize : dx;\n flag = !flag;\n for (let x = x0; x < w - cellSize; x += dx) {\n points.push ([x+Math.random()*jitter-jitter/2,y+Math.random()*jitter-jitter/2])\n }\n }\n return points\n}\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":116,"value":"voronoiCells = function (w,h,points) {\n let delaunay = d3.Delaunay.from(points)\n let voronoi = delaunay.voronoi([-1, -1, w + 1, h + 1])\n return points.map((d, i) => [d, voronoi.cellPolygon(i)]);\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":120,"value":"voronoiImage = function (w, h, cells, getPixel, strokeColor = null) {\n \n let ctx = DOM.context2d(w,h,1)\n \n for (let [center,poly] of cells) {\n if (!poly) continue;\n let [cx,cy] = center;\n let {r,g,b,a} = getPixel(~~cx,~~cy);\n ctx.fillStyle = ctx.strokeStyle = `rgb(${r},${g},${b})`;\n let [x,y] = poly[0];\n ctx.beginPath()\n ctx.moveTo (x,y)\n for (let [x,y] of poly) {\n ctx.lineTo(x,y)\n }\n ctx.fill()\n if (strokeColor) ctx.strokeStyle = strokeColor;\n ctx.stroke()\n }\n return ctx.canvas\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":125,"value":"$2f","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":139,"value":"$30","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"async function randomImage(sizeOrWidth = null, height = sizeOrWidth, term='flower') {\n const size = sizeOrWidth ? `/${+sizeOrWidth}x${+height}` : '';\n return (await fetch(`https://source.unsplash.com/${+sizeOrWidth}x${+height}/?${term}`, {\n method: 'head',\n cache: 'no-store',\n })).url;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":282,"value":"defaultImage = (\n {\"640x480\": await FileAttachment(\"640x480.jpg\").image(),\n \"800x600\": await FileAttachment(\"800x600.jpg\").image(),\n \"1024x768\": await FileAttachment(\"1024x768.jpg\").image(),\n }\n)","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"loadImage = {\n return function loadImage(src) {\n const img = DOM.element('img', {crossorigin: 'anonymous', src});\n return img.decode().then(() => img);\n };\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":78,"value":"function imageData (image) {\n let [w,h] = [image.width, image.height];\n let ctx = DOM.context2d(w,h,1)\n ctx.imageSmoothingEnabled = false;\n ctx.drawImage(image,0,0)\n return ctx.getImageData (0,0,w,h)\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":128,"value":"md`## Libraries`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":27,"value":"d3 = require(\"d3@6\")","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":132,"value":"createRegl = require('regl@1.4.2/dist/regl.js')","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":245,"value":"import {select,number,radio,text,checkbox,button,color} from \"@jashkenas/inputs\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":247,"value":"import {combo} from \"@esperanc/aggregated-inputs\"","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W31","stdlib":"1","titling":"auto"}} 2d:"$2c:body"