1d:{"title":"Variations on Symmetric Nearest Neighbour smoothing","cells":[{"id":0,"value":"$1f","pinned":false,"hidden":false,"mode":"ojs"},{"id":35,"value":"tulip = await new Promise((resolve, reject) => {\n const image = new Image();\n image.crossOrigin = \"anonymous\";\n image.onerror = reject;\n image.onload = () => {\n resolve(image);\n };\n image.src = \"https://blindedcyclops.neocities.org/ObservableData/SNN/tulip.jpg\";\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":999,"value":"kiss = await new Promise((resolve, reject) => {\n const image = new Image();\n image.crossOrigin = \"anonymous\";\n image.onerror = reject;\n image.onload = () => {\n // image is 1200 x 600 pixels,\n // if width is less than that we crop \n // rather than resize to avoid artefacts\n if (width >= 1200) resolve(image);\n const ctx = DOM.context2d(width, 600);\n ctx.drawImage(image, 0, 0);\n resolve(ctx.canvas);\n };\n image.src = \"https://blindedcyclops.neocities.org/ObservableData/SNN/kiss.jpg\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":115,"value":"md`The tulip photo was picked because it is blurry at the edges, having nice examples of gradients in real-world photos, but also has elements that are in sharp focus. The dust in the corner will be a good point of reference too. The kissing couple combines fog with grain to create a very noisy signal that human eyes can extract information from quite well, but naive image filters tend to struggle with (for example, the subtle brick road texture that fades away).\n\nFirst we should recreate the original Symmetric Nearest Neighbour filter. This is done by combining a symmetric nearest neighbour selection algorithm with a box blur. Let's start with implementing the box blur to see if that works as expected:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":93,"value":"$20","pinned":true,"hidden":false,"mode":"ojs"},{"id":96,"value":"boxblurTulip = {\n const blurParams = makeFilterParams(tulipData, 10);\n return makeFilterWorker(boxblur, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1010,"value":"boxblurKiss = {\n const blurParams = makeFilterParams(kissData, 10);\n return makeFilterWorker(boxblur, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":81,"value":"md`Next we write a generic \\`selectNearest\\` selection function. To make it easier to plug into our filters, it will be applied directly to the \\`Uint8Array\\` of the image data, and return the index of the picked color in that array:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":22,"value":"$21","pinned":true,"hidden":false,"mode":"ojs"},{"id":1021,"value":"gaussianBlurSNNKiss = {\n const blurParams = makeFilterParams(kissData, 10);\n return makeFilterWorker(gaussianBlurSNN, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":23,"value":"$22","pinned":true,"hidden":false,"mode":"ojs"},{"id":223,"value":"$23","pinned":false,"hidden":false,"mode":"ojs"},{"id":32,"value":"$24","pinned":true,"hidden":false,"mode":"ojs"},{"id":194,"value":"md`Works like a charm! Ok, onto turning that into a symmetric nearest neighbour variant:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":46,"value":"boxblurSNNTulip = {\n const blurParams = makeFilterParams(tulipData, 10);\n return makeFilterWorker(boxblurSNN, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1013,"value":"boxblurSNNKiss = {\n const blurParams = makeFilterParams(kissData, 10);\n return makeFilterWorker(boxblurSNN, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":134,"value":"$25","pinned":false,"hidden":false,"mode":"ojs"},{"id":1289,"value":"function bellcurvish2D(radius) {\n const p = new Uint32Array(radius+1);\n for (let i = 0; i <= (radius+1)/2; i++){\n for (let j = 0; j <= radius/2; j++) {\n p[i+j]++;\n }\n }\n const q = new Uint32Array(p.length*2 - 1);\n for (let i = 0; i < p.length; i++){\n for (let j = 0; j < p.length; j++) {\n q[i+j] += p[j];\n }\n }\n \n let total = 0;\n const quadratic2D = [];\n for (let i = 0; i < q.length; i++){\n const c = q[i];\n const q2 = [];\n for(let j = 0; j < q.length; j++){\n const val = c * q[j];\n total += val;\n q2.push(val);\n }\n quadratic2D.push(q2);\n }\n const norm = 1/total;\n for (let i = 0; i < q.length; i++){\n for(let j = 0; j < q.length; j++){\n quadratic2D[i][j] *= norm;\n }\n }\n return quadratic2D;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":163,"value":"md`Now let's write a Gaussian(ish) blur:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":169,"value":"function gaussianBlur({source, width, height, radius}) {\n if (!(radius > 0)) return source.slice();\n let target = new Uint8ClampedArray(source.length);\n const kernel2 = bellcurvish2D(radius);\n \n const {min, max} = Math;\n for(let y = 0; y < height; y++) {\n const line = y * width * 4;\n for (let x = 0; x < width; x++) {\n let r = 0;\n let g = 0;\n let b = 0;\n for (let dy = -radius; dy <= radius; dy++) {\n const line_dy = min(max(0, y + dy), height-1) * width;\n for (let dx = -radius; dx <= radius; dx++) {\n const idx = (min(max(0, x + dx), width-1) + line_dy) * 4;\n const weight = kernel2[radius + dx][radius + dy];\n r += source[idx] * weight;\n g += source[idx + 1] * weight;\n b += source[idx + 2] * weight;\n }\n }\n const cIdx = x*4 + line;\n target[cIdx] = r;\n target[cIdx+1] = g;\n target[cIdx+2] = b;\n target[cIdx+3] = 255;\n }\n }\n\n return target;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":87,"value":"md`Now we can plug that \\`selectNearest\\` function into our simple box blur:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":181,"value":"gaussianBlurTulip = {\n const blurParams = makeFilterParams(tulipData, 10);\n return makeFilterWorker(gaussianBlur, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1017,"value":"gaussianBlurKiss = {\n const blurParams = makeFilterParams(kissData, 10);\n return makeFilterWorker(gaussianBlur, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":208,"value":"gaussianBlurSNNTulip = {\n const blurParams = makeFilterParams(tulipData, 10);\n return makeFilterWorker(gaussianBlurSNN, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":203,"value":"$26","pinned":true,"hidden":false,"mode":"ojs"},{"id":1685,"value":"$27","pinned":false,"hidden":false,"mode":"ojs"},{"id":1687,"value":"gaussianBlurSFNTulip = {\n const blurParams = makeFilterParams(tulipData, 10);\n return makeFilterWorker(gaussianBlurSFN, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2037,"value":"gaussianBlurSFNKiss = {\n const blurParams = makeFilterParams(kissData, 10);\n return makeFilterWorker(gaussianBlurSFN, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1694,"value":"md`So our edge-enhancing blur turned into an edge-*inverting* blur. That might seem kind of useless at first beyond intentional glitch art, but think about what basically happened here: if we pick the color that is the least like the central one, then pixels near an edge will likely pick a color outside of the edge. So the pixels near an edge will \"flip\", as we see in the above images, and the closer to the edge the stronger the flip.\n\nThis means that our Symmetrical Furthest Neighbour selection method responds most strongly to edges. So perhaps by combining nearest and furthers neighbour selection we could create a form of edge detection?`","pinned":false,"hidden":false,"mode":"ojs"},{"id":918,"value":"$28","pinned":true,"hidden":false,"mode":"ojs"},{"id":1721,"value":"$29","pinned":true,"hidden":false,"mode":"ojs"},{"id":1742,"value":"symmetricalNeighbourEdgeDetectTulip = {\n const blurParams = makeFilterParams(tulipData, 10);\n return makeFilterWorker(symmetricalNeighbourEdgeDetection, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":252,"value":"$2a","pinned":false,"hidden":false,"mode":"ojs"},{"id":1759,"value":"symmetricalNeighbourEdgeDetectKiss = {\n const blurParams = makeFilterParams(kissData, 10);\n return makeFilterWorker(symmetricalNeighbourEdgeDetection, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2234,"value":"$2b","pinned":false,"hidden":false,"mode":"ojs"},{"id":2241,"value":"symmetricalNeighbourEdgeDetectAbsoluteTulip = {\n const blurParams = makeFilterParams(tulipData, 10);\n return makeFilterWorker(symmetricalNeighbourEdgeDetectionAbsolute, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2238,"value":"symmetricalNeighbourEdgeDetectAbsoluteKiss = {\n const blurParams = makeFilterParams(kissData, 10);\n return makeFilterWorker(symmetricalNeighbourEdgeDetectionAbsolute, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1715,"value":"md`Looks like it works! Even the subtle brickwork in the kissing couple photo is slightly highlighted.\n\nNow that we have edge-detection we can use it to sharpen images. As a point of comparison, let's first look at a more traditional method: the [unsharp mask](https://en.wikipedia.org/wiki/Unsharp_masking). It turns out that once you have a Gaussian blur, you can quite easily implement a basic unsharp mask by subtracting the inverted version of the blurred image from the original image. The linked wikipedia article explains it in more detail, but here is an implementation:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":231,"value":"$2c","pinned":true,"hidden":false,"mode":"ojs"},{"id":235,"value":"unsharpMaskTulip = {\n const blurParams = makeFilterParams(tulipData, 10);\n return makeFilterWorker(unsharpMask, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1025,"value":"unsharpMaskKiss = {\n const blurParams = makeFilterParams(kissData, 10);\n return makeFilterWorker(unsharpMask, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":302,"value":"md`There we go! One unsharp mask, with all the familiar halos and over-sharpened noise. \n\nSo how to turn our earlier symmetric neighbour edge-detection method into a sharpening filter? Well, the output of the first edge-detection function showed darker or lighter pixels near edges, with lightness depending on which \"side\" of the edge our filter was on - a bit like a positive or negative sign. We did that by subtracting the difference of the sum of the nearest and furthest neighbors from a neutral gray value. All we have to do now is replace this neutral grey value with the value of the original pixel:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1807,"value":"$2d","pinned":true,"hidden":false,"mode":"ojs"},{"id":1810,"value":"symmetricalNeighbourSharpenTulip = {\n const blurParams = makeFilterParams(tulipData, 10);\n return makeFilterWorker(symmetricalNeighbourSharpen, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1815,"value":"symmetricalNeighbourSharpenKiss = {\n const blurParams = makeFilterParams(kissData, 10);\n return makeFilterWorker(symmetricalNeighbourSharpen, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2035,"value":"$2e","pinned":false,"hidden":false,"mode":"ojs"},{"id":2054,"value":"$2f","pinned":true,"hidden":false,"mode":"ojs"},{"id":2056,"value":"symmetricalNeighbourSharpenNoHaloTulip = {\n const blurParams = makeFilterParams(tulipData, 10);\n return makeFilterWorker(symmetricalNeighbourSharpenNoHalo, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2065,"value":"symmetricalNeighbourSharpenNoHaloKiss = {\n const blurParams = makeFilterParams(kissData, 10);\n return makeFilterWorker(symmetricalNeighbourSharpenNoHalo, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2078,"value":"md`Well, the halos are indeed gone! But isn't this just like our earlier Gaussian SNN blur now? It does look similar, but upon closer inspection we can see that contrast in fine details has been enhanced in this version: the dust in the upper-left corner of the tulip photo was smoothed away in the GSNNB filter, while it survives here. Similarly, small highlights in the kissing couple photo, like the lights in the background and the reflections on the bike were slightly blurred out with the GSNNB, while their contrast is higher in these outputs.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":911,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":669,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":680,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":684,"value":"boxblurSNNTwoPassTulip = {\n const blurParams = makeFilterParams(tulipData, 10);\n return makeFilterWorker(boxblurSNNTwoPass, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1053,"value":"boxblurSNNTwoPassKiss = {\n const blurParams = makeFilterParams(kissData, 10);\n return makeFilterWorker(boxblurSNNTwoPass, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":690,"value":"md`That turned out... surprisingly good actually? And since it now scales a lot better we can try using a big radius and see what the results are:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":778,"value":"bigboxblurTwoPassTulipSNN = {\n const blurParams = makeFilterParams(tulipData, 50);\n return makeFilterWorker(boxblurSNNTwoPass, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1064,"value":"bigboxblurTwoPassKissSNN = {\n const blurParams = makeFilterParams(kissData, 50);\n return makeFilterWorker(boxblurSNNTwoPass, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1837,"value":"md`... I'm not sure what I was expecting: I mentioned before that when the radius is too big, we get \"inversion\" problems. There is nothing about the two-pass version that would avoid this problem, so obviously we should see that effect too. \n\nSo if this works for box blur, we should expect the Gaussian blur to work as well. We need the one-dimensional version of our bellcurve approximation, but otherwise the principle is the same:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1363,"value":"function bellcurvish1D(radius) {\n const p = new Uint32Array(radius+1);\n for (let i = 0; i <= (radius+1)/2; i++){\n for (let j = 0; j <= radius/2; j++) {\n p[i+j]++;\n }\n }\n const q = new Uint32Array(p.length*2 - 1);\n for (let i = 0; i < p.length; i++){\n for (let j = 0; j < p.length; j++) {\n q[i+j] += p[j];\n }\n }\n\n const quadratic = [];\n for (let v of q){\n quadratic.push(v*v);\n }\n return quadratic;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":701,"value":"$33","pinned":true,"hidden":false,"mode":"ojs"},{"id":704,"value":"gaussianBlurSNNTwoPassTulip = {\n const blurParams = makeFilterParams(tulipData, 10);\n return makeFilterWorker(gaussianBlurSNNTwoPass, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":1056,"value":"gaussianBlurSNNTwoPassKiss = {\n const blurParams = makeFilterParams(kissData, 10);\n return makeFilterWorker(gaussianBlurSNNTwoPass, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2109,"value":"md`Also working fine. And finally, let's try adapting our no-halo sharpening:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2084,"value":"$34","pinned":true,"hidden":false,"mode":"ojs"},{"id":2090,"value":"symmetricalNeighbourSharpenNoHaloTwoPassTulip = {\n const blurParams = makeFilterParams(tulipData, 10);\n return makeFilterWorker(symmetricalNeighbourSharpenNoHaloTwoPass, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2091,"value":"\nsymmetricalNeighbourSharpenNoHaloTwoPassKiss = {\n const blurParams = makeFilterParams(kissData, 10);\n return makeFilterWorker(symmetricalNeighbourSharpenNoHaloTwoPass, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2142,"value":"md`Well, our two-pass version unsharpens, but it also re-introduces the halos and amplefies the grain noise again. Less so than a naive unsharp mask though. It may also be a matter of tweaking the strength of the filter through other means, because if I set the radius to 5 we seem to hit a sweet spot in sharpening without visible halos:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2164,"value":"symmetricalNeighbourSharpenNoHaloTwoPassTulip5 = {\n const blurParams = makeFilterParams(tulipData, 5);\n return makeFilterWorker(symmetricalNeighbourSharpenNoHaloTwoPass, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2161,"value":"\nsymmetricalNeighbourSharpenNoHaloTwoPassKissR5 = {\n const blurParams = makeFilterParams(kissData, 5);\n return makeFilterWorker(symmetricalNeighbourSharpenNoHaloTwoPass, blurParams);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":2171,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":166,"value":"html`

`","pinned":false,"hidden":false,"mode":"ojs"},{"id":38,"value":"tulipData = {\n width; // trigger resize when going to fullscreen, or landscape on mobile\n const ctx = DOM.context2d(tulip.width, tulip.height, 1);\n ctx.drawImage(tulip, 0, 0, ctx.canvas.width, ctx.canvas.height);\n const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);\n return imageData;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1005,"value":"kissData = {\n width;\n const ctx = DOM.context2d(kiss.width, kiss.height, 1);\n ctx.drawImage(kiss, 0, 0, ctx.canvas.width, ctx.canvas.height);\n const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);\n return imageData;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":1028,"value":"function makeFilterParams(imageData, radius) {\n return {\n source: imageData.data,\n width: imageData.width,\n height: imageData.height,\n radius,\n };\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":544,"value":"$36","pinned":true,"hidden":false,"mode":"ojs"},{"id":1112,"value":"function identityFilter({source}){\n return source;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":568,"value":"$37","pinned":true,"hidden":false,"mode":"ojs"}],"files":"$W38","stdlib":"1"}