最近邻法做图像分类

思想

最近邻法思想其实很简单:给出一大堆已经知道标签的图片。现在新来一张图片,新图片和所有的旧图片做比较,找出和旧图片中 “最相似” 的一张,输出这一张图片的标签作为预测值。

“最相近” 怎么办?

一张图片需要抽取它的特征,只要所有特征都很相近,那么两幅图片就很相似。“当看到一只鸟走起来像鸭子、游泳起来像鸭子、叫起来也像鸭子,那么这只鸟就可以被称为鸭子”。虽然简单粗暴,但是很有效。如何定义相近呢?比如求欧式距离,比如距离的绝对值之类的都可以。

那么,这个特征怎么求呢?这个 Toy 里面使用灰度共生矩阵来求。求得灰度共生矩阵(因为简单啊),然后求灰度共生矩阵的 5 个二次统计量(能量,对比度,相关性,均匀度,熵)作为特征。在这里,灰度共生矩阵可以使用四个方向(0°,45°,90°,135°),每个方向都能求出来 5 个二次统计量,也就是一幅图片可以求得 20 个特征。作为 Toy 差不多够用了吧?

下面呢,就是如何定义 “鸭子” 了。公式如下,应该没有打错把?最起码我是这么理解的公式:

$$
F(X)=arc\min_{k}(\sum(X-X_{i}^{k})^{2})
$$

实现

主程序:参数调整,读入图片,分出训练集和测试集,驱动整个程序的运行。

clear all;
close all;
clc;
% 参数们
NumLevels=8;
Scale=0.5;
Verbose=0;
Dims=4;
% 读入所有图片,获取特征和其他辅助信息
[n_samples,n_classes,n_features,classes,label,data]=ReadImg(NumLevels,Dims);
% 其他一些基础的东西
half=int32(n_samples*Scale);
my_yes=[];
dt_yes=[];
% GoGoGo
for iter=1:1:10
%     随机排序
    sel=randperm(n_samples);
%     分出训练集合和测试集合
    TrainSet_data=data(sel(1:half),:);
    TrainSet_label=label(sel(1:half),:);
    TestSet_data=data(sel(half+1:n_samples),:);
    TestSet_label=label(sel(half+1:n_samples),:);
%     开始做预测
    my_yes(iter)=TestAll(TrainSet_label,TrainSet_data,TestSet_label,TestSet_data,Verbose);
%     拿决策树作对比
    dt_yes(iter)=DTTestAll(TrainSet_label,TrainSet_data,TestSet_label,TestSet_data,Verbose);
%     输出看看
    fprintf('Iter%d:t My:%ft DT:%fn',iter,my_yes(iter),dt_yes(iter));
end
% 统计结果
fprintf('My:t max:%f:t average:%ft min:%fn',max(my_yes),mean(my_yes),min(my_yes));
fprintf('DT:t max:%f:t average:%ft min:%fn',max(dt_yes),mean(dt_yes),min(dt_yes));

读入图片

这里给的数据集比较特殊:数据集有 jpg 和 png 两种类型的图片,每幅图片都是 200*200 的纹理。共有 8 个类别,每个类别有 8 张图片。比如第 3 个类别第 6 张图片,文件名为 36.jpg。png 是对 jpg 做过直方图均衡化的结果。这两种图片在这里我混用了,为了让基数更大一点。(这个数据集叫 Brodatz

function [ n_samples,n_classes,n_features,classes,label,data ] = ReadImg(NumLevels,Dims)
% 标签和特征
label=[];
data=[];
% 样本总数
total=0;
% 因为图片是有规律的,所以采取这样读取图片
for i=1:1:8
    for j=1:1:8
        for k=1:1:2
%             后缀名的判断
            if k==1
                aft='.jpg';
            else
                aft='.png';
            end
            total=total+1;
%             拼接文件名
            filename=['data/',num2str(i),num2str(j),aft];
%             获得这个图片的特征
            data(total,:)=ImgFeatureGen(filename,NumLevels,Dims);
%             获得这个图片的标签
            label(total)=i;
        end
    end
end
% 标签转成列向量方便使用
label=reshape(label,[],1);
% 统计啦
n_samples=total;
classes=unique(label);
n_classes=length(classes);
n_features=size(data);
n_features=n_features(2);
end

对于每一张图片,转变成特征值

function [ feature ] = ImgInfoGen( f ,NumLevels,Dims)
feature=[];
% 读入图片,如果是彩色,则转化成灰度图片
IMG=imread(f);
if ndims(IMG)==3
    IMG=rgb2gray(IMG);
end
% 总共有多少个特征
total=0;
% 几个方向
angle=[0,1;-1,1;-1,0;-1,-1];
for i=1:1:Dims
%     得到灰度共生矩阵
    COMTX=graycomatrix(IMG,'Offset',angle(i,:),'NumLevels',NumLevels);
%     求二次统计量
    MAT_ANS=graycoprops(COMTX);
%     转成行向量便于计算
    MAT_ANS=struct2cell(MAT_ANS);
    for j=1:1:length(MAT_ANS)
        total=total+1;
        feature(total)=cell2mat(MAT_ANS(j));
    end
%     熵
%     total=total+1;
%     feature(total)=-sum(sum((COMTX+1).*log2(COMTX+1)));
end
end

测试的时候发现加上熵之后精度会下降。很奇怪。
熵哪里算错了?

$$
N=\sum_{i}\sum_{j}(i-j)^{2}p(i,j)
$$

另外我对灰度共生矩阵加上了 1, 防止 log(0)得到 NaN

下面开始做预测吧!因为这个分类器不像决策树那样需要做训练,所以直接做预测就好了。

做预测的引导程序如下:

function [ yes_rate ] = TestAll( TrainSet_label,TrainSet_data,TestSet_label,TestSet_data,Verbose )
yes=0;
n_samples=length(TestSet_label);
for i=1:1:n_samples
%     获得预测值和预测分数
    [prediction,score]=TestOne(TestSet_data(i,:),TrainSet_label,TrainSet_data);
    if TestSet_label(i)==prediction
        yes=yes+1;
    end
%     Verbose 报告
    if Verbose==1
        fprintf('label:%d:tpredict:%dtscore:%fn',TestSet_label(i),prediction,score);
    end
end
% 得到精度
yes_rate=yes/n_samples;
end

对于每一个样本,做预测的程序如下:

function [ prediction,bestScore ] = TestOne( test_data,train_label,train_data )
% 一些准备工作和统计工作
classes=unique(train_label);
n_classes=length(classes);
n_samples=length(train_label);
% 初始化工作
score=ones(n_classes,1);
score=score*413431390;
% 遍历训练集合中的每一个样本,得到此测试验本和每一个分类的最小距离
for i=1:1:n_samples
    score(train_label(i))=min(score(train_label(i)),sum((train_data(i,:)-test_data).^2));
end
% 找出最小值,作为预测结果
[bestScore,prediction]=min(score);
end

其实整个算法核心就四句话:

for i=1:1:n_samples
    score(train_label(i))=min( ...
        score(train_label(i)), ...
        pdist(train_data(i,:),test_data));
end
[bestScore,prediction]=min(score);

看出来了吧?

我还用了决策树作对比:

function [ yes_rate ] = DTTestAll(TrainSet_label,TrainSet_data,TestSet_label,TestSet_data,Verbose)
yes=0;
TREE=fitctree(TrainSet_data,TrainSet_label);
n_samples=length(TestSet_label);
for i=1:1:n_samples
    prediction=predict(TREE,TestSet_data(i,:));
    if TestSet_label(i)==prediction
        yes=yes+1;
    end
    if Verbose==1
        fprintf('label:%d:tpredict:%dn',TestSet_label(i),prediction);
    end
end
yes_rate=yes/n_samples;
end

话说 Matlab 自带的决策树用的是什么算法?Sk-learn 带的决策树用的是什么算法?

整体代码风格受到 sk-learn 的影响比较大。比如说参数传递和参数命名之类的。

下面结果是在某个 Brodatz 数据集上跑的效果。

结果

运行结果如下

Iter1:   My:0.562500     DT:0.468750
Iter2:   My:0.578125     DT:0.546875
Iter3:   My:0.562500     DT:0.421875
Iter4:   My:0.484375     DT:0.437500
Iter5:   My:0.515625     DT:0.421875
Iter6:   My:0.578125     DT:0.421875
Iter7:   My:0.531250     DT:0.281250
Iter8:   My:0.500000     DT:0.421875
Iter9:   My:0.640625     DT:0.468750
Iter10:  My:0.484375     DT:0.406250
My:  max:0.640625:   average:0.543750    min:0.484375
DT:  max:0.546875:   average:0.429688    min:0.281250

看来还是可以的。但加上熵之后,精度反而会下降:

Iter1:   My:0.437500     DT:0.468750
Iter2:   My:0.484375     DT:0.578125
Iter3:   My:0.484375     DT:0.578125
Iter4:   My:0.437500     DT:0.562500
Iter5:   My:0.453125     DT:0.453125
Iter6:   My:0.421875     DT:0.453125
Iter7:   My:0.515625     DT:0.625000
Iter8:   My:0.437500     DT:0.515625
Iter9:   My:0.453125     DT:0.531250
Iter10:  My:0.437500     DT:0.546875
My:  max:0.515625:   average:0.456250    min:0.421875
DT:  max:0.625000:   average:0.531250    min:0.453125

不知道是哪里有问题。

然后可以调整参数,例如加大训练集合、减少样本数之类、改变灰度共生矩阵量化精度之类的。在这里就不做对比了。反正就是,训练集合越大精度越好、特征数量增加可能导致精度减小。

最后附上一些很神奇的代码段:

主程序
ReadImage
TestOne

十分解气啊!

收工开始复习考试。

参考文档

[1] 杨杰. 数字图像处理及 Matlab 实现. 北京:电子工业出版社
[2] 宋相法. 数字图像处理课堂 PPT. 河南:河南大学

留下评论