Title: Color Descriptors Author: Thomas Breuel Institution: UniKL
from pylab import *
import tables
from collections import Counter
def crop_black(image):
gray = image
if gray.ndim==3: gray = sum(image,axis=2)
yr = find(sum(gray,axis=1)>0)
y0 = yr[0]
y1 = yr[-1]
xr = find(sum(gray,axis=0)>0)
x0 = xr[0]
x1 = xr[-1]
if image.ndim==3: return image[y0:y1,x0:x1,:]
else: return image[y0:y1,x0:x1]
hdf = tables.openFile("1k.h5","r")
image = crop_black(hdf.root.icons[60]/255.0)
imshow(image)
<matplotlib.image.AxesImage at 0x336b810>
pixels = image.reshape(-1,3)
from scipy.cluster.vq import kmeans,vq
centers,_ = kmeans(pixels,8)
palettized,_ = vq(pixels,centers)
imshow(palettized.reshape(image.shape[:2]),cmap=cm.spectral)
<matplotlib.image.AxesImage at 0x3804f10>
quant = centers[palettized].reshape(image.shape)
subplot(121); imshow(quant)
subplot(122); imshow(image)
<matplotlib.image.AxesImage at 0x3c4a990>
quant = centers[numpy.sort(palettized)].reshape(image.shape)
subplot(121); imshow(quant)
subplot(122); imshow(image)
<matplotlib.image.AxesImage at 0x3e92790>
from collections import Counter
counts = Counter(palettized)
[(centers[c],n) for c,n in counts.most_common(100)]
[(array([ 0.21777742, 0.52941719, 0.32857721]), 8672), (array([ 0.75221995, 0.6000601 , 0.40396081]), 7864), (array([ 0.0094247 , 0.33484434, 0.53066996]), 7347), (array([ 0.05656605, 0.48873567, 0.3034896 ]), 5201), (array([ 0.20373189, 0.378372 , 0.34389597]), 5091), (array([ 0.57252269, 0.30912692, 0.18218118]), 3143), (array([ 0.06442288, 0.19430474, 0.2356602 ]), 2918), (array([ 0.35297821, 0.56341501, 0.48379856]), 2859)]
def color_descriptor(image,k=8):
image = crop_black(image)
total = 1.0*prod(image.shape[:2])
if amax(image)>1: image = image/255.0
pixels = image.reshape(-1,3)
pixels = pixels[sum(pixels,axis=1)>0.01]
centers,_ = kmeans(pixels,k)
palettized,_ = vq(pixels,centers)
counts = Counter(palettized)
return [(centers[c],n/total) for c,n in counts.most_common(k)]
color_descriptor(hdf.root.icons[1])
[(array([ 0.42162644, 0.57817704, 0.57616437]), 0.22676470588235295), (array([ 0.33697095, 0.49405299, 0.47145013]), 0.21987745098039216), (array([ 0.53563625, 0.67073403, 0.67544354]), 0.1482843137254902), (array([ 0.27099995, 0.34549485, 0.36266592]), 0.10313725490196078), (array([ 0.74400308, 0.76799886, 0.77709715]), 0.095171568627450978), (array([ 0.73263741, 0.50180797, 0.56723781]), 0.087818627450980388), (array([ 0.19987478, 0.09595162, 0.19616403]), 0.060588235294117644), (array([ 0.63098088, 0.33157494, 0.38071008]), 0.058357843137254901)]
Fast palettizers:
Matching Color Descriptors:
optimal solution:
other solutions:
Let's compute descriptors for the database.
descriptors = [color_descriptor(hdf.root.icons[i]) for i in range(len(hdf.root.icons))]
Now we define a simple match function. This accumulates positive scores for color vectors that are not too distant from another, proportional to the number of pixels that may match between the clusters.
def cdmatch(desc1,desc2,delta=0.25):
delta2 = delta**2
total = 0.0
for v,p in desc1:
for w,q in desc2:
d = maximum(1-norm(v-w)**2/delta2,0)
total += d * minimum(p,q)
return total
Note that matches are not normalized.
print cdmatch(descriptors[1],descriptors[1])
print cdmatch(descriptors[1],descriptors[2])
1.53552189807 0.345921690125
To normalize matches, we divide by the maximum of the two self-similarities. We also turn the match score into a dissimilarity score.
def cddissim(desc1,desc2,delta=0.25):
score = cdmatch(desc1,desc2,delta)
score1 = cdmatch(desc1,desc1,delta)
score2 = cdmatch(desc2,desc2,delta)
return 1-score/max(score1,score2,1e-6)
With this dissimilarity score, we can now perform fairly quick matching.
scores = [cddissim(descriptors[5],descriptors[i]) for i in range(100)]
print scores[:8]
argsort(scores)
[0.39887869140269039, 0.46623600194604276, 0.73968197869845431, 0.6674964755602687, 0.63788109223564049, 0.0, 0.45286671204188356, 0.99977751751444344]
array([ 5, 47, 59, 49, 98, 38, 57, 96, 80, 43, 24, 12, 83, 73, 0, 35, 39, 91, 45, 26, 30, 88, 6, 74, 1, 37, 69, 33, 9, 10, 46, 97, 71, 28, 75, 53, 18, 16, 22, 89, 85, 13, 20, 61, 54, 50, 95, 4, 93, 34, 66, 82, 3, 79, 77, 86, 17, 94, 8, 90, 84, 78, 2, 92, 42, 76, 11, 60, 65, 72, 68, 23, 48, 55, 56, 40, 81, 63, 70, 32, 52, 99, 36, 19, 87, 51, 62, 14, 64, 29, 15, 58, 27, 25, 21, 44, 67, 31, 41, 7])
Now let's perform some searches.
scores = [cddissim(descriptors[5],descriptors[i]) for i in range(100)]
for i,j in enumerate(argsort(scores)[:6]):
subplot(1,6,i+1); axis("off"); imshow(hdf.root.icons[j]); title("%d %.2f"%(j,scores[j]))
In evaluating matches, it's important to keep match statistics in mind. Scores below 0.3 are probably significant, the rest random.
subplot(121); hist(scores)
subplot(122); plot(sorted(scores)[:30])
[<matplotlib.lines.Line2D at 0x532d2d0>]
scores = [cddissim(descriptors[22],descriptors[i]) for i in range(100)]
for i,j in enumerate(argsort(scores)[:6]):
subplot(1,6,i+1); axis("off"); imshow(hdf.root.icons[j]); title("%d %.2f"%(j,scores[j]))
scores = [cddissim(descriptors[60],descriptors[i]) for i in range(100)]
for i,j in enumerate(argsort(scores)[:6]):
subplot(1,6,i+1); axis("off"); imshow(hdf.root.icons[j]); title("%d %.2f"%(j,scores[j]))
subplot(121); hist(scores)
subplot(122); plot(sorted(scores)[:30])
[<matplotlib.lines.Line2D at 0x48ec550>]
h,w,_ = image.shape
scale = 3.0
rs,cs = mgrid[:h,:w]*scale/max(h,w)
augmented = array(list(transpose(image,[2,0,1]))+[rs,cs])
augmented = transpose(augmented,[1,2,0])
apixels = augmented.reshape(-1,5)
apixels[:10]
array([[ 0.75294118, 0.59607843, 0.3254902 , 0. , 0. ], [ 0.67843137, 0.54509804, 0.26666667, 0. , 0.01176471], [ 0.58431373, 0.45882353, 0.23529412, 0. , 0.02352941], [ 0.64313725, 0.49411765, 0.24313725, 0. , 0.03529412], [ 0.74509804, 0.59607843, 0.34901961, 0. , 0.04705882], [ 0.73333333, 0.58039216, 0.3254902 , 0. , 0.05882353], [ 0.73333333, 0.57254902, 0.31764706, 0. , 0.07058824], [ 0.74901961, 0.59607843, 0.3372549 , 0. , 0.08235294], [ 0.73333333, 0.58039216, 0.32156863, 0. , 0.09411765], [ 0.74901961, 0.6 , 0.34901961, 0. , 0.10588235]])
acenters,_ = kmeans(apixels,64)
apalettized,_ = vq(apixels,acenters)
imshow(apalettized.reshape(image.shape[:2]))
<matplotlib.image.AxesImage at 0x59b2f50>
aquant = acenters[apalettized].reshape(h,w,5)
subplot(121); imshow(aquant[:,:,:3])
subplot(122); imshow(image)
<matplotlib.image.AxesImage at 0x46b5f90>
counts = Counter(apalettized)
[(acenters[c],n) for c,n in counts.most_common(100)]
[(array([ 0.19681423, 0.51303416, 0.27892056, 1.35085506, 0.15875076]), 967), (array([ 0.17816504, 0.5449806 , 0.30430534, 1.81916326, 1.048229 ]), 935), (array([ 0.19113421, 0.53632099, 0.27921738, 1.79421907, 0.15476673]), 925), (array([ 0.1838273 , 0.45701987, 0.3694109 , 1.01844127, 1.64925421]), 910), (array([ 0.14767457, 0.42216691, 0.3247347 , 0.98503865, 0.17610376]), 898), (array([ 0.23191193, 0.51675841, 0.43463094, 1.17887128, 2.13223689]), 886), (array([ 0.20091459, 0.52552143, 0.30282183, 1.28857659, 0.54897946]), 877), (array([ 0.16244344, 0.42517025, 0.3378765 , 0.96633758, 0.53672014]), 862), (array([ 0.37447228, 0.58103012, 0.5152641 , 1.21967352, 2.44372361]), 832), (array([ 0.23824491, 0.5415321 , 0.29381007, 1.61525375, 0.76450404]), 815), (array([ 0.00472711, 0.34875913, 0.57525505, 0.15003256, 2.72327617]), 814), (array([ 0.196916 , 0.52961026, 0.31183733, 1.30248366, 0.92810458]), 814), (array([ 0.13132673, 0.5379495 , 0.29083761, 1.83875262, 1.44577093]), 813), (array([ 0.17912993, 0.39446934, 0.35245459, 0.89689261, 1.2731175 ]), 808), (array([ 0.16096145, 0.43739021, 0.32906734, 0.99213226, 0.9066647 ]), 803), (array([ 0.06870988, 0.50846509, 0.2895966 , 1.82400899, 1.82050206]), 785), (array([ 0.09406184, 0.50252391, 0.32454151, 1.80129366, 2.17013926]), 773), (array([ 0.77934265, 0.6190191 , 0.35523473, 0.15217325, 0.5183382 ]), 761), (array([ 0.10597499, 0.32499099, 0.42008131, 0.68465339, 0.83625135]), 760), (array([ 0.24935072, 0.55335506, 0.29675617, 1.59841689, 0.40686016]), 759), (array([ 0.19569202, 0.50631576, 0.32816376, 1.19404715, 1.25692802]), 753), (array([ 0.19647216, 0.38715909, 0.36336194, 0.87657296, 1.9134735 ]), 747), (array([ 0.01521253, 0.32753783, 0.491591 , 0.66341887, 1.53321753]), 744), (array([ 0.02937718, 0.27744167, 0.40734296, 0.6582329 , 0.16802618]), 737), (array([ 0.75468646, 0.59477479, 0.32148349, 0.13964403, 0.17219251]), 735), (array([ 0.00395358, 0.35125517, 0.57268774, 0.44132853, 2.23747099]), 734), (array([ 0.17340737, 0.55659988, 0.29914434, 1.86917196, 0.57888469]), 730), (array([ 0.0343714 , 0.35557753, 0.52195309, 0.57731092, 1.90217499]), 716), (array([ 0.01368923, 0.31215798, 0.49718015, 0.46394444, 2.66347586]), 702), (array([ 0.70858475, 0.54845216, 0.34149671, 0.37672341, 0.91488286]), 701), (array([ 0.00334251, 0.22522073, 0.36855865, 0.65636395, 2.84508084]), 685), (array([ 0.01935986, 0.2977105 , 0.44312572, 0.65885813, 0.51266436]), 681), (array([ 0.81420479, 0.66580683, 0.42750327, 0.13831808, 1.1927146 ]), 674), (array([ 0.0118359 , 0.36026816, 0.58401115, 0.13318501, 2.30189552]), 659), (array([ 0.02222222, 0.28269028, 0.41250565, 0.62309569, 1.15993494]), 652), (array([ 0.03525136, 0.3977338 , 0.6255635 , 0.18286604, 1.97707532]), 644), (array([ 0.06393012, 0.44965488, 0.34457883, 1.76479751, 2.88420377]), 642), (array([ 0.76074667, 0.59367529, 0.34827922, 0.12079059, 0.84871529]), 628), (array([ 0.64955835, 0.49037148, 0.3432876 , 0.21473407, 1.698271 ]), 626), (array([ 0.02580078, 0.30684863, 0.45689725, 0.65906824, 2.37735529]), 626), (array([ 0.26260436, 0.50844129, 0.42444423, 1.52637943, 2.64291335]), 613), (array([ 0.67493043, 0.53053129, 0.30446515, 0.40823141, 0.17037468]), 606), (array([ 0.2128963 , 0.40009105, 0.3334569 , 1.37594381, 2.87117354]), 603), (array([ 0.73426332, 0.66211427, 0.57268559, 1.42206614, 1.42772412]), 602), (array([ 0.71534371, 0.40950703, 0.28244429, 1.52054419, 1.47565822]), 599), (array([ 0.68955556, 0.54054248, 0.3308366 , 0.42270588, 0.53133333]), 599), (array([ 0.1712857 , 0.35877089, 0.34010396, 0.88304382, 2.24135413]), 596), (array([ 0.45243332, 0.38097737, 0.26998957, 0.40294622, 1.62252043]), 583), (array([ 0.72763109, 0.5868692 , 0.38048731, 0.38901009, 1.27472729]), 578), (array([ 0.35939301, 0.63455072, 0.50537766, 1.80937084, 2.42825575]), 575), (array([ 0.09117303, 0.19867905, 0.19916065, 0.97141383, 2.88526316]), 574), (array([ 0.24471687, 0.44699701, 0.39855087, 1.14272175, 2.69727001]), 572), (array([ 0.13132049, 0.26976922, 0.25999653, 0.86086413, 2.57713691]), 563), (array([ 0.66360294, 0.21565023, 0.09209919, 1.41020761, 1.95480104]), 547), (array([ 0.68984917, 0.50511312, 0.40515083, 1.48174208, 1.79843891]), 523), (array([ 0.12645716, 0.51162273, 0.39598634, 1.84344423, 2.65320594]), 511), (array([ 0.61287737, 0.43754279, 0.31092437, 1.55424837, 1.12455649]), 502), (array([ 0.75857843, 0.61362271, 0.41049178, 0.103463 , 1.51257116]), 498), (array([ 0.60853903, 0.28620083, 0.16753858, 1.52946089, 2.35439027]), 481), (array([ 0.30719613, 0.12672495, 0.05067417, 1.51699511, 2.06199437]), 397), (array([ 2.21515633e-03, 2.20964494e-01, 3.73630101e-01, 2.42130366e-01, 2.93096979e+00]), 369), (array([ 0.41746688, 0.14852146, 0.06794913, 1.36286169, 1.63758347]), 368), (array([ 0.73583693, 0.73351058, 0.62274288, 0.29581256, 2.50176138]), 354), (array([ 0.79281289, 0.64345798, 0.67128799, 0.37616444, 2.04767111]), 269)]