Fundamentals of Computer Vision

Dr. Shouvik Chakraborty

September 22, 2025

Contents

1 Introduction to Computer Vision 3

1.1 The Effortless Illusion of Sight . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Defining Computer Vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Applications of Computer Vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 A Brief History of Computer Vision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.5 Why Vision is Hard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.5.1 The Complexity of the Input: Ambient Light . . . . . . . . . . . . . . . . . . . . . 7
1.5.2 The Complexity of the Output: Scene Properties vs. Light . . . . . . . . . . . . . 7
1.6 A Simple Image Formation Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6.1 Parallel (Orthographic) Projection . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6.2 Perspective Projection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.7 Looking at Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.7.1 Looking at Individual Pixels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7.2 The More You Look, the More You See . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7.3 Tree Shadows and Image Formation . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.7.4 Horizontal or Vertical . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.7.5 Motion Blur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7.6 Looking at Raindrops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.7.7 How Do You Know Something Is Wet? . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.7.8 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2 Image Formation 17
2.1 Lighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.1 Diffuse (Lambertian) Reflection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.2 Specular (Phong) Reflection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2 The Pinhole Camera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.1 The Basic Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.2.2 Formalizing the Geometry: Coordinate Systems . . . . . . . . . . . . . . . . . . . . 19
2.2.3 The Perspective Projection Equations . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.4 From Camera Coordinates to Pixel Coordinates . . . . . . . . . . . . . . . . . . . . 20
2.2.5 Building Your Own Pinhole Camera . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3 Lenses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.1 The Thin Lens Equation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.2 Circle of Confusion and Depth of Field . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.3 Aperture and the F-Number . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.4 Real Lenses and Aberrations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4 Image Sensing and Acquisition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.1 Image Acquisition Using a Single Sensing Element . . . . . . . . . . . . . . . . . . 25
2.4.2 Image Acquisition Using Sensor Strips . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.3 Image Acquisition Using Sensor Arrays . . . . . . . . . . . . . . . . . . . . . . . . 25
2.5 The Digital Camera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.5.1 The Image Sensing Pipeline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.5.2 Sensor Technology: CCD vs. CMOS . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5.3 Key Factors Affecting Image Quality . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.6 Sampling and Aliasing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.6.1 Basic Concepts in Sampling and Quantization . . . . . . . . . . . . . . . . . . . . . 30

1
 2.6.2 What is Aliasing? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.6.3 Aliasing in Real Images: Moiré Patterns . . . . . . . . . . . . . . . . . . . . . . . . 32
2.7 Color . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.7.1 Additive and Subtractive Color Models . . . . . . . . . . . . . . . . . . . . . . . . 33
2.8 Compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.8.1 Measuring Compression Quality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3 Image Processing 38
3.1 Representing an Image for a Computer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1.1 Image as a Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.1.2 Image as a Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2 Image Processing Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2.1 Point Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.2.2 Histogram Shape and Image Characteristics . . . . . . . . . . . . . . . . . . . . . . 43
3.2.3 Histogram Equilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2.4 Local Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2.5 Global Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3 Spatial Filtering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.1 The Mechanics of Linear Spatial Filtering . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.2 Correlation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.3 Convolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.3.4 Usage and Properties of Correlation and Convolution . . . . . . . . . . . . . . . . 49
3.4 Edge Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.4.1 Classification of Edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.4.2 Gradient Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4.3 Edge Detection Using First-order Derivatives . . . . . . . . . . . . . . . . . . . . . 53
3.4.4 Edge Detection from Gradients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.5 Derivatives and Edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.6 Laplacian (∇2 ) as Edge Detector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.7 Discrete Laplacian Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.8 Effects of Noise and the Solution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.9 Derivative of Gaussian and Laplacian of Gaussian . . . . . . . . . . . . . . . . . . . . . . . 57
3.9.1 Derivative of Gaussian (∇(nσ )) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
3.9.2 Laplacian of Gaussian (∇2 nσ or ∇2 G) . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.10 Comparing Gradient and Laplacian Operators . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.11 Canny Edge Detector . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3.11.1 The Effect of Scale (σ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.12 Corner Detection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.12.1 Analyzing Image Gradients . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.12.2 Distribution of Image Gradients . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.12.3 Fitting an Ellipse to the Gradient Distribution . . . . . . . . . . . . . . . . . . . . 62
3.12.4 Interpreting the Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.12.5 The Harris Corner Response Function . . . . . . . . . . . . . . . . . . . . . . . . . 64
3.12.6 Non-Maximum Suppression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.13 Hough Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.13.1 Line Detection: The Core Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
3.13.2 The Line Detection Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.13.3 A Better Parameterization: Polar Coordinates . . . . . . . . . . . . . . . . . . . . 67
3.13.4 Generalization to Other Shapes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3.14 SIFT: Scale-Invariant Feature Transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.14.1 What is an Interesting Point? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.14.2 Detecting Blobs using Scale-Space . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.14.3 The SIFT Detector: Implementation with DoG . . . . . . . . . . . . . . . . . . . . 72
3.14.4 The SIFT Descriptor: Creating a Robust Signature . . . . . . . . . . . . . . . . . . 72
3.14.5 Matching SIFT Descriptors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.14.6 SIFT in Practice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

2
Chapter 1

Introduction to Computer Vision

1.1 The Effortless Illusion of Sight

Let’s start with a simple observation: every day, when you wake up, you open your eyes and you see.
You see without any effort, and you do not get tired after a few hours from seeing too much. The same
happens with all the other senses. With them, you perceive the world around you: you hear the birds
or the car noises, you smell breakfast and feel the touch of the sheets, and that keeps going on and on
until the end of the day. The most surprising fact is that your brain is continuously solving very complex
tasks still unmatched by any artificial system.
The apparent simplicity of perceiving the world around us produces the false intuition that it will
be easy to build a machine capable of seeing as humans do. This intuition has been proven wrong time
and again. In 1966, Seymour Papert and Marvin Minsky, two pioneers of artificial intelligence, launched
the so-called Summer Vision Project. They believed that in just a two-month period, and with a team
of just ten engineers, they could build a computer system that could identify objects in an image. More
than five decades later, after an untold number of researcher hours, published papers, and billions in
funding, basic object recognition is still not considered a solved problem.

We may have the sense that vision should, in fact, be a relatively simple problem. After all, we
open our eyes every morning and we just ”see.” We seemingly effortlessly reason about and navigate our
environment, recognize our friends and family, find our car keys, and solve a myriad of tasks that today’s
most sophisticated computer vision systems still struggle with.
The field of computer vision is largely dedicated to building computer systems that mimic this marvel
that is the human visual system. Its goal is to allow a machine to reason about, navigate through, and
understand the physical three-dimensional world from one or more images. To do this, the system must
understand how human vision works. Human vision is capable of extracting information about the world
around us using only the light that reflects off surfaces in the direction of our eyes. The light that reaches
our eyes does not tell us what object we are looking at; it only gives us information about the amount
of light reaching our eye from each direction in space. Our brains have to translate the information

3
collected by millions of photoreceptors in our retinas into an interpretation of the world in front of us.
What we ”see” is different than the raw light that reaches our eyes, as visual illusions prove to us.
The study of vision is, by its nature, an interdisciplinary study involving many disciplines:
• Physics and Optics

• Psychology and Neuroscience

• Biology
• Signal and Image Processing

• Linear Algebra, Probability, and Numerical Methods

• Computer Science and Machine Learning
The techniques introduced in this field are not exclusive to images and possess the versatility to
be adapted for the processing of various other signal types. Applications of computer vision are now
widespread and include everything from building fully autonomous vehicles to automatically detecting
and classifying cancer in CT scans, facial recognition that allows you to unlock your phone, and aug-
mented reality filters that add bunny ears to your video. To accomplish these feats, we must first start by
understanding the geometry of image formation and then develop a set of mathematical and numerical
tools to analyze and reason about images, with the goal of getting us closer to building computer vision
systems that can mimic our own visual system.

1.2 Defining Computer Vision

At its core, Computer Vision is a field that automates and endows computing frameworks with the ability
to interpret images and videos as humans do. As a sub-topic of Artificial Intelligence, its primary goal
is to enable a machine to answer complex, and sometimes subjective, questions about visual data. For
example, given an image of a cluttered desk, a system should be able to answer ”Where is the gluestick?”
or given an unusual piece of art, it should be able to reason ”What is wrong with this image?”
Over the decades, researchers have offered several formal definitions that capture the essence of the
field:
• Ballard & Brown (1982): “The construction of explicit, meaningful descriptions of physical
objects from images.”
• Trucco & Verri (1998): “Computing properties of the 3D world from one or more digital images.”
• Sockman & Shapiro (2001): “To make useful decisions about real physical objects and scenes
based on sensed images.”

The pursuit of this goal is inherently interdisciplinary, standing at the intersection of several domains
including Machine Learning, Artificial Intelligence, Signal Processing, Physics, and Neurobiology.
However, the task is exceptionally difficult. Many practical use cases are inverse model applications;
that is, we must model the real world (its shape, lighting, objects, and interactions) from incomplete and
noisy information captured in a 2D image. This is the opposite of a forward model, used in computer
graphics, where a 3D world is used to generate a 2D image. The challenge is compounded by high-
dimensional data, which brings heavy computational requirements, and the fact that no complete, holistic
model of the human visual system exists to guide the process.

1.3 Applications of Computer Vision

The ”why” of computer vision is answered by its vast and growing number of applications, which are
transforming nearly every major industry. Some of the most prominent categories include:
• Autonomous Vehicles: Enabling cars, drones, and robots to perceive and navigate their envi-
ronment.

• Surveillance: Monitoring public and private spaces for security and safety.

4
 • Factory Automation: Using machine vision for quality control, assembly, and robotics.
• Medical Imaging: Assisting doctors in the analysis of X-rays, CT scans, and other medical
imagery to detect diseases.
• Human-Computer Interaction: Allowing humans to interact with computers through gestures
and motion.
• Visual Effects: Integrating computer-generated imagery into live-action footage for movies and
games.
Beyond these broad categories, computer vision powers a diverse array of specific solutions across
many sectors:
• Retail and Retail Security: Including checkout-free stores like Amazon Go, Virtual Try-on
technology, and theft prevention systems like StopLift.
• Healthcare: With tools such as the Blood Loss Detector for surgical monitoring and DermLens
for skin cancer screening.
• Agriculture: Utilizing platforms like SlantRange for crop analytics and Cainthus for livestock
facial recognition.
• Banking and Finance: Powering features like Mobile Deposit and enabling Insurance Risk
Profiling from property imagery.
• Remote Sensing: For applications in Land Use Understanding and AI-driven Forestry Modeling.
• Structural Health Monitoring: In areas like Oilwell Inspection, Drone-based Bridge Inspection,
and 3D Reconstruction of infrastructure.
• Document Understanding: Involving technologies like Optical Character Recognition and in-
telligent Robotic Process Automation.
• Tele- and Social Media: Through automated Image Understanding and Brand Exposure Ana-
lytics.
• Augmented Reality: For enterprise solutions like TechSee Visual Support and AR-guided Ware-
house and Enterprise Management.

1.4 A Brief History of Computer Vision

The journey of computer vision from a theoretical concept to a world-changing technology is marked
by decades of biological inspiration, foundational algorithms, and pivotal breakthroughs in computing.
The narrative is not just one of engineering, but of a deep, iterative process of understanding how both
machines and humans see.

1950s-1960s: Biological Inspiration and Early Attempts

The conceptual origins of computer vision are deeply intertwined with neuroscience. In 1959, neurophys-
iologists David Hubel and Torsten Wiesel conducted a landmark experiment on a cat, discovering that
specific neurons in the visual cortex fired in response to simple patterns like lines at specific orientations.
[1] They identified ”simple cells” that responded to basic features and ”complex cells” that aggregated
the input from simple cells. This hierarchical model of vision provided a powerful biological blueprint
that would influence the field for decades to come. [1]
The first attempts to translate these ideas into a computational model began in the 1960s. In
1963, Lawrence Roberts, often considered the ”father of computer vision,” wrote his Ph.D. thesis on
”Machine Perception of Three-Dimensional Solids.” His work demonstrated how a computer could derive
3D information, such as shape and orientation, from a 2D image by identifying edges and objects. [1]
This early success fueled a wave of optimism, culminating in the now-famous 1966 ”Summer Vision
Project” at MIT. Researchers, believing the problem was straightforward, assigned a group of students
the task of solving machine vision over a single summer. [1] The project’s inability to achieve this goal
served as a crucial reality check, revealing the profound, unexpected complexity of sight.

5
1970s-1980s: Foundational Theories and Early Neural Networks
The 1970s shifted focus toward building a more structured, theoretical foundation. David Marr, a
visionary neuroscientist at MIT, proposed that vision is a hierarchical process that operates on three
levels of understanding: the computational theory (what the problem is), the representation and
algorithm (how to solve it), and the hardware implementation (the physical means of doing so). He
argued that a system first builds a ”primal sketch” of an image from edges and features, then a ”2.5D
sketch” that includes depth and orientation, and finally a full 3D model. [1]
In the 1980s, the influence of Hubel and Wiesel’s work re-emerged in a computational model. Japanese
computer scientist Kunihiko Fukushima developed the Neocognitron, an early artificial neural network
designed for character recognition. [1] The Neocognitron mimicked the visual cortex with layers of ”S-
cells” (simple) and ”C-cells” (complex) that could learn to detect patterns in a hierarchical fashion. It
is now widely regarded as the direct ancestor of modern Convolutional Neural Networks (CNNs). [1]

1990s: The First Practical CNNs

Building on the Neocognitron, Yann LeCun and his colleagues at Bell Labs made a series of critical
advancements throughout the 1990s. They combined Fukushima’s layered architecture with the back-
propagation algorithm, creating a trainable model. This work culminated in the creation of LeNet-5 in
1998, a sophisticated 7-layer CNN that was deployed to successfully recognize handwritten zip codes on
checks for the U.S. Postal Service. [1] This was one of the first commercially successful applications of
neural networks and proved their real-world viability.

2000s: The Rise of Data and Real-Time Detection

The 2000s were characterized by two key developments that set the stage for the modern era. First,
in 2001, Paul Viola and Michael Jones developed a highly efficient algorithm that could detect faces
in images in real-time. The Viola-Jones framework did not use deep learning but relied on Haar-like
features and a clever ”attentional cascade” to rapidly discard non-face regions of an image. [1] It was a
landmark achievement that was soon integrated into consumer cameras and software everywhere.
Second was the rise of large-scale, annotated datasets. The PASCAL VOC challenge, starting in
2005, provided a standardized benchmark for object classification. This was followed by the launch of
the ImageNet project in 2009, an unprecedented database containing millions of high-resolution, labeled
images. ImageNet provided the massive amount of training data necessary for deep neural networks to
finally reveal their true potential. [1]

2010s: The Deep Learning Revolution

The trajectory of computer vision changed forever in 2012 at the annual ImageNet Large Scale Visual
Recognition Challenge (ILSVRC). A deep convolutional neural network named AlexNet, created by
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton, achieved an error rate of 15.3
Its resounding success was a watershed moment that triggered the deep learning revolution. In the
years that followed, research exploded, and new, even deeper architectures were introduced, including
ZFNet (2013), GoogLeNet/Inception (2014), VGGNet (2014), and Microsoft’s ResNet (2015). ResNet’s
introduction of ”residual connections” finally allowed for the training of networks hundreds or even thou-
sands of layers deep. By 2015, the top models were outperforming humans on the ImageNet challenge.
[1] Computer vision became ubiquitous, powering countless applications and cementing deep learning as
the dominant paradigm in the field.

1.5 Why Vision is Hard

It is difficult to say exactly what makes understanding the mechanisms of vision hard, as we do not
have a full solution yet [2]. In this section, we will explore two aspects that make vision one of the
most challenging problems in artificial intelligence: the complex structure of the input signal and the
interpretive nature of the desired output.
What is the goal of vision? Our eyes are sensors, and for an agent that navigates and solves tasks
in the world, the role of the sensor is to provide relevant information for solving the task. In computer
vision, we often study visual perception from a disembodied perspective where there is no agent and no

6
specific task. This perspective makes the study of vision difficult, as the relevance of information is not
always clear.

1.5.1 The Complexity of the Input: Ambient Light

From a light source, a dense array of light rays emerges in all directions. Before these rays reach the eye,
they interact with the objects in the world. Let’s consider a single ray emerging from a light source (using
a simple geometric interpretation). If the light ray is not directed toward the eye, this ray will strike
some surface in the world and, as a result, a new set of rays will be emitted in many directions. This
process continues, producing more and more interactions and filling the space with light. The observer,
situated in the middle of this space, will sense only a subset of the light rays that happen to strike the
eye. As a result of this complex pattern of interactions, even a single light source can form a complex
image.
Figure 1.1 shows pictures taken when illuminating a complex scene with a laser pointer, which
approximates the image produced by a single, narrow beam of light. The resulting images show the
complexity of the interactions between the different surfaces. The sum of the contribution of all the light
rays emitted by a light source will give rise to a natural-looking picture.

Figure 1.1: (a) Scene illuminated with a ceiling lamp. (b-c) Two images obtained by illuminating a scene
with a laser pointer (the red line indicates the direction of the ray).

Despite the complexity of this ambient light (a term coined by James J. Gibson [3])—with its multiple
reflections, shadows, and specular surfaces—our visual system has no problem interpreting this scene,
even if it is among the first things we see after waking up.

1.5.2 The Complexity of the Output: Scene Properties vs. Light

Vision is not a deterministic process that analyzes input images independently of our internal state. Even
when two people look at the same thing, they can have different visual awareness. Our visual experience
is greatly influenced by what we know, what we are doing, and what we expect to see.
If the goal of vision were simply to measure the light intensity coming from a particular direction
(like a photometer), then the problem would be easy. However, the goal of vision is to provide an
interpretation of the world in terms of ”meaningful” surfaces, objects, and materials. This is hard
because most of the information about the 3D world is lost in the 2D projection, and the visual system
must make a number of assumptions to recover the desired information. It is also hard because our
understanding of what is ”relevant” for an observer is incomplete. The human visual system constantly
tries to recover the scenes that are the cause of the images it receives, as illustrated in Figure 1.2.

1. In Figure 1.2(a), we see a red square occluding a smaller blue square. But why do we see a square
and not an L-shaped figure? Our brain assumes that squares are typical and that occlusions are
common, making an occluded square the most natural interpretation.
2. Figure 1.2(b) shows the ”turning tables illusion” by Roger Shepard [5]. In this illusion, both table
tops have the same shape and size. However, our visual system insists on interpreting them as 3D
objects, giving the strong impression that the left table is longer and narrower than the right one.
This perception cannot be shut down, even when we know it is an illusion.

7
Figure 1.2: We cannot shut down the automatic mechanisms that interpret these images not as light
patterns but as pictures of real three-dimensional (3D) scenes. (a) Occluding figures, (b) R. Shepard’s
turning tables illusion, and (c) E. Adelson’s Checkershadow illusion.

3. Figure 1.2(c) shows the ”checkershadow illusion” by Edward Adelson [6]. Here, the squares marked
A and B have the exact same pixel intensity. But our visual system automatically corrects for the
shadow, trying to measure the true surface reflectance. As a result, we perceive square B as being
much lighter than square A.

When looking at a 2D picture, we automatically interpret it as a 3D scene if the right cues are present.
The ultimate goal of vision is to provide the observer with information relevant to understanding the
outside world and to enable them to solve other tasks. Tasks within computer vision include the following:
• Detecting changes in the environment
• Motion estimation
• Object recognition and localization
• Recognizing materials
• Reading text and visual symbols
• Building 3D models from images
• Finding free space to move
• Recognizing other people and their behavior
• Deciding if food is in good condition
Not all of these tasks are at the same level. Some seem to require a great deal of external knowledge,
while others seem solvable from the images alone.

1.6 A Simple Image Formation Model

To understand how a three-dimensional world is captured in a two-dimensional image, we must first look
at the process of projection. The projection model determines how points in 3D space are mapped onto
a 2D image plane. There are two primary models that describe this process: parallel (orthographic)
projection and perspective projection.

1.6.1 Parallel (Orthographic) Projection

One of the simplest forms of projection is parallel, or orthographic, projection. In this image formation
model, it is assumed that light rays travel parallel to each other and perpendicular to the camera’s
image plane. This model is a good approximation for imaging objects from a great distance, where the
curvature of light rays becomes negligible.
This type of projection produces images with distinct characteristics:
• Objects do not change size as they move closer to or farther from the camera.

8
 Figure 1.3: Perspective Projection (Top) and Parallel Projection (Bottom)

• Parallel lines in the 3D world remain parallel in the 2D image.

• While geometrically simple, it does not produce realistic-looking images for scenes with significant
depth.

1.6.2 Perspective Projection

In perspective projection, the center of projection (often modeled as a single point, the ”pinhole”) is at
a finite distance from the projection plane. This model accurately describes how the human eye and
standard cameras perceive the world.
This projection produces realistic views but does not preserve the relative proportions of an object’s
dimensions across depth. Its key properties include:

• Projections of distant objects appear smaller than projections of objects of the same size that are
closer to the projection plane. This effect is known as foreshortening.
• Parallel lines in the 3D world appear to converge to a ”vanishing point” in the 2D image, as shown
in the figure above.

• This is the standard model used for rendering realistic scenes in computer graphics and is the
foundation for recovering 3D structure in computer vision.

1.7 Looking at Images

Vision is about solving an amazing problem: Can we build a system capable of perceiving its surrounding
world using only the information available in the small number of electromagnetic waves that fall into the
observer’s sensor (eye or camera), after accidentally bouncing off the objects surrounding the observer?
How is it possible to sense the world and its three-dimensional (3D) structure without touching it? It
seems quite likely that if humans did not have the sense of vision, we would think that solving this
problem is impossible.
The goal of this section is to present vision not as an engineering problem that we want to solve, but
as a set of scientific questions that we want to answer. We want to understand how it is that our visual
system can interpret the world the way it does. We want to explain what components of an image can
be used to infer certain properties of the world. We want to know what questions about the world can
be answered by just looking at an object with the light that reaches our eyes.
In this section we will not answer any of those questions; instead, we will use images to motivate a
set of questions that vision scientists and computer vision engineers have been studying for many years.
The goal of this chapter is to help you ask questions about how you perceive the world around you.

9
1.7.1 Looking at Individual Pixels
Before we build systems that can see, it is good to learn to look at images and to pay attention to
individual pixels. The image in Figure 1.4 is a tiny image with just 32 × 32 pixels. What is the
minimum number of pixels needed to form a recognizable image? The answer depends on the image. It
is possible to create visually recognizable images with very few pixels [2].

Figure 1.4: A tiny image with 32 × 32 color pixels. Despite the very low resolution, we can still recognize
most of its content. Source: Original image created with Dall-E, and downsampled with Photoshop.

It is so small that we can actually look at each single pixel and think about how it is that we can
make sense of it. For instance, let’s look at the pixel in row 13 counting from the bottom, and column
12 counting from the left. That pixel corresponds to a dark gray pixel, which is near a couple of other
pixels with similar intensity, surrounded by a set of white pixels. That pixel seems to be a pen, but how
do we know what it is? The pen is barely three pixels long and one pixel wide. How can that provide
enough information?
Recognition of the meaning of that pixel cannot come just from the intensity of that pixel or the
few pixels nearby. There are way too many possible situations in which different objects in the world
could map to a similar set of pixel intensities. Instead, it is the whole image and the context of the pen
that provides the necessary information to recognize it. Taken in isolation, those pixels are impossible
to recognize, as shown in Figure 1.5.

Figure 1.5: Small image patches from Figure 1.4 shown in isolation. It is difficult to recognize image
patches outside their natural context.

10
1.7.2 The More You Look, the More You See
Visual perception cannot be formulated as a simple input-output function over predefined domains.
Vision is a dynamical system, even when looking at a static image. The longer you look at an image,
the more details you see and the better you understand the scene. Just look at the image shown in
Figure 1.6 and try to write down everything you see down to the smallest detail.

Figure 1.6: A street in Paris. Is everything fine in this picture?

But this feeling of unlimited and effortless understanding of a picture is also an illusion. Do you truly
understand everything you see? For instance, are you sure you can make sense of all the chair legs in
Figure 1.6? In fact, this image has been manipulated so that some of the legs do not correspond to any
chair. As the visual cognitive load increases, we are more likely to make judgment mistakes.
As you look around the image, notice that each patch you look at is actually a small photo in its own
right. In fact, a big image like this contains thousands of tiny images within it (Figure 1.7). A common
trick in computer vision is to take a method that was developed for processing a dataset and instead
apply it to the set of patches in an image, or vice versa.

Figure 1.7: Each picture contains lots of images.

1.7.3 Tree Shadows and Image Formation

When walking under the shadow of a tree on a bright sunny day when the sun is right above us (Fig-
ure 1.8[left]), we can see how some light rays get through the holes left between leaves, creating spots on
the floor (Figure 1.8[right]).
But something is a bit odd about the shape of the bright spots. We would expect them to have
irregular shapes, matching the openings between the leaves. Instead, the spots appear to be circular
and of similar size. This observation puzzled Aristotle. As a hint, Figure 1.9 shows the shadow of leaves
during a solar eclipse.
The tiny holes between the leaves of a tree create a multitude of natural pinhole cameras. When
these openings are small enough, the shape of the projected spot of light is dominated by the shape of

11
Figure 1.8: The shadow of this tree on a normal day projects dozens of pictures of the sun on the ground.

Figure 1.9: During an eclipse, the shadow of the tree contains many copies of the crescent sun.

the sun. This is why we see circular spots on a normal day and crescent-shaped spots during an eclipse.

1.7.4 Horizontal or Vertical

Looking at the previous picture, how do you know you are looking at the ground? Look at the two
drawings in Figure 1.10. The drawing on the left appears to be a horizontal surface, while the one on the
right looks like a vertical surface. The only difference is a 90-degree rotation. The perception is driven
by the location of the vanishing points where the parallel lines seem to converge. The orientation of the
horizon line (which connects the vanishing points) signals to our brain whether the surface is a floor or
a wall.

12
Figure 1.10: Line drawings. The one on the left seems to correspond to a horizontal surface while the
one on the right looks like a vertical surface.

1.7.5 Motion Blur

When we take a picture from a moving car, the image often appears blurred (Figure 1.11). This is
because the camera’s sensor collects light over a period of time while the car is moving. The resulting
picture is an average of several translated copies of the scene. Note that not all objects are equally
blurry; distant objects remain sharp while nearby objects appear very blurry. The amount of blur is
related to the car’s speed, the exposure time, and the distance of each object from the camera.

Figure 1.11: Picture of Paris taken from a moving car.

1.7.6 Looking at Raindrops

When it rains, every raindrop on a window refracts a panorama of the scene around it (Figure 1.12).
You are seeing not just one photo, but hundreds of images of the scene, each from a slightly different

13
angle. This is the principle behind a light field camera, which uses an array of tiny lenses instead of
raindrops. By capturing what a scene looks like from hundreds of viewing angles, these cameras can
perform interesting tricks, like triangulating depth and synthetically refocusing an image after it has
been taken.

Figure 1.12: A naturally occurring light field camera. This picture of raindrops on a window contains
hundreds of tiny images of the scene. The images to the right are zoomed-in raindrops from the photo
on the left.

1.7.7 How Do You Know Something Is Wet?

Our visual system recognizes not just objects, but also materials. We can often tell if something is wet
or not without touching it (Figure 1.13). Why does sand look darker when it is wet? Does everything
look darker when wet? How can we distinguish parts of the sand that are dark because they are wet
from those that are dark because they are in shadow? These are the kinds of subtle question that a
complete theory of vision must address.

1.7.8 Concluding Remarks

Your brain is like a detective looking at all the clues that reveal what the world is made of and how we
recognize them. There are many things that we see every day that we recognize by the way they look,
and yet we seldom ask ourselves why they look that way. Why does the sky appear blue? Why does the
moon always look the same? Why do hot things get redder?

Review Questions
1. What was the overly optimistic goal of the 1966 “Summer Vision Project,” and what did its failure
demonstrate?
2. According to the text, what is a key visual characteristic of perspective projection that makes
images appear realistic?
3. What real-world problem was the LeNet-5 network successfully deployed to solve in the 1990s,
proving the viability of CNNs?

14
Figure 1.13: Why does wet sand look dark? The answer to this question is interesting, but not as much
as the question itself.

4. The text describes raindrops on a window as a “naturally occurring light field camera.” What
basic principle do they share with an actual light field camera?

5. According to Ballard & Brown’s (1982) definition, what is the goal of computer vision?
6. Explain the difference between an inverse model (used in vision) and a forward model (used in
graphics).
7. Explain what the “checkershadow illusion” (Figure 3) demonstrates about the human visual sys-
tem’s goal. Why do we perceive squares A and B as having different shades even though they have
the same pixel intensity?
8. Describe the key findings from Hubel and Wiesel’s experiments with cats and explain how this
biological discovery influenced the hierarchical structure of Kunihiko Fukushima’s Neocognitron.
9. Using the concept of a natural pinhole camera, explain why the spots of light on the ground under
a tree are circular on a normal day but become crescent-shaped during a solar eclipse.
10. In a photo taken from a moving car (Figure 11), objects at different distances from the camera
show varying amounts of motion blur. Explain the relationship between an object’s distance and
the amount of blur it exhibits.

15
Bibliography

[1] Saha, S. (2017). A Brief History of Computer Vision and Convolutional Neural Networks.
Hacker Noon. Retrieved from [Link]
and-convolutional-neural-networks-8fe8aacc79f3
[2] Lopes, A. (2017). Recognizing an Image with Just a Few Pixels. Proceedings of the IEEE Conference
on Computer Vision and Pattern Recognition Workshops.

[3] Minnaert, M. (1937). Light and Color in the Outdoors.

16
Chapter 2

Image Formation

Before any analysis or interpretation can occur, a computer vision system must first capture a repre-
sentation of the three-dimensional world in the form of a two-dimensional digital image. This chapter
delves into the fundamental process of image formation, tracing the journey of light from its source to
its final digital representation as a grid of pixels. Understanding this physical and geometric process is
essential, as the properties of the final image are direct consequences of the principles that govern its
creation [1, 2].

2.1 Lighting
Visible light is electromagnetic radiation, but for many imaging applications, it is helpful to use the
abstraction of a light ray. A light ray describes the radiation heading in a particular direction and is
specified by its position, direction, and intensity as a function of wavelength. When a light ray strikes a
surface, it reflects. The properties of this outgoing light are determined by the bidirectional reflection
distribution function (BRDF), which describes the surface’s appearance 2.1. The general form of

Figure 2.1: Why does wet sand look dark? The answer to this question is interesting, but not as much
as the question itself.

the BRDF states that the outgoing light power, ℓout , is a function of the incoming light, ℓin , the surface
normal, n, and the incoming and outgoing directions, p and q:
ℓout = F (ℓin , n, p, q) (2.1)
In practice, we often use simplified models to describe two main components of reflection: diffuse and
specular.

2.1.1 Diffuse (Lambertian) Reflection

A Lambertian surface is an ideal diffuse reflector, which provides a good model for matte or non-glossy
surfaces like chalk or flat paint. The key characteristic of a Lambertian surface is that it scatters incoming
light equally in all directions. As a result, its brightness appears the same regardless of the viewing angle.
The brightness of the surface depends only on the angle between the incoming light direction p and
the surface normal n. The model is defined by the surface reflectance or albedo, denoted by a:
ℓout = aℓin (n · p) (2.2)

17
2.1.2 Specular (Phong) Reflection
A specular reflection is a mirror-like reflection that is highly dependent on the viewing angle. It creates
the bright highlights we see on shiny objects like polished metal or plastic.
A widely used model that combines both diffuse and specular components is the Phong reflec-
tion model. It assumes that the light reflected from a surface has three components: (1) an ambient
component, (2) a diffuse (Lambertian) component, and (3) a specular component.
The specular component, ℓPhong spec , is strongest along the direction of perfect reflection, r, and
creates a highlight whose size is controlled by the parameter α:

ℓPhong spec = ks (r · q)α ℓin (2.3)

where ks is a constant and the direction of maximum reflection r is given by:

r = 2(p · n)n − p (2.4)

Figure 2.2 compares the Lambertian and Phong models with a real photograph. The Phong model,
which includes a specular highlight, appears much more realistic for a shiny sphere.

(a) Lambertian (b) Phong (c) Photograph

Figure 2.2: A comparison of reflection models for a sphere under two-source illumination. The Lamber-
tian model (a) is purely diffuse. The Phong model (b) adds a specular highlight, making it appear more
like the real photograph (c).

In general, surface reflection behaves linearly: the reflection from the sum of two light sources is the
sum of the reflections from the individual sources. To associate this reflected light with surfaces in the
world, we need to know which light rays came from which direction. That requires that we form an
image.

2.2 The Pinhole Camera

The simplest possible device that can form an image is the pinhole camera. It is the theoretical
foundation upon which the geometry of nearly all modern cameras is built.

2.2.1 The Basic Principle

A pinhole camera requires only three components: a light-tight box, a tiny hole (the pinhole or aperture)
on one side, and a projection surface (or film) on the opposite side.
The principle behind it is that light travels in straight lines. As shown in Figure 2.3, for any given
point on the projection surface, the only light that can reach it must travel in a straight line from a point
in the outside world through the tiny pinhole. This one-to-one mapping between points in the scene and
points on the projection surface is what allows an image to be formed. Because the light rays cross at
the pinhole, the resulting image is inverted.
The size of the pinhole is critical. A very small pinhole ensures that light rays from a single point in
the scene land on a very small area of the projection surface, creating a sharp but dim image. A larger
pinhole lets in more light, creating a brighter image, but light rays from the same scene point can now
strike a wider area, making the image blurry.

18
Figure 2.3: The geometry of a pinhole camera. Light rays from the scene pass through a single small
hole, forming an inverted image on the projection wall inside the camera.

2.2.2 Formalizing the Geometry: Coordinate Systems

To describe the image formation process mathematically, we need to define a set of coordinate systems,
as illustrated in Figure 2.4.

Figure 2.4: The three primary coordinate systems used in the pinhole camera model: the 3D world
coordinates, the 2D camera coordinates on the virtual image plane, and the 2D pixel-based image
coordinates.

• World Coordinates (X, Y, Z): This is a 3D coordinate system fixed in the world. We use it
to define the location of any point P = (X, Y, Z) in the real scene. By convention, the Z-axis is
perpendicular to the camera’s front plane.
• Camera Coordinates (x, y): This is a 2D coordinate system on the projection plane. To simplify
the math, it’s common to use a virtual image plane, which is placed in front of the pinhole at
a distance f , known as the focal length. This is a mathematical convenience that allows us to
work with an upright, non-inverted image. The coordinates of the projected point are p = (x, y).
• Image Coordinates (n, m): This is the final coordinate system of the digital image, measured in
pixels. The origin of this system is typically in the top-left corner of the image. An affine transform
is used to convert the metric camera coordinates (x, y) into the pixel coordinates (n, m).

2.2.3 The Perspective Projection Equations

The relationship between a 3D world point P = (X, Y, Z) and its 2D projection p = (x, y) on the virtual
image plane can be derived using similar triangles, as shown in Figure 2.6.

19
Figure 2.5: The three primary coordinate systems used in the pinhole camera model: the 3D world
coordinates, the 2D camera coordinates on the virtual image plane, and the 2D pixel-based image
coordinates.

Figure 2.6: Derivation of the perspective projection equations using similar triangles. The ratio of
corresponding sides of the two triangles (one in the 3D world and one inside the camera) gives the
relationship between the coordinates.

From the geometry of the similar triangles, we get the following fundamental relations, known as the
perspective projection equations:
X
x=f (2.5)
Z
Y
y=f (2.6)
Z
These two equations are the mathematical heart of perspective. They tell us that the projected
coordinate of a point is inversely proportional to its depth (Z). This is why objects appear smaller
as they get farther away—as Z increases, x and y decrease. This principle applies not just to pinhole
cameras, but to most lens-based cameras and to the human visual system as well.

2.2.4 From Camera Coordinates to Pixel Coordinates

The final step is to relate the camera coordinates (x, y), which are in real-world units (like millimeters),
to the final pixel coordinates (n, m). This is done via a simple transformation:

n = −ax x + cx and m = ay y + cy (2.7)

20
where ax and ay are scaling factors that relate the camera’s metric units to pixels, and (cx , cy ) is the pixel
location of the camera’s optical axis (the image center). The negative sign on ax accounts for potential
flips in the coordinate system definition between the camera and image sensor.

2.2.5 Building Your Own Pinhole Camera

Making a pinhole camera is a simple and effective way to build intuition for the image formation process.
As shown in Figure 2.7, a basic camera can be constructed from a paper bag, some newspaper to block
stray light, and a white piece of paper to act as the projection screen. This simple setup allows one
to directly observe the effects of changing the distance between the pinhole and the projection plane,
providing a tangible connection to the theory.

Figure 2.7: Instructions for creating a simple pinhole camera from a grocery bag. This exercise provides
a practical understanding of how an inverted image is formed.

2.3 Lenses
While pinhole cameras can form good images, they suffer from a serious drawback: the images are very
dim because not much light passes through the small pinhole to the sensing plane of the pinhole camera.
As shown in Figure 2.8, one can try to let in more light by making the pinhole aperture bigger. However,
that allows light from many different positions to land on a given position at the sensor plane, resulting
in a bright but blurry image. Putting a lens in the larger aperture can give the best of both worlds,
capturing more light while redirecting the light rays entering the camera so that each sensor plane position
maps to just one surface point, creating a focused image on the sensor plane. For many applications,
it suffices to treat the lens as an ideal pinhole that simply projects all rays through a common center

21
of projection. A lens is an optical device that focuses light, gathering many rays from a single point in

Figure 2.8: Change in brightness/sharpness of Pin-Hole Camera

the scene and converging them onto a single point on the image sensor. For many applications, we can
simplify a complex camera lens to a thin lens model. This model is the foundation for understanding
focus, exposure, and depth of field.

2.3.1 The Thin Lens Equation

The fundamental relationship between an object, the lens, and the focused image is described by the
thin lens equation. It connects the distance from the lens to the object (zo ), the distance from the lens
to the sensor where a sharp image is formed (zi ), and a core property of the lens itself, its focal length
(f ).

Figure 2.9: A diagram of the thin lens model. An object at distance zo is brought into focus at a distance
zi behind the lens. If the image plane is moved, the point becomes a blurry circle of confusion, c.

The relationship is given by:

1 1 1
+ = (2.8)
zo zi f
Easy Explanation: This equation tells you exactly where to place the camera’s sensor (zi ) to get a
sharp image of an object at a specific distance (zo ), given a lens with a fixed focal length (f ). If an
object is ”in focus,” it means these three values perfectly satisfy the equation. A special case is when an
object is infinitely far away (zo → ∞); in this case, the image forms exactly at the focal length (zi = f ).

22
2.3.2 Circle of Confusion and Depth of Field
In reality, a photograph captures more than a single point in space. What happens to objects that are
not at the perfect focus distance zo ?

• Circle of Confusion (CoC): When an object is out of focus, the light rays from it do not converge
to a perfect point on the sensor. Instead, they form a small, blurry disc. This disc is called the
circle of confusion. As shown in Figure 2.9, the farther an object is from the plane of perfect
focus, the larger its circle of confusion becomes.
• Depth of Field (DOF): Our eyes cannot distinguish a very small circle of confusion from a
perfect point. This leads to the concept of Depth of Field. The DOF is the range of distances in a
scene—in front of and behind the main subject—where objects still appear acceptably sharp. This
”acceptable sharpness” simply means their circle of confusion is too small for our eyes to notice
the blur.

2.3.3 Aperture and the F-Number

The brightness of an image and the depth of field are both controlled by the aperture, which is the
opening in the lens that lets light pass through. We control the size of this opening using the f-number
(or f-stop).

Figure 2.10: Depth of field indicators on real camera lenses. The aperture ring (f-stops) and focus ring
work together to control what parts of the scene are in focus.

The f-number, denoted as N , is defined as the ratio of the lens’s focal length f to the diameter of its
aperture d:
f
N= (2.9)
d
Easy Explanation: This equation reveals a simple but crucial inverse relationship.
• A small f-number (e.g., f/1.8) means the aperture diameter d is large. This lets in a lot of light
but creates a very shallow depth of field (only a small zone is in focus).

• A large f-number (e.g., f/16) means the aperture diameter d is small. This lets in less light but
creates a very deep depth of field (much more of the scene appears sharp).

Figure 2.11: Effect of f number in real lenses.

23
 On a camera lens, you will see f-numbers like f/1.4, f/2, f/2.8, f/4, and so on. Each step in this
sequence (a ”full stop”) corresponds to halving the area of the aperture, which means halving the
amount of light reaching the sensor.

2.3.4 Real Lenses and Aberrations

Of course, the thin lens model is an idealization. Real lenses are made from multiple glass elements to
correct for various optical aberrations—imperfections that can cause blurriness or distortion. These
include issues like spherical aberration (where rays hitting the edge of a lens focus differently than rays
hitting the center) and chromatic aberration (where different colors of light bend at slightly different
angles). Nonetheless, the simple models discussed here provide the essential foundation for understanding
how any camera works. Two of the most common effects are chromatic aberration and vignetting.

Chromatic Aberration
Because the index of refraction for glass varies slightly with the wavelength (color) of light, a simple
lens will bend different colors by slightly different amounts. This phenomenon is called chromatic
aberration.

Figure 2.12: An illustration of chromatic aberration. Light of different wavelengths (e.g., red and blue)
is focused at slightly different distances, leading to a loss of focus and color fringing.

As shown in Figure 2.12, this causes light of different colors to focus at slightly different points. The
practical result in a photograph is a noticeable color fringing, which often appears as purple or green
halos along high-contrast edges. This aberration has two components: a blur caused by the different
focal planes, and a geometric distortion caused by the different magnifications for each color.
To reduce chromatic and other kinds of aberrations, modern photographic lenses are not single pieces
of glass. They are compound lenses made of different glass elements, often with specialized coatings.
This complexity means they can no longer be modeled as having a single nodal point (like a pinhole).
Instead, they have a front nodal point (where rays appear to enter the lens) and a rear nodal point
(where they appear to exit on their way to the sensor).

Vignetting
Another common property of real-world lenses is vignetting, which is the tendency for the brightness
of an image to gradually fall off from the center towards the corners. This darkening effect is usually
caused by a combination of two physical phenomena.
The first cause is geometric. As illustrated in Figure 2.13, for parts of the scene that are off-axis
(away from the center of the view), the circular aperture of the lens appears as a smaller ellipse from
that angle. This foreshortening of the aperture physically blocks some of the light, preventing it from
reaching the sensor.
The second cause relates to the physics of light. Light rays traveling from an object to the corners
of the sensor have to travel a slightly longer distance than rays traveling to the center. This causes the
light to be less intense when it arrives, further contributing to the darkening. Together, these effects are
why images, especially those taken with wide-angle lenses at a large aperture (a small f-number), are
often significantly darker at their edges than in the center.

24
Figure 2.13: The geometry of vignetting. An off-axis part of the scene is imaged by light rays that pass
through the lens at an angle, reducing the amount of light that reaches the sensor.

2.4 Image Sensing and Acquisition

Most images of interest are generated by the combination of an ”illumination” source and the reflection
or absorption of energy from that source by a ”scene”. The terms illumination and scene are used
broadly. For instance, the illumination could be from an X-ray system, and the scene could be a human
brain. The energy is sensed and converted into a digital image.

2.4.1 Image Acquisition Using a Single Sensing Element

A 2-D image can be generated from a single sensor. A familiar example of a single sensor is a photodiode,
whose voltage output is proportional to the incident light intensity.
• Mechanism: To generate a two-dimensional image, there must be relative displacement in both
the x- and y-directions between the sensor and the area to be imaged.
• Application: High-precision scanning often uses this method. For example, a film negative can
be mounted on a rotating drum to provide displacement in one dimension, while the sensor moves
on a lead screw in the perpendicular direction to provide displacement in the other, as shown in
Figure 2.15.

• Trade-offs: This method is inexpensive and can produce very high-resolution images because the
mechanical motion can be controlled with high precision. However, its main disadvantages are that
it is slow and not easily portable.

2.4.2 Image Acquisition Using Sensor Strips

A more common geometry is the in-line sensor strip (or line sensor).
• Mechanism: The sensor strip, composed of many sensors in a line, provides imaging elements in
one direction. Motion perpendicular to the strip provides the second dimension to create a 2-D
image (Figure 2.16a).
• Applications: This arrangement is used in most flatbed scanners and in airborne imaging, where
an aircraft flies over a geographical area. Sensor strips in a ring configuration are used in medical
imaging, such as Computerized Axial Tomography (CAT), to obtain cross-sectional ”slice” images
of 3-D objects (Figure 2.16b).

2.4.3 Image Acquisition Using Sensor Arrays

While images can be acquired with single sensors or sensor strips that require mechanical motion, the
predominant arrangement in modern digital cameras and other devices is the sensor array.

• Structure: As shown in Figure 2.14(c) from the text, a sensor array consists of individual sensing
elements arranged in a two-dimensional grid.

25
Figure 2.14: Image Sensing a) Single Element, b) Sensor Strip c) Sensor Array

26
Figure 2.15: Combining a single sensing element with mechanical motion to generate a 2-D image.
Rotation of the drum provides one dimension of motion, and linear displacement of the sensor provides
the other. (From Fig. 2.13 in the text).

Figure 2.16: (a) Image acquisition using a linear sensor strip with motion. (b) Image acquisition using
a circular sensor strip, as in medical CAT scanners. (From Fig. 2.14 in the text).

27
 Figure 2.17: An example of Digital Image Aquisition

• Technology: A common example is the CCD (charge-coupled device) array, which can be manu-
factured with high sensor counts (e.g., 4000x4000 elements or more).
• Key Advantage: Because the sensor array is two-dimensional, its key advantage is that a complete
image can be captured at once simply by focusing the energy pattern from the scene onto the surface
of the array. This eliminates the need for mechanical motion, which is required for single-point or
line sensors.
The process of acquiring an image with a sensor array is illustrated in Figure 2.17.
1. An imaging system (such as an optical lens for visible light) collects the incoming energy from the
scene.
2. The system focuses the energy onto an image plane.
3. The sensor array, which is placed at the focal plane, produces outputs proportional to the integral
of the light received at each sensor.
4. This grid of outputs is then converted into a digital image by analog and digital circuitry.

2.5 The Digital Camera

After passing through the camera’s lens, light finally reaches the image sensor. Here, the complex process
of converting physical photons into the digital R, G, B values of an image begins. This section outlines
the journey of light through a modern digital camera, from the sensor to the final processed image.

2.5.1 The Image Sensing Pipeline

The conversion from light to a familiar image format like JPEG involves a series of steps, often performed
by a dedicated chip called an Image Signal Processor (ISP). The typical pipeline is shown in Figure
2.18.
The key stages are:
1. Sensor (CCD/CMOS): The sensor captures photons and converts them into an electrical signal
(a voltage).
2. Analog-to-Digital Converter (ADC): The ADC measures the analog voltage from the sensor
and converts it into a digital number. The output at this stage is a RAW image file, which contains
the unprocessed data directly from the sensor.

28
Figure 2.18: A typical image sensing pipeline, showing the path from the scene to a final JPEG image
and identifying various sources of noise.

3. Image Signal Processor (ISP): The raw data then enters the ISP for a sequence of crucial
enhancements:
• Demosaicing: Most sensors use a color filter array (like a Bayer filter), meaning each pixel
only measures one color (red, green, or blue). Demosaicing is the process of intelligently
interpolating the missing two color values for every pixel.
• Denoise and Sharpen: Algorithms are applied to reduce unwanted noise and enhance the
sharpness of edges.
• White Balance: Colors are adjusted to remove any color cast from the lighting conditions
(e.g., making a white wall appear neutral white instead of yellow under indoor lighting).
• Gamma/Curve: The brightness and contrast are adjusted to produce a visually pleasing
image that matches how humans perceive light.
• Compress: Finally, the processed image data is compressed into a standard format like
JPEG.

2.5.2 Sensor Technology: CCD vs. CMOS

The two main types of image sensors are the Charge-Coupled Device (CCD) and the Complementary
Metal-Oxide-Semiconductor (CMOS).
• CCD Sensors: In a CCD, the electrical charge generated by light at each pixel is transferred
down a line of pixels in a ”bucket brigade” fashion until it reaches the end, where a single, high-
quality amplifier converts it to a voltage. This method produced very high-quality, low-noise images
but was slower and prone to ”blooming,” where an overexposed pixel could leak its charge into
neighboring pixels.
• CMOS Sensors: In a CMOS sensor, each pixel has its own amplifier. This allows the charge
at any pixel to be converted to a voltage and read out directly, much like reading data from a
memory chip. This architecture makes CMOS sensors faster, more power-efficient, and cheaper to
manufacture. While originally considered lower quality, technological advances have made CMOS
the dominant technology used in most digital cameras today, from smartphones to professional
DSLRs.

29
Figure 2.19: A comparison of CCD and CMOS sensor technology. (a) CCDs move charge from pixel
to pixel to a single output node. (b) CMOS sensors have an amplifier at each pixel, allowing for direct
readout.

2.5.3 Key Factors Affecting Image Quality

Several key parameters of a digital camera’s design influence the final quality of its images:

• Shutter Speed: This is the amount of time the sensor is exposed to light. A longer exposure
makes the image brighter but can cause motion blur if the camera or scene is moving. A shorter
exposure freezes motion but results in a darker image.
• Sampling Pitch: This is the physical distance between the centers of adjacent pixels on the
sensor. A smaller pitch means more pixels can be packed into the same area (higher resolution).
However, smaller pixels capture fewer photons, making them more susceptible to noise, especially
in low light.
• Fill Factor: This is the percentage of a pixel’s area that is actually sensitive to light (as opposed to
being taken up by wiring). A higher fill factor is more efficient at capturing light, leading to better
image quality. Modern technologies like back-side illumination (BSI) move the wiring behind the
light-sensitive area to maximize the fill factor.
• Chip Size: The physical size of the image sensor is crucial. A larger sensor can accommodate
larger pixels, which can capture more light and produce images with less noise and a wider dynamic
range. This is why a large DSLR camera generally produces much cleaner images than a small
smartphone camera, especially in challenging lighting conditions.
• Analog Gain (ISO): Before the analog signal is converted to digital, it can be amplified. This
amplification is known as analog gain, and it is the basis for a camera’s ISO setting. Increasing
the ISO makes the image appear brighter, which is useful in dark situations, but it also amplifies
any existing noise in the signal.

2.6 Sampling and Aliasing

When a digital camera sensor captures an image, it is performing an act of sampling. It converts the
continuous field of light from the real world into a discrete grid of pixels.

2.6.1 Basic Concepts in Sampling and Quantization

An image is continuous with respect to its spatial (x and y) coordinates and also in its amplitude
(intensity). To digitize the image, we must digitize both aspects.
• Sampling: Digitizing the coordinate values is called sampling.
• Quantization: Digitizing the amplitude values is called quantization.

30
 Figure 2.20 illustrates this process. A continuous image (a) has its intensity profile taken along a scan
line (b). To digitize this line, we first sample it at discrete points (c). At this stage, the spatial location
is discrete, but the intensity value at each sample is still a continuous quantity. Next, we quantize these
continuous intensity values into a finite set of discrete levels. The result is a digital scan line (d) where
both position and intensity are discrete quantities. Repeating this process for all lines in the image
produces a two-dimensional digital image.

Figure 2.20: The process of sampling and quantization. (From Fig. 2.16 in the text).

In practice, the sampling method is determined by the sensor arrangement. For a sensor array, the
number of sensors in the array establishes the sampling limits in both directions. Figure 2.21 shows a
continuous image projected onto a sensor array (a) and the resulting digital image after sampling and
quantization (b).
Although, this process of discretization can lead to strange and undesirable artifacts, most notably
an effect called aliasing.

2.6.2 What is Aliasing?

Aliasing occurs when a signal is sampled too slowly. When this happens, a high-frequency signal can
masquerade as a lower-frequency one after being sampled.
A simple example is shown in Figure 2.22. Two different sine waves—one with a high frequency (blue)
and one with a low frequency (red)—are sampled at the same discrete points. The resulting samples
are identical for both waves. Once sampled, it is impossible to know which of the original signals was
present. The high-frequency signal has created an ”alias” of the low-frequency one.
The Nyquist-Shannon Sampling Theorem gives us the rule to avoid this. It states that to
perfectly reconstruct a signal, the sampling frequency (fs ) must be at least twice the highest frequency

31
Figure 2.21: (a) A continuous image is projected onto a sensor array. (b) The result of image sampling
and quantization. (From Fig. 2.17 in the text).

Figure 2.22: An illustration of aliasing. A high-frequency signal (blue) and a low-frequency signal (red),
when sampled at the same points (black dots), produce identical sets of samples. The original high-
frequency signal cannot be recovered.

present in the signal (fmax ):

fs ≥ 2fmax (2.10)
When this condition is not met, aliasing occurs.

2.6.3 Aliasing in Real Images: Moiré Patterns

In digital images, aliasing artifacts often appear as Moiré patterns. These are strange, wavy, and often
colorful patterns that emerge when you photograph a scene containing fine, repeating details, such as a
finely woven fabric, a window screen, or the pixels on a computer monitor.
This happens because the fine pattern in the real world has a very high frequency. The camera’s
sensor, with its own grid of pixels, samples this pattern. If the pattern’s frequency is higher than what
the sensor’s sampling rate can handle (i.e., it violates the Nyquist limit), the sensor creates a new, false,
lower-frequency pattern that was not there in the original scene. This is the Moiré pattern shown in
Figure 2.23.
To combat this, many high-end digital cameras intentionally include an anti-aliasing filter (also
called an optical low-pass filter). This is a specialized filter placed directly in front of the image sensor
that slightly blurs the image, smoothing out the very highest frequencies before they can be sampled.
This intentional blur prevents aliasing artifacts from appearing in the final photograph.

2.7 Color
When light from the world hits the image sensor, light from different parts of the spectrum is integrated
into the discrete red, green, and blue (RGB) color values that we see in a digital image. To understand
how digital color works, we must first look at the two primary ways colors can be mixed.

32
Figure 2.23: A real-world example of aliasing. When photographing a computer screen, the high-
frequency pattern of the screen’s pixels interferes with the camera sensor’s grid of pixels, creating a new,
artificial Moiré pattern.

2.7.1 Additive and Subtractive Color Models

You probably recall from childhood that mixing yellow and blue paint makes green. Later, you may have
learned that for light, mixing red and green makes yellow. This is not a contradiction; these are simply
two different color systems at work.

• Additive Color (RGB): This model applies to systems that emit light, such as computer mon-
itors, projectors, and televisions. It starts with black (the absence of light). The primary colors
are Red, Green, and Blue. As shown in Figure ??, mixing these primaries produces brighter,
secondary colors: red + green = yellow, green + blue = cyan, and blue + red = magenta. Mixing
all three primaries in equal intensity produces white.
– Hardware-oriented model.
– Widely used for color monitors, digital cameras, and other display devices.
– Based on additive mixing of light.
• Subtractive Color (CMY/CMYK): This model applies to pigments like paint or ink on paper,
which absorb (or subtract) light. It starts with white (the paper). The primary colors are Cyan,
Magenta, and Yellow. As shown in Figure ??, these pigments subtract certain colors from white
light. Mixing them produces darker, secondary colors: cyan + magenta = blue, magenta + yellow
= red, and yellow + cyan = green. Theoretically, mixing all three should produce black, but in
reality, it creates a muddy brown. For this reason, printers use a fourth pigment, K (Key, or black),
for pure blacks and sharp details. This is known as the CMYK model.
– Hardware-oriented model.
– Primarily used for color printing.
– CMYK adds black (K) because mixing CMY often produces a muddy brown rather than a
true black due to impurities in inks.
– Based on subtractive mixing of pigments.

• HSI (Hue, Saturation, Intensity):

– Application-oriented model, aligning closely with how humans describe and interpret color.
– Hue: Represents the pure color (e.g., red, blue, green).
– Saturation: Describes the purity of the color, or how much white light is mixed with the
hue. A highly saturated color is vibrant, while a less saturated color appears washed out.

33
Figure 2.24: A comparison of primary and secondary colors in the two main color models. (a) Additive
color mixes light, starting with black. (b) Subtractive color mixes pigments, starting with white.

– Intensity: Represents the brightness of the color.

– A key advantage of HSI is that it decouples color information (hue, saturation) from grayscale
information (intensity), making it suitable for many image processing techniques that operate
on intensity.

The combination of hue and saturation is referred to as chromaticity. Therefore, a color can be
characterized by its brightness and its chromaticity.
The amounts of red, green, and blue light required to form any particular color are known as the
tristimulus values, denoted as X, Y , and Z, respectively. A color can then be specified by its trichro-
matic coefficients, which are the normalized tristimulus values, defined as follows:

X
x= (2.11)
X +Y +Z
Y
y= (2.12)
X +Y +Z
Z
z= (2.13)
X +Y +Z
From these equations, we can see a fundamental relationship between the trichromatic coefficients:

x+y+z =1 (2.14)

For any wavelength of light within the visible spectrum, the tristimulus values (X, Y, Z) needed
to produce the color corresponding to that wavelength can be obtained directly from curves or tables
compiled from extensive experimental results (Poynton [1996, 2012]).

2.8 Compression
The final stage in a typical camera’s processing pipeline is image compression. This is a crucial step
designed to reduce the file size of an image, unless you are using a lossless format like camera RAW or
PNG.
The most common compression technique used in cameras today is JPEG, which is a lossy method,
meaning some information is permanently discarded to achieve a smaller file size. The process involves
several key steps:

1. Color Space Conversion: The first step is to convert the image from the RGB color space to a
different one, typically YCbCr. This space separates the image into one luminance (brightness)

34
Figure 2.25: Primary and secondary colors of light (additive primaries) and pigment (subtractive pri-
maries). (Courtesy of the General Electric Co., Lighting Division.)

Figure 2.26: Common representations of the HSI space when viewed along the intensity axis. Hue (H)
is an angle, and Saturation (S) is the distance from the center.

35
 channel, Y, and two chrominance (color) channels, Cb and Cr. This is done because the human
visual system is much more sensitive to changes in brightness than it is to changes in color.
2. Chroma Subsampling: Because we are less sensitive to color information, we can discard some
of it without a major impact on perceived quality. This process is called chroma subsampling. For
JPEG images, the color channels (Cb and Cr) are often subsampled (or averaged) by a factor of
two, both horizontally and vertically. This step alone can significantly reduce the data required to
store the image.
3. Discrete Cosine Transform (DCT): Once the luminance and chrominance channels are sep-
arated, the image is divided into small 8×8 pixel blocks. The Discrete Cosine Transform is then
applied to each block. The DCT is a mathematical operation that converts the spatial pixel values
into their frequency components. Its main advantage is that it ”packs” most of the visual energy of
the block into just a few coefficients that represent low-frequency information (smooth gradients),
while the many high-frequency coefficients (fine details) become close to zero.
4. Quantization and Encoding: This is the main ”lossy” step. The high-frequency coefficients from
the DCT, which are already small, are heavily compressed or discarded entirely. The remaining,
more important low-frequency coefficients are then efficiently organized and encoded.

2.8.1 Measuring Compression Quality

Since lossy compression algorithms discard information, it is important to have a way to measure how
much the compressed image deviates from the original. The quality of a compression algorithm is usually
reported using its peak signal-to-noise ratio (PSNR), a metric derived from the error between the
original and compressed images.
The foundation for this metric is the mean square error (MSE), which calculates the average
squared difference between the pixel values of the original and compressed images over all pixels.
1 Xh i2
M SE = ˆ
I(x) − I(x) (2.15)
n x

ˆ
where I(x) is the original uncompressed image, I(x) is its compressed counterpart, and n is the total
number of pixels.
Closely related is the root mean square error (RMS error), which is simply the square root of
the MSE, bringing the error metric back to the same scale as the original pixel intensities.
√
RM S = M SE (2.16)

Using the MSE, the PSNR is then defined as the ratio of the maximum possible signal power to the
power of the compression error (noise). The PSNR is typically expressed in decibels (dB), and a higher
PSNR value generally indicates better compression quality.
2
Imax Imax
P SN R = 10 log10 = 20 log10 (2.17)
M SE RM S
In this equation, Imax is the maximum possible pixel value for the image. For a standard 8-bit grayscale
or color image, this value is 255. This entire process, used in both JPEG for images and MPEG for video,
is highly effective at reducing file sizes by intelligently removing information that is least perceptible to
the human eye.

36
Bibliography

[1] Szeliski, R. (2010). Computer Vision: Algorithms and Applications. Springer.

[2] Forsyth, D. A., & Ponce, J. (2011). Computer Vision: A Modern Approach. Prentice Hall.

37
Chapter 3

Image Processing

Having explored the principles of image formation, we now possess a digital representation of a scene—typically
as a large matrix of pixel values. The raw data from a camera’s sensor is often not in an ideal state for
either human viewing or machine analysis. In this chapter we discuss how images are represented in a
computer and also learn about various operations on the image.

3.1 Representing an Image for a Computer

For a computer to perform operations on an image, the visual information must be converted into a
structured, numerical format. The two primary ways to conceptualize this are as a matrix and as a
mathematical function.

3.1.1 Image as a Matrix

The most direct and common way to represent a digital image is as a matrix of numbers. Each element
in this matrix corresponds to a pixel (a portmanteau of ”picture element”), which is the smallest unit
of an image.
For a grayscale (black and white) image, the representation is a single 2D matrix. Each entry in the
matrix is an integer that represents the intensity or brightness of the corresponding pixel. It is standard
practice to use one byte (8 bits) per pixel, which allows for 28 = 256 distinct values. By convention:
• A value of 0 represents pure black.

• A value of 255 represents pure white.

• Values in between represent shades of gray.
For a color image, this concept is extended by using three separate matrices: one for the Red channel,
one for the Green channel, and one for the Blue channel. Therefore, a color image can be thought of as
a 3D tensor of size (Height × Width × 3). The final color of any given pixel is the result of combining
the intensity values from its corresponding location in each of the three color matrices.

3.1.2 Image as a Function

A more abstract and mathematically powerful way to think of an image is as a function. A grayscale
image can be seen as a function, f , which maps a 2D spatial coordinate (x, y) to a single intensity value.
We can write this formally as:
f : R2 → R (3.1)
In this view, the image is a continuous surface where the height at any point (x, y) corresponds to the
brightness at that location, as visualized in Figure 3.2.
A digital image is the discrete version of this ideal continuous function. The process of creating a
digital image involves two key steps:
• Sampling: The continuous 2D space of the function is sampled into a discrete grid of points. The
density of this grid determines the image’s resolution.

38
Figure 3.1: A grayscale image is a 2D matrix of intensity values. A color image is typically composed of
three such matrices, one for each color channel (R, G, B).

(a) Original Grayscale Image (b) Intensity as a 3D Surface

Figure 3.2: A grayscale image (a) can be viewed as a function (b), where the intensity at each coordinate
(x, y) is plotted as a height, forming a 3D surface. Credit: Noah Snavely, Cornell Univ.

• Quantization: The continuous intensity values are mapped to a finite set of discrete numbers
(e.g., integers from 0 to 255).

39
Thinking of an image as a function is particularly useful because it allows us to apply a wide range of
mathematical tools from calculus and signal processing to perform complex image transformations.

3.2 Image Processing Operations

An image processing operator is a function that takes one or more images as input and produces a new
image as output. This can be expressed formally in the continuous domain as:

g(x) = h(f (x)) (3.2)

or for an operator that combines multiple images:

g(x) = h(f0 (x), ..., fn (x)) (3.3)

For a discrete digital image, where pixel locations are denoted by coordinates (i, j), this simplifies to:

g(i, j) = h(f (i, j)) (3.4)

These operators can be broadly classified into three categories based on how many pixels from the input
image are used to compute the value of a single output pixel.

3.2.1 Point Operations

Point operations are the simplest type of image transformation. In a point operation, the output value of
a pixel at a given coordinate depends only on the input value of the pixel at the exact same coordinate.
This means each pixel is processed independently, and the operation has a constant complexity per pixel.
Common point operations include:

• Brightness and Contrast Adjustment: This is a fundamental operation often modeled with a
linear equation:
g(x) = a · f (x) + b (3.5)
Here, f (x) is the input pixel value and g(x) is the output. The parameters a and b are known as
the gain and bias.

– The gain parameter (a > 0) controls the contrast. A value a > 1 increases the contrast,
while a < 1 decreases it.
– The bias parameter (b) controls the brightness. A positive b brightens the image, and a
negative b darkens it.

These parameters can also be spatially varying, a(x) and b(x), to create effects like a graded density
filter that darkens only the sky in a landscape photo.
• Contrast Reversal (Image Negative): This operation inverts the intensity values of an im-
age, turning black pixels into white, white pixels into black, and inverting all shades of gray in
between. It is useful for enhancing white or gray details embedded in dark regions of an image.
The transformation is defined as:
ˆ 0 , n0 ) = (IM AX − I(m0 , n0 )) + IM IN
I(m (3.6)

For a standard 8-bit image where the intensity range is [0, 255], IM AX = 255 and IM IN = 0, so
the formula simplifies to inverting the pixel value relative to the maximum.
Reversing the intensity levels of a digital image in this manner produces the equivalent of a pho-
tographic negative. This type of processing is used, for example, in enhancing white or gray detail
embedded in dark regions of an image, especially when the black areas are dominant in size. Figure
3.4 shows an example. The original image is a digital mammogram showing a small lesion. Despite
the fact that the visual content is the same in both images, some viewers find it easier to analyze
the fine details of the breast tissue using the negative image.

40
(a) A digital mammogram. (b) Negative image obtained using Eq. (3-3). (Image (a) Courtesy of General
Electric Medical Systems.)

• Log Transformation : The logarithmic transformation is a fundamental intensity mapping func-

tion used to enhance images by altering their dynamic range. The general form of the log trans-
formation is given by the formula:

s = c · log(1 + r) (3.7)

In this equation, r is the intensity of the input pixel (with r ≥ 0), s is the intensity of the output
pixel, and c is a scaling constant. The ‘+1‘ term is included to prevent the logarithm of zero,
ensuring the function is defined for all possible input pixel values, including black (r=0).
The primary characteristic of the log transformation is its non-linear mapping of intensity values.
As can be seen from its functional shape:
– It expands the range of low-intensity (dark) values in the input image into a wider range of
output levels.
– It compresses the range of high-intensity (bright) values into a narrower range of output
levels.
This behavior makes the log transformation particularly useful for revealing details hidden in the
darker regions of an image while preserving the overall context of the brighter regions. The inverse
log (or exponential) transformation has the opposite effect, expanding bright areas and compress-
ing dark ones.

Finding the Perfect Scaling Constant ”c” for Logarithmic Transformation

The effectiveness of a logarithmic transformation, defined by the equation s = c log(1 + r), is highly
dependent on the choice of the scaling constant ‘c‘. This constant is crucial for mapping the output
of the log function to a specific and desirable display range, such as [0, 255] for a standard 8-bit
image.
A robust method for determining ‘c‘ is to scale the transformation so that the maximum input
intensity value maps to the maximum possible output intensity value. This gives rise to the
following formula:

41
 Figure 3.3: Log Transformation at various C levels

(Max Pixel Intensity in image)

C= (3.8)
log(1 + Max Pixel Intensity in image)

– C: The scaling constant required for the logarithmic transformation.

– Max Pixel Intensity in image: This value is typically the maximum intensity possible for
the image’s bit depth. For an image with L intensity levels, this value is L − 1.

• Contrast Stretching (Normalization): This operation is used to enhance a low-contrast image

by expanding its narrow range of intensity values to cover the full dynamic range. For example, if
a dark image only has pixel values between 50 and 130, this operation ”stretches” that range to
fill the entire 0 to 255 spectrum. The formula for linear contrast stretching is:
 
ˆ IM AX − IM IN
I(m0 , n0 ) = I(m0 , n0 ) − min I(x, y) × + IM IN (3.9)
x,y maxx,y I(x, y) − minx,y I(x, y)

This equation remaps each pixel’s original intensity to a new value that is proportionally scaled to
the full available intensity range.
• Linear Blending: This operator combines two input images, f0 (x) and f1 (x), to create a single
output. It is commonly used for cross-dissolve transitions in videos and for image morphing. The
transformation is defined by:
g(x) = (1 − α)f0 (x) + αf1 (x) (3.10)
By varying the parameter α from 0 to 1, the output image smoothly transitions from image f0 to
image f1 .
• Gamma Correction: This is a highly important non-linear transformation used to correct for
the fact that the relationship between input radiance and the final pixel values in a digital camera
is not perfectly linear. The gamma correction function is:

g(x) = [f (x)]1/γ (3.11)

A gamma value of γ ≈ 2.2 is a common and reasonable fit for most digital cameras.

42
3.2.2 Histogram Shape and Image Characteristics
The shape of an image’s histogram provides a global description of its appearance and is a valuable tool
for understanding its quality. Figure 3.4 illustrates the direct relationship between four basic image types
and their corresponding histograms.

Figure 3.4: Four basic image types and their corresponding histograms. (a) dark; (b) light; (c) low
contrast; (d) high contrast. The horizontal axis of the histograms represents the intensity values (rk ),
and the vertical axis represents the normalized count (p(rk )).

By examining the distribution of pixel intensities shown in the histograms, we can infer the following:

• Dark Image (a): The histogram is skewed towards the left (low-intensity end). Most pixels are
dark, and there is a lack of bright detail.

• Light Image (b): The histogram is skewed towards the right (high-intensity end). The image is
predominantly bright, potentially with washed-out highlights.
• Low-Contrast Image (c): The histogram is narrow and concentrated in a small range, typically
in the middle of the intensity scale. The image lacks a full range of tones, resulting in a dull or
”washed-out” appearance.
• High-Contrast Image (d): The histogram is spread out over a wide range of intensity levels.
A well-distributed histogram indicates that the image utilizes the full tonal range, resulting in a
visually rich image with clear details.

The key insight from this analysis is that an image with a wide and relatively uniform histogram will
exhibit high contrast and reveal a great deal of detail. This principle is the basis for powerful enhance-
ment techniques, such as histogram equalization, which aim to automatically generate a transformation
function that reshapes the histogram to achieve this desirable distribution.

3.2.3 Histogram Equilization

This section breaks down the process of histogram equalization for a given 5x5 input image. The image
uses 3-bit gray levels, which means there are 23 = 8 possible intensity levels (from 0 to 7).
Histogram equalisation is done by performing the following steps:
1. Find the running sum of the histogram values.
2. Normalise the values from Step (1) by dividing by the total number of pixels.

43
 3. Multiply the values from Step (2) by the maximum gray-level value and round.
4. Map the gray level values to the results from Step (3) using a one-to-one correspondence.

Example: Perform histogram equalisation of the image

Given the following 5x5 image matrix:
 
4 4 4 4 4
3 4 5 4 3
 
3
I= 5 5 5 3
3 4 5 4 3
4 4 4 4 4

Solution
The maximum value is found to be 5. We need a minimum of 3 bits to represent the number. There are
eight possible gray levels from 0 to 7. The histogram of the input image is given below:

Gray level 0 1 2 3 4 5 6 7
Number of pixels 0 0 0 6 14 5 0 0

Step 1: Compute the running sum of histogram values

The running sum of histogram values is otherwise known as cumulative frequency distribution.

Gray level 0 1 2 3 4 5 6 7
Number of pixels 0 0 0 6 14 5 0 0
Running sum 0 0 0 6 20 25 25 25

Step 2: Divide the running sum by the total number of pixels

The total number of pixels is 25.

Gray level 0 1 2 3 4 5 6 7
Number of pixels 0 0 0 6 14 5 0 0
Running sum 0 0 0 6 20 25 25 25
Running Sum/Total 0/25 0/25 0/25 6/25 20/25 25/25 25/25 25/25

Step 3: Multiply by the maximum gray-level value and round

The result from Step 2 is multiplied by the maximum gray-level value, which is 7 in this case.

Gray level 0 1 2 3 4 5 6 7
Number of pixels 0 0 0 6 14 5 0 0
Running Sum 0 0 0 6 20 25 25 25
Running Sum/Total 0/25 0/25 0/25 6/25 20/25 25/25 25/25 25/25
0 0 0 6 20 25 25 25
Multiply by max gray level 25 · 7 25 · 7 25 · 7 25 · 7 25 · 7 25 · 7 25 · 7 25 · 7

The result is then rounded to the closest integer to get the following table:

Gray level 0 1 2 3 4 5 6 7
Number of pixels 0 0 0 6 14 5 0 0
Running Sum 0 0 0 6 20 25 25 25
Running Sum/Total 0/25 0/25 0/25 6/25 20/25 25/25 25/25 25/25
Multiply and Round 0 0 0 2 6 7 7 7

44
 Figure 3.5: Result of histogram Equalization

Step 4: Map gray levels by a one-to-one correspondence

Original gray level Histogram equalised values
0 0
1 0
2 0
3 2
4 6
5 7
6 7
7 7

The original image and the histogram equalised image are shown side by side.
   
4 4 4 4 4 6 6 6 6 6
3 4 5 4 3 2 6 7 6 2
  Histogram Equalisation  
3 5 5 5 3 −
 −−−−−−−−−−−−−−→ 2 7 7 7 2

 
3 4 5 4 3 2 6 7 6 2
4 4 4 4 4 6 6 6 6 6
| {z } | {z }
Original Image Histogram equalised image

3.2.4 Local Operations

In a local operation, the output value of a pixel depends on the input values in a small neighborhood
surrounding that pixel. These operations are essential for tasks like blurring, sharpening, and edge
detection.
A classic example is a moving average, which is used to smooth an image or reduce noise. To
compute the new value for a pixel at location (i, j), a local operator might take the average of all pixel
values in a 3 × 3 or 5 × 5 window centered at (i, j) in the input image. Because the output depends on

45
a neighborhood of pixels, the complexity is higher than for point operations (e.g., on the order of p2 for
a p × p neighborhood).

Figure 3.6: Local Operations using Average Filter.

3.2.5 Global Operations

A global operation is one where the output value of a single pixel depends on all of the pixels in the
entire input image. These are the most computationally intensive operations.
A primary example is the Fourier Transform, which is a coordinate transformation that converts
an image from its spatial domain (a grid of pixels) into the frequency domain. In the frequency domain,
each point represents information about the entire image, making any subsequent operation global in
nature.

3.3 Spatial Filtering

In the realm of digital image processing, spatial filtering is a fundamental technique used to modify
or enhance an image. The process, often referred to as ”filtering,” involves moving a ”filter,” ”mask,”
”kernel,” ”template,” or ”window” across the image from pixel to pixel. At each position, a new value
for the corresponding pixel in the output image is calculated based on a predefined relationship between
the filter and the underlying image pixels. If the operation performed is linear, the process is known as
linear spatial filtering.
Spatial filtering is primarily employed for tasks such as noise reduction, sharpening, and blurring.
For instance, a low-pass filter, which attenuates high frequencies in an image’s spectrum, results in a
blurring effect. This is achieved by smoothing the transitions in pixel intensities.
The core of spatial filtering lies in the application of a filter kernel to each pixel and its neighbors.
The size and values of the kernel determine the outcome of the filtering operation.

3.3.1 The Mechanics of Linear Spatial Filtering

A linear spatial filter operates by performing a sum-of-products operation between an image and a filter
kernel. The kernel is a small matrix of coefficients. For a given pixel (x, y) in the input image, the
response g(x, y) of the filter is the sum of the products of the kernel coefficients and the corresponding
image pixels.
The general expression for linear spatial filtering is given by:
a
X b
X
g(x, y) = w(s, t)f (x + s, y + t) (3.12)
s=−a t=−b

where w is the filter kernel of size m × n, f is the input image, m = 2a + 1, and n = 2b + 1. This equation
represents the core of two closely related but distinct processes: correlation and convolution.

3.3.2 Correlation
Correlation is the process of moving a filter kernel over the image and, at each location, calculating the
sum of products of the kernel and the overlapping image pixels.

46
Process of 1-D Correlation
Consider a 1-D function f and a kernel w. The process involves sliding the kernel w across the function
f.
• Starting Position: The process begins with the kernel positioned at the origin of the function.
The correlation is the sum of the products of the elements.
• Padding: If the kernel extends beyond the boundaries of the image, a common practice is to
pad the image with zeros (zero-padding). This ensures that the operation is defined for all pixels,
including those at the edges.
• Shifting: The kernel is then shifted one pixel at a time, and the sum of products is recalculated
at each position.
• Final Position: The process continues until the kernel has traversed the entire function.
The illustration below demonstrates the 1-D correlation of a function f with a kernel w, including
the use of zero-padding.

Figure 3.7: Illustration of 1-D correlation of a discrete function f with a kernel w. Padding is used to
handle the borders.

47
Process of 2-D Correlation
The concept of 1-D correlation extends directly to 2-D images. For a 2-D kernel w and an image f , the
correlation at a point (x, y) is given by Equation 3.12.

Figure 3.8: The mechanics of 2-D linear spatial filtering using a 3 × 3 kernel. The process shown is
correlation.

Algorithm for 2-D Correlation:

1. Define the Kernel: Specify the m × n filter kernel w.
2. Pad the Image: Pad the input image f with m − 1 rows and n − 1 columns of zeros to handle
the borders.
3. Iterate Over Image Pixels: For each pixel (x, y) in the original image dimensions:
(a) Initialize Sum: Set a variable sum to 0.

48
 (b) Iterate Over Kernel: For each element w(s, t) in the kernel (from s = −a to a and t = −b
to b):
i. Multiply the kernel coefficient w(s, t) by the corresponding image pixel f (x + s, y + t).
ii. Add the result to sum.
(c) Assign Output Pixel: The value of the output pixel g(x, y) is set to sum.

3.3.3 Convolution
Convolution is a similar operation to correlation, with one crucial difference: the filter kernel is rotated
by 180 degrees before the sum of products is calculated. The equation for 2-D convolution is:
a
X b
X
(f ∗ w)(x, y) = w(s, t)f (x − s, y − t) (3.13)
s=−a t=−b

Notice the change in the sign of s and t in the f term compared to the correlation equation (Equation
3.12). This change is what mathematically represents the 180-degree rotation of the kernel.

Why Rotate the Kernel?

The rotation of the kernel in convolution is a fundamental property in linear systems theory. Convolving
a function with a unit impulse results in the function itself, a property that is essential for many signal
and image processing applications. If the kernel is symmetric, correlation and convolution produce the
same result.

Algorithm for 2-D Convolution:

1. Define and Rotate the Kernel: Specify the m × n filter kernel w and rotate it by 180 degrees.

2. Pad the Image: Pad the input image f as in the correlation process.
3. Iterate Over Image Pixels: For each pixel (x, y) in the original image dimensions:
(a) Perform the sum-of-products operation using the rotated kernel.
(b) Assign the result to the output pixel g(x, y).

Alternatively, without pre-rotating the kernel:

1. Define the Kernel: Specify the m × n filter kernel w.

2. Pad the Image: Pad the input image f .

3. Iterate Over Image Pixels: For each pixel (x, y):
(a) Initialize Sum: Set sum to 0.
(b) Iterate Over Kernel: For each w(s, t):
i. Multiply w(s, t) by the image pixel f (x − s, y − t).
ii. Add the result to sum.
(c) Assign Output Pixel: Set g(x, y) to sum.

3.3.4 Usage and Properties of Correlation and Convolution

Both correlation and convolution are used extensively in spatial filtering. Many image processing software
implementations use the term ”convolution” generically to refer to any spatial filtering operation, even if
they are technically performing correlation. This is often because the kernels used for common filtering
tasks like blurring (e.g., a Gaussian kernel) are symmetric, making the distinction irrelevant in practice.
However, understanding the difference is crucial for designing and implementing custom filters.

49
Figure 3.9: Correlation (middle row) and convolution (last row) of a 1-D kernel with an image consisting
of a discrete unit impulse. The 180-degree rotation of the kernel for convolution is shown.

Key Properties
• Commutative Property: Convolution is commutative (f ∗ w = w ∗ f ), while correlation is not.
• Associative Property: Convolution is associative ((f ∗ g) ∗ h = f ∗ (g ∗ h)), while correlation is
not.

The associative property of convolution is particularly useful, as it allows for the pre-computation of a
single kernel from multiple successive filtering operations, leading to significant computational savings.

50
 Property Convolution Correlation
Commutative f ⋆g =g⋆f —
Associative f ⋆ (g ⋆ h) = (f ⋆ g) ⋆ h —
Distributive f ⋆ (g + h) = (f ⋆ g) + (f ⋆ h) f ⋆ (g + h) = (f ⋆ g) + (f ⋆ h)

3.4 Edge Detection

Edge-based segmentation exploits spatial information by detecting the edges in an image. Edges corre-
spond to discontinuities in the homogeneity criterion for segments. Edge detection is usually done with
local linear gradient operators such as Prewitt, Sobel and Laplacian filters. These operators work well
for images with sharp edges and low amounts of noise. The detected boundaries using these operators
may not necessarily form a set of closed connected curves, so some edge linking may be required.

3.4.1 Classification of Edges

Points in an image where brightness changes abruptly are called edges or edge points. Edges are signifi-
cant local changes of intensity in an image. Edges are the boundaries between segments. Edges are a very
important portion of the perceptual information content in an image. Edges can be broadly classified
into (i) step edge, (ii) line edge, (iii) ramp edge, and (iv) roof edge.

Step Edge
The step edge defines a perfect transition from one segment to another. In the case of a step edge, the
image intensity abruptly changes from one value to one side of the discontinuity to a different value on
the opposite side. If segments are piecewise constant and pixels can only belong to one segment, then a
step edge model is implicitly used.

Figure 3.10: Step edge profile.

Line Edge
If a segment of an image is very narrow, it necessarily has two edges in close proximity. This arrangement
is called a line. The line edge is shown in Fig. 7.18.

Figure 3.11: Line edge profile.

Ramp Edge
A ramp allows for a smoother transition between segments. A ramp edge is useful for modeling the
blurred edges created from sampling a scene containing objects not aligned to the pixel grid.

51
 Figure 3.12: Ramp edge profile.

Roof Edge
Two nearby ramp edges result in a line structure called a roof. Basically, there are two types of roof
edges: (i) convex roof edges, and (ii) concave roof edges which are shown in Fig. 7.20.

(a) Convex roof edge (b) Concave roof edge

Figure 3.13: Roof edge profiles.

Causes of Edges Edges can be created by shadows, texture, geometry, and so forth. Edges are basi-
cally discontinuities in the image intensity due to changes in the image structure. These discontinuities
originate from different features in an image. Edge points are to be associated with the boundaries of
objects and other kinds of changes. Edges within an image generally occur at various resolutions or
scales and represent transitions of different degrees or gradient levels.

3.4.2 Gradient Operator

A gradient is a two-dimensional vector that points to the direction in which the image intensity grows
fastest. The gradient operator ∇ is given by
∂
∇ = ∂x ∂ (3.14)
∂y

If the operator ∇ is applied to the function f then

" #
∂f
∇f = ∂x (3.15)
∂f
∂y

The two functions that can be expressed in terms of the directional derivatives are the gradient magnitude
and the gradient orientation. It is possible to compute the magnitude ||∇f || of the gradient and the
orientation ϕ(∇f ).
The gradient magnitude gives the amount of the difference between pixels in the neighbourhood which
gives the strength of the edge. The gradient magnitude is defined by
" #
  ∂f
Gx 1
|∇f | = = ∂x
∂f = [G2x + G2y ] 2 (3.16)
Gy ∂y

The magnitude of the gradient gives the maximum rate of increase of f (x, y) per unit distance in the
gradient orientation of |∇f |. The gradient orientation gives the direction of the greatest change, which
presumably is the direction across the edge. The gradient orientation is given by
 
−1 Gy
ϕ(∇f ) = tan (3.17)
Gx

52
 Figure 3.14: Gradient of edge pixel.

where the angle is measured with respect to the x-axis.

The direction of the edge at (x, y) is perpendicular to the direction of the gradient vector at that
point. Figure 3.14 indicates the gradient of the edge pixel. The circle indicates the location of the pixel.
An edge pixel is described using two important features:
(i) Edge strength, which is equal to the magnitude of the gradient
(ii) Edge direction, which is equal to the angle of the gradient

3.4.3 Edge Detection Using First-order Derivatives

The derivative of a digital pixel grid can be defined in terms of differences. The first derivative of an
image containing gray-value pixels must fulfill the following conditions—it must be zero in flat segments,
i.e. in area of constant gray-level values; it must be non-zero at the beginning of a gray-level step or ramp;
and it must be non-zero along the ramp (constant change in gray values). The first-order derivative of
a one-dimensional function f (x) can be obtained using

df
= f (x + 1) − f (x) (3.18)
dx
An image is a function of two variables f (x, y). Equation (7.11) only refers to the partial derivative along
the x-axis. Pixel discontinuity can be determined along eight possible directions such as up, down, left,
right and along the four diagonals.
The other method of calculating the first-order derivative is given by estimating the finite difference:

∂f f (x + h, y) − f (x, y)
= lim (3.19)
∂x h→0 h
∂f f (x, y + h) − f (x, y)
= lim (3.20)
∂y h→0 h
The finite difference can be approximated as

∂f f (x + h, y) − f (x, y)
= = f (x + 1, y) − f (x, y), (hx = 1) (3.21)
∂x hx
and
∂f f (x, y + h) − f (x, y)
= = f (x, y + 1) − f (x, y), (hy = 1) (3.22)
∂y hy
Using the pixel coordinate notation and considering that j corresponds to the direction of x, and i
corresponds to the y direction, we have
∂f
= f (i, y + 1) − f (i, j) (3.23)
∂x
and
∂f
= f (i, j) − f (i + 1, j) (3.24)
∂y

53
Most edge-detecting operators can be thought of as gradient calculators. Because the gradient is a
continuous function concept and the input signal is a finite signal (image), the gradient computations
have to be approximated. Since derivatives are linear and shift-invariant, gradient calculation is most
often done using convolution. Numerous kernels have been proposed for finding edges.

Roberts Kernel
The main objective is to determine the differences between adjacent pixels. One way to find an edge is to
explicitly use {+1, −1} that calculates the difference between adjacent pixels. Mathematically, these are
called forward differences. The simplest way to implement the first-order partial derivative is by using
the Roberts cross-gradient operator. The partial derivatives can be implemented by approximating them
to two 2 × 2 masks. The Roberts operator masks are given by
   
−1 0 0 −1
Gx = and Gy = (3.25)
0 1 1 0

These filters have the shortest support, thus the position of the edges is more accurate, but the problem
with the short support of the filters is its vulnerability to noise.

Prewitt Kernel
The Prewitt kernels are based on the idea of central difference and are an improvement over the Roberts
operator for noise reduction. Due to their larger 3 × 3 size, they have better noise immunity. The Prewitt
operator masks are obtained as:
   
−1 −1 −1 −1 0 1
Gx =  0 0 0  and Gy = −1 0 1 (3.26)
1 1 1 −1 0 1

Sobel Kernel
The Sobel kernels also rely on central differences but give greater weight to the central pixels when
averaging. This provides better noise-suppression characteristics compared to the Prewitt mask. The
3 × 3 Sobel masks are given as:
   
−1 −2 −1 −1 0 1
Gx =  0 0 0  and Gy = −2 0 2 (3.27)
1 2 1 −1 0 1

3.4.4 Edge Detection from Gradients

Let us take a look at an example. Here, we have the gradient operator, specifically the 3x3 Sobel operator,
applied to an image that is popularly known as the Lena image. On the left is the first derivative with
respect to x, in the middle is the first derivative with respect to y, and on the right is the gradient
magnitude computed from both. Now, there is one last step: we have the magnitude and the orientation
at every pixel, but we still need to declare each pixel as being an edge or not.
In other words, we need to threshold the edge map. There are essentially two simple ways to do this.
The first is to use a single threshold — if the magnitude is less than some value T it is not an edge,
and if the magnitude is greater than or equal to T, then it is an edge. We can do a bit better than
this by introducing some hysteresis in the thresholding, by using two thresholds. We declare no edge if
the magnitude is less that the lower threshold, and an edge if it is greater than the higher threshold. If
the magnitude lies between the two thresholds, we can make a decision based on the how “edgy” the
neighboring pixels are.

3.5 Derivatives and Edges

In the context of image processing, edges are significant local changes in image intensity. These changes
can be effectively identified by analyzing the derivatives of the image signal. The first derivative of the
image intensity function highlights the rate of change. At an edge, where the intensity changes rapidly,
the first derivative will exhibit a local extremum (a peak or a valley).

54
 Figure 3.15: Application of the Sobel operator to find the gradient components and magnitude.

Standard: (Single Threshold T )

∥∇I(x, y)∥ < T Definitely Not an Edge
∥∇I(x, y)∥ ≥ T Definitely an Edge

Hysteresis Based: (Two Thresholds T0 < T1 )

∥∇I(x, y)∥ < T0 Definitely Not an Edge
∥∇I(x, y)∥ ≥ T1 Definitely an Edge
T0 ≤ ∥∇I(x, y)∥ < T1 Is an Edge if a Neighboring Pixel
is Definitely an Edge

Table 3.1: A summary of single-threshold and hysteresis-based edge thresholding methods. (Page 18)

The second derivative, which represents the rate of change of the first derivative, provides an even
more precise localization of the edge. Specifically, the zero-crossings of the second derivative correspond
to the locations of the edges. This is because the first derivative reaches its maximum or minimum at
the center of the edge, and the derivative of a function at its extremum is zero.

3.6 Laplacian (∇2 ) as Edge Detector

For a 2D image, the concept of the second derivative is extended to the Laplacian operator, denoted as
∇2 . The Laplacian is a scalar operator that is the sum of the second partial derivatives with respect to
the x and y directions.
Laplacian: Sum of Pure Second Derivatives

∂2I ∂2I
∇2 I = +
∂x2 ∂y 2
Pronounced as ”Del Square I”.
Edges are identified as ”zero-crossings” in the Laplacian of the image. A key characteristic of the
Laplacian operator is that it does not provide information about the direction or orientation of the edges.

55
Figure 3.16: The first derivative’s local extrema and the second derivative’s zero-crossings indicate the
locations of edges.

3.7 Discrete Laplacian Operator

To apply the Laplacian to a discrete image, we use finite differences to approximate the second derivatives.
This results in a convolution operation with a specific kernel.
The Laplacian operation can be expressed in terms of difference equations as given below:
∂f
≈ f (x + 1, y) − f (x, y) (3.28)
∂x
∂2f
≈ f (x + 1, y) − 2f (x, y) + f (x − 1, y) (3.29)
∂x2
∂2f
≈ f (x, y + 1) − 2f (x, y) + f (x, y − 1) (3.30)
∂y 2
This implies that:

∇2 f ≈ [f (x + 1, y) + f (x − 1, y) + f (x, y + 1) + f (x, y − 1)] − 4f (x, y) (3.31)

This discrete approximation of the Laplacian can be implemented by convolving the image with a
kernel, also known as a mask. Commonly used Laplacian kernels include:
 
0 1 0
K1 = 1 −4 1 (3.32)
0 1 0
 
−1 −1 −1
K2 = −1 8 −1 (3.33)
−1 −1 −1

3.8 Effects of Noise and the Solution

A significant challenge in edge detection is the presence of noise in the image. Since the Laplacian
operator is a second-derivative operator, it is highly sensitive to noise, which can lead to the detection
of false edges.
To mitigate the effects of noise, the image is typically smoothed with a Gaussian filter before applying
the Laplacian operator. This blurring process removes high-frequency noise.

56
 Figure 3.17: The effect of noise on a function and its gradient. The gradient becomes very noisy.

Figure 3.18: Smoothing the signal with a Gaussian filter reduces noise before differentiation.

3.9 Derivative of Gaussian and Laplacian of Gaussian

The processes of Gaussian smoothing and differentiation are both linear operations. Therefore, they can
be combined into a single convolution step. This is a key insight that leads to the development of the
Derivative of Gaussian (DoG) and Laplacian of Gaussian (LoG) operators.

3.9.1 Derivative of Gaussian (∇(nσ ))

Instead of first convolving the image with a Gaussian and then taking the derivative, we can first
compute the derivative of the Gaussian and then convolve the image with this new filter. This reduces

57
two operations to one.
∇(nσ ∗ f ) = ∇(nσ ) ∗ f

Figure 3.19: Combining Gaussian smoothing and differentiation into a single filter.

3.9.2 Laplacian of Gaussian (∇2 nσ or ∇2 G)

Similarly, for the Laplacian, we can first apply the Laplacian operator to the Gaussian function and then
convolve the image with the resulting filter, known as the Laplacian of Gaussian (LoG). This operator is
also famously known as the Mexican Hat operator due to its shape. Because the convolution operation
is associative, this method is more efficient as it combines two steps into one.

∇2 (nσ ∗ f ) = ∇2 (nσ ) ∗ f

Figure 3.20: The Laplacian of Gaussian (LoG) or Mexican Hat operator.

The LoG operator is a powerful tool for edge detection as it combines noise reduction and edge
enhancement into a single convolution. The zero-crossings in the resulting image correspond to the
edges.

3.10 Comparing Gradient and Laplacian Operators

Both the gradient and Laplacian operators are fundamental in edge detection, but they have distinct
properties and applications.

• Gradient Operator:

58
 – A first-derivative operator.
– Provides edge location, magnitude (strength), and direction.
– Typically requires a threshold step to identify edges from the gradient magnitude.
– Is a non-linear operation and generally requires two convolutions to compute the x and y
derivatives.
• Laplacian Operator:
– A second-derivative operator.
– Provides only the location of the edge through zero-crossings.
– Does not provide information about edge direction.
– Is a linear operation and requires only a single convolution.

In summary, the choice between the gradient and Laplacian operators often depends on the specific
requirements of the application, such as the need for edge orientation information or computational
efficiency.

3.11 Canny Edge Detector

The Canny edge detector is arguably the most widely used and effective edge detection algorithm in
computer vision. It was developed by John F. Canny in 1986 with the goal of creating an optimal edge
detector. The algorithm uses a multi-stage process that effectively combines the strengths of both the
gradient and Laplacian operators to detect a wide range of edges while being robust to noise.
The Canny algorithm follows a series of steps to achieve this:

1. Noise Reduction: The first step is to reduce the noise in the input image, as edge detection is
highly susceptible to it. This is done by convolving the image I with a 2D Gaussian filter nσ . The
degree of smoothing is controlled by the standard deviation of the Gaussian, σ.

Ismoothed = nσ ∗ I

2. Finding the Image Gradient and Magnitude: The gradient of the smoothed image is then
computed to identify the intensity changes. An operator like the Sobel operator is applied to get
the derivatives in the x and y directions.

∇Ismoothed = ∇(nσ ∗ I)

From these derivatives, the gradient magnitude (edge strength) is calculated for each pixel. The
magnitude represents how strong the edge is, where brighter pixels in the magnitude image indicate
stronger edges.

Figure 3.21: ||∇nσ ∗ I||

3. Non-Maximum Suppression: This step is designed to thin the ”thick” edges produced by the
gradient magnitude into sharp, single-pixel-wide edges. This involves several sub-steps:

59
 • First, the gradient orientation is found at each pixel. This determines the direction of the
edge.
∇nσ ∗ I
n̂ =
||∇nσ ∗ I||

Figure 3.22: ||∇nσ ∗ I||

• Next, a 1D Laplacian (second derivative) is computed along the gradient direction n̂ at each
pixel.
∂ 2 (nσ ∗ I)
∂ n̂2

Figure 3.23: Computing the second derivative along the gradient direction.

• Finally, the algorithm finds the zero-crossings in this 1D Laplacian. An edge is declared at the
location of a zero-crossing. This process effectively suppresses pixels that are not at the peak
of the gradient ridge, resulting in thinned edges. The advantage of applying the Laplacian
only along the gradient direction is that it is less affected by pixels unrelated to the edge.

Figure 3.24: Zero-crossings are found (left) to produce the final, thinned edge map (right).

60
 4. Hysteresis Thresholding: The final step is to decide which of the thinned lines are actual edges
and which are not. For this, two thresholds are used: a high threshold and a low threshold.
• Any edge pixel with a gradient magnitude greater than the high threshold is considered a
”strong” edge pixel and is immediately included in the final edge map.
• Any edge pixel with a gradient magnitude below the low threshold is discarded.
• Any edge pixel with a gradient magnitude between the two thresholds is considered a ”weak”
edge pixel. It is included in the final edge map only if it is connected to a ”strong” edge pixel.
This technique helps in connecting broken edges and eliminating spurious edges caused by noise.

3.11.1 The Effect of Scale (σ)

The smoothing parameter, σ, plays a crucial role in the Canny edge detector as it determines the ”scale”
at which edges are detected.

• A small σ (e.g., 1) results in less smoothing. This allows the detector to find fine, sharp edges and
detailed textures. However, it is also more sensitive to noise.
• A large σ (e.g., 4) results in more significant smoothing. This causes the detector to miss fine
details but allows it to identify larger, more prominent edges, making it less sensitive to noise.

This phenomenon is related to the ”scale space” of an image. By adjusting the parameter σ, the
Canny detector can be tuned to extract edges corresponding to the specific scale of interest for a given
application.

Figure 3.25: Canny edge detector results for different values of the smoothing parameter σ.

61
3.12 Corner Detection
Beyond edges, another important type of feature in an image is a corner. A corner can be defined as a
point where two edges meet, or more generally, a point where there is a rapid change in image intensity in
more than one direction within a small local region. Unlike an edge, which has a consistent orientation,
a corner is a 2D feature. Detecting corners is crucial for tasks like image matching, object recognition,
and motion tracking.

Figure 3.26: Comparison of a flat region, an edge region, and a corner region.

3.12.1 Analyzing Image Gradients

To find corners, we analyze the image gradients, similar to edge detection. We look at a small window
of pixels and examine the distribution of the gradients within that window. We compute the image
derivatives with respect to x (Ix ) and y (Iy ).
For different types of image regions, these gradients behave differently:
• Flat Region: Gradients are very small in all directions.
• Edge Region: A strong gradient exists in one direction (perpendicular to the edge), but gradients
are small along the edge direction.
• Corner Region: Strong gradients exist in multiple directions.

3.12.2 Distribution of Image Gradients

If we plot the gradient vectors (Ix , Iy ) for all pixels within a window, we can visualize the structure of
the region.

• In a flat region, the gradient vectors are all close to the origin (0,0), forming a compact cluster.
• In an edge region, the gradients are large and aligned in a single direction, forming an elongated,
linear cluster.
• In a corner region, the gradients are large and point in various directions, resulting in a more
distributed, two-dimensional cluster.

3.12.3 Fitting an Ellipse to the Gradient Distribution

To quantify the shape of this gradient distribution, we can fit an ellipse to it. The shape and size of
the ellipse will tell us what kind of region we are looking at. This is achieved by analyzing the second
moment matrix, also known as the structure tensor, of the image gradients within the window.

62
 Figure 3.27: Image gradients (Ix and Iy ) for flat, edge, and corner regions.

Figure 3.28: The distribution of gradient vectors for each of the three regions.

The second moments are calculated as:

X
a= (Ix2i )
i∈W
X
b=2 (Ixi Iyi )
i∈W
X
c= (Iy2i )
i∈W
63
 Figure 3.29: Fitting an elliptical disk to the distribution of gradients.

where W is the window centered at the pixel of interest.

From these values, we can compute the eigenvalues of the second moment matrix. These eigenval-
ues, λ1 and λ2 , correspond to the lengths of the semi-major and semi-minor axes of the fitted ellipse.
1 p
λ1 = Emax = [a + c + b2 + (a − c)2 ]
2
1 p
λ2 = Emin = [a + c − b2 + (a − c)2 ]
2

3.12.4 Interpreting the Eigenvalues

The values of λ1 and λ2 allow us to classify the local image region:
• Flat Region: Both λ1 and λ2 are small. The distribution is a small, circular cluster.
• Edge Region: One eigenvalue is large, and the other is small (λ1 ≫ λ2 ). The distribution is
elongated, forming a thin ellipse.

• Corner Region: Both λ1 and λ2 are large. The distribution is spread out in two directions,
forming a fat ellipse.

3.12.5 The Harris Corner Response Function

Harris and Stephens designed a response function, R, that maps the two eigenvalues to a single number,
avoiding the explicit calculation of the eigenvalues. A common form of this function is:

R = λ1 λ2 − k(λ1 + λ2 )2

where k is a tunable sensitivity parameter, typically in the range of 0.04 to 0.06.

By applying a threshold to the response value R, we can identify potential corners. If R is large and
positive, the region is likely a corner. If R is negative, it is likely an edge. If R is small, it is likely a flat
region.

64
 Figure 3.30: Classification of image regions based on the eigenvalues λ1 and λ2 .

Figure 3.31: The Harris corner response function R in the (λ1 , λ2 ) space.

3.12.6 Non-Maximum Suppression

A problem with the Harris detector is that it produces a high response not just at the corner’s exact
location but also in its immediate neighborhood, resulting in clusters of detected points.
To find the precise location of each corner, we apply a technique called non-maximum suppression.
This method is used to find local maxima in the response image. The procedure is as follows:
• Slide a window (e.g., 3x3 or 5x5) over the Harris response image R.
• At each position, if the value of the center pixel is the maximum value within the window, it is
retained as a corner.
• If the center pixel is not the maximum, its value is suppressed (set to zero).

65
 Figure 3.32: Harris corner detector response shows clusters around actual corners.

This process ensures that only the pixels with the peak response in their local neighborhood are selected
as the final corners.

Figure 3.33: Result of applying non-maximum suppression to the Harris response image.

3.13 Hough Transform

The Hough transform is a powerful feature extraction technique used in image analysis and computer
vision for detecting shapes that can be represented in a parametric form, such as lines, circles, or ellipses.
Developed by Paul Hough in 1962, it is particularly effective because it is robust to noise and tolerant
of gaps or occlusions in the feature boundary.
The fundamental idea is to transform the problem of detecting shapes in the image space into a
simpler problem of finding peaks in a parameter space (also known as Hough space). Each point in the
image space ”votes” for a set of possible parameters that could define a shape passing through it.

3.13.1 Line Detection: The Core Concept

Let’s consider the simplest case: detecting straight lines. A common way to represent a line is using the
slope-intercept form:
y = mx + c (3.34)

66
 (a) A set of edge points in image space. (b) A potential line fitting the points.

Figure 3.34: The problem of fitting a line to a set of points.

Here, the parameters defining the line are the slope m and the y-intercept c. The task is to find the pairs
(m, c) that best fit the set of edge points detected in an image.
The Hough transform uses a clever duality. Instead of working in the image space (x, y), it works in
the parameter space (m, c). A single point (xi , yi ) in the image space can be part of an infinite number
of lines. If we rearrange the line equation, we get:

c = −xi m + yi (3.35)

This equation shows that a single point (xi , yi ) in the image space corresponds to a single line in the
(m, c) parameter space.
The key insight is this: if multiple points (x1 , y1 ), (x2 , y2 ), . . . are collinear in the image space (i.e.,
they lie on the same line with parameters m∗ and c∗ ), their corresponding lines in the parameter space
will all intersect at a single point (m∗ , c∗ ).

3.13.2 The Line Detection Algorithm

The conceptual idea of finding intersections is implemented using a ”voting” procedure in a discretized
parameter space. This space is represented by a 2D array called an accumulator.

1. Quantize the parameter space: The parameter space (m, c) is divided into a grid of cells. Each
cell represents a specific pair of (m, c) values.
2. Initialize accumulator array: A 2D array, A(m, c), is created, with all its elements initialized
to zero. This array will store the ”votes.”
3. Vote for parameters: For each edge point (xi , yi ) in the image:
• For every possible quantized value of m, calculate the corresponding c using c = −xi m + yi .
• Increment the accumulator cell A(m, c) for each (m, c) pair that satisfies the equation.
4. Find local maxima: After all edge points have voted, the accumulator array is searched for cells
with high values. These local maxima correspond to the parameters of the lines that are most
likely present in the image. The value in the cell represents the number of points that lie on that
line.

3.13.3 A Better Parameterization: Polar Coordinates

The slope-intercept form (y = mx + c) has a major drawback: the slope m can be infinite for vertical
lines. This would require an infinitely large accumulator array. To solve this, a different parameterization
is used—the polar or normal form of a line:

x cos θ + y sin θ = ρ (3.36)

67
 (a) A single point (xi , yi ) in image space. (b) The corresponding line in parameter space (m, c).

Figure 3.35: The duality between points in image space and lines in parameter space.

(b) Intersecting lines in parameter space, identifying

(a) Collinear points in image space. the line’s parameters (m, c).

Figure 3.36: Collinear points in image space correspond to a single intersection point in parameter space.

68
Figure 3.37: Multiple lines in image space (left) correspond to multiple peaks in the accumulator (right).

Figure 3.38: The polar parameterization of a line.

Here, ρ (rho) is the perpendicular distance from the origin to the line, and θ is the angle of this perpen-
dicular vector with the x-axis.
This parameterization is advantageous because the parameters are bounded. For any image, θ can
range from 0 to 180◦ (or 0 to π radians), and ρ can range from −D to +D, where D is the length of the
image diagonal. This makes the accumulator array finite and manageable.
In this (ρ, θ) space, a point (xi , yi ) from the image space is transformed into a sinusoidal curve defined
by:
ρ = xi cos θ + yi sin θ (3.37)
Collinear points in the image space will correspond to sinusoidal curves that intersect at a common point
(ρ, θ) in the parameter space. The rest of the algorithm (quantization, voting, and finding maxima)
remains the same.

3.13.4 Generalization to Other Shapes

The Hough transform can be extended to detect other shapes with analytical descriptions. For example,
a circle is defined by:
(x − a)2 + (y − b)2 = r2 (3.38)
This gives a 3D parameter space (a, b, r), where (a, b) is the center and r is the radius. In this case, each
edge point (xi , yi ) votes for all possible circles it could lie on, which forms a cone in the 3D parameter
space. The intersection of these cones gives the parameters of the circle.

69
 However, the computational complexity and memory requirements increase polynomially with the
number of parameters. This ”curse of dimensionality” makes the classical Hough transform practical
only for simple curves with few parameters.

3.14 SIFT: Scale-Invariant Feature Transform

While edges and corners are fundamental features, recognizing complex objects under varying condi-
tions requires more descriptive and robust features. Simple template matching fails when an object’s
appearance changes due to variations in scale, rotation, illumination, and occlusion. The Scale-Invariant
Feature Transform (SIFT), developed by David Lowe, is a powerful algorithm designed to detect and
describe local features in images that are invariant to these transformations.

3.14.1 What is an Interesting Point?

The core idea is to find ”interest points” or ”keypoints” that are distinctive and can be reliably matched
across different views of an object or scene. A good interest point should possess several key attributes:

• Rich Content: The local patch around the point should have significant brightness or color
variation, making it distinctive. Uniform or weakly textured patches are not interesting.
• Well-defined Position: The point must be precisely localizable in the image. Simple edges are
poorly localized along their length (the aperture problem).
• Invariance to Scale and Rotation: The feature’s description (its signature) should remain the
same even if the object is scaled or rotated.
• Insensitivity to Lighting Changes: The signature should be robust to changes in brightness
and contrast.

SIFT identifies interest points by finding features that resemble ”blobs”—regions that are stable
across different scales. To be useful, a blob-like feature needs:
1. A defined location (position).

2. A defined size (scale).

3. A defined orientation.
4. A descriptive signature that is independent of its size and orientation.

3.14.2 Detecting Blobs using Scale-Space

The foundation of SIFT’s scale invariance is the concept of a scale-space. A scale-space is a stack of
images generated by convolving the original image I(x, y) with Gaussian filters of increasing standard
deviation, σ.
S(x, y, σ) = n(x, y, σ) ∗ I(x, y) (3.39)
As σ increases, the image becomes more blurred, and fine details disappear, revealing larger-scale struc-
tures.
To find blobs, SIFT uses the Laplacian of Gaussian (LoG) operator. The LoG operator is a blob
detector whose response is maximized when the scale of the operator (σ) matches the size of the blob
in the image. To make responses comparable across different scales, the operator is normalized by σ 2 .
The goal is to find local extrema (maxima or minima) of the scale-normalized LoG response across both
space (x, y) and scale (σ).

(x∗ , y ∗ , σ ∗ ) = arg max σ 2 ∇2 nσ ∗ I(x, y) (3.40)

(x,y,σ)

Here, (x∗ , y ∗ ) is the position of the blob, and σ ∗ is its characteristic scale, which is proportional to
the blob’s size.

70
 (b) ”Blobs,” regions with distinct texture or intensity,
(a) Edges are not ideal as they cannot be localized are better candidates as they have a well-defined posi-
along their length. tion and size.

Figure 3.39: Comparing edges and blobs as interest points.

Figure 3.40: The response of the normalized 2nd derivative (1D LoG) for blobs of different sizes. The
response peaks when the filter’s scale σ matches the blob’s size.

71
3.14.3 The SIFT Detector: Implementation with DoG
Directly computing the LoG at many scales is computationally expensive. SIFT uses a highly efficient
approximation: the Difference of Gaussians (DoG). The DoG is calculated by subtracting two nearby
images in the Gaussian scale-space, which is a good approximation of the scale-normalized LoG.

DoG = S(x, y, sσ) − S(x, y, σ) ≈ (s − 1)σ 2 ∇2 S (3.41)

where s is a constant multiplier between scales.

The SIFT interest point detection process is as follows:

1. Build Scale-Space and DoG Pyramid: The original image is convolved with Gaussians of
increasing σ to create a scale-space. The DoG images are then generated by subtracting adjacent
Gaussian images.
2. Find Local Extrema: Each pixel in the DoG stack is compared with its 26 neighbors (8 in the
same image and 9 in each of the images above and below). If it is a local maximum or minimum,
it is selected as a keypoint candidate.
3. Refine and Filter Keypoints: The keypoint candidates are refined to achieve sub-pixel accuracy.
Weak extrema (low-contrast points) and points located on edges (which are poorly localized) are
discarded. This results in a final set of stable SIFT interest points.

3.14.4 The SIFT Descriptor: Creating a Robust Signature

After detecting keypoints, SIFT computes a descriptor for each one, which is a signature of the local
image appearance. This descriptor is designed to be highly distinctive and invariant to the remaining
variations, like rotation and illumination.

1. Assigning a Principal Orientation: To achieve rotation invariance, a canonical orientation is

assigned to each keypoint. This is done by computing the gradient magnitudes and orientations
in a neighborhood around the keypoint. A histogram of these orientations (weighted by gradient
magnitude) is created, and the peak of this histogram defines the keypoint’s principal orientation.
2. Creating the Descriptor Vector:
• An image patch around the keypoint is taken, scaled according to the keypoint’s characteristic
scale, and rotated to align with its principal orientation. This normalizes for scale and rotation.
• This normalized patch (typically 16x16 pixels) is divided into a 4x4 grid of subregions.
• For each of the 16 subregions, an 8-bin orientation histogram is computed.
• These 16 histograms are concatenated into a single 128-dimensional vector (16 × 8 = 128).
• This vector is normalized to unit length to make it robust to illumination changes (e.g.,
changes in brightness and contrast).

This 128-element vector is the final SIFT descriptor.

3.14.5 Matching SIFT Descriptors

To find corresponding features between two images, their SIFT descriptors are compared. A common
method is to calculate the Euclidean (L2) distance between two descriptor vectors.
sX
d(H1 , H2 ) = (H1 (k) − H2 (k))2 (3.42)
k

A smaller distance indicates a better match. To ensure robust matching and reject ambiguous cases,
Lowe proposed a ratio test: for a keypoint in the first image, find its nearest and second-nearest neighbors
in the second image. If the ratio of the distances (distance to nearest / distance to second-nearest) is
below a threshold (e.g., 0.8), the match is accepted. This ensures that the match is distinctive.

72
Figure 3.41: The characteristic scale σ ∗ at which the response is maximal is directly proportional to the
size of the blob.

Figure 3.42: The Difference of Gaussians (DoG) is an excellent and efficient approximation of the Nor-
malized Laplacian of Gaussian (NLoG).

Figure 3.43: From the input image, a Gaussian scale-space is created, from which the Difference of
Gaussians (DoG) stack is computed.

73
 Figure 3.44: Local extrema are found by checking a 3x3x3 neighborhood in the DoG stack.

Figure 3.45: Weak extrema are removed, leaving the final SIFT interest points, each with a specific
location and scale (indicated by the circle’s radius).

74
Figure 3.46: A histogram of gradient orientations in the keypoint’s neighborhood is used to find its most
prominent, or principal, orientation.

Figure 3.47: The SIFT descriptor is created by concatenating orientation histograms from a 4x4 grid of
subregions around the keypoint.

75
 (a) Scale Invariance. (b) Rotation Invariance.

Figure 3.48: SIFT provides excellent matching results despite large changes in scale and rotation.

(a) Matching SIFT features between images. (b) Warping and blending to create a panorama.

Figure 3.49: Panorama stitching using SIFT.

76
3.14.6 SIFT in Practice
SIFT has proven to be extremely effective in a wide range of applications due to its robustness.
One of the most popular applications is panorama stitching, where SIFT features are matched
across multiple images of a scene to align them and create a single, seamless panoramic image.
Despite its power, SIFT is primarily designed for 2D (planar) objects or scenes viewed from similar
viewpoints. It is less reliable for 3D objects viewed from significantly different angles, as the local
appearance of features can change dramatically with large changes in viewpoint.

77