31:T71d,// This is what produces the filtered images, using Canvas2D. It could probably be optimized more. async function filter(func, inImg = curImg) { let img = await inImg; const ctx = DOM.context2d(img.width, img.height); // for bizarre reasons this is sometimes needed on FF ctx.canvas.width = img.width; ctx.canvas.height = img.height; ctx.drawImage(img, 0, 0); const imgData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height); if (img.width !== ctx.canvas.width) throw new Error("mismatched dims " + img.width + " " + ctx.canvas.width); const outData = ctx.createImageData(img.width, img.height); let errsum = 0; const makeGray = conf.includes("Make gray"); // when recalculating all, do paeth last await new Promise(resolve => setTimeout(resolve, 0)); // force non-blocking evaluation for (let idx = 0; idx < imgData.data.length; ++idx) { if ((idx % 4) === 3) { outData.data[idx] = 255; // alpha continue; } const upper = idx <= ctx.canvas.width * 4; const left = idx % (4 * ctx.canvas.width) === 0; let a = left ? 0 : imgData.data[idx - 4]; let b = (upper || left) ? 0 : imgData.data[idx - ctx.canvas.width * 4]; let c = upper ? 0 : imgData.data[idx - ctx.canvas.width * 4 - 4]; let val = func(imgData.data[idx], a, b, c); if (val < 0) throw new Error("got negative val"); if (val > 255) throw new Error("val too big"); const adjVal = mod256(val + 128); errsum += Math.abs(adjVal - 128); if (makeGray) val = adjVal; outData.data[idx] = val; } // return outData.data; ctx.putImageData(outData, 0, 0); ctx.canvas.style.maxWidth = ctx.canvas.width + "px"; ctx.canvas.style.width = "100%"; return html`

${ctx.canvas}

Score: ${errsum.toLocaleString()}

`; }32:[{"id":"29f9d0f08ce789ca34e523d893de19dfccb159e4c338a94181e047ac9ac503aff8051be2fa39d89689d9a4c2826c96f0c6cbc3c032908395d53cb27d3a06e193","href":"https://static.observableusercontent.com/files/29f9d0f08ce789ca34e523d893de19dfccb159e4c338a94181e047ac9ac503aff8051be2fa39d89689d9a4c2826c96f0c6cbc3c032908395d53cb27d3a06e193","name":"eggs-in-basket.png","type":"image/png","lastModified":1635526474514.246,"size":592634},{"id":"a4de5be925819719982db68284580a994db8eb248c460f5a251acbcadcfc0b113e7f02bfa3108ea85bebce654ba092a0c7a512b8cbf03069d8d177ded03acac2","href":"https://static.observableusercontent.com/files/a4de5be925819719982db68284580a994db8eb248c460f5a251acbcadcfc0b113e7f02bfa3108ea85bebce654ba092a0c7a512b8cbf03069d8d177ded03acac2","name":"a256.png","type":"image/png","lastModified":1635529715680.823,"size":49784},{"id":"d5d073033b34f4d2fed85720f1d0bcb4820d76cfe585b73e44f9c5158d53a58e055984b360e8e886513b6685093b6bc2dfffba41b08ca0ebda2be672d80cf673","href":"https://static.observableusercontent.com/files/d5d073033b34f4d2fed85720f1d0bcb4820d76cfe585b73e44f9c5158d53a58e055984b360e8e886513b6685093b6bc2dfffba41b08ca0ebda2be672d80cf673","name":"eggbasket.png","type":"image/png","lastModified":1635627828385.589,"size":165701},{"id":"ce1fe4e158a55a564e22d046b56776fc992ce9912460e5592a89efecf1cb60614fd1c7de47bd9fc7cd2378127a1fe341c0217578347397da00d00d047ef1618a","href":"https://static.observableusercontent.com/files/ce1fe4e158a55a564e22d046b56776fc992ce9912460e5592a89efecf1cb60614fd1c7de47bd9fc7cd2378127a1fe341c0217578347397da00d00d047ef1618a","name":"quadbuttons.png","type":"image/png","lastModified":1635708222967.053,"size":9291}] 2f:{"title":"How PNG compresses images using filters","cells":[{"id":0,"value":"# How PNG compresses images using filters\nPNG compression is surprisingly simple. You take the raw pixel data, filter it, and run it through zlib. The filtering stage doesn't affect the uncompressed size, but instead tries to get it into a form that zlib can compress better. Filtering is the only image-specific compression mechanism used in PNG. PNG compression programs like [Pngcrush](https://pmt.sourceforge.io/pngcrush/) use herusitics to find the optimal zlib parameters that result in the smallest size. By default, Pngcrush just uses the no-op filter, but each scanline of an image can have 1 of 5 different [filters](http://www.libpng.org/pub/png/book/chapter09.html) applied to it for a better compression ratio. The first byte of each filtered line of the image is the filter type. Here's an image I'll be using to demonstrate:","pinned":false,"hidden":false,"mode":"md"},{"id":556,"value":"curImg","pinned":false,"hidden":false,"mode":"ojs"},{"id":771,"value":"*Putting all of your eggs into one basket*","pinned":false,"hidden":false,"mode":"md"},{"id":70,"value":"The idea with all of the filters is to make the image into a form that zlib compresses better. When a decoder reads back the image, it does the inverse of the filter applied to each row to get back the original image. Filtering doesn't reduce the image size by itself, though. Encoders don't have to support filtering: you can set the filter to 0 to make a line unfiltered. And since each line gets its own filter, you can optimize each line to have the best filter.","pinned":false,"hidden":false,"mode":"md"},{"id":317,"value":"## Filters\nHere's the most basic filter: each pixel is stored as the difference between it, and the pixel to the left:","pinned":false,"hidden":false,"mode":"md"},{"id":143,"value":"filter((orig, a, b, c) => mod256(orig - a))","pinned":true,"hidden":false,"mode":"ojs"},{"id":323,"value":"You can edit that code, then hit Shift-Enter to experiment with your own filters. The inputs to `filter` are the pixels to the left (`a`), top (`b`), and upper-left (`c`) of the current pixel (`orig`). \n\n","pinned":false,"hidden":false,"mode":"md"},{"id":336,"value":"\n\n \n \n

c	b
a	orig

","pinned":false,"hidden":false,"mode":"html"},{"id":432,"value":"Pixel values need to be between 0 and 255, so they wrap around when they would go out of range. This makes the image look mostly black and white, since most values are either close to 0, or close to 255 after wrapping around.","pinned":false,"hidden":false,"mode":"md"},{"id":150,"value":"mod256 = x => x & 0xFF","pinned":true,"hidden":false,"mode":"ojs"},{"id":695,"value":" We can make the images look a bit better by displaying the pixel values as signed offsets from gray, so a small offset from 0 doesn't wrap all the way around to 255:","pinned":false,"hidden":false,"mode":"md"},{"id":261,"value":"viewof conf = Inputs.checkbox([\"Make gray\"])","pinned":false,"hidden":false,"mode":"ojs"},{"id":353,"value":"Ideally, the images should look as close as possible to pure gray, since it's a lot easier for zlib to compress data with bytes that are all similar.\n\nHere's what we get when we use the pixel above the current pixel. It's pretty similar.","pinned":false,"hidden":false,"mode":"md"},{"id":146,"value":"filter((orig, a, b, c) => mod256(orig - b))","pinned":true,"hidden":false,"mode":"ojs"},{"id":560,"value":"The score underneath each image is based on a simple heuristic that tries to guess how compressible an image is, the sum of differences from gray. A pure gray image would be the most compressible, and score 0. It looks like the above filtering method is worse then the earlier one (at least when using one filter for the whole image).","pinned":false,"hidden":false,"mode":"md"},{"id":702,"value":"Here's another filter that tries to be smarter, where we take the average of the pixel to the left and above the current one:","pinned":false,"hidden":false,"mode":"md"},{"id":666,"value":"filter((orig, a, b, c) => mod256(orig - mod256(Math.floor((a + b) / 2))))","pinned":true,"hidden":false,"mode":"ojs"},{"id":394,"value":"An even more complicated way to predict pixels is Paeth prediction (which I have even made [a video about](https://www.youtube.com/watch?v=X42MZqXHXDM)). Essentially, this function is pretty good at predicting the next pixel from the three surrounding ones by intelligently choosing a nearby pixel to copy:","pinned":false,"hidden":false,"mode":"md"},{"id":84,"value":"function paeth(a, b, c) {\n const p = a + b - c; // extend the gradient\n // return whatever input is closest to p\n const pa = Math.abs(p - a);\n const pb = Math.abs(p - b);\n const pc = Math.abs(p - c);\n if (pa <= pb && pa <= pc) {\n return a;\n } else if (pb <= pc) {\n return b;\n } else {\n return c;\n }\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":398,"value":"We once again compute the difference from this predicted value:","pinned":false,"hidden":false,"mode":"md"},{"id":138,"value":"filter((orig, a, b, c) => mod256(orig - paeth(a, b, c)))","pinned":true,"hidden":false,"mode":"ojs"},{"id":766,"value":"If you want to play around more, you can change the image used in the above examples:","pinned":false,"hidden":false,"mode":"md"},{"id":515,"value":"viewof curImg = imageInput({\n crossOrigin: \"anonymous\",\n initialUrl: await FileAttachment(\"eggbasket.png\").url()\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":840,"value":"## Where is each filter best?","pinned":false,"hidden":false,"mode":"md"},{"id":843,"value":"Remember that each line of an image can have its own filter. As such, we want to select the best filter for each line, not the image as a whole. I use the same filter for each line of the image in these examples so you can see the effects of the filters more clearly.","pinned":false,"hidden":false,"mode":"md"},{"id":850,"value":"Here's all of the filters again. ${conf.includes(\"Make gray\") ? \"The No-op one looks weird because of the gray-adjustment.\" : \"\"}","pinned":false,"hidden":false,"mode":"md"},{"id":814,"value":"filterGrid()","pinned":false,"hidden":false,"mode":"ojs"},{"id":862,"value":"The easiest way for a PNG encoder to determine what combination of filters to use is to brute force it: see what combination of filters on each line works best. This would take far too long though. Instead, encoders use heuristics to guess what filters results in the most zlib compression. Traditionally, the *least differences method* is used. The offset of each pixel from gray is calculated when using each filter on a given line, and whatever filter results in the least differences from gray is used. Underneath each image I have the total least squares when the filter is applied to all lines of then image.","pinned":false,"hidden":false,"mode":"md"},{"id":889,"value":"filterGrid(FileAttachment(\"quadbuttons.png\").image())","pinned":false,"hidden":false,"mode":"ojs"},{"id":897,"value":"For mostly rectangular shapes, Left only needs to encode the pixels on the left and right side. Up only needs the top and bottom. Paeth manages to only do the edges, getting the best of both worlds here by dynamically choosing what pixel to copy for each pixel. Average doesn't fare very well, encoding the whole outline. In my testing, Average performs poorly for most lines, and Paeth tends to do the best. It wouldn't be unreasonable for PNG compressors to ignore Average when selecting a filter.","pinned":false,"hidden":false,"mode":"md"},{"id":53,"value":"## Appendix\nThe [egg basket example image](https://commons.wikimedia.org/wiki/File:Eggs_in_basket_2020_G1.jpg), by George Chernilevsky, is licensed under the terms of [CC-BY-SA-4.0](https://creativecommons.org/licenses/by-sa/4.0/deed.en). My avatar [can be used under the terms of CC0-1.0](https://smitop.com/avatar/). Everything else is licensed under the terms of [Apache-2.0](https://www.apache.org/licenses/LICENSE-2.0).","pinned":false,"hidden":false,"mode":"md"},{"id":687,"value":"### Filtering functions\nThese functions are responsible for creating the filtered images used in this notebook.","pinned":false,"hidden":false,"mode":"md"},{"id":74,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":808,"value":"async function filterGrid(img = curImg) {\n const filters = [\n [\"No-op\", o => o],\n [\"Left\", (orig, a, b, c) => mod256(orig - a)],\n [\"Up\", (orig, a, b, c) => mod256(orig - b)],\n [\"Average\", (orig, a, b, c) => mod256(orig - mod256(Math.floor((a + b) / 2)))],\n [\"Paeth\", (orig, a, b, c) => mod256(orig - paeth(a, b, c))]\n ];\n return html`

${await Promise.all(filters.map(async x=>html`

${x[0]}

${await filter(x[1], img)}

`))}

`;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":685,"value":"### Imports","pinned":false,"hidden":false,"mode":"md"},{"id":548,"value":"import {imageInput} from \"@mbostock/file-input\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":656,"value":"html = htl.html","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W32","stdlib":"1","titling":"auto"}