[plt-scheme] 2htdp/image

In my (aborted) attempt to reproduce the functionality of the teaching
languages in Python, I used PNG encryption for bitmaps. Since PNG is
lossless and well understood, I just saved bitmaps as a string
containing the base64 encoding of the PNG data (obtained by the same
method for all bitmaps). Equality worked out to simple string
equality.

I don't know how hard it is to PNG-ify an image, but I can't imagine
it'd be much more expensive than creating the bitmap itself. If you
attach the PNG data to the structure, then you have an easy way to do
bitmap comparison that's at most O(width * height), and probably much
better assuming you do simple compression on the PNG data.

Todd

On Wed, Nov 18, 2009 at 4:07 PM, Robby Findler
<robby at eecs.northwestern.edu> wrote:
> What you describe in the first paragraph (below) is what htdp/image
> did, except that it didn't provide the second equality operator, only
> the bitmap-based one. One of the things we found is that doing a full
> bitmap comparison for equality was too expensive for systems and that
> was part of the impetus for 2htdp/image.
>
> So far, all of the trickyness in 2htdp/image is in setting up the
> precise data definition for images to make equality match what one
> would expect (and still be linear time (usually)).
>
> Finally, what you say about matrices (in a followup message) doesn't
> really work for rotation because you need to compute the bounding box
> of the shape (to be prepared for future overlays and stuff) and thus
> you actually need to do a linear time computation to find that bound
> box (ie, apply the matrix to all of the points in the shape)-- it
> isn't just (constant time) matrix multiply. But yes, thinking thru all
> of these issues is what we've been doing recently.
>
> Robby
>
> On Wed, Nov 18, 2009 at 9:13 AM, Stephen Bloch <sbloch at adelphi.edu> wrote:
>> I think this is a reasonable approach to images: by default, store them in
>> terms of drawing primitives (so rotation, scaling, etc. work nicely) but for
>> display and some other purposes, "flatten" them to bitmaps.  It also makes
>> sense to have two different equality operators on images: do they have the
>> same bit-map representation right now, and would they continue to have the
>> same bit-map representation after rotation, reflection, scaling, etc?
>>
>> So what should the drawing primitives be?  The obvious base cases (to me)
>> are ellipses (filled or outline), polygons (filled or outline), line
>> segments, and bitmaps.  And maybe text in a specified font.  The obvious
>> operators, off the top of my head, are vertical and horizontal
>> concatenation, overlay (with translation), rotation, reflection, scaling,
>> and clipping.  Concatenation is the composition of an overlay and a
>> translation.  Conveniently enough, rotation, reflection, translation, and
>> scaling (as well as skewing) can all be represented as matrix
>> multiplication, and matrix multiplication (at least in a pure, exact
>> mathematical world) is associative, so any SEQUENCE of rotations,
>> translations, reflections, scalings, and skews can be represented as a
>> single matrix multiplication.  Overlay, and clipping to an arbitrary
>> rectangular region aligned with the current coordinate system, should be
>> trivial (although they can't be represented as matrix multiplication).
>>
>> Now, about exactness.  It would be nice if (reflect-horiz (rotate 72 (rotate
>> 200 (rotate 88 (reflect-horiz blah))))) were exactly equal to blah.  If you
>> represent rotation, reflection, scaling, and skewing by matrix
>> multiplication with floating-point matrix entries, it may not be.  On the
>> other hand, if you represent each of these operations by separate tree nodes
>> even when they're in sequence, flattening (and therefore displaying) becomes
>> needlessly expensive, especially after you've run an animation of a spinning
>> star for a few minutes.  Obviously, images coming from photographs should by
>> rights be considered inexact, as should anything stored in a lossy format
>> like JPEG... and for display on a physical monitor, we don't need exact
>> images anyway.  Why don't we just cut the Gordian knot and say that ALL
>> images and ALL functions on them are inexact, and you can't reasonably rely
>> on the equality I mentioned at the top of this paragraph?  At low
>> magnification, they may turn out to have equal bitmaps, just as the result
>> of a floating-point computation may be within a large delta of another
>> floating-point value, but one would no more expect exact equality on
>> computed images than on computed inexact numbers.
>>
>> Most of what I've said above applies to 3-D "images" too, of course, but
>> that's another bucket of worms....
>>
>>
>> Stephen Bloch
>> sbloch at adelphi.edu
>>
>>
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>