Find the closest vector
- by Alexey Lebedev
Hello!
Recently I wrote the algorithm to quantize an RGB image. Every pixel is represented by an (R,G,B) vector, and quantization codebook is a couple of 3-dimensional vectors. Every pixel of the image needs to be mapped to (say, "replaced by") the codebook pixel closest in terms of euclidean distance (more exactly, squared euclidean).
I did it as follows:
class EuclideanMetric(DistanceMetric):
def __call__(self, x, y):
d = x - y
return sqrt(sum(d * d, -1))
class Quantizer(object):
def __init__(self, codebook, distanceMetric = EuclideanMetric()):
self._codebook = codebook
self._distMetric = distanceMetric
def quantize(self, imageArray):
quantizedRaster = zeros(imageArray.shape)
X = quantizedRaster.shape[0]
Y = quantizedRaster.shape[1]
for i in xrange(0, X):
print i
for j in xrange(0, Y):
dist = self._distMetric(imageArray[i,j], self._codebook)
code = argmin(dist)
quantizedRaster[i,j] = self._codebook[code]
return quantizedRaster
...and it works awfully, almost 800 seconds on my Pentium Core Duo 2.2 GHz, 4 Gigs of memory and an image of 2600*2700 pixels:(
Is there a way to somewhat optimize this? Maybe the other algorithm or some Python-specific optimizations.
