## 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.

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

2. Nice effort !!

3. Very nice! reminds me of captcha breaking :p

4. 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)

5. 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.

6. 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

7. 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.

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

9. Hello,

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

10. 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/

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

12. 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
corel videostudio crack

13. 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

14. 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
wintousb enterprise crack
microsoft office 2007 crack

15. 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
mixxx crack

16. 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!
minitool partition wizard crack
guitar pro crack
sony vegas pro crack

17. 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!
stellar data recovery crack
windows 10 home crack

18. 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
roundcube webmail crack
avast secureline vpn crack
pro tools crack
xilisoft video converter ultimate crack
daemon tools pro crack

19. 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
microsoft toolkit crack
malwarebytes crack
just cause crack

20. Thank you so much for sharing this amazing information. Keep it up.
Xenonauts 2 Crack
Dragon Ball FighterZ Crack
blufftitler ultimate crack
SnowRunner Crack

21. 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.
“you are doing a great job, and give us up to dated information”.
designcoreldraw graphics crack
idm ultraedit crack
audials one platinum crack
opencloner ripper crack

22. 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

23. 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
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

24. Nice Post MEN
FL Studio 20 Crack ---------------------------------------
Filmora 11 Crack
AVG Internet Security Key

25. 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

26. Foxit pdf editor cracked Amazing blog. I liked it. thanks for this.