基于K邻近分类法(KNN)的图像分类及应用
目录
1. K邻近分类法(KNN)
K最近邻(k-Nearest Neighbor，KNN)分类算法，是一个在分类方法中最简单且用的最多的一种方法，也是最简单的机器学习算法之一。该方法的思路是：如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别，则该样本也属于这个类别。
这种方法通常分类效果较好，但也存在弊端：
- 该算法需要预设k值，而k值的选择会影响分类的性能。k的大小在特定环境下是由数据决定的。（不能太大也不能太小）
- 对于非常大的训练集，搜索速度就非常慢。
- 对噪声敏感。
- 可行性一般。
1.1 KNN的实现
所谓K近邻算法，即是给定一个训练数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例（也就是上面所说的K个邻居）， 这K个实例的多数属于某个类，就把该输入实例分类到这个类中。
这里利用一个简单的二维示例来说明病可视化分类器的工作原理。
1.1.1 创建二维点集
实现最基本的KNN形式非常简单。给定训练样本集和对应的标记列表，这些训练样本和标记可以在一个数组里成行摆放或者干脆摆放列表里。训练样本可能是数字、字符串等任何你喜欢的形状。
定义一个类并用训练数据初始化非常简单。每次想对某些东西进行分类时，用KNN方法，我们就没必要存储并将训练数据作为参数来传递。用一个字典来存储邻近标记，我们便可以用文本字符串或数字来表示标记。
在下面这个例子中我们用欧氏距离进行度量，创建了两个不同的二维点集。每个点集有两类，并用Pickle模块来保存创建的数据。
相关代码块：
from numpy.random import randn
import pickle
from pylab import *
# create sample data of 2D points
n = 200
# two normal distributions
class_1 = 0.6 * randn(n,2)
class_2 = 1.2 * randn(n,2) + array([1,6])
labels = hstack((ones(n),-ones(n)))
# save with Pickle
with open('points_normal_test.pkl', 'wb') as f:
pickle.dump(class_1,f)
pickle.dump(class_2,f)
pickle.dump(labels,f)
# normal distribution and ring around it
print ("save OK!")
class_1 = 0.6 * randn(n,2)
r = 0.8 * randn(n,1) + 10
angle = 2*pi * randn(n,1)
class_2 = hstack((r*cos(angle)/2,r*sin(angle)/4))
labels = hstack((ones(n),-ones(n)))
# save with Pickle
with open('points_ring_test.pkl', 'wb') as f:
pickle.dump(class_1,f)
pickle.dump(class_2,f)
pickle.dump(labels,f)
1.1.2 可视化分类
这里我们创建一个简短的辅助函数以获取x和y二维坐标数组和分类器，并返回一个预测的类标记数组。下面把函数作为参数传递给实际的绘图函数。
绘图函数需要一个决策函数（分类器），并且用meshgrid()函数在一个网格上进行预测。决策函数的等值线可以显示边界位置，默认边界为0等值线。
相关代码块：
import pickle
from pylab import *
from PCV.classifiers import knn
from PCV.tools import imtools
pklist=['points_normal.pkl','points_ring.pkl']
figure()
# load 2D points using Pickle
for i, pklfile in enumerate(pklist):
with open(pklfile, 'rb') as f:
class_1 = pickle.load(f)
class_2 = pickle.load(f)
labels = pickle.load(f)
# load test data using Pickle
with open(pklfile[:-4]+'_test.pkl', 'rb') as f:
class_1 = pickle.load(f)
class_2 = pickle.load(f)
labels = pickle.load(f)
model = knn.KnnClassifier(labels,vstack((class_1,class_2)))
# test on the first point
print (model.classify(class_1[0]))
#define function for plotting
def classify(x,y,model=model):
return array([model.classify([xx,yy]) for (xx,yy) in zip(x,y)])
# lot the classification boundary
subplot(1,2,i+1)
imtools.plot_2D_boundary([-6,6,-6,6],[class_1,class_2],classify,[1,-1])
titlename=pklfile[:-4]
title(titlename)
show()
1.1.3 绘制结果
上图中，不同颜色代表不同类的标记。正确分类的点用星号表示，分类错误的点用圆点表示，曲线是分类器的决策边界。
1.2 利用稠密SIFT的分类实例
要对图像进行分类，就需要一个特征向量来表示一副图像。该实例用稠密sift特征向量来表示图像。
1.2.1 稠密SIFT(Dsift)
在整副图像上用一个规则的网格应用sift描述子可以得到稠密sift的表示形式。
1.2.1.1 稠密sift和sift的区别
稠密SIFT是一种用特征进行目标跟踪的算法。该算法首先将表达目标的矩形区域分成相同大小的矩形块，计算每一个小块的SIFT特征，再对各个小块的稠密SIFT特征在中心位置进行采样，建模目标的表达。
然后度量两个图像区域的不相似性，先计算两个区域对应小块的Bhattacharyya距离，再对各距离加权求和作为两个区域间的距离。
因为目标所在区域靠近边缘的部分可能受到背景像素的影响，而区域的内部则更一致，所以越靠近区域中心权函数的值越大。最后提出了能适应目标尺度变化的跟踪算法。
该算法具有良好的性能。
而SIFT算法没有将图像的特征分成多个矩形块采样，而是直接将每个像素都作为可能的特征，通过得到的特征描述子作为图像的特征点。
1.2.1.2 稠密sift的简单示例
下面的代码可计算稠密SIFT描述子，并可视化它们的位置。
from PCV.localdescriptors import sift, dsift
from pylab import *
from PIL import Image
dsift.process_image_dsift('gesture/empire.jpg','empire.dsift',90,40,True)
l,d = sift.read_features_from_file('empire.dsift')
im = array(Image.open('gesture/empire.jpg'))
sift.plot_features(im,l,True)
title('dense SIFT')
show()
1.2.1.3 运行效果
1.2.2 手势识别示例
在此示例中，用稠密sift描述子来表示这些手势图像，并建立一个简单的手势识别系统。
相关代码块：
import os
from PCV.localdescriptors import sift, dsift
from pylab import *
from PIL import Image
imlist=['gesture/train/0_06.jpg','gesture/train/2_22.jpg',
'gesture/train/5_17.jpg']
figure()
for i, im in enumerate(imlist):
print (im)
dsift.process_image_dsift(im,im[:-3]+'dsift',30,15,True)
l,d = sift.read_features_from_file(im[:-3]+'dsift')
dirpath, filename=os.path.split(im)
im = array(Image.open(im))
#显示手势含义title
titlename=filename[:-14]
subplot(1,3,i+1)
sift.plot_features(im,l,True)
title(titlename)
show()
以上为构建3类简单手势图像的稠密sift描述子
具体运行结果为
from PCV.localdescriptors import dsift
import os
from PCV.localdescriptors import sift
from pylab import *
from PCV.classifiers import knn
def get_imagelist(path):
""" Returns a list of filenames for
all jpg images in a directory. """
return [os.path.join(path,f) for f in os.listdir(path) if f.endswith('.jpg')]
def read_gesture_features_labels(path):
# create list of all files ending in .dsift
featlist = [os.path.join(path,f) for f in os.listdir(path) if f.endswith('.dsift')]
# read the features
features = []
for featfile in featlist:
l,d = sift.read_features_from_file(featfile)
features.append(d.flatten())
features = array(features)
# create labels
labels = [featfile.split('/')[-1][0] for featfile in featlist]
return features,array(labels)
def print_confusion(res,labels,classnames):
n = len(classnames)
# confusion matrix
class_ind = dict([(classnames[i],i) for i in range(n)])
confuse = zeros((n,n))
for i in range(len(test_labels)):
confuse[class_ind[res[i]],class_ind[test_labels[i]]] += 1
print ('Confusion matrix for')
print (classnames)
print (confuse)
filelist_train = get_imagelist('gesture/train')
filelist_test = get_imagelist('gesture/test')
imlist=filelist_train+filelist_test
# process images at fixed size (50,50)
for filename in imlist:
featfile = filename[:-3]+'dsift'
dsift.process_image_dsift(filename,featfile,10,5,resize=(50,50))
features,labels = read_gesture_features_labels('gesture/train/')
test_features,test_labels = read_gesture_features_labels('gesture/test/')
classnames = unique(labels)
# test kNN
k = 1
knn_classifier = knn.KnnClassifier(labels,features)
res = array([knn_classifier.classify(test_features[i],k) for i in
range(len(test_labels))])
# accuracy
acc = sum(1.0*(res==test_labels)) / len(test_labels)
print ('Accuracy:', acc)
print_confusion(res,test_labels,classnames)
上述代码用训练数据及其标记作为输入，创建分类器对象。然后在整个测试集上遍历并用classify()方法对每幅图像进行分类。将布尔数组和1相乘并求和，可计算出分类的正确率。
由于所用的图像数据集特征明显，所以计算出的正确率为1。
换了一个数据集测试后得到
6类简单手势图像，计算出的正确率为0.813。
其中最后的混淆矩阵是一个可以显示每类有多少个样本被分在每一个类中的矩阵。它可显示错误的分布情况，以及哪些类经常相互“混淆”。
上图的混淆矩阵显示“P”经常被误分为“V”。