30:T655,dct_passes_test = { // Using http://www.whydomath.org/node/wavlets/basicjpg.html as reference const start_matrix = `5 176 193 168 168 170 167 165 6 176 158 172 162 177 168 151 5 167 172 232 158 61 145 214 33 179 169 174 5 5 135 178 8 104 180 178 172 197 188 169 63 5 102 101 160 142 133 139 51 47 63 5 180 191 165 5 49 53 43 5 184 170 168 74` .split("\n") .map(r => r.split("\t").map(c => parseInt(c, 10))); const zero_centered = start_matrix.map(r => r.map(c => c - 127 /* note that this isn't 128 b/c of reference site */) ); const dct_out = naive_2d_dct(zero_centered); const ref_dct = `-27.500 -213.468 -149.608 -95.281 -103.750 -46.946 -58.717 27.226 168.229 51.611 -21.544 -239.520 -8.238 -24.495 -52.657 -96.621 -27.198 -31.236 -32.278 173.389 -51.141 -56.942 4.002 49.143 30.184 -43.070 -50.473 67.134 -14.115 11.139 71.010 18.039 19.500 8.460 33.589 -53.113 -36.750 2.918 -5.795 -18.387 -70.593 66.878 47.441 -32.614 -8.195 18.132 -22.994 6.631 12.078 -19.127 6.252 -55.157 85.586 -0.603 8.028 11.212 71.152 -38.373 -75.924 29.294 -16.451 -23.436 -4.213 15.624` .split("\n") .map(r => r.split("\t").map(c => Number(c))); const matches_ref = dct_out .map((r, ri) => r.map((c, ci) => Math.abs(ref_dct[ri][ci] - c) < 0.001)) .reduce((vec, r) => vec.concat(r), []) .every(c => c); const dct_inv_out = naive_2d_dct_inverse(dct_out); const matches_start = dct_inv_out .map((r, ri) => r.map((c, ci) => Math.abs(start_matrix[ri][ci] - (c + 127)) < 0.001) ) .reduce((vec, r) => vec.concat(r)) .every(c => c); return matches_ref && matches_start; }31:[] 2e:{"title":"JPEG","cells":[{"id":0,"value":"md`# JPEG\n\nImplemented following http://www.whydomath.org/node/wavlets/basicjpg.html.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":16,"value":"md`## Compression`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"viewof input = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":150,"value":"viewof quant_input = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":19,"value":"viewof row_separator = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":24,"value":"viewof col_separator = html``","pinned":false,"hidden":false,"mode":"ojs"},{"id":18,"value":"input_matrix = parse_matrix_str(input)","pinned":false,"hidden":false,"mode":"ojs"},{"id":156,"value":"input_quant_matrix = parse_matrix_str(quant_input)","pinned":false,"hidden":false,"mode":"ojs"},{"id":31,"value":"trans_matrix = math.add(input_matrix, min_range)","pinned":false,"hidden":false,"mode":"ojs"},{"id":211,"value":"md`\n### Translated Matrix:\n\n\\`\\`\\`\n${matrix_to_str(trans_matrix, {\n longest_cell: \"-128\"\n})}\n\\`\\`\\`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":54,"value":"dct_matrix = math.matrix(naive_2d_dct(trans_matrix._data))","pinned":false,"hidden":false,"mode":"ojs"},{"id":190,"value":"md`\n### DCT Matrix:\n\n\\`\\`\\`\n${matrix_to_str(dct_matrix, {\n cell_2_str: c => c.toFixed(2),\n longest_cell: \"-128.00\"\n})}\n\\`\\`\\`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":149,"value":"quant_matrix = math.dotDivide(dct_matrix, input_quant_matrix).map(Math.round)","pinned":false,"hidden":false,"mode":"ojs"},{"id":169,"value":"md`\n### Quantized Matrix:\n\n\\`\\`\\`\n${matrix_to_str(quant_matrix)}\n\\`\\`\\`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":216,"value":"md`### Huffman Codes\n\n_At this point the matrix would be zig-zagged and Huffman coded._\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":218,"value":"md`## Decoding`","pinned":false,"hidden":false,"mode":"ojs"},{"id":223,"value":"unquant_matrix = math.dotMultiply(quant_matrix, input_quant_matrix)","pinned":true,"hidden":false,"mode":"ojs"},{"id":221,"value":"md`### Unquantized Matrix\n\n\\`\\`\\`\n${matrix_to_str(unquant_matrix)}\n\\`\\`\\`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":230,"value":"inv_dct_matrix = math.matrix(naive_2d_dct_inverse(unquant_matrix._data))","pinned":false,"hidden":false,"mode":"ojs"},{"id":235,"value":"md`### Inverted DCT-ed Matrix\n\n\\`\\`\\`\n${matrix_to_str(inv_dct_matrix, {\n cell_2_str: c => c.toFixed(2),\n longest_cell: \"-128.00\"\n})}\n\\`\\`\\`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":238,"value":"untrans_matrix = math\n .add(inv_dct_matrix.map(Math.round), -min_range)\n .map(c => (c > 0 ? c : 0))","pinned":false,"hidden":false,"mode":"ojs"},{"id":242,"value":"md`### Recovered Matrix\n\n\\`\\`\\`\n${matrix_to_str(untrans_matrix)}\n\\`\\`\\`\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":9,"value":"md`## Appendix`","pinned":false,"hidden":false,"mode":"ojs"},{"id":248,"value":"min_range = -128","pinned":false,"hidden":false,"mode":"ojs"},{"id":72,"value":"isqrt2 = 1 / Math.sqrt(2)","pinned":false,"hidden":false,"mode":"ojs"},{"id":32,"value":"naive_2d_dct = matrix => {\n const n = matrix.length,\n m = matrix[0].length;\n const px = Math.PI / m,\n py = Math.PI / n;\n const out = [];\n for (let ry = 0; ry < n; ry++) {\n const r = [];\n for (let rx = 0; rx < m; rx++) {\n const c = Math.pow(isqrt2, (rx === 0) + (ry === 0));\n let t = 0;\n for (let y = 0; y < n; y++) {\n for (let x = 0; x < m; x++) {\n var v = matrix[y][x];\n t +=\n v * Math.cos(px * (x + 0.5) * rx) * Math.cos(py * (y + 0.5) * ry);\n }\n }\n r.push((c * t) / 4);\n }\n out.push(r);\n }\n return out;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":36,"value":"naive_2d_dct_inverse = matrix => {\n const n = matrix.length,\n m = matrix[0].length;\n const px = Math.PI / m,\n py = Math.PI / n;\n const out = [];\n for (let ry = 0; ry < n; ry++) {\n const r = [];\n for (let rx = 0; rx < m; rx++) {\n let t = 0;\n for (let y = 0; y < n; y++) {\n for (let x = 0; x < m; x++) {\n const c = Math.pow(isqrt2, (x === 0) + (y === 0));\n const v = matrix[y][x];\n t +=\n c *\n v *\n Math.cos(px * (rx + 0.5) * x) *\n Math.cos(py * (ry + 0.5) * y);\n }\n }\n r.push(t / 4);\n }\n out.push(r);\n }\n return out;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":93,"value":"rmo_to_2d = vector =>\n vector.reduce(\n (rows, c) => (\n rows[rows.length - 1].length == 8\n ? rows.push([c])\n : rows[rows.length - 1].push(c),\n rows\n ),\n [[]]\n )","pinned":false,"hidden":false,"mode":"ojs"},{"id":97,"value":"rmo_from_2d = matrix => matrix.reduce((vec, r) => vec.concat(r))","pinned":false,"hidden":false,"mode":"ojs"},{"id":83,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":159,"value":"parse_matrix_str = input => {\n const matrix = input\n .split(new RegExp(row_separator))\n .map(r => r.split(new RegExp(col_separator)).map(c => parseInt(c, 10)));\n if (matrix.length !== 8 || matrix[0].length !== 8)\n throw new Error(\"The matrix must be 8x8\");\n if (matrix.some(r => r.length !== matrix[0].length))\n throw new Error(\"The matrix must be 8x8\");\n return math.matrix(matrix);\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":185,"value":"matrix_to_str = (matrix, { cell_2_str = String, longest_cell = \"-127\" } = {}) =>\n matrix\n .map(c => padNum(cell_2_str(c), longest_cell, \" \"))\n ._data.map(r => r.join(\" \"))\n .join(\"\\n\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":171,"value":"padNum = (num, max, pad = \"0\") =>\n (pad.repeat(String(max).length) + num).slice(-String(max).length)","pinned":false,"hidden":false,"mode":"ojs"},{"id":47,"value":"math = require(\"mathjs@5.2.2/dist/math.js\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":11,"value":"default_input = `5 176 193 168 168 170 167 165\n6 176 158 172 162 177 168 151\n5 167 172 232 158 61 145 214\n33 179 169 174 5 5 135 178\n8 104 180 178 172 197 188 169\n63 5 102 101 160 142 133 139\n51 47 63 5 180 191 165 5\n49 53 43 5 184 170 168 74`","pinned":false,"hidden":false,"mode":"ojs"},{"id":154,"value":"default_quant_input = `16 11 10 16 24 40 51 61\n12 12 14 19 26 58 60 55\n14 13 16 24 40 57 69 56\n14 17 22 29 51 87 80 62\n18 22 37 56 68 109 103 77\n24 35 55 64 81 104 113 92\n49 64 78 87 103 121 120 101\n72 92 95 98 112 100 103 99`","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}