Source Code for Module pyvision.other.distance

  1  # PyVision License 
  2  # 
  3  # Copyright (c) 2006-2008 David S. Bolme 
  4  # All rights reserved. 
  5  # 
  6  # Redistribution and use in source and binary forms, with or without 
  7  # modification, are permitted provided that the following conditions 
  8  # are met: 
  9  #  
 10  # 1. Redistributions of source code must retain the above copyright 
 11  # notice, this list of conditions and the following disclaimer. 
 12  #  
 13  # 2. Redistributions in binary form must reproduce the above copyright 
 14  # notice, this list of conditions and the following disclaimer in the 
 15  # documentation and/or other materials provided with the distribution. 
 16  #  
 17  # 3. Neither name of copyright holders nor the names of its contributors 
 18  # may be used to endorse or promote products derived from this software 
 19  # without specific prior written permission. 
 20  #  
 21  #  
 22  # THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
 23  # ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
 24  # LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 
 25  # A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR 
 26  # CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 
 27  # EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 
 28  # PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 
 29  # PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 
 30  # LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 
 31  # NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 
 32  # SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 33   
 34   
 35  from math import sqrt 
 36  import numpy as np 
 37   
 38   
 39  # Create a table that can look up the hamming distance for each byte 
 40  hamming_table = np.zeros(256,dtype=np.int32) 
 41  for i in range(256): 
 42      bits = (i&1>0) + (i&2>0) + (i&4>0) + (i&8>0) + (i&16>0) + (i&32>0) + (i&64>0) + (i&128>0) 
 43      hamming_table[i] = bits   
 44       
 45   
 46 -def boolToUbyte(x): 
 47      "Convert a boolean vector to a ubyte vector which is much more space efficient." 
 48      assert isinstance(x,np.ndarray) 
 49      assert x.dtype in [np.bool] 
 50      assert len(x.shape) == 1 
 51      assert x.shape[0] % 8 == 0 
 52       
 53      out =   1*x[7::8] + \ 
 54              2*x[6::8] + \ 
 55              4*x[5::8] + \ 
 56              8*x[4::8] + \ 
 57             16*x[3::8] + \ 
 58             32*x[2::8] + \ 
 59             64*x[1::8] + \ 
 60            128*x[0::8] 
 61       
 62      out = out.astype(np.ubyte) 
 63      return out 
 64   
 65   
 66 -def ubyteToBool(x): 
 67      "Convert a byte vector to a bool vector." 
 68      assert isinstance(x,np.ndarray) 
 69      assert x.dtype in [np.ubyte] 
 70      assert len(x.shape) == 1 
 71       
 72      out = np.zeros(x.shape[0]*8,dtype=np.bool) 
 73       
 74      out[7::8] = 1&x > 0 
 75      out[6::8] = 2&x > 0 
 76      out[5::8] = 4&x > 0 
 77      out[4::8] = 8&x > 0 
 78      out[3::8] = 16&x > 0 
 79      out[2::8] = 32&x > 0 
 80      out[1::8] = 64&x > 0 
 81      out[0::8] = 128&x > 0 
 82       
 83      return out 
 84             
 85       
 86 -def hamming(a,b): 
 87      if a.dtype == np.bool and b.dtype == bool: 
 88          return (a ^ b).sum() 
 89      elif a.dtype == np.ubyte and b.dtype == np.ubyte: 
 90          return hamming_table[a^b].sum() 
 91      else: 
 92          raise NotImplementedError("Unsupported array types %s and %s",a.dtype,b.dtype) 
 93   
 94   
 95 -def l1(a,b): 
 96      ''' Compute the l1 distance measure ''' 
 97      return abs(a - b).sum() 
 98   
 99   
100 -def l2(a,b): 
101      ''' compute the l2 distance ''' 
102      d = (a - b) 
103      return sqrt( (d*d).sum() ) 
104   
105       
106 -def correlation(a,b): 
107      ''' Compute the correlation of two vectors ''' 
108      #mean subtract 
109      a = a - a.mean() 
110      b = b - b.mean() 
111   
112      #unit length - avoid dev by zero 
113      a = (1.0/sqrt((a*a).sum()+0.000001))*a 
114      b = (1.0/sqrt((b*b).sum()+0.000001))*b 
115                   
116      # correlation 
117      c = (a*b).sum() 
118       
119      return c 
120