Marco Pavone clashes classical vision with neural networks

Marco Pavone对比经典视觉与神经网络 尽管卷积神经网络为自主导航提供了无与伦比的语义处理能力，但其不可解释的黑箱特性带来了关键的安全验证障碍，而经典的确定性滤波器则避开了这些问题。 Marco Pavone教授详细介绍了自主机器人领域使用的经典图像处理流程，涵盖空间线性滤波、移动平均、高斯核，以及掩模可分离性与卷积结合律所带来的数学计算效率提升。随后，他解析了利用离散梯度、阈值化和非极大值抑制进行边缘检测的方法，以及诸如Harris角点检测器等角点检测算法，还有用于视觉里程计的SIFT和ORB等不变性描述子。讲座最后将具有可解释性且在数学上可验证的经典滤波器与现代卷积神经网络进行了对比，重点指出了在DARPA资助的自主飞机滑行研究背景下持续面临的安全保障与可解释性挑战。 在数值微分前使用高斯核进行图像平滑是一道必不可少的预处理工序，旨在防止高频图像噪声被极度放大。 (8:42) 卷积的代数结合律允许将平滑和求导操作合并为一步完成，即直接用解析求导得到的高斯掩模与图像进行卷积。 (24:45) 掩模的可分离性使得二维 $m \times m$ 卷积能够分解为两个连续的一维卷积通道，从而将每个像素的操作次数从 $m^2$ 降至 $2m$。 (26:34) 虽然像Harris检测器这样的经典算法具备旋转和光照强度不变性，但它们缺乏尺度不变性，因此在跨尺度匹配和视觉里程计中需要使用SIFT或ORB等描述子。 (59:06) 深度卷积神经网络执行与经典视觉相同的基本滤波流程，但其缺乏可解释性，在自主飞机滑行等关键任务应用中带来了严峻的安全保障挑战。 (68:16)

In Stanford's AA274A course, Prof. Marco Pavone presents classical image processing as a structured pipeline running from noise-suppression filtering to feature detection and description, establishing the deterministic geometric foundations required for robotic perception before contrasting them with deep learning. Spatial Filtering, Associativity, and Mask Separability (8:42) Digital images are represented as 2D functions mapping pixel coordinates to intensity values, from 0 (black) to 255 (white). Because downstream feature detection relies on image derivatives that severely amplify high-frequency noise, spatial smoothing is required as an initial pre-processing step. Linear spatial filters execute localized weighted sums across odd-sized neighborhoods, such as $(2N+1) \times (2N+1)$, with missing edge values handled by strategies like zero-padding, cropping, or circular wrapping. Moving average filters apply uniform weights, whereas Gaussian filters decay weights radially based on standard deviation $\sigma$. Unlike cross-correlation, 2D convolution mirrors the kernel, conferring associativity: $(I * G) * F = I * (F * G)$. This property allows vision systems to differentiate a compact smoothing filter analytically before convolving it with the image, bypassing two sequential full-image operations. Computational efficiency improves further when spatial masks are separable into outer products of 1D vectors (such as moving average and Gaussian kernels). Decomposing an $m \times m$ 2D mask into two successive 1D convolutions slashes operations from $m^2 W H$ to $2m W H$ across an image of size $W \times H$. Edge Extraction via Analytical Derivatives and Post-Processing (41:58) Edges correspond to sharp intensity transitions marked by high first-order derivatives and zero-crossings in the second-order derivative. To detect them robustly, algorithms must satisfy three core criteria: accuracy, precise localization, and a single response per physical edge. Rather than taking noisy numerical differences on raw images, systems convolve the image with differentiated 2D Gaussian masks along horizontal and vertical axes to produce gradient maps $s_x$ and $s_y$, or employ Sobel operators that combine directional smoothing with central finite differences. The overall edge magnitude is combined per-pixel via $\sqrt{s_x^2 + s_y^2}$. Downstream post-processing applies a designer-tuned threshold $h$ to balance false positives against false negatives, followed by non-maximum suppression within local neighborhoods. This final step suppresses non-peak responses, thinning gradient clusters into precise, single-pixel boundary representations. Keypoint Detection, Descriptors, and Invariance Limits Beyond boundaries, visual navigation relies on localized keypoints that satisfy repeatability across differing camera poses and distinctiveness within their local neighborhoods. While flat regions exhibit no directional change and edges show change in only one orthogonal direction, corners register sharp intensity variations across all directions. The Harris corner detector identifies these points using eigenvalue decomposition of the local second-moment matrix. This makes it invariant to image rotations and uniform intensity shifts, but it fails under scale variations because fixed window sizes cannot distinguish between a zoomed-in corner and a straight edge boundary. Once keypoints are localized, descriptors generate representations to enable matching across frames for tasks like visual odometry and stereo reconstruction. Raw pixel intensity patches degrade rapidly under perspective and illumination changes. Advanced descriptors such as SIFT encode 128-dimensional local gradient distributions to guarantee scale and rotation invariance at a higher computational expense. In high-contrast environments—such as asteroid-hopping rovers transitioning between pitch-black space and bright surface reflections—Prof. Pavone notes that alternative descriptors like ORB demonstrate superior robustness against extreme lighting swings. The Shift to CNNs and Autonomous Safety Verification (66:32) Deep convolutional neural networks (CNNs) mirror classical pipelines by performing filtering, feature detection, and semantic extraction, but they replace hand-crafted analytical operators with data-driven learned weights. While CNNs dominate modern industry applications by excelling at complex semantic scene segmentation and 3D bounding box prediction, they shift visual autonomy from deterministic engineering into data engineering, requiring massive labeled datasets. This empirical reliance creates verification challenges in safety-critical autonomous systems. Early CNN layers often learn filters resembling classical smoothing and derivative kernels, yet deeper layers function as uninterpretable black boxes. Under federal research initiatives like the DARPA Assured Autonomy program, Prof. Pavone investigates scenarios such as autonomous aircraft taxiing, where forward-facing cameras guide nose-wheel steering along a runway centerline. While classical edge detection offers mathematically verifiable guarantees, neural network controllers risk outputting catastrophic steering commands when exposed to anomalous pavement reflections, glare, or snow without formal safety wrappers. Classical vision pipelines provide transparent mathematical guarantees and computational efficiency for feature tracking and visual odometry, whereas deep learning excels at complex semantic reasoning. A central unresolved engineering challenge remains bridging this divide: developing formal verification methods and safety assurances that prevent uninterpretable neural network failures in safety-critical autonomy.

斯坦福大学Marco Pavone教授系统阐明了机器人自主感知管线中经典图像处理的核心机制，涵盖空间滤波、边缘与角点检测及特征描述符的数学原理与计算权衡。他指出，尽管以卷积神经网络为代表的深度学习在语义理解中占据主导，但经典算子的可解释性与确定性数学边界在安全攸关任务中仍具不可替代的工程价值。 空间线性滤波与结合律优化 (12:41) 数字图像在计算层面上被形式化为离散二维强度函数，其灰度范围通常为0至255。空间线性滤波本质上是利用大小为(2N+1)×(2N+1)的核掩码在像素局部邻域内执行加权求和运算。相比均值滤波采用均匀权重可能诱发不自然的矩形模糊伪影，高斯平滑滤波依据连续二维高斯分布衰减权重，通过标准差参数控制平滑宽度，成为抑制传感器高频噪声的通用预处理手段。针对核掩码超出图像边缘的边界问题，工程上常用零填充（Zero-padding）、裁剪（Cropping）、边界延拓或循环环绕等策略解决。 Pavone教授辨析了互相关与卷积的关键数学差异：卷积在滑动前需将核掩码沿水平与垂直双向翻转，这赋予了其代数结合律特性。在边缘检测等组合操作中，系统无须先平滑整幅大图再逐像素求导，而是可以直接对尺寸紧凑的高斯核求解析导数，单次卷积即可完成平滑与微分复合运算。此外，高斯与均值核均具备可分离性，可将二维m×m卷积分解为行向与列向两次一维卷积，使单像素运算量从m²降至2m，在百万像素规模的整图处理中能实现数倍至数十倍的算力节省。 离散微分机制与边缘检测管线 (41:58) 物理边缘在图像中体现为强度的剧烈跳变，数学上表现为一阶导数的极大值与二阶导数的零交叉点。由于数字图像为离散点阵，梯度计算依赖有限差分实现；相较于单侧前向或后向差分，对称的双侧中心差分对离散跳变展现出更高的稳健性。经典的Sobel算子实质上是在求导方向应用离散差分的同时，在正交方向叠加高斯平滑加权，从而构筑了抗噪能力更强的微分掩码。由于直接对含噪信号求差分会灾难性地放大高频噪声，工程标准方案是采用高斯导数滤波器（Derivative of Gaussian, DoG），利用结合律在单次滤波中完成噪声滤除与梯度提取。 在二维空间中，算法分别沿横向与纵向应用正交的高斯导数核输出分量sx与sy，再通过逐像素求欧氏范数得到梯度幅值图。后续处理包含两个关键阶段：首先是阈值化（Thresholding），设定设计者参数h滤除微弱响应，在假阳性与假阴性之间平衡检出精度；随后引入非极大值抑制（Non-Maximum Suppression, NMS），在像素邻域内仅保留沿梯度方向的局部峰值，从而消除模糊扩散，输出单像素宽度的紧凑边缘线。 角点检测不变性与特征描述符 与边缘仅在单一正交方向存在强度跃变不同，角点被定义为在所有移动方向上均呈现强烈强度变化的特征，是立体视觉与定位建图的关键基元。合格的检测器必须兼具重复性（跨视点稳定检出）与显著性（特征局部足够独特以避免匹配混淆）。Harris角点检测器通过分析局部窗口二阶矩矩阵的特征值，实现了对图像平面旋转和全局均匀亮度偏移的数学不变性。然而，Pavone教授指出其关键短板在于缺乏尺度不变性：当相机向目标靠近时，原先尺寸核窗口内的尖锐角点在近距离视域下会退化为平缓边缘，导致跨视点匹配彻底中断，无法维持视觉里程计等下游任务的稳定性。 检测到关键特征点后，算法需通过描述符表征其邻域信息以支持跨图数据关联。直接存储原始像素块对光照、透视和尺度极度敏感；现代算子如SIFT将局部梯度方向分布编码为128维特征向量，具备出色的尺度与旋转不变性，但计算成本高昂。Pavone教授结合其在NASA JPL参与小行星跳跃探测器研发的经历指出，在小行星表面从深空漆黑瞬间切换到剧烈镜面反光的极端光照工况下，ORB特征在动态光照耐受度与计算实时性上展现出显著优势，说明实际机器人系统需根据具体环境边界在算法鲁棒性与计算资源间审慎权衡。 深度学习范式转型与安全验证 (66:32) 计算机视觉在2010至2012年间转向以深度卷积神经网络（CNN）为核心的学习范式。CNN在底层功能上承接了经典管线中的滤波、特征检测与描述，但将人工设计的数学算子替换为基于海量数据端到端优化习得的权值。CNN在语义分割以及2D/3D目标边界框检测等高层语义感知任务上展现出压倒性优势，已成为自动驾驶与移动机器人感知的工业界标准，但这同时也使计算机视觉从严密推导的分析几何学转变为依赖数据标注与网络优化的实证工程。 深度神经网络的黑盒属性在安全关键型系统中引发了可解释性与系统验证难题。虽然训练完成的浅层CNN卷积核通常自发收敛为类似于Sobel或高斯导数的边缘平滑模式，但更深层网络的决策路径完全无法进行形式化分析。在DARPA“有保证的自主性”（Assured Autonomy）研究框架下，Pavone教授探讨了自主飞机地面跑道滑行的视觉闭环控制案例：当前置相机配合PD控制器根据跑道中心线调整前轮偏转时，经典边缘检测算法的行为完全透明且可被数学证明；相反，纯深度神经网络在遭遇反光、跑道积雪或非常规光照波动等未见扰动时，可能突发灾难性转向跳变，凸显了安全关键自主架构中融合确定性物理边界与安全包络的必要性。 自主机器人的视觉感知技术正处于经典解析几何与现代数据驱动方法的交汇点。经典空间滤波与特征提取算法依靠清晰的数学性质与低算力开销，为底层几何定位提供了具备严格因果解释的可靠基石；深度神经网络则主导了高维语义推理。在严苛物理约束与多变真实工况下，如何兼顾端到端学习模型的语义感知能力与经典解析算法的形式化安全边界，仍是自主系统迈向完全可靠落地的核心挑战。

[24:45] Prof. Marco Pavone: It turns out that depending on the sequence with respect to which you carry out convolution you might require less operations so it runs faster. [55:33] Prof. Marco Pavone: So corner is basically defined as a part of the image where you have changes in all directions, and you exploit this definition in order to design a corner detector. [7:07] Prof. Marco Pavone: An image from the purposes of the image processing pipeline is represented as a two-dimensional function that maps each row column value into an integer that corresponds to the intensity value for that pixel.

[0:05] So today we're going to continue our [0:07] discussion on computer vision. In [0:10] particular, last week [snorts] we talked [0:13] about how to uh the mathematical [0:18] transformation that allow us to map [0:20] points in the 3D world onto uh a camera [0:24] image and most importantly how to [0:27] leverage that mathematical mapping in [0:30] order to reconstruct the environment in [0:33] 3D once we have access to 2D images. [0:38] Now this is a very important process [0:40] because one of the most fundamental [0:42] tasks that you want to achieve with a [0:45] vision sensor is that of reconstructing [0:48] the environment. But that is only one of [0:51] the tasks that you want to achieve with [0:53] a vision sensor. There are many more and [0:55] in particular through vision you are [0:58] interested in detecting uh objects that [1:02] can be used in order to reason [1:05] semantically about environment. in [1:07] particular is a blob human or an object [1:11] and what are the implications in terms [1:13] of decision making. So in order to do so [1:16] we have to dig a little bit deeper about [1:20] how to extract information from uh [1:22] images. In particular, uh the topic of [1:26] today is to learn how to first of all [1:30] filter images in order to remove for [1:32] example noise that might affect the [1:35] information that we extract from an [1:37] image and second how to detect and [1:40] describe key features of an image such [1:43] as a corner edges and so on. On [1:47] Thursday, we'll see how to use this [1:49] information in order to reason at a [1:51] higher level about the reconstruction of [1:54] environment like how do we start [1:56] extracting lines that can be used for [1:58] localization or how do we identify [2:01] whether there is a person in an image [2:03] and so on. So today is mostly geometric [2:06] understanding on Thursday will be mostly [2:08] a semantic understanding. [2:11] Now how do we represent um images? Well, [2:16] the raw output of an image sensor is a [2:19] collection of pixels. But in practice, [2:22] we want to describe images in a more [2:25] succinct way and in particular in terms [2:27] of features that can be used, for [2:29] example, to match points of interest [2:32] across images and can be used in order [2:35] to uh detect whether a certain part of [2:38] an image correspond to a person, an [2:41] object and so on and so forth. typical [2:44] features that you would like to extract [2:45] are for example corners, edges, blobs [2:48] and so on and so forth. [2:51] So for example here in the in this image [2:53] of a butterfly I'm showing the typical [2:56] output of an image detector where you [2:59] can see how the image detector in [3:00] question is picking up a number of uh [3:04] salient uh features or key points of the [3:07] image that can be used later on in [3:09] downstream application in order to do [3:12] semantic uh understanding. [3:15] Now an image processing pipeline at the [3:18] end of the day consists of four main [3:21] steps. The first step is the first is [3:24] the step of image filtering. Basically [3:27] we want to clean up or in other words uh [3:31] modify the image in order to ease the [3:35] downstream task of future uh detection [3:38] description and uh later on higher level [3:41] processing. [3:43] At the very least we want for example to [3:45] remove noise from an uh from an image. [3:48] The second step is the step of detecting [3:52] uh key features or equivalently referred [3:54] to as key points as I said corners edges [3:58] and so on. They can be used across [4:00] images for uh stereo correspondences or [4:04] for structure from motion or can also be [4:06] used in order to detect uh objects. [4:10] The third step is a step a step step of [4:12] future description. So once we have [4:15] detected a feature, we want to be able [4:18] to describe it with photometric [4:21] quantities like for example local [4:23] gradients around it in a way that allow [4:25] us to match that future with the same [4:28] feature in another image. So for [4:31] example, we take an image and then we [4:33] take another image from a different [4:36] pose. The point is that if there is a [4:39] corner that we want to track, we want to [4:41] be able to establish a correspondence [4:43] between that corner in the first image [4:44] and a corner in the second image. To do [4:46] so, we need to be able to describe [4:49] locally what that image looks looks like [4:51] in order to have a robust matching [4:53] between the same feature in two [4:55] different images. [4:57] Make sense? [5:00] Future detection means there is a [5:01] corner. Future description means well [5:03] this corner has this specific [5:05] properties. For example, there is a lot [5:06] of yellow around it. So that when I see [5:10] another corner in another image with a [5:12] lot of yellow around it, most likely [5:14] those two corners are indeed the same [5:16] just image into different images. [5:19] And based on that, then we can have [5:21] matching pairs that can be used for a [5:23] number of applications. For example, [5:25] serial reconstruction. The fourth step, [5:27] and this is the step that we look at on [5:30] Thursday, is the one or high level [5:32] processing. Now that we're able to [5:34] detect futures, robustly track them [5:36] across images, how do we use them for [5:39] high level processing such as [5:42] localization or uh object detection and [5:45] so on. [5:47] So today we're going to focus on the [5:48] first three steps and on Thursday we're [5:50] going to focus on the fourth step. [5:53] Let's start then uh with the first step [5:56] which is the step of image processing [5:59] that in a nutshell entails accepting or [6:03] rejecting uh certain frequency [6:05] components. So if you're familiar with [6:07] signal processing this is very similar [6:09] to what is done to uh signals like for [6:13] example electromagnetic waves. you [6:16] filter them out in order to keep some [6:18] frequency components in order to for [6:20] example remove noise or for example make [6:22] sure that within the same channel you [6:24] can transmit multiple signals at [6:26] different frequencies. The difference [6:28] here though is that instead of dealing [6:30] with a a signal in time we're dealing [6:34] with an image. [6:38] So the idea of filtering practically [6:40] corresponds to finding a new image whose [6:45] pixels are a combination of the pixels [6:47] of the previous image. In particular, [6:49] the key idea is to represent an image as [6:52] a two-dimensional uh function that maps [6:57] uh row coordinates and pixel coordinates [7:00] into intensity values. So for example, [7:03] consider this image here which is in [7:06] grayscale. [7:07] This image is a bunch of pixels. Each [7:11] pixel is labelled by a row referred to [7:15] as I and a column referred to as J. [7:20] And each pixel is stored in the computer [7:23] with a number which represent the gray [7:28] level typically between 0 to 155. [7:32] Okay. So zero corresponds to black, 255 [7:36] corresponds to white. [7:39] If you have a colors, then you should [7:42] think of having three of these tables, [7:46] one on top of each other, each one for [7:48] the three fundamental colors like red, [7:50] blue, and so on. An equation about this [7:54] this fundamental. So an image from the [7:56] purposes of the image processing [7:59] pipeline is represented as a [8:01] two-dimensional function. that maps each [8:05] um row column value into an integer that [8:10] corresponds to the intensity value for [8:12] that pixel. If you use grayscale will be [8:14] a number between 0 and 255. [8:17] Then with this interpretation then uh [8:20] filtering corresponds to producing an [8:23] output image that takes as an input [8:27] input image and applies some [8:29] transformation of the pixels in the [8:31] input image according to some rules that [8:33] I'm going to discuss in a second. [8:39] All right. So [8:42] filtering can be done in fundamentally [8:44] two ways either in the frequency domain [8:46] or in the special domain. Again if [8:48] you're familiar with signal processing [8:51] you know that often times filtering is [8:53] done in the frequency domain whereby you [8:55] take the FIA transform of your signal [8:58] then you operate in the FIA domain and [9:01] then you transform back the signal to [9:03] the time domain. [9:06] If you're not familiar with the FIA [9:08] transforms, it's not a problem because [9:09] in this class actually we're going to [9:11] focus on filters in the special domain, [9:15] meaning without leveraging FIA [9:17] transforms. FY transforms are indeed [9:19] quite useful. For example, when I was [9:22] working um at JPL and was doing a lot of [9:26] image processing on the images taken by [9:28] the orbiter Amaro around Mars. Um, in [9:33] order to make computation efficient, [9:34] what I was doing was to take discrete FA [9:37] transforms on the images, do all the [9:38] image processing pipeline in the FA [9:40] domain, which is much faster, and then [9:42] convert it back into the uh special [9:44] domain. But anyway, so this is beyond [9:46] the scope of this class. So in this [9:48] class, we're going to focus on special [9:50] uh feeders. A special filters is [9:53] relatively simple and it consists of two [9:56] main ingredients. The first ingredient [9:58] is a neighborhood of a pixel under [10:01] examination which I refer here as S [10:04] subscript of XY. [10:06] S of XY is a neighborhood that for a [10:09] given pixel with the coordinates XY [10:12] associate a set of neighboring pixels. [10:18] For example, this could be a rectangle [10:20] with a 3x3 neighborhood. [10:23] the pixel xy itself and then one pixel [10:26] to the right, one pixel to the left and [10:27] the three on top and the three on the [10:29] bottom. [10:32] The second step is then a predefined [10:36] operation on the uh image pixels [10:39] encompassed by that uh neighborhood. [10:44] So for example here I'm taking this [10:47] image as an input with offs and coins. I [10:50] consider a rectangular uh neighborhood [10:54] and I consider as operation that of [10:58] smoothing. So in particular the [11:01] operation sxy [11:03] entails. [11:09] So say that s of xy [11:12] is [11:13] a 3x3 [11:16] neighborhood with [11:19] the pixel with coordinate xy at the [11:21] center. [11:25] Then a possible operation is to multiply [11:29] each one of the intensities of the [11:32] neighborhood pixels including XY pixels [11:34] by one and then divide by nine the sides [11:38] of the neighborhood. [11:40] So what we're doing here is basically [11:42] just taking the special average of the [11:44] intensities around pixel xy. So this [11:47] correspond to smoothing and we'll see [11:49] that more formally later. [11:52] So the so the end result will be uh this [11:56] image which looks a bit blurred. So you [11:59] might say why on earth you buy an [12:01] expensive camera in order to get an [12:04] image that is very crisp and then [12:06] through image processing you get [12:07] something that is blurred. Do you have [12:09] an idea why that could be useful? [12:14] >> Well yes down sampling could be one [12:16] reason. [12:19] >> Exactly. remove noise. So as we will see [12:22] in order to detect features like for [12:23] example edges you're trying to look at [12:27] parts of an image where you have [12:28] discontinuity in the intensities which [12:32] basically entail looking at the notion [12:35] of derivative for an image. But as you [12:38] may know taking a derivative amplifies [12:41] noise. So before taking a derivative, [12:43] you want to smooth out your inputs. For [12:45] example, with a uh average [12:48] filter, [12:52] specifically within the special within [12:55] the domain of special filters, special [12:57] filters can be either linear or [12:59] nonlinear. Linear means that we perform [13:02] an operation over the neighborhood of [13:04] pixels that is linear. Nonlinear means [13:07] that we perform a nonlinear operation. [13:09] In this class, we focus on linear [13:12] filters. So, we focus on special linear [13:14] filters. In particular, linear filters [13:17] is are filters that can be written as a [13:19] correlation between the input image [13:22] denoted as I and a mask or kernel or [13:27] window denoted as F. So, the notation [13:31] could be a little bit cumbersome, but [13:33] the notion is very easy and I will give [13:35] you an example in a second. So just to [13:38] fix uh the nomenclature capital n is uh [13:44] so specifically 2 n plus one is the [13:47] number of rows of the filter mask and 2 [13:49] n +1 is the number of columns on the [13:52] filter mask. [13:54] The filter mask is basically [13:58] another matrix that is smaller than [14:02] usually than your input image. [14:05] For example, in the case of example that [14:07] I just gave you, it was the matrix 3x3 [14:13] with all ones. [14:15] So what that formula is saying is [14:18] actually [14:20] encoding the operation that I just [14:22] mentioned before. You multiply each [14:24] pixel in neighborhood for the [14:26] corresponding component in the mask and [14:29] then you sum them out. [14:33] So it's an average basically correlation [14:35] you can see it as an average of the [14:37] instances in the pixel neighborhood. [14:42] Of course nobody tells you that you need [14:44] to have all ones. You can give weights [14:48] that are different and we will see later [14:50] on different how different filters give [14:52] different weights and how that [14:54] corresponds to different operations. So [14:56] just to make sure that uh [14:59] everyone is clear with this concept. So [15:01] let's consider this image. [15:03] where you have um say one two [15:09] one two one two one two one two [15:15] [snorts] [15:16] better [15:21] one two one two one one uh one one one [15:30] two one two one one one one one. [15:35] So that will be your input image [15:47] which we denote as I. [15:50] Let's consider as a mask f [15:55] the mask three by 3x3 where all the [15:58] numbers are one [16:01] which basically means that we consider a [16:03] neighborhood that is just a 3x3 [16:06] neighborhood basically rectangular [16:08] neighborhood. So let's assume that the [16:10] idea is to process each pixel one by [16:13] one. Let's let's assume that we are [16:15] processing this pixel here. [16:17] So how is this pixel mapped into the [16:21] output image Y prime? So what's the [16:24] value of this pixel? [16:29] So this will be the pixel with second [16:32] row and the third column. So in the [16:35] output image, what is the value of the [16:37] pixel second row and third column? [16:41] If we apply this mask and we consider [16:44] the process of correlation. [16:48] >> What's [clears throat] that? [16:49] >> Was it 13? [16:50] >> So we have 2 two two. So this is 8 [16:56] 9 10 11 12 13. [17:00] Yeah. [17:06] So what is a bit awkward here [17:10] is that uh by applying this mask we are [17:15] actually increasing the intensity [17:16] uniformly. We'll see later on how [17:19] actually the average filter should be [17:21] normalized in order to make sure that if [17:24] you apply it on a patch that has uniform [17:27] intensity you get the same intensity as [17:29] an output. But this is just to give you [17:32] an example of what mathematically this [17:34] formula uh means. [17:39] A natural equation is what do you do at [17:41] a boundary? So if you're here [17:45] say [17:48] you can think of applying this mask as a [17:50] superimposing this mask on your image [17:53] and then multiply the uh corresponding [17:57] components. [17:59] So here we're getting out the [18:02] neighborhood is getting out of the [18:03] domain of the image. So what do we do? [18:07] So what do we multiply this uh number [18:09] here, this number here and this number [18:11] here [18:12] in terms of the corresponding input [18:14] image I since I don't have values for [18:16] the input image I here. So this is a [18:18] little bit of a convention. In reality [18:21] the image is much larger than the mask. [18:23] So what happens at the boundary is not [18:25] that important. But you had to code [18:27] something for your code to run. So you [18:30] have a number of options. The easiest [18:32] one and the one that you would use in [18:33] your pet is just pad the image with the [18:36] zeros. [18:40] So just a larger image so that your [18:42] correlation operation is well defined [18:44] also along the boundaries. [18:48] But you can do also other stuff. You [18:49] could for example crop the image. So [18:53] just consider [18:57] this sub image here and then work on the [19:00] restricted image so that the boundary is [19:02] well defined. [19:04] Or you can extend it by using some [19:06] modified notion of extrapolation or if [19:10] you have a little bit more imagination [19:11] you can think of warping the image such [19:14] that uh this boundary becomes attached [19:19] to this boundary. [19:22] sometimes might make sense. Basically, [19:23] you would wrap it in this direction and [19:26] in that direction. [19:28] In reality, just padding with zeros is [19:30] the more natural option. So, it is [19:32] clear. Just want to make sure it's clear [19:34] because if this is not clear, then [19:35] everything else is going to be very uh [19:38] confusing. [19:43] So, the easiest way of thinking about uh [19:46] correlation is that uh we have an image [19:52] which is represented as a [19:53] two-dimensional function. [19:59] And then we consider a mask. [20:11] And then for each element of the mask, [20:13] we multiply the corresponding elements [20:16] of uh the image. [20:19] And then we center the mask at each [20:21] pixel of the input image. So basically [20:23] this is a moving mask that goes [20:25] throughout that is lead throughout the [20:28] image. [20:29] >> Yeah. [20:32] >> Convolution. [20:33] >> No convolution [20:36] as we will see in a second is when [20:38] instead of having a plus here we have a [20:41] minus which in other words correspond to [20:43] do a correlation with a mirrored version [20:46] of the mask. It's a tiny detail but it [20:49] turns out that uh defining it's still [20:52] the convolution is still a linear [20:53] filter. So it's still under the purview [20:55] of this class but turns out that that [20:58] slightly different definition of the [20:59] mathematical operation uh provides a [21:02] very important property that is that of [21:04] associativity that we're going to see in [21:05] a second. But strictly speaking this [21:07] formulation is formulation of [21:08] correlation. [21:12] All right. [21:14] So let's look at some example. First [21:16] example is the moving average uh filter [21:20] uh whereby the output image is the [21:24] average has pixel values that represent [21:26] the um average values of the pixels [21:30] as weighted by the mask. In particular, [21:33] the mask in the case of 3x3 is a mask [21:35] with the constant values which is [21:37] normalized in order to make sure that [21:39] the background intensity stays the same. [21:41] So if you apply this moving average [21:42] filter to an image with a constant [21:45] intensity say all equal to 50 as an [21:47] output we still get 50 an image with all [21:50] pixels equal to 50 [21:54] >> output value rounded or [21:58] >> well typic no the intensity are always [22:00] rounded. Yeah. [22:03] Uh all right so this is an important [22:06] [clears throat] uh uh filter but one may [22:09] argue that it's really weird that when [22:12] we take the average we give the same [22:15] weight to the pixels in at the boundary [22:18] of the neighborhood as we give to the [22:21] pixel whereby this mask is centered at. [22:25] So a more common um [22:29] uh smoothing mask is the so-cal gausian [22:32] smoothing mask whereby uh the idea is to [22:36] have as a mask something that gives more [22:38] weight to the pixel where the mask is [22:41] centered and less weight to the pixels [22:44] that are far from the center [22:46] in proportion to an underlying gausian [22:49] distribution. So think of a [22:51] two-dimensional gausian whose formula is [22:54] given here. As usual, sigma is the uh [22:58] standard deviation and it controls how [23:00] fat your distribution is. [23:04] The gausian mask is simply obtained by [23:06] taking the two dimensional gausian [23:08] distrib distribution and sampling it. [23:10] Like for example, if you use sigma equal [23:12] to 0.85, this is the gausian mask that [23:15] you get which is a very typical one. [23:18] Changing sigma basically changes the [23:20] values of uh these weights but the [23:24] intuition is the same that you give more [23:27] weight to the pixel where the mask is [23:30] centered and less weight to the [23:32] neighborhoods. As usual the mask is [23:34] normalized. If you sum all these numbers [23:37] you get 16. So when you divide by 16 you [23:39] still get one. in order to ensure that [23:41] if you apply this mask to something that [23:43] has a uniform intensity, you get as an [23:45] output something with the same intensity [23:47] value. [23:49] Now [23:51] as we mentioning before one of the most [23:54] fundamental operations in image [23:56] processing is to take derivatives which [23:58] means that uh uh since derivatives as [24:00] discussed might amplify noise um as we [24:04] will see more explicit in a second. The [24:06] first step is actually to smooth or to [24:08] blur that image. [24:11] The gausa mask is the most typical way [24:14] of doing so. So pretty much in any image [24:17] processing pipeline that uses classical [24:19] techniques as opposed to neural networks [24:21] that's the first pre-processing step [24:28] an equation about correlation as I said [24:30] the concept is simple but if you are [24:32] confused about annotation then [24:34] everything else becomes confusing [24:37] in the pet I will ask you to do by hand [24:40] a couple of correlations so that that [24:42] becomes super here [24:45] convolution. So convolution is another [24:48] natural uh special feature is very [24:51] similar to correlation. The only thing [24:54] is that we have we replace [24:57] the plus with the minus. [25:01] So instead of waiting the uh [25:07] so if this is our xy [25:14] So instead of um waiting, so this will [25:19] be our J. [25:24] Well, [25:25] this will be the um instead of waiting [25:28] it this pixel by this pixel, we actually [25:32] flip the way this uh um waiting is done. [25:37] Flip means a mirrored. [25:40] So it turns out so this operation is [25:42] conceptually the same just that we are [25:44] flipping the indices. It turns out that [25:46] this operation has the associativity [25:48] property meaning that convolving a mask [25:53] with the image input I and then [25:56] convolving the resulting image with F is [25:59] equal to first convolve the two masks F [26:02] and G and then use the convolved mask to [26:07] convolve it with I. the result is the [26:10] same. [26:12] So you might say who cares. So it turns [26:13] out that depending on the sequence with [26:16] respect to which you carry out [26:17] convolution [26:18] you might require less operations so it [26:21] runs faster [26:24] and in particular when we try to detect [26:26] the edges what we do is to smooth the [26:29] image and take a derivative. So instead [26:31] of smoothing the image and then take the [26:34] derivative of the smooth image, what you [26:36] do is to take the derivative of the [26:39] smoothing mask and then use that mask in [26:41] order to uh detect an edge. We will see [26:45] that in a few minutes. [26:51] >> Yeah. [snorts] [26:52] >> The associivity property why it's used [26:55] so much in applications like machine [26:58] learning. Well, one in in the case of [27:03] image processing application is one of [27:04] the reasons. Yeah, [27:10] >> we were going to define that formally. [27:12] >> Okay. Of course, since the image is a [27:16] discrete function whereby the domain is [27:19] discrete and the output is discrete, the [27:22] derivative cannot be defined in the same [27:24] way that is defined in calculus because [27:26] the notion of limit for an increment [27:27] that tends to zero is not well defined. [27:29] So we will consider a discrete [27:31] definition for a derivative. [27:33] >> The question I was more thinking about [27:34] is the fact that there's both an x and a [27:35] y. So don't need like a derivative but a [27:38] gradient. [27:39] >> Oh yeah, sure. Of course. Yeah, that [27:41] concept carries forward here because we [27:44] inter two dimensional function. [27:47] All right, so it turns out that some [27:50] masks are separable which means that [27:53] they can be written as the convolution [27:55] of two sub masks. Sometime this is [27:59] useful because applying and exploiting [28:02] the sensitivity property um it's often [28:06] cheaper to cheaper to first apply [28:08] f_sub_1 followed by f_sub_2 rather than [28:10] applying f directly. So these are just [28:12] some tricks that people use in order to [28:13] speed up um [28:17] the image processing pipeline. So in [28:20] there is a particular case [28:23] whereby a mask is representable as an [28:26] outer product of two vectors which [28:28] corresponds to two dimensional [28:30] convolution. So outer product will be [28:32] the product of say this vector and this [28:35] vector [28:37] say one one one [28:40] uh one one one [28:43] is the result of this outer product [28:47] >> capital f. So basically the uh moving [28:50] average unnormalized moving average [28:52] matrix. [28:54] So why is so we started with an f that [28:57] was a matrix we represented it as a [29:00] outer product of two vectors. Why is [29:02] that useful? So suppose that we want to [29:06] again carry out the same operation. [29:13] So we have convolution. [29:16] So in general let m [29:20] let the mask be m by m and let the I [29:23] want to make sure I use the same [29:24] notation. The image has size w * h. W is [29:29] the width the number of columns. H is [29:32] the height the number of rows. [29:34] So if I apply [29:38] um the moving average mask with size m [29:41] by m to an image with size w * h how [29:46] many operations do I have to carry out? [29:49] So per pixel [29:52] I need to carry out [29:55] m² [29:57] multiplications. [29:59] Is that right? [30:02] because I have to carry out one [30:04] multiplication for each component of the [30:06] mask. You're assuming that the mask has [30:09] sides m * m which means that I have m [30:12] square components. So per each pixel in [30:15] the input image I had to carry out m [30:17] square multiplications and then an [30:20] addition [30:22] since how many pixels do I have in the [30:24] input image? [30:28] W * h. So in total I have to carry out M [30:33] square WH operations. [30:36] But now we are smarter and we recognize [30:38] that actually the matrix [30:41] with all ones unnormalized. If it is [30:44] normalized that we would just add the DS [30:46] here wouldn't make any difference can be [30:48] written as the outer product of two [30:50] vectors. So let's first apply [30:54] convolution of the input image with [30:55] respect to this vector which can be [30:58] considered a mask is a trivial mask [31:00] because there's only one row but still [31:02] is a mask and then we apply the [31:05] convolution of the resulting uh and then [31:07] we consider the convolution of the [31:08] resulting image with this mask. [31:12] So when we first take the convolution [31:13] with respect to this vector, how many [31:16] operation do I need to carry out [31:20] for each pixel? Now I have a max mask [31:23] with the three elements. So I need to [31:25] carry out three operations. In general [31:28] with m elements, I have to carry out m [31:30] operations per pixel. And again I have [31:32] to repeat this procedure uh w * h times. [31:39] And then I have to convolve the [31:42] resulting uh image with this column [31:45] vector which again entail MW operations. [31:50] So in total I need to carry out the two [31:52] MW operations. [31:55] So in general m square is much larger [31:58] than 2 m which means that actually [32:01] recognizing that in the case of the [32:04] moving average filter the filter is [32:06] separable would lead to dramatic [32:09] computational savings. Yeah. [32:10] >> Um but also is aren't all these filters [32:12] like based on some sort of look localess [32:16] so m is not going to get too big right. [32:17] So this is doesn't give like too [32:19] dramatic of savings. [32:20] >> Well still 3x3 is a very small thing. So [32:24] uh it could be say of the order of five [32:27] or six. So the difference between m² and [32:30] 2 m is seen is uh sizable especially [32:36] because you're multiplying by wh right [32:37] which will be quite large. So like even [32:40] a factor of 10 or a factor of 50 pixels. [32:44] >> Yeah. Yeah. [32:47] >> And it cost you nothing. So there is [32:50] also the other thing right [32:52] >> there just for this example the [32:54] convolution is equal to the other [32:56] product. Yeah. [32:57] >> Yeah. [32:59] >> No. So, not all masks are separable, but [33:01] it turns out that a lot of them are. In [33:05] particular, besides the moving average, [33:08] also the gashian sming is separable. And [33:11] this is due to the fact that the uh [33:14] gashian distribution uh can be uh broken [33:18] into its x and y gashion distributions. [33:22] So for most practical cases we can use [33:25] leverage [33:27] uh separable masks but you're right not [33:29] all of them are separable. [33:33] Okay [33:35] so [33:37] we talked about filters special near [33:40] filters we considered two main classes [33:42] uh correlation and convolution which [33:45] basically are brothers. One is just a [33:47] flipped version of the other ones. We [33:49] consider example as example smoothing [33:51] filters either the moving average of the [33:54] gausian smoothing filter. But a very [33:57] very important uh uh additional example [34:00] of a linear filter is the one whereby [34:03] the mask implements the notion of a [34:06] derivative of an image. Now how do we [34:09] define the derivative of an image? Since [34:11] an image is a discrete function means [34:13] that the domain is uh basically the rows [34:19] and columns of an image. So it's a [34:21] discrete domain. The output is discrete [34:23] as well at the quantized levels of [34:26] intensity. We cannot really use the [34:28] standard notion of derivative for uh the [34:31] console calculus. We have to consider [34:33] discrete version of a derivative. [34:35] [snorts] Now in this case in the case of [34:37] a discrete [34:42] definition of the derivative of a [34:44] function we have actually quite a bit of [34:46] freedom as we can define a derivative of [34:49] a discrete function. So in particular a [34:53] possible way is to define the derivative [34:56] of the image with respect to x. X means [35:01] in the horizontal component. So the [35:03] column wise uh component as [35:10] actually sorry it means in the row wise [35:12] component e i of x + y [35:16] - i x -1 i. [snorts] So basically if [35:24] we have our image [35:31] so this is our xy [35:33] say that this is four this is eight this [35:37] is 10 [35:41] what is the derivative in the row wise [35:44] direction [35:49] >> two yeah no it's not going to be a [35:51] tricky a trick question just two. [35:54] So then in the output image at the [35:57] corresponding xy location I will put two [36:02] which makes sense. The derivative [36:03] encodes the notion of change in a [36:06] signal. [36:07] Here we cannot really reason in terms of [36:10] an differential increments but still we [36:13] can reason in terms of finite [36:14] differences. [36:16] So the derivative of a image is really [36:18] defined as a finite difference in the [36:20] pixel space. Yep. [36:22] >> You say there's multiple ways to do it. [36:24] But is there a reason we consider we're [36:25] looking at the indices of either side [36:27] versus the one we're at versus [36:29] >> Yeah. So another way is to consider [36:31] onesided [36:33] uh derivatives like whereby you could [36:36] define this as I size X + 1 Y minus IXY. [36:43] So this is the one side derivative or [36:46] also yx y - yx - one y it will be up or [36:51] down. In reality this is generally a [36:56] little bit more robust by consider [36:59] because it considers values in the [37:01] neighborhood both in this the both sides [37:04] both sides of the neighborhood of the [37:05] pixel equation. [37:07] But [snorts] this uh uh um prompts the [37:11] question about can we consider even more [37:13] robust definition of a a derivative or a [37:17] computation of a derivative which leads [37:19] to the so-called so masks that are [37:21] really the ones that are used in [37:23] computer vision to take derivatives. [37:25] The point with the soil mask is try to [37:28] uh provide a more robust [37:31] uh definition of derivative by taking [37:34] into account not just the difference [37:37] within with respect to a single column [37:40] so column y but also the differences [37:44] uh discrete differences in neighboring [37:46] columns and then take an average of [37:48] those differences in an effort to have [37:50] something that is more robust to [37:52] outliers noise and so on. [37:55] So for example on the x direction the um [38:00] um so [38:02] uh consists of a 3x3 uh mask where we [38:06] take um derivative in three neighboring [38:11] directions. We give a more weight to the [38:14] one where the pixel equation lies and [38:16] less weight to the rows where which are [38:20] in neighbors of that pixel. Similar to [38:23] the what we do with the gash moving [38:25] mask. [38:28] >> Is there a reason why all of these [38:30] filters are 3x3 or we could choose? [38:32] >> Oh no no [38:34] usually they're larger. I do 3x3 simply [38:37] because it's easier to print it easy to [38:39] explain it and when you do computation [38:41] by hand it's easier but no in general [38:44] it's left a little bit up to the user to [38:46] decide what is the width of the mask. [38:50] That's a good question. [38:53] So view soel masks as just a more robust [38:56] implementation of the two side uh [39:00] discrete difference definition of the [39:01] derivative of a mask but the key point [39:04] is that basically you take differences [39:06] of intensities [39:08] ask so what's the direction of the x [39:11] orientation [39:12] >> so x here this will be the uh the row so [39:18] it will be in the uh vertical direction [39:21] here. It will be in the um in the Y. So [39:25] this will be in the column Y direction. [39:28] Keep in mind that we're doing um a [39:31] convolution here. So these are mirrored. [39:36] >> All right. So the filters can also be [39:40] used for uh detecting um um similarities [39:47] in particular similarities between two [39:50] uh images in order for example to detect [39:53] correspondences that are useful for [39:54] structural promotion. Two popular way of [39:57] detecting similarities are to take [40:02] differences in intensity values in the [40:04] neighborhood of each pixel and then take [40:07] the absolute difference or take the [40:09] square of the difference. The first [40:11] approach is referred to as sum of [40:13] absolute differences. The second one is [40:15] refer to a sum of square differences. [40:18] They're just two definitions. [40:22] All right. [40:24] I think this is good background in terms [40:26] of filtering. Now, how do we make [40:28] filtering useful? Well, as I said, the [40:31] second step in the image processing [40:33] pipeline entails detecting local uh [40:37] features uh that is a patterns that um [40:42] differ from immediate uh uh the [40:45] immediate neighborhood such as an edge, [40:46] a corner, blob and so on and so forth. [40:50] In particular, in this class, we will [40:52] focus on edge detectors and corner [40:54] detectors. Edge detectors will be useful [40:57] because they will allow us to detect [40:59] lines that we will use as a geometric [41:01] primitives in order to build a [41:04] localization module for your robot. [41:08] Now, [41:09] why are detectors descriptors useful? [41:12] Well, first of all, for steer [41:13] reconstruction, as already mentioned. [41:15] Second of all, they can be useful in [41:17] order to uh reconstruct transformation [41:21] and hence uh they're very related to the [41:24] notion of structure from motion if you [41:25] were in the lecture on Friday. But [41:27] beyond robotics, they can be used for [41:29] other computer vision tasks such as [41:31] panorama stitching. You take the images [41:35] of a mountain from two different [41:36] perspectives and then you want to stitch [41:38] them in order to in order to have a [41:40] broader view. you detect points that [41:44] correspond to each other and then you [41:46] use them as anchors in order to stitch [41:48] the two images or even to uh detect [41:52] objects as we will see next time. [41:58] So as I said the first feature that we [42:00] want to detect is um an edge. An edge is [42:05] defined as an region of an image where [42:08] you have a stark difference in intensity [42:13] saying from white to black or from black [42:16] to white. Now for you I mean for the [42:18] human eye detecting an edge is [42:20] relatively simple but for uh computer [42:24] vision it could be quite tricky. [42:27] In particular, from a mathematical [42:29] standpoint, an edge is a region of the [42:32] environment whereby you have a large [42:35] difference in the large chain well a [42:38] large value for the first order [42:39] derivative and a very small value for [42:41] the second order derivative. The very [42:44] large value for the first order [42:46] derivative is obvious because you have [42:48] this discrete jump discrete discrete [42:51] jump in intensities. The reason for the [42:53] second order derivative to be small will [42:55] be seen in a second. [42:59] The point is to exploit uh this fact [43:02] that an edge corresponds to a uh [43:06] dramatic difference in intensity and [43:08] hence high value of the derivative in [43:09] order to detect them. So in particular [43:11] we will implement a derivative filter [43:15] and then we apply to the input image. We [43:17] get an output image that corresponds to [43:19] the derivatives. So the differences [43:21] intensities and then we say that there [43:23] is an edge where those derivatives are [43:26] very large. [43:28] So it's pretty simple. Make sense? [43:33] So [43:35] there are a number of criteria for [43:36] having a good edge detection uh [43:39] algorithm. First of all, we want to have [43:41] an we want to have accuracy meaning that [43:43] we want to minimize a false uh positive [43:46] detecting an edge when actually there is [43:49] no edge or false neg negatives missing [43:52] real edges. Localization we want to make [43:54] sure that once we detect an edge we also [43:58] um localize that edge in the same [44:01] position where that edge really is. And [44:04] third we want to have single response. [44:06] So we want to make sure that one edge is [44:08] detected as a single edge as opposed to [44:10] multiple edges. [44:13] Now the approach entails basically two [44:15] steps that I already alluded to. First [44:18] we will apply a smoothing step in order [44:20] to remove noise and then we will take a [44:23] derivative with respect to the smooth [44:26] image. Eventually we will realize that [44:29] um the entire procedure encompasses a [44:32] convolution. So by using the sensitivity [44:34] property we will uh differentiate this [44:37] moving filter and apply the resulting [44:39] mask to the target image. [44:42] So to make things concrete let's assume [44:44] that we have just a one-dimensional [44:47] image. So basically we have an image [44:50] that is just [44:54] a raw vector with intensities [44:59] uh say 50 70 well in this case would be [45:02] what uh say well I don't have the y [45:05] levels but say 50 50 and then all of the [45:09] sudden 120 120 and so on. So basically [45:13] we have a one-dimensional image which [45:15] corresponds to just a row and we have [45:19] um low intensity and then discrete jump [45:23] and then we have high intensity [45:25] but in general in the intensity values [45:28] we have some noise. It's not that you [45:31] have 50 5050 but maybe you have a 51 you [45:34] have 48 52 and so on. [45:38] So if you were to differentiate this [45:40] image directly by applying the finite [45:43] difference scheme that I mentioned [45:44] before, this will be a typical output. X [45:49] here denotes the uh index of the vector. [45:53] Y is the value intensity. As you can see [45:56] by just looking at the output of the [45:58] differentiated image, it's impossible to [46:02] see where the edge really lies. Why is [46:05] it the case is that since we had all [46:08] this noise, this noise by taking the [46:10] derivative gets amplified. So basically [46:13] the difference that you can take here [46:14] per pixel are very different are very [46:16] similar to the differences that you can [46:18] take here per pixel. And so what you get [46:20] as an output is something that is not [46:22] usable. [46:26] So what you do is actually to filter the [46:29] image out. [46:30] So we again we had the input image which [46:34] um entails this step in intensity but [46:37] it's a bit noisy. So what you would do [46:40] is to consider [46:42] a gussian smoothing mask [46:46] that as you remember [46:48] um averages the pixels in the [46:51] neighborhood but gives more weight to [46:54] the pixel where the mask is centered at [46:56] and then less um weight to the tail of [47:00] the mask. And of course the idea is that [47:02] you apply the uh average operation here [47:06] then you move one step to the right and [47:08] then you keep going. The result will be [47:10] the smooth image here at the bottom [47:14] which is the result of applying this [47:16] smoothing gausian kernel or mask with [47:19] the input image. At this point [47:23] you apply the derivative filter [47:26] and then what you get is magically bomb [47:29] blimp. [47:31] So one um patch of the image where you [47:34] have a high gradient and here the second [47:37] derivative is uh zero because first you [47:41] go up and then you go down. So that's [47:42] why you have [47:44] so now it will be very easy to detect [47:47] where an edge is. You just look at the [47:50] peak of the derivative and that's where [47:53] the edge is which corresponds more or [47:55] less where the actual edge is. [47:59] Does it make sense? [48:02] Good. So, as I said before, whatever [48:06] done will work fine. [snorts] But for [48:08] computational reason is easier to [48:11] exploit the property of a convolution [48:13] that says that the convolution is [48:15] associative. Which means that instead of [48:19] first smoothing the image and then [48:21] taking the derivative of the image, what [48:23] we can do is to first take the [48:25] derivative of the smoothing mask [48:29] and then apply the resulting mask that I [48:32] refer to as a G prime to the input [48:34] image. The advantage is that we only do [48:38] the convolution with a big [48:41] 2x2 matrix. The image only once here [48:44] instead here you would do it twice. [48:50] you need to pad the mask with zeros. [48:52] >> Yeah. Every time uh you have to do uh [48:56] you have to account for the conditions. [48:58] Yes. [49:00] So so here you see how here actually the [49:04] width of the mask is quite large. So we [49:06] have about 400 values. So remember what [49:10] the smoothing gausian mask was. It's [49:14] just a gian just a p of course [49:16] discretized. [49:18] So what is the derivative here? The [49:20] derivative is positive and here the [49:22] derivative is negative. So how does this [49:25] derivative of the smooth the smoothing [49:27] gashion mask look like? Like like this. [49:30] First the derivative is positive and [49:32] then the derivative is negative. So then [49:35] if you apply the [49:38] uh derivated uh differentiated gausian [49:42] filter to the original input we get the [49:45] same output. [49:48] Isn't that neat that we do this in one [49:50] step? [49:52] Now in reality what we care about are [49:55] the two dimensional images. So what we [49:58] had to do is to [50:00] smooth the image in two dimensions. So [50:04] basically accounting for the two [50:06] dimensional uh smoothing gashian [50:09] smoothing mask. The one that was here [50:14] this one here is two dimensional [50:16] basically you can view it as a um gash [50:21] in two dimensions. And [50:25] now you have to take derivatives in the [50:28] two directions horizontal and vertical [50:30] direction. [50:32] As you were saying, you have to account [50:34] for variations not just with respect to [50:37] the rows or the columns but with respect [50:38] to both the rows and the columns because [50:40] the edge obviously can be orient [50:42] oriented in uh any possible way. [50:47] So this just a straightforward [50:49] generalization what we did before. Again [50:51] the idea is that instead of taking the [50:53] the smoothing of on instead of [50:55] performing the smoothing on the image we [50:58] first take the derivative of the [50:59] smoothing mask and then we convert that [51:01] to the input image to save on [51:03] operations. [51:06] So you do that and you get as an output [51:09] image [51:11] uh two images. [51:13] One which um encodes the derivatives in [51:19] the x direction and y that encodes and [51:22] then the other one that encodes the [51:23] derivative in the y direction. [51:27] Then pixel by pixels you take the square [51:32] values and you sum them. the result is [51:34] still an image and then you look at [51:38] those pixels in the resulting image that [51:41] has a [51:43] maximum value. It's a bit there's a bit [51:46] more to to that but we will see that in [51:48] the next slide. [51:50] Does it make sense? [51:56] So this is in particular how the gausian [51:58] filter looks like in two dimensions [52:01] when you take the derivative with [52:04] respect to the x direction again here [52:06] it's going up so the derivative is [52:08] positive here it's going down so that's [52:10] why you have a ballet [52:12] and then when you do the y it will be [52:14] like in the orthogonal direction. [52:18] So this is the filter that you will have [52:20] here and the one that is rotated by 90° [52:24] is the filter that you will have here. [52:28] >> How does this work for diagonal edges? [52:31] Is it the same thing or [52:32] >> Yes, because that is accounted for here. [52:35] >> Okay. [52:35] >> Yeah, that's why at the end you have to [52:37] take basically the uh the square root of [52:41] the squares of both. [52:45] All right. So let's see in practice. So [52:46] let's get the image of this person. [52:48] First we use the differentiated gausian [52:54] uh filter. [52:56] This will be the output with respect to [52:58] y. That will be the output with respect [53:00] to x. These are the two images sx and sy [53:04] that I mentioned here. At this point I [53:08] combine them by taking the square root [53:10] of sx² + sy. That is pixel per pixel. So [53:14] that's why as an output I still get an [53:16] image. [53:17] I only [53:19] um select those pixels such that the uh [53:24] value is greater than a certain [53:26] threshold which is a designer choice. [53:28] Everything else is set equal to zero. [53:31] And finally in order to have a crisper [53:33] result I apply I apply a last step which [53:37] is the no maxima suppression. Basically [53:40] I look in each neighborhood and for each [53:43] neighborhood I only consider the uh [53:46] points that are at the maximum [53:49] in order to have basically lines that [53:51] are thinner. [53:52] >> Yeah. [53:53] >> Is this value h that we're uh you know [53:56] dropping out all the all the things that [53:58] are below a certain threshold. Is that [53:59] sort of what you said on like an image [54:01] slider for image trace when you're using [54:03] >> for example? Yes. Because basically if [54:05] you make h very high then uh You won't [54:09] get all the same. [54:10] >> What's that? [54:10] >> You won't get very much. [54:12] >> You don't get very much. But on the [54:14] other hand, uh you don't classify as an [54:17] edge something that is not an edge. If [54:19] you start you making very low, then [54:22] there is the risk that you're [54:23] classifying as an edge something that is [54:24] not an edge. So it's really a threshold [54:27] that you get that you tune in order to [54:29] find a good trade-off between false [54:30] positives and false negatives. [54:33] So that requires a bit of tuning. But in [54:36] any case, does the entire process [54:37] pipeline make sense? [54:49] The concept as I said is quite simple. [54:52] You just take this uh smoothing in order [54:56] to remove noise. Then you take [54:58] differences in uh y direction and x [55:01] direction. [55:03] And then you have two images. each one [55:05] for each pixel you have the difference [55:07] is one of the two directions. Then you [55:10] combine them by basically summing them [55:13] by making sure that you square this one, [55:14] you square the other one and you take [55:15] the square root. That will be the output [55:18] and then you do a little bit of [55:19] post-processing in order to retain uh [55:23] only those gradient information that uh [55:26] pass a threshold test in order to find [55:29] good trade between false positive and [55:30] false negatives. [55:33] All right. So it was for edges. Let's [55:35] talk about corners. [55:38] So corners are um also very useful [55:42] features especially for uh matching like [55:45] for example for stereo vision. Similar [55:47] to edges, we have a number of criteria [55:49] that we would like for a corner detector [55:51] to have like a repeatability. Same [55:54] future can be found in multiple images [55:56] despite geometric and photometric [55:58] transformations and distinctness meaning [56:01] that information carried by patch [56:03] surrounding the future should be as [56:05] distinctive as possible in order to make [56:07] sure again to make sure that you have a [56:10] uh consistent matching pairs across [56:13] images. in particular in terms of [56:16] repeatability. [56:17] If you pick some uh corners here then [56:23] then for for whatever reason you cannot [56:26] pick on an image with a slightly [56:29] different pose then you cannot find any [56:31] matching. So here this is a case where [56:34] this corner was not detected. Actually [56:38] none of these corners were detected [56:42] and other corners were detected but now [56:44] we cannot find the matchings anymore [56:46] which means that we can do anything in [56:48] terms of processing these two images. So [56:49] this will be bad performance [56:52] and the other one is distinct uh to be [56:55] distinctive. So if [56:58] uh I detect um uh this corner here but I [57:04] cannot describe it in a way that is [57:06] distinctive enough in order to [57:08] understand whether this corner really [57:10] corresponds to this one, this one, this [57:12] one and this one then again uh I cannot [57:16] do any sort of matching. [57:20] So do you have an intuition about how we [57:22] could detect a corner? So we said that [57:24] an edge corresponds to a region of an [57:26] image whereby we have a sudden change in [57:29] intensity in one direction. [57:33] >> Exactly. So corner is uh basically [57:37] defined as a um part of the image where [57:42] you have uh changes in all directions [57:45] actions [57:48] and you exploit [57:50] this definition in order to design a [57:53] corner uh detector. I'm not going to go [57:56] into the details of how to design a [57:59] corner detector but I mean by now you [58:02] get corner detectors already implemented [58:04] for you in visual libraries but just [58:06] want to give an intuition. [58:09] The idea is to take [58:12] um a window say a mask and then you [58:15] slide it around each pixel. So if you [58:19] are in a region that is flat mean the [58:22] intensity is uniform if you shake this [58:25] window around the response is the same. [58:28] So here there is neither an edge nor a [58:30] corner. [58:32] If instead you're close to an edge and [58:35] you move the window up and down then the [58:40] response is the same. But when you move [58:42] it in the orthogonal direction, then you [58:45] have this drastic change in intensity, [58:48] which means that you have an edge. If [58:50] you're here, no matter how you move the [58:53] window, you have a drastic change in [58:55] intensity, which means that you are a [58:56] corner. That's basically what a corner [58:59] detector exploits in order to detect a [59:02] corner. Now [59:06] uh one very popular corner detector is a [59:08] so-cal harist detector that exploits [59:12] this notion that if you move a window [59:14] locally in all directions and you have a [59:17] changes of intensity in all directions [59:21] then you have a corner. So that detector [59:23] is referred to as a hardest detector. [59:25] What a harist detector do is really to [59:27] translate this notion of this notion of [59:29] shaking around the window into a [59:30] mathematical test that essentially [59:34] entails taking some derivatives [59:36] um and then um processing those [59:40] derivatives [59:42] through an value de composition in order [59:43] to well very simple value composition in [59:45] order to find [snorts] the corners. So [59:48] here you can see how the Harris detector [59:50] detects uh uh corners [59:55] with remarkable repetit repeat [59:58] repetibility even though the image [60:02] uh is taken from a very different [60:05] perspective and there are significant [60:08] uh uh intensity differences. This is [60:10] much more gray than this one [60:16] in particular. One can show and this is [60:18] due to the fact that the Harris detector [60:20] detector reasons in terms of values that [60:23] the Harris detector is invariant to uh [60:26] rotation. So if you rotate the image the [60:30] Harris detector will pick up the same [60:32] corners which is great and it's also [60:36] environment to intensity changes. So if [60:38] you uniformly scale your image by the [60:42] same quantity, so you add 50 to all [60:44] pixels, the hardest detector will uh [60:46] pick the same um [60:50] corn the same corners, which again is [60:52] great. The problem though is that the [60:54] harist detector is not invited to scale [60:58] changes. This is annoying. So meaning [61:00] that if I move away from an object there [61:03] is a danger that the Harris detector [61:05] does not pick the same corners that they [61:07] picked with the previous image. The [61:10] reason why is that the case is that [61:12] since the Harris detector uses a window [61:14] with a fixed size at some scale [61:18] something may look as a corner but at [61:21] another scale the very same feature well [61:24] the very same uh geometric uh uh um [61:30] entity in the image may look like an [61:32] edge. So for example, let's say that [61:35] this is the original image and you have [61:36] this line. You apply your window. You [61:39] move it around in all directions. You [61:41] have changes. We classify as a corner. [61:44] Now we get a closer to the line. We [61:47] apply this window with the same sides. [61:50] So now as I move the window around, I [61:53] get change in this direction but not so [61:54] much in this direction. So now I [61:56] classify this as an edge [62:00] which is disastrous. [62:03] Because if you do it for all corners [62:05] then you cannot you don't have any [62:07] matching anymore and so uh stereo vision [62:11] and then say for example for robots [62:14] visual odometry whereby you use sequency [62:18] of images in order to understand by how [62:20] much you have moved can't be done [62:22] anymore. [62:24] So this triggered a lot of research on [62:26] how to find detectors that not only are [62:30] rotation environment but and intensity [62:33] environment but also environments to uh [62:36] scale uh changes. [62:39] Some of the very popular ones are an [62:41] extension the harist detector refer to a [62:43] haris llashian or the sift detector [62:46] which uh is also very very popular. [62:50] Again we won't go into more details [62:52] about detectors. This is not really a [62:54] class only on computer vision but I just [62:56] want to make sure that you know the [62:58] relevant terms in computer vision for [63:00] the main detectors like for example [63:01] sift. [63:03] So so far we talked about detectors. [63:07] Once you have detected a future you want [63:09] to make sure that you describe it so [63:10] that you can associate it with the same [63:13] future in another image. [63:16] That's the role of a descriptor. [63:18] descriptor describe the key points or [63:20] futures so that we can compare them [63:22] across images. The most naive way of um [63:28] coding a descriptor is just to detect a [63:32] future and then use as descriptor the um [63:39] um pixel intensities in the neighborhood [63:42] of that uh [63:45] of that feature. [63:47] Now [63:49] to the descriptive is that we associate [63:51] with a given key point an MM window of [63:54] pixel intensity center at that key [63:55] point. Like for example here we have [63:57] this blob we consider as descriptor just [64:02] the intensities of the neighboring [64:04] pixels. [64:06] Now the main drawback of [64:09] um this descriptor is that is very [64:12] sensitive to uh scale. So if uh we get [64:17] closer to this lamp then everything in [64:20] the neighborhood will look very bright [64:22] and then again there is not a very good [64:24] way of matching is also so it's very [64:27] sensitive to scale is sensitive to pose [64:29] and is also poorly distinctive. [64:32] So there are much better descriptors out [64:35] there. Again sift is one of the more [64:38] prominent one. Sift is both a detector [64:39] and a descriptor. So sift is um um [64:46] detect and a descriptor and as a [64:48] descriptor essentially relies on a local [64:51] distribution of image gradients around [64:54] key points [64:55] but it takes many many gradients and [64:57] indeed the descriptor is a 128 [65:00] dimensional vector. So actually the sift [65:03] detector and descriptor is a very [65:05] heavyweight [65:07] uh descriptor. [65:10] So that's a disadvantage. The advantage [65:11] though is that has a number of uh very [65:14] appealing properties in terms of scaling [65:17] variance and variance rotation and so [65:19] on. There are many others out there [65:23] uh like orb brisk for my work on visual [65:27] gometry for navigation asteroids for [65:29] robots. I was using for example orb is [65:32] very robust to situations whereby [65:36] um you have uh dramatic changes in [65:40] intensity. So you're basically jumping [65:42] on an asteroid and you have the pitch [65:45] black of the universe and then you have [65:47] the very shiny white uh reflection of [65:52] the sand [65:54] and as you bounce you have this pitch [65:56] black or very bright white. So you need [65:59] to have detector that is very robust [66:00] with respect to these sudden changes in [66:02] intensity. So orb works very well for [66:05] us. I mean the point is that uh if in [66:09] the future you need to reason at the [66:12] level of detectors and descriptors there [66:14] are a bunch out there most of them [66:16] already implemented in uh vision [66:19] libraries. So what you would do is first [66:21] look at the literature about what people [66:23] say in terms of advantages, [66:24] disadvantages, but most importantly you [66:27] would try them all and see which ones uh [66:30] work best. [66:32] Now since 2010 2012 [66:37] a new paradigm has emerged in computer [66:39] vision that relies on uh neural networks [66:42] and in particular in convolutional [66:44] neural networks. This is a completely [66:46] different pardium that in a nutshell [66:51] um [66:54] implements the same functionalities that [66:56] we uh described before in terms of [67:00] filtering in terms of uh uh detecting [67:03] features, describing features and so on. [67:05] But it does so in a completely different [67:07] computational parad which is the parad [67:10] of neural networks. We won't be covering [67:12] neural networks in this class. So if [67:14] you're interested then you should take a [67:16] 274B. uh principal robot autonomy 2 [67:20] whereby the first module will be about [67:23] uh learning based and neural network [67:26] based vision and control and in [67:28] particular we'll have one week where we [67:30] will discuss how uh neuron nets can be [67:33] used to do a lot of the tasks that I um [67:38] explained before and in particular what [67:40] they do very well is the fourth task [67:42] that of semantic understanding for [67:45] example detected images putting bounding [67:47] box around objects and so on to the [67:50] point that neural nets have become the [67:53] de facto standard for computer vision [67:55] applications in robot autonomy. [67:58] The disadvantage. [68:00] Well, first of all, they need a lot of [68:02] data to train. This is more a learning [68:04] procedure as opposed to a mathematical [68:07] computational procedure. But that is not [68:09] so much of a problem. Fortunately, [68:12] uh right now there are very large data [68:14] sets to train neural nets. [68:16] But the problem is that sometimes it's [68:20] very hard to understand how exactly [68:23] um [68:25] neural nets really work after they have [68:28] been trained. Like for example, you can [68:29] see how in the first layers you can see [68:32] the uh so these are basically the [68:34] visualized initial layers of a CNN. You [68:37] can see they can be interpreted as a [68:39] mask whereby for example here looks like [68:42] you're taking differences and then [68:44] you're taking allergies for smoothing. [68:46] So, so these basically are masks that [68:48] are learned from data in order to um uh [68:53] classify objects and so on, but they're [68:56] not super interpretable. I mean, [68:57] sometimes they are, sometimes they're [68:58] not to the point that it's an open [69:01] question of how much one can trust a [69:04] neural network application. If I tell [69:06] you that in order to detect an edge, I [69:08] use a gussian filter and a derivative [69:10] filter, you know exactly what I'm doing. [69:12] Here is a little bit less clear. So now [69:14] you're an airplane that is trying to [69:17] detect other objects on the runway [69:20] uh and it's based on a neuronet and you [69:23] know exactly what are the computation [69:26] that neuronet is doing in order to [69:28] detect other objects. So the question is [69:31] am I relaxed? I sit back and relax or am [69:33] I a bit concerned to [snorts] the point [69:36] that uh um [69:38] for example a number of agencies in the [69:40] United States such as NAZA and DARPA [69:43] have a specific programs in order to uh [69:47] improve the interpretability of neural [69:49] net pipelines for visual processing and [69:52] for control. at [snorts] the same time [69:54] try to reason in terms of asurances or [69:58] properties that this system has and for [70:00] example I work on a program with DARPA [70:02] called assure autonomy where the problem [70:04] is very simple so the problem is that [70:06] you have a plane that is maneuvering on [70:09] a on the tarmac on a runway it's trying [70:12] to align itself with the center lane in [70:15] order to take off so it's relying on a [70:18] camera in order to detect the center [70:20] lane for the runway [70:23] and then on a simple proportional [70:25] derivative controller in order to make [70:27] sure that the airplane is aligned. So [70:30] you have as an input an image as an [70:31] output you have steering control for the [70:33] front wheel. In principle with the [70:36] classical approach is super easy like [70:38] you just put the edge detectors that I [70:41] show you today they're trivial. On the [70:43] other hand if you use a neural net the [70:45] question is how do you ensure that from [70:47] time to time the neural net doesn't give [70:49] a crazy output maybe because there is [70:51] some snow or some reflection or [70:53] something. What type of asurances you [70:55] can give? Well this is a very active [70:57] problem of research. So if you are [70:58] interested in this line of research uh [71:00] let me know. All right. So this is all I [71:03] wanted to say in terms of filtering [71:05] detection and description. Obviously as [71:08] it is usual for all the other topics in [71:10] this class there is more to it. I gave [71:13] you some readings at the beginning of [71:15] the lecture. You can ask me if you're [71:17] interested in getting deeper here. I [71:18] just want to give you a general idea of [71:20] the first three steps. And uh on [71:23] Thursday we will look at this type of [71:25] extracting [71:27] uh [71:29] more large scale features that might [71:30] have also semantic meaning in order to a [71:34] inform localization and b inform [71:36] decision making. All right. So I'll see [71:39] you on Thursday.