8-2-04

Hough Transforms (cont.)
- Problem: recognition of lines
- Given a set of points, identify lines through them and reduce error
- Lines represented in polar form
- A point in the x-y plane corresponds to a sine curve in the polar plane
- All entries in the accumulator matrix that are passed through by the curve in the polar plane are incremented (correspond to lines through the point)

for each point (x[k],y[k]) in the input
   for i=0 to M (which is the # of lines associated)
      theta = 2π/M
      R = x[k] cos(theta) + y[k] sin(theta)
      Accum[R,theta]++;
   end
end
for theta to maxTheta
   for r=0 to maxR
      if Accum[R,theta]>threshhold
         found line at R, theta
      end
   end
end

- Circles on the x-y graph correspond to points in the circle accumulator matrix (which is in terms of x[0] and y[0]), while points go to circles

for each point (x[k],y[k]) in the input
   for i= 0 to M
      theta = 2π/M
      x[0] = R cos(theta) + x[0]
      y[0] = R sin(theta) + y[0]
      Accum[x[0],y[0]]++;
   end
end
for x[0] = 0 to maxX
   for y[0] = 0 to maxY
      if Accum[x[0],y[0]] > threshhold
         found circle of radius R centered at (x[0],y[0])
      end
   end
end

8-3-04

Fourier series
- We can express a periodic function as a summation of sin and cos functions
- Assume that f(x) is periodic with period of 2π
- f(x) = a[0]/2 + ∑[j=1;∞] (a[j]cos(jx) + b[j]sin(jx))
∫ [-π;π]f(x) = (∫[-π;π]a[0]/2)+ ∑[j=1;∞](∫[-π;π]a[j]cos(jx)+∫[-π;π]b[j]sin(jx))
= a[0]π
- a[0] is the average of f(x) over [-π,π]
- To obtain a[m] for m ≥ 1, multiply by cos(mx) and integrate from -π to π
- While j ∫ m, cos(jx)cos(mx) = 0 (otherwise, it equals π)
- sin(jx)cos(mx) = 0 for all possible j and m
- While j ∫ m, sin(jx)sin(mx) = 0 (otherwise, it equals π)
- ∫[-π;p] f(x)cos(mx) = a[j] π, so a[j] = (1/π)(∫[-π;p] f(x)cos(mx))
- b[m] = (1/π)(∫[-π;π] f(x)sin(mx)) for m ≥ 1
- The coefficients a[m] and b[m] are referred to as the Fourier transform (and are the representation of f(x) in the frequency domain)
- Sound compression (using FFT, which is O(n log n), instead of Simpson/Trapezoidal rules, which are O(n^2))
   * Digital sound is a sequence of sound levels in time
   * This representation is also called PCM (Pulse Code Modulation)
   * Level of fidelity refers to the # of sound levels per second
   * Hi-Fi = 44K saved per second
   * Telephone = 6K saved per second
   * Method for compression
      + Data is divided into slices (such as 1/20 of a second)
      + Fourier transform is applied to each slice (get a[i],b[j])
      + In telephony, the high-frequency components are eliminated
      + In MP3, small coefficients near larger ones are eliminated (or are stored with fewer bits in order to save space), the rest are encoded smaller
      + If a good encoding/decoding scheme is used, it is difficult/impossible to tell the difference between the original and the reconstructed signal