11.
Image Data Analytics
Jacobs University
Visualization and Computer Graphics Lab
Motivation
Images (and even videos) have become a popular data
format for storing information digitally.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 377
Motivation
Traditionally, scientific and medical imaging
techniques were considered.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 378
Motivation
Nowadays, photographs form the majority.
1 pixel
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 379
Image Analytics?
Similarity computation is difficult.
Similar images may look very different.
E.g., two photographs of cars may have completely different
colors and shapes.
Digital image processing allows for the detection of
features in the images.
Semantic queries on images is difficult without
metadata.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 380
Semantic gap
Image processing allows for the detection of regions
of certain properties (typically homogeneous regions).
Heuristics can be used to combine homogeneous
regions to larger structures.
Larger structures can be considered as low-level
semantics.
E.g., detect human hands.
The problem is to bridge the low-level semanstics to
high-level semantics as in queries:
E.g., show me all images, where presidents are shaking hands.
The gap between the low-level and high-level
semantics is called the semantic gap.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 381
11.1 Digital Image Processing
Jacobs University
Visualization and Computer Graphics Lab
Digital Image Processing
Image Morphological
Restoration Processing
Image
Segmentation
Enhancement
Image Object
Acquisition Recognition
Representation
Problem Domain
& Description
Colour Image Image
Processing Compression
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 383
Image Aquisition
Image Morphological
Restoration Processing
Image
Segmentation
Enhancement
Image Object
Acquisition Recognition
Representation
Problem Domain
& Description
Colour Image Image
Processing Compression
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 384
Image Enhancement
Image Morphological
Restoration Processing
Image
Segmentation
Enhancement
Image Object
Acquisition Recognition
Representation
Problem Domain
& Description
Colour Image Image
Processing Compression
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 385
Image Restoration
Image Morphological
Restoration Processing
Image
Segmentation
Enhancement
Image Object
Acquisition Recognition
Representation
Problem Domain
& Description
Colour Image Image
Processing Compression
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 386
Morphological Processing
Image Morphological
Restoration Processing
Image
Segmentation
Enhancement
Image Object
Acquisition Recognition
Representation
Problem Domain
& Description
Colour Image Image
Processing Compression
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 387
Segmentation
Image Morphological
Restoration Processing
Image
Segmentation
Enhancement
Image Object
Acquisition Recognition
Representation
Problem Domain
& Description
Colour Image Image
Processing Compression
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 388
Object Recognition
Image Morphological
Restoration Processing
Image
Segmentation
Enhancement
Image Object
Acquisition Recognition
Representation
Problem Domain
& Description
Colour Image Image
Processing Compression
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 389
Representation & Description
Image Morphological
Restoration Processing
Image
Segmentation
Enhancement
Image Object
Acquisition Recognition
Representation
Problem Domain
& Description
Colour Image Image
Processing Compression
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 390
Image Compression
Image Morphological
Restoration Processing
Image
Segmentation
Enhancement
Image Object
Acquisition Recognition
Representation
Problem Domain
& Description
Colour Image Image
Processing Compression
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 391
Colour Image Processing
Image Morphological
Restoration Processing
Image
Segmentation
Enhancement
Image Object
Acquisition Recognition
Representation
Problem Domain
& Description
Colour Image Image
Processing Compression
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 392
11.2 Image Segmentation
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 393
Definition
Image segmentation is the operation of partitioning
an image into a collection of connected sets of pixels.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 394
Definition
A segmentation is a partition of an image I into a set of
regions S satisfying the following conditions:
1. Partition covers the whole image.
2. No regions intersect.
3. Each region is homogeneous within itself.
4. Adjacent regions form no homogeneous region when
united.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 395
Region Growing
Region growing techniques start with one pixel of a
potential region and try to grow it by adding adjacent
pixels till the pixels being compared are too disimilar.
The first pixel selected can be just the first
unlabeled pixel in the image or a set of seed pixels
can be chosen from the image.
Usually a statistical test is used to decide which
pixels can be added to a region, e.g., threshold on
(N-1) * N 1/2
T = -------------- (y - X)2 / S 2
(N+1)
to decide whether pixel with intensity y is added,
where X denotes the mean, S standard deviation, and
N is the number of pixels in the region.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 396
Region Growing
Result:
image
segmentation
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 397
Clustering
Apply a clustering approach on the pixel intensities.
Histogram-based approaches try to automatically
split the range of the intensities by looking into
minima of the histogram.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 398
Clustering
We can use the clustering methods we have been
looking into.
For example, we can use k-means with a guessed
number of segments k.
There exist modifications to k-means that look into
local statistics to consider spatial distribution of
pixels.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 399
Clustering
Results for k-means:
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 400
Clustering
Graph cut algorithms are widely used.
Let G = (V,E) be a graph.
The vertices V represent the pixels.
Each edge (u,v) has a weight w(u,v) that represents
the similarity between u and v.
The goal is to partition the vertices into disjoint sets
with high similarity within each set and low similarity
across sets.
Graph G can be broken into 2 disjoint graphs by
removing edges that connect these sets.
The segmentation is obtained by finding minimal cuts
of G.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 401
Clustering
Graph cuts with normalized cut:
cut(A,B) = w(u,v).
uA, vB
cut(A, B) cut(A,B)
Ncut(A,B) = ------------- + ------------- asso(A,V) = w(u,t)
uA, tV
asso(A,V) asso(B,V)
A B
2 2 2
3 3
2
2 2 2 2 Ncut(A,B) = ------- + ------
1 4 3 1 2 21 16
2 2 3
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 402
Clustering
Graph cut results:
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 403
11.3 Image Collection Data Analytics
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 404
Image collections
Image segmentation helps to identify certain
features in the image.
They do not work perfectly.
However, if we are trying to perform a data analytics
approach on a collection of images, the data
segmentation results are only of use for low-level
semantics queries.
Is there a way to analyze a collection of images on a
higher level?
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 405
Data analytics
Assume that we can characterize an image by a
number of image descriptors, we can try to compute
similarities based on those descriptors.
Then, we can build a similarity (or distance) matrix of
pairwise (dis-)similarities of images.
Based on the similarity (or distance) matrix, we can
apply the data analytics approaches:
Cluster approaches,
Classification approaches,
Interactive visual analysis based on MDS projections.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 406
Data analytics example
Corel data set includes 1,000 photographs on 10
different themes, described by 150 dimensions (SIFT
descriptors).
The Medical data set is of magnetic resonance (MRI)
images and has 540 objects and 28 dimensions
(Fourier descriptors and energies derived from
histograms, plus mean intensity and standard
deviation).
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 407
Projection-based visualization of labeled data
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 408
11.4 Image Descriptors
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 409
Image descriptors
Fourier analysis
Wavelet analysis
SIFT features
Color statistics
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 410
Image Transforms
Many times, image processing tasks are best
performed in a domain other than the spatial
domain.
Key steps
(1) Transform the image
(2) Carry the task(s) in the transformed domain.
(3) Apply inverse transform to return to the spatial domain.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 411
Fourier Series Theorem
Any periodic function f(t) can be expressed as a
weighted sum (infinite) of sine and cosine
functions of varying frequency:
is called the fundamental frequency
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 412
Fourier Series
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 413
Continuous Fourier Transform (FT)
Transforms a signal (i.e., function) from the spatial
(x) domain to the frequency (u) domain.
Jacobs University
where
Visualization and Computer Graphics Lab
Data Analytics 414
Example: Removing undesirable frequencies
noisy signal frequencies
To remove certain remove high reconstructed
frequencies signal
frequencies, set their
corresponding F(u)
coefficients to zero!
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 415
How do frequencies show up in an image?
Low frequencies correspond to slowly varying pixel
intensities (e.g., continuous surface).
High frequencies correspond to quickly varying pixel
intensities (e.g., edges)
Original Image Low-passed
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 416
Example of noise reduction using FT
Input Spectrum
image (frequency
domain)
Band-
Output
reject
image
filter
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 417
Extending FT in 2D
Forward FT
Inverse FT
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 418
Discrete Fourier Transform
Assume that f(x,y) is M x N.
Forward DFT
Inverse DFT:
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 419
Extending DFT to 2D
2D cos/sin functions
Interpretation:
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 420
Magnitude and Phase of DFT
only phase
only magnitude phase (woman) phase (rectangle)
magnitude (rectangle) magnitude (woman)
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 421
Wavelet transform
An alternative to Fourier transforms are wavelet
transforms.
They have the advantage that they represent the
image at multiple levels of details.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 422
B-spline representation
coarsening
details
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 423
B-spline representation
Haar wavelet transform
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 424
Haar wavelets
Basis function
Wavelet function
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 425
Haar wavelets
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 426
Multiresolution representation
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 427
Multiresolution representation
Object is represented as a sequence of resolutions.
The resolutions are called levels (levels of detail,
LOD)
The differences are called detail coefficients.
The levels build a multiresolution hierarchy:
The level is the base level.
The base level does not need to be represented by a
regular mesh. All levels use then semi-regular meshes.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 428
Multiresolution representation with Haar wavelets
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 429
2D Haar wavelet transform
2D basis and wavelet functions are tensor products
of 1D basis and wavelet functions.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 430
2D Haar wavelet transform
Basis:
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 431
2D Haar wavelet transform
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 432
2D Haar wavelet transform
Alternative construction:
Use 2D basis function
and three 2D wavelet functions
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 433
2D Haar wavelet transform
Basis:
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 434
2D Haar wavelet transform
Advantage: One obtains undistorted
downscaled versions of the 2D image.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 435
2D wavelet transform in RGB space
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 436
Image compression
Haar wavelets:
100% 21% 4% 1%
Error: 0% 5% 10% 15%
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 437
Image compression
JPEG 2000: Cohen-Daubechies-Feauveau wavelets
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 438
Image compression
JPEG 2000: lossy compression leads to blurring.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 439
SIFT features
The scale-invariant feature transform (SIFT) is
another transform that can be used to describe
image characteristics.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 440
Canonical Frames
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 441
Multi-Scale Oriented Patches
Extract oriented patches at multiple scales
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 442
Application: Image Stitching
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 443
Multi-Scale Oriented Patches
1. Detect an interesting patch with an interest operator.
Patches are translation invariant.
2. Determine its dominant orientation.
3. Rotate the patch so that the dominant orientation
points upward. This makes the patches rotation
invariant.
4. Do this at multiple scales, converting them all to one
scale through sampling.
5. Convert to illumination invariant form
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 444
Idea of SIFT
Image content is transformed into local feature
coordinates that are invariant to translation, rotation,
scale, and other imaging parameters
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 445
Claimed Advantages of SIFT
Locality: features are local, so robust to occlusion
and clutter (no prior segmentation)
Distinctiveness: individual features can be matched
to a large database of objects
Quantity: many features can be generated for even
small objects
Efficiency: close to real-time performance
Extensibility: can easily be extended to wide range of
differing feature types, with each adding robustness
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 446
Overall Procedure at a High Level
1. Scale-space extrema detection
Search over multiple scales and image locations.
2. Keypoint localization
Fit a model to determine location and scale.
Select keypoints based on a measure of stability.
3. Orientation assignment
Compute best orientation(s) for each keypoint region.
4. Keypoint description
Use local image gradients at selected scale and rotation
to describe each keypoint region.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 447
Using SIFT for Matching Objects
Jacobs University
Visualization and Computer Graphics Lab
11/15/2016 448
Data Analytics 448
Color statistics
We have been looking at greyscale images
(application: medical imaging data).
We have been using histograms on color distribution.
However, photographs are typically color images.
How can we process color statistics?
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 449
11.5 Color Models
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 450
Electromagnetic spectrum
purple blue green yellow orange red
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 451
Visible light spectrum
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 452
Relative sensitivity of human eye
The ability of the human eye to distinguish colors is
based on the sensitivity in the retina to light of
different wavelength.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 453
Tristimulus
The retina contains 3 types of receptor cells, which is
called tristimulus.
The receptors are most responsive to light of
wavelengths 420nm, 534nm, and 564nm.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 454
RGB color model
Idea:
Use three wavelengths R, G, and B that reflect
monochromatic light and represent a tristimulus.
Other colors are obtained by combining/mixing the
three components R, G, and B.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 455
RGB color model
Implementation:
Choose three colors:
R = red (700 nm)
G = green (546.1 nm)
B = blue (435.8 nm)
Arrange them in a 3D Cartesian coordinate system
such that
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 456
RGB color model
This model allows the generation of colors c with
where .
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 457
RGB color cube
All colors c that can be generated are represented by
the unit cube in the 3D Cartesian coordinate system.
green
yellow
cyan
white
ey
gr
black red
blue magenta
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 458
Additive color scheme
RGB color model is additive, i.e., adding colors makes
the resulting color brighter.
Application: color monitors.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 459
Composition example
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 460
Compositing in the RGB color cube
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 461
Caveat
It is often believed that the RGB color model
reflects the tristimulus of the human eye.
This is wrong.
In particular, the large wavelength of the human eyes
tristimulus is 565 nm, which is not red but rather
yellow-green.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 462
Choice of RGB wavelength
The choice of the wavelength in the RGB model has
historical and practical reasons.
When first monitors were developed, generating
monochromatic light was a difficult task.
The chosen wavelength were those that could be
generated most easily.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 463
Reconstruction of visible spectral light
In order to reconstruct all wavelengths of the visible
spectral light, we have to add the R, G, and B
components with the following weighting factors:
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 464
Reconstruction of visible spectral light
The negative values indicate that not all visible colors
can be produced with the RGB color model.
Nevertheless, close approximations can be achieved.
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 465
11.6 Assignment
Jacobs University
Visualization and Computer Graphics Lab
Assignment 9
Download and extract the archive of an image collection data set from
[Link]
The data set consists of around 5,000 images of different buildings in
Oxford. If processing of the entire data set takes too long, you may use
a subset, but make sure the subset contains images of different
buildings. Then, convert the color images to grayscale images.
Approach 1: Interpreting the grayscale images as 1D vectors of pixel
intensities, run a clustering algorithm with an appropriate distance
metric. What do the clusters represent?
Approach 2: Transform the greyscale images into the space of SIFT
descriptors. How many dimensions does this space have?
Hint: You may use the Python bindings of OpenCV. Here is a tutorial:
[Link]
py_feature2d/py_sift_intro/py_sift_intro.html.
Apply a clustering approach to the SIFT descriptors and visualise the
result in an MDS projection (in 2D). What do the clusters represent?
p.t.o
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 467
Assignment 9
Approach 3: Exchange the order of the two analysis steps in
Approach 2, i.e., first project the SIFT descriptors to a 2D space
using an MDS approach and then cluster the 2D points using the
same clustering approach as above. Again, visualise the result. What
do the discovered clusters represent?
How do the three approaches compare?
Jacobs University
Visualization and Computer Graphics Lab
Data Analytics 468