08-02-04

 

Hough Transform

 

Pattern Recognition

Problem: Recognition of lines, given a set of points (X0,Y0),(X1,Y1),……(Xn,Yn)

Identify the lines that pass through them and reduce the error

 

 

 

The Hough Transform uses an accumulator matrix where each element represents a possible line

 

                        Input Points                                                      Accumulator matrix, lines are represented in polar form, R=xcosӨ + ysinӨ, R, Ө are constants

 

The Hough Algorithm for every input data point it increments all the possible entries in the accumulator matrix that may contain the point

 

A point (x,y) corresponds to a sine curve in the accumulator matrix

 

The Hough Algorithm increments by one all the entries in the accumulator matrix that correspond to the lines that may include x,y.

Hough Algorithm for a line for each point (Xk,Yk) in the input  

for i = 0 to M, Example M = 100 (# of line associated to x,y)

                        TETA = 2pi/M

                        R = Xk*cos(TETA) + Yk*cos(TETA)

                        Accum[R,TETA]++;

            end

            //Get accumulator entries above threshold

            for TEAT = 0 to MaxTETA

                        for R = o to MaxR

                                    If Accum[R,TETA[ > threshold

                                                Found line at R,TETA

                                    end

                        end

            end

 

Reconstruction from Accumulator Matrix using the entries above threshold

 

Hough Transform for Circles

Assume R is know for Ө = 0 to 2pi, x = Rcos Ө + x0, y = Rsin Ө + y0 or R² = (x-x0)²+(y-y0)²

A point x,y in the input will correspond to a circle in the accumulator matrix that will be center at x,y with radiur R

 

Algorithm:

            for each point (Xk,Yk)

                        for I =0 to M    //(M =100 # of circle that contain this point)

                                    TETA = 2pi/M;

                                    X0= R*cos(TEAT) + x0;

                                    Y0= R*sin(TETA) + y0;

                                    Accum[X0][Y0]++;

                        end

            end

            for X0 = 0 to MaxX

                        for Y0 = 0 to MaxY

                                    if accum[X0][Y0] > threshold

                                                found circle of Radius R centered at X0,Y0

                                    end

                        end

            end

 

08-03-04

 

Fourier Series

 

We can express a periodic function as a summation of sine and cosine functions

Uses of Fourier Transform

            + sound compression

                        -digital sound is a sequence of numbers or data samples that represent the sound level at different points of time

                        -this representation is also called PCM or pulse-code-modulation

Example of a sound files 254,253,200,189

What sampling rate to use? (# of samples per second)

HiFià44k samples per second

Telephonyà6k samples per second

If you use 2 bytes per sample of sound at 44k samples/sec

            44k/sec * 2 bytes = 88 kb/sec

For a 5 minutes song

            =5 minutes *  60secs/min * 88 kb/sec

            = 300 * 88kb = 270000000, 27MB

Sound Compression, the sound data is divided into slices (example every 1/20th of a sec)

-in each slice apply the Fourier transform and obtain the ai, bj coefficients

-in telephony the high frequency components that is, the coefficients with large I or j are eliminated

MP3 ENCODER

-         in MP3 compression, the small coefficients that are adjacent to large coefficients are eliminated since they are no parceled

Only the peak of signal are stored, the other components are eliminated or less bits will be used to store the smaller coefficients

-         the remaining coefficients are stored in the MP3 file with the reduction in the size

 

MP3 DECODER

-the Mp3 decoder will use the coefficient to reconstruct the original signal to equation (1) described before

-in good MP3 encoder/decoder and with a high sampling rate it is difficult to tell the difference between the original signal and the reconstructed signal

- the Fourier Transform can be obtained using Numerical Integration or an optimized algorithm called FFt- Fast Fourier Transform that takes O(nlogn) n-samples with Trapezoidal rule or Simpson we need n integration for n-samples to obtain n coefficients,that is O(n²).