So we’ve been working on Dargon. You know, the mod installer we’re shipping before the sun explodes.
For a plethora of reasons, we’ve needed a way to generate modification thumbnails. Good thumbnails have the following criteria:
- They focus on the character featured in the modification.
- They are sourced from images of decent resolution.
- They actually improve our user experience.
Goal 1 is the hardest: We can’t use facial recognition on characters like Kogmaw.
Here’s how we generate thumbnails: You can follow along our code here or watch it’s development stream here (jump to 2:10:00, we hit 30 viewers!):
Step One: Edge Detection and Edge Density Histogram
The core of our algorithm relies on three ideas:
- 2D character artwork is usually drawn by artists.
- When 2D character artwork is drawn by artists, artists tend to place more details on the characters that the artwork should focus on, to draw attention to them.
- The majority of characters tend to stand upright, rather than lay sideways.
Our algorithm is simple, involving edge detection and a luminosity histogram:
From there, we compute the mean (Green line) and median (Red line) of the histogram. Starting at the median, we run a hill-climbing algorithm that attempts to select a range with the highest luminosity (Region between Purple Lines).
Nerd note: The cyan lines contain the region within one standard deviation of the median. We have other methods of computing spread, so we don’t really use this.
Step Two: Image Ranking
The algorithm performs this operation for many images while generating a score for them. The score factors in a few variables:
- Wing Spread Factor – Punishes characters like Anivia for spreading features across the image.
- Focus Factor – Rewards images for having their details squishes into a tiny width.
- Width/Height Factor – Punishes images for being too tiny to help in thumbnail generation.
- Brightness Factor – Rewards images for being bright. This helps filter particle textures.
Step Three: Character Slice Compositing
Finally, we select the best images (with a bit of randomization). When compositing a final image from multiple images, we rank our image ‘slices’ based on luminosity and shuffle them in a way that alternates light and dark images. We need to improve this a bit, but here are our final results:
Clearly, the algorithm doesn’t work so well on in-game texture files (they are drawn with different design considerations), but at the least they’re representative of their modifications. Surpringly, though, the algorithm works very well with character artwork, where facial detection would likely fail.
Requirement three was that our algorithm improve our user experience. The thing runs pretty fast and in the background. The only filters we use (which take most of our algorithm’s processor time) are AForge’s Grayscale filter and Homogenity Edge Detector – the Grayscale one iterates per-pixel and multiples rFactor * R + gFactor * G + bFactor * B while the other simply looks for a pixels’s maximum contrast with its neighbors.
Our algorithm does not handle images with bimodal edge distributions. Future improvements might detect these “humps” in our images and generate two output slices. There’s a ton of improvements we could make to this algorithm after we ship Dargon, though for now, we feel pretty k.
So long for now, Michael Yu