image processing
assignment #5
Houghing Lines
Magnitude |
Original |
Binary |
Houghspace |
Lines only |
Overlay |
Lax |
|||||
Lenna |
Direction |
Original |
Binary |
Houghspace |
Lines only |
Overlay |
Lax( 5 degrees) |
|||||
Lenna ( -60 degrees ) |
commentary
Speed
Obtaining hough space
for( y=0; y<rows; y++ )
for( x=0; x<cols; x++ )
if( ptr[ y*cols + x ] == 255 )
{
x = x - halfCols ;
y = halfRows - y ;
for( angle=0; angle<360; angle++ )
{
theta = pii * angle ;
//equation for a line
r = (int)( x * cos( theta ) + y * sin( theta ) ) ;
r += halfxAxis ;//get rid of negative sign
lineArray[ angle * xAxis + r ]++ ;//accummulating
}
}
The algorithms used to detect lines had a maximum length of Order O( n^3 ) as one can see. The speed for detecting lines is tolerable compared with circle detection.
For redrawing the lines
for( angle=window; angle<=180+window; angle++ )
for( r=window; r<xAxis-window; r++ )
if( lineArray[ angle*xAxis + r ] > threshold )
{
int count = 0 ;
int nextHighest = lineArray[ angle*xAxis + r ] ;
for( int j=angle-window; j<=angle+window; j++ )
for( int i=r-window; i<=r+window; i++ )
if( lineArray[ j*xAxis + i ] > nextHighest )
count++ ;
//if highest value then draw its line
if( !count )
rasterLine( r, angle ) ; O( n^1 )
}//end if
The algorithms used for redrawing lines has worst case of O( n^5 ) as one can see. Raster Line contains one loop so it is of O( n^1 ). However this algorithm runs faster than the previous algorithm since the third, fourth and fifth loops get operated on a small percentage of the time in practice.
Memory requirements
The memory requirements for detecting lines was tolerable. That is, the size of the hough space is of the same order as the worked on image, roughly O( n^2 ).
Two main arrays were kept full at all times. One to hold the image and the other to keep the accumulator information in tact. I also used some temp arrays. I usually deleted these temp arrays after their use.
Quality of results
The lines detected , by the Hough transform trancended the entire image. Thus it was impossible to segment the derived lines in order to keep their original length. Also, the hough space showed a rather highlighted line when the range = 0 in the hough space. For this reason I had to ignore lines whose range = 0. Due to time constraints, I could not investigate this matter further.
Theoretically, points on a line in x-y space should coincide on the hough space as one point. However, such factors such as round off errors makes it impossible for that type of precision. So I also used a window to track down the local maxima. The larger the window the more restrictive the results were( that is, the lines became less apparent ). For the lines I used a 7x7 window and about 50% of the maximum accumulation to obtain the images above.
Directional
For this project we also had to implement the directional gradient. According to Dr. Goldgof, implementing the direction aspect of the gradient should reduce the magnitude of the problem, or speed by a factor of one. That is, O( n^2 ) instead of O( n^3 ). However, I had trouble grasping the concept rightaway. For the directional implementation I just used the sobel operator to detect the direction information and then used that binary image as input.
I used an angle of 5 degrees on the lax to detect the smaller horizontal lines. However some vertical lines became present. I had increased the size of my window then perhaps the vertical might have waned.
Houghing Circles
magnitude |
Original |
Binary |
Houghspace |
Circles only |
Overlay |
Ge |
|||||
Gear |
direction |
Original |
Binary |
Houghspace ( direction = -90degrees ) |
Circles only |
Overlay |
Ge ( -90 degrees ) |
|||||
Gear ( -90 degrees ) |
commentary
Speed
Obtaining hough space
for( y=0; y<rows; y++ )
for( x=0; x<cols; x++ )
if( ptr[ y*cols + x ] == 255 )
{
for( a=0; a<aRows; a++ )
for( b=0; b<bCols; b++ )
{
dy = y - a ;
dx = x - b ;
//equation for a circle
r = sqrt( dx*dx + dy*dy ) ;
circleArray[ r ][ a*bCols + b ] =
circleArray[ r ][ a*bCols + b ] + 1 ;//accumalate
}
}
As the routine above stands it is of order O( n^4 ), pretty slow.
Redrawing the circles
z = view ;
for( a=window; a<aRows-window; a++ )
for( b=window; b<bCols-window; b++ )
if( circleArray[ z ][ a*bCols + b ] > threshold )
{
int count = 0 ;
//get highest value
int nextHighest = circleArray[ z ][ a*bCols + b ] ;
for( int k=z-window; k<=z+window; k++ )
for( int j=a-window; j<=a+window; j++ )
for( int i=b-window; i<=b+window; i++ )
//if it is not the highest in the cube
//then do not draw the circle
if( circleArray[ k ][ j*bCols + i ] > nextHighest )
count++ ;
//if it is the only maxima then draw the circle
if( !count )
rasterCircle( b, a, z ) ;//O( n^1 )
}//end if
As the routine above stands it is of order O( n^6 ) with rasterCircle containing one loop as well. This speed is very slow. If I had to loop through the entire zAxis then the order would have reached
O( n^7 ). Time enough to make you and all your classmates some coffee I suppose. The third inner for loop makes reference to k. This only loops as many times as the window size is since z is constant here.
However, since the third, fourth, fifth, and sixth loops get called less frequently this algorithm operates much faster than the previous algorithm.
Memory requirements
The memory requirements for detecting circles required one more magnitude than detecting lines due to circle equation containing five parameters instead of the lines four. That is, the size of the hough space( O(n^3) is one order more than the image( O( n^2 ) ). Like the line, the two main arrays were kept full at all times. One to hold the image and the other to keep the accumulator information in tact. I again also used some temp arrays. I usually deleted these temp arrays after their use.
Quality of results
The circles detected , by the Hough transform contained a radius of 10. If any circles had a radius larger than 10 than more than one circle would represent that circle. Also if the circle was less than radius 10 the circle generated by the hough would contain it plus some extra pixels.
Theoretically, points on a circle in x-y space should coincide on the hough space as a cone. However, such factors such as round off errors makes it impossible for that type of precision. So I again used a window to track down the local maxima. However instead of a large the window, I found using a smaller window helped obtain better results. For the circles I used a 3x3 window and about 50% of the maximum accumulation to obtain the images above.
Directional
Again, implementing the direction aspect of the gradient should reduce the magnitude of the problem, or speed by a factor of one. That is, O( n^3 ) instead of O( n^4 ). For the directional implementation I just used the sobel operator to detect the direction information and then used that binary image as input.
The results using angle of -90degrees +/- 10 degrees shows up rather well for the gear but not the ge.