In [60]:
%matplotlib inline

import matplotlib.pyplot as plt
import numpy as np

from skimage import measure
from scipy import interpolate
from numpy import fft

import networkx as nx

from pandas import read_csv, DataFrame
import sklearn
from sklearn.neighbors import KNeighborsClassifier
from sklearn import preprocessing

from sklearn.model_selection import train_test_split

from sklearn import metrics

In [ ]:


In [61]:
path = '/Users/calebignace/etsu-thesis-s17/TrainingSet/'

In [62]:
class Transform:
    #points = np.array([]) # (x,y) points
    def __init__(self, curve):
                # complex representation:
        complex_curve = curve[0] + 1j*curve[1] 
        self.transform = np.abs(fft.fft(complex_curve))
    
    def Plot():
        plt.plot(self.transform)
        plt.yscale('log')
        plt.axis('equal')

In [230]:
class Contour:
    #(x,y) points
    #Area enclosed by the points
    def __init__(self, curve, points):
        self.contour = self.Interpolate(curve, points)
        self.centroid = [np.average(self.contour[0]), np.average(self.contour[1])]
        self.area = self.Area()
    
    # Use Green's theorem to compute the area 
    # enclosed by the given contour.
    def Area(self):
        # vs - vertices/points on closed curve                                                                  
        a = 0
        x0, y0 = self.contour[0][0], self.contour[1][0]
        #for [x1, y1] in vs[1:]:
        for i in range(1,len(self.contour[0])):
            xi = self.contour[0][i]
            yi = self.contour[1][i]
            dx = xi - x0
            dy = yi - y0
            a += 0.5*(y0*dx - x0*dy)
            x0 = xi
            y0 = yi
        return a
    
    def Interpolate(self,curve, points):
        x = curve[:,1]
        y = curve[:,0]
        tck, u = interpolate.splprep([x, y], s=0)
        unew = np.arange(0, 1.0001, 1.0001/points)
        return interpolate.splev(unew, tck)
    
    def Plot(self):
        plt.plot(self.contour[0],self.contour[1])
        plt.plot(self.centroid[0], self.centroid[1], 'b*', markersize=10)

In [224]:
class Character:
    """
    image_path               - File path to image
    image                    - The actual image
    original_image_contours  - A list of Contour objects that we found in the image
    original_areas
    reduced_image_contours   - A list of Contour objects that met requirements
    reduced_areas
    image_transforms         - A list of the reduced_image_contours's Transform objects
    classification           - What we have classified this object's respective image as
    """
    def __init__(self, image_path, classification = None):
        self.classification = classification
        self.image_path = image_path
        self.image = plt.imread(self.image_path)
        self.original_contours = [Contour(contour, points = 2**8) for contour in 
            measure.find_contours(self.image, level = 0.5, fully_connected = 'high')]
        self.original_areas = [contour.area for contour in self.original_contours]
        self.largest_area = np.max(np.abs(self.original_areas))
        self.reduced_contours, self.reduced_areas = self.RemoveInsignificantContours()
        self.largest_area_index = self.reduced_areas.index(self.largest_area)
        self.transforms = [Transform(contour.contour) for contour in self.reduced_contours]
        self.centroids = [contour.centroid for contour in self.reduced_contours]
        self.ordinals = self.Ordinals()
        
    def Ordinals(self):
        epsilon = 1
        ordinals = [[0, 0] for i in self.reduced_contours]
        for i in range(len(self.reduced_contours)):
            for j in range(len(self.reduced_contours)):
                if i != j:
                    print(type())
                    centroid1 = self.reduced_contours[i].centroid
                    centroid2 = self.reduced_contours[j].centroid
                    print(centroid1)
                    print(centroid2)
                    if centroid1[0] > centroid2[0] + epsilon:
                        ordinals[i][0] += 1
                        print(1)
                    if centroid1[1] > centroid2[1] + epsilon:
                        ordinals[i][1] += 1
                        print(2)
                input()
        return ordinals
                    
        
    def in_hull(p, hull):
        """
        Test if points in `p` are in `hull`

        `p` should be a `NxK` coordinates of `N` points in `K` dimensions
        `hull` is either a scipy.spatial.Delaunay object or the `MxK` array of the 
        coordinates of `M` points in `K`dimensions for which Delaunay triangulation
        will be computed
        """
        from scipy.spatial import Delaunay
        if not isinstance(hull,Delaunay):
            hull = Delaunay(hull)

        return hull.find_simplex(p)>=0
        
    def RemoveInsignificantContours(self):
        contours_copy = self.original_contours.copy()
        contours_to_delete = []
        j = 0
        while j < len(contours_copy):
            if np.abs(contours_copy[j].area) < 0.10*self.largest_area: 
                del contours_copy[j]
            else: j += 1    
        return [contours_copy, [contour.area for contour in contours_copy]]
    
    def PlotImage(self):
        plt.imshow(self.image, cmap = 'gray')
    
    def PlotOriginalContours(self):
        for contour in self.original_contours:
            contour.Plot()
        plt.axis('equal')
    
    def PlotReducedContours(self):
        for contour in self.reduced_contours:
            contour.Plot()
        plt.axis('equal')
            
    def PlotImageAndOriginalContours(self):
        self.PlotImage()
        self.PlotOriginalContours()
    
    def PlotImageAndReducedContours(self):
        self.PlotImage()
        self.PlotReducedContours()

In [6]:
def GenerateClassifications(N):
    digits = ['0','1','2','3','4','5','6','7','8','9']
    digits = list(np.sort(N*digits))
    lower_letters = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
    lower_letters = list(np.sort(N*lower_letters))
    upper_letters = [char.upper() for char in lower_letters]
    return digits + upper_letters + lower_letters

In [7]:
def GetImagePaths(folder_path, M, N):
    image_paths = []
    for i in range(0, 62):
        if i < 10:
            si = '0'+str(i)
        else:
            si = str(i)
        for j in range(M, M+N):
            image_paths.append(folder_path+si+'/'+si+'-'+(5 - len(str(j)))*'0'+str(j)+'.png')
    return image_paths

In [8]:
def CreateDataSet(M, N, folder_path = '/Users/calebignace/etsu-thesis-s17/TrainingSet/'):
    """
    Caleb Ignace
    Febuary 1, 2017
    
    | Inputs:
    =====================
    *folder_path      *M - start at image M      *N - include N images
    
    | Outputs:
    =====================
    *dataset - A list of Character objects.
    
    
    | Notes:
    =====================
    Refering to the file structure of the data set in the folder TrainingSet:
        A directory below TrainingSet are folders for each character (0,1,...,9,A,B,...,Z,a,b,...,z), labeled 
        00,01,...,61. For images of the digit "0" (zero), the paths will be 
        "TrainingSet/00/00-00001.png",
        "TrainingSet/00/00-00002.png",
                    ...
        "TrainingSet/00/00-00100.png".
        The other folders 01 through 61 follow the same structure.
    The images of each character that are includes are M,M+1,...,M+N-1.
    (1) If N = 2, then image_classifications = ['0', '0', '1', '1', ... , 'z', 'z'] and its length is 62*N = 124.
    (2) A list of Strings that contain the file path of each image in data set.
    """
    #image_classifications = GenerateClassifications(N)                  # (1)
    image_paths = GetImagePaths(folder_path, M, N)                       # (2)
    dataset = [Character(image_path) for image_path in image_paths]             
    return dataset

k-Nearest Neighbors Classifier


In [9]:
def TransformsInASingleList(transforms_arrays): # 124 enteries of 256 points
    #print(transforms_arrays)
    transforms = np.zeros( (len(transforms_arrays[0]),len(transforms_arrays)) )
    #print(transforms.shape)
    for i in range(len(transforms_arrays)):
        #print(len(transforms[:,i]))
        #print(len(transforms_arrays[i]))
        a =  transforms_arrays[i]
        transforms[:,i] = a
        #input()
        #break
    return transforms

In [10]:
class KNN:
    def __init__(self, k_neighbors):
        self.k_neighbors = k_neighbors
        self.kNN = KNeighborsClassifier(n_neighbors = self.k_neighbors, metric='euclidean')
        
    def Fit(self, data_train, N_train):
        self.data_train = data_train
        self.N_train = N_train
        self.kNN.fit(self.data_train.T, self.data_train.columns)
        #self.distances, self.neighbors = self.kNN.kneighbors(data_train.T)
        
    def Predict(self, data_test, N_test, image_classifications_test):
        self.N_test = N_test
        
        predictions = self.kNN.predict(data_test.T)
        
        accuracies = []
        result = 'Symbol   Accuracy   Predictioned as'

        truth = predictions == image_classifications_test

        digits = ['0','1','2','3','4','5','6','7','8','9']
        lower_letters = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
        upper_letters = [char.upper() for char in lower_letters]
        symbols = digits + upper_letters + lower_letters
        
        for i in range(62):
            f = i*N_test
            l = (i+1)*self.N_test
            accuracies.append(np.sum([1 for p in truth[f:l] if p])/N_test)
            result += "\n" + str(symbols[i]) + "        " + '{0:.3f}'.format(float(round(accuracies[i], 3))) + "      " + str(''.join(predictions[f:l]))      
            
        accuracy = np.sum(accuracies)/len(accuracies)
        
        predictions_upper = [p.upper() for p in predictions]
        image_classifications_test_upper = [c.upper() for c in image_classifications_test]

        truth = [predictions_upper[i] == image_classifications_test_upper[i] for i in range(len(predictions_upper))]

        real_accuracy = np.sum(truth)/len(truth)
        
        head = "Accuracy: " + str(accuracy) + "\nReal Accuracy: " + str(real_accuracy) + "       (example: 'W' is equivalent to 'w')\n"
    
        result = head + result
        
        return accuracy, real_accuracy, result
    
    def Plot(self, figuresize = (15,15), save = False, labels = True, vertex_size = 300, vertex_color = "cyan", font_size = 10):
        # NOTE TO SELF: When I start to actually test agains real scene images, N_train will not longer apply at (1)
        kNNadjacencies = self.kNN.kneighbors_graph()     
        kNNgraph = nx.Graph( kNNadjacencies )
        nx.relabel_nodes(kNNgraph, dict(zip(range(62*self.N_train),self.data_train.columns)), copy=False ) # (1)
        plt.figure(figsize = figuresize)
        nx.draw(kNNgraph, node_color = vertex_color, with_labels = labels, node_size = vertex_size)
        plt.title('nodes labeled classification', fontsize = font_size)
        if save: plt.savefig("graph.pdf")

In [11]:
def RunKNN(k_neighbors, M_train, N_train, M_test, N_test):
    
    training_set = CreateDataSet(M = M_train, N = N_train)
    transforms_train = [character.transforms[character.largest_area_index] for character in training_set] 
    image_classifications_train = GenerateClassifications(N_train)
    trans = [transform.transform for transform in transforms_train]
    transforms_curves_train = TransformsInASingleList(trans)
    transforms_train = DataFrame(transforms_curves_train, columns = image_classifications_train)
    #transforms_train.head()
    
    testing_set = CreateDataSet(M = M_test, N = N_test)
    transforms_test = [character.transforms[character.largest_area_index] for character in testing_set] 
    image_classifications_test = GenerateClassifications(N_test)
    transforms_curves_test = TransformsInASingleList([transform.transform for transform in transforms_test])
    transforms_test = DataFrame(transforms_curves_test, columns = image_classifications_test)
    #transforms_test.head()
    
    #accuracies = [0]*number_runs
    #real_accuracies = [0]*number_runs
    #results = []
    
    #for run in range(number_runs):
    kNN = KNN(k_neighbors)
    kNN.Fit(transforms_train, N_train)
    accuracy, real_accuracy, result = kNN.Predict(transforms_test, N_test, image_classifications_test)
    
    return accuracy, real_accuracy, result

Trainig set: for every character, will start at file number M_train and take N_train files.

Testing set: for every character, will start at file number M_test (M_train + 1) and take N_test files.


In [12]:
accuracy, real_accuracy, result = RunKNN(k_neighbors = 2, M_train = 1, N_train = 1, M_test = 1 + 1, N_test = 2)

In [13]:
accuracy, real_accuracy


Out[13]:
(0.50806451612903225, 0.62096774193548387)

In [14]:
print(result)


Accuracy: 0.508064516129
Real Accuracy: 0.620967741935       (example: 'W' is equivalent to 'w')
Symbol   Accuracy   Predictioned as
0        1.000      00
1        0.500      1I
2        1.000      22
3        1.000      33
4        1.000      44
5        0.000      22
6        1.000      66
7        1.000      77
8        0.500      08
9        1.000      99
A        1.000      AA
B        0.500      OB
C        0.500      C3
D        0.000      O0
E        0.500      6E
F        0.500      FE
G        1.000      GG
H        1.000      HH
I        1.000      II
J        0.000      99
K        1.000      KK
L        1.000      LL
M        1.000      MM
N        0.000      HH
O        0.500      O0
P        1.000      PP
Q        0.500      QB
R        1.000      RR
S        1.000      SS
T        0.000      PF
U        0.000      nR
V        1.000      VV
W        0.500      MW
X        1.000      XX
Y        1.000      YY
Z        1.000      ZZ
a        1.000      aa
b        1.000      bb
c        0.000      aC
d        1.000      dd
e        0.000      a9
f        0.500      fT
g        0.000      99
h        0.000      44
i        1.000      ii
j        0.000      ii
k        0.000      b5
l        0.000      II
m        0.000      GG
n        1.000      nn
o        0.000      QO
p        0.000      DP
q        0.000      Qp
r        0.000      77
s        0.000      SS
t        0.000      bL
u        0.000      nn
v        0.500      vV
w        0.000      WW
x        0.000      XX
y        0.000      YY
z        0.000      8Z

In [ ]:


In [15]:
def ManyRuns(rangeK, M_train, N_train, M_test, N_test):
    
    print("Building data sets")
    
    training_set = CreateDataSet(M = M_train, N = N_train)
    transforms_train = [character.transforms[character.largest_area_index] for character in training_set] 
    image_classifications_train = GenerateClassifications(N_train)
    trans = [transform.transform for transform in transforms_train]
    transforms_curves_train = TransformsInASingleList(trans)
    transforms_train = DataFrame(transforms_curves_train, columns = image_classifications_train)
    #transforms_train.head()
    
    testing_set = CreateDataSet(M = M_test, N = N_test)
    transforms_test = [character.transforms[character.largest_area_index] for character in testing_set] 
    image_classifications_test = GenerateClassifications(N_test)
    transforms_curves_test = TransformsInASingleList([transform.transform for transform in transforms_test])
    transforms_test = DataFrame(transforms_curves_test, columns = image_classifications_test)
    
    accuracies = [0]*len(rangeK)
    real_accuracies = [0]*len(rangeK)
    results = []
    
    for i in range(len(rangeK)):
        print("Running on k = "+str(rangeK[i]))
        kNN = KNN(rangeK[i])
        kNN.Fit(transforms_train, N_train)
        accuracies[i], real_accuracies[i], result = RunKNN(rangeK[i], M_train, N_train, M_test, N_test)
        results.append(result)
        
    return accuracies, real_accuracies, results

In [ ]:
rangeK = [1,2,3]#list(range(1,10)) # Note k cannot be creater than 62*N_train
accuracies, real_accuracies, results = ManyRuns(rangeK, M_train = 1, N_train = 900, M_test = 901, N_test = 100)


Building data sets

In [43]:
print(results[0])


Accuracy: 0.826451612903
Real Accuracy: 0.871935483871       (example: 'W' is equivalent to 'w')
Symbol   Accuracy   Predictioned as
0        0.680      000000000000oo00o00O0O000000oo0000Oo000oo00000o00oOO00000000O0O0O0O0O0O0O0O000000000Q0ooX8QX0000O00O
1        0.820      11111111111111rr111111111111bb111111111111111111111111111111ll11ll11ll11ll11111111111q71yyQV11111111
2        0.950      22222222222222222222222222222g22222222222222222222222222sS222222222222222222222222225522222222222222
3        0.920      3333333333333333333333333333trlF33333333333333333333333333333333333333333333333333333333SSVV33333333
4        0.920      444444444444hhWW444444444444444444444444444444444444444444444444444444444444444444444b444uzA44444444
5        0.890      5555555555555555555555555555gggg555S55555555555555555555555555555555555555555555555s5S5533VV55555555
6        0.830      6666666666666666666966666666996666669666666666666666666666669666966696669666696666661bp7VVQN66666666
7        0.920      7777777777777777777777777777777777777777777777777777777777777777777777777777777777771111SmCC77777777
8        0.930      88888888888888888888888888888888888888888888888888888888888888888888888888888888888866668NNN88888888
9        0.880      9999999999999999999999999999bp669999999999999999999999999999999999999999999999999999mm5zNNXz99999999
A        0.850      AAAAAAAaAAAAkkkkAAAAAAAAAAAAddddAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAvvAANNzQAAAAAAAA
B        0.830      BBBBBBBBBBBBLLssBB8BBBBBBBBBhhhhBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBFFF8TJMVBBBBBBBB
C        0.720      CcCcCCccCCCcccCCCcCCCCCCCCcCeeeCCcCcCCCCCcCcCCCCCCCCCcCcCCCCCcCCCcCCCcCCCcCCCcCcCCCCCCCCVmNNCCCCCCCC
D        0.840      DDDDDDDDDDDD99ssDDDDDDDDDDDDeebbDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDeqeqOSyVDDDDDDDD
E        0.880      EEEEEEEEEEEECCCCEEEEEEEEEEEE3339EEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEmmEEEEVVEEEEEEEE
F        0.870      FFFFFFFFFFFFWWVVFFFFFFFFFFFFLLffFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFfFFFCGVVFFFFFFFF
G        0.810      GcGcGGCcGGGGccccGGGGGGGGGGGGGnu2GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGccvkVmNNGGGGGGGG
H        0.890      HHHHHHHHHHHHqqkkHHHHHHHHHHHHz2zhHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHxMWHHHHHHHH
I        0.850      IIIIIIIIIIIl99ccIIIIIIIIIIIIL9LgIIIIIIIIIIIIIIIIIIIIIIIIIkllIIIIIIIIIIIIIIIIIIIIIIIIIJIIIIyyIIIIIIII
J        0.840      JJJJJJJJJJJJvvVVJJJJJJJJJJJJJJLJCclJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJJ77llKKyyJJJJJJJJ
K        0.890      KKKKKKKKKKKKzzHHKKKKKKKKKKKKHpKfKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKKUUQQKKKKKKKK
L        0.840      LLLLLLLLLLLLAAAALlLLLLLLLLLLihhhLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL11JLJ622LLLLLLLL
M        0.790      MWMWMWMWMMMMmmmmMMmMMMMMMMMMFFw3MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMKAuHVI33MMMMMMMM
N        0.920      NNNNNNNNNNNNNNNNNNNNNNNNNNNNMgggNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNIIyyNNNNNNNN
O        0.450      O0O0O00OOOoo99LLOO0ooOoOOoOOGGceooOooOOooooOOOOOOOOOoOoOOoOO0000O0000000O000OOOoOoOoQogomXNNOOOOOOOO
P        0.860      PPPPPPPPPPPPPPssPPPPPPPPPPPPnun4PPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPbopbtFNMPPPPPPPP
Q        0.850      QQQQQQQQQQQQ22RRQQQQQQQQQQQQBGGGQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ1qbQX8NNQQQQQQQQ
R        0.850      RRRRRRRRRRRRyyaaRRRRRRRRRRRRrr44RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRt1tRtwVZRRRRRRRR
S        0.700      SsSsSsSsSSSS3333SSzZSSSSSSSSIIIISsSsSsSsSSSsSSSSSSSSSSSSsSSSSSSSSSSSSSSSSSSSSSSSSsssSs5s88VVSSSSSSSS
T        0.890      TTTTTTTTTTTTPPTTTTTTTTTTTTTT77VVTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTppTTT9mmTTTTTTTT
U        0.850      UUUUUUUUUUUURRvvUuUUUUUUUUUUUUMgUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUhhnnTDQyUUUUUUUU
V        0.740      VVVVVVVvVVVVvvvvVvvvVvVvVVVVlqvvVvVvVVVVVVvVVvVvVVVVVVvVVVVVVVVVVVVVVVVVVVVVVVVvVVVVVVvVyyXQVVVVVVVV
W        0.730      WWWWWWWWWWWWwwwwWWWWWwWWwwwwzzmwWWwWWWWWWwWWWWWWWWWWWWWWWWWWWWWwWWWwWWWwWWWwWWWWWMWMmwWWy8XXWWWWWWWW
X        0.760      XXXXXXxXXXXXxxxxXXXxXxXXXXXXkkAkXXXXXXXXXxXxXXXXXXXXXXXXXxXxXXXXXXXXXXXXXXXXXXxXXXXXkk11QQQNXXXXXXXX
Y        0.860      YYYYYYYYYYYYhhyyYYYYYYYYYYYYYYyrYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYyyyyMMQVYYYYYYYY
Z        0.730      ZZZZZZZZZZZZWWttZzZZZZZZZZZZNNNxzzzZZzZzZzZzZZZZZZZZZZzZZZZZZZZZZZZZZZZZZZZZZZZZZzZz2222Sm22ZZZZZZZZ
a        0.880      aaaaaaaaaaaa44aaaaagaaaaaaaaaaaQaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaahAhAYYNNaaaaaaaa
b        0.870      bbbbbbbbbbbbbbIIbbbbbbbbbbbbqqb4bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbLIl9IUyQbbbbbbbb
c        0.610      ccccccccccccbbhhCcCCCccCcccceeeCCCCCcCccccccccCcccccCcCcccCcCCccCCccCCccCCcccccccCcceeneX8NNcccccccc
d        0.930      ddddddddddddAAddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddAdddUUQVdddddddd
e        0.870      eeeeeeeeeeeebbGGeeeeeeeeeeeeeee9eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeqqLQKUKKeeeeeeee
f        0.870      ffffffffffffyyAAfffffffffffffffFffffffffffffffffffffffffffffffffffffffffffffffffffffkl99TnVVffffffff
g        0.840      ggggggggggggppbbgggggggggggg9999ggggggggggggggggggggggggggggggggggggggggggggggggggggft11iiXXgggggggg
h        0.890      hhhhhhhhhhhhkkhhhhhhhhhhhhhhhhhehhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhbmb6KUQQhhhhhhhh
i        0.950      iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiijiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiAAXViiiiiiii
j        0.910      jjjjjjjjjjjjiijjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjiijiLLQyjjjjjjjj
k        0.880      kkkkkkkkkkkkkkkkkkkkkkkkkkkkuuaakkkkkRkRkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkknkhkKUzQkkkkkkkk
l        0.820      l7l7llllllllLLLLllllllllllllQQ11lllllllllllllllllllllllllllllllllllllllllllll1lIllllJJlJlkyyllllllll
m        0.910      mmmmmmmmmmmmttttmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmmrmmmUU88mmmmmmmm
n        0.800      nnnnnnnnnnunwwMMnnnnnnnnnnnnuuuunnnnnnnnnnuunnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnunnnnnWwwwVINNnnnnnnnn
o        0.600      ooooooooooOoppqqoooOOoooooooooOOOO0O0ooOoOOoooooooooOoooooooOoOo0oOoOoOo0oOooOooOOOO4QbQX8NNooooOooo
p        0.840      ppppppppppppWWhhpppPpppppppppprpppppppppppppppppppppppppppppppppppppppppppppppppppPPgfgtIIVVpppppppp
q        0.840      qqqqqqqqqqqqKKKKqqqqqqqqqqqqbbVVqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqNzN1UYXXqqqqqqqq
r        0.870      rrrrrrrrrrrrWWrrrrrrrrrrrrrr7rpPrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrHuuhIIQNrrrrrrrr
s        0.690      ssssssssssssLLddssZZsSsSsssssSssssssssssssssssssssssssssSsSsSsSSSsSSSsSSSsSSssssssssuuhh888Vssssssss
t        0.850      ttttttttttttqqxxttttttttttttoPPPttttttttttttttttttttttttttttttttttttttttttttttttttttk4tfKwVVtttttttt
u        0.840      ununuunuuuuuuuuuuuuuuunuuuuunuuuuunuuuuuuuuuuuuuuuuuuunuuuuuuuuuuuuuuuuuuuuuuunuuuuuaWhWYYzzuuuuuuuu
v        0.680      vvvvvvvvvvvv7711vvvvvVvvVvvvVvv7VvvvvvvvvvvVvvvvvvvvvvvvvvVvVVVVVvVVVVVVVvVVvvvvvvvvPevByyVVvvvvvvvv
w        0.840      wwwwwwwwwwwwmmmmwwwwwWwWWwWwwwwwwwWwwwwwwWwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww4tww88yzwwwwwwww
x        0.830      xXxXxxxxxxxxxxxxxxxxxxxxXxXxxxxXxxxxxxxxxXxXxxxxxxxxxxxxxXxXxxxxxxxxxxxxxxxxxxxxxxxxkkMMQQ8Qxxxxxxxx
y        0.880      yyyyyyyyyyyyKKFFyyyYyyyyyyyyyPy7yyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyyzyyYzy88yyyyyyyy
z        0.620      zzzzzzzzzzzzkkuuzzZZzzzzzzzznNHHzZzZzzzzzZzzzzzzzzzzzzZzzzzzZZZZZZZZZZZZZZZZzzzzzzzzgtygZZVVzzzzzzzz