Programming 6

Put your programming skills to the test in these challenges.

Programming 6

Post by lokcoo on Mon Jul 20, 2009 4:48 pm
([msg=27056]see Programming 6[/msg])

Need major help!

Not sure how to even start with this one. Any ideas? Anyone?
lokcoo
New User
New User
 
Posts: 13
Joined: Mon Jul 20, 2009 12:19 pm
Blog: View Blog (0)


Re: Programming 6

Post by Nines on Tue Jul 21, 2009 6:37 am
([msg=27115]see Re: Programming 6[/msg])

There's a couple of ways of doing it:

a) Parse the JavaScript array on the page which contains all the drawing details and then count lines and arcs in the specific areas of the spiral to determine which letter is there, dealing with line lengths, intersections, etc.

b) Grab the image. Rotate the spiral and use a set of heuristics to determine which character is which with an OCR method like counting pixels in certain areas of characters or use some sort of tracing method around the outside of the characters to work out what they are.

There could be another way of doing it that I couldn't think of but these are the two main ways of doing it. I used the latter.
User avatar
Nines
Poster
Poster
 
Posts: 191
Joined: Sun Apr 13, 2008 5:57 pm
Blog: View Blog (0)


Re: Programming 6

Post by lokcoo on Tue Jul 21, 2009 5:38 pm
([msg=27172]see Re: Programming 6[/msg])

How would write an OCR? Could you pm me some source code if you have it? I'm really curious about this one.
lokcoo
New User
New User
 
Posts: 13
Joined: Mon Jul 20, 2009 12:19 pm
Blog: View Blog (0)


Re: Programming 6

Post by Nines on Tue Jul 21, 2009 6:45 pm
([msg=27179]see Re: Programming 6[/msg])

Well I don't really want to solve the challenge for you, but a "counting pixels" method is probably the easiest way of doing it.
If you had an image of a character, you could count how many pixels are in a specific area of the image and make inferences based on it.

Let's use 'A' as an example:

Code: Select all
----#----
---#-#---
---#-#---
--#---#--
--#####--
-#-----#-
#-------#


If we check the first two pixels on the first two lines:

Code: Select all
**--#----
**-#-#---
---#-#---
--#---#--
--#####--
-#-----#-
#-------#


Then if we check the last two pixels on the first two lines:

Code: Select all
----#--**
---#-#-**
---#-#---
--#---#--
--#####--
-#-----#-
#-------#


And find that they are blank then we can eliminate certain characters from our search.

We then check the middle 3 pixels on the first two lines:

Code: Select all
---***---
---***---
---#-#---
--#---#--
--#####--
-#-----#-
#-------#


And find non-blank pixels then it looks like the top of an 'A' or maybe a '1'... Maybe a '4' ?

If we then check the bottom two corners:

Code: Select all
----#----
---#-#---
---#-#---
--#---#--
--#####--
**-----**
**-----**


We find that they aren't blank so we can say that it's probably not a '4', however it could still be a '1' as the character on the mission looks like:

Code: Select all
---#---
--##---
---#---
---#---
---#---
---#---
---#---
-#####-


And so our heuristics would identify it as an 'A'. What we CAN say is that a '1' is noticably thinner than an 'A' in all cases, so if it passes our heuristics, but it's width is 7 or less, then it's got to be a '1', as no 'A' can be less than 7 pixels.

Can you see where I'm coming from here? Obviously your heuristics will need to be much tighter for certain characters (good luck distinguishing B's from 8's ! ;)) but you should get the general idea here.

Also you'll need to take into account the distortions of all characters as you rotate the image. There's no 100% way of getting it right every time, so it'll take a few runs whereby you'll type the spiral out yourself and then debug your heuristics as needed. Every time you do this you fine-tune it.

Hope this helps.
User avatar
Nines
Poster
Poster
 
Posts: 191
Joined: Sun Apr 13, 2008 5:57 pm
Blog: View Blog (0)


Re: Programming 6

Post by lokcoo on Tue Jul 21, 2009 11:19 pm
([msg=27194]see Re: Programming 6[/msg])

Yeah it does a ton. Thanks! Got the A working, now for the rest. lol
lokcoo
New User
New User
 
Posts: 13
Joined: Mon Jul 20, 2009 12:19 pm
Blog: View Blog (0)


Re: Programming 6

Post by Nines on Wed Jul 22, 2009 5:31 pm
([msg=27246]see Re: Programming 6[/msg])

No problem.. Good luck with the challenge :)
User avatar
Nines
Poster
Poster
 
Posts: 191
Joined: Sun Apr 13, 2008 5:57 pm
Blog: View Blog (0)


Re: Programming 6

Post by jpmut on Thu Jul 23, 2009 12:49 pm
([msg=27286]see Re: Programming 6[/msg])

thnks...i had the second method in mind, but i thought its too far-fetched....beause of the spiral rotation....so i've spent almost a week trying to understand the javascript function. atleast i can go back to my original solution n think it throug.

Edit: FINALLY!!! i week ago, i told myself i'll do it, tonight, after many trials i've passed it! everytym i kept on getting a 1 dat supposed to b a 4, a 0 thats supposed to b D or vice-versa!! :D goodluk, to everyone who's doing this mission.

NB: Remember patience pays! mission 6 here i come!
The philosopher and mathematician Bertrand Russell was asked, "If a false premise can imply any conclusion, use 1 = 2 to prove you're the Pope!" Russell replied, "The Pope and I are two, so we are one."
User avatar
jpmut
New User
New User
 
Posts: 22
Joined: Fri Jul 03, 2009 1:13 pm
Blog: View Blog (0)


Re: Programming 6

Post by edilVin on Thu Dec 17, 2009 12:14 am
([msg=31500]see Re: Programming 6[/msg])

I got the origin point of the spiral from the javascript code, and the method I used to get the letters is like in here http://i570.photobucket.com/albums/ss149/edelvp/Programming/originRectangles.jpg.
I divide and get whatever is in each rectangle, split them in two parts, flip them in the right direction, and subdivide to get each letter.
Now the problem is to recognize the letters, I tried asprise (sadly only works on java) and many other OCR tools and API's but none of them are capable to recognize correctly any of these images, even if I fix the image with photoshop, so I started making my own OCR, the problem is that I cannot find a way to recognize either if is a D or 0, sometimes 7 and 1. So I'm wondering if any of you know any other way to solve this problem, other than counting pixels, or if there is any good article I can read. I would appreciate ur help


"Seamos realistas y hagamos lo imposible" Ernesto Che Gevara
User avatar
edilVin
New User
New User
 
Posts: 15
Joined: Thu Mar 05, 2009 10:57 pm
Blog: View Blog (0)


Re: Programming 6

Post by lordofthelefthand on Thu Dec 17, 2009 12:12 pm
([msg=31510]see Re: Programming 6[/msg])

Yeah I'd had to give up on this one for now. My application reads the letters but with only about 95% accuracy, with over 200 letters, 95% just isn't good enough.
User avatar
lordofthelefthand
New User
New User
 
Posts: 16
Joined: Tue Feb 24, 2009 8:28 pm
Blog: View Blog (0)


Re: Programming 6

Post by Rascob on Fri Dec 18, 2009 10:37 am
([msg=31551]see Re: Programming 6[/msg])

I've just finished Prog 3 and 4 so I'll have some time to clean up my head until I try 6. But, thinking about it, I've thought of the two approaches Nines mentions:

1.Calculating: Every character is specified by some lines and/or some arcs. So according to the values you get from the js array, you calculate the relation among them to figure out the characters(eg. 2 arcs [like that] and 2 lines [like this] = "0" zero character).

2.OCRing

OCR is quite hard, especially since there appear to be characters quite small and "noisy". So I think that I'll try my luck through the first approach, which is just geometry and does not involve pixel manipulation. Besides, 1st approach will eliminate problems of telling similar letters apart, such as "0" and "D": D=1line,1arc but 0=2lines,2arcs etc.

But then again, I could be wrong :P
Rascob
New User
New User
 
Posts: 1
Joined: Sat Jun 07, 2008 7:54 am
Blog: View Blog (0)


Next

Return to Programming

Who is online

Users browsing this forum: No registered users and 0 guests

cron