Measuring and validating the algorithm

In order to measure the performance and validate the algorithm described in the previous post, I created a validation script (attached below). The code randomly splits the character set in two and evaluates the similarity score. The assumption is that the two subsets of the same script should come out with a good similarity score (0 being identity - same character set). This is done 150 times for each of the scripts and outputs the average score received. The results are displayed below. For comparison, with this algorithm, the lowest similarity score between scripts is ~0.25 (between Thai and Gujarati) and the highest is ~25.24 (between Greek and Telugu).

Telugu: 2.17015555556

Cyrillic: 1.64583333333

Greek: 1.57917647059

Malayalam: 2.70133333333

Thai: 1.98205128205

Latin: 1.80256410256

Gujarati: 2.85166666667

Hebrew: 1.5647985348

Devanagari: 1.81041666667

Arabic: 2.29111111111

Tamil: 4.74801742919

The results are surprisingly good for such a simple algorithm (below 3 with the exception of Tamil). It seems to do better with the "straight - lined" scripts, such as Latin, Greek and Hebrew, than with the "round" scripts such as Tamil, Gujarati and Malayalam. I hope to improve the algorithm in the future, to reach a point where validation scores approach 0.

# -----------------------------------------------------------------------------

#

#  This script was created by Tamar Rucham

#

#  Measures the the algorithm in data_collection and languages_heatmap_results

#

# -----------------------------------------------------------------------------

from freetype import *

from data_collection import CalcChar, scripts

def run(chars, face):

    total_chars, total_contours, total_lines, total_curves = 0,0,0,0

    for singleChar in chars:

        ch = unichr(singleChar)

        contours, lines, curves = CalcChar(ch, face)

        total_chars = total_chars + 1

        total_contours = total_contours + contours

        total_lines = total_lines + lines

        total_curves = total_curves + curves

    return {'evarage_lines': float(total_lines)/float(total_chars), 'evarage_curves': float(total_curves) / float(total_chars)}

if __name__ == '__main__':

    import numpy

    import json

    import copy

    import random

    from languages_heatmap_results import getDiff

    face = Face('data/Arial Unicode.ttf')

    face.set_char_size( 48*64 )

    num_iterations = 150

    for scriptName, charsRange in scripts.items():

        total_diff = 0

        for iteration in range(num_iterations):

            diff = 0

            # Create two random subsets of the characters

            charsSlice1 = copy.deepcopy(charsRange)

            charsSlice2 = []

            for i in range(len(charsRange) / 2):

                # Dynamically get the len of the remaining of the array

                randIdx = random.randint(0, len(charsSlice1) - 1)

                charsSlice2.append(charsSlice1.pop(randIdx))

            slice1 = run(charsSlice1, face)

            slice2 = run(charsSlice2, face)

            total_diff += getDiff(slice1, slice2)

        print scriptName, ': ', (total_diff / float(num_iterations))

First algorithm to compare scripts

As I mentioned in my previous post from the FreeType python library I am able to get vector glyph information such as contours, lines and curves. For the first version of the algorithm for comparing scripts I created a python script to iterate over the character sets and output the average number of lines and curves per char. Then I wrote a second python script to grab that output and for each combination of scripts calculate the difference between them and output into a heatmap readable format. The formula is the total of the difference between average number of lines and average number of curves of the two scripts:

absolute_value(script_1_lines - script_2_lines) + absolute_value(script_1_lines - script_2_lines)

This produces a difference value of 0 between a script and itself and the higher the number - the bigger the difference. Both scripts are included at the bottom.

11 scripts that evolved from the Egypthian Hieroglyphs origin were analyzed in this manner and displayed in a heatmap with a tree relation to the left that demonstrates condensed evolutionary relationships between the scripts.

It is interesting to note that the script families do indeed form similarity "blocks". Though Arabic and Hebrew have more of a shared ancestry with the Brahmi family, it has a better geographical proximity to the Greek related scripts, it may also be related to the time of creation (of the scripts). The goal is to integrate such information in future versions.

The script to extract the data:

# -----------------------------------------------------------------------------

#

#  This script was created by Tamar Rucham, based on the FreeType library example 

#  glyph_vector.py

#

#  Assuming the ttf file and input file in a data folder from currently run script

#  this script will generate the statistics for each character in the given ranges

#  for the given languages, as well as general statistics for the language

#

# -----------------------------------------------------------------------------

from freetype import *

import numpy

# Extend the end of each script by 1 because of how ranges work

scripts = {

    'Latin': range(0x0041,0x005A+1) + range(0x0061, 0x007A+1),

    'Greek': range(0x0391,0x03A9+1) + range(0x03B1, 0x03C9+1),

    'Cryllic': range(0x0410,0x044F+1),

    'Hebrew': range(0x05D0,0x05EA+1),

    'Arabic': range(0x0621,0x063A+1) + range(0x0641, 0x064A+1),

    'Thai': range(0x0E01,0x0E2F+1) + range(0x0E40, 0x0E44+1),

    'Tamil': range(0x0B85,0x0B8A+1) + range(0x0B8E, 0x0B90+1) + range(0x0B92, 0x0B95+1)

            + range(0x0B99, 0x0B9A+1) + range(0x0BA3, 0x0BA4+1) + range(0x0BA8, 0x0BAA+1) + range(0x0BAE, 0x0BB9+1),

    'Malayalam': range(0x0D05,0x0D0C+1) + range(0x0D0E, 0x0D10+1) + range(0x0D12, 0x0D3A+1),

    'Telugu': range(0x0C05,0x0C0C+1) + range(0x0C0E, 0x0C10+1) + range(0x0C12, 0x0C28+1)

             + range(0x0C2A, 0x0C33+1) + range(0x0C35, 0x0C39+1),

    'Gujarati': range(0x0A85,0x0A8D+1) + range(0x0A8F, 0x0A91+1) + range(0x0A93, 0x0AA8+1) + range(0x0AAA, 0x0AB0+1)

             + range(0x0AB2, 0x0AB3+1) + range(0x0AB5, 0x0AB9+1),

    'Devanagari': range(0x0904,0x0939+1) + range(0x0958, 0x0961+1)

}

def CalcChar(singleChar, face):

    face.load_char(singleChar)

    slot = face.glyph

    outline = slot.outline

    points = numpy.array(outline.points, dtype=[('x',float), ('y',float)])

    x, y = points['x'], points['y']

    start, end = 0, 0

    lines, curves1, curves2 = 0, 0, 0

    # Iterate over each contour

    for i in range(len(outline.contours)):

        end    = outline.contours[i]

        points = outline.points[start:end+1] 

        points.append(points[0])

        tags   = outline.tags[start:end+1]

        tags.append(tags[0])

        segments = [ [points[0],], ]

        for j in range(1, len(points) ):

            segments[-1].append(points[j])

            if tags[j] & (1 << 0) and j < (len(points)-1):

                segments.append( [points[j],] )

        for segment in segments:

            if len(segment) == 2:

                lines+=1

            elif len(segment) == 3:

                curves1+=1

            else:

                # as reference - inner curves for complex curves

                for i in range(1,len(segment)-2):

                    A,B = segment[i], segment[i+1]

                    C = ((A[0]+B[0])/2.0, (A[1]+B[1])/2.0)

                curves2+=1

        start = end+1

    return len(outline.contours), lines, (curves1 + curves2)

if __name__ == '__main__':

    import json

    face = Face('data/Arial Unicode.ttf')

    face.set_char_size( 48*64 )

    languages_arr = []

    for scriptName, charsRange in scripts.items():

        print scriptName

        language_dic = {"language": scriptName, "chars": []}

        total_chars, total_contours, total_lines, total_curves = 0,0,0,0

        for i in charsRange:

            ch = unichr(i)

            contours, lines, curves = CalcChar(ch, face)

            total_chars = total_chars + 1

            total_contours = total_contours + contours

            total_lines = total_lines + lines

            total_curves = total_curves + curves

            char_dic = {"char": ch.encode('utf-8'), "contours": str(contours),

                        "lines": str(lines),"curves": str(curves)}

            language_dic["chars"].append(char_dic)

        total_chars = float(total_chars)

        language_dic["total_chars"] = total_chars

        language_dic["total_contours"] = total_contours

        language_dic["evarage_contours"] = (total_contours/total_chars)

        language_dic["total_lines"] = total_lines

        language_dic["evarage_lines"] = (total_lines/total_chars)

        language_dic["total_curves"] = total_curves

        language_dic["evarage_curves"] = (total_curves / total_chars)

        languages_arr.append(language_dic)

    outputFile = open('data/output.json','w')

    outputFile.write('{\n"languages":')

    outputFile.write(json.dumps(languages_arr,indent=4))

    outputFile.write('}')

    outputFile.close()

The script to calculate the heatmap data:

import json

def getDiff(char1, char2):

return (abs(float(char1['evarage_lines']) - float(char2['evarage_lines'])) + abs(float(char1['evarage_curves']) - float(char2['evarage_curves'])))

# def generateCharJson():

inputFile = open('data/output.json')

data = json.load(inputFile)

inputFile.close()

names_arr = []

data_arr = []

languages_data = []

maxData = 0

languages_info = data['languages']

row_index = 0

for language1 in languages_info:

lang1_name = language1['language']

names_arr.append(lang1_name)

row_arr = []

col_index = 0

# Now iterate through the rest of the chars and determine link weight

for language2 in languages_info:

lang2_name = language2['language']

weight = 0 if lang1_name == lang2_name else getDiff(language1, language2)

if weight > maxData: maxData = weight

row_arr.append([weight, row_index, col_index])

col_index += 1

data_arr.append(row_arr)

lang_data_dict = {lang1_name:[]}

for char in language1['chars']:

lang_data_dict[lang1_name].append(char['char'])

languages_data.append(lang_data_dict)

row_index += 1

outputFile = open('data/languages_heatmap.json', 'w')

outputFile.write('{\n"labels":')

outputFile.write(json.dumps(names_arr,indent=4))

outputFile.write(',\n"data":')

outputFile.write(json.dumps(data_arr,indent=4))

outputFile.write(',\n"languages_data":')

outputFile.write(json.dumps(languages_data,indent=4))

outputFile.write(',\n"minData":0')

outputFile.write(',\n"maxData":{}'.format(maxData))

outputFile.write('\n}')

Starting to explore the vector glyph information

I started exploring the freetype-py library and the vector information available for glyphs. As part of the exploration I found this great unicode characters table. In addition to the character code and the writing system it belongs to, this table also shows the areas of the world where the writing system is used. This can be very useful to the third layer of the visualization regarding the history / geography of writing systems.

I started by looking at the glyph-vector example provided with the library. Note that this example uses matplotlib to plot the glyph. The glyph information is initially divided into closed contours - closed lines, for example the letter O has two contours, the outer circle and the inner circle while the letter S has only one contour. The closed contours are in turn divided into segments that can be either a straight line or a quadratic Bezier curve (or curves). A clear and concise description of the outlines and how the control points define the line in TrueType can be found here.

Below are a few examples of characters from different writing systems with their control lines (dashed). These are of course just single characters and therefore do not represent the entire writing system to which they belong. This is only meant to show the type of information available, the great variance between the writing systems and how these parameters can be used to asses similarity. 

These are characters from the Chinese character set, Latin, Hebrew and Tibetan (from left to right respectively). The statistics for each character is as follows:

Writing System	Chinese	English	Hebrew	Tibetan
Closed contours	7	2	1	9
Total segments	57	17	12	58
Straight lines	47	11	8	9
Curves	9	6	4	49

The code is below. Note that it relies on having matplotlib and the path to the ttf file.

# coding=UTF8

# -----------------------------------------------------------------------------
#
#  FreeType high-level python API - Copyright 2011 Nicolas P. Rougier
#  Distributed under the terms of the new BSD license.
#
# -----------------------------------------------------------------------------
'''
Show how to access glyph outline description.
'''
from freetype import *

if __name__ == '__main__':
    import numpy
    import matplotlib.pyplot as plt
    from matplotlib.path import Path
    import matplotlib.patches as patches

    face = Face('path/to/file/Arial Unicode.ttf')
    face.set_char_size( 48*64 )
    face.load_char(u'\u0F03')
    slot = face.glyph

    outline = slot.outline
    points = numpy.array(outline.points, dtype=[('x',float), ('y',float)])
    x, y = points['x'], points['y']

    figure = plt.figure(figsize=(8,10))
    axis = figure.add_subplot(111)
    #axis.scatter(points['x'], points['y'], alpha=.25)
    start, end = 0, 0
    lines, curves1, curves2 = 0, 0, 0

    VERTS, CODES = [], []
    # Iterate over each contour
    for i in range(len(outline.contours)):
        end    = outline.contours[i]
        points = outline.points[start:end+1] 
        points.append(points[0])
        tags   = outline.tags[start:end+1]
        tags.append(tags[0])

        segments = [ [points[0],], ]

        for j in range(1, len(points) ):
            segments[-1].append(points[j])
            if tags[j] & (1 << 0) and j < (len(points)-1):
                segments.append( [points[j],] )
        verts = [points[0], ]
        codes = [Path.MOVETO,]
        for segment in segments:
            if len(segment) == 2:
                verts.extend(segment[1:])
                codes.extend([Path.LINETO])
                lines+=1
            elif len(segment) == 3:
                verts.extend(segment[1:])
                codes.extend([Path.CURVE3, Path.CURVE3])
                curves1+=1
            else:
                verts.append(segment[1])
                codes.append(Path.CURVE3)
                for i in range(1,len(segment)-2):
                    A,B = segment[i], segment[i+1]
                    C = ((A[0]+B[0])/2.0, (A[1]+B[1])/2.0)
                    verts.extend([ C, B ])
                    codes.extend([ Path.CURVE3, Path.CURVE3])
                verts.append(segment[-1])
                codes.append(Path.CURVE3)
                curves2+=1
        VERTS.extend(verts)
        CODES.extend(codes)
        start = end+1
    
    print 'segments: ', len(outline.contours)
    print 'lines: ', lines
    print 'curves: ', curves1+curves2

    # Draw glyph lines
    path = Path(VERTS, CODES)
    glyph = patches.PathPatch(path, facecolor='.75', fill=False, lw=1)

    # Draw "control" lines
    for i, code in enumerate(CODES):
        if code == Path.CURVE3:
            CODES[i] = Path.LINETO
    path = Path(VERTS, CODES)
    patch = patches.PathPatch(path, ec='.5', fill=False, ls='dashed', lw=1 )

    axis.add_patch(patch)
    axis.add_patch(glyph)

    axis.set_xlim(x.min()-100, x.max()+100)
    plt.xticks([])
    axis.set_ylim(y.min()-100, y.max()+100)
    plt.yticks([])
    plt.show()

Setup Mountain Lion with the freetype-py library

Today wanted to start exploring how I'm going to create a generic representation of a character based on the fonts information. However since I have changed my laptop I need to get the framework setup again, so I'll describe the process here for future use.

I have a mountain lion mac (which I love), running v10.8.4. In order to run the freetype-py library, the freetype library needs to be installed, which in turn requires GNU Make. freetype-py is a python binding to the freetype library that is written in C. Since I don't want to write this in C unless I have to, I'll see if I can get everything I need from freetype-py. If not I may take a look at the Ruby binding for freetype: ft2-ruby.

So the steps were:

1. Download GNU Make and run the configuration file. 
2. Download FreeType.
3. From the root of the freetype folder run the following commands (as described in this post):

./configure
make
sudo make install

4. Download FreeType-py.
5. From the freetype-py root directory run:

   python setup.py build
   python setup.py install

   To verify the system is setup correctly try entering the python shell and run:

   import freetype

   If no error occurs the installation of freetype and freetype-py was successful.
6. Next I wanted to also install matplotlib so I can run the example I was interested in. For that I followed the installation steps describe here.
7. Finally I was able to run the glyph-vector examples that display the use of outlines in the library!

Well, that only took way too many hours...

Meeting with Alex on Aug 7

We discussed mainly the need to focus the tasks this visualization will enable. There are so many directions this can take and so much information this data represents that without first defining the tasks it is extremely hard to decide on a direction. So here is a first run:

1. Determine strongest visual themes of different writing systems
2. Make a visual comparison between writing systems
3. Find story behind above connection - historical / geographical

Based on this, I'm thinking on the main page described above with an emphasis on visual themes and not just space distributions. A connected graph that defines the resemblance of writing systems and a third layer, that is to be determined that exposes the story behind.

First steps

Starting from the two projects done as part of cs-171 visualization class, I was trying to define what it is that I want to do for my thesis. With Hanspeter guidance I started thinking of the tasks I want to enable in the visualization and came up with:

• What are the visual themes of a given writing system?
• How visually similar are different systems?
• What are the connections between the similarity level of writing systems and their geographical and historical proximity?

Then I met with Alex and with his help I started thinking of how to give form to the data that can help answer the research questions. A few important notes that came up in the meeting were:

• Establish contact with domain experts
• font selection and does the system break with font change?
• visualization of poetry reference: http://www.cs.utah.edu/~miriah/publications/poem-viewer13.pdf

In parallel I was working with Jeff in order to complete my Thesis proposal and have it approved. This included summarizing the previous projects, investigating some of the technical aspects of the implementation and of course, above all, trying to design the project.

I have had several views in mind - a connected graph and a map of the world were the main ones. I realized that the space distribution view is effective for visual comparison and decided to use it as well. However this view represented spoken languages and I will want to combine them into writing systems. To this I wished to add sorting and filtering.

Sorting by:

Convexity

Density

Segmentation

Number of spoken languages

Filtering by:

Geography (continent)

History (time of writing system creation)

(add images)

I was thinking of the transition between the visualizations and decided a tabbed layout makes most sense.

(add images)

As for the main view, the space distribution did not necessarily provide a strong sense of the visual themes of a given writing system (example Thai) so I am trying to find a better way of capturing it. I'm currently focusing on the idea of curve fitting (either based on the space dist. or using the contours provided by the glyph library.

I have issues gathering the information for the history and geography layers - it is too fuzzy and not  well structured enough for scripting. How do I determine the geography of a given script? Do I manually enter the time period for each language?