[javascript]Algorithms for JPEG processing

algorithms-for-jpeg.js

/* eslint no-unused-vars: 0, no-multi-spaces: 0 */
"use strict";

// [JPEG encode process]
// 1. RGB to YUV
// 2. Padding & chunk to 8x8-blocks
// 3. DCT
// 4. Quantization
// 5. zigzag scan
// 6. Huffman coding
//    a. (DC) diff array of first 0 byte of blocks
//    b. (AC) remain 1-63 bit of a block with run length only 0
// 7. pack bytes of JPEG container format


// Algorithms for JPEG processing (nothing optimized)

// array helpers
function range(n, map = v => v) {
    return Array.from(Array(n), (_, i) => map(i));
}
function split(arr, size, count) {
    return range(count, i => arr.slice(i * size, i * size + size));
}

// DCT(Discrete Cosine Transform) and IDCT(Inverse DCT) for JPEG
function dct2d(mat, w = 8, h = 8) {
    console.assert(mat.length === w * h);
    const cos = Math.cos, PI = Math.PI, isqrt2 = 1 / Math.sqrt(2);
    const px = PI / w, py = PI / h;
    return range(w * h, uvw => { // uvw = u + v * w
        const u = uvw % w, v = (uvw - u) / w;
        const c = (u === 0 ? isqrt2 : 1) * (v === 0 ? isqrt2 : 1);
        return mat.reduce((t, fxy, xyw) => { // xyw = x + y * w
            const x = xyw % w, y = (xyw - x) / w;
            return t + fxy * cos(px * (x + 0.5) * u) * cos(py * (y + 0.5) * v);
        }, 0) * c / 4;
    });
}
function idct2d(mat, w = 8, h = 8) {
    console.assert(mat.length === w * h);
    const cos = Math.cos, PI = Math.PI, isqrt2 = 1 / Math.sqrt(2);
    const px = PI / w, py = PI / h;
    return range(w * h, xyw => {
        const x = xyw % w, y = (xyw - x) / w;
        return mat.reduce((t, fuv, uvw) => {
            const u = uvw % w, v = (uvw - u) / w;
            const c = (u === 0 ? isqrt2 : 1) * (v === 0 ? isqrt2 : 1);
            return t +
                c * fuv * cos(px * (x + 0.5) * u) * cos(py * (y + 0.5) * v);
        }, 0) / 4;
    });
}


// pad 8nx8m size <=> shrink original size
function padding(mat, w, h, cw = 8, ch = 8) {
    console.assert(mat.length === w * h);
    const rw = Math.ceil(w / cw) * cw, rh = Math.ceil(h / ch) * ch;
    const extw = split(mat, w, h).map(l => {
        const last = l[l.length - 1];
        const ext = range(rw - w, _ => last);
        return l.concat(ext);
    });
    const lastl = extw[extw.length - 1];
    const extl = range(rh - h, _ => lastl.slice());
    return [].concat(...extw, ...extl);
}
function shrink(mat, w, h, cw = 8, ch = 8) {
    const rw = Math.ceil(w / cw) * cw, rh = Math.ceil(h / ch) * ch;
    console.assert(mat.length === rw * rh);
    return [].concat(
        ...split(mat, rw, rh).map(l => l.slice(0, w)).slice(0, h));
}

// block chunk list <=> full screen flat matrix
function chunks2d(mat, w, h, cw = 8, ch = 8) {
    console.assert(w % cw === 0 && h % ch === 0);
    const tw = w / cw, th = h / ch;
    return range(tw * th, ti => {
        const tx = ti % tw, ty = (ti / tw) | 0;
        const lx = tx * cw, ly = ty * ch;
        return [].concat(...range(ch, li => {
            const s = (ly + li) * w + lx;
            return mat.slice(s, s + cw);
        }));
    });
}
function concat2d(chunks, w, h, cw = 8, ch = 8) {
    console.assert(w % cw === 0 && h % ch === 0);
    const tw = w / cw, th = h / ch;
    return [].concat(...range(th, ti => {
        const tl = chunks.slice(ti * tw, ti * tw + tw);
        return [].concat(...range(ch, ci => {
            const ls = tl.map(chunk => chunk.slice(ci * cw, ci * cw + cw));
            return [].concat(...ls);
        }));
    }));
}

// 24bit RGB <=> YUV444
function yuvFactors(YR = 0.299, YB = 0.114, UB = 1 / 2, VR = 1 / 2) {
    // constraints: YR + YG + YB = 1, UR + UG + UB = 0, VR + VG + VB = 0
    //              BU * UB + YB = 1, RV * VR + YR = 1
    // [RGB<=>YUV Formula]
    // Y = YR * R + YG * G + YB * B
    // U = UR * R + UG * G + UB * B
    // V = VR * R + VG * G + VB * B
    // R = Y +  0 * U + RV * V
    // G = Y + GU * U + GV * V
    // B = Y + BU * U +  0 * V

    const RU = 0, BV = 0;
    const YG = 1 - YR - YB;   //=>  0.587
    const BU = (1 - YB) / UB; //=>  1.772
    const RV = (1 - YR) / VR; //=>  1.402
    const UR = -YR / BU;      //=> -0.168736
    const UG = -UB - UR;      //=> -0.331264
    const VB = -YB / RV;      //=> -0.081312
    const VG = -VR - VB;      //=> -0.418688
    const GU = -BU * YB / YG; //=> -0.344136
    const GV = -RV * YR / YG; //=> -0.714136
    return {
        YR, YG, YB, UR, UG, UB, VR, VG, VB,
        RU, RV, GU, GV, BU, BV
    };
}
//console.log(yuvFactors(0.299, 0.114, 0.5, 0.5)); // for JPEG
//console.log(yuvFactors(0.299, 0.114, 0.436, 0.615)); // for SDTV-BT601
//console.log(yuvFactors(0.2126, 0.0722, 0.436, 0.615)); // for HDTV-BT709
function clampUint8(n) {
    //return Math.min(Math.max(0, n), 255);
    return Math.min(Math.max(0, Math.round(n)), 255);
}
function rgb2yuv(rgb) {
    const {YR, YG, YB, UR, UG, UB, VR, VG, VB} = yuvFactors();
    return {
        y: rgb.r.map((r, i) => {
            const g = rgb.g[i], b = rgb.b[i];
            return clampUint8(YR * r + YG * g + YB * b);
        }),
        u: rgb.r.map((r, i) => {
            const g = rgb.g[i], b = rgb.b[i];
            return clampUint8(128 + UR * r + UG * g + UB * b);
        }),
        v: rgb.r.map((r, i) => {
            const g = rgb.g[i], b = rgb.b[i];
            return clampUint8(128 + VR * r + VG * g + VB * b);
        }),
        w: rgb.w, h: rgb.h, format: "RGB"
    };
}
function yuv2rgb(yuv) {
    const {RU, RV, GU, GV, BU, BV} = yuvFactors();
    return {
        r: yuv.y.map((y, i) => {
            const u = yuv.u[i] - 128, v = yuv.v[i] - 128;
            return clampUint8(y + RU * u + RV * v);
        }),
        g: yuv.y.map((y, i) => {
            const u = yuv.u[i] - 128, v = yuv.v[i] - 128;
            return clampUint8(y + GU * u + GV * v);
        }),
        b: yuv.y.map((y, i) => {
            const u = yuv.u[i] - 128, v = yuv.v[i] - 128;
            return clampUint8(y + BU * u + BV * v);
        }),
        w: yuv.w, h: yuv.h, format: "YUV444"
    };
}

// 0-255(stored color) <=> -128-127(for DCT)
function uint2int(mat) {
    return mat.map(v => v - 128);
}
function int2uint(mat) {
    return mat.map(v => v + 128);
}

// quantization <=> dequantization
const qmat = [
    16,  11,  10,  16,  24,  40,  51,  61,
    12,  12,  14,  19,  26,  58,  60,  55,
    14,  13,  16,  24,  40,  57,  69,  56,
    14,  17,  22,  29,  51,  87,  80,  62,
    18,  22,  37,  56,  68, 109, 103,  77,
    24,  35,  55,  64,  81, 104, 113,  92,
    49,  64,  78,  87, 103, 121, 120, 101,
    72,  92,  95,  98, 112, 100, 103,  99];
function quantize(color8x8) {
    return color8x8.map((c, i) => Math.round(c / qmat[i]));
}
function dequantize(quant8x8) {
    return quant8x8.map((q, i) => q * qmat[i]);
}

// chunk square array <=> zigzag scan array
function square2zigzag(square, w = 8) {
    console.assert(square.length === w * w);
    const zigzag = Array(square.length);
    const max = 2 * (w - 1);
    let i = 0;
    for (let sum = 0; sum <= max; sum++) {
        const start = sum < w ? 0 : sum - w + 1, end = sum < w ? sum : w - 1;
        if (sum % 2 === 0) {
            for (let x = start; x <= end; x++) {
                const y = sum - x;
                zigzag[i++] = square[y * w + x];
            }
        } else {
            for (let x = end; x >= start; x--) {
                const y = sum - x;
                zigzag[i++] = square[y * w + x];
            }
        }
    }
    return zigzag;
}
function zigzag2square(zigzag, w = 8) {
    console.assert(zigzag.length === w * w);
    const square = Array(zigzag.length);
    const max = 2 * (w - 1);
    let i = 0;
    for (let sum = 0; sum <= max; sum++) {
        const start = sum < w ? 0 : sum - w + 1, end = sum < w ? sum : w - 1;
        if (sum % 2 === 0) {
            for (let x = start; x <= end; x++) {
                const y = sum - x;
                square[y * w + x] = zigzag[i++];
            }
        } else {
            for (let x = end; x >= start; x--) {
                const y = sum - x;
                square[y * w + x] = zigzag[i++];
            }
        }
    }
    return square;
}


// huffman coding
// encode
function distribution(nums) {
    const dist = new Map();
    nums.forEach(n => dist.set(n, (dist.get(n) || 0) + 1));
    return Array.from(dist, kv => ({value: kv[0], count: kv[1]}));
}
function huffmanTree(nums) {
    const queue = distribution(nums).sort((a, b) => a.count - b.count);
    while (queue.length > 1) {
        const left = queue.shift();
        const right = queue.shift();
        const count = left.count + right.count;
        const index = queue.findIndex(n => n.count > count);
        queue.splice(index < 0 ? queue.length : index, 0,
                     {left, right, count});
    }
    return queue[0];
}
function huffmanTable(nums) {
    const tree = huffmanTree(nums);
    const table = new Map();
    (function walk(node, bits) {
        if (Reflect.has(node, "value")) {
            table.set(node.value, bits);
        } else {
            walk(node.left, bits.concat([0]));
            walk(node.right, bits.concat([1]));
        }
    })(tree, []);
    return table;
}
function huffmanEncode(nums) {
    const table = huffmanTable(nums);
    // pack from upper bits
    const bytes = [];
    let byte = 0, top = 7;
    nums.forEach(n => {
        table.get(n).forEach(b => {
            if (b) byte |= 1 << top; // put 1 to cursor
            top--;
            if (top < 0) {
                bytes.push(byte);
                byte = 0;
                top = 7;
            }
        });
    });
    if (top !== 7) bytes.push(byte);
    return {bytes, table, length: nums.length};
}
// decode (very slow)
function table2tree(table) {
    const ts = Array.from(table, kv => ({value: kv[0], bits: kv[1]}));
    return (function make(ts, top) {
        if (ts.length === 1) return ts[0];
        return [
            make(ts.filter(t => t.bits[top] === 0), top + 1),
            make(ts.filter(t => t.bits[top] === 1), top + 1),
        ];
    })(ts, 0);
}
function huffmanDecode({bytes, table, length}) {
    const tree = table2tree(table);
    //console.dir(tree, {depth: 6});
    const nums = [];
    let cur = tree, bindex = 0, byte = bytes[0], top = 7;
    while (nums.length < length) {
        // read 1 bit
        const b = (byte & (1 << top)) >>> top;
        top--;
        if (top < 0) {
            byte = bytes[++bindex];
            top = 7;
        }
        // walk huffman tree
        cur = cur[b];
        if (Reflect.has(cur, "value")) {
            nums.push(cur.value);
            cur = tree;
        }
    }
    return nums;
}


// packing as run length of former 0
function nums2zerorun(nums) {
    let zeros = 0;
    const r = [];
    nums.forEach(value => {
        if (value === 0) {
            zeros++;
        } else {
            r.push({zeros, value});
            zeros = 0;
        }
    });
    return r;
}
function zerorun2nums(zerolength, length = 63) {
    const decoded = [].concat(...zerolength.map(
        ({zeros, value}) => Array(zeros).fill(0).concat([value])));
    return decoded.concat(Array(length - decoded.length).fill(0));
}

dct-elements.html

<!doctype html>
<html>
  <head>
    <meta charset="utf-8" />
    <script src="algorithms-for-jpeg.js"></script>
    <script src="dct-elements.js" defer="defer"></script>
  </head>
  <body>
    <h1>DCT Series and the Images</h1>
    <p>Inverse DCT the 8x8 matrix as:</p>
    <p>only <code>(x, y) = 255 * 64</code>,
      other 63 elements are <code>0</code></p>
  </body>
</html>

dct-elements.js

/* globals idct2d, clampUint8 */
"use strict";

function dctElement(x, y) {
    const dct = Array(64).fill(0);
    dct[y * 8 + x] = 255 * 64;
    const colors = idct2d(dct).map(v => clampUint8((v + 128) | 0));
    const imagedata = new ImageData(8, 8);
    colors.forEach((c, i) => {
        imagedata.data[i * 4 + 0] = c;
        imagedata.data[i * 4 + 1] = c;
        imagedata.data[i * 4 + 2] = c;
        imagedata.data[i * 4 + 3] = 255;
    });
    return imagedata;
}

function canvasImage(imagedata, scale) {
    const scaled = new ImageData(
        imagedata.width * scale, imagedata.height * scale);
    for (let y = 0; y < scaled.height; y++) {
        for (let x = 0; x < scaled.width; x++) {
            const sx = (x / scale) | 0, sy = (y / scale) | 0;
            const di = x + y * scaled.width, si = sx + sy * imagedata.width;
            for (let ofs = 0; ofs < 4; ofs++) {
                scaled.data[di * 4 + ofs] = imagedata.data[si * 4 + ofs];
            }
        }
    }
    const canvas = document.createElement("canvas");
    canvas.width = imagedata.width * scale;
    canvas.height = imagedata.height * scale;
    canvas.getContext("2d").putImageData(scaled, 0, 0);
    canvas.style.borderStyle = "ridge";
    canvas.style.borderColor = "red";
    return canvas;
}

function main() {
    const table = document.createElement("table");
    for (let y = 0; y < 8; y++) {
        const row = table.insertRow(y);
        for (let x = 0; x < 8; x++) {
            const cell = row.insertCell(x);
            const imagedata = dctElement(x, y);
            const h = document.createElement("div");
            h.innerHTML = `(${x},${y})`;
            cell.appendChild(h);
            cell.appendChild(canvasImage(imagedata, 4));
        }
    }
    table.border = "border";
    document.body.appendChild(table);
}
main();

image-demo.html

<!doctype html>
<html>
  <head>
    <meta charset="utf-8" />
    <script src="algorithms-for-jpeg.js"></script>
    <script src="image-demo.js" defer="defer"></script>
  </head>
  <body>
    <div>Select an Image File: <input id="image" type="file" /></div>
  </body>
</html>

image-demo.js

/* globals rgb2yuv, yuv2rgb, range, padding, shrink, chunks2d, concat2d,
           dct2d, idct2d, uint2int, int2uint, quantize, dequantize
 */
"use strict";

function flow(gfunc) {
    return new Promise((f, r) => {
        const g = gfunc(), n = r => g.next(r), t = r => g.throw(r);
        const step = item => item.done ? f(item.value) :
                  Promise.resolve(item.value).then(n, t).then(step, r);
        step(n());
    });
}
function wait(o) {
    return new Promise(f => {
        setTimeout(_ => f(o), 0);
    });
}

function drawImageSteps(file) {
    const img = new Image();
    img.src = file;
    img.addEventListener("load", ev => {
        //console.log(img.width, img.height);
        //document.body.appendChild(img);
        flow(function* () {
            const raw = document.createElement("canvas");
            raw.width = img.width; raw.height = img.height;
            const raw2d = raw.getContext("2d");
            raw2d.drawImage(img, 0, 0);
            append(raw, "Raw Image");
            yield wait();
            const rawdata = raw2d.getImageData(0, 0, raw.width, raw.height);
            //addCanvas(diff(rawdata, rawdata), "DIFF RAW: RAW");
            const rgbdata = imagedata2rgb(rawdata);
            const yuvdata = rgb2yuv(rgbdata);
            let imageyuv = null;
            {
                const rgbFromYuv = yuv2rgb(yuvdata);
                const imagedata = rgb2imagedata(rgbFromYuv);
                addCanvas(imagedata, "YUV Converted");
                addCanvas(diff(imagedata, rawdata), "DIFF RAW: YUV Converted");
                imageyuv = imagedata;
                yield wait();
            }
            const blocks = chunk(yuvdata);
            //{
            //    const merged = concat(blocks);
            //    const rgbFromYuv = yuv2rgb(merged);
            //    const imagedata = rgb2imagedata(rgbFromYuv);
            //    addCanvas(imagedata, "Block");
            //    yield wait();
            //}
            let imagedct = null;
            const dcts = applyDCT(blocks);
            {
                const idcts = applyIDCT(dcts);
                const merged = concat(idcts);
                const rgbFromYuv = yuv2rgb(merged);
                const imagedata = rgb2imagedata(rgbFromYuv);
                addCanvas(imagedata, "DCT Converted");
                addCanvas(diff(imagedata, rawdata), "DIFF RAW: DCT Converted");
                addCanvas(diff(imagedata, imageyuv), "DIFF YUV: DCT Converted");
                imagedct = imagedata;
                yield wait();
            }
            const quants = applyQuantize(dcts);
            {
                const dequants = applyDequantize(quants);
                const idcts = applyIDCT(dequants);
                const merged = concat(idcts);
                const rgbFromYuv = yuv2rgb(merged);
                const imagedata = rgb2imagedata(rgbFromYuv);
                addCanvas(imagedata, "Quantized");
                addCanvas(diff(imagedata, rawdata), "DIFF RAW: Quantized");
                addCanvas(diff(imagedata, imageyuv), "DIFF YUV: Quantized");
                addCanvas(diff(imagedata, imagedct), "DIFF DCT: Quantized");
            }
        });
    });
}

function addCanvas(imagedata, title) {
    const canvas = document.createElement("canvas");
    canvas.width = imagedata.width;
    canvas.height = imagedata.height;
    const c2d = canvas.getContext("2d");
    c2d.putImageData(imagedata, 0, 0);
    append(canvas, title);
}

function append(elem, title) {
    const h3 = document.createElement("h3");
    h3.textContent = title;
    const div = document.createElement("div");
    div.appendChild(h3);
    div.appendChild(elem);
    document.body.appendChild(div);
}
function diff(a, b) {
    const r = new ImageData(a.width, a.height);
    const size = r.width * r.height;
    //const d = (a, b) => a - b + 128;
    const d = (a, b) => (a - b) * 16 + 128;
    for (let i = 0; i < size; i++) {
        r.data[i * 4 + 0] = d(a.data[i * 4 + 0], b.data[i * 4 + 0]);
        r.data[i * 4 + 1] = d(a.data[i * 4 + 1], b.data[i * 4 + 1]);
        r.data[i * 4 + 2] = d(a.data[i * 4 + 2], b.data[i * 4 + 2]);
        r.data[i * 4 + 3] = 255;
    }
    return r;
}

function imagedata2rgb(imagedata) {
    const size = imagedata.width * imagedata.height;
    return {
        r: range(size, i => imagedata.data[i * 4 + 0]),
        g: range(size, i => imagedata.data[i * 4 + 1]),
        b: range(size, i => imagedata.data[i * 4 + 2]),
        w: imagedata.width, h: imagedata.height, format: "RGB"
    };
}
function rgb2imagedata(rgb) {
    const size = rgb.w * rgb.h;
    const imagedata = new ImageData(rgb.w, rgb.h);
    for (let i = 0; i < size; i++) {
        imagedata.data[i * 4 + 0] = rgb.r[i];
        imagedata.data[i * 4 + 1] = rgb.g[i];
        imagedata.data[i * 4 + 2] = rgb.b[i];
        imagedata.data[i * 4 + 3] = 255;
    }
    return imagedata;
}

// YUV blocks
function chunk(yuvdata) {
    const w = Math.ceil(yuvdata.w / 8) * 8;
    const h = Math.ceil(yuvdata.h / 8) * 8;
    const ow = yuvdata.w, oh = yuvdata.h;
    return {
        y: chunks2d(padding(yuvdata.y, ow, oh), w, h),
        u: chunks2d(padding(yuvdata.u, ow, oh), w, h),
        v: chunks2d(padding(yuvdata.v, ow, oh), w, h),
        w, h, ow, oh, format: yuvdata.format
    };
}
function concat(chunked) {
    const {w, h, ow, oh} = chunked;
    return {
        y: shrink(concat2d(chunked.y, w, h), ow, oh),
        u: shrink(concat2d(chunked.u, w, h), ow, oh),
        v: shrink(concat2d(chunked.v, w, h), ow, oh),
        w: ow, h: oh, format: chunked.format
    };
}

function applyDCT(blocks) {
    const {w, h, ow, oh, format} = blocks;
    return {
        y: blocks.y.map(block => dct2d(uint2int(block), 8, 8)),
        u: blocks.u.map(block => dct2d(uint2int(block), 8, 8)),
        v: blocks.v.map(block => dct2d(uint2int(block), 8, 8)),
        w, h, ow, oh, format
    };
}
function applyIDCT(blocks) {
    const {w, h, ow, oh, format} = blocks;
    return {
        y: blocks.y.map(block => int2uint(idct2d(block, 8, 8))),
        u: blocks.u.map(block => int2uint(idct2d(block, 8, 8))),
        v: blocks.v.map(block => int2uint(idct2d(block, 8, 8))),
        w, h, ow, oh, format
    };
}

function applyQuantize(blocks) {
    const {w, h, ow, oh, format} = blocks;
    return {
        y: blocks.y.map(block => quantize(block)),
        u: blocks.u.map(block => quantize(block)),
        v: blocks.v.map(block => quantize(block)),
        w, h, ow, oh, format
    };
}
function applyDequantize(blocks) {
    const {w, h, ow, oh, format} = blocks;
    return {
        y: blocks.y.map(block => dequantize(block)),
        u: blocks.u.map(block => dequantize(block)),
        v: blocks.v.map(block => dequantize(block)),
        w, h, ow, oh, format
    };
}

// CC0 Image from
// https://www.pexels.com/photo/close-up-photo-of-orange-petaled-flower-121942/
//drawImageSteps("photo.png");

function main() {
    const input = document.getElementById("image");
    input.type = "file";
    input.accept = "image/*";
    input.addEventListener("change", ev => {
        if (input.files.length === 0) return;
        const reader = new FileReader();
        reader.addEventListener("load", ev => {
            setTimeout(_ => {
                drawImageSteps(ev.target.result);
            }, 0);
        }, false);
        reader.readAsDataURL(input.files[0]);
    }, false);
}
main();

photo.png

Demo does not work on githack/rawgit because they redirect URL of png files(not served from their sites).
c2d.getImageData do not allow with external resource used by c2d.drawImage. (Change to use file input for loading image)

---

• JPEG Algorithm Demo: https://gist.githack.com/bellbind/eb3419516e00fdfa13f472d82fd1b495/raw/image-demo.html
• Image table for each DCT series: https://gist.githack.com/bellbind/eb3419516e00fdfa13f472d82fd1b495/raw/dct-elements.html