Python Archives - Robotics with ROS

SSH connection to Google Colaboratory and Transfering files from Google Drive

Leave a Comment / Python, Tutorials / admin

Do like to access the Google Colaboratory directly from your machine? Running your script via terminal and having shell access? Then there is a good news, just do the followings: SSH to Google Colaboratory 1. Install colab_ssh on Google Colaboratory

!pip install colab_ssh --upgrade

1	!pip install colab_ssh --upgrade

Add cloudflared and password for root user:

from colab_ssh import launch_ssh_cloudflared, init_git_cloudflared
launch_ssh_cloudflared(password="<PUT_YOUR_PASSWORD_HERE>")

1 2	from colab_ssh import launch_ssh_cloudflared, init_git_cloudflared launch_ssh_cloudflared(password="<PUT_YOUR_PASSWORD_HERE>")

2. Install cloudflared on your machine […]

SSH connection to Google Colaboratory and Transfering files from Google Drive Read More »

Metrics for Evaluating Machine Learning Models – Classification

Leave a Comment / Machine Learning, Python, Tutorials / admin

Confusion Matrix Let’s say we have a binary classifier cats and non- cats, we have 1100 test images, 1000 non cats, 100 cats. The output of the classifier is either Positive which means “cat” or Negative which means non-cat. The following is called confusion matrix: How to interpret these term is as follows: Correctness of

Metrics for Evaluating Machine Learning Models – Classification Read More »

Extended Kalman Filter Explained with Python Code

12 Comments / Machine Learning, Python, Robotic, Tutorials / admin

In the following code, I have implemented an Extended Kalman Filter for modeling the movement of a car with constant turn rate and velocity. The code is mainly based on this work (I did some bug fixing and some adaptation such that the code runs similar to the Kalman filter that I have earlier implemented).

import matplotlib.dates as mdates
import numpy as np
np.set_printoptions(threshold=3)
np.set_printoptions(suppress=True)

from numpy import genfromtxt
import matplotlib.pyplot as plt
from scipy.stats import norm
from sympy import Symbol, symbols, Matrix, sin, cos
from sympy import init_printing
from sympy.utilities.codegen import codegen
init_printing(use_latex=True)

x0 = []
x1 = []
x2 = []

def prediction(X_hat_t_1,P_t_1,Q_t,drivingStraight):
    X_hat_t=X_hat_t_1

    if drivingStraight: # Driving straight
        X_hat_t[0] = X_hat_t_1[0] + X_hat_t_1[3]*dt * np.cos(X_hat_t_1[2])
        X_hat_t[1] = X_hat_t_1[1] + X_hat_t_1[3]*dt * np.sin(X_hat_t_1[2])
        X_hat_t[2] = X_hat_t_1[2]
        X_hat_t[3] = X_hat_t_1[3] + X_hat_t_1[5]*dt
        X_hat_t[4] = 0.0000001 # avoid numerical issues in Jacobians
        X_hat_t[5] = X_hat_t_1[5]
       
    else: # otherwise
        X_hat_t[0] = X_hat_t_1[0] + (X_hat_t_1[3]/X_hat_t_1[4]) * (np.sin(X_hat_t_1[4]*dt+X_hat_t_1[2]) - np.sin(X_hat_t_1[2]))
        X_hat_t[1] = X_hat_t_1[1] + (X_hat_t_1[3]/X_hat_t_1[4]) * (-np.cos(X_hat_t_1[4]*dt+X_hat_t_1[2])+ np.cos(X_hat_t_1[2]))
        X_hat_t[2] = (X_hat_t_1[2] + X_hat_t_1[4]*dt + np.pi) % (2.0*np.pi) - np.pi
        X_hat_t[3] = X_hat_t_1[3] + X_hat_t_1[5]*dt
        X_hat_t[4] = X_hat_t_1[4] # Constant Turn Rate
        X_hat_t[5] = X_hat_t_1[5] # Constant Acceleration
        
    
    # Calculate the Jacobian of the Dynamic Matrix A
    # see "Calculate the Jacobian of the Dynamic Matrix with respect to the state vector"
    a13 = float((X_hat_t[3]/X_hat_t[4]) * (np.cos(X_hat_t[4]*dt+X_hat_t[2]) - np.cos(X_hat_t[2])))
    a14 = float((1.0/X_hat_t[4]) * (np.sin(X_hat_t[4]*dt+X_hat_t[2]) - np.sin(X_hat_t[2])))
    a15 = float((dt*X_hat_t[3]/X_hat_t[4])*np.cos(X_hat_t[4]*dt+X_hat_t[2]) - (X_hat_t[3]/X_hat_t[4]**2)*(np.sin(X_hat_t[4]*dt+X_hat_t[2]) - np.sin(X_hat_t[2])))
    a23 = float((X_hat_t[3]/X_hat_t[4]) * (np.sin(X_hat_t[4]*dt+X_hat_t[2]) - np.sin(X_hat_t[2])))
    a24 = float((1.0/X_hat_t[4]) * (-np.cos(X_hat_t[4]*dt+X_hat_t[2]) + np.cos(X_hat_t[2])))
    a25 = float((dt*X_hat_t[3]/X_hat_t[4])*np.sin(X_hat_t[4]*dt+X_hat_t[2]) - (X_hat_t[3]/X_hat_t[4]**2)*(-np.cos(X_hat_t[4]*dt+X_hat_t[2]) + np.cos(X_hat_t[2])))
    JA = np.matrix([[1.0, 0.0, a13, a14, a15, 0.0],
                    [0.0, 1.0, a23, a24, a25, 0.0],
                    [0.0, 0.0, 1.0, 0.0, dt, 0.0],
                    [0.0, 0.0, 0.0, 1.0, 0.0, dt],
                    [0.0, 0.0, 0.0, 0.0, 1.0, 0.0],
                    [0.0, 0.0, 0.0, 0.0, 0.0, 1.0]])
    
    
    # Project the error covariance ahead
    P_t_1 = JA*P_t_1*JA.T + Q_t
    return X_hat_t,P_t_1

def update(X_hat_t,P_t,Z_t,R_t,GPSAvailable):
    hx = np.matrix([[float(X_hat_t[0])],
                    [float(X_hat_t[1])],
                    [float(X_hat_t[3])],
                    [float(X_hat_t[4])],
                    [float(X_hat_t[5])]])

    if GPSAvailable: # with 10Hz, every 5th step
        JH = np.matrix([[1.0, 0.0, 0.0, 0.0, 0.0, 0.0],
                        [0.0, 1.0, 0.0, 0.0, 0.0, 0.0],
                        [0.0, 0.0, 0.0, 1.0, 0.0, 0.0],
                        [0.0, 0.0, 0.0, 0.0, 1.0, 0.0],
                        [0.0, 0.0, 0.0, 0.0, 0.0, 1.0]])
    else: # every other step
        JH = np.matrix([[0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
                        [0.0, 0.0, 0.0, 0.0, 0.0, 0.0],
                        [0.0, 0.0, 0.0, 1.0, 0.0, 0.0],
                        [0.0, 0.0, 0.0, 0.0, 1.0, 0.0],
                        [0.0, 0.0, 0.0, 0.0, 0.0, 1.0]])        
    
    S = JH*P_t*JH.T + R_t
    K = (P_t*JH.T) * np.linalg.inv(S)
    #print("K:\n",K)
    # Update the estimate via
    Z = Z_t.reshape(JH.shape[0],1)
    #print("Z:\n",Z)
    y = Z - (hx)                         # Innovation or Residual
    X_t = X_hat_t + (K*y)

    # Update the error covariance
    
    
    I = np.eye(X_hat_t.shape[0])
    P_t = (I - (K*JH))*P_t


    x0.append(float(X_t[0]))
    x1.append(float(X_t[1]))
    x2.append(float(X_t[2]))
    return X_t,P_t

numstates=6 # States

dt = 1.0/50.0 # Sample Rate of the Measurements is 50Hz
dtGPS=1.0/10.0 # Sample Rate of GPS is 10Hz

vs, psis, dpsis, dts, xs, ys, lats, lons, axs = symbols('v \psi \dot\psi T x y lat lon a')

gs = Matrix([[xs+(vs/dpsis)*(sin(psis+dpsis*dts)-sin(psis))],
             [ys+(vs/dpsis)*(-cos(psis+dpsis*dts)+cos(psis))],
             [psis+dpsis*dts],
             [axs*dts + vs],
             [dpsis],
             [axs]])
state = Matrix([xs,ys,psis,vs,dpsis,axs])


#Initial State cov
P_t = np.diag([1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0])

#Measurment cov

varGPS = 5.0 # Standard Deviation of GPS Measurement
varspeed = 3.0 # Variance of the speed measurement
varyaw = 0.1 # Variance of the yawrate measurement
varacc = 1.0 # Variance of the longitudinal Acceleration
R_t = np.diag([varGPS**2, varGPS**2, varspeed**2, varyaw**2, varacc**2])


#Measurment Matrix
hs = Matrix([[xs],
             [ys],
             [vs],
             [dpsis],
             [axs]])

#Process cov
sGPS     = 0.5*8.8*dt**2  # assume 8.8m/s2 as maximum acceleration, forcing the vehicle
sCourse  = 0.1*dt # assume 0.1rad/s as maximum turn rate for the vehicle
sVelocity= 8.8*dt # assume 8.8m/s2 as maximum acceleration, forcing the vehicle
sYaw     = 1.0*dt # assume 1.0rad/s2 as the maximum turn rate acceleration for the vehicle
sAccel   = 0.5

Q_t = np.diag([sGPS**2, sGPS**2, sCourse**2, sVelocity**2, sYaw**2, sAccel**2])

path="data/"
datafile = '2014-03-26-000-Data.csv'

fullPath=path+datafile

def bytespdate2num(fmt, encoding='utf-8'):
    strconverter = mdates.strpdate2num(fmt)
    def bytesconverter(b):
        s = b.decode(encoding)
        return strconverter(s)
    return bytesconverter


date, time, millis, ax, ay, az, rollrate, pitchrate, yawrate, roll, pitch, yaw, speed, course, latitude, longitude, altitude, pdop, hdop, vdop, epe, fix, satellites_view, satellites_used, temp = np.loadtxt(fullPath, delimiter=',', unpack=True, 
                  converters={1:bytespdate2num('%H%M%S%f'),
                              0: bytespdate2num('%y%m%d')},
                  skiprows=1)


# A course of 0 means the Car is traveling north bound
# and 90 means it is traveling east bound.
# In the Calculation following, East is Zero and North is 90
# We need an offset.
course =(-course+90.0)

# ## Approx. Lat/Lon to Meters to check Location

# In[17]:

RadiusEarth = 6378388.0 # m
arc= 2.0*np.pi*(RadiusEarth+altitude)/360.0 # m/

dx = arc * np.cos(latitude*np.pi/180.0) * np.hstack((0.0, np.diff(longitude))) # in m
dy = arc * np.hstack((0.0, np.diff(latitude))) # in m

mx = np.cumsum(dx)
my = np.cumsum(dy)

ds = np.sqrt(dx**2+dy**2)

GPS=(ds!=0.0).astype('bool') # GPS Trigger for Kalman Filter

# ## Initial State
X_hat_t = np.matrix([[mx[0], my[0], course[0]/180.0*np.pi, speed[0]/3.6+0.001, yawrate[0]/180.0*np.pi, ax[0]]]).T

measurements = np.vstack((mx, my, speed/3.6, yawrate/180.0*np.pi, ax))
# Lenth of the measurement
m = measurements.shape[1]

for i in range(measurements.shape[1]):
#for i in range(3):
    
    if  np.abs(yawrate[i])<0.0001:
        drivingStraight=True
    else:
        drivingStraight=False
    
    
    X_hat_t,P_hat_t = prediction(X_hat_t,P_t,Q_t,drivingStraight)
    #print("Prediction:")
    #print("X_hat_t:\n",X_hat_t,"\nP_t:\n",P_hat_t)
   
    Z_t=measurements[:,i]
    if GPS[i]:
        GPSAvailable=True
    else:
        GPSAvailable=False
    
    X_t,P_t=update(X_hat_t,P_hat_t,Z_t,R_t,GPSAvailable)
    #print("Update:")
    #print("X_t:\n",X_t,"\nP_t:\n",P_t)
    X_hat_t=X_t
    P_hat_t=P_t
    
fig = plt.figure(figsize=(16,9))

# EKF State
plt.quiver(x0,x1,np.cos(x2), np.sin(x2), color='#94C600', units='xy', width=0.05, scale=0.5)
plt.plot(x0,x1, label='EKF Position', c='k', lw=5)

# Measurements
plt.scatter(mx[::5],my[::5], s=50, label='GPS Measurements', marker='+')

# Start/Goal
plt.scatter(x0[0],x1[0], s=60, label='Start', c='g')
plt.scatter(x0[-1],x1[-1], s=60, label='Goal', c='r')

plt.xlabel('X [m]')
plt.ylabel('Y [m]')
plt.title('Position')
plt.legend(loc='best')
plt.axis('equal')
plt.show()

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

import matplotlib.dates as mdates

import numpy as np

np.set_printoptions(threshold=3)

np.set_printoptions(suppress=True)

from numpy import genfromtxt

import matplotlib.pyplot as plt

from scipy.stats import norm

from sympy import Symbol, symbols, Matrix, sin, cos

from sympy import init_printing

from sympy.utilities.codegen import codegen

init_printing(use_latex=True)

x0 = []

x1 = []

x2 = []

def prediction(X_hat_t_1,P_t_1,Q_t,drivingStraight):

X_hat_t=X_hat_t_1

if drivingStraight: # Driving straight

X_hat_t[0] = X_hat_t_1[0] + X_hat_t_1[3]*dt * np.cos(X_hat_t_1[2])

X_hat_t[1] = X_hat_t_1[1] + X_hat_t_1[3]*dt * np.sin(X_hat_t_1[2])

X_hat_t[2] = X_hat_t_1[2]

X_hat_t[3] = X_hat_t_1[3] + X_hat_t_1[5]*dt

X_hat_t[4] = 0.0000001 # avoid numerical issues in Jacobians

X_hat_t[5] = X_hat_t_1[5]

else: # otherwise

X_hat_t[0] = X_hat_t_1[0] + (X_hat_t_1[3]/X_hat_t_1[4]) * (np.sin(X_hat_t_1[4]*dt+X_hat_t_1[2]) - np.sin(X_hat_t_1[2]))

X_hat_t[1] = X_hat_t_1[1] + (X_hat_t_1[3]/X_hat_t_1[4]) * (-np.cos(X_hat_t_1[4]*dt+X_hat_t_1[2])+ np.cos(X_hat_t_1[2]))

X_hat_t[2] = (X_hat_t_1[2] + X_hat_t_1[4]*dt + np.pi) % (2.0*np.pi) - np.pi

X_hat_t[3] = X_hat_t_1[3] + X_hat_t_1[5]*dt

X_hat_t[4] = X_hat_t_1[4] # Constant Turn Rate

X_hat_t[5] = X_hat_t_1[5] # Constant Acceleration

# Calculate the Jacobian of the Dynamic Matrix A

# see "Calculate the Jacobian of the Dynamic Matrix with respect to the state vector"

a13 = float((X_hat_t[3]/X_hat_t[4]) * (np.cos(X_hat_t[4]*dt+X_hat_t[2]) - np.cos(X_hat_t[2])))

a14 = float((1.0/X_hat_t[4]) * (np.sin(X_hat_t[4]*dt+X_hat_t[2]) - np.sin(X_hat_t[2])))

a15 = float((dt*X_hat_t[3]/X_hat_t[4])*np.cos(X_hat_t[4]*dt+X_hat_t[2]) - (X_hat_t[3]/X_hat_t[4]**2)*(np.sin(X_hat_t[4]*dt+X_hat_t[2]) - np.sin(X_hat_t[2])))

a23 = float((X_hat_t[3]/X_hat_t[4]) * (np.sin(X_hat_t[4]*dt+X_hat_t[2]) - np.sin(X_hat_t[2])))

a24 = float((1.0/X_hat_t[4]) * (-np.cos(X_hat_t[4]*dt+X_hat_t[2]) + np.cos(X_hat_t[2])))

a25 = float((dt*X_hat_t[3]/X_hat_t[4])*np.sin(X_hat_t[4]*dt+X_hat_t[2]) - (X_hat_t[3]/X_hat_t[4]**2)*(-np.cos(X_hat_t[4]*dt+X_hat_t[2]) + np.cos(X_hat_t[2])))

JA = np.matrix([[1.0, 0.0, a13, a14, a15, 0.0],

[0.0, 1.0, a23, a24, a25, 0.0],

[0.0, 0.0, 1.0, 0.0, dt, 0.0],

[0.0, 0.0, 0.0, 1.0, 0.0, dt],

[0.0, 0.0, 0.0, 0.0, 1.0, 0.0],

[0.0, 0.0, 0.0, 0.0, 0.0, 1.0]])

# Project the error covariance ahead

P_t_1 = JA*P_t_1*JA.T + Q_t

return X_hat_t,P_t_1

def update(X_hat_t,P_t,Z_t,R_t,GPSAvailable):

hx = np.matrix([[float(X_hat_t[0])],

[float(X_hat_t[1])],

[float(X_hat_t[3])],

[float(X_hat_t[4])],

[float(X_hat_t[5])]])

if GPSAvailable: # with 10Hz, every 5th step

JH = np.matrix([[1.0, 0.0, 0.0, 0.0, 0.0, 0.0],

[0.0, 1.0, 0.0, 0.0, 0.0, 0.0],

[0.0, 0.0, 0.0, 1.0, 0.0, 0.0],

[0.0, 0.0, 0.0, 0.0, 1.0, 0.0],

[0.0, 0.0, 0.0, 0.0, 0.0, 1.0]])

else: # every other step

JH = np.matrix([[0.0, 0.0, 0.0, 0.0, 0.0, 0.0],

[0.0, 0.0, 0.0, 0.0, 0.0, 0.0],

[0.0, 0.0, 0.0, 1.0, 0.0, 0.0],

[0.0, 0.0, 0.0, 0.0, 1.0, 0.0],

[0.0, 0.0, 0.0, 0.0, 0.0, 1.0]])

S = JH*P_t*JH.T + R_t

K = (P_t*JH.T) * np.linalg.inv(S)

#print("K:\n",K)

# Update the estimate via

Z = Z_t.reshape(JH.shape[0],1)

#print("Z:\n",Z)

y = Z - (hx) # Innovation or Residual

X_t = X_hat_t + (K*y)

# Update the error covariance

I = np.eye(X_hat_t.shape[0])

P_t = (I - (K*JH))*P_t

x0.append(float(X_t[0]))

x1.append(float(X_t[1]))

x2.append(float(X_t[2]))

return X_t,P_t

numstates=6 # States

dt = 1.0/50.0 # Sample Rate of the Measurements is 50Hz

dtGPS=1.0/10.0 # Sample Rate of GPS is 10Hz

vs, psis, dpsis, dts, xs, ys, lats, lons, axs = symbols('v \psi \dot\psi T x y lat lon a')

gs = Matrix([[xs+(vs/dpsis)*(sin(psis+dpsis*dts)-sin(psis))],

[ys+(vs/dpsis)*(-cos(psis+dpsis*dts)+cos(psis))],

[psis+dpsis*dts],

[axs*dts + vs],

[dpsis],

[axs]])

state = Matrix([xs,ys,psis,vs,dpsis,axs])

#Initial State cov

P_t = np.diag([1000.0, 1000.0, 1000.0, 1000.0, 1000.0, 1000.0])

#Measurment cov

varGPS = 5.0 # Standard Deviation of GPS Measurement

varspeed = 3.0 # Variance of the speed measurement

varyaw = 0.1 # Variance of the yawrate measurement

varacc = 1.0 # Variance of the longitudinal Acceleration

R_t = np.diag([varGPS**2, varGPS**2, varspeed**2, varyaw**2, varacc**2])

#Measurment Matrix

hs = Matrix([[xs],

[ys],

[vs],

[dpsis],

[axs]])

#Process cov

sGPS = 0.5*8.8*dt**2 # assume 8.8m/s2 as maximum acceleration, forcing the vehicle

sCourse = 0.1*dt # assume 0.1rad/s as maximum turn rate for the vehicle

sVelocity= 8.8*dt # assume 8.8m/s2 as maximum acceleration, forcing the vehicle

sYaw = 1.0*dt # assume 1.0rad/s2 as the maximum turn rate acceleration for the vehicle

sAccel = 0.5

Q_t = np.diag([sGPS**2, sGPS**2, sCourse**2, sVelocity**2, sYaw**2, sAccel**2])

path="data/"

datafile = '2014-03-26-000-Data.csv'

fullPath=path+datafile

def bytespdate2num(fmt, encoding='utf-8'):

strconverter = mdates.strpdate2num(fmt)

def bytesconverter(b):

s = b.decode(encoding)

return strconverter(s)

return bytesconverter

date, time, millis, ax, ay, az, rollrate, pitchrate, yawrate, roll, pitch, yaw, speed, course, latitude, longitude, altitude, pdop, hdop, vdop, epe, fix, satellites_view, satellites_used, temp = np.loadtxt(fullPath, delimiter=',', unpack=True,

converters={1:bytespdate2num('%H%M%S%f'),

0: bytespdate2num('%y%m%d')},

skiprows=1)

# A course of 0 means the Car is traveling north bound

# and 90 means it is traveling east bound.

# In the Calculation following, East is Zero and North is 90

# We need an offset.

course =(-course+90.0)

# ## Approx. Lat/Lon to Meters to check Location

# In[17]:

RadiusEarth = 6378388.0 # m

arc= 2.0*np.pi*(RadiusEarth+altitude)/360.0 # m/

dx = arc * np.cos(latitude*np.pi/180.0) * np.hstack((0.0, np.diff(longitude))) # in m

dy = arc * np.hstack((0.0, np.diff(latitude))) # in m

mx = np.cumsum(dx)

my = np.cumsum(dy)

ds = np.sqrt(dx**2+dy**2)

GPS=(ds!=0.0).astype('bool') # GPS Trigger for Kalman Filter

# ## Initial State

X_hat_t = np.matrix([[mx[0], my[0], course[0]/180.0*np.pi, speed[0]/3.6+0.001, yawrate[0]/180.0*np.pi, ax[0]]]).T

measurements = np.vstack((mx, my, speed/3.6, yawrate/180.0*np.pi, ax))

# Lenth of the measurement

m = measurements.shape[1]

for i in range(measurements.shape[1]):

#for i in range(3):

if np.abs(yawrate[i])<0.0001:

drivingStraight=True

else:

drivingStraight=False

X_hat_t,P_hat_t = prediction(X_hat_t,P_t,Q_t,drivingStraight)

#print("Prediction:")

#print("X_hat_t:\n",X_hat_t,"\nP_t:\n",P_hat_t)

Z_t=measurements[:,i]

if GPS[i]:

GPSAvailable=True

else:

GPSAvailable=False

X_t,P_t=update(X_hat_t,P_hat_t,Z_t,R_t,GPSAvailable)

#print("Update:")

#print("X_t:\n",X_t,"\nP_t:\n",P_t)

X_hat_t=X_t

P_hat_t=P_t

fig = plt.figure(figsize=(16,9))

# EKF State

plt.quiver(x0,x1,np.cos(x2), np.sin(x2), color='#94C600', units='xy', width=0.05, scale=0.5)

plt.plot(x0,x1, label='EKF Position', c='k', lw=5)

# Measurements

plt.scatter(mx[::5],my[::5], s=50, label='GPS Measurements', marker='+')

# Start/Goal

plt.scatter(x0[0],x1[0], s=60, label='Start', c='g')

plt.scatter(x0[-1],x1[-1], s=60, label='Goal', c='r')

plt.xlabel('X [m]')

plt.ylabel('Y [m]')

plt.title('Position')

plt.legend(loc='best')

plt.axis('equal')

plt.show()

Extended Kalman Filter Explained with Python Code Read More »

Parcticle Filter Explained With Python Code From Scratch

8 Comments / Machine Learning, Python, Robotic, Tutorials / admin

In the following code I have implemented a localization algorithm based on particle filter. I have used conda to run my code, you can run the following for installation of dependencies:

conda create -n Filters python=3
conda activate Filters
conda install -c menpo opencv3
conda install numpy scipy matplotlib sympy

conda create -n Filters python=3

conda activate Filters

conda install -c menpo opencv3

conda install numpy scipy matplotlib sympy

and the code:

import numpy as np
import scipy as scipy
from numpy.random import uniform
import scipy.stats


np.set_printoptions(threshold=3)
np.set_printoptions(suppress=True)
import cv2


def drawLines(img, points, r, g, b):
    cv2.polylines(img, [np.int32(points)], isClosed=False, color=(r, g, b))

def drawCross(img, center, r, g, b):
    d = 5
    t = 2
    LINE_AA = cv2.LINE_AA if cv2.__version__[0] == '3' else cv2.CV_AA
    color = (r, g, b)
    ctrx = center[0,0]
    ctry = center[0,1]
    cv2.line(img, (ctrx - d, ctry - d), (ctrx + d, ctry + d), color, t, LINE_AA)
    cv2.line(img, (ctrx + d, ctry - d), (ctrx - d, ctry + d), color, t, LINE_AA)
    

def mouseCallback(event, x, y, flags,null):
    global center
    global trajectory
    global previous_x
    global previous_y
    global zs
    
    center=np.array([[x,y]])
    trajectory=np.vstack((trajectory,np.array([x,y])))
    #noise=sensorSigma * np.random.randn(1,2) + sensorMu
    
    if previous_x >0:
        heading=np.arctan2(np.array([y-previous_y]), np.array([previous_x-x ]))

        if heading>0:
            heading=-(heading-np.pi)
        else:
            heading=-(np.pi+heading)
            
        distance=np.linalg.norm(np.array([[previous_x,previous_y]])-np.array([[x,y]]) ,axis=1)
        
        std=np.array([2,4])
        u=np.array([heading,distance])
        predict(particles, u, std, dt=1.)
        zs = (np.linalg.norm(landmarks - center, axis=1) + (np.random.randn(NL) * sensor_std_err))
        update(particles, weights, z=zs, R=50, landmarks=landmarks)
        
        indexes = systematic_resample(weights)
        resample_from_index(particles, weights, indexes)

    previous_x=x
    previous_y=y
    


WIDTH=800
HEIGHT=600
WINDOW_NAME="Particle Filter"

#sensorMu=0
#sensorSigma=3

sensor_std_err=5


def create_uniform_particles(x_range, y_range, N):
    particles = np.empty((N, 2))
    particles[:, 0] = uniform(x_range[0], x_range[1], size=N)
    particles[:, 1] = uniform(y_range[0], y_range[1], size=N)
    return particles



def predict(particles, u, std, dt=1.):
    N = len(particles)
    dist = (u[1] * dt) + (np.random.randn(N) * std[1])
    particles[:, 0] += np.cos(u[0]) * dist
    particles[:, 1] += np.sin(u[0]) * dist
   
def update(particles, weights, z, R, landmarks):
    weights.fill(1.)
    for i, landmark in enumerate(landmarks):
       
        distance=np.power((particles[:,0] - landmark[0])**2 +(particles[:,1] - landmark[1])**2,0.5)
        weights *= scipy.stats.norm(distance, R).pdf(z[i])

 
    weights += 1.e-300 # avoid round-off to zero
    weights /= sum(weights)
    
def neff(weights):
    return 1. / np.sum(np.square(weights))

def systematic_resample(weights):
    N = len(weights)
    positions = (np.arange(N) + np.random.random()) / N

    indexes = np.zeros(N, 'i')
    cumulative_sum = np.cumsum(weights)
    i, j = 0, 0
    while i < N and j<N:
        if positions[i] < cumulative_sum[j]:
            indexes[i] = j
            i += 1
        else:
            j += 1
    return indexes
    
def estimate(particles, weights):
    pos = particles[:, 0:1]
    mean = np.average(pos, weights=weights, axis=0)
    var = np.average((pos - mean)**2, weights=weights, axis=0)
    return mean, var

def resample_from_index(particles, weights, indexes):
    particles[:] = particles[indexes]
    weights[:] = weights[indexes]
    weights /= np.sum(weights)

    
x_range=np.array([0,800])
y_range=np.array([0,600])

#Number of partciles
N=400

landmarks=np.array([ [144,73], [410,13], [336,175], [718,159], [178,484], [665,464]  ])
NL = len(landmarks)
particles=create_uniform_particles(x_range, y_range, N)


weights = np.array([1.0]*N)


# Create a black image, a window and bind the function to window
img = np.zeros((HEIGHT,WIDTH,3), np.uint8)
cv2.namedWindow(WINDOW_NAME)
cv2.setMouseCallback(WINDOW_NAME,mouseCallback)

center=np.array([[-10,-10]])

trajectory=np.zeros(shape=(0,2))
robot_pos=np.zeros(shape=(0,2))
previous_x=-1
previous_y=-1
DELAY_MSEC=50

while(1):

    cv2.imshow(WINDOW_NAME,img)
    img = np.zeros((HEIGHT,WIDTH,3), np.uint8)
    drawLines(img, trajectory,   0,   255, 0)
    drawCross(img, center, r=255, g=0, b=0)
    
    #landmarks
    for landmark in landmarks:
        cv2.circle(img,tuple(landmark),10,(255,0,0),-1)
    
    #draw_particles:
    for particle in particles:
        cv2.circle(img,tuple((int(particle[0]),int(particle[1]))),1,(255,255,255),-1)

    if cv2.waitKey(DELAY_MSEC) & 0xFF == 27:
        break
    
    cv2.circle(img,(10,10),10,(255,0,0),-1)
    cv2.circle(img,(10,30),3,(255,255,255),-1)
    cv2.putText(img,"Landmarks",(30,20),1,1.0,(255,0,0))
    cv2.putText(img,"Particles",(30,40),1,1.0,(255,255,255))
    cv2.putText(img,"Robot Trajectory(Ground truth)",(30,60),1,1.0,(0,255,0))

    drawLines(img, np.array([[10,55],[25,55]]), 0, 255, 0)
    


cv2.destroyAllWindows()

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

import numpy as np

import scipy as scipy

from numpy.random import uniform

import scipy.stats

np.set_printoptions(threshold=3)

np.set_printoptions(suppress=True)

import cv2

def drawLines(img, points, r, g, b):

cv2.polylines(img, [np.int32(points)], isClosed=False, color=(r, g, b))

def drawCross(img, center, r, g, b):

d = 5

t = 2

LINE_AA = cv2.LINE_AA if cv2.__version__[0] == '3' else cv2.CV_AA

color = (r, g, b)

ctrx = center[0,0]

ctry = center[0,1]

cv2.line(img, (ctrx - d, ctry - d), (ctrx + d, ctry + d), color, t, LINE_AA)

cv2.line(img, (ctrx + d, ctry - d), (ctrx - d, ctry + d), color, t, LINE_AA)

def mouseCallback(event, x, y, flags,null):

global center

global trajectory

global previous_x

global previous_y

global zs

center=np.array([[x,y]])

trajectory=np.vstack((trajectory,np.array([x,y])))

#noise=sensorSigma * np.random.randn(1,2) + sensorMu

if previous_x >0:

heading=np.arctan2(np.array([y-previous_y]), np.array([previous_x-x ]))

if heading>0:

heading=-(heading-np.pi)

else:

heading=-(np.pi+heading)

distance=np.linalg.norm(np.array([[previous_x,previous_y]])-np.array([[x,y]]) ,axis=1)

std=np.array([2,4])

u=np.array([heading,distance])

predict(particles, u, std, dt=1.)

zs = (np.linalg.norm(landmarks - center, axis=1) + (np.random.randn(NL) * sensor_std_err))

update(particles, weights, z=zs, R=50, landmarks=landmarks)

indexes = systematic_resample(weights)

resample_from_index(particles, weights, indexes)

previous_x=x

previous_y=y

WIDTH=800

HEIGHT=600

WINDOW_NAME="Particle Filter"

#sensorMu=0

#sensorSigma=3

sensor_std_err=5

def create_uniform_particles(x_range, y_range, N):

particles = np.empty((N, 2))

particles[:, 0] = uniform(x_range[0], x_range[1], size=N)

particles[:, 1] = uniform(y_range[0], y_range[1], size=N)

return particles

def predict(particles, u, std, dt=1.):

N = len(particles)

dist = (u[1] * dt) + (np.random.randn(N) * std[1])

particles[:, 0] += np.cos(u[0]) * dist

particles[:, 1] += np.sin(u[0]) * dist

def update(particles, weights, z, R, landmarks):

weights.fill(1.)

for i, landmark in enumerate(landmarks):

distance=np.power((particles[:,0] - landmark[0])**2 +(particles[:,1] - landmark[1])**2,0.5)

weights *= scipy.stats.norm(distance, R).pdf(z[i])

weights += 1.e-300 # avoid round-off to zero

weights /= sum(weights)

def neff(weights):

return 1. / np.sum(np.square(weights))

def systematic_resample(weights):

N = len(weights)

positions = (np.arange(N) + np.random.random()) / N

indexes = np.zeros(N, 'i')

cumulative_sum = np.cumsum(weights)

i, j = 0, 0

while i < N and j<N:

if positions[i] < cumulative_sum[j]:

indexes[i] = j

i += 1

else:

j += 1

return indexes

def estimate(particles, weights):

pos = particles[:, 0:1]

mean = np.average(pos, weights=weights, axis=0)

var = np.average((pos - mean)**2, weights=weights, axis=0)

return mean, var

def resample_from_index(particles, weights, indexes):

particles[:] = particles[indexes]

weights[:] = weights[indexes]

weights /= np.sum(weights)

x_range=np.array([0,800])

y_range=np.array([0,600])

#Number of partciles

N=400

landmarks=np.array([ [144,73], [410,13], [336,175], [718,159], [178,484], [665,464] ])

NL = len(landmarks)

particles=create_uniform_particles(x_range, y_range, N)

weights = np.array([1.0]*N)

# Create a black image, a window and bind the function to window

img = np.zeros((HEIGHT,WIDTH,3), np.uint8)

cv2.namedWindow(WINDOW_NAME)

cv2.setMouseCallback(WINDOW_NAME,mouseCallback)

center=np.array([[-10,-10]])

trajectory=np.zeros(shape=(0,2))

robot_pos=np.zeros(shape=(0,2))

previous_x=-1

previous_y=-1

DELAY_MSEC=50

while(1):

cv2.imshow(WINDOW_NAME,img)

img = np.zeros((HEIGHT,WIDTH,3), np.uint8)

drawLines(img, trajectory, 0, 255, 0)

drawCross(img, center, r=255, g=0, b=0)

#landmarks

for landmark in landmarks:

cv2.circle(img,tuple(landmark),10,(255,0,0),-1)

#draw_particles:

for particle in particles:

cv2.circle(img,tuple((int(particle[0]),int(particle[1]))),1,(255,255,255),-1)

if cv2.waitKey(DELAY_MSEC) & 0xFF == 27:

break

cv2.circle(img,(10,10),10,(255,0,0),-1)

cv2.circle(img,(10,30),3,(255,255,255),-1)

cv2.putText(img,"Landmarks",(30,20),1,1.0,(255,0,0))

cv2.putText(img,"Particles",(30,40),1,1.0,(255,255,255))

cv2.putText(img,"Robot Trajectory(Ground truth)",(30,60),1,1.0,(0,255,0))

drawLines(img, np.array([[10,55],[25,55]]), 0, 255, 0)

cv2.destroyAllWindows()

Parcticle Filter Explained With Python Code From Scratch Read More »

Kalman Filter Explained With Python Code From Scratch

23 Comments / C++, Machine Learning, Python, Robotic, Tutorials / admin

This snippet shows tracking mouse cursor with Python code from scratch and comparing the result with OpenCV. The CSV file that has been used are being created with below c++ code. A sample could be downloaded from here 1, 2, 3. Python Kalman Filter

import numpy as np
np.set_printoptions(threshold=3)
np.set_printoptions(suppress=True)
from numpy import genfromtxt


#Notation used coming from: https://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures/


def prediction(X_hat_t_1,P_t_1,F_t,B_t,U_t,Q_t):
    X_hat_t=F_t.dot(X_hat_t_1)+(B_t.dot(U_t).reshape(B_t.shape[0],-1) )
    P_t=np.diag(np.diag(F_t.dot(P_t_1).dot(F_t.transpose())))+Q_t
    return X_hat_t,P_t
    

def update(X_hat_t,P_t,Z_t,R_t,H_t):
    
    K_prime=P_t.dot(H_t.transpose()).dot( np.linalg.inv ( H_t.dot(P_t).dot(H_t.transpose()) +R_t ) )  
    print("K:\n",K_prime)
    
    X_t=X_hat_t+K_prime.dot(Z_t-H_t.dot(X_hat_t))
    P_t=P_t-K_prime.dot(H_t).dot(P_t)
    
    return X_t,P_t


acceleration=0
delta_t=1/20#milisecond

groundTruth = genfromtxt('data/groundTruth.csv', delimiter=',',skip_header=1)

#Observations: position_X, position_Y
measurmens = genfromtxt('data/measurmens.csv', delimiter=',',skip_header=1)


#Checking our result with OpenCV
opencvKalmanOutput = genfromtxt('data/kalmanv.csv', delimiter=',',skip_header=1)

#Transition matrix
F_t=np.array([ [1 ,0,delta_t,0] , [0,1,0,delta_t] , [0,0,1,0] , [0,0,0,1] ])

#Initial State cov
P_t= np.identity(4)*0.2

#Process cov
Q_t= np.identity(4)

#Control matrix
B_t=np.array( [ [0] , [0], [0] , [0] ])

#Control vector
U_t=acceleration

#Measurment Matrix
H_t = np.array([ [1, 0, 0, 0], [ 0, 1, 0, 0]])

#Measurment cov
R_t= np.identity(2)*5

# Initial State
X_hat_t = np.array( [[0],[0],[0],[0]] )
print("X_hat_t",X_hat_t.shape)
print("P_t",P_t.shape)
print("F_t",F_t.shape)
print("B_t",B_t.shape)
print("Q_t",Q_t.shape)
print("R_t",R_t.shape)
print("H_t",H_t.shape)

for i in range(measurmens.shape[0]):
    X_hat_t,P_hat_t = prediction(X_hat_t,P_t,F_t,B_t,U_t,Q_t)
    print("Prediction:")
    print("X_hat_t:\n",X_hat_t,"\nP_t:\n",P_t)
    
    Z_t=measurmens[i].transpose()
    Z_t=Z_t.reshape(Z_t.shape[0],-1)
    
    print(Z_t.shape)
    
    X_t,P_t=update(X_hat_t,P_hat_t,Z_t,R_t,H_t)
    print("Update:")
    print("X_t:\n",X_t,"\nP_t:\n",P_t)
    X_hat_t=X_t
    P_hat_t=P_t
    
    print("=========================================")
    print("Opencv Kalman Output:")
    print("X_t:\n",opencvKalmanOutput[i])

import numpy as np

np.set_printoptions(threshold=3)

np.set_printoptions(suppress=True)

from numpy import genfromtxt

#Notation used coming from: https://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures/

def prediction(X_hat_t_1,P_t_1,F_t,B_t,U_t,Q_t):

X_hat_t=F_t.dot(X_hat_t_1)+(B_t.dot(U_t).reshape(B_t.shape[0],-1) )

P_t=np.diag(np.diag(F_t.dot(P_t_1).dot(F_t.transpose())))+Q_t

return X_hat_t,P_t

def update(X_hat_t,P_t,Z_t,R_t,H_t):

K_prime=P_t.dot(H_t.transpose()).dot( np.linalg.inv ( H_t.dot(P_t).dot(H_t.transpose()) +R_t ) )

print("K:\n",K_prime)

X_t=X_hat_t+K_prime.dot(Z_t-H_t.dot(X_hat_t))

P_t=P_t-K_prime.dot(H_t).dot(P_t)

return X_t,P_t

acceleration=0

delta_t=1/20#milisecond

groundTruth = genfromtxt('data/groundTruth.csv', delimiter=',',skip_header=1)

#Observations: position_X, position_Y

measurmens = genfromtxt('data/measurmens.csv', delimiter=',',skip_header=1)

#Checking our result with OpenCV

opencvKalmanOutput = genfromtxt('data/kalmanv.csv', delimiter=',',skip_header=1)

#Transition matrix

F_t=np.array([ [1 ,0,delta_t,0] , [0,1,0,delta_t] , [0,0,1,0] , [0,0,0,1] ])

#Initial State cov

P_t= np.identity(4)*0.2

#Process cov

Q_t= np.identity(4)

#Control matrix

B_t=np.array( [ [0] , [0], [0] , [0] ])

#Control vector

U_t=acceleration

#Measurment Matrix

H_t = np.array([ [1, 0, 0, 0], [ 0, 1, 0, 0]])

#Measurment cov

R_t= np.identity(2)*5

# Initial State

X_hat_t = np.array( [[0],[0],[0],[0]] )

print("X_hat_t",X_hat_t.shape)

print("P_t",P_t.shape)

print("F_t",F_t.shape)

print("B_t",B_t.shape)

print("Q_t",Q_t.shape)

print("R_t",R_t.shape)

print("H_t",H_t.shape)

for i in range(measurmens.shape[0]):

X_hat_t,P_hat_t = prediction(X_hat_t,P_t,F_t,B_t,U_t,Q_t)

print("Prediction:")

print("X_hat_t:\n",X_hat_t,"\nP_t:\n",P_t)

Z_t=measurmens[i].transpose()

Z_t=Z_t.reshape(Z_t.shape[0],-1)

print(Z_t.shape)

X_t,P_t=update(X_hat_t,P_hat_t,Z_t,R_t,H_t)

print("Update:")

print("X_t:\n",X_t,"\nP_t:\n",P_t)

X_hat_t=X_t

P_hat_t=P_t

print("=========================================")

print("Opencv Kalman Output:")

print("X_t:\n",opencvKalmanOutput[i])

C++ and OpenCV Kalman Filter Rapidcsv has been downloaded from

Kalman Filter Explained With Python Code From Scratch Read More »

How to develop GUI Application with PyQt (python Qt)

Leave a Comment / C++, Python, Tutorials / admin

There are two main methods for developing GUI application with qt: 1) Adding all widgets in your code (your cpp or python code) 2) Creating qt UI files, adding widgets there and load everything into your application. 1)Adding all widgets in your code Here is the snippet for adding all widgets and their slots in code:

import sys
print(sys.version)
import warnings
warnings.filterwarnings('ignore')


from PyQt5 import QtCore, QtWidgets
from PyQt5.QtWidgets import QMainWindow, QLabel, QSlider
from PyQt5.QtCore import QSize, Qt, pyqtSlot,pyqtSignal 



class HelloWindow(QMainWindow):
    
    pushButtonClicked = pyqtSignal()
    valueUpdating = pyqtSignal(int)
    
    
    def pushButtonClicked(self):
        self.title.setText("PyQt updated!")
            
    def valueUpdating(self, value):
        self.title.setText(str(value))
    
    def __init__(self):
        QMainWindow.__init__(self)

        self.setMinimumSize(QSize(640, 480))    
        self.setWindowTitle("Hello world") 

        self.title = QLabel("PyQt!", self)
        self.title.setAlignment(QtCore.Qt.AlignCenter) 


        self.pushButton = QtWidgets.QPushButton(self)
        self.pushButton.setGeometry(QtCore.QRect(140, 200, 99, 27))#x,y, width, height
        self.pushButton.setObjectName("pushButton")
        self.pushButton.setText("Click Me!")
        self.pushButton.clicked.connect(self.pushButtonClicked)
        
        self.slider = QtWidgets.QSlider(self)
        self.slider.setGeometry(QtCore.QRect(100, 20, 100, 30))
        self.slider.setFocusPolicy(Qt.StrongFocus)
        self.slider.setTickPosition(QSlider.TicksBothSides)
        self.slider.setSingleStep(1)
        self.slider.setPageStep(1)
        self.slider.setMaximum(100)
        self.slider.setMinimum(0)
        self.slider.setOrientation(Qt.Horizontal)
        
        self.slider.valueChanged.connect(self.valueUpdating)
        


if __name__ == "__main__":
    app = QtWidgets.QApplication(sys.argv)
    mainWin = HelloWindow()
    mainWin.show()
    sys.exit( app.exec_() )

import sys

print(sys.version)

import warnings

warnings.filterwarnings('ignore')

from PyQt5 import QtCore, QtWidgets

from PyQt5.QtWidgets import QMainWindow, QLabel, QSlider

from PyQt5.QtCore import QSize, Qt, pyqtSlot,pyqtSignal

class HelloWindow(QMainWindow):

pushButtonClicked = pyqtSignal()

valueUpdating = pyqtSignal(int)

def pushButtonClicked(self):

self.title.setText("PyQt updated!")

def valueUpdating(self, value):

self.title.setText(str(value))

def __init__(self):

QMainWindow.__init__(self)

self.setMinimumSize(QSize(640, 480))

self.setWindowTitle("Hello world")

self.title = QLabel("PyQt!", self)

self.title.setAlignment(QtCore.Qt.AlignCenter)

self.pushButton = QtWidgets.QPushButton(self)

self.pushButton.setGeometry(QtCore.QRect(140, 200, 99, 27))#x,y, width, height

self.pushButton.setObjectName("pushButton")

self.pushButton.setText("Click Me!")

self.pushButton.clicked.connect(self.pushButtonClicked)

self.slider = QtWidgets.QSlider(self)

self.slider.setGeometry(QtCore.QRect(100, 20, 100, 30))

self.slider.setFocusPolicy(Qt.StrongFocus)

self.slider.setTickPosition(QSlider.TicksBothSides)

self.slider.setSingleStep(1)

self.slider.setPageStep(1)

self.slider.setMaximum(100)

self.slider.setMinimum(0)

self.slider.setOrientation(Qt.Horizontal)

self.slider.valueChanged.connect(self.valueUpdating)

if __name__ == "__main__":

app = QtWidgets.QApplication(sys.argv)

mainWin = HelloWindow()

mainWin.show()

sys.exit( app.exec_() )

How to develop GUI Application with PyQt (python Qt) Read More »

Breadth-first search (BFS) and Depth-first search (DSF) Algorithm with Python and C++

Leave a Comment / C++, Machine Learning, Python, Tutorials / admin

Python Implementation BFS traverse:

Root='a'
g.nodes[Root]['visited']=True
print Root 
Q=[Root]
BFS_travrse(Q,g)

Root='a'

g.nodes[Root]['visited']=True

print Root

Q=[Root]

BFS_travrse(Q,g)

DFS traverse:

Root='a'
print Root
g.nodes[Root]['visited']=True
coloring_tree(g)
DFS_travrse(Root,g)

Root='a'

print Root

g.nodes[Root]['visited']=True

coloring_tree(g)

DFS_travrse(Root,g)

import networkx as nx
import matplotlib.pyplot as plt
from networkx.drawing.nx_agraph import write_dot, graphviz_layout


def coloring_tree(G):

    visited_list=[]
    for i in G.nodes():
        visited_list.append( g.nodes[i]['visited'] )
    
    graph_color_map=[]
    for i  in visited_list:
        if i:
            color='blue'
        else:
            color='red'
        graph_color_map.append(color)
    pos =graphviz_layout(G, prog='dot')
    nx.draw(G, pos, with_labels=True, arrows=True,node_color =  graph_color_map)
    #plt.savefig('nx_test.png')
    plt.show()
    
    return

def DFS_travrse(N,G):
    neighbors =G.neighbors(N)
    size=len( list(neighbors))
    if size==0:
        return
    neighbors =G.neighbors(N)
    for neighbor in neighbors:
        G.nodes[neighbor]['visited']=True
        coloring_tree(G)
        DFS_travrse(neighbor,G)
    return

def BFS_travrse(Q,G):
    if len(Q)==0:
        return
    Root=Q[0]
    Q=Q[1:len(Q)]
    neighbors =G.neighbors(Root)
    for neighbor in neighbors:
        print neighbor
        coloring_tree(G)
        G.nodes[neighbor]['visited']=True
        Q.append(neighbor)
 
    BFS_travrse(Q,G)
    return


g=nx.DiGraph()
g.add_node('a',visited=False)
g.add_node('b',visited=False)
g.add_node('c',visited=False)
g.add_node('d',visited=False)
g.add_node('e',visited=False)
g.add_node('f',visited=False)
g.add_node('g',visited=False)
g.add_node('h',visited=False)


g.add_edge('a','b')
g.add_edge('a','c')
g.add_edge('b','e')
g.add_edge('b','d')
g.add_edge('e','h')
g.add_edge('c','f')
g.add_edge('c','g')

import networkx as nx

import matplotlib.pyplot as plt

from networkx.drawing.nx_agraph import write_dot, graphviz_layout

def coloring_tree(G):

visited_list=[]

for i in G.nodes():

visited_list.append( g.nodes[i]['visited'] )

graph_color_map=[]

for i in visited_list:

if i:

color='blue'

else:

color='red'

graph_color_map.append(color)

pos =graphviz_layout(G, prog='dot')

nx.draw(G, pos, with_labels=True, arrows=True,node_color = graph_color_map)

#plt.savefig('nx_test.png')

plt.show()

return

def DFS_travrse(N,G):

neighbors =G.neighbors(N)

size=len( list(neighbors))

if size==0:

return

neighbors =G.neighbors(N)

for neighbor in neighbors:

G.nodes[neighbor]['visited']=True

coloring_tree(G)

DFS_travrse(neighbor,G)

return

def BFS_travrse(Q,G):

if len(Q)==0:

return

Root=Q[0]

Q=Q[1:len(Q)]

neighbors =G.neighbors(Root)

for neighbor in neighbors:

print neighbor

coloring_tree(G)

G.nodes[neighbor]['visited']=True

Q.append(neighbor)

BFS_travrse(Q,G)

return

g=nx.DiGraph()

g.add_node('a',visited=False)

g.add_node('b',visited=False)

g.add_node('c',visited=False)

g.add_node('d',visited=False)

g.add_node('e',visited=False)

g.add_node('f',visited=False)

g.add_node('g',visited=False)

g.add_node('h',visited=False)

g.add_edge('a','b')

g.add_edge('a','c')

g.add_edge('b','e')

g.add_edge('b','d')

g.add_edge('e','h')

g.add_edge('c','f')

g.add_edge('c','g')

C++ Implementation

#include <algorithm>
#include <iostream>
#include <memory>

class node
{
public:
    std::vector<std::shared_ptr<node> > leaves;
    double data;
};

void populateTree(std::shared_ptr<node> rootNodePtr)
{
/*
                   -1
                  /   \
                3       7
              /  \    /
             4    1  5
*/

    rootNodePtr->data=-1;
    std::shared_ptr<node>  leftNodePtr,rightNodePtr;
    std::shared_ptr<node>  leftNode1stKidPtr,leftNode2ndtKidPtr, rightNode1stKidPtr;

    leftNodePtr.reset(new node) ;
    rightNodePtr.reset(new node);
    rootNodePtr->leaves.push_back(leftNodePtr);
    rootNodePtr->leaves.push_back(rightNodePtr);

    leftNodePtr->data=3;
    rightNodePtr->data=7;

    leftNode1stKidPtr.reset(new node);
    leftNode2ndtKidPtr.reset(new node);
    rightNode1stKidPtr.reset(new node);

    leftNode1stKidPtr->data=4;
    leftNode2ndtKidPtr->data=1;
    rightNode1stKidPtr->data=5;

    leftNodePtr->leaves.push_back(leftNode1stKidPtr);
    leftNodePtr->leaves.push_back(leftNode2ndtKidPtr);

    rightNodePtr->leaves.push_back(rightNode1stKidPtr);

}

void DFS(std::shared_ptr<node> rootNode)
{
    std::cout<<rootNode->data <<std::endl;
    for(auto n:rootNode->leaves)
        DFS(n);
}

void BFS(std::shared_ptr<node> rootNode)
{

    for(auto n:rootNode->leaves)
        std::cout<<n->data <<std::endl;

    for(auto n:rootNode->leaves)
        BFS(n);
}
int main()
{
    std::shared_ptr<node> tree(new node);
    populateTree(tree);
    DFS(tree);
    BFS(tree); 
}

#include <algorithm>

#include <iostream>

#include <memory>

class node

{

public:

std::vector<std::shared_ptr<node> > leaves;

double data;

};

void populateTree(std::shared_ptr<node> rootNodePtr)

{

-1

/ \

3 7

/ \ /

4 1 5

rootNodePtr->data=-1;

std::shared_ptr<node> leftNodePtr,rightNodePtr;

std::shared_ptr<node> leftNode1stKidPtr,leftNode2ndtKidPtr, rightNode1stKidPtr;

leftNodePtr.reset(new node) ;

rightNodePtr.reset(new node);

rootNodePtr->leaves.push_back(leftNodePtr);

rootNodePtr->leaves.push_back(rightNodePtr);

leftNodePtr->data=3;

rightNodePtr->data=7;

leftNode1stKidPtr.reset(new node);

leftNode2ndtKidPtr.reset(new node);

rightNode1stKidPtr.reset(new node);

leftNode1stKidPtr->data=4;

leftNode2ndtKidPtr->data=1;

rightNode1stKidPtr->data=5;

leftNodePtr->leaves.push_back(leftNode1stKidPtr);

leftNodePtr->leaves.push_back(leftNode2ndtKidPtr);

rightNodePtr->leaves.push_back(rightNode1stKidPtr);

}

void DFS(std::shared_ptr<node> rootNode)

{

std::cout<<rootNode->data <<std::endl;

for(auto n:rootNode->leaves)

DFS(n);

}

void BFS(std::shared_ptr<node> rootNode)

{

for(auto n:rootNode->leaves)

std::cout<<n->data <<std::endl;

for(auto n:rootNode->leaves)

BFS(n);

}

int main()

{

std::shared_ptr<node> tree(new node);

populateTree(tree);

DFS(tree);

BFS(tree);

}

Breadth-first search (BFS) and Depth-first search (DSF) Algorithm with Python and C++ Read More »

Populating directed graph in networkx from CSV adjacency matrix

3 Comments / Python, Tutorials / admin

import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt
import csv


def make_label_dict(labels):
    l = {}
    for i, label in enumerate(labels):
        l[i] = label
    return l

input_data = pd.read_csv('data/adjacency_matrix.csv', index_col=0)
#print input_data.head
print input_data.values
G = nx.Graph(input_data.values)

with open('data/adjacency_matrix.csv', 'r') as f:
    d_reader = csv.DictReader(f)
    headers = d_reader.fieldnames

#print headers

labels=make_label_dict(headers)
#print labels

edge_labels = dict( ((u, v), d["weight"]) for u, v, d in G.edges(data=True) )
pos = nx.spring_layout(G)
nx.draw(G, pos)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
nx.draw(G,pos,node_size=500, labels=labels, with_labels=True)
plt.show()

import pandas as pd

import networkx as nx

import matplotlib.pyplot as plt

import csv

def make_label_dict(labels):

l = {}

for i, label in enumerate(labels):

l[i] = label

return l

input_data = pd.read_csv('data/adjacency_matrix.csv', index_col=0)

#print input_data.head

print input_data.values

G = nx.Graph(input_data.values)

with open('data/adjacency_matrix.csv', 'r') as f:

d_reader = csv.DictReader(f)

headers = d_reader.fieldnames

#print headers

labels=make_label_dict(headers)

#print labels

edge_labels = dict( ((u, v), d["weight"]) for u, v, d in G.edges(data=True) )

pos = nx.spring_layout(G)

nx.draw(G, pos)

nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)

nx.draw(G,pos,node_size=500, labels=labels, with_labels=True)

plt.show()

Populating directed graph in networkx from CSV adjacency matrix Read More »

Drawing graphs in Python with networkx

Leave a Comment / Python, Tutorials / admin

import networkx as nx
import matplotlib.pyplot as plt

G=nx.Graph()

###########################Adding nodes###########################
G.add_node(1)
G.add_nodes_from([2,3,4])

#Add an nbunch: iterable container of nodes  (e.g. a list, set, graph, file, etc..)
H=nx.path_graph(1)
#G now contains the nodes of H as nodes of G. 
G.add_nodes_from(H)
#Graph of Graph
#G.add_node(H)



G.add_node("b")       # adds node "behnam"
G.add_nodes_from("behnam") # adds 6 nodes: 'b','e' ,'h', 'n', 'a','m'


###########################Adding edges###########################
G.add_edge(1, 4)
edge_2_3=(2,3)
G.add_edge(*edge_2_3) # unpack edge tuple with *

#An edge can be associated with any object x using G.add_edge(n1,n2,object=x).
edge_2_4=(2,4,{'weight':3.1415})

G.add_edge(*edge_2_4)

G.add_edge(1, 2, weight=4.7 )
G.add_weighted_edges_from([(3,4,0.125)])


###########################Accessing nodes,edges and neighbors###########################
print 'Nodes'
print G.nodes()
print 'List of edges'
print G.edges()
print 'Neighbors'
print G.neighbors(1)


#Accessing edges
print 'Accessing edges'
print G[3]
print G[4]
print G[4][2]['weight']


for (u,v,d) in G.edges(data='weight'):
    if d>0.5: print('(%d, %d, %.3f)'%(u,v,d))


###########################Adding attributes to nodes###########################
G.add_node(1, time='5pm')
print G.node[1]

G.add_edges_from([(1,2,{'color':'blue'}), (2,3,{'weight':8})])

###########################Multigraphs###########################
#allow you to add the same edge twice, possibly with different edge data.

MG=nx.MultiGraph()
MG.add_weighted_edges_from([(1,2,.5), (1,2,.75), (2,3,.5)])
MG.degree(weight='weight')

GG=nx.Graph()
for n,nbrs in MG.adjacency_iter():
    for nbr,edict in nbrs.items():
        minvalue=min([d['weight'] for d in edict.values()])
        GG.add_edge(n,nbr, weight = minvalue)

print 'shortest path from 1 to 3'
print nx.shortest_path(GG,1,3)



###########################Graph operations###########################
#subgraph(G, nbunch)      - induce subgraph of G on nodes in nbunh
#union(G1,G2)             - graph union
#disjoint_union(G1,G2)    - graph union assuming all nodes are different
#cartesian_product(G1,G2) - return Cartesian product graph
#compose(G1,G2)           - combine graphs identifying nodes common to both
#complement(G)            - graph complement
#create_empty_copy(G)     - return an empty copy of the same graph class
#convert_to_undirected(G) - return an undirected representation of G
#convert_to_directed(G)   - return a directed representation of G

###########################Ploting Graphs ###########################


#nx.draw_spectral(G)
#nx.draw_circular(G)
#nx.draw_random(G)

pos=nx.spring_layout(G) # positions for all nodes
nx.draw_networkx_labels(G,pos,font_size=20,font_family='sans-serif')
nx.draw(G,pos)

plt.show()

100

101

102

103

import networkx as nx

import matplotlib.pyplot as plt

G=nx.Graph()

###########################Adding nodes###########################

G.add_node(1)

G.add_nodes_from([2,3,4])

#Add an nbunch: iterable container of nodes (e.g. a list, set, graph, file, etc..)

H=nx.path_graph(1)

#G now contains the nodes of H as nodes of G.

G.add_nodes_from(H)

#Graph of Graph

#G.add_node(H)

G.add_node("b") # adds node "behnam"

G.add_nodes_from("behnam") # adds 6 nodes: 'b','e' ,'h', 'n', 'a','m'

###########################Adding edges###########################

G.add_edge(1, 4)

edge_2_3=(2,3)

G.add_edge(*edge_2_3) # unpack edge tuple with *

#An edge can be associated with any object x using G.add_edge(n1,n2,object=x).

edge_2_4=(2,4,{'weight':3.1415})

G.add_edge(*edge_2_4)

G.add_edge(1, 2, weight=4.7 )

G.add_weighted_edges_from([(3,4,0.125)])

###########################Accessing nodes,edges and neighbors###########################

print 'Nodes'

print G.nodes()

print 'List of edges'

print G.edges()

print 'Neighbors'

print G.neighbors(1)

#Accessing edges

print 'Accessing edges'

print G[3]

print G[4]

print G[4][2]['weight']

for (u,v,d) in G.edges(data='weight'):

if d>0.5: print('(%d, %d, %.3f)'%(u,v,d))

###########################Adding attributes to nodes###########################

G.add_node(1, time='5pm')

print G.node[1]

G.add_edges_from([(1,2,{'color':'blue'}), (2,3,{'weight':8})])

###########################Multigraphs###########################

#allow you to add the same edge twice, possibly with different edge data.

MG=nx.MultiGraph()

MG.add_weighted_edges_from([(1,2,.5), (1,2,.75), (2,3,.5)])

MG.degree(weight='weight')

GG=nx.Graph()

for n,nbrs in MG.adjacency_iter():

for nbr,edict in nbrs.items():

minvalue=min([d['weight'] for d in edict.values()])

GG.add_edge(n,nbr, weight = minvalue)

print 'shortest path from 1 to 3'

print nx.shortest_path(GG,1,3)

###########################Graph operations###########################

#subgraph(G, nbunch) - induce subgraph of G on nodes in nbunh

#union(G1,G2) - graph union

#disjoint_union(G1,G2) - graph union assuming all nodes are different

#cartesian_product(G1,G2) - return Cartesian product graph

#compose(G1,G2) - combine graphs identifying nodes common to both

#complement(G) - graph complement

#create_empty_copy(G) - return an empty copy of the same graph class

#convert_to_undirected(G) - return an undirected representation of G

#convert_to_directed(G) - return a directed representation of G

###########################Ploting Graphs ###########################

#nx.draw_spectral(G)

#nx.draw_circular(G)

#nx.draw_random(G)

pos=nx.spring_layout(G) # positions for all nodes

nx.draw_networkx_labels(G,pos,font_size=20,font_family='sans-serif')

nx.draw(G,pos)

plt.show()

Drawing graphs in Python with networkx Read More »

Hierarchical Clustring in python

Leave a Comment / Machine Learning, Python, Tutorials / admin

Hierarchical Clustering is a method of clustering which build a hierarchy of clusters. It could be Agglomerative or Divisive. Agglomerative: At the first step, every item is a cluster, then clusters based on their distances are merged and form bigger clusters till all data is in one cluster (Bottom Up). The complexity is \( O (n^2log(n) ) \). Divisive: At the beginning,

Hierarchical Clustring in python Read More »

Cookie	Duration	Description
cookielawinfo-checbox-analytics	11 months	This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Analytics".
cookielawinfo-checbox-functional	11 months	The cookie is set by GDPR cookie consent to record the user consent for the cookies in the category "Functional".
cookielawinfo-checbox-others	11 months	This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Other.
cookielawinfo-checkbox-necessary	11 months	This cookie is set by GDPR Cookie Consent plugin. The cookies is used to store the user consent for the cookies in the category "Necessary".
cookielawinfo-checkbox-performance	11 months	This cookie is set by GDPR Cookie Consent plugin. The cookie is used to store the user consent for the cookies in the category "Performance".
viewed_cookie_policy	11 months	The cookie is set by the GDPR Cookie Consent plugin and is used to store whether or not user has consented to the use of cookies. It does not store any personal data.