4 ms·

Hah! Author of that 20-year-old web page here. At the time I was attempting to use standard open source image processing software like ImageMagick to manipulat

Hah! Author of that 20-year-old web page here. 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/projects.html 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.html 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 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 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.bc.ca/awpaeth/awpaeth.html 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!

deleted 4y ago
[deleted]
deleted 4y ago
[deleted]
enriquto 4y ago
> the author of that algorithm: https://en.wikipedia.org/wiki/Alan_W._Paeth https://en.wikipedia.org/wiki/Alan_W._Paeth 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. [0] https://en.wikipedia.org/wiki/ICL_Distributed_Array_Processor https://en.wikipedia.org/wiki/ICL_Distributed_Array_Processo...
- Y_Y 4y ago
  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.
Someone 4y ago
> 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/ 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.
ChrisMarshallNY 4y ago
Kudos! 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.
SilasX 4y ago
You were doing fixed floating headers 20 years ago? Now I know who to blame ;-)
- tobinfricke 4y ago
  I'm not sure what you're talking about.
  - SilasX 4y ago
    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.)
    - tobinfricke 4y ago
      Oh I see what you mean. My page is the one linked from that page. It's written in very plain HTML: https://www.ocf.berkeley.edu/~fricke/projects/israel/paeth/rotation_by_shearing.html https://www.ocf.berkeley.edu/~fricke/projects/israel/paeth/r...
hoytech 4y ago
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!

deleted 4y ago

[deleted]

deleted 4y ago

[deleted]

enriquto 4y ago

> the author of that algorithm: https://en.wikipedia.org/wiki/Alan_W._Paeth https://en.wikipedia.org/wiki/Alan_W._Paeth 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. [0] https://en.wikipedia.org/wiki/ICL_Distributed_Array_Processor https://en.wikipedia.org/wiki/ICL_Distributed_Array_Processo...

Y_Y 4y ago
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.

Someone 4y ago

> 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/ 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.

ChrisMarshallNY 4y ago

Kudos! 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.

SilasX 4y ago

You were doing fixed floating headers 20 years ago? Now I know who to blame ;-)

tobinfricke 4y ago
I'm not sure what you're talking about.
- SilasX 4y ago
  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.)
  - tobinfricke 4y ago
    Oh I see what you mean. My page is the one linked from that page. It's written in very plain HTML: https://www.ocf.berkeley.edu/~fricke/projects/israel/paeth/rotation_by_shearing.html https://www.ocf.berkeley.edu/~fricke/projects/israel/paeth/r...

hoytech 4y ago

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!