精华内容
下载资源
问答
  • 相似性度量方法介绍

    2018-03-21 11:32:05
    相似性度量的一些方法总结,方便使用,便于操作编写代码
  • 推荐系统中相似性度量标准

    1、 皮尔逊相关系数
    在早期的推荐系统中皮尔逊相关系数是一个基础的相似性衡量标准,先从这个参数定义开始说起。
    这里写图片描述
    皮尔逊系数度量两个一一对应数列之间的线性相关程度,上述四种公式都是计算该系数方法,下面python 代码使用就是公式4。

    def sim_pearson(prefs,p1,p2):
        # Get the list of mutually rated items
        si={}
        for item in prefs[p1]: 
            if item in prefs[p2]: si[item]=1
        # if they are no ratings in common, return 0
        if len(si)==0: 
            return 0
        # Sum calculations
        n=len(si)
        # Sums of all the preferences
        sum1=sum([prefs[p1][it] for it in si])
        sum2=sum([prefs[p2][it] for it in si])  
        # Sums of the squares
        sum1Sq=sum([pow(prefs[p1][it],2) for it in si])
        sum2Sq=sum([pow(prefs[p2][it],2) for it in si])      
    # Sum of the products
        pSum=sum([prefs[p1][it]*prefs[p2][it] for it in si])  
    # Calculate r (Pearson score)
        num=pSum-(sum1*sum2/n)
        den=sqrt((sum1Sq-pow(sum1,2)/n)*(sum2Sq-pow(sum2,2)/n))
        if den==0:
            return 0
        r=num/den
        return r

    说完皮尔逊系数的计算后我们来分析该系数的优势和不足。
    优势:该系数可以修正‘夸大分值’的情况,举例就是user1 倾向总是评分为高分,user2 倾向总是评分在低分区域,加入使用时欧式距离这样两个user的相似性比较低,但是其实两个user爱好可能类似,只是他们对分数的标准不是那么一致。
    不足:首先没有考虑到两个用户的给出评分数目,两个看过200部电影的用户,即便他们偶尔有些评分不一致,但我们也会觉得比两个仅仅看了2部相同电影用户相似。
    其次,根据公式可以发现,如果两个user重叠的评分只有一个item 这样,该公式定义是无法进行计算的,在稀疏数据集上面这个问题尤其凸显出来,当然如果两个用户重叠次数太少我们也基本可以认为两者相似性不高。
    最后,根据公式可以明显发现,如果一个user评分序列中所有的评分都是一样的,这样导致该公式是未定义的。

    2、 欧式距离定义相似度
    这是最常用相似度,不做详细介绍。
    3、 余弦相似性度量
    简单贴下mahout中余弦公式实现

     public static double distance(double[] p1, double[] p2) {
        double dotProduct = 0.0;
        double lengthSquaredp1 = 0.0;
        double lengthSquaredp2 = 0.0;
        for (int i = 0; i < p1.length; i++) {
          lengthSquaredp1 += p1[i] * p1[i];
          lengthSquaredp2 += p2[i] * p2[i];
          dotProduct += p1[i] * p2[i];
        }
        double denominator = Math.sqrt(lengthSquaredp1) * Math.sqrt(lengthSquaredp2);
    
        // correct for floating-point rounding errors
        if (denominator < dotProduct) {
          denominator = dotProduct;
        }
    
        // correct for zero-vector corner case
        if (denominator == 0 && dotProduct == 0) {
          return 0;
        }
    
        return 1.0 - dotProduct / denominator;
      }
    

    4、 斯皮尔曼相关系数
    理论可以参考这个博客:http://blog.csdn.net/wsywl/article/details/5859751
    下面是mahout中该参数实现主要部分

     @Override
      public double userSimilarity(long userID1, long userID2) throws TasteException {
        PreferenceArray xPrefs = dataModel.getPreferencesFromUser(userID1);
        PreferenceArray yPrefs = dataModel.getPreferencesFromUser(userID2);
        int xLength = xPrefs.length();
        int yLength = yPrefs.length();
    
        if (xLength <= 1 || yLength <= 1) {
          return Double.NaN;
        }
    
        // Copy prefs since we need to modify pref values to ranks
        xPrefs = xPrefs.clone();
        yPrefs = yPrefs.clone();
    
        // First sort by values from low to high
        xPrefs.sortByValue();
        yPrefs.sortByValue();
    
        // Assign ranks from low to high
        float nextRank = 1.0f;
        for (int i = 0; i < xLength; i++) {
          // ... but only for items that are common to both pref arrays
          if (yPrefs.hasPrefWithItemID(xPrefs.getItemID(i))) {
            xPrefs.setValue(i, nextRank);
            nextRank += 1.0f;
          }
          // Other values are bogus but don't matter
        }
        nextRank = 1.0f;
        for (int i = 0; i < yLength; i++) {
          if (xPrefs.hasPrefWithItemID(yPrefs.getItemID(i))) {
            yPrefs.setValue(i, nextRank);
            nextRank += 1.0f;
          }
        }
    
        xPrefs.sortByItem();
        yPrefs.sortByItem();
    
        long xIndex = xPrefs.getItemID(0);
        long yIndex = yPrefs.getItemID(0);
        int xPrefIndex = 0;
        int yPrefIndex = 0;
    
        double sumXYRankDiff2 = 0.0;
        int count = 0;
    
        while (true) {
          int compare = xIndex < yIndex ? -1 : xIndex > yIndex ? 1 : 0;
          if (compare == 0) {
            double diff = xPrefs.getValue(xPrefIndex) - yPrefs.getValue(yPrefIndex);
            sumXYRankDiff2 += diff * diff;
            count++;
          }
          if (compare <= 0) {
            if (++xPrefIndex >= xLength) {
              break;
            }
            xIndex = xPrefs.getItemID(xPrefIndex);
          }
          if (compare >= 0) {
            if (++yPrefIndex >= yLength) {
              break;
            }
            yIndex = yPrefs.getItemID(yPrefIndex);
          }
        }
    
        if (count <= 1) {
          return Double.NaN;
        }
    
        // When ranks are unique, this formula actually gives the Pearson correlation
        return 1.0 - 6.0 * sumXYRankDiff2 / (count * (count * count - 1));
      }
    
    展开全文
  • 最近做目标跟踪时,需要度量两个模板的相似性,来寻找目标,当跟踪的目标的特征选取后,相似性度量函数,就是影响跟踪效果的关键因素了,对比了几种相似性度量函数,最终选取了一种方法----直方图欧氏距离的相似性...

      最近做目标跟踪时,需要度量两个模板的相似性,来寻找目标,当跟踪的目标的特征选取后,相似性度量函数,就是影响跟踪效果的关键因素了,对比了几种相似性度量函数,最终选取了一种方法----直方图欧氏距离的相似性度量方法。

    理论公式为:

    matlab代码为:

    function comFit = comFitness(target1,target2,N)
    %target1和target2表示两个模板的直方图,N为直方图的大小
    comFit = 0;
    for i = 1 : N
        max_feature = max(target1(i),target2(i));
        abs_minus = abs(target1(i)-target2(i));
        comFit = comFit + 1 - (abs_minus/max_feature);
    end
    comFit = comFit / N;
    

      

     

    转载于:https://www.cnblogs.com/gousheng/p/6579408.html

    展开全文
  • 时间序列相似性度量-DTW

    万次阅读 多人点赞 2019-01-25 16:44:59
    最近项目中遇到求解时间序列相似性问题,这里序列也可以看成向量。在传统算法中,可以用余弦相似度和pearson相关系数来描述两个序列的相似度。但是时间序列比较特殊,可能存在两个问题: 两段时间序列长度不同。...

    1. 背景

    最近项目中遇到求解时间序列相似性问题,这里序列也可以看成向量。在传统算法中,可以用余弦相似度和pearson相关系数来描述两个序列的相似度。但是时间序列比较特殊,可能存在两个问题:

    1. 两段时间序列长度不同。如何求相似度?
    2. 一个序列是另一个序列平移之后得到的。如何求相似距离?

    第一个问题,导致了根本不能用余弦相似度和pearson相关系数来求解相似。第二个问题,导致了也不能基于欧式距离这样的算法,来求解相似距离。比如下面两个长度不同的序列:

    s1 = [1, 2, 0, 1, 1, 2]
    s2 = [1, 0, 1]
    

    本文记录一种算法,一方面:如果两个序列中的其中一个序列是另一个序列的平移序列,则可以比较合理的求出两个序列的相似距离。另一方面:也可以求解长度不同序列的相似距离。主要参考:dtaidistance 这个项目的源码和其中的Dynamic Time Warping (DTW)思想。

    同时基于这个算法,先计算相似距离,再把相似距离通过 11+dist\frac{1}{1+dist} 转化为相似度。这样就可以得到长度不同向量的相似度。

    2. 核心思想

    Dynamic Time Warping (DTW) 本质上和通过动态规划来计算这个序列的相似距离。其实这和求解字符串的最长公共子串、子序列这类问题本质比较类似,参考:

    这里基于动态规划构建序列a和序列b的距离矩阵dp[i][j],其中dp[i][j]表示序列a[0:i]和b[0:j]之间的相似距离的平方。并且有:
    dp[i][j]={(a[0]b[0])2i = 0, j = 0(a[0]b[j])2+dp[0][j1]i = 0(a[i]b[0])2+dp[i1][0]j = 0(a[i]b[j])2+min(dp[i1][j],dp[j1][i],dp[i1][j1])i,j>0 dp[i][j] = \begin{cases} (a[0] - b[0])^2 \quad\quad &\text{i = 0, j = 0} \\ (a[0] - b[j])^2 + dp[0][j-1] \quad\quad &\text{i = 0} \\ (a[i] - b[0])^2 + dp[i-1][0] \quad\quad &\text{j = 0} \\ (a[i] - b[j])^2 + min(dp[i-1][j],dp[j-1][i],dp[i-1][j-1]) \quad\quad &i,j > 0 \end{cases}

    所以dp[len(a)-1][len(b)-1] 就是相似距离的平方,最后开方就是两个时间序列的相似距离,这也就是DTW算法核心实现。实际上,上文的那个github核心代码其实也就是这么写的,只不过在此基础上加了其他参数、画图、层次聚类的代码实现而已。

    3. 实现

    在实际使用中解读了dtaidistance这个项目的源码,其中除去所有参数后,DTW最简单的实现如下:

    import numpy as np
    
    float_formatter = lambda x: "%.2f" % x
    np.set_printoptions(formatter={'float_kind': float_formatter})
    
    
    def TimeSeriesSimilarity(s1, s2):
        l1 = len(s1)
        l2 = len(s2)
        paths = np.full((l1 + 1, l2 + 1), np.inf)  # 全部赋予无穷大
        paths[0, 0] = 0
        for i in range(l1):
            for j in range(l2):
                d = s1[i] - s2[j]
                cost = d ** 2
                paths[i + 1, j + 1] = cost + min(paths[i, j + 1], paths[i + 1, j], paths[i, j])
    
        paths = np.sqrt(paths)
        s = paths[l1, l2]
        return s, paths.T
    
    
    if __name__ == '__main__':
        s1 = [1, 2, 0, 1, 1, 2]
        s2 = [1, 0, 1]
    
        distance, paths = TimeSeriesSimilarity(s1, s2)
        print(paths)
        print("=" * 40)
        print(distance)
    

    输出

    [[0.00 inf inf inf inf inf inf]
    [inf 0.00 1.00 1.41 1.41 1.41 1.73]
    [inf 1.00 2.00 1.00 1.41 1.73 2.45]
    [inf 1.00 1.41 1.41 1.00 1.00 1.41]]
    ========================================
    1.4142135623730951
    

    这里的矩阵
    [0.001.001.411.411.411.731.002.001.001.411.732.451.001.411.411.001.001.41] \begin{bmatrix} 0.00 & 1.00 & 1.41 & 1.41 & 1.41 & 1.73 \\ 1.00 & 2.00 & 1.00 & 1.41 & 1.73 & 2.45 \\ 1.00 & 1.41 & 1.41 & 1.00 & 1.00 & 1.41 \end{bmatrix}

    就是dp[i][j]。这里代码用另一种写法实现了求解dp[i][j]。并且矩阵右下角元素1.41,就是我们求解的相似距离。

    4. 改进

    其实在实际使用中,我们发现该算法对周期序列的距离计算不是很好。尤其两个序列是相同周期,但是是平移后的序列。如下:

    s1 = np.array([1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1])
    s2 = np.array([0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2])
    s3 = np.array([0.8, 1.5, 0, 1.2, 0, 0, 0.6, 1, 1.2, 0, 0, 1, 0.2, 2.4, 0.5, 0.4])
    

    用图表展示:

    很明显从图中可以看到s1s_1s2s_2是相同的时间序列,但是s1s_1s2s_2平移后得到的,s3s_3是我随意构造的一个序列。但是,现在用上面的算法求解,得:
    dist(s1,s2)=2.0dist(s1,s3)=1.794435844492636 \begin{aligned} dist(s_1,s_2) &= 2.0 \\ dist(s_1,s_3) &= 1.794435844492636 \end{aligned}

    我们发现s1s_1s3s_3反而比较像,这是我们不能接受的。因此,这里需要对算法有个改进。以下有两个改进策略。

    4.1 改进策略1

    目的是想求得一个惩罚系数α\alpha,这个α\alpha和原算法的distance相乘,得到更新后的distance。首先基于原算法包dtaidistance,可以求出dp[i][j]从左上角,到右下角的最优路径。

    其实这样的最优路径,可以用图示表示,比如s1s_1s2s_2的dp[i][j]的最优路径:

    再比如s1s_1s3s_3的dp[i][j]的最优路径:

    其实可以很明显看到,s1s_1s2s_2的最优路径拐点比较少,对角直线很长。而s1s_1s3s_3的拐点比较多,对角直线很短。因此我基于这个考虑进行优化,公式如下:
    α=1i=1ncomLeni2seqLen2 \alpha = 1- \sqrt{\sum_{i=1}^n \frac{comLen_i^2}{seqLen^2}}

    其中seqLen 是这个图中最优路径节点个数,comLenicomLen_i表示每段对角直线的长度。求和后开发表示一个长度系数,这个长度系数越大,表示对角直线越长。最后1减去这个长度系数得到,我们要的衰减系数α\alpha。以下是代码实现:

    说明:这里best_path()是直接摘自dtaidistance,TimeSeriesSimilarity()方法是修改自这个项目。

    import numpy as np
    import math
    
    
    def get_common_seq(best_path, threshold=1):
        com_ls = []
        pre = best_path[0]
        length = 1
        for i, element in enumerate(best_path):
            if i == 0:
                continue
            cur = best_path[i]
            if cur[0] == pre[0] + 1 and cur[1] == pre[1] + 1:
                length = length + 1
            else:
                com_ls.append(length)
                length = 1
            pre = cur
        com_ls.append(length)
        return list(filter(lambda num: True if threshold < num else False, com_ls))
    
    
    def calculate_attenuate_weight(seqLen, com_ls):
        weight = 0
        for comlen in com_ls:
            weight = weight + (comlen * comlen) / (seqLen * seqLen)
        return 1 - math.sqrt(weight)
    
    
    def best_path(paths):
        """Compute the optimal path from the nxm warping paths matrix."""
        i, j = int(paths.shape[0] - 1), int(paths.shape[1] - 1)
        p = []
        if paths[i, j] != -1:
            p.append((i - 1, j - 1))
        while i > 0 and j > 0:
            c = np.argmin([paths[i - 1, j - 1], paths[i - 1, j], paths[i, j - 1]])
            if c == 0:
                i, j = i - 1, j - 1
            elif c == 1:
                i = i - 1
            elif c == 2:
                j = j - 1
            if paths[i, j] != -1:
                p.append((i - 1, j - 1))
        p.pop()
        p.reverse()
        return p
    
    
    def TimeSeriesSimilarity(s1, s2):
        l1 = len(s1)
        l2 = len(s2)
        paths = np.full((l1 + 1, l2 + 1), np.inf)  # 全部赋予无穷大
        paths[0, 0] = 0
        for i in range(l1):
            for j in range(l2):
                d = s1[i] - s2[j]
                cost = d ** 2
                paths[i + 1, j + 1] = cost + min(paths[i, j + 1], paths[i + 1, j], paths[i, j])
    
        paths = np.sqrt(paths)
        s = paths[l1, l2]
        return s, paths.T
    
    
    if __name__ == '__main__':
        # 测试数据
        s1 = np.array([1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1])
        s2 = np.array([0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2])
        s3 = np.array([0.8, 1.5, 0, 1.2, 0, 0, 0.6, 1, 1.2, 0, 0, 1, 0.2, 2.4, 0.5, 0.4])
    
        # 原始算法
        distance12, paths12 = TimeSeriesSimilarity(s1, s2)
        distance13, paths13 = TimeSeriesSimilarity(s1, s3)
    
        print("更新前s1和s2距离:" + str(distance12))
        print("更新前s1和s3距离:" + str(distance13))
    
        best_path12 = best_path(paths12)
        best_path13 = best_path(paths13)
    
        # 衰减系数
        com_ls1 = get_common_seq(best_path12)
        com_ls2 = get_common_seq(best_path13)
    
        # print(len(best_path12), com_ls1)
        # print(len(best_path13), com_ls2)
        weight12 = calculate_attenuate_weight(len(best_path12), com_ls1)
        weight13 = calculate_attenuate_weight(len(best_path13), com_ls2)
    
        # 更新距离
        print("更新后s1和s2距离:" + str(distance12 * weight12))
        print("更新后s1和s3距离:" + str(distance13 * weight13))
    

    输出:

    更新前s1和s2距离:2.0
    更新前s1和s3距离:1.794435844492636
    更新后s1和s2距离:0.6256314581274465
    更新后s1和s3距离:0.897217922246318
    

    结论:
    用新的算法更新后,我们会发现s1和s2距离比s1和s3的距离更加接近了,这就是我们要的结果。

    4.2 改进策略2

    也想求得一个惩罚系数α\alpha。方案如下:

    1. 先求解两个序列seq1和seq2的最长公共子串,长度记为a。
    2. 因为seq1和seq2是数值序列,在求最长公共子串时,设置了一个最大标准差的偏移容忍。也就是说,两个数值在这个标准差内,认为也是公共子串中的一部分。
    3. 衰减系数:α=1a×alen(seq1)×len(seq2)\alpha = 1 - \frac{a \times a}{len(seq1) \times len(seq2)}

    也就是说,两个数值序列的最长公共子串越长,则衰减系数越小。这里把:s2 = np.array([0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2])改成s2 = np.array([0, 1, 1, 2, 0, 1, 1.7, 2, 0, 1, 1, 2, 0, 1, 1, 2]),来验证最大标准差的偏移容忍。

    实际代码实现和效果如下:

    import numpy as np
    
    float_formatter = lambda x: "%.2f" % x
    np.set_printoptions(formatter={'float_kind': float_formatter})
    
    
    def TimeSeriesSimilarityImprove(s1, s2):
        # 取较大的标准差
        sdt = np.std(s1, ddof=1) if np.std(s1, ddof=1) > np.std(s2, ddof=1) else np.std(s2, ddof=1)
        # print("两个序列最大标准差:" + str(sdt))
        l1 = len(s1)
        l2 = len(s2)
        paths = np.full((l1 + 1, l2 + 1), np.inf)  # 全部赋予无穷大
        sub_matrix = np.full((l1, l2), 0)  # 全部赋予0
        max_sub_len = 0
    
        paths[0, 0] = 0
        for i in range(l1):
            for j in range(l2):
                d = s1[i] - s2[j]
                cost = d ** 2
                paths[i + 1, j + 1] = cost + min(paths[i, j + 1], paths[i + 1, j], paths[i, j])
                if np.abs(s1[i] - s2[j]) < sdt:
                    if i == 0 or j == 0:
                        sub_matrix[i][j] = 1
                    else:
                        sub_matrix[i][j] = sub_matrix[i - 1][j - 1] + 1
                        max_sub_len = sub_matrix[i][j] if sub_matrix[i][j] > max_sub_len else max_sub_len
    
        paths = np.sqrt(paths)
        s = paths[l1, l2]
        return s, paths.T, [max_sub_len]
    
    
    def calculate_attenuate_weight(seqLen1, seqLen2, com_ls):
        weight = 0
        for comlen in com_ls:
            weight = weight + comlen / seqLen1 * comlen / seqLen2
        return 1 - weight
    
    
    if __name__ == '__main__':
        # 测试数据
        s1 = np.array([1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1, 1, 2, 0, 1])
        s2 = np.array([0, 1, 1, 2, 0, 1, 1.7, 2, 0, 1, 1, 2, 0, 1, 1, 2])
        s3 = np.array([0.8, 1.5, 0, 1.2, 0, 0, 0.6, 1, 1.2, 0, 0, 1, 0.2, 2.4, 0.5, 0.4])
    
        # 原始算法
        distance12, paths12, max_sub12 = TimeSeriesSimilarityImprove(s1, s2)
        distance13, paths13, max_sub13 = TimeSeriesSimilarityImprove(s1, s3)
    
        print("更新前s1和s2距离:" + str(distance12))
        print("更新前s1和s3距离:" + str(distance13))
    
        # 衰减系数
        weight12 = calculate_attenuate_weight(len(s1), len(s2), max_sub12)
        weight13 = calculate_attenuate_weight(len(s1), len(s3), max_sub13)
    
        # 更新距离
        print("更新后s1和s2距离:" + str(distance12 * weight12))
        print("更新后s1和s3距离:" + str(distance13 * weight13))
    

    输出:

    更新前s1和s2距离:2.0223748416156684
    更新前s1和s3距离:1.794435844492636
    更新后s1和s2距离:0.47399410350367227
    更新后s1和s3距离:1.6822836042118463
    

    结论:
    用新的算法更新后,我们会发现s1和s2距离比s1和s3的距离更加接近了,这就是我们要的结果。

    5. 参考

    1. https://github.com/wannesm/dtaidistance
    2. 两个字符串的最长子串
    3. 两个字符串的最长子序列
    展开全文
  • 图像相似性度量

    千次阅读 2016-02-29 18:02:22
    图像相似性度量 【转载】原文出处:http://blog.sina.com.cn/s/blog_4a540be60100vjae.html   图像相似度计算主要用于对于两幅图像之间内容的相似程度进行打分,根据分数的高低来判断图像内容的相近程度。  ...
    
    分类:

    图像相似性度量

    【转载】原文出处:http://blog.sina.com.cn/s/blog_4a540be60100vjae.html

     

    图像相似度计算主要用于对于两幅图像之间内容的相似程度进行打分,根据分数的高低来判断图像内容的相近程度。

       可以用于计算机视觉中的检测跟踪中目标位置的获取,根据已有模板在图像中找到一个与之最接近的区域。然后一直跟着。已有的一些算法比如BlobTracking,Meanshift,Camshift,粒子滤波等等也都是需要这方面的理论去支撑。

      还有一方面就是基于图像内容的图像检索,也就是通常说的以图检图。比如给你某一个人在海量的图像数据库中罗列出与之最匹配的一些图像,当然这项技术可能也会这样做,将图像抽象为几个特征值,比如Trace变换,图像哈希或者Sift特征向量等等,来根据数据库中存得这些特征匹配再返回相应的图像来提高效率。

      下面就一些自己看到过的算法进行一些算法原理和效果上的介绍。

       (1)直方图匹配。

          比如有图像A和图像B,分别计算两幅图像的直方图,HistA,HistB,然后计算两个直方图的归一化相关系数(巴氏距离,直方图相交距离)等等。

          这种思想是基于简单的数学上的向量之间的差异来进行图像相似程度的度量,这种方法是目前用的比较多的一种方法,第一,直方图能够很好的归一化,比如通常的256个bin条的。那么两幅分辨率不同的图像可以直接通过计算直方图来计算相似度很方便。而且计算量比较小。

          这种方法的缺点:

             1、直方图反映的是图像像素灰度值的概率分布,比如灰度值为200的像素有多少个,但是对于这些像素原来的位置在直方图中并没有体现,所以图像的骨架,也就是图像内部到底存在什么样的物体,形状是什么,每一块的灰度分布式什么样的这些在直方图信息中是被省略掉得。那么造成的一个问题就是,比如一个上黑下白的图像和上白下黑的图像其直方图分布是一模一样的,其相似度为100%。

             2、两幅图像之间的距离度量,采用的是巴氏距离或者归一化相关系数,这种用分析数学向量的方法去分析图像本身就是一个很不好的办法。

             3、就信息量的道理来说,采用一个数值来判断两幅图像的相似程度本身就是一个信息压缩的过程,那么两个256个元素的向量(假定直方图有256个bin条)的距离用一个数值表示那么肯定就会存在不准确性。

       下面是一个基于直方图距离的图像相似度计算的Matlab Demo和实验结果.

    %计算图像直方图距离
    %巴氏系数计算法

    M=imread('1.jpg');
    N=imread('2.jpg');
    I=rgb2gray(M);
    J=rgb2gray(N);

    [Count1,x]=imhist(I);
    [Count2,x]=imhist(J);
    Sum1=sum(Count1);Sum2=sum(Count2);
    Sumup = sqrt(Count1.*Count2);
    SumDown = sqrt(Sum1*Sum2);
    Sumup = sum(Sumup);
    figure(1);
    subplot(2,2,1);imshow(I);
    subplot(2,2,2);imshow(J);
    subplot(2,2,3);imhist(I);
    subplot(2,2,4);imhist(J);
    HistDist=1-sqrt(1-Sumup/SumDown)

     

    图像相似度计算

       通过上图可以看到这种计算图像相似度的方法确实存在很大的弊端。然而很多人也对于这种方法进行了修改,比如FragTrack算法,具体可以参见这篇论文《》。其中对图像分成横纵的小块,然后对于每一个分块搜索与之最匹配的直方图。来计算两幅图像的相似度,融入了直方图对应位置的信息。但是计算效率上很慢。

      还有一种是计算一个图像外包多边形,一般得到跟踪图像的前景图后计算其外包多边形,根据外包多边形做Delauny三角形分解,然后计算每个三角形内部的直方图,对于这两个直方图组进行相似距离计算。这样就融入了直方图的位置信息。

     (2)数学上的矩阵分解

       图像本身就是一个矩阵,可以依靠数学上矩阵分解的一些知识来获取矩阵中一些代表这个矩阵元素值和分布的一些鲁棒性特征来对图像的相似度进行计算。

        最常用的一般是SVD分解和NMF分解。

       下面简单介绍下SVD分解的一些性质,如果需要探究的更深入一点网上有一些相关文献,读者可以去探究的更清楚:

     <1> 奇异值的稳定性

     <2> 奇异值的比例不变性

     <3> 奇异值的旋转不变性

     <4> 奇异值的压缩性        

        综上所述,可以看出奇异值分解是基于整体的表示。图像奇异值特征向量不但具有正交变换、旋转、位移、镜像映射等代数和几何上的不变性,而且具有良好的稳定性和抗噪性,广泛应用于模式识别与图像分析中。对图像进行奇异值分解的目的是:得到唯一、稳定的特征描述;降低特征空间的维数;提高抵抗干扰和噪声的能力。但是由于奇异值分解得到的奇异矢量中有负数存在所以不能很好的解释其物理意义。

      非负矩阵分解(NMF):

        NMF的主要思想是将非负矩阵分解为可以体现图像主要信息的基矩阵与系数矩阵,并且可以对基矩阵赋予很好的解释,比如对人脸的分割,得到的基向量正是人的“眼睛”,“鼻子”等主要概念特征,源图像表示为这些特征的加权组合。所以NMF算法也在人脸识别等场合中发挥着巨大的作用。

       下面一个实验说明了SVD+NMF数学上的这些分解在图像相似度判定方面的应用,这个跟我目前的课题有关细节方面就不再透露更多了。

    图像相似度计算

    图像相似度计算

    图像相似度计算

    当然基于数学上的矩阵特征值计算的还有很多方法比如Trace变换,不变矩计算等等,当然如果有需要这方面资料的同学可以找我,我可以进行相关的帮助。
    (3)基于特征点的图像相似度计算

        每一幅图像都有自己的特征点,这些特征点表征图像中比较重要的一些位置,比较类似函数的拐点那种,通常比较常用的有Harris角点和Sift特征点。那么将得到的图像角点进行比较,如果相似的角点数目较多,那么可以认为这两幅图像的相似程度较高。这里主要介绍基于Sift算子。

       对于Sift的原理和代码可以参见David Lower的网站。

    David G Lowe Sift网站

       那么我们就可以通过找到匹配点的个数来判断两幅图像是否一致,这个算法的好处是对于一个物体,两个不同角度下得到的照片依然可以找到很多的匹配点,我也一直认为是一个综合来说结果相对较为准确的方法,但是由于每个特征点需要计算一个长度不小的特征值,也造成了该算法的时间消耗比较大。所以不常用于实时的视频处理。这个算法还有一个好处就是可以通过找到的匹配特征点进行图像校正。关于使用Sift做图像校正请参见我的另外一篇博文。

      图像相似度计算

    图像相似度计算

    我当时对于比如左边图像,找到50个特征点,如果其中有60%以上的与右边的匹配上了,认为两幅图像是相似图像。

    图像相似度计算

    上图使用Sift找到的匹配对应点,然后通过仿射变换的6维参数计算,然后逆变换得到校正后的图像,效果蛮不错的,可见Sift对于抗旋转和噪声的效果确实很好。

    对于Sift也不能全部相信,一般使用RANSAC对于错误匹配点去除可以达到更好的效果,当然目前也有很多对SIFT进行改进的算法。希望有这方面研究的可以多多交流。

     

    展开全文
  • 用户相似性度量

    千次阅读 2014-12-24 15:48:26
    场景:用于度量两个用户之间的相似性度量两个用户针对同一物品的偏好值变化趋势的一致性。 优点:结果直观。 缺点:没有考虑到两个用户同时给出偏好值的数目。解决办法:引入权重,即加权。  例如,两个用户如
  • 常用相似性度量(距离 相似系数)

    千次阅读 2018-05-22 10:32:03
    在分类聚类算法,推荐系统中,常要用到两个输入变量(通常是特征向量的形式)距离的计算,即相似性度量.不同相似性度量对于算法的结果,有些时候,差异很大.因此,有必要根据输入数据的特征,选择一种合适的相似性度量方法.令...
  • 相似性度量——机器学习

    千次阅读 2018-03-24 11:32:50
    相似性度量:给定数值的对象就可以看作一个n 维坐标系下的点,并通过点与点之间的距离来度量。例如:向量v1 = (01, 小明, 男, 175, 北京大学, 软件与微电子学院,软件工程)向量v2 = (02, 小红, 女, 165,...
  • 大家好,今天我给大家介绍一下什么是相似性度量,其中会重点介绍对象之间的相似性度量,有兴趣的朋友可以好好看一看。相似性度量是衡量变量之间互相关系的强弱、联系紧密程度的重要手段,因此相似性度经常被许多数据...
  • zipf定律与相似性度量

    千次阅读 2018-03-02 19:17:13
    zipf定律与相似性度量 Zipf定律指出,在文本中,标识符出现的频率与其在排序列表中的排名或位置成反比。这个定律描述了标识符在文本中是如何分布的,即一些标志符出现的频次很大,另一些出现的频次较低,还有一些...
  • 哈希+汉明距离进行相似性度量

    千次阅读 2020-01-16 17:07:43
    哈希+汉明距离进行相似性度量 哈希算法 aHash 定义 aHash 基于低频的均值哈希 :过于严格 更适合搜索缩略图 算法步骤 缩小图片尺寸 将其化为灰度图 计算灰度均值 根据与灰度均值的对比得到二值图 将二值图按序...
  • 距离和相似性度量机器学习中的相似性度量 马氏距离的几张截图 漫谈机器学习中距离和相似性度量方法 距离度量分类体系 本篇文章并不打算描述所有这些类别,要具体阐述它们...
  • 机器学习中的相似性度量

    千次阅读 2013-11-08 16:44:04
    在做分类时常常需要估算不同样本之间的相似性度量(Similarity Measurement),这时通常采用的方法就是计算样本间的“距离”(Distance)。采用什么样的方法计算距离是很讲究,甚至关系到分类的正确与否。 本文的目的...
  • 图像相似性度量方法

    千次阅读 2017-02-12 13:03:30
    图像相似度计算主要用于对于两幅图像之间内容的相似程度进行打分,根据分数的高低来判断图像内容的相近程度。    可以用于计算机视觉中的检测跟踪中目标位置的获取,根据已有模板在图像中找到一个与之最接近的...
  • 距离计算与相似性度量方法

    千次阅读 2018-10-17 09:51:46
    在机器学习和数据挖掘中,我们经常需要知道个体间差异的大小,进而评价个体的相似性和类别。最常见的是数据分析中的相关分析,数据挖掘中的分类和聚类算法,如 K 最近邻(KNN)和K均值(K-Means)等。根据数据特性的...
  • 图像相似度量Matlab代码

    热门讨论 2010-09-05 16:48:34
    图像相似度量Matlab代码, 采用了两种方式.
  • 在机器学习和数据挖掘中,我们经常需要知道个体间差异的大小,进而评价个体的相似性和类别。最常见的是数据分析中的相关分析,数据挖掘中的分类和聚类算法,如 K 最近邻(KNN)和 K 均值(K-Means)等等。根据数据...
  • 机器学习中距离和相似性度量方法

    千次阅读 2019-08-24 14:46:38
    在机器学习和数据挖掘中,我们经常需要知道个体间差异的大小,进而评价个体的相似性和类别。最常见的是数据分析中的相关分析,数据挖掘中的分类和聚类算法,如 K 最近邻(KNN)和 K 均值(K-Means)等等。根据数据...
  • 在数据挖掘分类算法中,常常提到根据数据表项的相似性进行分类,那么主要用到的相似性度量有哪些呢?这里总结一下最常用的两个:(1)欧几里德距离评价(2)皮尔逊相关评价:  (1)欧几里德距离评价  该系数...
  • 在机器学习和数据挖掘中,我们经常需要知道个体间差异的大小,进而评价个体的相似性和类别。根据数据特性的不同,可以采用不同的度量方法。 以下简要介绍机器学习和数据挖掘中一些常见的距离公式,包括: 欧氏距离...
  • 在机器学习以及很多应用场景里面各种相似性、分类相关的距离数学公式的原理
  • 在机器学习和数据挖掘中,我们经常需要知道个体间差异的大小,进而评价个体的相似性和类别。最常见的是数据分析中的相关分析,数据挖掘中的分类和聚类算法,如 K 最近邻(KNN)和 K 均值(K-Means)等等。根据数据...
  • 归一化互信息是度量两张图片相似度的一种表达方式,它的值越大代表两张图片的相似性越高。通常用来作为图像配准中的评判准则或是目标函数。它在两幅图像的灰度级数相似的情况下有良好的配准精度,较高的可靠性;但是...
  • 机器学习之距离和相似性度量方法

    千次阅读 2016-01-10 13:57:20
    在机器学习和数据挖掘中,我们经常需要知道个体间差异的大小,进而评价个体的相似性和类别。最常见的是数据分析中的相关分析,数据挖掘中的分类和聚类算法,如 K 最近邻(KNN)和 K 均值(K-Means)等等。根据数据...
  • ML之SSIM:基于输入图片RGB的三维向量利用SSIM(结构相似性度量)算法进行判别 目录 输出结果 代码实现 相关文章ML之相似度计算:图像数据、字符串数据等计算相似度常用的十种方法简介、代码实现ML之Hash_Edit...
  • difflib(Python自带):不一定为字符串,数组也可以匹配,但数组匹配时只有单个元素完全匹配才计入相似。 Levenshtein(第三方插件):需要输入为字符串,匹配时是整体匹配,数组匹配时需要用join把数组元素连接为...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 24,569
精华内容 9,827
关键字:

代码相似性度量