Image to Use for Hough Transform:
Threshold for finding circles, with the hough transform in purple and green circles representing circles found at that threshold.
6
Javascript Code:
// This builds a table that will give all possible centers that can
// come from this particular point on the circle. Better thing is to use gradients
// for orientation.
function buildLookUpTable(radiusMin, radiusMax)
{
var i = 0;
var incDen = 4 * radiusMin;
var radiusInc = 1;
var lut = [[[]],[[]]];
for (var i = 0; i < radiusMax; i++)
{
lut[0][i] = [];
lut[1][i] = [];
};
for (var tempRadius = radiusMin; tempRadius <= radiusMax; tempRadius++)
{
i = 0;
for (var row = 0; row < tempRadius; row++)
{
for (var col = 0; col < tempRadius; col++)
{
var dist = Math.sqrt(row*row + col*col);
var indexR = tempRadius - radiusMin;
if ((dist <= (tempRadius + 0.5)) && (dist >= (tempRadius - 0.5) ) )
{
lut[0][indexR][i] = col;
lut[1][indexR][i] = row;
i++;
};
};
};
};
return lut;
};
function houghTransform(img, imgd, thresh)
{
altImg = ctx.getImageData(0,0,ctx.viewportWidth,ctx.viewportHeight);
var altpix = altImg.data;
var pix = imgd.data;
var rowSize = ctx.viewportWidth;
var colSize = ctx.viewportHeight;
for (var row = 1; row < img.height - 1; row++)
{
for (var col = 1; col < img.width - 1; col++)
{
altpix[4*(row*rowSize + col) ] = 0;
altpix[4*(row*rowSize + col)+1 ] = 0;
altpix[4*(row*rowSize + col)+2 ] = 0;
altpix[4*(row*rowSize + col)+3 ] = 255;
};
};
var height = img.height;
var width = img.width;
var radiusMin = 1;
var radiusMax = 50;
var lut = buildLookUpTable(radiusMin, radiusMax);
var houghValues = [[[]]];
for (var i = 0; i <= img.width; i++)
{
houghValues[i] = [];
for (var j = 0; j <= height; j++)
{
houghValues[i][j] = [];
for (var k = 0; k < radiusMax + 1; k++)
{
houghValues[i][j][k] = 0;
};
};
};
//Hough Transform
for (var row = 1; row < img.height - 1; row++)
{
for (var col = 1; col < img.width - 1; col++)
{
for (var tempRadius = radiusMin; tempRadius <= radiusMax; tempRadius++)
{
// Binary image and image is a 1-D array so we need to skip by 4.
if (pix[4*((row)*img.width+(col))] > 1)
{
var indexR = (tempRadius - radiusMin);
// Let's add to the counter to every possible center or could be.
for (var i = 0; i < lut[0][indexR].length; i++)
{
var a = col + lut[1][indexR][i];
var b = row + lut[0][indexR][i];
if((b >= 0) && (b < height) && (a >= 0) && (a < width))
{
houghValues[a][b][indexR-1] = houghValues[a][b][indexR-1] + 1;
altpix[4*(b*rowSize + a) ] += 1;
altpix[4*(b*rowSize + a)+1 ] += 0;
altpix[4*(b*rowSize + a)+2 ] += 1;
altpix[4*(b*rowSize + a)+3 ] = 255;
}
};
};
};
};
};
//find the max radius
var maxCounter = 0;
var maxRs = [];
for (var k = 0; k < radiusMax + 1; k++ )
{
for (var j = 0; j < img.height; j++)
{
for (var i = 0; i < img.width; i++)
{
if (houghValues[i][j][k] > maxCounter)
{
maxCounter = houghValues[i][j][k];
};
};
};
};
for (var k = 0; k < radiusMax + 1; k++ )
{
for (var j = 0; j < img.height; j++)
{
for (var i = 0; i < img.width; i++)
{
if (houghValues[i][j][k] >= maxCounter-thresh)
{
for (var row = -k; row < k; row++)
{
for (var col = -k; col < k; col++)
{
var dist = Math.sqrt(row*row + col*col);
var b = j + row;
var a = i + col;
if ((dist <= (k + 1)) && (dist >= (k - 1) ) )
{
altpix[4*(b*rowSize + a) ] += 0;
altpix[4*(b*rowSize + a)+1 ] = 255;
altpix[4*(b*rowSize + a)+2 ] += 0;
altpix[4*(b*rowSize + a)+3 ] = 255;
};
};
};
};
};
};
};
console.log(maxCounter);
ctx.putImageData(altImg,0,height + 5);
};
Image to use for Haar Wavelet Transform
Can change how many times the Haar function recurses (as opposed to recursing until completion).
3
Javascript Code:
function OneDHaarTransform(HaarMatrix)
{
var sum = 0;
var diff = 0;
var hMLen = HaarMatrix.length/2;
var tempHaar = [];
//It only recurses on first half of the array
for (var i = 0; i < hMLen; i++)
{
sum = HaarMatrix[2*i] + HaarMatrix[2*i + 1];
sum = sum / Math.sqrt(2);
diff = HaarMatrix[2*i] - HaarMatrix[2*i + 1];
diff = diff / Math.sqrt(2);
tempHaar[i] = sum;
tempHaar[i + hMLen] = diff
};
for (var i = 0; i < HaarMatrix.length; i++) {
HaarMatrix[i] = tempHaar[i];
};
};
function HaarTransform(img, imgd, MaxStepHaar)
{
altImg = ctx.getImageData(0,0,ctx.viewportWidth,ctx.viewportHeight);
var altpix = altImg.data;
var pix = imgd.data;
var rowSize = ctx.viewportWidth;
var colSize = ctx.viewportHeight;
var width = img.width;
var height = img.height;
var currWidth = img.width;
var currHeight = img.height;
var Haar = [];
var tempHaar = [];
//Initialize the Haar matrix
for (var row = 0; row < img.height; row++)
{
Haar[row] = [];
for (var col = 0; col < img.width; col++) {
Haar[row][col] = [];
for (var i = 0; i < 3; i++) {
Haar[row][col][i] = pix[4*(row*img.width + col + i)];
};
};
};
//Do a Haar Wavelet Transform
while( (currWidth > 1 || currHeight > 1) && (MaxStepHaar > 1) )
{
MaxStepHaar = MaxStepHaar - 1;
//Do it for each row first
if (currWidth > 1)
{
for(var row = 0; row < currHeight; row++)
{
for (var i = 0; i < 3; i++) {
for(col = 0; col < currWidth; col++) {
tempHaar[col] = Haar[row][col][i];
};
OneDHaarTransform(tempHaar);
for(col = 0; col < currWidth; col++) {
Haar[row][col][i] = tempHaar[col];
};
};
};
};
//Then perform Haar transform on each column
tempHaar = [];
if (currHeight > 1)
{
for(var col = 0; col < currWidth; col++)
{
for (var i = 0; i < 3; i++) {
for(row = 0; row < currHeight; row++) {
tempHaar[row] = Haar[row][col][i];
};
OneDHaarTransform(tempHaar);
for(row = 0; row < currHeight; row++) {
Haar[row][col][i] = tempHaar[row];
};
};
};
};
tempHaar = [];
if (currHeight > 1) {currHeight = currHeight/2};
if (currWidth > 1) {currWidth = currWidth/2};
};
//Copy pix data to canvas
for (var row = 0; row < img.height; row++) {
for (var col = 0; col < img.width; col++) {
altpix[4*(row*rowSize + col) ] = Haar[row][col][0];
altpix[4*(row*rowSize + col)+1 ] = Haar[row][col][1];
altpix[4*(row*rowSize + col)+2 ] = Haar[row][col][2];
altpix[4*(row*rowSize + col)+3 ] = 255;
};
};
ctx.putImageData(altImg,0,0);
};