31:Ta72,md`--- ## Image: Ali Wong Using [this b&w image](https://commons.wikimedia.org/wiki/File:Ali_Wong_2012.jpg) of comedian and actress Ali Wong, calculate the cross-correlation of the full image and a crop of the image. Draw a boundary box within the full image of the calculated location of the second image. ### Load pixel info After loading the image into a canvas element, you can extract the individual r/g/b/a channel information for each pixel (this is only possible if the image is [loaded from a source that allows cross-origin resource sharing](https://developer.mozilla.org/en-US/docs/Web/HTML/CORS_enabled_image) ([CORS](https://developer.mozilla.org/en-US/docs/Web/HTTP/CORS)); WikiCommons and GitHub Gists are both configured to allow this). Because this is a b&w image, the information in the red, green, and blue channels are equivalent – extracting just the red channel info gives an accurate representation of the brightness of each pixel. ### Normalize pixels Because the value of each pixel is taken from a single 8-bit channel, values range from 0 (black in the below image) to 255 (white). Thus, broadly speaking, the cross-correlation calculation would find the location with the most amount of white overlap between img1 and img2 – the smaller img2 is, the more likely the algorithm is to return an inaccurate location. To help counteract this, I normalize the pixel values by subracting the average pixel value across both images; this way, the cross-correlation returns larger values for both white- and black-overlapping areas. Although not perfect, normalizing the values improves the algorithm's ability to locate the second image within the first. ### Downsample The source image of Ali Wong is 720x720 pixels. Cross-correlation requires calculating the sum of element-by-element multiplication for every possible overlap of the two images; using the full size image, this sum would need to be calculated approximately 2 million times. Since this would likely cause any browser to become unresponsive, I first downsample the image to be around 40x40 pixels. To do so, I divide up the images into equal-sized blocks, where the maximum number of blocks on any side is equal to the number of desired pixels in the downsampled image. Each block is then averaged; this effectively passes the input signal through a low pass filter before downsampling. This is a naive implementation, but there are innumerable other downsampling methods (the code for "nearest neighbor" is included in the \`downsampleMatrix()\` function below). A higher-resolution image (less downsampling) yields a more precise result, but will take longer to compute. `32:T6f6,async function xcorr_jpg(url1, url2, options = {}) { let {imgCrop1, imgCrop2, maxAllowedDim = 30, normalize = true, dataChannelMixer } = options // imgCrop_ = {cropX, cropY, cropWidth, cropHeight} -> crop image by given percent values, // constrained by orig img dimensions // maxAllowedDim -> reduce the # of samples in original images until there are no more than this # of pixels // get pixel values const img1 = await getJpgData(url1, imgCrop1, {dataChannelMixer}) const img2 = await getJpgData(url2, imgCrop2, {dataChannelMixer}) // normalize data const allData = img1.data.concat(img2.data) let min = d3.min(allData) let max = d3.max(allData) if (normalize) { const avg = d3.mean(allData) img1.data = img1.data.map(d => d-avg) img2.data = img2.data.map(d => d-avg) min -= avg max -= avg } // convert 1D array of image data into a 2D array of arrays (representing rows/columns) const mat1_full = arrayToMatrix(img1.data, img1.width, img1.height) const mat2_full = arrayToMatrix(img2.data, img2.width, img2.height) // downsample to speed up processing const largestDim = d3.max([img1.width, img1.height, img2.width, img2.height]) const downsampleFactor = Math.ceil(largestDim/maxAllowedDim) let mat1, mat2 if (downsampleFactor > 1) { mat1 = downsampleMatrix(mat1_full, downsampleFactor) mat2 = downsampleMatrix(mat2_full, downsampleFactor) } else { mat1 = mat1_full mat2 = mat2_full } // calculate xcorr values const c = xcorr(mat1, mat2) return {...c, downsampleFactor, min, max, img1: {url: url1, downsampledMatrix: mat1, ...img1}, img2: {url: url2, downsampledMatrix: mat2, ...img2} } }33:T554,async function getJpgData(url, cropOptions = {}, options = {}) { const {cropX = 0, // percentile start point cropY = 0, // percentile start point cropWidth = 1, // percent of total image width cropHeight = 1 // percent of total image height } = cropOptions const {dataChannelMixer = mixerList["red"] // x = [r, g, b, a], default: return just r } = options const img = await loadImg(url) const imgWidth = img.naturalWidth const imgHeight = img.naturalHeight // see: https://developer.mozilla.org/en-US/docs/Web/API/CanvasRenderingContext2D/drawImage const sx = Math.round(cropX * imgWidth) const sy = Math.round(cropY * imgHeight) const sWidth = Math.round(Math.min(cropWidth, 1 - cropX) * imgWidth) // don't let bounds exceed orig image const sHeight = Math.round(Math.min(cropHeight, 1 - cropY) * imgHeight) let ctx = DOM.context2d(sWidth,sHeight, 1) ctx.drawImage(img, sx, sy, sWidth, sHeight, 0, 0, sWidth, sHeight) // get image data, extract alpha channel info const {data: imgData} = ctx.getImageData(0, 0, sWidth, sHeight) const data = new Array(sWidth * sHeight) let dataSlice for (let i = 0; i < imgData.length/4; i++) { data[i] = dataChannelMixer(imgData,i) } return {data, sx, sy, width:sWidth, height:sHeight, origWidth:imgWidth, origHeight:imgHeight} }34:T46a,function downsampleMatrix(mat, skipAmt = 100, method = "average") { // downsample method: // - "average": low-pass filter input then sample // - "nearest neighbor": extract every 'skipAmt' sample from the input const newWidth = Math.floor(mat[0].length / skipAmt) const newHeight = Math.floor(mat.length / skipAmt) let oldCol, oldColEnd, oldRowEnd let oldRow = 0 let row, block let newMat = Array(newHeight) for (let rowNum = 0; rowNum < newHeight; rowNum++) { oldRowEnd = oldRow + skipAmt row = mat.slice(oldRow, oldRowEnd) newMat[rowNum] = Array(newWidth) oldCol = 0 for (let colNum = 0; colNum < newWidth; colNum++) { oldColEnd = oldCol + skipAmt if (method == "average") { block = row.map(x => x.slice(oldCol, oldColEnd)) newMat[rowNum][colNum] = Math.floor(d3.mean(block.flat())) } else if (method === "nearest neighbor") { newMat[rowNum][colNum] = mat[oldRow][oldCol] } else { // undefined newMat[rowNum][colNum] = 0 } oldCol = oldColEnd } oldRow = oldRowEnd } return newMat }35:T1249,async function drawJpgOverlap(url1, url2, options = {}) { let {imgCrop1, imgCrop2, maxAllowedDim = 50, boxColor = "orange", normalize = true, dataChannelMixer = mixerList["red"] } = options const defaultCrop = {cropX: 0, cropY: 0, cropWidth: 1, cropHeight: 1} if (imgCrop1 === undefined) imgCrop1 = defaultCrop if (imgCrop2 === undefined) imgCrop2 = defaultCrop const c = await xcorr_jpg(url1, url2, {imgCrop1, imgCrop2, maxAllowedDim, normalize, dataChannelMixer}) const max_c = matrixMax(c.xcorr) const max = max_c.location.map(d => ({x: (d.col + c.colOffset) * c.downsampleFactor, y: (d.row + c.rowOffset) * c.downsampleFactor})) // define final image dimensions/spacings const spacing = 10 const margin = spacing const labelHeight = 14 const marginTop = margin * 2 + labelHeight const marginBottom = margin * 2 + labelHeight*2 const maxHeight = 450 const inputImgWidths = c.img1.origWidth + c.img2.origWidth const scale = d3.min([(width - 2 * margin - spacing) / inputImgWidths, (maxHeight - margin - marginTop) / c.img1.origHeight, (maxHeight - margin - marginTop) / c.img2.origHeight]) const ctxWidth = inputImgWidths * scale + margin * 2 + spacing const height = Math.max(c.img1.origHeight, c.img2.origHeight) * scale + marginTop + marginBottom // draw original images const ctxImg = DOM.context2d(ctxWidth, height - labelHeight) ctxImg.fillRect(0,0,ctxWidth, height) const img1 = await loadImg(url1) const img2 = await loadImg(url2) ctxImg.drawImage(img1, c.img1.sx, c.img1.sy, c.img1.width, c.img1.height, margin, marginTop, c.img1.width * scale, c.img1.height * scale) ctxImg.drawImage(img2, c.img2.sx, c.img2.sy, c.img2.width, c.img2.height, c.img1.width * scale + margin + spacing, marginTop, c.img2.width * scale, c.img2.height * scale) // draw heatmap with calculated/downsampled images, save color function const ctxHeat = DOM.context2d(ctxWidth, height) const colorInterpolator = d3.interpolateMagma ctxHeat.fillStyle = "grey" ctxHeat.fillRect(0,0,ctxWidth, height) drawMatrix(c.img1.downsampledMatrix, {ctx: ctxHeat, blockSize: c.downsampleFactor * scale, min: c.min, max: c.max, x: margin, y: marginTop, colorInterpolator}) const heatColorFunc = drawMatrix(c.img2.downsampledMatrix, {ctx: ctxHeat, blockSize: c.downsampleFactor * scale, min: c.min, max: c.max, x: margin + c.img1.width * scale + spacing, y: marginTop, colorInterpolator}) // draw borders of orig image extents on heat map const heatDim = img => [c[img].downsampledMatrix[0].length * c.downsampleFactor * scale, c[img].downsampledMatrix.length * c.downsampleFactor * scale] ctxHeat.strokeStyle = "black" // downsampled image dimensions ctxHeat.strokeRect(margin, marginTop, ...heatDim("img1")) ctxHeat.strokeRect(margin + c.img1.width * scale + spacing, marginTop, ...heatDim("img2")) ctxHeat.strokeStyle = "white" // original image dimensions ctxHeat.strokeRect(margin, marginTop, c.img1.width * scale, c.img1.height * scale) ctxHeat.strokeRect(margin + c.img1.width * scale + spacing, marginTop, c.img2.width * scale, c.img2.height * scale) // heatmap key drawKey(ctxHeat, heatColorFunc, margin, height - margin - labelHeight * .8, Math.min(ctxWidth - margin*2, 400), labelHeight * .8) // label left/right images const label = (ctx, title) => { ctx.fillStyle = "white" ctx.textBaseline = "hanging" ctx.font = `${labelHeight}px sans-serif` ctx.fillText("Img 1", margin, margin) ctx.fillText("Img 2", margin + c.img1.width * scale + spacing, margin) ctx.fillText(title, margin, height - marginBottom + margin) } label(ctxImg, "ORIGINAL IMAGES") label(ctxHeat, "HEAT MAP OF DOWNSAMPLED VALUES") // draw calculated location of img2 on img1 (on both image versions) ctxImg.strokeStyle = boxColor ctxHeat.strokeStyle = "lightblue" ctxImg.lineWidth = 2 ctxHeat.lineWidth = 2 let loc max.forEach(position => { loc = [margin + position.x * scale, marginTop + position.y * scale] ctxImg.strokeRect(...loc, c.img2.width * scale, c.img2.height * scale) ctxHeat.strokeRect(...loc, ...heatDim("img2")) }) return {img: ctxImg.canvas, heat: ctxHeat.canvas} }36:T47a,function drawMatrix(mat, options = {}) { // draw a grid of colors representing the values in an array of arrays, // scaled by the min/max values in the matrix let {ctx, min = d3.min(mat.flat()), max = d3.max(mat.flat()), blockSize = Math.min(width/mat[0].length, 5), x = 0, // dimensions of top left corner location y = 0, colorInterpolator = d3.interpolateWarm, debug = false} = options const matWidth = mat[0].length const matHeight = mat.length if (ctx === undefined) ctx = DOM.context2d(blockSize * matWidth + x, blockSize * matHeight + y) const color = d3.scaleSequential() .domain([min, max]) .interpolator(colorInterpolator) // draw pixels for (let row = 0; row < matHeight; row++){ for (let col = 0; col < matWidth; col++){ ctx.fillStyle = color(mat[row][col]) ctx.fillRect(col * blockSize + x, row * blockSize + y, blockSize, blockSize) } } // border for debug purposes if (debug) { ctx.strokeStyle = "orange" ctx.lineWidth = 2 ctx.strokeRect(0,0,matWidth * blockSize, matHeight * blockSize) } return color }37:[] 2f:{"title":"Cross-correlation of 2 images","cells":[{"id":0,"value":"md`# Cross-correlation of 2 images\n\nThis notebook builds on my previous notebook: [Cross-correlation of 2 matrices](/@lemonnish/cross-correlation-of-2-matrices)\n\nThe general process:\n- Load two images and extract their pixel-by-pixel information\n- Normalize and downsample the pixel information\n- Calculate cross-correlation using the processed pixel information\n- Generate visual summaries of cross-correlation, highlighting areas of maximum image overlap\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":39,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":40,"value":"urlAliWong=\"https://upload.wikimedia.org/wikipedia/commons/3/3b/Ali_Wong_2012.jpg\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":79,"value":"xcorrAliWong = drawJpgOverlap(urlAliWong, urlAliWong, {imgCrop2: cropInputAliWong, maxAllowedDim: maxAllowedDimAliWong, normalize: !!normalizeAliWong})","pinned":false,"hidden":false,"mode":"ojs"},{"id":309,"value":"xcorrAliWong.img","pinned":false,"hidden":false,"mode":"ojs"},{"id":600,"value":"md`The below heatmap displays the input images reduced to their downsampled pixel values. These pixel values are used to calculate cross-correlation values.\n\nWhite rectangles show the extent of the input images, since downsampling is not guaranteed to produce an image of the same aspect ratio as the original. Black rectangles show the extent of the images after downsampling.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":292,"value":"xcorrAliWong.heat","pinned":false,"hidden":false,"mode":"ojs"},{"id":248,"value":"md`Change the crop of the right image:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":240,"value":"viewof cropInputAliWong = form(html``)","pinned":false,"hidden":false,"mode":"ojs"},{"id":577,"value":"viewof normalizeAliWong = checkbox({\n options: [{ value: \"doAction\", label: \"Normalize pixel values: subract average value\" }],\n value: \"doAction\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":233,"value":"viewof maxAllowedDimAliWong = slider({\n min: 10, \n max: 100, \n step: 10, \n value: 40, \n title: \"Downsample input images to have at most __ # of pixels per dimension:\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":489,"value":"md`---\n## Image set: donuts\n\nThe input images don't need to be the same for cross-correlation to find the approximate overlap.\n\nConsider these two images, taken from approximately the same location – although slight, differences include crop and table reflection location. Both images have the same number of pixels and the same aspect ratio.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":423,"value":"urlDonuts1 = 'https://gist.githubusercontent.com/lemonnish/a1d0bb1cd8d8fcc534b2571dd626e3bf/raw/0504d421ac83a2a6273abb41771629c51e9f827b/topPotHoriz.jpg'","pinned":false,"hidden":false,"mode":"ojs"},{"id":425,"value":"urlDonuts2 = 'https://gist.githubusercontent.com/lemonnish/a1d0bb1cd8d8fcc534b2571dd626e3bf/raw/0504d421ac83a2a6273abb41771629c51e9f827b/topPotVert.jpg'","pinned":false,"hidden":false,"mode":"ojs"},{"id":513,"value":"xcorrDonuts = drawJpgOverlap(urlDonuts1, urlDonuts2, {dataChannelMixer: mixerList[mixerDonuts], normalize: !!normalizeDonuts})//,{imgCrop2: cropInput, maxAllowedDim})","pinned":false,"hidden":false,"mode":"ojs"},{"id":517,"value":"xcorrDonuts.img","pinned":false,"hidden":false,"mode":"ojs"},{"id":450,"value":"xcorrDonuts.heat","pinned":false,"hidden":false,"mode":"ojs"},{"id":716,"value":"md`Change the function used to process the r/g/b/a channels of the original image, or define your own. The differences between different channel mixing methods becomes more apparent if normalization is turned off.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":729,"value":"viewof mixerDonuts = select({\n title: \"R/G/B/A channel mixing\",\n options: Object.keys(mixerList),\n value: Object.keys(mixerList)[0]\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":734,"value":"customMixer = (x,i) => {\n // custom function for mixing channel values\n // x = all pixel info; i = pixel number to mix (there are 4 values per pixel)\n const i0 = i*4 // r = x[i0]; g = x[i0 + 1]; b = x[i0 + 2]; a = x[i0 + 3]\n return x[i0]/2 + x[i0 + 1]\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":822,"value":"viewof normalizeDonuts = checkbox({\n options: [{ value: \"doAction\", label: \"Normalize pixel values: subract average value\" }],\n value: \"doAction\"\n})","pinned":false,"hidden":false,"mode":"ojs"},{"id":730,"value":"mixerList = ({\n // functions for mixing channel values\n // x = all pixel info; i = pixel number (there are 4 values per pixel)\n \"red\": (x,i) => x[i * 4 + 0],\n \"green\": (x,i) => x[i*4 + 1],\n \"blue\": (x,i) => x[i*4 + 2],\n \"alpha\": (x,i) => x[i*4 + 3],\n \"average color\": (x,i) => {\n const i0 = i*4\n return (x[i0] + x[i0 + 1] + x[i0 + 2])/3\n },\n \"average color (scaled by alpha)\": (x,i) => {\n const i0 = i*4\n return (x[i0] + x[i0 + 1] + x[i0 + 2]) * x[i0 + 3] / 765\n },\n \"customMixer\": customMixer\n})\n ","pinned":false,"hidden":false,"mode":"ojs"},{"id":504,"value":"md`---\n## Heavy-lifting functions`","pinned":false,"hidden":false,"mode":"ojs"},{"id":10,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":33,"value":"function loadImg(url) {\n return d3.image(url, {crossOrigin: \"anonymous\"})\n /*\n let img = new Image;\n img.crossOrigin = \"anonymous\";\n img.src = url\n return new Promise((resolve, reject) => {\n img.onload = () => resolve(img)\n img.onerror = reject\n })\n */\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":30,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":25,"value":"function arrayToMatrix(arr, width, height) {\n let mat = Array(height)\n let startVal = 0\n let endVal = startVal + width\n for (let i = 0; i < height; i++) {\n mat[i] = arr.slice(startVal, startVal += width)\n }\n return mat\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":36,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":685,"value":"md`### Display functions`","pinned":false,"hidden":false,"mode":"ojs"},{"id":76,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":23,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":361,"value":"function drawKey(ctx, color, x, y, width, height, options = {}) {\n const {steps = 10,\n displayDecimal = 2,\n fontColor = \"white\"} = options\n \n const minMax = color.domain()\n const textWidth = (displayDecimal + 4)*height*.6\n const textMargin = 5\n const format = d3.format(\".2f\")\n const blockWidth = (width - 2*textWidth - 2*textMargin)/steps\n \n // redefine/quantize color domain and draw color blocks\n color.domain([0, steps-1])\n for (let i = 0; i < steps; i++) {\n ctx.fillStyle = color(i)\n ctx.fillRect(x + textWidth + textMargin + i * blockWidth, y, blockWidth, height)\n }\n \n // label left/right value extremes\n ctx.fillStyle = fontColor\n ctx.font = `${height}px sans-serif`\n ctx.textAlign = \"right\"\n ctx.fillText(format(minMax[0]), x + textWidth, y + height)\n ctx.textAlign = \"left\"\n ctx.fillText(format(minMax[1]), x + width - textWidth, y + height)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":50,"value":"md`---\n## Imports`","pinned":false,"hidden":false,"mode":"ojs"},{"id":2,"value":"import {xcorr, visualizeXH, visualizeC, matrixMax} from \"@lemonnish/cross-correlation-of-2-matrices\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":231,"value":"import {slider, checkbox, select} from \"@jashkenas/inputs\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":238,"value":"import {form} from \"@mbostock/form-input\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":15,"value":"d3 = require(\"d3@5\")","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W37","stdlib":"1","titling":"auto"}