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.