Chapter 2 Point Operations
Definition of point operations
• A function that assigns a grey level to an output pixel of an output image based solely on corresponding pixel of input image. That is,
where
– A(i,j) and B(i,j) are grey level of input and output images at (i,j)
– f(.) is a function
• Also, called gray-scale transformation (GST).
2
Why point operations?
Contrast enhancement
• Features of interest may occupy a narrow range of the gray scale.
• Point operation is applied to expand the contrast so that features of interest occupy a wider range of displayed gray levels. Examples include:
– linear point operations
– nonlinear point operations: logarithmic and power law
– window and level contrast enhancement
– histogram equalization and matching
3
2.1 Common Point Operations
4
Linear Point Operation
where
DB = grey level in output image B.
DA = grey level in input image A.
a = constant called gain. b = constant called offset.
slope = a
5
Linear Point Operation
Effect of b: b affects brightness of image by shifting grey levels.
• e.g.,a=1(nogain)andb=-70.
Before After
Question: What is the effect of a positive b?
6
Linear Point Operation
Effect of a: a affects contrast and brightness. e.g., a = 1.46 = 255/175, b = 0
Before After
a > 1: increases contrast and brightness
0 < a < 1: decreases contrast and brightness.
7
A note on imshow in Python
• imshow maps the minimum to black and maximum to white by default.
• The images Coins and Coins2 (1.3Coins) plotted by imshow appear the same.
• Increase of brightness can be seen when we explicitly specify:
– vmin = 0 (value 0 mapped to black)
– vmax = 255 (value 255 mapped to white)
8
Nonlinear Transformations
• Logarithmic
– log/inverse log
• Power law
– nth power/nth root
9
Log Transformation
where is a positive constant.
• Maps a narrow range of low input gray levels into a wider range of output values
• The inverse log transformation performs the opposite transformation
10
Log Transformation Example
• Log functions are particularly useful when the input grey level values may have an extremely large range of values
• Here, the Fourier transform of an image is put through a log transform to reveal more detail.
11
Power-Law (Gamma) Transformation
where and are positive constants.
• •
Map narrow range of dark input to wider
range of output
Map wide range of dark input to narrow
range of output
12
Power-Law Example with
MRI of a fractured human spine (circled)
𝛾 0.4
𝛾 0.3
𝛾 0.6
13
Power-Law Example with
Aerial photo of a runway
𝛾4 𝛾5
𝛾3
14
Gamma Correction for Display
•
Power-law relationship for monitor display
•
Perform gamma
•
Result:
. .
Original Image
Input intensity Display value
correction before sending
the image to the monitor:
.
.
15
Python implementation
16
Window and Level
• Interactive contrast enhancement technique
• Expands contrast of pixels having gray levels within user-selected “window” (W)
• Window is centered at “level” (L)
• Clips values outside window
17
•
•
Window and Level in Python
• Most pixels have an intensity between 90 and 140.
• Use the
rescale_intensity
function to expand the range 90 to 140 to the entire dynamic range.
18
2.2 Histogram Processing
19
Definition of histogram
A function that shows, for each gray level (gl), the number of pixels in the image with that gray level.
uint8 image
20
Generation of histogram in Python
• D(0)=0,D(1)=1,...D(255)=255foranuint8 image.
• H(0) = Number of pixels in im with gl D(0) (i.e., 0)
• H(1) = Number of pixels in im with gl D(1) (i.e., 1)
• H(2) = Number of pixels in im with gl D(2) (i.e., 2)
• ......
• H(255)=NumberofpixelsinimwithglD(255) (i.e., 255)
21
Relationship among input, output histograms and point operation
• Output histogram depends on the input histogram and the point operation applied.
• Goal: Derive expression for output histogram, HB, in terms of (i) point operation, f, and (ii) input histogram, HA.
• Why?
– This relation is essential in the design of point operation to achieve desired histogram.
– Applied later in histogram equalization and
matching.
22
Relationship among input, output histograms and point operation
• Derivation is more convenient to be performed with continuous functions (i.e., HA, HB and f are all continuous in derivation).
• HA and HB are always discrete in practical implementation.
• Thus, we need an understanding of the subtle differences between continuous and discrete histograms.
23
Definition of histogram: Revisit
Histogram is a function that shows, for each gray level,
(i) Discrete:
area (expressed in pixels) in the image with that gray level (gl).
(ii) Continuous:
area per unit gray level. Here, histogram is a density function. To obtain area between a given interval, integration is needed.
Example 1: Number of pixels with gl between interval 128 to 130
Discrete Continuous
Example 2: Number of pixels with gl between interval 0 to 255
(whole range) (i.e., you are counting the total number of pixels in an image)
Discrete Continuous
where N is the total number of pixel in the image. 24
Normalized histogram: Probability density function
• Some textbooks normalizes H by the total number of pixels:
• p has the property of the probability density function (pdf):
• This normalized histogram will be denoted by p and referred to as probability density function or pdf hereafter in this course.
25
Expression for output histogram, HB • Given information:
• •
2. Histogram of input image, HA.
Goal: Derive an expression for the output
1. Point operation, f, that maps gl of an input image, A, to an output image, B, i.e.,
where DA and DB are respectively the gl of an input and an output pixel.
histogram, HB, in terms of HA and f. Assumption: f-1, i.e. inverse of f, exists.
26
0 255
Expression for output histogram, HB
• DA is mapped to DB
• DA + ΔDA is mapped to DB + ΔDB
• All gray levels between
DA and DA + ΔDA are mapped toDB andDB +ΔDB
0 255
0
255 27
Expression for output histogram, HB
• The number of pixels between DA and DA + ΔDA in input image equals the number of pixels between DB and DB + ΔDB:
28
Linear point operation revisited
• Given:
– Input histogram, HA.
– DB = f(DA) = aDA + b (i.e., linear point op)
• What is the output histogram, HB?
In general, For linear op,
29
Linear point operation revisited
For linear op,
Effect of b: b > 0 shifts histogram to right, b < 0 shifts histogram to left.
Effect of a:
Broaden histogram → Increase contrast
Amplitude reduced
• Area under histogram = Total number of pixels in image = constant
Histogram becomes narrower
→ contrast decreased
Amplitude increased
30
Linear point operation: Example
• b=-70,a=1.0 Before
After
Histogram shifted
to left (i.e., darker end)
31
Linear point operation: Example
• a=1.50,b=0.0 Before
After
• a > 1 increases contrast (broader histogram) and brightness.
• Amplitude did not reduce because of discretized gray levels
(see notes on next slide).
32
Continuous vs. Discrete Gray-Level
• Continuous case: [77.5, 78.5) has constant density of 5 pixels/gray level in HA. i.e., there are 5 pixels with gray level in the interval [77.5, 78.5)
• After point operation 1.5*Da + b, this group of 5 pixels have gray level in the interval [116.25, 117.75). Density in HB is 5 pixels/1.5 gray level = 3.33 pixels/gray level. That is density in HB is reduced by a factor of a (=1.5) compared to HA.
• Discrete case: HA(78) = 5 pixels. The whole group of 5 pixels is mapped to 117 (i.e., HB(117) = 5 pixels). No reduction in amplitude.
• Moral: Results obtained in continuous gray level domain can sometimes only be approximated in practical implementation because in practice, gray level domain is discretized. Results in continuous gray level domain does give us an idea that contrast and brightness are increased though, which are still very useful.
33
Summary for 2.2
• Defined “point operation”.
• Introduced histogram for image with continuous grey levels.
• Derived expression for output histogram given input histogram and point operation. This expression is essential for understanding of next chapter.
• Applied the derived expression for the case of linear point operation.
34
2.3 Histogram Equalization
35
Definition
• Histogram
equalization: A point operation that maps an input into output image such that there are equal number of pixels at each grey level in output.
• Used for contrast enhancement.
36
Why histogram equalization?
• Imageswithgood contrast:
– make full use of the entire range of possible grey levels.
– have intensity spread out over the entire grey level range.
• Ideally, we should spread out the intensity uniformly over the entire grey scale to achieve good contrast.
• Thisishistogram
equalization.
[Courtesy of Gozalez and Woods: Digital Image Processing]
37
Derivation in continuous domain
• Recall from Sec. 2.2, given the input histogram, HA, and the point operation, f, the output histogram, HB, can be expressed as:
• Now,
……(2)
……..(1)
38
Derivation in continuous domain
• Substituting eq. (2) into (1) gives • Integrating both sides yields
……(3)
39
Derivation in continuous domain
• So, what is f(0)?
• Requirement: Range of output grey levels
should be the same as input grey levels, both should be from 0 to Dm, i.e.,
• RangeoffisDm
• For Requirement to be satisfied, f(0) must be
set to 0.
• From Eq. (3), we obtain:
40
Point operation for histogram equalization
• Thepointoperationfthatflattenstheinput histogram, HA, is:
• Recall: pdf of Image A, pA, is the histogram normalized by the number of pixel. (i.e., HA/A0 here).
• The cumulative distribution function (cdf) of Image A, PA, is defined as:
• Eq. (4) can be written in terms of PA:
……(4)
41
Example
• Derive f that will flatten H1 where:
where Dm = max gray level and A0 = total number of pixels
42
Discrete implementation
• The discretized formula for implementation purpose is:
where Dm = max. gray level and A0 = total number of pixels
• e.g., Consider equalizing the following 4-bit image using the above formula:
43
Implementation Example
DA HA(DA) f(DA) Discretized f(DA)
00000 10000 20000 30000 40000
5 16023 6 17940 7 8659 8 15209 9 10125
16023
33963
42622
57831
67956
69385
69578
69708
69818
69840
69840
3.4414 3 7.2945 7 9.1542 9
10 1429 11 193 12 130 13 110 14 22 15 0
12.4207 12 14.5954 15 14.9023 15 14.9437 15 14.9716 15 14.9953 15
15 15 15 15
44
Implementation Example
• Dm = 15, A0 = 69840
Steps:
1. Obtain histogram, HA(DA), of input image.
2. For each input gray level, DA, compute the cumulative sum
3. For each DA, scale sum by Dm/A0, giving f(DA)
4. Discretize f(DA).
5. Replace each gray level DA in the input
image by the corresponding value of f(DA).
45
Implementation Example
Before After
46
Example
Before
After
• Resulting image spans a fuller range of the grey scale.
• However, resulting histogram is not completely flat, unlike the continuous case.
• Discrete implementation can only approximate the ideal case of uniform distribution.
47
Why histogram is not completely flat in discrete case?
• Consider this example: 25 students of the class scored a grade of 4 in DSE Math exam and another 25 students of the class scored 5. Determine the rank of each student with the student scoring the highest ranks no. 50 and that who scores the lowest ranks no. 1.
• This is basically an equalization problem in which you would expect each student has a unique rank.
• In practice, a unique rank cannot be assigned because students with the same grade cannot be ranked differently.
48
Summary of 2.3
• Defined “histogram equalization”
• Developed formulae for histogram equalization:
– Continuous case: – Discrete case:
• Discrete implementation
49
Implementation in Python
Note the range is from 0 to 1
Computed pdf without multiplication of 𝐷
50
Implementation in Python
Note that display is the same as the previous slide, as imshow maps max to white and min to black
Range becomes 0 to 255
Multiply output of equalize_hist by 255 Convert the numpy image to uint8
51
2.4 Histogram specification (matching)
52
Definition of histogram specification
• Point operation that maps an input image A into an output image C with a user-specified histogram.
53
Why histogram specification?
• Improve display (contrast and brightness)
• Preprocessing step before comparison of images.
• Comparison with equalization:
– More general than histogram equalization since output histogram is not restricted to be flat.
– Allow development of interactive enhancement technique: user can draw desired histogram to improve results
54
An application of histogram specification
• We wish to check whether a circuit board (image 1) has any deflect by comparing it with a template (image 2).
1: Manufactured 2: Template
55
An application of histogram specification
• Compute absolute difference image
• Binarize: 1 if absolute difference is non- zero, 0 otherwise.
Location where difference occurs (potential defect)
56
An application of histogram specification
• What if the overall brightness of image 1 is different from that of image 2?
1: Manufactured
• Difference image is white everywhere because there is a difference in the brightness of all pixels.
2: Template
• One solution would be to match the histograms of the two images before performing the subtraction.
57
Derivation in continuous domain
• Given information:
1. Input image A. Its associated histogram HA can be computed.
2. Desired histogram for output image C, HC.
• Goal: Derive a point operation, DC = f(DA), that maps the input image A into an output image, C, which has the user-specified
histogram, H
.
C
Goal
58
Derivation in continuous domain
Define the following:
• An intermediate image B with a flat histogram, HB.
• the point op, f1, that transforms image A into image B.
• the point op, f2, that transforms image C into image B.
Approach: f1 and f2 can be readily obtained from Sec. 2.3. We just apply f1 to flatten histogram and then f2-1 to convert flattened histogram to user-specified histogram. Desired DC = f(DA) is just DC=f2-1f1(DA).
59
Derivation in continuous domain
• Derivation:
– f1 equalizes Image A and produces Image B:
– f2 equalizes Image C and produces Image B,
– Recall: PA and PC are the cdfs of Images A and C respectively (see p. 9)
– The point operation, DC=f(DA), we need is just
60
Example (continuous tone): 1
• Digital subtraction angiography (DSA)
– (a) Pre-contrast: image obtained before contrast agent was injected into the arteries.
– (b) Post-contrast: image obtained after contrast agent was injected. Artery appears dark.
– (c) = (a) – (b): Only artery is displayed. Background is removed.
Courtesy of http://commons.wikimedia.org/wiki/File:DsaImages.jpg#mediaviewer/File:DsaImages.jpg
61
Example (continuous tone): 2
• Inthisexample,radiologistsuseDSAtodetermine whether coronary bypass surgery is required.
• Problemsinexposureanddevelopmentoftwo films → Direct comparison/subtraction inconclusive.
• Patientistooweaktoundergoanother angiography.
• Given:Thehistogramofbothfilmshavea Rayleigh distribution (below) with DM = 63 and:
– Image 1 (Pre-contrast): α = 16 – Image 2 (Post-contrast): α = 24
62
Example (continuous tone): 3
• Questions:Givepointoperationsto:
a) flatten Image 1
b) flatten Image 2
c) make Image 2 histogram match that of Image 1
• Solution:Thepointopforequalization: • ForRayleighdistribution,
63
Example (continuous tone): 4
• Solution: (con’t)
What is A0?
Results:
64
Discrete implementation: Example
Given a 3-bit gray-level image A with the following histogram:
Design point operation to match it to the following histogram:
DA
HA(DA) 1028 3544 5023 3201 1867 734 604 383
DC
HC(DC)
0 1 2 3 4 5 6 7
0 0
1 0
2 1638 3 4096 4 4916 5 4096 6 1638 7 0
65
Discrete implementation: Step 1
1. Equalize the input image (Image A) to get the intermediate image B:
DA HA(DA) DB 0 1028 0 1 3544 2 2 5023 4 3 3201 5 4 1867 6 5 734 7 6 604 7 7 383 7
66
Discrete implementation: Step 2
2. Equalize the image with desired histogram (Image C) to get the intermediate image B:
DC HC(DC) DB
000 100 2 1638 1 3 4096 2 4 4916 5 5 4096 6 6 1638 7 707
67
Rule for inverse calculation
• Case I: (DB, DC) is a unique pair – easy to map.
• Case II: One DB value is associated with more than one DC value
– map to lower DC value
• Case III: DB value does not appear in the
table
– use the DC value paired with the closest DB
value
– If two or more DB values are equally close,
then use the smaller DC value.
68
Discrete implementation: Step 3
With the point op DB =
f2(DC) defined in Step 2, function DC=f2-1(DB) reproduced below:
DC DB = f2(Dc) DB DC = f2-1(DB)
0000 1012 2123 3233 4544 5654 6765 7776
Calculate the inverse
69
Discrete implementation: Step 3
Case I: Unique pair
• e.g.,DB =1→DC =2
Case II: One DB mapped to multiple DC
• e.g.,DB=0
• Map to low DC
• i.e.,DB =0→DC =0(instead ofDC =1)
Case III: DB does not appear in table
• e.g.,DB =3or4
• Use the DB value that is closest
– DB =3→closesttoDB =2→DC =3
– DB =4→closesttoDB =5→DC =4
70
Discrete implementation: Step 4
The desired point operation DC=f(DA)=f2-1f1(DA) mapping from input image A to output image C is:
f1
f2-1
DA DB DC
000 123 244 354 465 576 676 776
4. For each pixel in Image A, replace the grey level DA with DC according to the above table.
71
f
Implementation in Python
72
Summary of 2.4
• Defined histogram specification (matching)
• Described applications
• Derived point operation achieving histogram specification in continuous domain
• Implemented derived point operation in discrete domain
73
Python examples
• Please have a good understanding of the skimage_histogram.ipynb file in demo3.zip
• Functions in skimage.exposure
adjust_gamma(image[, …]) adjust_log(image[, gain, inv]) adjust_sigmoid(image[, …])
Performs Gamma Correction on the input image.
cumulative_distribution(image) equalize_adapthist(image[, …])
Return cumulative distribution function (cdf) for the given image.
equalize_hist(image[, …]) histogram(image[, nbins, …]) is_low_contrast(image[, …])
Contrast Limited Adaptive Histogram Equalization (CLAHE). Return image after histogram equalization.
Return histogram of image.
Determine if an image is low contrast.
match_histograms(image, …) rescale_intensity(image[, …])
Adjust an image so that its cumulative histogram matches that of another.
Performs Logarithmic correction on the input image.
Performs Sigmoid Correction on the input image.
Return image after stretching or shrinking its intensity levels
74