DIP_Lecture-3_4-RKJ_Sampling_Quantization_2023.pdf

dip

1. Digital Image Processing
Dr. RajibKumar Jha
Associate Professor
Depart of Electrical Engineering
Indian Institute of Technology Patna
[email protected]
1
Lecture Notes-2025

2. 2
Lecture-3-4
Sampling, Quantization, Pixel
Relationship, Connectivity

3. Contents
•Image digitization.
•Sampling of images.
•Image reconstruction from the sampled signal.
•Image Quantization
•Dither
•Neighborhood of Pixels
•Connectivity
•Adjacency
•Path
•Algorithm for Connected Component Analysis
3

4. Sampling & Quantization
4

5. 1-Dimensional Sampling
•Sampling frequency, f
S=1/Δt
S
•Reducingsamplingintervalby1/2meansincreasing
samplingfrequencybytwice,i.e.,moreinformation
contentiskeptinthesampledsignal.
•Nowquestioniswhatshouldbethesampling
frequencybywhichmaximuminformationofthe
signalcanbekept.
If Δt
S
’
= Δt
S/2 the f
’
S
=
1/Δt
S
’
= 2/Δt
S= 2f
S

6. Sampling
6
Samplingfunctioncanbe
representedmathematicallybya
formofcombfunction.
�����;∆�=෍
??????=−∝
∝
�(�−�∆�)
�
�(t)=X(t).comb(t,Δt)
�
�(t)=෍
??????=−∝
∝
�(�∆�)�(�−�∆�)
•Samplingisproperonlywhenwecan
reconstructoriginalsignalback.

7. 7
Signal Reconstruction from Samples
•��.�(�)֞
??????�
�(�)∗�(�)
•��∗��֞
??????�
��.�(�)
•�
�(t)=X(t).comb(t,Δt
S)
•�
�(�)=X(�)∗F{comb(t,Δt
S)}
•�
�(�)=X(�)∗COMB(�)
Fourier Transform Properties

8. Comb and Gaussian function
8

9. Example-Convolution
9
000010000000010000000010000
2 5 7 9 3
h(n)
x(n)
��=෍
??????=−∝
∝
ℎ��(�−�)
3 9 7 5 2
x(-n)

10. Example-Convolution
10
000010000000010000000010000
3 9 7 5 2
x(-11-n)
002000000000000000000000000
002500000000000000000000000
0
-9 9

11. Convolution Continue
11
002570000000000000000000000
002579000000000000000000000
002579300000000000000000000
002579300002579300002579300
0-9 9

12. Convolution Continue
12
�
�(�)=X(�)∗COMB(�)
=
1
∆??????
??????
−�
0>�
0
=
1
∆????????????
>2�
0
=??????
�>2�
0
0 ω
0 1/Δt
s
--------------------1/Δt
s
0 ω
0
∗

13. Aliasing Effect
13

14. 14
Sampling/Image Reconstruction
1024 512 256
128 64 32

15. Sampling
15

16. Resolution is same but size is varying
1024
512
256
128
64
32
16
Reduce the file size of pixels => Save image as close as possible to
the original

17. Image Quantization
•Quantization is a mapping of a continuous variable �to a
discrete variable �
′.
•�
′
∈�
1,�
2,�
3,…..�
??????
•�
•Mapping is generally staircase representation.
•Quantization Rule: Define a set of decision or transition levels.
•{t
k, k=1,2,……..L+1};Where t
1is minimum value and t
L+1is
maximum value
•�
′
=r
kif t
k<u<t
k+1
17
Quantization &#3627408482;
′

18. 18
Staircase Quantizer

19. Sampling & Quantization Response
19
LetusseetheeffectofquantizationonReconstructedSignal
Quantization Error = Quantized signal –Input signal

20. Quantization
20

21. Quantization
21

22. 22
Quantization

23. Quantization-Example
23

24. 24

25. 25

26. © 2002 R. C. Gonzalez & R. E. Woods
y (intensity values)
Generatingadigitalimage.(a)
Continuousimage.(b)A
scalinglinefromAtoBinthe
continuousimage,usedto
illustratetheconceptsof
samplingandquantization.(c)
samplingandquantization.(d)
Digitalscanline.
ab
cd
Sampling & Quantization
26

27. © 2002 R. C. Gonzalez & R. E. Woods
(a)Continuousimage
projectedontoasensorarray.
(b)Resultofimagesampling
andquantization.
ab
Sampling & Quantization
27

28. Sampling & Quantization
28

29. Dither
29
Ditherisanintentionallyappliedformofnoiseusedtorandomizethequantizationerror,preventinglarge-scale
patternssuchascolorbandinginimages

30. 30
Dither

31. Dithering
31

32. Sampling Quantization and Display
32

33. Neighborhood of Pixels
•Apixelpatlocation(x,y)hastwohorizontaland2-vertical
neighbors.
•Thesetof4-pixelsiscalled4-neighborsofp,N
4(p)
•Eachoftheseneighborsisataunitdistancefromp
•Ifpistheboundarypixelthenitwillhavelessnumberof
neighbor
33
(x-1,y)
(x,y-1)P(x,y)(x,y+1)
(x+1,y)

34. Diagonal Neighbors & 8-Neighbors
•A pixel p has 4 diagonal neighbors N
D(p)
•The points of N
4(p) and N
D(p) together are
called 8-neighbors of p.
•N
8(p)= N
4(p) U N
D(p)
•If p is a boundary pixels then both N
D(p) and
N
8(p) will have less number of pixels.
34
(x-1, y-1) (x-1, y+1)
P(x,y)
(x+1,y-1) (x+1,y+1)
(x-1, y-1)(x-1,y)(x-1, y+1)
(x,y-1)P(x,y)(x,y+1)
(x+1,y-1)(x+1,y)(x+1,y+1)
8-neighbors
diagonal neighbors

35. Connectivity of pixels
•Twopixelsaresaidtobeconnectediftheyareneighbors
–Theyareneighbors(N
4,N
D,N
8)and
–Theirpixel/intensityvalues(graylevels)aresimilar.
–Example:ForabinaryimageB,twopixelspandqwillbeconnectedifp
εN(q)orqεN(p)andintensityvaluesofpandqaresame.
–Connectivityconceptisveryusefulforestablishingobjectboundaries
–Definingimagecomponents/regionsetc.
35
(x-1,y)
(x,y-1)P(x,y)(x,y+1)
(x+1,y)
(x-1, y-1) (x-1, y+1)
P(x,y)
(x+1,y-1) (x+1,y+1)

36. Connectivity in more general way
•LetVisthesetofpixelvaluesusedtodefineconnectivityfortwo
pixelspointsp,qεV.Threetypesofconnectivityaredefined.
•4-connectivity—Pointsp,qεV&pεN
4(q)
•8-connectivity---Pointsp,qεV&pεN
8(q)
•M-connectivity(Mixedconnectivity)---p,qεVarem-connectedif
–qεN
4(p)OR
–qεN
D(p)andN
4(p)ΩN
4(q)=φ
–N
4(p)ΩN
4(q)------Setofpixelsthatare4-neighborsofbothpointspandq
andwhosevaluesarefromV.
36

37. Connectivity
•Mixed connectivity is a modification of 8-connectivity
–M-connectivity eliminates multiple path connections that often arise
with 8-connectivity.
–Ex: V={1}
4-connected 8-connected m-connected
–For gray scale image
V={59,60,61}
37
0 1 1
0 1 0
0 0 0
0 1 1
0 1 0
0 0 1
0 1 1
0 1 0
0 0 1
100 60 200 59
59 200 60 61
61 61 100 59
59 60 100 61

38. Adjacency
•Two pixels p and q are adjacent if they are connected
–4-adjacency—
–8-adjacency---
–m-adjacency---
•Dependingonthetypeofconnectivityused
•TwoimagesubsetsS
iandS
jareadjacentifpixelpεS
iandqεS
j
suchthatpandqareadjacent.
38

39. Adjacency example
39Disjoint connected components

40. Path
•Apathfromp(x,y)toq(s,t)isasequenceofdistinctpixels.
•Define(x
0,y
0),(x
1,y
1),……..(x
n,y
n)
where(x
0,y
0)=(x,y)and(x
n,y
n)=(s,t)
•(x
i,y
i)isadjacentto(x
i-1,y
i-1)for1≤i≤n
wherenisthelengthofpath.
•DefineV={1,2}
•Shortestpath=5
40

41. Connected Component
•Let??????∁Iand&#3627408477;,&#3627408478;∈??????
•ThenpisconnectedtoqinSifthereisapathfrompto
qconsistingentirelyofpixelsinS.
•Forany&#3627408477;∈??????,thesetofpixelsinSthatareconnected
topiscalledaconnectedcomponentofS.
•Soanytwopixelsofaconnectedcomponentsare
connectedtoeachother.
•Distinctconnectedcomponentsaredisjoint.
41

42. Connected Component Labeling
•Abilitytoassigndifferentlabelstovariousdisjoint
connectedcomponentsofanimage.
•Connectedcomponentslabellingisafundamentalstep
inautomatedimageanalysis.
•Shape,
•Area
•Boundary
•Shape/area/boundarybasedfeatures
42

43. Algorithm Steps
•Scanimagefromlefttorightandfromtoptobottom.
•Assume4-connectivity,&letpbeapixelatanystepinthescanning
process.
•Beforep,pointrandtarescanned.
•Let,
•l(p)=pixelvalueatpositionp.
•L(p)=Labelassignedtopixellocationp.
•Ifl(p)=0,movetonextscanningposition.
•Ifl(p)=1andl(r)=l(t)=0
•Thenassignanewlabeltopositionp.
•Ifl(p)=1andonlyoneofthetwoneighboris1
•Thenassignitslabeltop.
43

44. Connected Component Labeling
•If l(p) =1 and both r and t are 1’s, then
•If L(r)=L(t) and L(p)=L(r)
•If L(r) ≠L(t) then assign 1 to labels to p and make a note that the
two labels are equivalent.
•At the end of the scan all pixels with value 1 are labeled.
•Some labels are equivalent.
•During 2
nd
pass process equivalent pairs to form equivalence class.
•Assign a different label to each class.
•In the 2
nd
pass through the image replace each label by the label
assigned to its equivalence class.
44

45. Example
45
(1,2),(3,4), (1,5)
(1,2), (1,5)=1
(3,4)=3

46. Algorithm Demonstration
46

47. Connectivity
47

48. Distance measures
•Take 3-pixels at locations p, q and z
•P=(x,y); q=(s,t) and z=(u,v)
•D is a distance function or metric if
•D(p,q)≥0;
•If D(p,q)=0 if p=q
•D(p.q)=D(q,p)
•D(p,z)≤D(p,q)+D(q,z)
48

49. Euclidean Distance
•??????
??????&#3627408477;,&#3627408478;=[(&#3627408485;−&#3627408480;)
2
+(&#3627408486;−&#3627408481;)
2
]
1
2
•Set of points S={q|(D(p,q) ≤ r)} are the points contained in a
disc of radius r cantered at p.
49

50. •D
4distance or city-block distance or Manhattan Distance:
•D
4(p,q)=|x-s|+|y-t|
•Points having city block distance from p less than or equal to r
from diamond centered at p.
50
City-Block Distance

51. Chess board distance
•D
8distanceorchessboarddistanceisdefinedas
•D
8(p,q)=max(|x-s|,|y-t|)
•S={q|D
8(p,q)≤r}formasquarecenteredatp.
•PointswithD
8=1are8-neighborsofp.
51

52. 52

53. 53

54. 54
Distance Measure output

55. 55

56. Arithmetic/Logical Operation
•Following Arithmetic/logical operations between two pixels p
and q are used extensively.
•P+q;p-q; p*q p%qArithmetic operation
•AND OR; NOT Logical operation
•Logical operations are applied on binary images only.
56

57. Addition of two images
57

58. Addition of 2-images
58

59. Subtraction of two images
59

60. Subtraction of two images
60

61. Multiplying by a constant
61

62. Division of two images
62
DivingDCTcoefficientmatrixelementwise
bythequantizationmatrixandroundingto
nearestinteger.
Ex:round(-415/16)=round(-25.93)=26

63. Logical Operation:
Negative Operation (NOT(A))
63

64. Negative Operation
64

65. Negative Operation
65

66. Convolution operation
66
Z
1 Z
2 Z
3
Z
4 Z
5 Z
6
Z
7 Z
8 Z
9
W
1 W
2 W
3
W
4 W
5 W
6
W
7 W
8 W
9
Z
R=W
1Z
1+W
2Z
2+……..+W
9Z
9
෍
??????=1
9
&#3627408458;
??????&#3627408461;
??????
For averaging operation divide by N=9;

67. Results of Image Averaging operation
67
Avg= fspecial('average',[5 5]);

68. Results of Image Averaging operation
•Avg= fspecial('average',[3 3]; [5 5]);
68

69. Results of Median Filtered Image
69

70. Median Filtered Image
70

71. Neighborhood operations
•Various important operations can be implemented by proper
selection of coefficients W.
•Noise filtering
•Thinning
•Edge detection
•Image enhancement
•Etc..
71

72. Lecture-5-6
Basics Transformations & Perspective
Transformations
72

73. Contents
•Basic Transformations –Translation, Scaling and
Rotation in both 2D and 3D
•Inverse Transformations
•Perspective Transformation
•Inverse Perspective Transformation
73

74. 74

75. Translation operation
75

76. Matrix Representation of Translation
&#3627408485;
′
&#3627408486;
′=
10
01
&#3627408485;
&#3627408486;
+
&#3627408485;
0
&#3627408486;
0
•&#3627408485;
′
=&#3627408485;+&#3627408485;
0
•&#3627408486;
′
=&#3627408486;+&#3627408486;
0
76
Matrix Representation of Translation in single matrix form
&#3627408485;
′
&#3627408486;
′=
10&#3627408485;
0
01&#3627408486;
0
&#3627408485;
&#3627408486;
1
&#3627408485;
′
&#3627408486;
′
1
=
10 &#3627408485;
0
01 &#3627408486;
0
00 1
&#3627408485;
&#3627408486;
1
Symmetrical matrix Called
Unified expression

77. Translated Image
77
J = imtranslate(I,[15, 25]);

78. Translated Image
78
J = imtranslate(I,[35,45]);

79. Rotation
79

80. Rotation (Anticlockwise)
80
Given,P=(x,y)Theoriginalpointto
transform
Φ=Angleformbytheline(0,0)top.
Θ=TheanglebywhichP=(x,y)isrotated
abouttheoriginandnewP=P
’
=(x
’
,y
’
)
R=Lengthoftheline(0,0)toP.AlsoRisthe
radiusofthecircleofrotation

81. Rotation (Anticlockwise)
81

82. Rotation (Anticlockwise)
82

83. Rotation about arbitrary point (a,b)
83
=

84. Rotated Image
84

85. Scaling:
85

86. Scaled Image
86

87. Thanks
87