Recognition of hand drawn digits

[BasicCoder2]

This is a FreeBasic conversion of the first attempt I made using the c64 at writing a program to recognize things drawn with a touch tablet. In this conversion you use the mouse and I have added buttons to make easier than using the keyboard.

The program demonstrates a simple template algorithm to learn to recognize the digits 0 to 9 drawn with a single stroke. First it asks you to draw each digit one at a time and it converts the resulting list of coordinates to a fixed length (template) list of 50 angles. Then it goes into the recognition phase where it asks you to draw one of the digits using a single stroke and searching the templates for the best match. If it gets it wrong it will ask you to click the button with the correct digit.

Run this program to get an idea of how the strokes are drawn using the mouse.

Code: Select all

screenres 640,480,32
color rgb(0,0,0),rgb(255,255,255):cls

sub thickLine(x1 As Integer,y1 As Integer,x2 As Integer,y2 As Integer,size As Integer,c As UInteger)
    dim as integer x,y
  if x1 = x2 and y1 = y2 then
      circle (x1, y1), size, c, , , , f        
  elseif abs(x2 - x1) >= abs(y2 - y1) then
    dim K as Single = (y2 - y1) / (x2 - x1)
    for I as Integer = x1 To x2 step sgn(x2 - x1)
        x = I
        y = K * (I - x1) + y1
        circle (x,y), size, c, , , , f
    next I
  else
    dim L as Single = (x2 - x1) / (y2 - y1)
    for J as Integer = y1 To y2 step sgn(y2 - y1)
        x = L * (J - y1) + x1
        y = J
        circle (x,y), size,c,,,,f
    next J
  end if
end sub

dim as integer x1,y1,x2,y2

dim as integer segmentCount
for j as integer = 0 to 9 'for each stroke
    cls
    locate 2,2
    print "Draw the digit ";str(j)
    read segmentCount
    read x1,y1

    for i as integer = 1 to segmentCount-1
        read x2,y2
        if x2<>0 then
            thickline (x1,y1,x2,y2,2,rgb(0,0,255))
            sleep 50
            x1 = x2
            y1 = y2
        end if
    next

    sleep 500
next j
    
'stroke 0
DATA  37
DATA  232, 139, 222, 144, 213, 150, 201, 160, 193, 167, 181, 182, 175, 191
DATA  168, 208, 165, 218, 165, 232, 168, 244, 178, 261, 185, 269, 197, 279
DATA  204, 283, 215, 287, 224, 288, 239, 288, 247, 287, 263, 284, 282, 276
DATA  291, 272, 299, 268, 307, 262, 320, 251, 328, 239, 334, 219, 335, 208
DATA  334, 195, 333, 187, 327, 176, 320, 169, 309, 159, 301, 152, 289, 143
DATA  280, 139, 272, 137

'stroke 1
DATA  14
DATA  254, 115, 253, 130, 252, 140, 252, 155, 252, 165, 252, 178, 252, 187
DATA  251, 200, 250, 209, 250, 221, 250, 233, 250, 245, 250, 257, 248, 265


'stroke 2
DATA  29
DATA  234, 133, 238, 126, 248, 117, 255, 113, 267, 109, 275, 107, 292, 108
DATA  303, 111, 310, 117, 315, 126, 318, 144, 319, 159, 320, 179, 320, 191
DATA  315, 210, 308, 221, 296, 239, 287, 249, 272, 262, 262, 270, 250, 278
DATA  242, 283, 252, 285, 263, 284, 277, 284, 293, 284, 313, 283, 327, 283
DATA  342, 282

'stroke 3
DATA  34
DATA  241, 118, 248, 113, 256, 110, 271, 106, 280, 105, 295, 105, 305, 105
DATA  319, 108, 327, 113, 331, 124, 332, 135, 328, 153, 323, 163, 313, 178
DATA  307, 187, 296, 196, 288, 200, 298, 203, 314, 212, 323, 219, 335, 230
DATA  341, 238, 344, 248, 343, 261, 334, 272, 328, 278, 314, 285, 301, 289
DATA  280, 291, 269, 291, 253, 286, 246, 281, 238, 272, 233, 264

'stroke 4
DATA  29
DATA  368, 190, 360, 191, 352, 193, 342, 193, 323, 195, 309, 196, 300, 197
DATA  285, 198, 272, 199, 258, 199, 262, 192, 270, 185, 286, 172, 297, 159
DATA  309, 140, 314, 128, 318, 115, 316, 125, 313, 143, 312, 151, 311, 168
DATA  311, 185, 312, 195, 314, 206, 316, 218, 322, 242, 324, 251, 327, 264
DATA  329, 273

'stroke 5
DATA  37
DATA  353, 120, 343, 120, 334, 120, 323, 120, 301, 120, 286, 120, 269, 120
DATA  260, 120, 257, 128, 258, 137, 259, 149, 260, 163, 262, 178, 263, 186
DATA  275, 185, 290, 184, 302, 184, 321, 185, 335, 188, 353, 195, 363, 200
DATA  376, 212, 382, 220, 386, 229, 384, 243, 379, 252, 373, 258, 365, 266
DATA  350, 279, 337, 287, 313, 297, 305, 299, 292, 301, 280, 302, 269, 299
DATA  257, 290, 251, 284

'stroke 6
DATA  43
DATA  335, 101, 330, 108, 324, 117, 314, 129, 308, 137, 291, 160, 284, 170
DATA  278, 180, 266, 197, 262, 205, 257, 216, 254, 225, 249, 244, 249, 255
DATA  248, 265, 248, 277, 248, 289, 249, 305, 253, 316, 265, 332, 272, 336
DATA  285, 344, 296, 349, 307, 352, 319, 352, 328, 346, 338, 338, 346, 328
DATA  353, 317, 358, 307, 362, 294, 362, 285, 360, 275, 356, 267, 351, 260
DATA  345, 253, 334, 248, 326, 247, 315, 247, 304, 246, 294, 244, 284, 244
DATA  275, 244

'stroke 7
DATA  25
DATA  247, 137, 256, 137, 269, 137, 279, 137, 297, 137, 311, 137, 328, 138
DATA  337, 139, 346, 140, 344, 151, 338, 158, 332, 169, 327, 187, 324, 198
DATA  322, 208, 320, 218, 317, 235, 315, 244, 314, 254, 310, 272, 308, 280
DATA  306, 288, 300, 310, 297, 321, 293, 329

'stroke 8
DATA  58
DATA  353, 128, 344, 125, 335, 123, 323, 121, 299, 119, 291, 118, 283, 117
DATA  261, 117, 248, 121, 234, 131, 227, 138, 220, 152, 218, 162, 220, 171
DATA  226, 180, 243, 192, 252, 194, 260, 197, 269, 199, 286, 202, 300, 206
DATA  308, 208, 321, 214, 332, 223, 344, 236, 349, 244, 355, 254, 357, 264
DATA  356, 273, 352, 281, 343, 294, 335, 303, 320, 312, 313, 316, 300, 320
DATA  286, 322, 274, 324, 258, 325, 247, 323, 234, 313, 228, 303, 223, 289
DATA  223, 280, 228, 265, 232, 257, 237, 250, 241, 243, 252, 230, 266, 219
DATA  278, 212, 300, 200, 310, 195, 319, 190, 326, 186, 338, 177, 347, 168
DATA  354, 156, 356, 147

'stroke 9
DATA  42
DATA  358, 131, 354, 123, 340, 115, 328, 111, 305, 108, 291, 108, 268, 110
DATA  258, 114, 250, 117, 242, 121, 230, 129, 219, 139, 215, 146, 211, 159
DATA  211, 173, 216, 194, 226, 206, 244, 219, 251, 223, 265, 226, 277, 228
DATA  289, 226, 308, 219, 318, 212, 331, 200, 338, 190, 344, 174, 346, 164
DATA  345, 172, 343, 191, 343, 206, 343, 215, 343, 234, 342, 243, 341, 251
DATA  340, 259, 339, 275, 338, 284, 338, 299, 336, 311, 335, 319, 333, 329

THIS IS THE DEMO

Code: Select all

screenres 640,480,32
dim shared as integer mx,my,mb,ox,oy

dim shared as double  stroke(200)      'strokes list of directions
dim shared as integer sCount           'number of strokes in strokes list

dim shared as double templates(10,50)  '10 template strokes with length 50
dim shared as double template(50)      'standardized template of test inputs
dim shared as integer px(1000),py(1000)'

sub thickLine(x1 As Integer,y1 As Integer,x2 As Integer,y2 As Integer,size As Integer,c As UInteger)
    dim as integer x,y
  if x1 = x2 and y1 = y2 then
      circle (x1, y1), size, c, , , , f        
  elseif abs(x2 - x1) >= abs(y2 - y1) then
    dim K as Single = (y2 - y1) / (x2 - x1)
    for I as Integer = x1 To x2 step sgn(x2 - x1)
        x = I
        y = K * (I - x1) + y1
        circle (x,y), size, c, , , , f
    next I
  else
    dim L as Single = (x2 - x1) / (y2 - y1)
    for J as Integer = y1 To y2 step sgn(y2 - y1)
        x = L * (J - y1) + x1
        y = J
        circle (x,y), size,c,,,,f
    next J
  end if
end sub

type BUTTON
    as integer x
    as integer y
    as integer w
    as integer h
    as string  t
    as integer v   'visible or not
end type

dim shared as BUTTON btn(13)

for i as integer = 0 to 9
    btn(i).x = i*20+20
    btn(i).y = 30
    btn(i).w = 16
    btn(i).h = 16
    btn(i).t = str(i)
    btn(i).v = 0
next i

btn(10).x = 5
btn(10).y = 30
btn(10).w = 4*8
btn(10).h = 16
btn(10).t = "YES "
btn(10).v = 1

btn(11).x = 105
btn(11).y = 30
btn(11).w = 4*8
btn(11).h = 16
btn(11).t = " NO "
btn(11).v = 1

btn(12).x = 205
btn(12).y = 30
btn(12).w = 5*8
btn(12).h = 16
btn(12).t = "EXIT"
btn(12).v = 1


sub drawButtons()
    for i as integer = 0 to 12
        if btn(i).v = 1 then
            line (btn(i).x,btn(i).y)-(btn(i).x+btn(i).w,btn(i).y+btn(i).h),rgb(255,255,255),b
            draw string (btn(i).x+4,btn(i).y+4),btn(i).t
        end if
    next i
end sub

function getButtonID() as integer
    dim as integer id
    getmouse mx,my,,mb
    while mb<>1
        getmouse mx,my,,mb
    wend
    id = -1
    for i as integer = 0 to 12
        if btn(i).v = 1 then
            if mx>btn(i).x and mx< btn(i).x+btn(i).w and my>btn(i).y and my<btn(i).y+btn(i).h then
                id = i
            end if
        end if
    next i
    while mb=1
        getmouse mx,my,,mb
    wend
    return id
end function



sub getStroke()
        dim as double  dx,dy,dd        'compute distance of mouse from last position
        dim as double  x1,y1,x2,y2
        dim as double  angle
        sCount = 0  'length of input
        ox = mx
        oy = my
        x1 = mx     'store start of stroke
        y1 = my
        px(sCount)=mx
        py(sCount)=my
        sCount = sCount + 1
        circle(mx,my),3,rgb(255,255,255)
        while mb = 1
            getmouse mx,my,,mb
            if ox<>mx or oy<>my then
                dx = abs(mx - ox)
                dy = abs(my - oy)
                dd = sqr(dx^2+dy^2)
                if dd > 8 then
                    thickline(ox,oy,mx,my,1,rgb(255,255,255))
                    circle(mx,my),3,rgb(255,255,255)
                    ox = mx
                    oy = my
                    x2 = mx  'store end of stroke
                    y2 = my
                    px(sCount)=mx
                    py(sCount)=my
                    
                    dx = x2 - x1
                    dy = y2 - y1
                    angle = int(atan2(dy,dx)*57.2958) 'get angle
                    if angle < 0 then angle = angle + 360
                    stroke(sCount) = angle                   
                    sCount = sCount + 1
                    
                    x1 = mx  'start new line at end of previous line
                    y1 = my
                    
                end if
            end if
            sleep 2
        wend
end sub 

'RETURN DIFFERENCE BETWEEN TWO ANGLES
function getDifference(angle1 as double,angle2 as double) as double
    dim as double dd
        dd = abs(angle1 - angle2)
        if dd > 180 then dd = 360 - dd
    return dd
end function

'========================================================================
'LEARNING:  ENTER STROKES TO REPRESENT NUMERALS 0 TO 9
'A STROKE BEGINS WITH LEFT MOUSE BUTTON DOWN AND ENDS WHEN IT IS RELEASED
'========================================================================

for k as integer = 0 to 9
    cls
    locate 2,2
    print " THIS IS THE LEARNING PHASE."
    print
    print " DRAW A STROKE TO REPRESENT THE NUMERAL ";k
    getmouse(mx,my,,mb)
    while mb <> 1 'wait for mouse button down
        getmouse mx,my,,mb
    wend
    getStroke()

    for i as integer = 1 to sCount-1
        thickline (px(i-1),py(i-1),px(i),py(i),2,rgb(0,0,255))
    next i

    'make template of stroke
    for i as integer = 0 to 49
        templates(k,i) = stroke(sCount*i/50)
    next i
    
next k

cls

dim as string key
dim as integer btnID



do
    cls
    locate 2,2
    print "USING A SINGLE STROKE DRAW A DIGIT TO BE RECOGNIZED"

    getmouse(mx,my,,mb)
    if mb = 1 then
        cls

        getStroke() 'input the stroke
        
        'make template of stroke
        for i as integer = 0 to 49
            template(i) = stroke(sCount*i/50)
        next i
        
        '===========================================
        'compare with saved templates for best match
        '===========================================
        dim as integer score,min,choice
        min = 99999
        choice =-1
        locate 1,1
        for k as integer = 0 to 9  'for each template

            'sum the differences
            score = 0
            for i as integer = 0 to 50
                score = score + getDifference(template(i),templates(k,i))
            next i
            
            if score < min then
                choice = k
                min = score
            end if
        next k
        '===============================================
        
        
        locate 2,2
        print
        print " WAS THIS THE DIGIT DRAWN [";choice;" ] ?"
        
        drawButtons()
        
        btnID = getButtonID()
        while btnID = -1
            btnID = getButtonID()
        wend
        
        if btnID = 11 then  'incorrect response
            'activate digit buttons
            for i as integer = 0 to 9
                btn(i).v = 1
            next i
            'deactivate other buttons
            btn(10).v = 0
            btn(11).v = 0
            btn(12).v = 0
            cls
            locate 2,2
            print "CLICK BUTTON WITH CORRECT DIGIT"
            drawButtons()
            btnID = getButtonID()
            while btnID = -1 and btnID<10
                btnID = getButtonID()
            wend
            'remake template of stroke
            for i as integer = 0 to 49
                templates(btnID,i) = stroke(sCount*i/50)
            next i
            'deactivate digit buttons
            for i as integer = 0 to 9
                btn(i).v = 0
            next i
            'activate other buttons
            btn(10).v = 1
            btn(11).v = 1
            btn(12).v = 1
        end if

    end if
    sleep 2
loop until btnID = 12

[Tourist Trap]

Nice job. I ran the demo, that's quite responsive. You should try to save the tests result in a file in order to compute some probabilities? For example a list of results such as test 23 // guess 3 - false // true answer 9. Then with a simple compilation of result you should know where your test is weak in order to make more efforts there. Just a suggestion of course, I've personally no time for doing this for the moment.

[BasicCoder2]

... Just a suggestion of course, I've personally no time for doing this for the moment.

Yes we all have different programming interests even if sharing an interest in programming itself.

[grindstone]

My introduction was via a hobby in electronics and automation where math is something I am forced to deal with on a needs basis.

That's exactly my own attitude (back in school I HATED maths). You see, you're not allone :)

Regards
grindstone

[BasicCoder2]

@grindstone,
I don't actually hate math I am just not as good at it as I would like to be. I am envious of those for whom math comes easily. I have to struggle hard to get my head around much of it. Math is an incredibly powerful tool and those who are proficient at using it can do things the rest of us can only dream about. Not being good at math is a handicap.

[grindstone]

@BasicCoder2:
I totally agree. Seems that we are related souls (at least concerning to math :-) ). In my opinion the strength of this non-mathematical kind of sight is the capability to think outside the box. As a television technician I often have to grapple with the quirks of firmware programmers: Hundreds of gimmicks that noone will ever need, but simply watching TV is nearly impossible. And then I have to explain the operation of such sophisticated equipment to an 80 year old lady...

But I'm getting off-topic. I'm actually analyzing the different shape recognition snippets. It seems to me that your intention is a shape rekognition software, about the way that you show a picture of a horse to the programme, and the programme says: "This is a horse". Am I right?

Regards
grindstone

[dodicat]

Very neat Basiccoder2.

As far as Maths knowledge is concerned everybody has the same complaint, even Mathematicians.
The subject has grown so vast that for one person to be proficient in all of it would be impossible.

Will you extend to other characters (A,B,C ....)

I think horse recognition would be nearly impossible, after all we don't even understand our own recognition method.
Philosophers quote things like universals of horses and dogs e.t.c. which exist in the minds of humans and horses and dogs e.t.c.

By the way grindstone, my own Mother is now 89 (and also German), she can flick through the Sky channels and do the necessary no problems at all.
My Father has a laptop with Windows 8 which he can operate very well.

But I dare say there are plenty out there, as you say, who find all the added software/gimmicks a burden.
Do you repair T.V.'s as well as setting them up?

[BasicCoder2]

As a television technician I often have to grapple with the quirks of firmware programmers: Hundreds of gimmicks that no one will ever need, but simply watching TV is nearly impossible. And then I have to explain the operation of such sophisticated equipment to an 80 year old lady...

Yes there seems to be no interest in providing an intuitive interface for modern equipment for older people.
Back in my early 20's when the analog tv existed I thought about being a tv and electronics technician but ended up working on the family citrus orchard instead.

It seems to me that your intention is a shape rekognition software, about the way that you show a picture of a horse to the programme, and the programme says: "This is a horse". Am I right?

That is right. A big subject I have read a lot about. There are simple visual systems that can be useful without having to mimic the human visual system. A toad with perfectly good eyes for complex vision appears to reduce its visual input to some set of characteristics that enable it to catch flying insects (moving dots), crawling worms (horizontal lines) and also avoid predators (input becomes darker).
.

[BasicCoder2]

Will you extend to other characters (A,B,C ....)

Yes that is the idea :) But the method of reducing a stroke to a simple fixed length template of angles is too crude to be reliable and it has to handle multiple strokes drawn in any order. For example an A might have two or three strokes. Straight lines are simple to describe but I am not sure yet how to deal with curves in letters such as B C D J O P S U. How do you convert a character into a description. "L is one vertical line, one horizontal line (along bottom) which connects on the right of the lowest point of the vertical line." A horizontal or vertical line doesn't have to be perfectly horizontal or vertical or perfectly straight however sometimes the angle is relevant such as with the characters / \ and |

Regarding the math: You can compute moment invariants as you trace an outline (generate a chain code) which can characterize a shape but they give them as equations that you have to translate to code. I figured out the code to compute the area of a blob as the outline is traced but there are other equations for other moments. I can't type the equation here because the use that funny E symbol and the triangle symbol and the rest is not a linear arrangement of symbols.

I think horse recognition would be nearly impossible, after all we don't even understand our own recognition method.

In fact we do know a lot about our visual system and indeed our brain although we have a long way to go.
There are many clues about how we store images and it is probably not as an image.

By the way grindstone, my own Mother is now 89 (and also German), she can flick through the Sky channels and do the necessary no problems at all. My Father has a laptop with Windows 8 which he can operate very well.

Then hopefully you have inherited her good gene set. Those who live beyond 90 have fewer mutations that make others likely to get cardiovascular diseases, cancer, diabetes and other life shortening ailments.
.

[grindstone]

Do you repair T.V.'s as well as setting them up?

Yes, I do, although it's become less common during the last years.

By the way grindstone, my own Mother is now 89 (and also German)

Please give her my regards.

Yes there seems to be no interest in providing an intuitive interface for modern equipment for older people.

Don't get me wrong: There are indeed exemplary implementations of operating, not every device is a source of anger.

Regarding to the "horse recognition": A promising way seems to me (just as a suggestion) to create a relatively coarse shape of a horse, define a kind of halo around its outline and then look which percentage of the outline of your pattern lies inside this halo.