Single stroke recognition
Christoph Burgmer
added a tool to automatically extract single stroke handwriting data from the
Japanese and Simplified Chinese models and used the Wagomu recognition engine
for first results. There's still work to do and I didn't run a proper
evaluation yet, but it seems to work OK. Zinnia failed horribly; I believe it
is not designed for recognizing single strokes. Wagomu is quick enough for
this limited set of "characters".
Strokes are position-normalized, but not normalized in size. My rationale is
to enable recognizing strokes when drawing a full character, so size does
matter, while positions vary freely. The current data needs to be improved
which partially needs work on the cjklib side, where stroke type mappings stem
from.
My next steps will be to write a short recognizer abstraction to recognize
single strokes in a Writing object, opposed to recognizing a whole character.
I eventually will add a stroke n-gram model to test if recognition results can
be improved.
I don't know if this project fits into Tegaki. Mathieu, you can just watch and
decide later if you want.
Feel free to chime in if you have any ideas.
-Christoph
Mathieu Blondel
On Wed, Oct 21, 2009 at 8:37 PM, Christoph Burgmer <cbur...@ira.uka.de> wrote:
>
> I started a branch at [1] with support for recognition of single strokes. I
> added a tool to automatically extract single stroke handwriting data from the
Can you confirm if the following is correct? I don't have too much
time to read your changes carefully. Your tool uses the character
stroke decomposition data found in cjklib to find the stroke sequence
corresponding to the character, then assign each stroke found in this
character to its corresponding "stroke pool". In the end, we get a
character collection (actually a stroke collection ;-)) which contains
several samples for each stroke.
How many stroke kinds did you get in the end?
You may have problems if the characters in the training data contain
invalid stroke-number or stroke-order.
> Japanese and Simplified Chinese models and used the Wagomu recognition engine
> for first results. There's still work to do and I didn't run a proper
> evaluation yet, but it seems to work OK. Zinnia failed horribly; I believe it
> is not designed for recognizing single strokes. Wagomu is quick enough for
> this limited set of "characters".
Two ways to speed up wagomu are:
1) compile it with CFLAGS=-"msse -O3" (this enables the SIMD code)
2) use a bigger value of downsample_threshold in the meta file, but
it's quite important to use the same value during training and
evaluation
Another important note is that Wagomu keeps only one instance per
class (here, instances are stroke samples and classes are strokes). So
even if your training character collection contains several stroke
samples per stroke, only one will be kept in the model, which is a
pity.
> I don't know if this project fits into Tegaki. Mathieu, you can just watch and
> decide later if you want.
Let's see how it turns out before putting it in master.
Mathieu
Christoph Burgmer
> You're becoming more active than me, that's cool ;-)
Teh, but I'm totally selfishly working on my stuff :)
> On Wed, Oct 21, 2009 at 8:37 PM, Christoph Burgmer <cbur...@ira.uka.de>
wrote:
> > I started a branch at [1] with support for recognition of single strokes.
> > I added a tool to automatically extract single stroke handwriting data
> > from the
>
> Can you confirm if the following is correct? I don't have too much
> time to read your changes carefully. Your tool uses the character
> stroke decomposition data found in cjklib to find the stroke sequence
> corresponding to the character, then assign each stroke found in this
> character to its corresponding "stroke pool". In the end, we get a
> character collection (actually a stroke collection ;-)) which contains
> several samples for each stroke.
I'll put it more precisely: I take a character from a collection the user
provides, tell cjklib to look up the stroke order (also telling it which
locale we use: Japanese, simplified Chinese...). Then I stupidly assume that
our stroke data match (which they do though for >~85%), and match a single
stroke in Tegaki to a single stroke type in cjklib. I then proof read the
resulting pool, removing some obvious wrong forms and still have pretty many
samples.
> How many stroke kinds did you get in the end?
Limiting to 100 I get from 0 up to 100.
But, cjklib is still at its beginning with stroke order data. I actually
worked my way up to radical 15 or so and the following basic characters still
miss proper data. But here I'm trying the "chicken-egg approach", with Tegaki
suggesting me strokes that I correct and put into cjklib.
> You may have problems if the characters in the training data contain
> invalid stroke-number or stroke-order.
Invalid stroke number is easy to find out, invalid stroke order is not. See my
correction process above.
> > Japanese and Simplified Chinese models and used the Wagomu recognition
> > engine for first results. There's still work to do and I didn't run a
> > proper evaluation yet, but it seems to work OK. Zinnia failed horribly; I
> > believe it is not designed for recognizing single strokes. Wagomu is
> > quick enough for this limited set of "characters".
>
> Two ways to speed up wagomu are:
>
> 1) compile it with CFLAGS=-"msse -O3" (this enables the SIMD code)
> 2) use a bigger value of downsample_threshold in the meta file, but
> it's quite important to use the same value during training and
> evaluation
Well, we are speaking of 36 strokes, so it's pretty quick.
> Another important note is that Wagomu keeps only one instance per
> class (here, instances are stroke samples and classes are strokes). So
> even if your training character collection contains several stroke
> samples per stroke, only one will be kept in the model, which is a
> pity.
Hmm, I feared that, didn't check though. I honestly cannot use Zinnia, at
least I got nearly random results. Maybe another recognition engine will solve
the issue. No time in the foreseeable future though. :(
I doubt that a sample per stroke will ever be enough. In the current situation
I do need to scale the stroke, as stroke size varies over characters. And a
dot and a falling stroke will suddenly look the same.
I could maybe create pseudo strokes and bypass the limit. Won't be the same as
proper variation support though.
-Christoph
Christoph Burgmer
I actually made the Wagomu recognizer handle multiple instances of the same
characters. As all characters in the model file are compared in a row, I though
filling up this flat list with multiple occurences won't do any structural harm.
If double entries are detected search results are first scanned in-place, and
dublicates removed, keeping the one with the minimum distance. Scanning comes
in O(n * log n + n), as I use quicksort just like the result set selection
process right after.
For 36 strokes even the current set with about 40 instances per stroke is
recognized in an instant.
Now for the training process. Am I correct, that I can't pass any parameters
to the engine's training routines? I would like to keep your
_get_representative_writing() method for selecting the best instance, but at
the same time want to allow passing of all or maybe the 10 best instances.
Maybe the selection process can go into tegaki-convert, but then the dtw
routines need to move.
Tell me what you think. I'll upload at least the C++-code I changed. I'm not
too good at C++, so feel free to reorder the stuff I added. I hope extending
Wagomu goes with your design ideas; I believe that for small sets it could
really improve things.
-Christoph
Mathieu Blondel
> I actually made the Wagomu recognizer handle multiple instances of the same
> characters. As all characters in the model file are compared in a row, I though
> filling up this flat list with multiple occurences won't do any structural harm.
> If double entries are detected search results are first scanned in-place, and
> dublicates removed, keeping the one with the minimum distance. Scanning comes
> in O(n * log n + n), as I use quicksort just like the result set selection
> process right after.
Currently you remove the duplicates for all the candidates and then
sort them by score. I wonder it it wouldn't be better to remove the
duplicates after the candidates are sorted by score. You can loop over
the candidates until the Results object contains n unique candidates.
Since we only need the n best unique candidates, you can use linear
search to check if a candidate is already in the Results object.
Another approach to removing duplicates is to add up the
score/distance of each instance and then divide by the number of
instances. In this case you would probably need a hash table where
keys are utf8 and values are score sums. Since I already depend on
glib, it's fine to use the hash table in glib. But it seems like this
approach wouldn't support allographs while your approach seems to.
>
> For 36 strokes even the current set with about 40 instances per stroke is
> recognized in an instant.
On my computer, Wagomu is able to recognize an input character against
the 6000+ characters of KanjiVG in less than 10 msec. In your case,
you have less than 100 classes and strokes are obviously shorter than
full characters so it is sure fast.
> Now for the training process. Am I correct, that I can't pass any parameters
> to the engine's training routines? I would like to keep your
> _get_representative_writing() method for selecting the best instance, but at
> the same time want to allow passing of all or maybe the 10 best instances.
This is something that I was planning to address after release 0.3. We
need to be able to pass trainer specific options to tegaki-build. In
addition, options like normalize_position, normalize_size,
downsample_threshold should be available for all recognizers
(currently only Wagomu uses them). Zinnia doesn't perform
normalization at all. So having an option to enable it can potentially
improve the accuracy.
> Tell me what you think. I'll upload at least the C++-code I changed. I'm not
> too good at C++, so feel free to reorder the stuff I added. I hope extending
> Wagomu goes with your design ideas; I believe that for small sets it could
> really improve things.
As long as it doesn't slow down the recognition process when the model
contains only 1 instance per class, which seems to be the case since
you detect first if the model has duplicates or not, I'm fine with
this change.
By the way, the strokerecognizer that you added ouputs a stroke
sequence given a writing object. If you have 30 stroke classes and a
character has on average 10 strokes, you have 30^10 possible sequences
on average. In practice, this will be smaller than that because some
stroke transitions are very unlikely but still, the number of possible
stroke sequences will be huge. This means that the probability of
mapping a stroke sequence to an actual character will be very small.
You need to use search algorithms which are "guided" with a stroke
tree.
To say the truth, I'm working on a related project but I can't publish
my code now since I may write a paper out of it.
Mathieu
Christoph Burgmer
> On Thu, Oct 22, 2009 at 4:16 AM, Christoph Burgmer <cbur...@ira.uka.de>
wrote:
> > I actually made the Wagomu recognizer handle multiple instances of the
> > same characters. As all characters in the model file are compared in a
> > row, I though filling up this flat list with multiple occurences won't do
> > any structural harm. If double entries are detected search results are
> > first scanned in-place, and dublicates removed, keeping the one with the
> > minimum distance. Scanning comes in O(n * log n + n), as I use quicksort
> > just like the result set selection process right after.
>
> Currently you remove the duplicates for all the candidates and then
> sort them by score. I wonder it it wouldn't be better to remove the
> duplicates after the candidates are sorted by score. You can loop over
> the candidates until the Results object contains n unique candidates.
> Since we only need the n best unique candidates, you can use linear
> search to check if a candidate is already in the Results object.
Hmm, if I understand you correctly we have n*n/2 steps (n-1 + n-2 + ... +2 +
1) for finding duplicates. The code would become easier to read, but for big
input the sorting approach should be quicker.
Your idea to get an average distance from the many character samples is
interesting. Actually we currently have a pretty bad abstraction, comparing to
all samples, as a single wrong sample will provide a false match. A svm
approach, I hope, could average over the given samples. I'll think about
trying an avg distance once I get proper evaluation implemented.
For the combinatorial problem: I thought about user correction from the first
stroke on, this then will be a left to right scanning solution. But this
depends on the use case.
-Christoph
Mathieu Blondel
>
> Hmm, if I understand you correctly we have n*n/2 steps (n-1 + n-2 + ... +2 +
> 1) for finding duplicates. The code would become easier to read, but for big
> input the sorting approach should be quicker.
I guess it also depends on how many duplicates you have. It seems a
waste to remove all the duplicates even though we only need the 10
best unique candidates. But I guess your solution may be better when
there are many duplicates in the best candidates. Likewise, it can
seem a waste to sort all the candidates by score even though we only
need the 10 best. I know that the STL has a partial_sort method. I
wonder if it just sorts all the results and then keeps the n first or
if it's more clever than that.
By the way, does anyone know a (publishable) reference for the number
of distinct stroke kinds? According to
http://unicode.org/charts/PDF/U31C0.pdf, there are 35 but ideally I
would prefer a famous kanji dictionary or a paper.
Thanks
Mathieu
Christoph Burgmer
> By the way, does anyone know a (publishable) reference for the number
> of distinct stroke kinds? According to
> http://unicode.org/charts/PDF/U31C0.pdf, there are 35 but ideally I
> would prefer a famous kanji dictionary or a paper.
I until now only used the Unicode classification and would be interested, if
most classifications actually could fit into a class hierarchy, so that
algorithmic conversion to systems with less classes would be possible.
-Christoph
Roger Braun
>
> I started a branch at [1] with support for recognition of single strokes. I
> added a tool to automatically extract single stroke handwriting data from the
> Japanese and Simplified Chinese models and used the Wagomu recognition engine
> for first results.
Sounds great! Do you think this could help with writing a recognizer
for Korean hangul? Using the standard approach of simply writing all
characters and training zinnia or wagomu with them seems a waste of
time, as there are around 12.000 possible hangul. A real decomposition
of the hangul characters may be a better way to go, but taking single
strokes and then figuring out which character they represent may also
be not too hard.
--
Roger Braun
http://yononaka.de
roger...@student.uni-tuebingen.de
Mathieu Blondel
> Sounds great! Do you think this could help with writing a recognizer
> for Korean hangul? Using the standard approach of simply writing all
> characters and training zinnia or wagomu with them seems a waste of
> time, as there are around 12.000 possible hangul. A real decomposition
> of the hangul characters may be a better way to go, but taking single
> strokes and then figuring out which character they represent may also
> be not too hard.
You need a dictionary which maps characters to their stroke sequences.
Does such free data exist already?
Mathieu
Mathieu Blondel
Instead of removing duplicates or taking the average distance, you can
also use the k-NN algorithm
(http://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm).
Originally this was I intended to use in combination with DTW but for
over 6000 character classes and several instances per class, k-NN is
too expensive. For the stroke approach, this can work though. Several
values of k must be tried to see which one is the best.
Mathieu
Christoph Burgmer
Thanks Mathieu, I was actually about to conduct some research on good
selection algorithms.
I'll try that!
-Christoph
Christoph Burgmer
You could, but I think single stroke recognition might just be too noisy.
I'd rather recommend another approach:
Decompose the Hangul into Jamo:
$ python
Python 2.5.4 (r254:67916, Sep 26 2009, 08:19:36)
[GCC 4.3.4] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import unicodedata
>>> unicodedata.normalize('NFD', u"걠")
u'\u1100\u1164\u11b3'
Then create rules to map those single Jamo to a position in the glyph. You
could now "only" draw 249 Jamo by hand and use the approach of tegaki-
bootstrap to build these into 12.000 models. Not even all Jamos will be needed
for modern Korean if I understand correctly.
-Christoph
Mathieu Blondel
found quite interesting:
http://www.cse.ust.hk/vldb2002/VLDB2002-proceedings/slides/S12P01slides.pdf
Two ideas that are described and could be implemented in Wagomu are:
- the Sakoe-Chiba band (constraint on the path)
- the lower bounding (don't perform the full DTW on items that don't warrant it)
These are ideas to speed up calculations at the cost of possibly
returning incorrect results. This can be useful for mobile phones or
when there are many instances per class.
And for the record, my informal presentation about DTW:
http://www.mblondel.org/journal/2009/08/31/dynamic-time-warping-theory/
Mathieu
Christoph Burgmer
I just commited my implementation of KNN [1]. I came up with a method of doing
incremental KNN recognition, as we need to provide a list of best matches.
It basically just keeps on increasing the number of k starting with a
predefined value (currently k=5). This though assumes that each character in
the set has at least k instances and for good recognition results, also, that
the number of instances is constant for all characters.
So either one needs to add means to cope with varying instance count, or one
makes sure that the instance count is really constant. As I have > 100
instances for strokes, I could kind of guarantee that for say k ~= 20, but how
do I select good representatives?
I need to select good instances either way, or my set grows too big. I though
about clustering, but right now didn't come up with features with which to
cluster the instance sets.
That being said, I do have some better results (compared to [2], F1 score:
45.81):
match1
Accuracy/Recall: 63.61
Precision: 63.38
F1 score: 63.50
match5
Accuracy/Recall: 83.33
match10
Accuracy/Recall: 83.33
And my stroke examples are still pretty bad.
Not sure where to go from here.
-Christoph
[1]
http://github.com/cburgmer/hwr/commit/9522d3dc5c885059a9b298d3932a2980730db480
[2] http://pastebin.ca/1644389
Mathieu Blondel
On 4 nov, 02:05, Christoph Burgmer <cburg...@ira.uka.de> wrote:
> I just commited my implementation of KNN [1]. I came up with a method of doing
> incremental KNN recognition, as we need to provide a list of best matches.
best candidates. k-NN is very straightforward when you need only the
one best.
> It basically just keeps on increasing the number of k starting with a
> predefined value (currently k=5).
the first character that reach k samples, then the second character
that reach k samples etc until n candidates are retrieved.
> This though assumes that each character in
> the set has at least k instances and for good recognition results, also, that
> the number of instances is constant for all characters.
of samples per characters may vary from model to model.
Also, in a database I have (unfortunately not free), the number of
samples per character is not uniform. Some characters have many
samples while others have just a few. In that case requiring k to be
the least-common denominator means that we don't use a lot of our
data. But I guess statistical models are the way to go in that case.
> That being said, I do have some better results (compared to [2], F1 score:
> 45.81):
> match1
> Accuracy/Recall: 63.61
> Precision: 63.38
> F1 score: 63.50
>
> match5
> Accuracy/Recall: 83.33
>
> match10
> Accuracy/Recall: 83.33
>
recognition based on your stroke models?
Did you try how the idea of averaging the distance of all instances
fairs compared to k-NN? This idea is simple, can probably be
implemented more compactly and doesn't suffer the problem of needing
to find representatives. The problem of taking the average is that
outliers can have a bad effect on the average. (k-NN is not robust to
outliers either) One idea I just had is to divide the average by the
ecart-type. This way, instances which don't vary too much will be
favored over instances which vary a lot.
Also you're starting to face problems which lead you to complicated
solutions, because of the shortcomings in Wagomu. The main motivation
for Wagomu was that it's simple and it works even with only 1 instance
per class. When you start to have many instances per class,
statistical models are the way to go. I'm planning to add an HMM-based
recognizer in about 2-3 months. It will solve the problem of finding
instance representatives since an HMM model is the average instance in
a statistical way. Performance-wise, HMMs will be better too. So I
would suggest not too spend too much time on that, although this can
be quite addictive to always try to improve the current state ;-)
Mathieu
Mathieu Blondel
> outliers either) One idea I just had is to divide the average by the
> ecart-type.
Oops, I have just made a francization :-) écart type is French for
standard deviation.
Mathieu
Christoph Burgmer
> On 4 nov, 02:05, Christoph Burgmer <cburg...@ira.uka.de> wrote:
> > I just commited my implementation of KNN [1]. I came up with a method of
> > doing incremental KNN recognition, as we need to provide a list of best
> > matches.
>
> Yeah, when I suggested k-NN, I omitted the fact that we need the n-
> best candidates. k-NN is very straightforward when you need only the
> one best.
>
> > It basically just keeps on increasing the number of k starting with a
> > predefined value (currently k=5).
>
> Why did you decide to increase k? Can't you keep k fixed and retrieve
> the first character that reach k samples, then the second character
> that reach k samples etc until n candidates are retrieved.
I wasn't precise and I think you are having a wrong though :)
When KNN is used, you take the k nearest neighbours, and detect the class
depending on majority of the found instances.
I then just go through the rest of the instance list, starting from the next
nearest neighbour. I only detect a new result, if a class has at least as many
instances as previous results (and especially the first KNN result).
I'll attach an example writing, I hope it goes through the ML. That's not my 5
year old neighbours drawing, its my first atempt to use a wacom board.
To describe my perfect drawing: the middle of circles is a data point we try
to classify (the dtw of a drawn character). The first yellow circle is the
selection from traditional KNN. Yellow wins, first match. By then going through
the list of other neighbours, the black square is the first class to reach the
same instance count as the previously detected yellow triangle. The array
beneath shows the situation of the outer black circle, when the third green
star is found (after k reaches 11). It's in our list already, but doesn't have
the requested instance count of 3 (max of preceding matches). When inserting
the instance we move the entry with count 2 to right after the black square
and by finding out that we reached the maximum count we register a new result.
> > This though assumes that each character in
> > the set has at least k instances and for good recognition results, also,
> > that the number of instances is constant for all characters.
>
> In that case, k should not be a compile-time option since the number
> of samples per characters may vary from model to model.
Agreed, but we need to have a way to specify such a parameter.
> Also, in a database I have (unfortunately not free), the number of
> samples per character is not uniform. Some characters have many
> samples while others have just a few. In that case requiring k to be
> the least-common denominator means that we don't use a lot of our
> data. But I guess statistical models are the way to go in that case.
Yes, one idea is to regard the last found instance of a class as having a
special weight, to fill up the instance count to reach the maximum count of
class instances. For example: green has 2 instances, yellow 4. With k=5 we say
that our result has 2 green instances and 3 yellow next to it. Traditional KNN
would favour yellow, but we'll set the second green instance have weight 3, so
that we reach count 4. In this case, Green wins with "4 instances", while
yellow has only 3.
> > That being said, I do have some better results (compared to [2], F1
> > score: 45.81):
> > match1
> > Accuracy/Recall: 63.61
> > Precision: 63.38
> > F1 score: 63.50
> >
> > match5
> > Accuracy/Recall: 83.33
> >
> > match10
> > Accuracy/Recall: 83.33
>
> Are these results for isolated stroke recognition or whole character
> recognition based on your stroke models?
That's recognition of the strokes from each character. We basically only
recognize 32? strokes by extracting them from the character model.
> Did you try how the idea of averaging the distance of all instances
> fairs compared to k-NN? This idea is simple, can probably be
> implemented more compactly and doesn't suffer the problem of needing
> to find representatives. The problem of taking the average is that
> outliers can have a bad effect on the average. (k-NN is not robust to
> outliers either) One idea I just had is to divide the average by the
> ecart-type. This way, instances which don't vary too much will be
> favored over instances which vary a lot.
No, haven't tried it yet. I'll put it on the list. But probably I first need to
get more stroke models, as some are seriously underrepresented. Only then does
evaluation work.
> Also you're starting to face problems which lead you to complicated
> solutions, because of the shortcomings in Wagomu. The main motivation
> for Wagomu was that it's simple and it works even with only 1 instance
> per class. When you start to have many instances per class,
> statistical models are the way to go. I'm planning to add an HMM-based
> recognizer in about 2-3 months. It will solve the problem of finding
> instance representatives since an HMM model is the average instance in
> a statistical way. Performance-wise, HMMs will be better too. So I
> would suggest not too spend too much time on that, although this can
> be quite addictive to always try to improve the current state ;-)
Sounds good. I had the same though. I'm not a fan of complicated algorithms,
KISS is probably a good principle here. And HMMs does sound good. If you do
implement such a recognizer, make it independent of Tegaki though, similar to
Zinnia.
-Christoph
Mathieu Blondel
> I wasn't precise and I think you are having a wrong though :)
> When KNN is used, you take the k nearest neighbours, and detect the class
> depending on majority of the found instances.
Correct, I was probably not fully awake ;)
> Sounds good. I had the same though. I'm not a fan of complicated algorithms,
> KISS is probably a good principle here. And HMMs does sound good. If you do
> implement such a recognizer, make it independent of Tegaki though, similar to
> Zinnia.
Ideally yes but it's more work... I actually think Wagomu is a good
mix of Python and C++.
Mathieu