Wednesday, December 2, 2009

Looking for tennis courts on aerial photos: how it works.

This is a description of how ahathereitis.com works.



The things I'll be looking for are basically just a bunch of lines on the ground (like tennis or basketball courts), so the first step is to convert the original image into an array of line segments (i.e. pairs of points, (x1, y1) - (x2, y2)). In order to do that, the image is converted into gray-scale and 1st and 2nd derivatives of each horizontal and vertical line are taken:



Note that these images aren't really binary 0-or-1 images, it's just the way OpenCV shows them. Instead, each pixel is a floating-point number which is the value of the derivative in the corresponding point.

Now, I'm interested in thin bright lines (i.e. the court boundaries, usually made with white paint), so I need to find the spots where the 1st derivative is somewhat large and positive (which means that the brightness is growing rather fast, transitioning from the green/blue/gray background to the bright-white court boundary line), and the 2nd derivative is somewhat large (by modulus) and negative (which means it wants to make the 1st derivative smaller and eventually negative, for the transition back from the white line to the darker background). Simultaneously scanning the 1st and 2nd derivatives for such spots produces the following:



The left image is the result of scanning the horizontal derivatives, the right one - of the vertical derivatives. The horizontal derivatives are better for finding the vertical lines and vice versa, which is to be expected - e.g. in the extreme case, when horizontal derivatives are taken along a horizontal line, the brightness doesn't change, so there's no information to gain as both derivatives will be constant.

The next step is to build the actual lines: I first merge the neighboring pixels into little horizontal and vertical segments ("slices"). Then I start at one of those slices - let's say a horizontal one - and see if there's another one immediately underneath it, such as that the projection of one of the second one's ends falls within the first one. If there is such a slice, I connect the two slices' centers with a line and look further down, hoping to find a third slice, that attaches to the 2nd one. If there is one, I discard the line between the 1st and 2nd slices and now make a line between the 1st and the 3rd one, but check if the line still goes through the 2nd slice. The process continues until an intermediate slice is no longer crossed by the line being built - then the last line that goes through all intermediate slices is taken and added to the glorious array of lines.

Quite often there's a gap between slices, so that there's no slice immediately under the previous one. In this case, I look along the line built so far to see if there are good candidates further down. This allows to "mend" broken lines and makes for stronger, longer lines.

Side note: OpenCV has an implementation of the Canny algorithm, but it tends to make somewhat jagged lines, especially when working on Terraserver's images, which aren't very sharp (and not particularly new). Half-way into the project I've discovered that USGS has greater (and public domain) imagery, for which the Canny algorithm may work better, but this slices sorcery was already implemented by then, so why throw away a working thing.
There's also a Hough transform implementation for making lines out of pixels, but that didn't work quite well for me... Perhaps I need to play with it some more, although since this is a hobby project, it is more fun to make stuff up by myself.




Once I have the lines, the actual search begins: first I locate a pair of perpendicular line segments (L1, L2) that are close enough to each other to be a part of the model shape... I guess I haven't written about the model shapes yet, but it is basically a set of lines that make up what I want to find (e.g. 11 lines for a tennis court), with some of the corners marked as "key" points, which represent unique ways of applying the model shape to an intersection of two lines.

The model is rotated so that the lines adjacent to the "key" point are parallel to that pair of perpendicular lines (L1 and L2) I found in the previous paragraph and then moved to the intersection point of L1 and L2. Then for each of the model shape's lines I look for a "matching" line within the rest of the image. "Matching" means it is more or less parallel to the model shape's line (a leeway of pi/60 is allowed) and, to quote the code comment (yes! I do have comments there ;))

1. at least one of the shorter segment's ends is "within" the longer segment ("within" means the end's projection onto the longer segment lies within the segment)
2. distance(s) from the end(s) of the shorter segment that are "within" the longer segment to the longer segment are less than a threshold.
3. the shorter line's length is at least a certain portion of the longer one (like 40%)

If enough of the model shape's lines have a matching line in the image, then...


It's a match!

A few more things are done that I didn't describe - e.g. the array of lines is sorted by the the angle each line makes with abscissa (the x axis), so that just a little portion of the array will have to be traversed when looking for matches/perpendiculars. Also, to avoid false positives, I check how many lines fall completely within the model shape and if there are too many, the match is discarded. This happens quite often when processing ocean shots, where sun's reflection off the waves produces a lot of rather randomly-directed lines, so a "matching" line for the model shape's lines can almost always be found - something akin to "comb jamming", I guess.

The next thing I'd like to try is finding the basketball courts, which pose some unique challenges, because they:

a) are of very varying sizes (and I'm not talking about different standard sizes, like "high school" vs "NCAA" vs "NBA" - it would seem that quite often these courts are drawn to take the available space, so if there's no room to make it as long as it should be, then it's just made shorter)

b) contain circles

Circles are probably a blessing in disguise, because even though it is harder to look for them then for the straight lines, they seem to be of standard size mostly, at least the middle one and the half-circles on top of the free-throw line. I think what I need to do is to find a suitable rectangle that is between the "high school" and "NBA" standards in size and then see if there are appropriate (half)circles where they should be.

I also intend to make the source code available if anyone wants it, I just need to clean it up somewhat - mostly remove all the experimental stuff that just sits there unused.

78 comments:

  1. Any thoughts on trying to use this to add features to OpenStreetMap, http://www.openstreetmap.org?

    ReplyDelete
  2. Very nice! reminds me of captcha breaking :p

    ReplyDelete
  3. Very cool, I had no idea there were so many tennis courts around! Where do the mistakes come from? I spotted very few false positives (excluding cases where a single court was tagged multiple times) but a fair number of cases it misses (for example it only finds 2 of 10 or so courts in the sunnyvale municipal tennis center)

    ReplyDelete
  4. For refinement purposes mitchell park in PA is a good case as it has an example of a court that was missed (it's a half sized kids court) and two that were double counted.

    ReplyDelete
  5. Hi there,

    I'm the tech lead at www.juump.com. We provide service for tennis lover (players, coaches, etc) to find each other to organize games & such.

    Our tennis place info has geocode information, but a lot of the time the actual court location isn't at the address. I'd love to apply your technique here to correct our geocode location, resulting in a more precise poiter to where the courts actually are.

    Your saying "make the code available" is music to my ears. How can I get it? It'll be used for a good cause of helping tennis players here in Vancouver (and the US soon, hopefully)

    Thanks
    - halhx

    ReplyDelete
  6. One thing that may interest you is that Washington, DC has a list of public tennis courts available free as KMZ/ESRI files: http://data.octo.dc.gov/ .

    See which ones you detect in the photos against a list of all courts might help you improve your algorithm.

    ReplyDelete
  7. 世間事沒有一樣沒有困難,只要有信心去做,至少可以做出一些成績。 ..................................................

    ReplyDelete
  8. 知識可以傳授,智慧卻不行。每個人必須成為他自己。 ..................................................

    ReplyDelete
  9. 有用的才華若不用,便如同日晷儀放在陰暗之中......................................................

    ReplyDelete
  10. Never put both feet in your mouth at the same time, because then you will not have a leg to stand on. ....................................................

    ReplyDelete
  11. 天下沒有走不通的路,沒有克服不了的困難,沒有打不敗的敵人。........................................

    ReplyDelete
  12. 如果相遇.你會感到相知.那麼.有一種習慣叫做陪伴;如果陪伴.你會感到珍惜.那麼.有一種甜蜜叫做存在!..................................................................

    ReplyDelete
  13. 喜歡看大家的文章,每篇都是一個故事,都是一種心情~~祝大家開心愉快............................................................

    ReplyDelete
  14. 看看blog調整心情,又要來繼續工作,大家加油..................................................................

    ReplyDelete
  15. 耐心是一株很苦的植物,但果實卻很甜美。.......................................................

    ReplyDelete
  16. 大肚能容,了卻人間多少事,滿腔歡喜,笑開天下古今愁。..................................................

    ReplyDelete
  17. Great work! Did you ever make the source code available?
    Best,
    Dan

    ReplyDelete
  18. Hello,

    Your blog provided us valuable information to work on. These images are quite nice. Thanks a lot for this site.

    Dade County Tennis

    ReplyDelete
  19. Another smart thought that I suggest that you quick for one day seven days while you are on your health improvement plan, particularly in the event that you have an exceptionally bustling timetable and don't have room schedule-wise to rest amid the day.

    https://ideal-shops.com/

    ReplyDelete
  20. When you use a genuine service, you will be able to provide instructions, share materials and choose the formatting style. https://racquetsportshq.com/

    ReplyDelete
  21. Let's start! This is the best article I've ever read!
    When I read your post, I returned to my cozy living room.
    a friend of mine! He always took.
    This is the article I'm going to send you.
    I have no doubt it will be interesting to read. I appreciate you sharing this with us.
    vmware workstation pro crack
    autocad crack
    advanced systemcare pro crack
    corel videostudio crack

    ReplyDelete
  22. This great article has really peaked my interest.
    No errors were found during the check.
    You can use it. I hope you like it.
    fineprint crack
    tweakbit driver updater crack
    artlantis studio crack
    movavi video converter premium crack

    ReplyDelete
  23. I'm impressed, to say the least. I've rarely come across a blog that's both educational and entertaining.
    me just say that your performance was flawless
    There are few men and women who are able to speak sensibly about a problem with their heads.
    I couldn't be happier to have discovered myself on this journey.
    There you go.

    ashampoo burning studio crack
    apowersoft video download capture crack
    wintousb enterprise crack
    microsoft office 2007 crack

    ReplyDelete
  24. On the Internet, I was happy to discover this installation.
    It was a wonderful read and I owe it to you at least once.
    It touched my interest a little and you kindly kept it.
    Become a fan of a new article on your site
    bridgechecker crack
    microsoft office 2016 crack
    advanced systemcare ultimate crack
    mixxx crack

    ReplyDelete
  25. Fantastic and useful information.
    I'm glad to hear you're doing well.
    Thanks for providing this useful information! Please keep us posted.
    Here you go. Thanks for sharing.
    driver booster pro license key
    anydesk crack
    driver booster pro crack
    anydesk crack

    ReplyDelete
  26. This plan is stupid! Of course you know how to entertain the reader.
    Between your ease and your videos, it almost inspired me to start my own blog (well, almost ... ha ha!) Good job.
    I liked what you said and, moreover, the way you presented it.
    That's it!
    adobe indesign crack
    minitool partition wizard crack
    guitar pro crack
    sony vegas pro crack

    ReplyDelete
  27. Hello there, I just discovered your blog on Google, and I like it.
    is quite useful. I'll keep an eye out for brussels sprouts.
    If you keep doing this in the future, I will be grateful. A large number of people will profit.
    based on your writing Cheers!
    cyberduck crack
    movavi slideshow maker crack
    activatorwinrar crack
    driver talent crack

    ReplyDelete
  28. I really like your site. Fantastic colors and themes.
    Did you create this site yourself? Reply again because I hope to create my own
    site itself and I would like to know where you have come to
    it is here or where the item is named from.
    Thank you!
    vmware workstation 12 license key
    stellar data recovery crack
    windows 10 home crack

    ReplyDelete
  29. This is a large cup. On your website, keep up the good work.
    Your blog has a lot of potential, and I look forward to exploring it further.
    Thank you very much for your hard work. I'm going to go out and find it for myself.
    It's something I'd suggest to others. They will, I am certain.
    utilise this website
    xsplit broadcaster crack
    roundcube webmail crack
    avast secureline vpn crack
    shadow defender crack
    pro tools crack
    xilisoft video converter ultimate crack
    daemon tools pro crack
    winzip free download with crack

    ReplyDelete
  30. I like your all post. You have done really good work. Thank you for the information you provide, it helped me a lot.I hope to have many more entries or so from you.
    Very interesting blog.
    Avira Phantom VPN Pro Crack
    Avast Driver Updater Crack
    IDM Crack
    CorelDraw Graphics Suite Crack

    ReplyDelete
  31. On the Internet, I was happy to discover this installation.
    It was a wonderful read and I owe it to you at least once.
    It touched my interest a little and you kindly kept it.
    Become a fan of a new article on your site
    asphalt 8 airborne crack
    goldwave crack
    auto tune pro crack
    apowersoft video download capture crack
    microsoft toolkit crack
    adobe indesign crack
    malwarebytes crack
    just cause crack

    ReplyDelete
  32. In the future, I want to avoid reading a blog article that has disappointed me so much that I won't even bother to open it.
    It was my choice to read, but I was hoping you might have something to say.
    The only thing I hear from you, if you weren't thirsty for attention, is a scream for help over something that could easily be addressed.
    inpixio photo focus crack
    inpixio photo focus crack
    spellforce 3 pc crack license key free download 2020
    windows 7 activator

    ReplyDelete
  33. Oh my goodness! Impressive article dude! Thanks, However I am having troubles with your RSS. I don’t understand the reason why I am unable to join it. Is there anybody having the same RSS issues? Anyone that knows the answer will you kindly respond? Thanx!!
    hd video converter factory pro crack
    3d tennis apk
    bandlab cakewalk crack
    windows 10 enterprise crack
    any video downloader crack
    cyberlink photodirector crack
    billiards master apk cracked mod

    ReplyDelete
  34. I like your all post. You have done really good work. Thank you for the information you provide, it helped me a lot.I hope to have many more entries or so from you.
    Very interesting blog.
    xcrack.org
    IDM Crack
    TeamViewer Crack

    ReplyDelete
  35. I am very impressed with your post because this post is very beneficial for me and provide a new knowledge to me. this blog has detailed information, its much more to learn from your blog post.I would like to thank you for the effort you put into writing this page.
    I also hope that you will be able to check the same high-quality content later.Good work with the hard work you have done I appreciate your work thanks for sharing it. It Is very Wounder Full Post.This article is very helpful, I wondered about this amazing article.. This is very informative.
    “you are doing a great job, and give us up to dated information”.
    designcoreldraw graphics crack
    allavsoft video downloader crack
    idm ultraedit crack
    audials one platinum crack
    opencloner ripper crack

    ReplyDelete
  36. Thank you so much for letting me express my feeling about your post.
    You write every blog post so well. Keep the hard work going and good luck.
    Hope to see such beneficial post ahead to.

    avg internet security crack
    em client crack
    wondershare recoverit crack
    glasswire elite crack
    aiseesoft video converter ultimate crack

    ReplyDelete
  37. I wonder if blogs use WYSIWYG editors or if you have to write your articles by hand.
    HTML coding book required.
    I start right away.
    I want to create a blog soon, but I know nothing about coding, so I need some information.
    from history to real life.
    Thanks for all the help you can give.
    enjoy good luck!
    avg internet security crack
    coreldraw graphics suite 2018 crack
    auslogics boostspeed license key
    icecream screen recorder crack
    parallels desktop crack

    ReplyDelete
  38. Sincerely, I am so glad I found your site, I accidentally found you while searching on google
    for something else, I am still here and I want to congratulate you on a nice post and
    a nice blog all over (love the theme/design too),
    I don't have time to watch anywhere in the minute, but I noticed and added
    your RSS feeds, so if I have time, I will return to
    read on, keep up the good work.
    driver talent pro crack
    sublime text crack
    beyond compare crack
    hide all ip crack
    avast internet security crack

    ReplyDelete
  39. Nice Post MEN I really like your site. Fantastic colors and themes.
    Did you create this site yourself? Reply again because I hope to create my own
    site itself and I would like to know where you have come to
    it is here or where the item is named from.
    Thank you!
    FL Studio 20 Crack ---------------------------------------
    Filmora 11 Crack
    AVG Internet Security Key
    AVG Antivirus Crack

    ReplyDelete
  40. You can Also download cracked softwares for windows and mac's.Check my web pageidm crack

    ReplyDelete