template recognition of any drawn stroke

Post your FreeBASIC source, examples, tips and tricks here. Please don’t post code without including an explanation.
Post Reply
BasicCoder2
Posts: 3906
Joined: Jan 01, 2009 7:03
Location: Australia

template recognition of any drawn stroke

Post by BasicCoder2 »

You can draw a single stroke inside the yellow box.
Each time you start another stroke the previous one will vanish.
When you like what you have drawn you can save it as a template by pressing the [NEW STROKE] button.
It will ask for a name for that stroke. eg. diamond, one, tree
A stroke must be drawn the same way to be recognized again.
Position and size doesn't matter but other variations will for example the width to height ratio of a rectangle will have pieces of the template that will not match and thus reduce the match score.
There is no way to correct the original template yet so get it right before hitting the [NEW STROKE] button for all future strokes meant to match it will match with the original.
You can delete a stored template by selecting it in the template list and pressing the [DELETE SELECTED TEMPLATE] button.

If you want to find the best match of the current drawn stroke with a template in the list of templates press [FIND BEST MATCH]. This will give you the "best" match. It should of course only give you the best match if it is close enough to some acceptable measure.

I haven't added the means to modify a template as at this stage I am just developing a platform to work out a more robust and multi stroked recognizer.

You can save the list of templates and load them again when you restart the program.

How it works:
Essentially it converts a list of coordinates of any length into a list of angles of a fixed length (template). Recognition is simply adding up the differences between each corresponding angle of two templates being compared. The less difference the greater the match.

This first program gives an idea how to draw a stroke.

Code: Select all

screenres 480,480,32
dim as integer x1,y1,x2,y2,count
dim as string sName

for k as integer = 0 to 3
    cls
    locate 2,2
    read sName
    print sName
    read count
    read x1,y1
    for i as integer = 1 to count
        read x2,y2
        line (x1,y1)-(x2,y2),rgb(255,255,255)
        sleep 100
        x1=x2
        y1=y2
    next i
    locate 4,2
    print "Tap space bar"
    sleep
next k

DATA "tree"
DATA  51
DATA  200,111,193,118,187,125,179,133,173,140,167,147,160,156,154,164,147,172,143,179,138,187
DATA  134,195,145,196,155,195,164,195,175,195,183,193,192,193,199,197,200,206,201,218,201,230
DATA  201,240,199,248,207,252,218,252,228,252,238,253,247,253,249,245,247,236,244,228,242,220
DATA  240,212,238,204,237,196,243,190,252,189,261,187,270,184,279,182,287,181,280,172,272,167
DATA  263,161,254,154,247,149,239,143,233,136,227,129,221,121,216,114

DATA  "square"
DATA  51
DATA  141,105,153,106,164,107,185,109,200,109,220,111,234,111,250,111,259,111,272,112,284,112
DATA  291,117,290,131,290,142,290,151,290,160,288,174,287,183,286,197,286,208,286,217,286,229
DATA  286,239,287,249,290,257,290,267,281,268,263,266,250,264,242,263,228,262,215,261,196,260
DATA  183,260,166,259,157,258,147,258,138,256,133,248,138,236,142,229,145,220,147,212,149,201
DATA  151,192,154,184,158,175,159,166,160,158,160,149,159,140,158,132

DATA  "diamond"
DATA  35
DATA  197,102,193,109,187,115,181,122,176,129,169,135,163,142,157,149,151,155,147,162,153,168
DATA  161,174,169,181,175,189,179,196,184,203,191,209,199,215,203,222,211,219,218,213,225,204
DATA  230,195,237,189,242,181,247,174,252,167,246,159,239,155,234,148,230,141,226,133,222,126
DATA  217,119,212,112,205,107

DATA "face"
DATA  43
DATA  239,136,232,140,225,147,222,155,220,163,219,171,218,179,220,187,221,196,216,203,213,211
DATA  207,218,200,223,193,228,188,235,195,240,203,241,211,242,219,243,221,251,220,259,220,268
DATA  228,270,237,270,245,271,237,272,228,272,220,274,219,282,220,290,222,298,229,303,237,304
DATA  246,304,255,303,264,303,272,302,281,302,289,305,297,308,301,315,301,324,301,333,301,342
This is the experimental demo program ...

Code: Select all

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

dim shared as any ptr canvas1   'canvas to draw stroke on

const TSIZE      = 500   'SIZE OF TEMPLATE MUST BE BIG ENOUGH 
const MAXPTS     = 1000  'MAXIMUM POINTS PER STROKE
const MAXSTROKES = 100   'MAXIMUM STROKES TO LEARN

dim shared as double  stroke(MAXPTS)       'strokes list of directions in angles
dim shared as integer ptCount              'number of points in each stroke
dim shared as integer sCount               'number of strokes stored as templates
dim shared as string  sName(MAXSTROKES)    'store name of stroke
dim shared as integer btnID                'returned ID button
dim shared as integer bestChoice           'template# of closest match

dim shared as double  templates(MAXSTROKES,TSIZE)  'template strokes with length TSIZE
dim shared as double  template(TSIZE)      'standardized template of test inputs
dim shared as integer selectedTemplate     'selected template from list
selectedTemplate = -1

dim shared as integer px(MAXPTS),py(MAXPTS)'

sub thickLine(x1 As Integer,y1 As Integer,x2 As Integer,y2 As Integer,size As Integer,c As ulong)
  var dx = x2 - x1
  var dy = y2 - y1
  if dx = 0 andalso dy=0 then
    circle (x1, y1), size, c, , , , f        
  elseif abs(dx) > abs(dy) then
    var m = dy / dx
    for x as Integer = x1 To x2 step sgn(dx)
      circle (x,m * (x - x1) + y1), size, c, , , , f
    next
  else
    var m =dx / dy
    for y as Integer = y1 To y2 step sgn(dy)
      circle (m * (y - y1) + x1,y), size, c, , , ,f
    next
  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
    as integer d   'button down = 1
end type


dim shared as BUTTON btn(7)

btn(0).x = 10
btn(0).y = 8
btn(0).h = 16
btn(0).t = "NEW STROKE"
btn(0).w = 8*len(btn(0).t)+8
btn(0).v = 1
btn(0).d = 0  'button down

btn(1).x = 105
btn(1).y = 8
btn(1).h = 16
btn(1).t = "FIND BEST MATCH"
btn(1).w = 8*len(btn(1).t)+8
btn(1).v = 1
btn(1).d = 0

btn(2).x = 240
btn(2).y = 8
btn(2).h = 16
btn(2).t = "  EXIT  "
btn(2).w = 8*len(btn(2).t)+8
btn(2).v = 1
btn(2).d = 0

btn(3).x = 10
btn(3).y = 32
btn(3).h = 16
btn(3).t = "SAVE TEMPLATES"
btn(3).w = 8*len(btn(3).t)+8
btn(3).v = 1
btn(3).d = 0

btn(4).x = 145
btn(4).y = 32
btn(4).h = 16
btn(4).t = "LOAD TEMPLATES"
btn(4).w = 8*len(btn(4).t)+8
btn(4).v = 1
btn(4).d = 0

btn(5).x = 10
btn(5).y = 64
btn(5).h = 16
btn(5).t = "DELETE SELECTED TEMPLATE"
btn(5).w = 8*len(btn(5).t)+8
btn(5).v = 1
btn(5).d = 0



sub drawButtons()
    for i as integer = 0 to 6
        if btn(i).v = 1 then
            if btn(i).d = 1 then
                line (btn(i).x,btn(i).y)-(btn(i).x+btn(i).w,btn(i).y+btn(i).h),rgb(100,100,255),bf
            else
                line (btn(i).x,btn(i).y)-(btn(i).x+btn(i).w,btn(i).y+btn(i).h),rgb(200,200,200),bf
            end if
            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,rgb(0,0,0)
        end if
    next i
    line (0,100)-(320,420),rgb(255,255,0),b
end sub

function getButtonID() as integer
    dim as integer id
    id = -1
    for i as integer = 0 to 5
        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
                btn(i).d = 1
            end if
        end if
    next i
    if id<>-1 then
        drawButtons()
        while mb=1
           getmouse mx,my,,mb
        wend
        btn(id).d = 0
    end if
    drawButtons()
    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
    line (1,101)-(319,419),rgb(0,0,0),bf 'clear drawing area
    ptCount = 0  'length of input
    ox = mx
    oy = my
    x1 = mx     'store start of stroke
    y1 = my
    px(ptCount)=mx
    py(ptCount)=my
    if ptCount < MAXPTS then
        ptCount = ptCount + 1
    end if
    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(ptCount)=mx
                py(ptCount)=my
                    
                dx = x2 - x1
                dy = y2 - y1
                angle = int(atan2(dy,dx)*57.2958) 'get angle
                if angle < 0 then angle = angle + 360
                stroke(ptCount) = angle                   
                ptCount = ptCount + 1
                    
                x1 = mx  'start new line at end of previous line
                y1 = my
                    
            end if
        end if
        sleep 2
    wend
    'make template of stroke
    locate 1,1
    for i as integer = 0 to TSIZE-1
        template(i) = stroke(ptCount*i/TSIZE)
    next i

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

function recognize() as integer
    dim as integer score,min,choice
    min = 99999
    choice =-1
    locate 1,1
    if sCount<>0 then
        for k as integer = 0 to sCount-1  'for each template
            score = 0
            for i as integer = 0 to TSIZE-1
                score = score + getDifference(template(i),templates(k,i))
            next i
            
            if score < min then 'least difference
                choice = k
                min = score
            end if
        next k
    end if
    return choice
end function

sub learn()
    line (321,0)-(639,479),rgb(50,50,50),bf
    locate 2,45
    input "ENTER NAME OF STROKE: ";sName(sCount)
    'save stroke in list of templates
    'make template of stroke
    for i as integer = 0 to TSIZE-1
        templates(sCount,i) = stroke(ptCount*i/TSIZE)
    next i
    sCount = sCount + 1 'new template added to list
end sub

sub saveTemplates()
    open "templates.txt"  for output as #1
    if sCount<>0 then
        print #1, sCount
        for i as integer = 0 to sCount-1  'each template
            print #1, chr(34);sName(i);chr(34)
            for j as integer = 0 to TSIZE-1
                print #1,templates(i,j);
            next j
            print #1,
        next i
        print #1,
    end if
    print #1,
    close #1
end sub

sub loadTemplates()
    open "templates.txt" for input as #1
    input #1,sCount
    for i as integer = 0 to sCount-1
        input #1,sName(i)
        for j as integer = 0 to TSIZE-1
            input #1,templates(i,j)
        next j
    next i
    close #1
end sub

sub deleteSelectedTemplate()
    if selectedTemplate <> -1 then
        if sCount>0 then
            for i as integer = selectedTemplate to sCount-1
                sName(i)=sName(i+1)
                for j as integer = 0 to TSIZE-1
                    templates(i,j)=templates(i+1,j)
                next j
            next i
            sCount = sCount-1
            selectedTemplate = -1
        end if
    end if
end sub

do
    screenlock()
    drawButtons()
    'input area
    line (321,0)-(639,479),rgb(50,50,50),bf
    
    'draw list of template names
    draw string (400,16),"TEMPLATE LIST",rgb(255,255,255)
    if sCount<>0 then
        for i as integer = 0 to sCount-1
            if selectedTemplate = i then
                draw string (400,i*16+32),str(i) & " " & sName(i),rgb(0,0,0)
            else
                draw string (400,i*16+32),str(i) & " " & sName(i),rgb(255,255,255)
            end if
        next i
    end if    
    screenunlock()
    
    getmouse mx,my,,mb
    if mb = 1 then  'check if button pressed
        
        btnID = getButtonID()
    
        if btnID<>-1 then
            
            if btnID = 0 then
                learn()
            elseif btnID = 1 then
                line (0,420)-(320,479),rgb(200,200,255),bf
                bestChoice = recognize()
                if bestChoice <> -1 then
                    draw string (10,450), "BEST MATCH IS: " & sName(bestChoice),rgb(255,0,0)
                else
                    draw string (10,450), "TEMPLATE LIST EMPTY",rgb(255,0,0)
                end if

            elseif btnID = 3 then
                saveTemplates()
            elseif btnID = 4 then
                loadTemplates()
            elseif btnID = 5 then
                deleteSelectedTemplate()
            end if
            
        else
            if mx<320 and my>100 then
                getStroke()
                drawButtons()
            elseif mx>320 and my >32 then
                if sCount>0 then  'is there any templates?
                    if ((my-32)/16) < sCount then 'does it exist?
                        selectedTemplate = (my-32)/16
                    else
                        selectedTemplate = -1  'deselect
                    end if
                end if
                while mb=1
                    getmouse mx,my,,mb
                wend
            end if
        end if

    end if
    
    
    sleep 2
    
loop until btnID=2
Last edited by BasicCoder2 on Jul 18, 2015 9:00, edited 1 time in total.
D.J.Peters
Posts: 8586
Joined: May 28, 2005 3:28
Contact:

Re: template recognition of any drawn stroke

Post by D.J.Peters »

good job

joshy

Code: Select all

sub thickLine(x1 As Integer,y1 As Integer,x2 As Integer,y2 As Integer,size As Integer,c As ulong)
  var dx = x2 - x1
  var dy = y2 - y1
  if dx = 0 andalso dy=0 then
    circle (x1, y1), size, c, , , , f        
  elseif abs(dx) > abs(dy) then
    var m = dy / dx
    for x as Integer = x1 To x2 step sgn(dx)
      circle (x,m * (x - x1) + y1), size, c, , , , f
    next
  else
    var m =dx / dy
    for y as Integer = y1 To y2 step sgn(dy)
      circle (m * (y - y1) + x1,y), size, c, , , ,f
    next
  end if
end sub
BasicCoder2
Posts: 3906
Joined: Jan 01, 2009 7:03
Location: Australia

Re: template recognition of any drawn stroke

Post by BasicCoder2 »

Thanks Joshy,

I don't know who wrote the first thickline, or maybe I simply adapted a draw line with the circle instead of the pset? All I know is I didn't write the original. I will use your version from now on as I assume it has some advantage over the other one.
Tourist Trap
Posts: 2958
Joined: Jun 02, 2015 16:24

Re: template recognition of any drawn stroke

Post by Tourist Trap »

Nice, very responsive.
BasicCoder2
Posts: 3906
Joined: Jan 01, 2009 7:03
Location: Australia

Re: template recognition of any drawn stroke

Post by BasicCoder2 »

Made some changes to the code in the first post of the thread to enable the deleting, saving and loading of templates.

The weakness is still there that the stroke has to be drawn the same way each time. If you draw a square for example and start at the top/left corner and move right you cannot later draw an identical square by starting at another place or start at the same place but move in the opposite direction.
Tourist Trap
Posts: 2958
Joined: Jun 02, 2015 16:24

Re: template recognition of any drawn stroke

Post by Tourist Trap »

BasicCoder2 wrote: If you draw a square for example and start at the top/left corner and move right you cannot later draw an identical square by starting at another place or start at the same place but move in the opposite direction.
Of course, but your code is so compact that you can easily add further features. Anyway for the case you describe, I see this possibility : you could generate programmatically an array of shapes from one initial hand drawing where you would offset the start position. Example :

Suppose the hand-drawn shape is abcdef , you 'll have then not only to store (or generate at demande) an array of all the possibilities such as abcdef, fabcde, cdefab .... fedcba... And those are truly equivalent here. The issue is that you've got then 2*(length(shape))! combinations - which can be very much.
Tourist Trap
Posts: 2958
Joined: Jun 02, 2015 16:24

Re: template recognition of any drawn stroke

Post by Tourist Trap »

BasicCoder2 wrote: If you draw a square for example and start at the top/left corner and move right you cannot later draw an identical square by starting at another place or start at the same place but move in the opposite direction.
Of course, but your code is so compact that you can easily add further features. Anyway for the case you describe, I see this possibility : you could generate programmatically an array of shapes from one initial hand drawing where you would offset the start position. Example :
  • Suppose the hand-drawn shape is abcdef , you 'll have then (or generate at demande) an array of all the possibilities such as abcdef, fabcde, cdefab .... fedcba... And those are truly equivalent here. The issue is that you've got then 2*(length(shape))! combinations - which can be very much.
Last edited by Tourist Trap on Jul 18, 2015 11:12, edited 1 time in total.
grindstone
Posts: 862
Joined: May 05, 2015 5:35
Location: Germany

Re: template recognition of any drawn stroke

Post by grindstone »

BasicCoder2 wrote:The weakness is still there that the stroke has to be drawn the same way each time. If you draw a square for example and start at the top/left corner and move right you cannot later draw an identical square by starting at another place or start at the same place but move in the opposite direction.
Maybe I have an idea to solve that. I'm actually working on an attempt to improve the "blob scanner", and this is the way the outline of the horse is saved. The two single numbers are the starting point of the line, and the cyphers in the following row show how the line continues from pixel to pixel. That means, every repeated pattern of cyphers means a line of a certain angle. And because the line(s) is/are scanned from the top to the bottom, it doesn't matter how the shape is drawn.

But let me first finish my work...
BasicCoder2
Posts: 3906
Joined: Jan 01, 2009 7:03
Location: Australia

Re: template recognition of any drawn stroke

Post by BasicCoder2 »

One of the issues was how to define a slope?

Probably as the ratio y/x but I found angles easier to visualize.

Below we have one line p1 to p2 which could branch up/left p2 to p3 and the other is down/right p2 to p4. Although the second two line segments have the same slope their spatial relationship to line p1 to p2 is very different.

Code: Select all

     + p3
      \
       \
        \
 p1 +----+ p2
          \
           \
            \
             + p4
One major issue with my computations was that a horizontal line will oscillate widely in value if it isn't exactly straight between say the values 10 and 350. This is illustrated in the program below.

Code: Select all

const Pi = 4 * Atn(1)
Dim Shared As Double TwoPi = 8 * Atn(1)
Dim Shared As Double RtoD = 180 / Pi   ' radians * RtoD = degrees
Dim Shared As Double DtoR = Pi / 180   ' degrees * DtoR = radians
      
screenres 640,480,32

dim as double x1,y1,x2,y2,cr,dx,dy
x1 = 320
y1 = 240
cr = 150

dim as double angle2

for angle as double = 0 to 350 step 10
    x2 = cos(angle*DtoR)*cr + x1
    y2 = sin(angle*DtoR)*cr + y1
    pset (x2,y2),rgb(255,255,255)
    dx = x2 - x1
    dy = y2 - y1
    angle2 = atan2(dy,dx) * RtoD
    print int(angle2)+180
    line (x1,y1)-(x2,y2),rgb(255,0,0)
    draw string (x2,y2),str(int(angle2)+180)
next angle

sleep
Last edited by BasicCoder2 on Jul 19, 2015 13:31, edited 9 times in total.
BasicCoder2
Posts: 3906
Joined: Jan 01, 2009 7:03
Location: Australia

Re: template recognition of any drawn stroke

Post by BasicCoder2 »

grindstone wrote: I'm actually working on an attempt to improve the "blob scanner",...
Blobs often have holes which have to be outlined as well.

You need to be able to traverse all the inner contours as well.

Code: Select all

screenres 640,480,32
circle (200,200),180,rgb(0,255,0),,,,f
circle (120,120),50,rgb(0,0,0),,,,f
circle (240,240),80,rgb(0,0,0),,,,f
circle (240,230),20,rgb(0,255,0),,,,f
sleep
grindstone
Posts: 862
Joined: May 05, 2015 5:35
Location: Germany

Re: template recognition of any drawn stroke

Post by grindstone »

BasicCoder2 wrote:Blobs often have holes which have to be outlined as well.
You need to be able to traverse all the inner contours as well.
That's what I meant with "improve". My intention is to convert an image of a PCB Board (photo or printed layout) to an HPGL-file, and I think it's kind of similar to your intention. See my attempt of a shape scanner:
http://www.freebasic.net/forum/viewtopi ... 19#p209721

The next step will be to convert the data file to a bunch of lines. Every repeated pattern of cyphers represents a line of a certain angle. I'm already thinking about it...

Regards
grindstone

EDIT: I scanned your circle pattern, and it works perfectly. Looking at the output file I think it should be even possible to recognize curves from the outline data.
Post Reply