Notes about speech processing, 1.9.201
Hexagonal lattice quantization
Disclaimer 1: This is my attempt at understanding lattice quantization, which is something I’ve struggled with for years. I’m pretty confident that what I say is correct, but there is well-established theory about lattices (see references below), so I might be ignorant about important parts of that.
Disclaimer 2: Conversion of Jupyter to medium failed with the latex symbols, so the math below is distorted, but I think the point is still comprehensible, so I decided to publish this already now and sort it out later.
In quantization, we would like to map input scalars $\xi$ to a discrete set of quantized values, $\hat \xi_k\in S$, such that the quantization error energy $|\xi — \hat\xi_k|²$ is minimized. The set of quantization values can be infinite, but generally we assume that it is at least enumerable. We can further assume without restriction to generality that the quantization levels are sorted $\xi_k < \xi_{k+1}$, such that (for uniformly distributed $\xi$) the optimal bin borders are half-way between the bin centers, $b_k = \frac12\left(\hat \xi_k + \hat \xi_{k+1}\right)$.
The more interesting case and the focus of this note is the 2-dimensional scenario. We can naturally quantize the two dimensions independently to get a square grid (see below). However, a honeycomb lattice gives a smaller (optimal) mean square error.
What I found confusing for a long time was the actual quantization process. What would be a simple way to decide which hexagonal bin a sample $\xi$ belongs to? One approach which I find simple to comprehend is to embed the 2D data into a 3D space, quantize in the 3D space into cubes with uniform quantization, and then convert back to 2D. In the code below, I will walk through this process step by step.
Though before going to the quantization, we can look at the actual bins. Square bins are easy to generate, just draw straight vertical and horizontal lines. Equivalently, we can make a grid of bin-centers, and draw Voroni-lines around them, since this will be useful for the hexagonal bins.
The bin-centers for hexagonal bins can then be created by a neat little matrix multiplication. Specifically, if you have uniform grid points in a matrix $\begin{bmatrix}x\y\end{bmatrix}$, then you can convert them to the corresponding hexagonal grid by matrix multiplication as $\begin{bmatrix}1&\frac12\0&\frac{\sqrt3}{2}\end{bmatrix}\begin{bmatrix}x\y\end{bmatrix}$. Then we get bin-borders again with the Voronoi-function.
from scipy.spatial import Voronoi, voronoi_plot_2d
import numpy as np
import matplotlib.pyplot as plt
# visualize a square grid
x = np.arange(0,144,1) // 12
y = np.arange(0,144,1) % 12
x = np.expand_dims(x,1)
y = np.expand_dims(y,1)
points = np.concatenate((x,y),axis=1)
vor = Voronoi(points)
voronoi_plot_2d(vor,show_vertices=False)
plt.xlim([.5, 9.5])
plt.ylim([.5, 9.5])
plt.title('A square grid')
plt.gca().set_aspect('equal', adjustable='box')
plt.show()
# visualize hexagonal grid
xh = x
A = np.array([[1, 0],[0.5, np.sqrt(3)/2]])
xy = np.concatenate((xh-y//2,y),axis=1) # offset by y//2 makes the plot square - otherwise a tilted area would be plotted
points = np.matmul(xy,A)
vor = Voronoi(points)
voronoi_plot_2d(vor,show_vertices=False)
plt.xlim([.5, 9.5])
plt.ylim([.5, 9.5])
plt.title('A hexagonal grid')
plt.gca().set_aspect('equal', adjustable='box')
plt.show()
First we create a 3D-square by tracing the edges. Then we rotate that square with some arbitrary orthogonal rotation $P$.
import matplotlib.pyplot as plt
import numpy as np
# Trace edges of square
x = [
[0,0,0],
[0,0,1],
[0,1,1],
[0,1,0],
[0,0,0],
[0,0,1],
[1,0,1],
[1,0,0],
[0,0,0],
[0,1,0],
[1,1,0],
[1,0,0],
[0,0,0],
[1,0,0],
[1,1,0],
[1,1,1],
[1,0,1],
[1,1,1],
[0,1,1]]
# Rotation matrix
P = np.eye(3)
t = .1
c,s = np.cos(t*np.pi*2), np.sin(t*np.pi*2)
P = np.matmul(P,np.array([[c,s,0],[-s,c,0],[0,0,1]]))
t = .4
c,s = np.cos(t*np.pi*2), np.sin(t*np.pi*2)
P = np.matmul(P,np.array([[1,0,0],[0,c,s],[0,-s,c]]))
t = -.3
c,s = np.cos(t*np.pi*2), np.sin(t*np.pi*2)
P = np.matmul(P,np.array([[c,0,s],[0,1,0],[-s,0,c]]))
# Rotate
y = np.matmul(x,P)
# Visualize
plt.plot(y[:,0],y[:,1])
plt.title('Projection of 3D box in 2D')
plt.gca().set_aspect('equal', adjustable='box')
plt.show()
If we then rotate it just right, then we see that the outline of the box is a hexagon.
# Rotation matrix
P = np.array([[2**-.5,0,2**-.5],[-(6**-.5),1.5**-.5,6**-.5],[-(3**-.5),-(3**-.5),(3**-.5),]])
# Rotate
y = np.matmul(x,np.transpose(P))
# Visualize
plt.plot(y[:,0],y[:,1])
plt.title('Projection of 3D box in 2D such that the outline is a hexagon')
plt.gca().set_aspect('equal', adjustable='box')
plt.show()
This means that if we quantize in this 3D space with uniform quantization, its projection to the original space will follow a hexagon lattice.
Conversely, if we start with a 2D space, extend it by a zero, we can then do an backwards rotation to the quantization space. In the quantization space we quantize (sic) with uniform quantization and rotate back to the 2D space.
We can then create a grid in 3D space and map it to 2D to verify that this is indeed a hexagonal grid.
s = np.expand_dims(np.arange(0,1000,1),axis=1)
xh = np.concatenate((s % 10, (s//10)%10, (s//100)%10),axis=1) # grid
points = np.matmul(xh,np.transpose(P))
vor = Voronoi(points[:,0:2])
voronoi_plot_2d(vor,show_vertices=False)
plt.xlim([2,8])
plt.ylim([2,8])
plt.title('A hexagonal grid')
plt.gca().set_aspect('equal', adjustable='box')
plt.show()
Now we can take some random data in the 2D space, map it to 3D, quantize, and map it back to 2D.
xh = np.random.randn(10000,2)*4
y = np.matmul(xh,P[0:2,:])
yh = np.round(y)
xq = np.matmul(yh,np.transpose(P[0:2,:]))
plt.plot(xq[:,0],xq[:,1],'.')
plt.xlim([-5,5])
plt.ylim([-5,5])
plt.gca().set_aspect('equal', adjustable='box')
plt.title('Data quantized to hexagonal grid')
plt.show()
That works nicely — the hexagonal grid is visible for the quantized points. Final step is enumeration, that is, each quantization bin needs a unique identifier. However, we already showed a mapping between a square and a hexagonal grid with the matrix $\begin{bmatrix}1&\frac12\0&\frac{\sqrt3}{2}\end{bmatrix}\begin{bmatrix}x\y\end{bmatrix}$, so now we can just take its scaled inverse to obtain the desired enumeration.
xq_indices = np.matmul(xq[:,0:2],np.transpose(A))*(2**.5)
plt.plot(xq_indices[:,0],xq_indices[:,1],'.')
plt.xlim([-5,5])
plt.ylim([-5,5])
plt.show()
This is exactly an integer grid, which can be directly enumerated with its 2D coordinates.
