mtg – Page 2 – Alexander Miles

Recognizing Cards - Effective Comparisons with Hashing

In the previous post we got as far as isolating and pre-processing the art from a card placed in front of the camera; now we come to the problem of effectively comparing it with all the possible matches. Given the possible "attacks" against the image we're trying to match, e.g. rotation, color balance, and blur, it's important to choose a comparison method that will be insensitive to the ones we can't control without losing the ability to clearly identify the correct match among thousands of impostors. A bit of googling led me to phash, a perceptual hashing algorithm that seemed ideal for my application. A good explanation of how the algorithm works can be found here, and illustrates how small attacks on the image can be neglected. I've illustrated the algorithm steps below using one of the cards from my testing group, Snowfall.

Illustration of the phash algorithm from left to right. DCT is the discrete cosine transform. Click for full-size.

The basic identification scheme is simple: calculate the hash for each possible card, then calculate the hash for the art we're identifying. These hashes are converted to ASCII strings and stored. For each hash in the collection, calculate the hamming distance (essentially how many characters in the hash string are dissimilar), and that number describes how different they are. The process of searching through a collection of hashes to find the best match in a reasonable amount of time will be the subject of the next post in this series (hint: it involves VP trees.) Obtaining hashes for all the possible card-arts is an exercise in web scrapping and loops, and isn't something I need to dive into here.

One of my first concerns upon seeing the algorithm spelled out was the discarding of color. The fantasy art we're dealing with is, in general, more colorful than most test image sets, so we might be discarding more information for less of a performance gain than usual. To that end, I decided to try a very simple approach, referred to as phash_color below: get a phash from each of the color channels and simply append them end-to-end. While it takes proportionally longer to calculate, I felt it should provide better discrimination. This expanded algorithm is illustrated below. While it is true that the results (far right column) appear highly similar across color channels, distinct improvements to identification were found across the entire corpus of images compared to the simpler (and faster) approach.

The color-aware extension of the phash algorithm. The rows correspond to individual color channels. Click for full-size.

I decided to make a systematic test of it, and chose four cards from my old box and grabbed images, shown below. Some small attempt was made to vary the color content and level of detail across the test images.

The four captured arts for testing the hashing algorithms. The art itself is the property of Wizards of the Coast.

For several combinations of hash and pre-processing I found what I'm calling the SNR, after 'signal-to-noise ratio'. This SNR is essentially how well the hash matches the image it should, divided by the quality of the next best match. The ideal hash size was found to be 16 by a good deal of trial and error. A gallery of showing the matching strength for the four combinations (original phash, the color version, with equalized histograms, and without pre-processing) are shown below, but the general take-away is that histogram equalization makes matching easier, and including color provides additional protection against false positives.

This slideshow requires JavaScript.

If there is interest I can post the code for the color-aware phash function, but it really is as simple as breaking the image into three greyscale layers and using phash function provided by the imagehash package. Up next: VP trees and quickly determining which card it is we're looking at!

Recognizing Cards - Image Capture

Back in October I posted a short blurb on my first attempts on recognizing Magic cards through webcam imagery. A handful of factors have brought me back around to it, not the least of which is a still un-sorted collection. Also, it happened to be a good excuse to dig into image processing and search trees, things I’ve heard a lot about but never really dug into. Probably the biggest push to get back on this project was a snippet of python I found for live display of the pre-and-post processed webcam frames in real time, here. There is real novelty in seeing your code in action in a very immediate way, and it also eliminated all of the frustration I was having with convincing the camera to stay in focus between captures. At present, the program appears to behave well and recognize cards reliably!

I plan to break my thoughts on this project into a few smaller posts focusing on the specific tasks and problems that came up along the way, so I can devote enough space to the topics I found most interesting.

Image Pre-Processing
Recognizing Blurry Images: Hashing and Performance
Finding Matches: Fancy Binary Trees

I should note here: a lot of the ideas used in this project were taken from code others posted online. Any time I directly used (or was heavily inspired by) a chunk of code, I’ll link out to the original source as well as include a listing at the bottom of each post in this series.

Pre-Processing

The goal here was to take the camera imagery and produce an image that was most likely to be recognized as "similar" by our hashing algorithm. First and foremost, we need to deal with the fact that our camera (1) is not perfect, the white-balance, saturation, and focus of our acquired image may all be different than the image we're comparing with, and (2) the camera captures a lot more than the card alone. Let's focus on the latter problem first, isolating the card from the background.

The method I described in the previous post works sometimes, but not particularly well. It required exactly ideal lighting and a perfectly flat background. The algorithm I ended up settling on is:

Convert a copy of the frame to grey-scale
Store the absolute difference between that frame, and the background (more on that later)
Threshold that difference-image to a binary image
Find the contours present using cv2.findContours()
Only look at the contours with a bounded area greater than 10k pixels (based on my camera)
Find a bounding box for each of these contours and compute the aspect ratio.
Throw out contours with a bounding box aspect ratio less than 0.65 or greater than 1.0
If we've got exactly one contour left in the set, that's our card!

The next problem to tackle is that of perspective and rotation, which thankfully we can tackle simultaneously. In the previous steps we were able to find the contour of the card and the bounding rectangle for that contour, and we can use these.

Find the approximate bounding polygon for our contour using cv2.approxPolyDp().
If the result has more than four corners, we need to trim out the spurious corners by finding the ones closest to any other corner. These might result from a hand holding the card, for example.
Using the width of the bounding box, known aspect ratio of a real card, and the corners of the trapezoid bounding the card, we can construct the perspective transformation matrix.
Apply the perspective transform.

Camera input image. Card contour is shown in red, bounding rectangle is shown in green. The text labels are the result of the look-up process I'll explain in the coming posts.

The isolated and perspective-corrected card image.

Lastly, to isolate the art we simply rely on the consistency of the printed cards. By measuring the cards it was fairly easy to pick out the fractional width and height bounds for the art, and simply crop to those fractions. Now we're left with the first problem: the imperfect camera. Due to the way we're hashing images, which will be discussed in the next post in this series, we're not terribly worried about image sharpness as the method does not preserve high frequencies. Contrast however, is a big concern. After much experimentation I settled on a very simple histogram equalization. Essentially modifying the image such that the brightest color is white and darkest color is black, without disrupting how the bits in the middle correspond. An example of this is given below.

Sample image showing (cw) the camera capture, the target image, the result of histogram equalizing the input, and the result of equalizing the target. — Sample image showing the camera capture, the target image, the result of histogram equalizing the input, and the result of equalizing the target.

So now we're at the point where we can capture convincing versions of the card art reliably from the webcam. In the next post I'll go over how I chose the hashing algorithm to compare each captured image against all the potential candidates, so we can tell which card we've actually got!

Recognizing Cards - First Attempts

Sorting images has been a problem on my mind for years, but I never had a really good reason to sink time into it. Just recently, I finally found a reason. It occurred to me that it would be useful to have my webcam recognize magic cards by their art, and add them to a database for collection tracking. I've since learned that this wasn't as new an idea as I'd thought, and several complete software packages for this specific application have become available in the last 6 months. Nevertheless, it was an interesting excursion into image processing, admittedly not my home turf. It worked much better than planned too.

To my mind, the problem had three main tasks that I'd not undertaken before, in order of drastically increasing difficulty:

Grabbing camera input from Python
Isolating the card from the background
Usefully comparing images

The first part was mostly just an exercise in googling it and adapting the code to my webcam. Short version, use OpenCV2's VideoCapture method, and be sure to chuck out a few frames while the camera is auto-focusing and tuning the white balance. The second bit proved to be slightly more interesting. Given a photo of a card on a plain white background, canny edge detection can reliably pull out the edge (though I haven't tried this with white-boarded cards yet). The card-background contour is easily picked it; it has the largest area. Once we've cropped the image down to that, we can isolate the art by knowing the ratios used to layout the cards. This process is shown below.

The third and most difficult step, effectively comparing the images, will have to wait until I've got more time to write. Soon!

Python: Filtering lists for value

Update: The way I was pulling price data (the Deckbrew API) has changed the format for data coming back, and I haven't updated my code, so the tool no longer functions. If you're looking for a intuitively laid out mtg price listing by set, I highly recommend the visualizers and listings over at mtg.dawnglare.com!

I've worked with Python for years now, but had never really pursued the idea of running it server-side to generate dynamic content. I came across a problem that was suited for it recently. I had a box of ~5000 Magic: The Gathering commons and uncommons from older sets, and I didn't have a good idea of which were worth something compared to the rest of the chaff. I found the Deckbrew API, and was able to make calls to that by grabbing a well-shaped URL. It was a short path to putting together a simple HTML form for specifying the filter and threshold values as well as displaying the results.

The resulting tool can be found here!

There are certainly bugs, primarily that I've already encountered cards that are listed, but have no listed price for the printing of interest. I'm thinking to work around this by picking the value of an alternate printing, but haven't bothered to work that out yet.

Magic: Mark of the Vampire Alter

I'm clearly still getting the hang of acrylic paint alters, but I'm making some progress. After weeks in a half-completed state I returned to this one and finished it this evening. Why this card? The last time I drafted my cube my friend stomped me 3-0, every time this card hit the table it ended the game. Always run removal, always.

Magic: Learning to make foil peel alters and an alternative method

Update 2: I've started adding the newer attempts to the gallery linked on the top bar. If there are any major process changes I'll likely make another post about it.

Update: It seems allowing the cards to soak for long times (that is, overnight) has mixed results. One of the two I tried came out perfectly, the other had some minor cracking though I'm not sure when it developed. Moving forward I'll probably keep it to 2 hours and make sure to use cold water when removing the residual paper. Hopefully I can update with more results this weekend!

I'd spotted some really excellent work posted up on reddit by users djpattiecake and bigupalters and became interested in giving foil alters a go. In short, the idea is to carefully peel away the foil layer from one card, trim it down, and glue it onto another card for visual effect.

My first attempt at this turned out to be rather ambitious, transferring a gnawing zombie I'd happened to have onto the text box of a swamp. I started primarily following the guide put up by bigupalters on facebook, here. Using a hobby knife I picked at the edges until I was able to get at a layer with mostly foil and very little paper. I thought it wasn't an issue, but it turns out having the fibrous layer beneath makes cutting small accurate segments very difficult and results in ragged white edges. A second gripe, once peeled the foil has the tendency to want to coil up like a scroll. I did try to flatten the foil out by pressing it under a stack of hefty books, but that didn't work.

A M14 Gnawing Zombie composited onto an 8th edition swamp.

For my second attempt I decided that getting a paper-free foil was absolutely key. I followed the advice given here. Namely, I got some acetone and rubbed the corner until it managed to dissolve the adhesive between the paper and foil layers, giving me a good clean peel. However, this still had the issue of yielding a very tightly curled foil layer.

At this point I decided to science at it a little bit: what causes the curling? Internal stress from the peeling process. The 'curl' clearly aligns with the direction of the peeling, likely due to alignment of the polymer in the film. We can, in principal, remove internal stress by heating the material up with it in the desired orientation, essentially ironing. I used two advertisement cards (generally regarded as worthless) to sandwich the foil flat, and kept a scrap of parchment paper on top. This stack was ironed for 10 seconds, cooled for 10 seconds, ironed for 10 seconds, then cooled for 10 seconds. This did indeed flatten it out, however the glue remelted and stuck it to one of the cards. After carefully pulling it off of that card it was much less curled, but it did begin to wrinkle and crack in several regions. Testing with a foil scrap showed that a single 10 second cycle produced substantially less wrinkling and cracking.

Joint Assault composited onto a Shards of Alara Forest. Note the cracking.

The peeling process itself was the cause of the problems. It got me thinking, "If only we could lift it straight off of the paper-adhesive stack without tensioning the film, we'd be golden", and it turns out we can. Given that the peeling method is destructive anyways, it opens the door to a lot of other methods I would normally shy away from. Short story: intentional water damage. When soaking the to-be-peeled card for long periods in water the adhesive eventually dissolves, the paper backing soaks up water and breaks away as it expands. The foil layer is a polymer, a water-proof plastic with water-proof ink on it, so it survives unscathed.

Below is an example, I wanted to composite the art from the 2012 Lifelink onto a 10th edition plains.

I used a small tupperware with room temperature tap water. Linked are images taken immediately, at 10 minutes, 30 minutes, 45 minutes. Below the card after 1.5 hours is shown. I'll be honest, I did get a bit impatient and started tugging at the corners after 45 minutes, hoping for a clean separation. This may have influenced the resulting curling, and I'm planning to let one soak over night to see if my impatience was a factor.

The foil layer was easily separated from the backing, with any residual paper removed by rubbing it under running water. Once the entire foil layer was smooth it was dried by pressing it between paper towels a few times, then being left to air dry. Some curling is still apparent, and this may just be a property of the foil as curling of foiled cards is an established problem. It is, however, much less curled than the peeled foil. From here we can simply cut it to size and glue it to the host card.

The foil layer removed from the cardboard backing. — The foil layer removed from the cardboard backing after drying.

From here on I cut out the art from the foil. In order to get the art the right size for the text box on the plains, I went ahead and made a template using a newspaper, artist's tape, and two advert cards, yielding three well-defined edges.

The foil layer cut apart, isolating the art

The template allowing me to cut a rectangle with the correct angle and height.

After the art was cut out, all that was left to do was to gingerly glue it in place and trim any stray edges.

The round handle of the hobby knife was used to roll over the glued region to ensure it lay flat. The final product actually looks pretty nice!

As with everything in life, there are many right ways to do it, but I'm happy to say I've found a method that works for me.

Stained Glass: First Attempt

On a recent visit to Berkeley I was given the chance to take a stab at assembling a stained glass piece. To be clear, I wasn't staining/coloring the glass myself, though I have done that back when I had access to the materials science glass blowing shop. The first step was to choose a design, and given my background I chose a rather suspect flower. Next the glass was picked out at a local stained glass craft shop near the bay; a bright blue, a purple, a green, and a reddish-purple provided all the colors I'd need. All said and done, about $20 worth of glass. Next we printed the design and outlined and numbered the obvious segments, and with a pair of three-bladed scissors (designed to remove a narrow strip of paper from between the segments to allow for solder and copper tape) cut out all the segments.

The edge has been trimmed off, the segments outlined and numbered.

The next step was to take each segment, keeping track of the color it was supposed to be, and gluing it down to the appropriate glass using an middle-school style glue stick. Each bit of glass was then broken out into the approximate shape of the segment using a glass scorer and pliers. Then came the grinding. The grinder sported a metal grinding post with a constant feed of water to keep the dust and heat down, and proved to be the most fun part of the entire process as there was little to no risk of breaking the pieces. After each piece had been ground to a more-or-less perfect shape, the segments were re-assembled into the original shape to check their fit. A few places had to be re-ground, but overall it came together nicely.

Now that we were convinced that the pieces all fit well, we were able to wash away the paper and finally see the design in the colors we picked out earlier in the day. The challenge here was to keep everything in order, as the pieces now had no identifying features and could easily be confused for similarly shaped pieces.

The shards were then washed, removing the now mushy paper and glue.

A bit of materials science wisdom comes into play here. Glass and metal rarely play well together, and soda-lime glass and solder are no exception. In order to get the solder to effectively glue the segments together an intermediate metal has to be applied to the edges of the segments. Copper tape, being a strip of copper with adhesive on one side, serves this purpose beautifully. Each piece of glass had a stripe of tape straddling it's edge such that the edge and a few millimeters on both sides were covered. You'll notice in the photo below that two of the petals on the left had to be broken into two parts as they broke during cutting, but the visual impact of this is quite minimal. I attribute this to my poor choice of shapes during the initial drawing process, as I didn't think about how easily the shapes could be realized.

Glass shards with copper tape applied. — Glass shards with copper tape applied, laid over the original image.

With everything taped, the remaining steps were to solder the pieces together, patina the solder to a darker color, and protect the whole thing with wax. Having soldered before this was an easy process, the only non-intuitive part of which was tapping. Tapping refers to dropping little blobs of solder around at key points to lock the pieces in a single orientation before trying to fill the gaps in a continuous manner.

A quick rinse with flux remover left the surface clean. The patina, with plenty of labels reminding us that it is very toxic, was quick acting and gave the solder a nice pewter look. Lastly the liquid wax was rubbed onto both sides, and the whole thing was washed in soap and water to remove any excess flux, patina, and wax to make it safe the handle.

An early flight left me without a good source of packing materials the morning I flew back to Tucson, so I trusted that my portfolio was sturdy enough to protect the piece for a few hours. When I got home I discovered that it apparently wasn't good enough; several cracks had formed in the central pieces. They were not enough to compromise the piece, and it should hold together for some time while looking awesome in my window.