Clustering and Bag of Visual Words
These programming exercises will focus on K-means clustering.
If you're unsure of how k-means works, read this very helpful and freely available online breakdown from Stanford's CS221 course;
This assignment requires you to loosely interpret how k-means is a specific case of a more general algorithm named Expectation Maximisation. This is explained toward the end of the above article.
First, lets loading the dataset.
import time
import sys
! pip install numpy
import numpy as np
! pip install matplotlib
import matplotlib.pyplot as plt
import math
import os
from matplotlib.pyplot import imread
! pip install patchify
from patchify import patchify
np.random.seed(1)X = np.load("./data_clustering.npy")
plt.scatter(X[:,0], X[:,1])
plt.show()output:
K-means is a special, simple case of the Expectation Maximisation (EM) algorithm.
This simplified EM (k-means), is divided into two steps.
The E-Step, where for every sample in your dataset you find which "centroid" that datapoint is closest to that sample, and record that information.
The M-Step, where you move each "centroid" to the center of the samples which were found to be closest to it in the E-Step.
Each centroid is simply an estimated mean of a cluster. If you have 1 centroid, then this centroid will become the mean of all your data.
Centroids are initially random values, and the k-means algorithm attempts to modify them so that each one represents the center of a cluster.
We have implemented a centroids initialization function.
def initialise_parameters(m, X):
C = X[np.random.choice(X.shape[0], m)]
return C
C = initialise_parameters(4, X)
print(C)output:
[[ 0.55638768 1.19083041]
[ 0.99468733 -0.63105385]
[-0.80861347 -0.47487527]
[ 0.83443335 0.7038998 ]]Now let's implement K-Means algorithm.
HINT:
https://en.wikipedia.org/wiki/K-means_clustering#Standard_algorithm
Each row of 𝐿 is a centroid taken from 𝐶.
def E_step(C, X):
# YOUR CODE HERE
pass
L = E_step(C, X)
plt.scatter(L[:, 0], L[:, 1])
plt.show()
def M_step(C, X, L):
# YOUR CODE HERE
pass
print('Before:')
print(C)
print('\nAfter:')
new_C = M_step(C, X, L)
print(new_C)
HINT: Using initialise_parameters to initial centroid
def kmeans(X, m, threshold):
# YOUR CODE HERE
pass
#CODE TO DISPLAY YOUR RESULTS. DO NOT MODIFY.
C_final, L_final = kmeans(X, 4, 1e-6)
print('Initial Parameters:')
print(C)
print('\nFinal Parameters:')
print(C_final)
def allocator(X, L, c):
cluster = []
for i in range(L.shape[0]):
if np.array_equal(L[i, :], c):
cluster.append(X[i, :])
return np.asarray(cluster)
colours = ['r', 'g', 'b', 'y']
for i in range(4):
cluster = allocator(X, L_final, C_final[i, :])
plt.scatter(cluster[:,0], cluster[:,1], c=colours[i])plt.show()
Bag of Visual Words (BOVW)
Implement Bag of Visual Words (BOVW) to perform pedestrian retrieval. See more information at:
First, let's understand the settings of datasets.
We provide you with 3 pedestrian image folders, 'train', 'gallery', and 'val_query'. There are 99 images in 'train' which are used to create a vocabulary through clustering. 'Gallery' contains 90 images which belong to 15 different pedestrians. If two images' file name have same first four digits, then these two images belong to same pedestrian. When we randomly select a query image from 'val_query', we aim to find the images from the 'gallery' that contain the same person as the query. Let's load the images in 'train' and visualise an example.
train_images = []
for file in os.listdir("./train"):
if file.endswith(".jpg"):
im = imread("./train/" + file)
train_images.append(im)
assert im.shape == (128, 64, 3)
plt.imshow(train_images[0])plt.show()To generate the vocabulary, the first step is computing local image features. For simplicity, patches of size 8×8 are densely sampled, and we use these patches for local feature extraction. The sampling step is 8, so there is no overlapping between patches
def patchify_images(image):
return patchify(image, (8, 8, 3), step=8).reshape((-1, 8, 8, 3))
patches = patchify_images(train_images[0])
print(f'Before splitting, the image size is {train_images[0].shape}')
print(f'After splitting, the patches are {patches.shape}')
print('A patch is like:')
plt.imshow(patches[50])plt.show()
def compute_patch_feature(patch):
#YOUR CODE HERE
pass
start = time.time()
print(f'The shape of the feature of a patch is :{compute_patch_feature(patches[50]).shape} in my implementation.')
end = time.time()
print(f'It takes {end-start} seconds to compute the feature for one image patch.')
def create_vocabulary(train_images):
#YOUR CODE HERE
pass
start = time.time()
vocabulary = create_vocabulary(train_images)
end = time.time()
print(f'The shape of my vocabulary is {vocabulary.shape}.')
print(f'It takes {end-start} seconds to generate the vocabulary.' )You have built the vocabulary successfully. You must know how to compute the feature representation of an image. Now, let's do a simple pedestrian retrieval task where we are going to pick a query image from 'val_query' and try to search for images in 'gallery' which contain the same person.
gallery_images = []
gallery_filenames = []
for file in os.listdir("./gallery"):
if file.endswith(".jpg"):
im = imread("./gallery/" + file)
gallery_images.append(im)
gallery_filenames.append(file)
query_image = imread("./val_query/0001_c5_0022.jpg")
# show a query image
plt.imshow(query_image)plt.show()
def image_similarity_ranking(gallery_images, query_image, vocabulary, gallery_filenames):
#YOUR CODE HERE
pass
# visualise your query image and its best match in gallery. Ideally, they should be the same person.
start = time.time()
name_list = image_similarity_ranking(gallery_images, imread("./val_query/0001_c5_0022.jpg"), vocabulary,gallery_filenames)
end = time.time()
print(f'It takes {end-start} seconds to get the matching results of a query')
print('Your query image is:')
plt.imshow(imread("./val_query/0001_c5_0022.jpg"))
plt.show()
print('The best matching is:')
plt.imshow(gallery_images[gallery_filenames.index(name_list[0])])
plt.show()
# We have 3 query images, you can try other two queries to see whether your algorithm performs well.Please use the following code to calculate the matching score of 'val_query' dataset. Make sure the score is reasonble to you. We will be evaluating your implementation using some test queries that are not provided to you.
def match_score(name, name_list):
def reid(idx):
return name_list[idx][:4]
base = 0.0
code = name[:4]
if reid(0) == code or reid(1) == code or reid(2) == code:
base += 0.4
if (reid(0) == code):
base += 0.3
elif (reid(1) == code):
base += 0.2
elif (reid(2) == code):
base += 0.1
if (reid(0) == code and reid(1) == code) or (reid(0) == code and reid(2) == code) or (
reid(1) == code and reid(2) == code):
base += 0.2
if (reid(0) == code and reid(1) == code and reid(2) == code):
base += 0.1
else:
if (reid(3) == code):
base += 0.4
elif (reid(4) == code):
base += 0.2
return base
def total_score():
score = 0
for file in os.listdir("./val_query"):
name_list = image_similarity_ranking(gallery_images, imread("./val_query/" + file), vocabulary, gallery_filenames)
score += match_score(file, name_list)
return score
print(total_score())Get help in K Means Clustering related Projects and Assignments. If you are not expertise to do code from scratch then don't worry. Here you will get quality work with reasonable price.
For more details you can contact us: