Category: Computer Vision
Computer vision is hard.
I have code written that detects edges in a video image, picks pairs of edges that are both within a certain ratio of lengths relative to each other and within a specific angle of each other. I’ll post the code up once I have pushing to my github account set up correctly. It’s actually pretty poor at locating cards in a video image, but it is a demo of how to use some of the UI and feature recognition stuff from OpenCV.
From here, I have a few ideas about how to proceed. The first is to have the program display a rectangle and ask the user to align the card to that rectangle. This means the program will not have to find the card in the image, and can focus on recognizing parts of the image. This will use template-based recognition to pick out mana symbols, and should be pretty simple. The classifier that tries to pick out colors will be even easier, as it will just select a sample region, blur it, and match it to precomputed colors. This can be calibrated for specific lighting conditions for each run.
An even less hands-on approach was suggested by my co-worker Eric. The cards could be displayed by a machine that essentially deals one card at a time. The machine would have a magazine of cards, and would photograph a card, deal it into a hopper, photograph the next card, and so forth, until it was empty. This would have the problem that it wouldn’t be something anyone could download and use, as it would require a special card-handling machine, but the software end would be compatible with the user-based registration approach described above, so someone with a lot of patience could use the manual method.
Another approach would be to throw all the cards on a flatbed scanner (possibly with a funny-colored (e.g. red) bed lid, do template matching to locate card borders, and then segment the images based on that. An ADF scanner with a business card attachment could probably also make short work of a modestly-sized set of cards.
I used to play the collectible card game (CCG) Magic:The Gathering. Like most CCGs, Magic has a large set of different cards that players can use to build a set for playing games. This is both fun, as it means new cards will allow new play types and strategies, and annoying because of the artificial rarity of some of the cards. I don’t have a lot of people to play with, so I am planning to sell my cards.
I will probably make more money selling the cards as individual cards (“singles”) than I would get by selling the whole set. However, that means that I need to know how many of each card I have. Given that I probably have upwards of 8,000 cards, I don’t want to sit down and type in the name of each card. It would be better if I could have a computer program do it for me, so I’m working on writing one. The rest of this article uses jargon from Magic and computer vision, so it may be a little incomprehensible to people who are not Magic-playing computer vision nerds.
The program will take an image using a web cam and look for two straight edges, probably using some form of edge detection or a Hough transform. Once it has the edges, it will look for two edges whose ratio of lengths is the same as a Magic card. The edges must share an endpoint, so that the system can tell they are the edges of the same object. The area inside the rectangle that has those lines as its edges is the card.
Once the card is detected, the simplest thing to do is to match the card image against card images stored in a massive database of all card images. Unfortunately, there are over 11,000 unique cards (11,458 as of Feb 2009), which would make for a processor-intensive comparison process.
My plan to circumvent this is to have the program get the casting cost of the card by using processing techniques similar to face detection. The most useful technology to detect mana symbols is probably feature-based template matching. Feature-based template matching allows the computer to pick out a region of a picture that matches another, smaller image, even in the presence of some distortion. Mana symbols haven’t changed significantly since the development of the game, so they should be easy to pick out.
I can also get the color of the card by selecting a region of border, blurring it to remove any texture, and comparing the color to a set of swatches. I’ve done this sort of comparison before, by measuring distance in RGB color space, and it can be done quickly and effectively. The main possible pitfall is poor lighting shifting the color of the object, but I can at least arrive at a probabilistic result based on the RGB distance. Combining the estimated color of the card and the casting cost will allow me to significantly reduce the set of possible pictures that the card image needs to be matched against.
There is also the question of building the database of card images, but I believe I can do that by screen-scraping the web site of the company that makes Magic Cards. I won’t be able to distribute the database with my program, as it will contain copies of copyrighted data, but I can distribute the screen-scraping script.
I may also be able to recognize features like card text, but that will rely on very good lighting and very good cameras. I would prefer that this program work with a moderately high-quality webcam, so that it will be useful to people other than me.
The recognizer will try to build a list of cards that it thinks matches, ordered by the confidence of the match. If the user rejects the first card, it will present the next, until it runs out of guesses. If the use accepts the guess, the recognizer will add that card to a database of all the cards the user owns. In this manner, the user can build a database of cards by simply showing the cards to a computer.