-
Notifications
You must be signed in to change notification settings - Fork 1
/
hough.pde
148 lines (132 loc) · 5.56 KB
/
hough.pde
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
ArrayList<PVector> hough(PImage edgeImg) {
float discretizationStepsPhi = 0.03f;
float discretizationStepsR = 2.5f;
// dimensions of the accumulator
int phiDim = (int) (Math.PI / discretizationStepsPhi);
int rDim = (int) (((edgeImg.width + edgeImg.height) * 2 + 1) / discretizationStepsR);
// our accumulator (with a 1 pix margin around)
int[] accumulator = new int[(phiDim + 2) * (rDim + 2)];
// pre-compute the sin and cos values
float[] tabSin = new float[phiDim];
float[] tabCos = new float[phiDim];
float ang = 0;
float inverseR = 1.f / discretizationStepsR;
for (int accPhi = 0; accPhi < phiDim; ang += discretizationStepsPhi, accPhi++) {
// we can also pre-multiply by (1/discretizationStepsR) since we need it in the Hough loop
tabSin[accPhi] = (float) (Math.sin(ang) * inverseR);
tabCos[accPhi] = (float) (Math.cos(ang) * inverseR);
}
// Fill the accumulator: on edge points (ie, white pixels of the edge
// image), store all possible (r, phi) pairs describing lines going
// through the point.
for (int y = 0; y < edgeImg.height; y++) {
for (int x = 0; x < edgeImg.width; x++) {
// Are we on an edge?
if (imgproc.brightness(edgeImg.pixels[y * edgeImg.width + x]) != 0) {
// ...determine here all the lines (r, phi) passing through
// pixel (x,y), convert (r,phi) to coordinates in the
// accumulator, and increment accordingly the accumulator.
// Be careful: r may be negative, so you may want to center onto
// the accumulator with something like: r += (rDim - 1) / 2
//int rMax = (int) ((edgeImg.width + edgeImg.height) * 2 + 1);
for (int i = 0; i < phiDim; ++i ) {
double r = x * tabCos[i] + y * tabSin[i];
r += (rDim - 1)/2;
accumulator[((i+1)*(rDim+2) + (int)(r+1))] += 1;
}
}
}
}
// Step 2
//houghImg = createImage(rDim + 2, phiDim + 2, ALPHA);
//for (int i = 0; i < accumulator.length; i++) {
// houghImg.pixels[i] = color(min(255, accumulator[i]));
//}
//// You may want to resize the accumulator to make it easier to see:
//houghImg.resize(175, 240);
//houghImg.updatePixels();
ArrayList<Integer> bestCandidates = new ArrayList<Integer>();
// size of the region we search for a local maximum
int neighbourhood = 50;
// only search around lines with more that this amount of votes
// (to be adapted to your image)
int minVotes = 170;
for (int accR = 0; accR < rDim; accR++) {
for (int accPhi = 0; accPhi < phiDim; accPhi++) {
// compute current index in the accumulator
int idx = (accPhi + 1) * (rDim + 2) + accR + 1;
if (accumulator[idx] > minVotes) {
boolean bestCandidate=true;
// iterate over the neighbourhood
for(int dPhi=-neighbourhood/2; dPhi < neighbourhood/2+1; dPhi++) {
// check we are not outside the image
if( accPhi+dPhi < 0 || accPhi+dPhi >= phiDim) continue;
for(int dR=-neighbourhood/2; dR < neighbourhood/2 +1; dR++) {
// check we are not outside the image
if(accR+dR < 0 || accR+dR >= rDim) continue;
int neighbourIdx = (accPhi + dPhi + 1) * (rDim + 2) + accR + dR + 1;
if(accumulator[idx] < accumulator[neighbourIdx]) {
// the current idx is not a local maximum!
bestCandidate=false;
break;
}
}
if(!bestCandidate) break;
}
if(bestCandidate) {
// the current idx *is* a local maximum
bestCandidates.add(idx);
}
}
}
}
Collections.sort(bestCandidates, new HoughComparator(accumulator));
int nLines = 4;
ArrayList<PVector> lines = new ArrayList<PVector>();
for (int i = 0; i < nLines; ++i) {
if (i < bestCandidates.size()) {
int idx = bestCandidates.get(i);
// first, compute back the (r, phi) polar coordinates:
int accPhi = (int) (idx / (rDim + 2)) - 1;
int accR = idx - (accPhi + 1) * (rDim + 2) - 1;
float r = (accR - (rDim - 1) * 0.5f) * discretizationStepsR;
float phi = accPhi * discretizationStepsPhi;
lines.add(new PVector(r,phi));
// Cartesian equation of a line: y = ax + b
// in polar, y = (-cos(phi)/sin(phi))x + (r/sin(phi))
// => y = 0 : x = r / cos(phi)
// => x = 0 : y = r / sin(phi)
// compute the intersection of this line with the 4 borders of
// the image
/*int x0 = 0;
int y0 = (int) (r / sin(phi));
int x1 = (int) (r / cos(phi));
int y1 = 0;
int x2 = edgeImg.width;
int y2 = (int) (-cos(phi) / sin(phi) * x2 + r / sin(phi));
int y3 = edgeImg.width;
int x3 = (int) (-(y3 - r / sin(phi)) * (sin(phi) / cos(phi)));
// Finally, plot the lines
imgproc.stroke(204,102,0);
if (y0 > 0) {
if (x1 > 0)
imgproc.line(x0, y0, x1, y1);
else if (y2 > 0)
imgproc.line(x0, y0, x2, y2);
else
imgproc.line(x0, y0, x3, y3);
}
else {
if (x1 > 0) {
if (y2 > 0)
imgproc.line(x1, y1, x2, y2);
else
imgproc.line(x1, y1, x3, y3);
}
else
imgproc.line(x2, y2, x3, y3);
}*/
}
}
return lines;
}