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.

32 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. Great work! Did you ever make the source code available?
    Best,
    Dan

    ReplyDelete
  8. 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
  9. 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
  10. When you use a genuine service, you will be able to provide instructions, share materials and choose the formatting style. https://racquetsportshq.com/

    ReplyDelete
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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
  21. 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
  22. 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
  23. The best platform where intelligent and hardworking minds come together and there is an exchange of knowledge and learning.
    castmagic ai
    supercreator ai

    ReplyDelete