2013-09-06 00:58:25 stevenhu_223 阅读数 8134

     前言:手势识别在Android手势中是最重要的部分,基本上算是手势的精髓;手势识别的算法有点类似人脸识别;手势识别的利用很普遍,涉及到用户安全操作的领域也比较多;比如可以通过手势识别来实现手机的解锁,安全启动用户设置的用户模式应用等;

    一. 基于第三方开发的手势识别    

        一般情况下,如果需要将用户当前绘制手势和已保存的手势进行匹配。那么,在用户绘制完当前手势时就可以进行匹配处理。这个过程可以在手势监听器GesturePerformedListener的onGesturePerformed方法中处理。

       如下示例代码片段:

...
			@Override
			public void onGesturePerformed(GestureOverlayView overlay, Gesture gesture)
			{
				// TODO Auto-generated method stub
			    final GestureLibrary store = MainActivity.getStore();
			    store.setOrientationStyle(4);
				//识别用户刚刚所绘制的手势
				ArrayList<Prediction> predictions = store.recognize(gesture);
				//遍历所有找到的Prediction对象
				for(Prediction pred : predictions)
				{
					//只有相似度大于2.0的手势才会被输出
					if (pred.score > 2.0)
					{
					    //testPActivityName();	
						Log.d("RecogniseGesture", "name-->" + pred.name);
						startApp(pred.name);
					    return;
					}
					else
					{
					    //Log.d("FxRecogniseGesture", "无匹配手势");
						new AlertDialog.Builder(RecogniseGesture.this).setMessage("不存在该手势").
						setPositiveButton("确定", null).show();
					}
				}
				
			}
...

       通过上面的代码片段可知,调用GestureLibrary的recognize对当前用户绘制的手势进行匹配操作,recognize的参数gesture对应的是当前用户绘制的手势。recognize方法返回类型为ArrayList<Prediction>集合,该集合中的元素Prediction类的源代码如下:

package android.gesture;

public class Prediction {
    public final String name;

    public double score;

    Prediction(String label, double predictionScore) {
        name = label;
        score = predictionScore;
    }

    @Override
    public String toString() {
        return name;
    }
}

        Prediction的属性name为被匹配的手势名字,score为手势的匹配分数(匹配分数越高,说明对手势的相似度匹配要求就越高)。所以,通过调用GestureLibrary的recognize方法返回的Prediction,就可以知道当前手势和已保存的手势匹配的相似度。

    二. 手势匹配源码实现

        在分析手势匹配源码实现之前,先总体来看看有关涉及到手势匹配相关的源码类之间的关系,如下图:


       上图中的相关类简介:

        GestureLibrary:手势库类,对外提供recognize函数,是实现手势匹配的关键入口。

        GestureStoreGestureLibrary的recognize函数真正的源码内部实现类。

        Instance:封装手势通过时间采样或空间采样后的离散点。该类的vector属性描述的就是当前被采样后的手势对应的多个离散点(这些点是有方向的,所以又可以称为向量)。

        Learner:抽象类,内部提供了对Instance进行添加、获取、移除操作的方法。同时提供了抽象方法classify。

        InstanceLearner:继承Learner,覆盖实现Learner中的抽象方法classify。

        GestureUtils:手势源码中的工具类。手势匹配源码实现,基本上最终都会通过调用该工具类中提供的方法来实现。

        GestureUtils类中相关的重点方法实现介绍:

         1). spatialSampling:对连续点进行空间采样(gesture由多个连续点组成)

         2). temporalSampling:  对连续点进行时间采样(gesture由多个连续点组成)

         3). computeCentroid:计算一组点的质心

         4). computeCoVariance: 计算一组点的方差-协方差矩阵

         5). computeTotalLength:  计算一组点的总长度

         6). computeStraightness:  计算一组点的直线度

         7). squaredEuclideanDistance:计算两个向量之间的平方欧式距离

         8). cosineDistance:  计算两个向量之间的余弦值,返回的是0到π之间的值

         9). minimumCosineDistance: 计算两个向量之前最小的余弦距离,参数vector1为之前保存的向量,vector2为当前输入的向量。

         10). computeOrientedBoundingBox:计算一个点集的最小边界框

         11). rotate:  旋转一组点

         12). translate:  移动一组点

         13). scale:  缩放一组点


       在前篇文章《手势的保存和加载》中,可以知道,用户绘制的手势是通过调用GestureLibrary的addGesture添加到手势库中,而该函数最终是通过调用GestureStore对象的addGesture来实现的。

        回顾一下GestureStore类中的addGesture方法实现代码,如下:

public class GestureStore {
...
    private final HashMap<String, ArrayList<Gesture>> mNamedGestures =
            new HashMap<String, ArrayList<Gesture>>();

    private Learner mClassifier;

    private boolean mChanged = false;

    public GestureStore() {
        mClassifier = new InstanceLearner();
    }
    //手势保存在一个ArrayList集合里,ArrayList又以entryName为key值保存在HashMap集合里
    public void addGesture(String entryName, Gesture gesture) {
        if (entryName == null || entryName.length() == 0) {
            return;
        }
        ArrayList<Gesture> gestures = mNamedGestures.get(entryName);
        if (gestures == null) {
            gestures = new ArrayList<Gesture>();
            mNamedGestures.put(entryName, gestures);
        }
        gestures.add(gesture);
        //通过gesture得到的Instance对象,存放到mClassifier对象(Learner类型)的成员mInstances集合中
        mClassifier.addInstance(
                Instance.createInstance(mSequenceType, mOrientationStyle, gesture, entryName));
        mChanged = true;
    }
...
}
        在addGesture方法中:

         Step1. 根据保存的手势及手势名字通过调用Instance的静态方法createInstance,创建对应的Instance对象(参数),然后将创建的Instance对象通过调用Learner的addInstance方法保存到Learner的成员变量mInstance集合中(ArrayList<Instance>类型)。

         Step2. 因此,Learner中的mInstance集合将保存着各手势对应的Instance对象。这样的话,在进行手势匹配时,就可以通过执行Learner的getInstances方法取出保存手势对应的Instance对象,然后将保存的Instance对象和当前绘制的手势创建的Instance对象进行匹配;

         对当前手势进行匹配是通过调用GestureLibrary的recognize方法实现的,该法返回描述匹配相似度的ArrayList<Prediction>集合。接下来对该方法的源码实现进行分析;

        --->GestureLibraryrecognize方法实现代码如下:

public abstract class GestureLibrary {
    protected final GestureStore mStore;

    protected GestureLibrary() {
        mStore = new GestureStore();
    }
    ...
    public ArrayList<Prediction> recognize(Gesture gesture) {
        return mStore.recognize(gesture);
    }
    ...
}
      通过上面代码可知,GestureLibraryrecognize方法通过调用GestureStore对象的recognize方法来实现的。  

      --->GestureStorerecognize方法实现代码如下:

public class GestureStore {
    ...
    public static final int SEQUENCE_SENSITIVE = 2;
    ...
    public static final int ORIENTATION_SENSITIVE = 2;
    ...
    private int mSequenceType = SEQUENCE_SENSITIVE;
    private int mOrientationStyle = ORIENTATION_SENSITIVE;
    ...
    private Learner mClassifier;
    ...
    public GestureStore() {
        mClassifier = new InstanceLearner();
    }
    ...
    public ArrayList<Prediction> recognize(Gesture gesture) {
        //根据gesture创建Instance对象
        Instance instance = Instance.createInstance(mSequenceType,
                mOrientationStyle, gesture, null);
        //此处的instance.vector已经过时间采样或空间采样处理
        return mClassifier.classify(mSequenceType, mOrientationStyle, instance.vector);
    }
    ...
}

      在GestureStorerecognize方法中:

        Step1.根据得到的mSequenceType值(默认值为SEQUENCE_SENSITIVE)、mOrientationStyle值(默认值为ORIENTATION_SENSITIVE)、gesture对象(当前手势),通过调用Instance的静态方法createInstance创建相应的Instance对象instance。

       Step2. 根据得到的mSequenceType值值、mOrientationStyle值、instance对象的属性vector,通过调用InstanceLearner对象的classify方法,方法返回的是ArrayList<Prediction>类型。

      --->Instance的静态方法createInstance代码实现如下:

class Instance {
    ...
    /**
     * create a learning instance for a single stroke gesture
     * 
     * @param gesture
     * @param label
     * @return the instance
     */
    static Instance createInstance(int sequenceType, int orientationType, Gesture gesture, String label) {
        float[] pts;
        Instance instance;
        if (sequenceType == GestureStore.SEQUENCE_SENSITIVE) {
            //通过时间采样得到对应手势的样品pts
            pts = temporalSampler(orientationType, gesture);
            instance = new Instance(gesture.getID(), pts, label);
            //对pts手势样品进行正常化
            instance.normalize();
        } else {
            //通过空间采样得到对应手势的样品
            pts = spatialSampler(gesture);
            instance = new Instance(gesture.getID(), pts, label);
        }
        return instance;
    }
    ...
}

     在Instance的静态方法createInstance中:

      Step1.根据得到的gesture中的第一个GestureStroke对象(一个Gesture对象由单个或多个GestureStroke组成)、SEQUENCE_SAMPLE_SIZE值(默认值为16),通过调用GestureUtils的静态方法temporalSampling将GestureStroke对象中封装的多个连续点进行时间采样成多个离散点。然后将得到的多个离散点赋值给浮点型数组pts。

      Step2.对通过时间采样得到的多个离散点进行一些处理操作(计算质心、移动、旋转等),然后将这些通过处理的离散点返回给Instance的createInstance静态方法中的局部变量pts。最终,通过执行temporalSampler(orientationType, gesture)后,局部变量pts存放的是,当前用户绘制的手势中的第一个GestureStroke(单笔画识别)对象经过时间采样生成的多个离散点。

      Step3.执行完temporalSampler(orientationType, gesture)得到pts后,接着,根据得到的当前手势的ID、pts、label(为空)创建Instance对象instance。在Instance的构造函数中,会将ID、pts、label分别赋值给Instance的属性id、vector、label。所以instance. vector即为当前用户绘制的手势经过时间采样后的离散点。

      Step4.在执行创建Instance对象后,通过调用Instance对象的normalize对离散点进行正常化。

       到此,Instance的temporalSampler方法就执行完了,接着会返回创建得到的Instance对象instance。

       --->回到GestureStore的recognize方法中:

       在执行完Instance的静态方法createInstance返回得到的instance对象后,接着继续执行mClassifier.classify(mSequenceType, mOrientationStyle, instance.vector),instance.vector就是已经经过时间采样或空间采样后得到的当前手势对应的多个离散点。mClassifier为InstanceLearner对象,InstanceLearner的classify方法代码实现如下:

class InstanceLearner extends Learner {
    ...
    //分类识别手势
    @Override
    ArrayList<Prediction> classify(int sequenceType, int orientationType, float[] vector) {
        ArrayList<Prediction> predictions = new ArrayList<Prediction>();
        ArrayList<Instance> instances = getInstances();
        int count = instances.size();
        TreeMap<String, Double> label2score = new TreeMap<String, Double>();
        for (int i = 0; i < count; i++) {
            //取出之前保存的Instance和当前的Instance进行比较识别
            Instance sample = instances.get(i);
            if (sample.vector.length != vector.length) {
                continue;
            }
            double distance;
            if (sequenceType == GestureStore.SEQUENCE_SENSITIVE) {   
                //最小的余弦值,此处的vector是经过时间采样的时间序列点
                distance = GestureUtils.minimumCosineDistance(sample.vector, vector, orientationType);
            } else {
                /*平方欧氏距离,欧式距离就是两点之间的距离:如a(x1,y1),b(x2,y2),则欧式距离为d = sqrt((x1-x2)^ + (x2-y2)^)
                 * vector是经过空间采样的点序列
                 */
                distance = GestureUtils.squaredEuclideanDistance(sample.vector, vector);
            }
            double weight;
            if (distance == 0) {
                weight = Double.MAX_VALUE;
            } else {
                weight = 1 / distance;
            }
            Double score = label2score.get(sample.label);
            if (score == null || weight > score) {
                label2score.put(sample.label, weight);
            }
        }

//        double sum = 0;
        for (String name : label2score.keySet()) {
            double score = label2score.get(name);
//            sum += score;
            predictions.add(new Prediction(name, score));
        }

        // normalize
//        for (Prediction prediction : predictions) {
//            prediction.score /= sum;
//        }

        Collections.sort(predictions, sComparator);

        return predictions;
    }
    ...
}
    InstanceLearner的classify中做了如下处理:

     Step1.创建ArrayList<Prediction>集合对象predictions。获取保存在手势库中的所有Instance对象instances(ArrayList<Instance>集合)。创建TreeMap<String, Double>类型映射表label2score,以保存手势的名字为键值,对应保存当前手势与保存手势之间的匹配分数score。

     Step2. 遍历手势库中已保存的instances集合中的每个Instance对象,将遍历出的每个Instance对象中封装的vector和当前Instance对象的vector(classify方法传进来的实参instance.vector)进行处理。

     Step3. 在遍历instances的处理中,当classify方法传进来的sequenceType为GestureStore.SEQUENCE_SENSITIVE(默认值)时,则根据遍历出的每个Instance对象中封装的vector和当前Instance对象的vector,调用GestureUtils的minimumCosineDistance方法,计算这两个vector的最小的余弦值minimumCosineDistance返回distance(double类型)。

     Step4. 在Step3中,当sequenceType不为GestureStore.SEQUENCE_SENSITIVE时,则调用GestureUtils的squaredEuclideanDistance方法,计算这两个vector平方欧氏距离squaredEuclideanDistance返回distance(double类型)。

     Step4. 通过Step3Step4得到distance转化为手势匹配分数score(权重weight = 1/distance即为score), 然后将其以对应被遍历的Instance对象的名字(即已保存的某一手势对应的名字)为键值,保存到集合label2score中。

     Step5. 遍历完instances,得到label2score后,接着将label2score保存的信息进行遍历,将根据遍历得到的每个key值name和value值score,创建对应的Prediction对象,然后将创建得到的Prediction对象添加到集合predictions中。

     Step6. 对predictions集合中的内容进行排序,然后返回predictions。

     所以,调用GestureLibrary的recognize方法进行手势匹配操作,最终返回的是ArrayList<Prediction>集合predictions。遍历predictions中的Prediction对象,通过Prediction对象的score值就可以知道当前手势和已保存手势之间的匹配相似度(即手势匹配分数)。


2018-12-26 09:44:52 u013379553 阅读数 623

其实鼠标手势识别在实际中好像并没有太多应用场景,比较常见的就是浏览器的手势操作,不过感觉这个也比较鸡肋,如果和硬件结合起来会好一些。我是由于一个小项目的需要,所以动手做鼠标手势识别这个东西,本来想在网上找一下看有没有相关文章,奈何很多根本都看不懂。。所以我就自己构思要如何实现,后来我就想到了一种比较简单的方法,经过测试,识别率是挺高的,应该可以>90%。

先上个图:

从实际效果来看,识别率挺不错的。接下来说说我实现的思路。

一、要知道鼠标手势,那就要知道移动的方向,那么我们可以用一个数组来保存鼠标每次移动的方向,如前次坐标(3,5),此次坐标(5,4),则将结果(大于为1,小于为-1,等于与0)记为(1,-1),这时我们便知道鼠标是向右下方滑动的。

二、接着将这些方向与标准的手势进行比较,若方向与上次相同则忽略,比较得出匹配的轨迹种类之后,我们还不能确定就是此轨迹,因为我们只确定了方向,所以此时我们还要将绘制出的轨迹图像与标准轨迹图片进行对比,若相似度大于阈值,则匹配成功。

三、因为用户在移动鼠标的过程中,肯定不可能完全是标准轨迹的样子,所以要设置一个误差范围,在此范围内可认为前后坐标相同。这个误差范围是根据用户绘制的轨迹图像的大小来动态确定的,图像越大,误差范围越大,最高不超过20。然后用户在绘制的过程中,可能出现手抖,可能会导致出现一个与标准轨迹不同的方向,这时我们就要设置一个容错次数,在这个次数内的错误的方向均不计,若超过了,则跳到识别下一个轨迹。

明白了以上三点,那么来写代码也就不难了。那么要怎么做呢?请继续看:

一、保存标准轨迹的配置文件

{ "track":[
{"trackImage":"d:/0/0.png", 
"description":"下一张", 
"function":"NEXT",
"scene":0,
"direction":[[0,1],[1,0]]} ] }

  • trackImage : 鼠标轨迹图片
  • description : 鼠标轨迹描述,将在程序下方提示
  • function : 要执行的功能编号
  • scene : 使用场景(暂时不用,比如说在不同的窗口时执行同样的功能需要按下不同的快捷键)
  • direction : 鼠标轨迹的移动方向,方向越多的话判断起来越准确

二、图像相似度比较

我在网上找了几个算法,直方图比较,均值哈希,汉明距离,发现均值哈希比较好,它的比较过程大体如下:

第一步,缩小尺寸。

将图片缩小到8x8的尺寸,总共64个像素。这一步的作用是去除图片的细节,只保留结构、明暗等基本信息,摒弃不同尺寸、比例带来的图片差异。

第二步,简化色彩。

将缩小后的图片,转为64级灰度。也就是说,所有像素点总共只有64种颜色。

第三步,计算平均值。

计算所有64个像素的灰度平均值。

第四步,比较像素的灰度。

将每个像素的灰度,与平均值进行比较。大于或等于平均值,记为1;小于平均值,记为0。

第五步,计算哈希值。

将上一步的比较结果,组合在一起,就构成了一个64位的整数,这就是这张图片的指纹。组合的次序并不重要,只要保证所有图片都采用同样次序就行了。
得到指纹以后,就可以对比不同的图片,看看64位中有多少位是不一样的。

三、鼠标坐标记录

每隔几次移动后将鼠标坐标保存到一个动态数组中,并且刚开始移动时的坐标不要计入,因为此时的误差范围很小,所以可能会识别出某个轨迹

四、开始识别

int offset=(int)(cut.getWidth()/10.0+2);//鼠标移动时的误差范围
		offset=offset>20?20:offset;
		System.out.println("offset: "+offset+"  "+cut.getWidth());
		double max=0;
		int max_index=-1;//图片相似度最大的轨迹索引
		int interval=MouseTrack.INTERVAL;
		for(int i=0;i<tracks.length();i++) {
			JSONObject obj=tracks.getJSONObject(i);
			JSONArray ts=obj.getJSONArray("direction");
			int ts_i=0;
			String[] last=null;
			String last_dir=null,//前一次的坐标
			last_res="";//前两个坐标比较后的结果
			int mistake_times=0;//容错率
			String last_mistake="";
			for(String dir:dis) {//遍历鼠标运动方向
			String[] ds=dir.split(",");//此次的坐标
			if(last_dir!=null) {
				last=last_dir.split(",");//上次的坐标
				int lx=Integer.parseInt(last[0]),ly=Integer.parseInt(last[1]),
					nx=Integer.parseInt(ds[0]),ny=Integer.parseInt(ds[1]);
				int ox=nx-lx>offset?1:nx-lx<=-offset?-1:0
						,oy=ny-ly>offset?1:ny-ly<=-offset?-1:0;
					String dir_res=ox+","+oy;//得到方向
						
				if(ts_i>=ts.length()) {//超出标准轨迹的方向数目了,允许小范围内的超出
							if(interval--==0) {//每移动10次记录一次,不然太密集的话总是在误差范围内
							last_res=dir_res;
							interval=MouseTrack.INTERVAL;
							}
							if(!last_res.equals(dir_res)) {//瞎画的时候退出
							ts_i=0;
							break;
							}
							continue;
						}
						
			if((!dir_res.equals(last_res))) {//新的运动方向
						
						if((dir_res).equals(ts.getString(ts_i))) {//运动方向与轨迹吻合
						ts_i++;
						last_res=dir_res;
						}else if(!last_mistake.equals(dir_res)&&mistake_times++>MAX_MISTAKE_TIMES) {//同个错误不重复计入
							last_mistake=dir_res;
							break;
						}
					}
					last_dir=dir;
				}else {
					last_dir=dir;
				}
			}
				System.out.println(i+" ) Mistake: "+mistake_times);
		if(mistake_times>MAX_MISTAKE_TIMES)continue;
			if(ts_i==ts.length()) {//手势运动方向吻合,判断图片相似度
				double tmp=new FingerPrint(cut).compare(trackImages[i]);
					if(tmp>max) {
						max=tmp;
						max_index=i;
					}
					
				}
				
		}
		if(max_index>=0&&max>=0.8) {//有匹配的轨迹
			tip.setVisible(true);
			JSONObject obj=tracks.getJSONObject(max_index);
			tip.setIcon(new ImageIcon(drawTip(obj.getString("description"))));
			func=obj.getString("function");
			if(!sameFlag) {
				
				sameFlag=true;
			}
		}else {
			func="NONE";
			tip.setIcon(new ImageIcon(invalid));
		}
		

大致的过程就是如此,github项目地址:https://github.com/starkZH/MouseTrack-Recognition

 

 

2016-03-09 23:50:53 su749520 阅读数 1302

引子

印度客户的一个需求,希望实现来电时翻转静音的功能。具体如下:
1.电话铃声到来时;
2.采取下面动作:
a.手机正面翻到背面<顺时针或者逆时针旋转180度>
b.手机背面翻到正面<顺时针或者逆时针旋转180度>
3.来电静音,或者你喜欢的话,可以换成翻转闹铃静音;

技术点

1.数据来源:ACC传感器(即重力加速度传感器)
2.翻转算法:根据翻转动作的三轴原始数据变化观察,找出规律完成算法;

本算法的价值

翻转的识别度 > 95%,欢迎直接复制使用,大家快乐分享代码呗。
废话不多说了,直接上Android代码.

翻转算法实现步骤:

1.注册ACC传感器的使用权利,在程序的onResume()或者onCreate()找个地方,实现具体如下代码:
    SensorManager mSensorManager = (SensorManager) mContext.getSystemService(Context.SENSOR_SERVICE);
    mSensorManager.registerListener(this, mSensorManager.getDefaultSensor(Sensor.TYPE_ACCELEROMETER), SensorManager.SENSOR_DELAY_NORMAL);
2. 接下来完成一个好习惯,在程序的onPause()或者onDestory()进行注销ACC传感器的使用,因为如果忘了会导致用户无意和无形中过多损失的电量。步骤如下:
    if (mSensorManager != null) {
        mSensorManager.unregisterListener(mSensorListener);
3.在接下来实现SensorEventListener 接口,类似下面的:
 public class xxx implement SensorEventListener {  
4.上面步骤完成了,需要重新SensorEventListener 对应onSensorChanged的方法,下面直接贴代码了(本文的核心)
    private float curZ;
    private float preZ;
    private int count;
    private SensorManager mSensorManager;
    private static final int FLIP_MAX = 10; 

   @Override
   public void onSensorChanged(SensorEvent event) {
        if (event.sensor.getType() != Sensor.TYPE_ACCELEROMETER){      
            return;
        }                                          
        curZ = event.values[SensorManager.DATA_Z];
        if (count++ % FLIP_MAX == 0) {
            Log.v(this, "Flip->current=" + curZ + " ,preZ = " + preZ);
            if ((curZ * preZ) < 0 
                  && (Math.abs(curZ - preZ) > FLIP_MAX)) {    
                  // 判定翻转动作生效
                 Log.v(this, "suhuazhi Flip->" + curZ + ",preZ" + preZ); 
                 silent();   
             }
          }
        preZ = curZ;
        count = 1;
      }
    }
5.铃声静音的功能代码块
    private void silent(){
        TelecomManager tm;
        tm = (TelecomManager).getSystemService.
            (Context.TELECOM_SERVICE);
        if (tm != null && tm.isRinging()) {
            tm .silenceRinger();
        }
    }

结束语

希望上面的手势体感的翻转算法能给你的开发带来帮助!
感恩开源,支持开源,以前经常索取,现在我也要分享自己的代码。

2019-05-19 16:44:13 theblacksummer 阅读数 56

KNN算法

一、KNN算法概述

kNN算法的核心思想是如果一个样本在特征空间中的k个最相邻的样本中的大多数属于某一个类别,则该样本也属于这个类别,并具有这个类别上样本的特性。该方法在确定分类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。

二、KNN算法介绍

最简单最初级的分类器是将全部的训练数据所对应的类别都记录下来,当测试对象的属性和某个训练对象的属性完全匹配时,便可以对其进行分类。但是怎么可能所有测试对象都会找到与之完全匹配的训练对象呢,其次就是存在一个测试对象同时与多个训练对象匹配,导致一个训练对象被分到了多个类的问题,基于这些问题呢,就产生了KNN。 KNN是通过测量不同特征值之间的距离进行分类。它的的思路是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。K通常是不大于20的整数。KNN算法中,所选择的邻居都是已经正确分类的对象。该方法在定类决策上只依据最邻近的一个或者几个样本的类别来决定待分样本所属的类别。 下面通过一个简单的例子说明一下:如下图,绿色圆要被决定赋予哪个类,是红色三角形还是蓝色四方形?如果K=3,由于红色三角形所占比例为2/3,绿色圆将被赋予红色三角形那个类,如果K=5,由于蓝色四方形比例为3/5,因此绿色圆被赋予蓝色四方形类。
在这里插入图片描述

由此也说明了KNN算法的结果很大程度取决于K的选择。
在KNN中,通过计算对象间距离来作为各个对象之间的非相似性指标,避免了对象之间的匹配问题,在这里距离一般使用欧氏距离或曼哈顿距离:
在这里插入图片描述
同时,KNN通过依据k个对象中占优的类别进行决策,而不是单一的对象类别决策。这两点就是KNN算法的优势。
接下来对KNN算法的思想总结一下:就是在训练集中数据和标签已知的情况下,输入测试数据,将测试数据的特征与训练集中对应的特征进行相互比较,找到训练集中与之最为相似的前K个数据,则该测试数据对应的类别就是K个数据中出现次数最多的那个分类,其算法的描述为:
1)计算测试数据与各个训练数据之间的距离;
2)按照距离的递增关系进行排序;
3)选取距离最小的K个点;
4)确定前K个点所在类别的出现频率;
5)返回前K个点中出现频率最高的类别作为测试数据的预测分类。

代码:
from numpy import *
class KnnClassifier(object):
def init(self,labels,samples):
“”" Initialize classifier with training data. “”
self.labels = labels
self.samples = sample
def classify(self,point,k=3):
“”" Classify a point against k nearest
in the training data, return label. “”"
# compute distance to all training points
dist = array([L2dist(point,s) for s in self.samples])
# sort them
ndx = dist.argsort()
# use dictionary to store the k nearest
votes = {}
for i in range(k):
label = self.labels[ndx[i]]
votes.setdefault(label,0)
votes[label] += 1
return max(votes, key=lambda x: votes.get(x))

def L2dist(p1,p2):
return sqrt( sum( (p1-p2)**2) )

def L1dist(v1,v2):
return sum(abs(v1-v2))

-- coding: utf-8 --
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([5, 1])
labels = hstack((ones(n), -ones(n)))
#save with Pickle
#with open(‘points_normal.pkl’, ‘w’) as f:
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) + 5
angle = 2 * pi * randn(n, 1)
class_2 = hstack((r * cos(angle), r * sin(angle)))
labels = hstack((ones(n), -ones(n)))
#save with Pickle
#with open(‘points_ring.pkl’, ‘w’) as f:
with open(‘points_ring_test.pkl’, ‘wb’) as f:
pickle.dump(class_1, f)
pickle.dump(class_2, f)
pickle.dump(labels, f)

print(“save OK!”)

#-- coding: utf-8 --
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)])
e 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)
savefig(“test1.png”)
show()
实验结果:
在这里插入图片描述
在这里插入图片描述

稠密SIFT算法

一、原理

传统的SIFT算法即Sparse SIFT,不能很好地表征不同类之间的特征差异,达不到所需的分类要求。而Dense SIFT算法,是一种对输入图像进行分块处理,再进行SIFT运算的特征提取过程。Dense SIFT根据可调的参数大小,来适当满足不同分类任务下对图像的特征表征能力。
该算法首先将表达目标的矩形区域分成相同大小的矩形块,计算每一个小块的SIFT特征,再对各个小块的稠密SIFT特征在中心位置进行采样,建模目标的表达.然后度量两个图像区域的不相似性,先计算两个区域对应小块的Bhattacharyya距离,再对各距离加权求和作为两个区域间的距离.因为目标所在区域靠近边缘的部分可能受到背景像素的影响,而区域的内部则更一致,所以越靠近区域中心权函数的值越大.最后提出了能适应目标尺度变化的跟踪算法。
代码:
#-- coding: utf-8 --
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(’.ppm’)]

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/test1’)
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)
实验结果:
在这里插入图片描述
实验总结:
在进行图片识别时,KNN算法对图片的识别敏感。
在训练集大的时,正确率可以达到80%左右。
在训练集小的时,正确率可以达到50%左右。
在静态手势数据库下,陌生场景下的手势正确率只能达到7%左右,但是保持稳定状态。
从一方面,说明训练集过小,容易造成数据过拟合的问题
从另一方面,对不是很明显的手势区别也可以判断,分类敏感。

2018-11-23 20:50:05 dingjikerbo 阅读数 99

计算机视觉在移动端的应用,典型的如手势识别,人脸识别,流程都差不多,都是利用移动端的相机采集数据,丢给算法层,根据识别的结果来做一些业务,中间可能还要做一些图形的渲染。

本文主要讨论这中间涉及到的一些问题以及优化的思路,算是对过往工作的总结吧。大致问题有以下五点:

一,相机采集数据的格式是NV21,而算法层所需的格式是RGB,这中间需要转换,对于每秒30帧,每帧1920*1080的图像转换的耗时还是不可忽视的。

二,算法层耗时在20ms-80ms不定,这样平均下来算法输出帧率大概在15~20,而相机的原始帧率是30,这会造成明显的延时,所以如何提升算法的输出帧率是个问题。

三,整个流程是异步的,相机数据是异步的,RGB转换是异步的,算法是异步的,渲染也是异步的,如何设计整个系统让数据流稳定地跑起来,要注意线程同步的问题。

四,设计到大量的数据读写,要尽可能减少数据拷贝,尽可能复用对象

五,图形渲染,除了相机每秒30帧的预览数据,还有额外关于人脸和手的渲染效果

先说说第一点,RGB转换用Java实现肯定性能是有问题的,后来改用C++实现了,对于1280*720的帧转换平均要10ms,1920*1080可能要20ms左右了,Neon实现可能效果会好不少,不过没试过。我这里是直接采用GPU来做转换的,可以参考我的Github项目Android-Camera,其中对GPU的RGB转换的几种方案做了实验和对比,性能最好的是采用PBuffer和PBO的方式,对于1280*720转换降到了2ms,1920*1280在6ms左右,这样差不多可以接受了,而且也没有占用CPU。这里转换生成的RGB可以丢给算法层,也可以保存为本地图像。

再来说说第二点,算法层耗时较多会拖慢输出帧率,通常是在视野内没有聚焦时的全量扫描会非常耗时,当跟踪到手或脸之后就会快多了。除了算法层优化之外,移动端也可以进一步优化以提高输出帧率。常规流程是相机的帧数据来之后,先判断当前算法层是否Busy,如果Busy则丢弃当前相机帧,如果Free则将相机帧做RGB转换,然后丢给算法层。这样逻辑上实现相对简单,但是仔细分析后会发现算法层其实有一部分时间是白白浪费的,极端的情况是相机上一帧刚过,算法层就返回了,结果要等到下一帧数据来时才能开始下一次计算,这就白白浪费了30ms。解决的方式是采用双缓冲,开辟两个buffer,一个buffer用于算法层计算,另一个用于相机帧写入,当算法层返回时,切换到另一个buffer继续算,而无需额外等待,这样吞吐量就提升了。效果还是很明显的,基本能到25帧左右。关键代码如下:

public class DoubleBuffer {

    private FrameBuffer[] mBuffers;

    /**
     * 另一个buffer是否准备好了
     */
    private volatile boolean mReady;

    /**
     * 当前正在占用的buffer
     */
    private volatile int mActive = 0;

    public DoubleBuffer() {
        mBuffers = new FrameBuffer[2];
        mBuffers[0] = new FrameBuffer();
        mBuffers[1] = new FrameBuffer();
    }

    public FrameBuffer get() {
        synchronized (mBuffers) {
            while (!mReady) {
                try {
                    mBuffers.wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            mActive = 1 - mActive;
            mReady = false;
            return mBuffers[mActive];
        }
    }

    public void put(final ByteBuffer yuv, final ByteBuffer rgba) {
        synchronized (mBuffers) {
            int idx = 1 - mActive;
            mBuffers[idx].put(yuv, rgba);
            mReady = true;
            mBuffers.notifyAll();
        }
    }
}

再来说说第三点,首先相机帧数据过来要先丢给GPU做RGB转换,GPU在单独一个线程将NV21渲染成纹理,然后读出RGB像素数据丢到Double Buffer中,这个是不能做耗时操作阻塞的,如果有截图的需要,可以在这里保存RGB图像到文件,注意另开一个线程。而算法层由于耗时较多,所以也要单独放在一个线程,此外图像渲染也是单独一个线程。算法层所在的线程要不断地从Double Buffer中取数据运算,识别出手和人脸,然后给结果保存下来,跟随接下来的相机帧一起渲染,如给手和人脸框出来,这个理论上是有延迟的,尤其当手移动很快时,框会跟不上手的移动。不过如果算法层的输出帧率能到25以上,问题就不大了。

再来说说第四点,要减少数据拷贝,尽可能复用对象避免频繁GC。减少数据拷贝尤其是在Java层和算法层之间传递数据时。图像相关的操作都要小心翼翼,一方面要尽可能复用缓冲,同时要小心内存泄露,因为一帧的缓冲就是8M,

最后说说第五点,要实现相同的效果有几种方案,可以将相机预览输出到TextureView,然后在canvas上画人脸和手框,但是性能堪忧。也可以做几层Surface View,底层是相机预览,上层Surface是做人脸和手框,还可以再叠加一层Surface做其它动画。不过这样实在是太费事了,麻烦不说,每个Surface渲染都要单独开线程,并且如果需要同时录制相机预览和人脸框就没法做,因为是分开在两个Surface中渲染的,录制通常是围绕一个Surface的数据进行的。所以比较好的方案是采用一层Surface,然后所有东西都绘制在一起,只用一个渲染线程,录制视频也方便。另外还要说说GLSurfaceView和SurfaceView,这两个其实是一回事,GLSurfaceView是继承自SurfaceView,只不过内部自动开了个渲染线程,并且自己管理Egl上下文。而如果我们用SurfaceView的话这些都得自己来处理了,虽然麻烦些,但是灵活性很好。比如我们可以给EglContext共享给另一个渲染线程,这样就可以共享纹理,而无需重复渲染,但是GLSurface中EglContext是没有开放出来的。

手势识别

阅读数 1

没有更多推荐了,返回首页