One thing that has always bothered me is software patents. They just seem wrong. How can someone own a way of doing something? Or own a technique that others would come up with when trying to solve the same problem? They seem like unnatural restraints, like patenting the solution to a math problem. I can understand wanting to protect your ideas, but I honestly don’t think most software ideas are novel enough to warrant a patent, especially at the rate that the US government seems to be giving them out. I’m mean hell, who can be expected to know about all the stupid things people have patented? There is no fucking way that there were 40,000 patent-worthy software ideas that came out last year. That’s completely absurd.

One example that always comes to mind when of thinking about why software patents are bad is the story of what happened to id Software while they were developing Doom 3. Essentially John Carmack, the technical director at id Software, came up with a neat way of doing real time shadowing, which he called Carmack’s Reverse. After discussing the technique on his blog, it was discovered that two researchers had already patented the idea. In order to be able to use the technique, Carmack had to come to an agreement with them. Someone else, independently of these two parties, had also discovered the technique and presented it at a conference before the patent was filed. This person offered to let id Software use it for free, but id Software decided to play it safe and strike a deal with the patent owners [1].

Its things like that that bother me. Someone is toiling away writing a piece of code, they come up with a great way for solving a problem, implement it, and then later learn some researcher in a lab somewhere has patented the idea – probably just so they can say they have X number of patents – and now they have to pay to use a technique that they came up with on their own.

But I digress. I could go on for 10 pages about why I don’t like software patents. My focus here is that I’ve learned that a patent has been granted for the creation of photomosaics, those neat images that are made up of smaller images. The abstract reads as follows [2]:

A mosaic image is formed from a database of source images. More particularly, the source images are analyzed, selected and organized to produce the mosaic image. A target image is divided into tile regions, each of which is compared with individual source image portions to determine the best available matching source image by computing red, green and blue channel root-mean square error. The mosaic image is formed by positioning the respective best-matching source images at the respective tile regions.

I honestly don’t blame the person who filed this patent, since they were one of the first people to create mosaics with photos [3], and they wanted to make sure people didn’t profit at their expense. However, I still really dislike the idea of patenting a way of doing something, especially when the method seems rather obvious. I was able to write a photomosaic generation program when I was in 11th grade, and I didn’t have to look up an algorithm, I just made one up (yes, Mosaicer was written when I was in high school).

The only part of that abstract that seems outside the normal algorithm for creating your basic mosaic is the part that mentions the “root-mean square error” in relation to the color difference. That part is significant because it does a much better matching job than taking a simple color difference (what Mosaicer does). However, spend any time in a reading up on color differences, and you’ll learn that that’s the way to do color differences in RGB color space. So I’m not sure why this abstract as a whole was considered so novel.

Furthermore, the RGB color space is flawed in that it’s a non-uniform color space. Instead of using the RGB color space, one could use the L*a*b* color space, which is a uniform color space that has some of the most precise color difference formulas ever developed.

There’s also another way of creating photomosaics, outside of simply changing the color space and color difference methods. 90% of the people who read what follows will have no clue what I’m talking about, but try to follow along because this is a completely different way of patch matching than what is described in the patent abstract. Instead of dividing the target image into blocks and seeing which input images best fit the blocks, one can use Fast Fourier Transform patch matching [4, 5]. This technique wasn’t discovered until 2002, and I haven’t seen anyone discuss it with relation to creating photomosaics.

When using this method you transform you data into frequency space, perform some calculations, and then you transform your data back into the normal space. Because frequency space is a weird place, multiplication becomes addition. Therefore your computation time is greatly reduced when calculating squared color differences in frequency space. Kwatra et at [6] wrote about the speed up this matching technique provided in their paper on graph cut texture synthesis. With the simple RGB method, generation time for a particular video was 10 minutes, with the FFT method, generation time on the same video was 5 seconds. This is actually how I came across the FFT patch matching. I had to implement Kwatra’s paper for a graphics project I was assigned.

After reading the FFT paper, I immediately saw the possible application to photomosaics – however, after implementing the FFT patch matching method and seeing its nuts and bolts I wasn’t sure how much of a speed up it would actually provide, since it performs more calculations than needed for photomosaic patch matching (it tells you how well the image matched at every offset instead of just the subset of offsets needed for tile placement). In fact, I wondered if it could end up slowing things down. But there are ways of optimizing it for photomosaics, so it was (and is) unclear to me how much of a speed up or slow down effect it would have.

As you can probably tell, I never got around to trying out the above method in relation to photomosaics, mostly because I’m not that interested in photomosaics anymore. But I did put it on my list of possible things to do in the future. I will never patent any of these ideas discussed here so they’re free for anyone to use. However, I have no clue if someone has already thought of them and patented them. So I can’t make that guarantee. Though I figured I’d make a post noting all of this in case no patent for this exist, just so there are patent free methods for photomosaic creation out there.

References:
[1] http://techreport.com/onearticle.x/7113
[2] http://v3.espacenet.com/textdoc?DB=EPODOC&IDX=US6137498
[3] http://en.wikipedia.org/wiki/Photomosaic#History
[4] http://www.cs.sfu.ca/~torsten/Publications/Papers/icip02.pdf
[5] http://www.cs.sfu.ca/~mark/ftp/Icip02/images/icip_2002.jpg
[6] http://www.cc.gatech.edu/~turk/my_papers/graph_cuts.pdf