At the time I was attempting to use standard open source image processing software like ImageMagick to manipulate scientific data. I was disappointed to find that it was not suitable, both due to approximations like this one, and because all the libraries I looked at only allowed 8-bit grayscale. I really wanted floating point data.
I was a summer student at the Weizmann Institute of Science in Rehovot, Israel, processing electron micrographs of a particular protein structure made by a particular bacterium. It's very interesting: this bacterium attacks plants and injects some genetic material into the plant, causing the plant to start manufacturing food for the bacterium. By replacing the "payload" of this protein structure, the mechanism can be used to insert other genetic structures into the plant, instead of the sequence that causes it to produce food for the bacterium. Or something like that.
If you liked this trick, check out Alan Paeth's "Graphics Gems" series of books.
Kudos and thanks to the OCF at UC Berkeley which has hosted my web page there for more than a quarter century with just about zero maintenance on my part.
It seems that this algorithm was independently discovered by several authors, some of them earlier than Paeth's:
* H.Kiesewetter, A.Graf, Rotation in Digital Grids and Corresponding Models, Tech. Rep. Zentralinstitut für Kybernetik und Informationsprozesse, Akademie de Wissenschaften der DDR, 1985
* A.W.Paeth, A fast algorithm for general raster rotation, Proceedings GIVIP 1986
* P.E.Danielsson, M.Hammerin, High-accuracy rotation of
images, CVGIP: Graphical Models and Image Processing, 1992.
And this algorithm was implemented on the image package of the ICL Distributed Array Processor [0] as soon as 1984.
The most cited reference for this method seems to be the famous "Yaroslavski" rotation:
* M.Unser, P.Thevenaz, L.Yaroslavski, Convolution-Based Interpolation for
Fast, High-Quality Rotation of Images, IEEE Trans. Image Processing 1995
This is the same method but the shears are computed as filters in the frequency domain, thus they are exactly invertible (which is not the case if you use splines to perform the shears). Here the method really shines: you can rotate 36 times by 10 degrees and get back to the initial image, which is really spectacular.
I wouldn't be surprised if the decomposition itself was a well-known older result in linear algebra, for it seems to be closely related to the QR factorisation.
A 2d shear looks like [[1,a],[0,1]] and a rotation of q is [[cos q, -sin q],[sin q, cos q]]
So you have a system like this to solve:
[[1,a],[0,1]]*[[1,0],[b,1]]*[[1,c],[0,1]]
== [[cos q, -sin q],[sin q, cos q]]
It's not hard to solve (despite being overdetermined) and you can even throw that line above into a CAS directly. The solution is a bit long to paste here though.
I had Dr. Alan Paeth as a university professor for 4 years, one or two classes every semester. I tried to fit my schedule around the classes he was teaching.
When you went to his classes you really had no idea what it was going to be about. I got the sense that sometimes he would just teach whatever was on his mind that day, nevermind the syllabus. It was sometimes bizarre, often challenging, and always interesting. I learned a lot from him.
I'm sad that he has passed and sorry to see his website is no longer online, but also pleased that his legacy is living on and people other than me still think of him -- thank you!
> At the time I was attempting to use standard open source image processing software like ImageMagick to manipulate scientific data. I was disappointed to find that it was not suitable, both due to approximations like this one, and because all the libraries I looked at only allowed 8-bit grayscale. I really wanted floating point data.
Did you try ImageJ (https://imagej.net/)? I think it had support for floating point data 20 years ago. It also can be extended through plug-ins, so if it lacked a feature, it could be added fairly cleanly.
Back in those days, game programmers were like wizards. They did some pretty awesome stuff, with terrible toolsets.
They also tended to be paid fairly poorly, and worked to death, if I remember. I was once recruited by Sierra Online, and decided that discretion was the better part of valor, and all that.
Your site has a fixed floating header. See that bar at the top that follows you as you scroll down? Sorry if I didn't use the technical term or establish enough context that you could infer what I was referring to. (Not sorry if it's just an issue of you playing dumb or not making an effort on your end.)
At the time I was attempting to use standard open source image processing software like ImageMagick to manipulate scientific data. I was disappointed to find that it was not suitable, both due to approximations like this one, and because all the libraries I looked at only allowed 8-bit grayscale. I really wanted floating point data.
Here is what I was working on back in those days: https://www.ocf.berkeley.edu/~fricke/projects/israel/project...
I was a summer student at the Weizmann Institute of Science in Rehovot, Israel, processing electron micrographs of a particular protein structure made by a particular bacterium. It's very interesting: this bacterium attacks plants and injects some genetic material into the plant, causing the plant to start manufacturing food for the bacterium. By replacing the "payload" of this protein structure, the mechanism can be used to insert other genetic structures into the plant, instead of the sequence that causes it to produce food for the bacterium. Or something like that.
Here's a random chunk of my research journal from those days: https://www.ocf.berkeley.edu/~fricke/projects/israel/journal...
The work contributed to this paper: https://www.jbc.org/article/S0021-9258(20)66439-0/fulltext
Here's the Wikipedia article about the author of that algorithm: https://en.wikipedia.org/wiki/Alan_W._Paeth
And his original web page that I linked to, now via archive.org: https://web.archive.org/web/20050228223159/http://people.ouc...
If you liked this trick, check out Alan Paeth's "Graphics Gems" series of books.
Kudos and thanks to the OCF at UC Berkeley which has hosted my web page there for more than a quarter century with just about zero maintenance on my part.
And thanks for the trip down memory lane!