Python计算机视觉编程_02
基于SIFT算法的图像匹配
-
前言
-
1.Harris角点检测算法
-
- 1.1.特征点
- 1.2.Harris角点
- 1.3.Harris角点检测基本思想
- 1.4.Harris角点检测数学原理
- 1.5.Harris焦点检测算法代码解析
-
2.SIFT(尺度不变特征变换)算法
-
- 2.1.兴趣点(关键点)
- 2.2.描述符
- 2.3.关键点匹配
- 2.4.SIFT算法特征点匹配代码解析
-
3.SIFT匹配地理标记图像
前言
提到图像匹配,就不得不提到SIFT(尺度不变特征变换) 算法,作为图像特征提取的典型算法,SIFT算法单单在论文上的引用就已经到了6万多次,更不用提工程项目上的使用次数了。不过在介绍经典算法之前,我先介绍下啥是特征点和一个简单的Harris角点检测算法 。
本篇博客代码参考,来源于书本Python计算机视觉编程:https://github.com/jesolem/PCV
1.Harris角点检测算法
1.1.特征点
特征点就像我们平时辨认两个物品分别是什么的判断依据,一个物品是正立方体,一个物品是球,那么我们会说一个物品有棱角,一个物品很圆滑。但对于计算机来说,棱角和圆滑都是无法解析的词,于是计算机需要一个计算机来识别不同物品的方法,而起到让计算机分辨作用的点就是特征点。
1.2.Harris角点
很显然,不是每个像素点都能作为特征点的,特征点也不是仅用一个像素点就能概括的,为了便于理解,现在说的特征点仅指一个像素点,便于大家理解。
而角点顾名思义就是转角的点,比如三角形的三个顶点,正方体的八个顶点等。
1.3.Harris角点检测基本思想

如图所示,我们用一个四边形方框不断移动来判断这个正方形方框是否有巨大变化;第一幅图中,不管我们怎么移动,图像的的内容都不会有太大变换;第二幅图中,如果我们左右移动,图像的内容就会有比较明显的改变,但如果上下移动电话,图像又没有多大的变化;第三幅图中,不管我们往哪个方向移动,图像都会有明显变化。
我们要明确一点,图像的明显变化并不是我们看出来的,而是让计算机对比图像对应位置的像素值之差的累计之和得到的。
1.4.Harris角点检测数学原理
假设方框的大小为x*y的矩形,方框变化的距离为u,v,产生的灰度变化为E(u,v),那么会有以下公式:

式子中的I(x,y)为坐标x,y的像素值,w(x,y)为每个像素值的权重,比如我们认为中间部分的像素值更重要,那么我们就把中间部分的w(x,y)调大。
使用泰勒公式展开化简后可以得到这个式子:

于是对于局部微小的移动量,我们可以得到以下式子



我们记M的特征值为λ1(y向)和λ2(x向),那么就有

如果λ1和λ2都很小,说明图像窗口在所有方向上移动都无明显灰度变化。
1.5.Harris焦点检测算法代码解析
还是以之前拍的照片为例

#在一幅灰度图像中,计算每一个像素点的Harris角点
def compute_harris_response(im,sigma=3):
# 计算导数
imx = zeros(im.shape)
filters.gaussian_filter(im, (sigma,sigma), (0,1), imx)
imy = zeros(im.shape)
filters.gaussian_filter(im, (sigma,sigma), (1,0), imy)
# 可视化原图
plt.subplot(2, 3, 1)
plt.title('gray')
plt.axis('off')
plt.imshow(img, plt.cm.gray)
# 可视化x方向导数图像
plt.subplot(2, 3, 2)
plt.title('Derivative in X direction')
plt.axis('off')
plt.imshow(imx, plt.cm.gray)
# 可视化y方向导数图像
plt.subplot(2, 3, 3)
plt.title("Derivative in y direction")
plt.axis('off')
plt.imshow(imy, plt.cm.gray)
plt.subplot(2, 3, 4)
plt.title("Second derivative in X direction")
plt.axis('off')
plt.imshow(imx * imx, plt.cm.gray)
plt.subplot(2, 3, 5)
plt.title("Second derivative in X/Y direction")
plt.axis('off')
plt.imshow(imx * imy, plt.cm.gray)
plt.subplot(2, 3, 6)
plt.title("Second derivative in y direction")
plt.axis('off')
plt.imshow(imy * imy, plt.cm.gray)
plt.show()
# 计算Harris矩阵的分量
Wxx = filters.gaussian_filter(imx*imx,sigma)
Wxy = filters.gaussian_filter(imx*imy,sigma)
Wyy = filters.gaussian_filter(imy*imy,sigma)
# 计算特征值和迹
Wdet = Wxx*Wyy - Wxy**2
Wtr = Wxx + Wyy
return Wdet / (Wtr*Wtr)

#从一幅Harris响应图像中返回角点。min_dist为分隔角点和图像边界的最少像素数目
def get_harris_points(harrisim,min_dist=10,threshold=0.1):
# 寻找高于阈值的候选角点
corner_threshold = harrisim.max() * threshold
harrisim_t = (harrisim > corner_threshold)
# 得到候选点的坐标
coords = array(harrisim_t.nonzero()).T
# 得到候选点的Harris响应值
candidate_values = [harrisim[c[0],c[1]] for c in coords]
# 对候选点按照Harris响应值进行排序
index = argsort(candidate_values)
# 将可行点的位置保存到数组中
allowed_locations = zeros(harrisim.shape)
allowed_locations[min_dist:-min_dist,min_dist:-min_dist] = 1
# 按照min_distance原则,选择最佳Harris点
filtered_coords = []
for i in index:
if allowed_locations[coords[i,0],coords[i,1]] == 1:
filtered_coords.append(coords[i])
allowed_locations[(coords[i,0]-min_dist):(coords[i,0]+min_dist),
(coords[i,1]-min_dist):(coords[i,1]+min_dist)] = 0
return filtered_coords
#绘制图像中检测到的角点
def plot_harris_points(image,filtered_coords):
figure()
gray()
imshow(image)
plot([p[1] for p in filtered_coords],
[p[0] for p in filtered_coords],'*')
axis('off')
show()
这是get_harris_points(harrisim,6,0.1)的效果

检测的角点数目有点过多了,我们换成get_harris_points(harrisim,6,0.5)再试一次

还是骗多了,可能是照片本身偏暗了,换张亮的试试

threshold=0.1

threshold=0.5

仔细观察了一下,发现可能是因为最开始的照片像素值过大了,将其resize后

虽然角点还是过多,但至少能看出原来的样子了
2.SIFT(尺度不变特征变换)算法
2.1.兴趣点(关键点)
就像我们之前演示的那样,单纯的角点检测会有角点数目过多的问题,而SIFT则是要选取十分突出的点,这些点不会因光照,尺度,旋转等因素的改变而消失,比如角点、边缘点、暗区域的亮点以及亮区域的暗点。
SIFT特征使用高斯差分函数来定位兴趣点:

等式左边是一个图像的尺度空间,I(x,y)为原始图像,G(x,y,σ)为可变尺度的2维高斯函数:

得到这些关键点后,我们采用DOG函数来进行优化,进而大幅度减少关键点的数量:

比如一幅(1000,1000)的图像,我们通过高斯函数模糊得到多福图像,(750,750),(500,500)等,然后我们进行相应坐标的像素值相减得到像素值的变化(没有变化就代表没有特征,特征是尽可能变化多的点)


这些特征点是由DOG空间的局部极值点组成的,一般的局部极值点是比较检测点周围8个像素的大小(3x3的九宫格),如果均大于或均小于,那么这个点就当做特征点;对于DOG空间来说他要比较同尺度的8个像素点和上下相邻尺度对应的9x2个像素点,也就是一共26个像素点(可以理解为一个3x3x3的正方体,每一层都是不同尺度的图像),来确保在尺度空间和二维图像空间检测到极值点。
很显然,对于最上层和最下层的点来说,他们周围只有两层(最上层只有下层,最下层只有上层),那么就会有较强的边缘效应,为了避免边缘效应的影响,我们通过主曲率的比较来确定是否保留该关键点。
主曲率由该点位置尺度的2X2的Hessian矩阵得到:

Dxx代表x方向求导两次;Dxy代表x方向一次,y方向一次;Dyy代表y方向求导两次
D的主曲率和H的特征值成正比。令 α ,β为特征值,则有:

该值在两特征值相等时达最小。Lowe论文中建议阈值T为1.2,即

时保留关键点,反之舍去
2.2.描述符
为了实现旋转不变性,SIFT算法在特征点上加入了方向来对特征进行描述,通过求每个极值点的梯度来为极值点赋予方向。
像素点的梯度表示为:

梯度幅值为:

梯度方向为:

为了避免方向判定出错,我们选择检测点周围的所有点投票得出该特征点的方向,比如


那这个特征点的方向就是:

为了增强匹配的鲁棒性,我们将第二高的方向(投票数至少达到主方向的80%)定位辅方向,Lowe的论文指出这些具有多方向的点对匹配的稳定性至为关键。
为了进一步优化,我们可以将特征区域分为四个部分

通过四个区域的方向投票来决定最终结果,同理,我们可以进一步划分

Lowe实验结果表明:描述子采用4×4×8=128维向量表征,综合效果最优(不变性与独特性)
2.3.关键点匹配
和之前的匹配一样,我们采用两个特征点的描述向量的欧氏距离来得到是否匹配,为了保证匹配正确率,我们设定一个阈值,保证匹配对的唯一性


2.4.SIFT算法特征点匹配代码解析
我们使用的是开源工具包VLFeat提供的SIFT算法,所以我们先下载VLFeat(链接)。我选择的是vlfeat-0.9.20-bin.tar.gz
解压后添加到环境变量。

基础配置就完成了。
虽然配置完成了,但是调了半天还是无法实现,最后使用opencv方法直接解决(可能因为图像过大)
import cv2 as cv
from cv2 import waitKey
import numpy as np
import matplotlib.pyplot as plt
if __name__ == '__main__':
box = cv.imread("C:\ Users\ 19835\ Desktop\ opencv\ task2\ task_1.jpg")
# 压缩图片以便显示
box=cv.resize(box,(960,540))
box_in_sence = cv.imread("C:\ Users\ 19835\ Desktop\ opencv\ task2\ task_2.jpg")
box_in_sence=cv.resize(box_in_sence,(960,540))
cv.imshow("box", box)
cv.imshow("box_in_sence", box_in_sence)
# 创建SIFT特征检测器
sift = cv.SIFT_create()
# 特征点提取与描述子生成
kp1, des1 = sift.detectAndCompute(box,None)
kp2, des2 = sift.detectAndCompute(box_in_sence,None)
# 暴力匹配
bf = cv.DescriptorMatcher_create(cv.DescriptorMatcher_BRUTEFORCE)
matches = bf.match(des1,des2)
# 绘制最佳匹配
matches = sorted(matches, key = lambda x:x.distance)
result = cv.drawMatches(box, kp1, box_in_sence, kp2, matches[:15], None)
cv.imshow("-match", result)
cv.waitKey(0)
cv.destroyAllWindows()

3.SIFT匹配地理标记图像
from pylab import *
from PIL import Image
from PCV.localdescriptors import sift
from PCV.tools import imtools
import pydot
#download_path = "panoimages" # set this to the path where you downloaded the panoramio images
#path = "/FULLPATH/panoimages/" # path to save thumbnails (pydot needs the full system path)
download_path = "C:\ Users\ 19835\ Desktop\ opencv\ task2" # set this to the path where you downloaded the panoramio images
path = "C:\ Users\ 19835\ Desktop\ opencv\ task2" # path to save thumbnails (pydot needs the full system path)
# list of downloaded filenames
imlist = imtools.get_imlist(download_path)
nbr_images = len(imlist)
# extract features
featlist = [imname[:-3] + 'sift' for imname in imlist]
for i, imname in enumerate(imlist):
sift.process_image(imname, featlist[i])
matchscores = zeros((nbr_images, nbr_images))
for i in range(nbr_images):
for j in range(i, nbr_images): # only compute upper triangle
print ('comparing ', imlist[i], imlist[j])
l1, d1 = sift.read_features_from_file(featlist[i])
l2, d2 = sift.read_features_from_file(featlist[j])
matches = sift.match_twosided(d1, d2)
nbr_matches = sum(matches > 0)
print ('number of matches = ', nbr_matches)
matchscores[i, j] = nbr_matches
print ("The match scores is: \n", matchscores)
# copy values
for i in range(nbr_images):
for j in range(i + 1, nbr_images): # no need to copy diagonal
matchscores[j, i] = matchscores[i, j]
#可视化
threshold = 2 # min number of matches needed to create link
g = pydot.Dot(graph_type='graph') # don't want the default directed graph
for i in range(nbr_images):
for j in range(i + 1, nbr_images):
if matchscores[i, j] > threshold:
# first image in pair
im = Image.open(imlist[i])
im.thumbnail((100, 100))
filename = path + str(i) + '.png'
im.save(filename) # need temporary files of the right size
g.add_node(pydot.Node(str(i), fontcolor='transparent', shape='rectangle', image=filename))
# second image in pair
im = Image.open(imlist[j])
im.thumbnail((100, 100))
filename = path + str(j) + '.png'
im.save(filename) # need temporary files of the right size
g.add_node(pydot.Node(str(j), fontcolor='transparent', shape='rectangle', image=filename))
g.add_edge(pydot.Edge(str(i), str(j)))
g.write_png('test.png')

