Digital Signal and Image Processing Lecture 3 PDF

Digital Signal and Image Processing Lecture 3 – Analog to Digital Conversion Cont. Dr. T. Akilan [email protected] © Dr. T. Akilan 1 This Session Recap Analog and digital signals o Sampling th...

Digital Signal and Image Processing Lecture 3 – Analog to Digital Conversion Cont. Dr. T. Akilan [email protected] © Dr. T. Akilan 1 This Session Recap Analog and digital signals o Sampling theorem o Quantization o Numerical examples Digital Images o Digital Image Processing MATLAB © Dr. T. Akilan 3  Recap – Sampling and Reconstruction Three core steps in A/D conversion: Example of sampling & reconstruction of a signal, 𝒇(𝒕) o Sampling, Quantization, and Coding. Original Sample Reconstructed Reconstruction requires sufficient 𝒇(𝒕) samples. Otherwise, we could not 𝟏. 𝟎 accurately reconstruct the signal 𝟎. 𝟓 (observe the animation) 𝒕 Q: How do we know what is the minimum number of samples that are −𝟎. 𝟓 sufficient for a perfect reconstruction? Reconstructed signal is becoming closer to the original signal with A: Use Nyquist sampling frequency or steadily increasing sample-densities Nyquist rate (sample rate - 𝜔𝑠 ) Image Source: https://upload.wikimedia.org/wikipedia/commons/4/43/Nyquist_sampling.gif © Dr. T. Akilan 4  Sampling and Reconstruction: Nyquist-Shannon Sampling Theorem CT signals DT signals. A sufficient condition, i.e., a sample rate that permits a discrete sequence of samples to capture all the information from a continuous-time signal of finite bandwidth. The sample rate guarantees no actual information is lost in the sampling process, resulting in a perfect Harry Nyquist (1889 – 1976) reconstruction of the original signal from the samples. If a function 𝑥(𝑡) contains no frequencies higher than 𝐵 Hz, it is completely determined by giving its ordinates at a series of 1 points spaced sec. apart: 2𝐵 o sample-rate (𝑓𝑠 ) is anything > 2𝐵 samples/s, i.e., 𝑓𝑠 > 2𝐵 𝐻𝑧 ▪ Formulated in 1928 by Harry Nyquist, a Bell Laboratories scientist and engineer. ▪ Claude E. Shannon, also from Bell Labs, proved the theorem formally in 1949. Claude E. Shannon (1916 - 2001) → Sampling theorem E.g. Image Sources: https://en.wikipedia.org/wiki/Harry_Nyquist, https://flatironschool.com/ © Dr. T. Akilan 5  Nyquist-Shannon Sampling Theorem – Example # 1 If the maximum frequency contained in an analog signal is fmax = B, then it can be perfectly reconstructed from samples taken at the sampling frequency fs = 2B. o fmax is called the Nyquist frequency o fs is called the Nyquist rate o Typically, we sample at a rate a little above fs for safety. o fs > 2fmax For example, an audio signal has 𝐹𝑚𝑎𝑥 of 20𝑘𝐻𝑧, so we need 40𝑘𝐻𝑧, but we typically use 44𝑘𝐻𝑧 If a voice signal containing frequencies up to 4kHz, what appropriate sampling frequency can be used to discretize the signal? → Sampling theorem E.g. # 2 © Dr. T. Akilan 6 Sampling and Reconstruction – Example # 2 𝑠3 (𝑥) = sin 40𝑥 o fmax = 6.3662 Hz How do we know fmax = 6.3662 Hz? o fs = 12.7324 Hz Let’s sample the signal at 10 Hz, i.e., Ts = 0.1s and reconstruct it (w/o considering Nyquist rate) s3 (nTs ), Ts = 0.1 What went wrong? © Dr. T. Akilan 7 Sampling and Reconstruction 𝑠3 (𝑥) = sin( 40𝑥) o fmax = 6.3662 Hz o fs = 12.7324 Hz Considering Nyquist theorem, let’s sampling the signal at 14 Hz Observation: Still, it looks like a bad reconstruction, due to straight-line interpolation, but we have the right general shape © Dr. T. Akilan 8 Sampling – Numerical Example # 1 A message signal defined by 𝑚 𝑡 = 2 sin 2𝜋𝑡 × cos(𝜋𝑡), compute its Nyquist sampling rate in rad/sec and Hz. Step 1: Represent the signal into sum of different sinusoids sin(𝛼 + 𝛽) + sin(𝛼 − 𝛽) = 2 sin(𝛼) cos(𝛽) 𝑚 𝑡 = 𝑚1 𝑡 + 𝑚2 (𝑡) 𝑚 𝑡 = 𝑠𝑖𝑛 2𝜋𝑡 + 𝜋𝑡 + 𝑠𝑖𝑛 2𝜋𝑡 − 𝜋𝑡 𝑚 𝑡 = 𝑠𝑖𝑛 3𝜋𝑡 + 𝑠𝑖𝑛 𝜋𝑡 𝜔1 = 3𝜋 𝜔2 = 𝜋 Step 2: Find the maximum frequency component: 𝜔𝑚 = 3𝜋 rad/s Step 3: Estimate the appropriate sampling frequency: 𝜔𝑠 = 2𝜔𝑚 = 6𝜋 rad/s 𝜔𝑠 6𝜋 𝑓𝑠 = = = 3 Hz 2𝜋 2𝜋 © Dr. T. Akilan 9 Sampling – Numerical Example # 1 Cont.: Nyquist’s property A message signal defined by 𝑚 𝑡 = 2 sin 2𝜋𝑡 × cos(𝜋𝑡), compute its Nyquist sampling rate in rad/sec and Hz. Using Nyquist property: 𝑚 𝑡 = 𝑚1 𝑡 × 𝑚2 (𝑡)  product of two signals 𝜔𝑠 = 𝜔𝑠1 + 𝜔𝑠2  overall signal’s sampling freq. is sum of the individual signal’s sampling freq. Nyquist’s property Let 𝑚1 𝑡 = sin 2𝜋𝑡 ⇒ 𝜔𝑚1 = 2𝜋 ⇒ 𝜔𝑠1 = 2𝜔𝑚1 = 4𝜋 Similarly let 𝑚2 𝑡 = co𝑠 𝜋𝑡 ⇒ 𝜔𝑚2 = 𝜋 ⇒ 𝜔𝑠2 = 2𝜔𝑚2 = 2𝜋 So, 𝜔𝑠 = 4𝜋 + 2𝜋 = 6𝜋 rad/s 𝜔𝑚 6𝜋 𝑓𝑠 = = = 3 Hz 2𝜋 2𝜋 © Dr. T. Akilan 11 Sampling – Pop Quiz # 2 A message signal defined by 𝑚 𝑡 = cos 200𝜋𝑡 × cos(100𝜋𝑡), compute its Nyquist sampling rate in rad/sec and Hz. © Dr. T. Akilan 12 Analog to Digital Signals – Step 2: Quantization After the sampling, the discrete time continuous signal still carry infinite information (can take any value) in terms of amplitude. Quantization is the process to reduce infinite information of the amplitude. Quantizer do the conversion of discrete time continuous valued signal into a discrete-time discrete-valued signal. o The value of each sample is represented by a value selected from a finite set of possible values. © Dr. T. Akilan 13 Analog to Digital Signals – Quantization Level The quantizer chooses a quantization level for each analog sample. # of levels of a quantizer, 𝑳 = 𝟐𝑵 Amplitude (Voltage) An N-bit A/D converter chooses among 2N possible quantization levels. o E.g., 3-bit converter has 8 quantization levels, and 4-bit converter has 16 quantization levels. More quantization levels, a better resolution! Time (ms) What's the downside of more quantization levels? © Dr. T. Akilan 14  Analog to Digital Signals – Quantization Step E.g., an analog signal has a range of 0V - 10V The quantization step size or resolution 𝑹 is calculated as: Δ = 𝑸 = 𝑵 , where 𝟐 Amplitude (Voltage) o R: full-scale range of the analog signal (i.e., Ymax - Ymin) o N: number of bits used by the converter Resolution of a quantizer is the distance between two successive quantization levels ms Strength of the signal: It is determined 3-bit quantization: 𝑄 = 2𝑁 = 𝑅 10−0 = 1.25 23 by quantization errors, dynamic range, and signal-to-noise ratio. Compute the resolution of 16-bit quantization Quantization Error → © Dr. T. Akilan 15 Analog to Digital Signals – Quantization Error The error caused by representing a Example continuous-valued signal (infinite set) Digital Quantized Digital signal 𝒙𝒒[𝒏] Sample-and-hold signal level (v) by a finite set of discrete-valued levels. code 111 0.875 𝒙[𝒏] 110 0.750 Quantized It is calculated as the difference 101 levels 0.625 between the quantized level and the 100 0.500 Analog true sample level. 011 0.375 signal Let a quantizer operation given by 010 0.250 𝑄(. ) is performed on continuous-valued 001 0.125 samples 𝑥[𝑛] is given by 𝑄 𝑥 𝑛 , then 000 0.000 the quantization error is given by: Quantization 𝒆𝒒[𝒏] = 𝒙[𝒏] – 𝒙𝒒[𝒏] error 𝒙[𝒏] – 𝒙𝒒[𝒏]  # of quantization levels, results in  Digital signal codes: 011 101 110 111 111 111 110 101 011 010 quantization errors. © Dr. T. Akilan 16 Analog to Digital Signals – Quantization Error Cont. Quantization error can be reduced, if the number of quantization levels is increased as illustrated in the figure below. 0.14 × 𝟏𝟎−𝟑 4 0.02 0 3-bit ADC Quantization error 8-bit ADC Quantization error We can see that there is a difference between continuous-valued samples 𝑥[𝑛] (blue circle) and the quantized samples 𝑥𝑞 [𝑛] (red Lines). This is the error produced while quantization. © Dr. T. Akilan 17 Hold on! Shall we take the understanding of signal sampling and quantization to digital image? © Dr. T. Akilan 18  Useful References Tamal Bose, Digital Signal and Image Processing, Wiley 2004, ISBN: 978-0-471-32727-1 Digital Image Processing, 4th Edition, Richard E. Woods, 2018 , Pearson. Understanding Digital Signal Processing, Third Edition, Richard G. Lyon © Dr. T. Akilan 19 Next up Digital Image Representation © Dr. T. Akilan 20