In [ ]:
In [1]:
using Images
In [2]:
img=load("files/Indore.jpg")
Out[2]:
In [3]:
img=map(Gray,img)
Out[3]:
In [4]:
# Extract the matrix
A=float(img)
Out[4]:
In [5]:
sort(A[:])
Out[5]:
In [6]:
# Truncate small elements (0 is black, 1 is white)
sum(A.>0.2)
Out[6]:
In [7]:
A.*=(A.<=0.2)
Out[7]:
In [8]:
sum(A.>0), prod(size(A))
Out[8]:
In [9]:
colorview(Gray,A)
Out[9]:
In [10]:
# Increase the contrast for clustering
A=ones(size(A)).*map(Float64,A.>0)
Out[10]:
In [11]:
colorview(Gray,rotl90(A))
Out[11]:
In [12]:
# Create the data points from letters
X=Array{Int}(undef,2,sum(A.==1))
Out[12]:
In [13]:
ind=findall(A.==1)
Out[13]:
In [14]:
ind=findall(A.==1)
for i=1:length(ind)
X[:,i]=[ind[i][1],ind[i][2]]
end
X=map(Float64,X)
Out[14]:
In [15]:
# import Pkg; Pkg.add("Clustering")
In [16]:
# Solve it
using Clustering
In [17]:
out=kmeans(X,6)
Out[17]:
For plotting we use the function from the notebook K-means Algorithm.
In [21]:
function plotKmeansresult(out::KmeansResult,X::Array)
k=size(out.centers,2)
# Clusters
scatter(X[1,findall(out.assignments.==1)],X[2,findall(out.assignments.==1)])
for j=2:k
scatter!(X[1,findall(out.assignments.==j)],
X[2,findall(out.assignments.==j)],markersize=1)
end
# Centers
scatter!(out.centers[1,:],out.centers[2,:],markercolor=:black)
end
Out[21]:
In [22]:
using Plots
In [23]:
plotKmeansresult(out,X)
Out[23]:
Now we try the spectral $k$-partitioning. We:
In [24]:
# Now some functions
using SparseArrays
using LinearAlgebra
function my_weight_matrix(src::Array,dst::Array,weights::Array)
n=nv(G)
sparse([src;dst],[dst;src],[weights;weights],n,n)
end
my_laplacian(W::AbstractMatrix)=spdiagm(0=>vec(sum(W,dims=2)))-W
function my_normalized_laplacian(L::AbstractMatrix)
D=1.0./sqrt.(diag(L))
n=length(D)
[L[i,j]*(D[i]*D[j]) for i=1:n, j=1:n]
end
Out[24]:
In [25]:
function plotKpartresult(C::Vector,X::Array)
k=maximum(C)
# Clusters
scatter(X[1,findall(C.==1)],X[2,findall(C.==1)])
for j=2:k
scatter!(X[1,findall(C.==j)],X[2,findall(C.==j)])
end
scatter!()
end
Out[25]:
In [26]:
# import Pkg; Pkg.add("Distances")
In [27]:
using Distances
S=pairwise(SqEuclidean(),X,dims=2)
# S=pairwise(Cityblock(),X)
β=1
Out[27]:
In [28]:
# Weight matrix
W=exp.(-β*S)
# Sum of weights
D=vec(sum(W,dims=2))
# Laplacian matrix
L=my_laplacian(W)
# Normalized Laplacian matrix
Ln=my_normalized_laplacian(L)
Out[28]:
In [29]:
# Normalized Laplacian
using Arpack
k=6
m=size(L,1)
λ,Y=eigs(Ln,nev=k,which=:SM, v0=ones(m))
λ
Out[29]:
In [30]:
Y=Diagonal(1.0./sqrt.(D))*Y
out=kmeans(Y',k)
plotKpartresult(out.assignments,X)
Out[30]: