Compression through time

So the last time, I told you I came up with my own video format so I could load videos into my game engine. Today, I’m going to tell you what it is.

The concept isn’t revolutionary. Image compression is the art of expressing an image in as small a form as possible. There are 2 versions: lossy and lossless. Lossy compression means some data is lost, meaning the file size can be smaller, but overall you won’t notice the difference (much). The jpeg format uses this. Lossless compression doesn’t lose any data at all. The png format uses a lossless compression.

I don’t know much about video compression. However, a video is a series of images. So what I did was instead of focusing on image-by-image compression, I adopted time-based compression.

For each pixel position, I try to come up with an algorithm (or specifically a maths formula) that will represent all the pixels in that pixel position throughout the entire video.

Let’s say we use the top-left pixel of the video. And let’s say that pixel is pure white for half of the video, and black for the other half of the video. My aim is to represent this “pure white 1st half, pure black 2nd half” information in 1 formula.

With this in mind, let’s say I’ve got a maths formula somehow. Let’s say it’s a 640 by 480 pixel video (it was considered good resolution back then. I know we have HD now…). Let’s say there are 3 variables in that maths formula. This means, I have to store 3 * 640 * 480 variables in my movie format.

Yes, that’s the compression tactic.

Well, more specifically, I had to come up with 3 * 640 * 480 maths formulas that compresses itself as efficiently as possible. With some research, I found that the less the variables vary (hahahah…), the better the compression. This means the colour space I use is important. RGB values change too much.

And with some more research, I found the YUV colour space ideal for use. I think what I actually did was count the number of consecutive values and store that. The YUV space has a “lightness” component, which for most videos, doesn’t change very often.

This means in the ideal case, I store “N of X” for the “lightness” component, where N is the number of times the value X occurs for the “lightness” component of that pixel position. And in the ideal case, N would be approximately the frame rate multiplied by the number of seconds.

So for each pixel position, I store a series of counts of the Y component (could be 10, 50 or ideally just 1). Then I store a series of counts of the U component. And similarly for the V component.

Then I move on to the next pixel.

The idea is that the longer the video, the “better” the compression. It’s not that the compression tactic is better. It’s just that the tactic takes advantage of the fact that certain colour components don’t change much. If a pixel is always white, it doesn’t matter if the video is 1 second long or 1 hour long, we just store “30 white” and “3600 white” respectively (assuming 30 frames per second).

This works great for screencast videos because the screen typically doesn’t change much. It’s usually just the mouse moving around and clicking stuff and sometimes the screen changes. This means most of the screen stays the same. And if you’re like me, you’ve probably watched some screencast videos where nothing on the screen happens for minutes. It’s just the person talking.

Of course, I fudged the actual values a bit so they can compress better. Meaning it’s a lossy compression. But in the end, it was comparable to a moderately compressed QuickTime movie file, so I was ok with that.

But even if the compressed size is still larger than other movie file types, at least it’s not copyrighted. So I can use that. And if you want to try this compression method, go ahead and use it (you have my permission). Let me know how it works out for you.

Compression and space

Back when I was in my making games mode years ago, I was interested in space. Specifically data storage.

Blitting images to the screen as quickly as possible to keep the frame rate consistent was a thing. Texture images are pre-created. Then there’s the concept of generating textures as the program was executed. This was how demos pack data into a small space.

I was studying fractals then, the iterated function system was a thing. I found it a pain to implement though…

And then I was interested in having moving images in my game engine. Packing movies was way harder than images.

Due to the copyrights of all the video formats, in my infinite wisdom, I decided to create my own. I mean, it’s a series of images, right?

The resulting customised movie file was just slightly larger in size than the QuickTime .mov format. I took that as an encouragement. I’ll tell you what I did next time.

Pictures in Excel have way too much power…

You’d think inserting a picture into an Excel worksheet is pretty straightforward. If you’re just inserting the picture, then it is.

Then you check what other properties you can play with manipulating the picture. Woah amigo! There’s a whole plethora of options!

Excel picture format options

That’s like giving the typical user a (good enough) subset of rendering functions, including 3D. And here I thought you could just resize the picture, and maybe rotate it… If you’re not going for full 3D manipulation as in OpenGL or DirectX, Excel will do it for you.

Excel respects alpha/transparency of the picture (right now, I only know of PNG images that contain alpha information AND is fairly prevalent). And you can outline the picture and fill the transparent portions with a colour.

SpreadsheetLight picture fill and outline

You can even do shadows!

SpreadsheetLight picture shadows

Do you know it can take a phenomenal amount of work to get shadows working in 3D renderings? You’ve got to know the light source position, calculate the rays of light blocked by an object to create the illusion of a shadow (by creating a polygon that’s the outline of that object as described by those blocked rays of light). Well, technically speaking, Excel has got it easy, since the object is always a rectangle (an image).

Speaking of light, we can also do reflections. Let’s run a full gamut of the 3D power.

SpreadsheetLight 3D pictures

I lost the software keys to my 2 3D rendering software (Bryce 4 and TrueSpace). It sucked that I couldn’t render landscapes anymore… But, I’m seeing Excel as an alternative to getting some 3D-ish images.

Well, the above screenshots were from a spreadsheet generated by my software library, SpreadsheetLight. The library is based on the Open XML SDK, which in turn is based on what Excel can do. Here’s how the source code looks like:

SLDocument sl = new SLDocument(SLThemeTypeValues.Oriel);

SLPicture pic;
                
sl.SetCellValue(2, 2, "Accent 1");
sl.ApplyNamedCellStyle(2, 2, SLNamedCellStyleValues.Accent1);
sl.SetCellValue(2, 3, "Accent 2");
sl.ApplyNamedCellStyle(2, 3, SLNamedCellStyleValues.Accent2);
sl.SetCellValue(2, 4, "Accent 3");
sl.ApplyNamedCellStyle(2, 4, SLNamedCellStyleValues.Accent3);
sl.SetCellValue(2, 5, "Accent 4");
sl.ApplyNamedCellStyle(2, 5, SLNamedCellStyleValues.Accent4);
sl.SetCellValue(2, 6, "Accent 5");
sl.ApplyNamedCellStyle(2, 6, SLNamedCellStyleValues.Accent5);
sl.SetCellValue(2, 7, "Accent 6");
sl.ApplyNamedCellStyle(2, 7, SLNamedCellStyleValues.Accent6);

pic = new SLPicture("mandelbrot.png");
// anchor at cell (4,2) with 0 horizontal and vertical offsets.
pic.SetRelativePositionInPixels(4, 2, 0, 0);
sl.InsertPicture(pic);

pic = new SLPicture("mandelbrot.png");
pic.SetRelativePositionInPixels(4, 6, 0, 0);
pic.SetSolidFill(DocumentFormat.OpenXml.Drawing.SchemeColorValues.Accent3, 20);
pic.SetSolidOutline(DocumentFormat.OpenXml.Drawing.SchemeColorValues.Accent4, 0);
pic.SetOutlineStyle(4, DocumentFormat.OpenXml.Drawing.CompoundLineValues.Double, DocumentFormat.OpenXml.Drawing.PresetLineDashValues.LargeDash, DocumentFormat.OpenXml.Drawing.LineCapValues.Round, SLPicture.SLPictureJoinType.Bevel);
sl.InsertPicture(pic);

sl.AddWorksheet("Sheet2");

sl.SetCellValue(2, 2, "Accent 1");
sl.ApplyNamedCellStyle(2, 2, SLNamedCellStyleValues.Accent1);
sl.SetCellValue(2, 3, "Accent 2");
sl.ApplyNamedCellStyle(2, 3, SLNamedCellStyleValues.Accent2);
sl.SetCellValue(2, 4, "Accent 3");
sl.ApplyNamedCellStyle(2, 4, SLNamedCellStyleValues.Accent3);
sl.SetCellValue(2, 5, "Accent 4");
sl.ApplyNamedCellStyle(2, 5, SLNamedCellStyleValues.Accent4);
sl.SetCellValue(2, 6, "Accent 5");
sl.ApplyNamedCellStyle(2, 6, SLNamedCellStyleValues.Accent5);
sl.SetCellValue(2, 7, "Accent 6");
sl.ApplyNamedCellStyle(2, 7, SLNamedCellStyleValues.Accent6);

pic = new SLPicture("mandelbrot.png");
pic.SetRelativePositionInPixels(4, 2, 0, 0);
// transparency 0%, blur 6pt, angle 90 degrees, distance 3pt
pic.SetInnerShadow(DocumentFormat.OpenXml.Drawing.SchemeColorValues.Accent1, 0, 6, 90, 3);
sl.InsertPicture(pic);

pic = new SLPicture("mandelbrot.png");
pic.SetRelativePositionInPixels(4, 6, 0, 0);
// transparency 50%, horizontal size 100%, vertical size -23%, horizontal skew -13.34%, vertical skew 0%
// blur 6pt, angle 45 degrees, distance 3pt
// origin at picture's bottom left, don't rotate with picture.
pic.SetPerspectiveShadow(DocumentFormat.OpenXml.Drawing.SchemeColorValues.Accent2, 50, 100, -23, -13.34m, 0, 6, 45, 3, DocumentFormat.OpenXml.Drawing.RectangleAlignmentValues.BottomLeft, false);
sl.InsertPicture(pic);

sl.AddWorksheet("Sheet3");

sl.SetCellValue(2, 2, "Accent 1");
sl.ApplyNamedCellStyle(2, 2, SLNamedCellStyleValues.Accent1);
sl.SetCellValue(2, 3, "Accent 2");
sl.ApplyNamedCellStyle(2, 3, SLNamedCellStyleValues.Accent2);
sl.SetCellValue(2, 4, "Accent 3");
sl.ApplyNamedCellStyle(2, 4, SLNamedCellStyleValues.Accent3);
sl.SetCellValue(2, 5, "Accent 4");
sl.ApplyNamedCellStyle(2, 5, SLNamedCellStyleValues.Accent4);
sl.SetCellValue(2, 6, "Accent 5");
sl.ApplyNamedCellStyle(2, 6, SLNamedCellStyleValues.Accent5);
sl.SetCellValue(2, 7, "Accent 6");
sl.ApplyNamedCellStyle(2, 7, SLNamedCellStyleValues.Accent6);

pic = new SLPicture("mandelbrot.png");
pic.SetRelativePositionInPixels(6, 3, 0, 0);
pic.SetFullReflection();
// width 6pt, height 6pt
pic.Set3DBevelBottom(DocumentFormat.OpenXml.Drawing.BevelPresetValues.Convex, 6, 6);
// width 3pt, height 4pt
pic.Set3DBevelTop(DocumentFormat.OpenXml.Drawing.BevelPresetValues.ArtDeco, 3, 4);
// extrusion colour transparency 0%, extrusion (or depth) height 15 pt
pic.Set3DExtrusion(System.Drawing.Color.Green, 0, 15);
// contour colour transparency 40%, contour width 4pt
pic.Set3DContour(DocumentFormat.OpenXml.Drawing.SchemeColorValues.Accent3, 40, 4);
pic.Set3DMaterialType(DocumentFormat.OpenXml.Drawing.PresetMaterialTypeValues.TranslucentPowder);
// 5 pt above "ground"
pic.Set3DZDistance(5);
// field of view 105 degrees, zoom 100%
// camera latitude, longitude, revolution in degrees (50, 40, 30)
// light rig latitude, longitude, revolution in degrees (0, 0, 30)
pic.Set3DScene(DocumentFormat.OpenXml.Drawing.PresetCameraValues.PerspectiveFront, 105, 100, 50, 40, 30, DocumentFormat.OpenXml.Drawing.LightRigValues.Sunrise, DocumentFormat.OpenXml.Drawing.LightRigDirectionValues.TopLeft, 0, 0, 30);
sl.InsertPicture(pic);

sl.SaveAs("Pictures.xlsx");

I use the enumerations available in Open XML SDK as far as possible. This means you can sort of port over any programs you have written using Open XML SDK. And also that I don’t have to invent my own enumerations that are essentially copies of the SDK enumerations.

One thing that confused me was the 3D rotation options in Excel.

SpreadsheetLight 3D picture rotation options

Excel used the vertical “axis” as the X value, and the horizontal “axis” as the Y value. To the user, the X, Y and Z values are like the first, second and third values of … something.

To me, X, Y and Z have special meanings, particularly when applied to the context of 3D. Those values don’t even increase in a consistent manner. The X value decreases if you use the right-hand rule (the left button), but the Y and Z values increase when you use the right-hand rule (left and right buttons respectively).

The Open XML SDK then complicates matters by using the terms latitude, longitude and revolution. Each ranging from 0 degrees to 359.9 degrees (or strictly less than 360 degrees in other words).

And in case you’re wondering about the state of the spreadsheet library progress, I froze the feature set of SpreadsheetLight for version 1. Otherwise, I’d never get it shipped. I’m now documenting the hashbrown out of the source code. The point is to make it ridiculously easy for a programmer to pick up SpreadsheetLight and start using it (without having to refer to a manual, which I’ll also be writing).

How to insert multiple images in Excel Open XML

A blog reader, Fabrice Sacré, sent me an email with code about how to insert multiple images into an Excel file using Open XML. (I had fun playing Yanni’s “In The Mirror” on the virtual piano on his site.) He based it on my article on inserting just one single image into an Excel file. Based on his email address and signature, he works in the Red Cross. Wow! I’m honoured to be saving lives somehow, somewhere, even if in a long, circuitous and indirect manner. Possibly, I’m thinking too highly of myself and there’s no impact at all to the world at large, but I’m trying not to consider that.

Now when I started with the original code, I was in that “create xlsx, rename to zip, scrutinise xml till I fall asleep” mode. Frankly speaking, I had no idea what I was doing most of the time. And in this respect, the order of the individual code/data components was important, but I don’t know which one should come first (in fact, I still don’t). In particular, the code for inserting an image was before the code for inserting data. That worked fine for 1 image, but didn’t turn out so well when I tried with Fabrice’s code.

Ok, here’s the thing. Fabrice used an Excel template file (.xltx). He loaded that up into a new Excel file, then inserted images. Basically, you have an Excel file, then you obtained the worksheet you want, and then insert images to that worksheet. After I understood that (I had to ask him to send his full source code, because he only sent the image insertion function code), I made some changes to my original code to use his function code, and it worked! I’m not going to post the full source code he sent, because it might be sensitive (Red Cross! Saving lives, people!).

Here are the 3 images I used:
Cloud streaks
I like clouds and blue skies.

Crystallised pavillion
I used the “Crystalize” [sic] function in Paint.NET.

Dozing cat
Everyone loves cats, right?

So here’s the main body of the code:

static void Main(string[] args)
{
    string sFile = "ExcelOpenXmlMultipleImageInsert.xlsx";
    if (File.Exists(sFile))
    {
        File.Delete(sFile);
    }
    try
    {
        BuildWorkbook(sFile);
    }
    catch (Exception e)
    {
        Console.WriteLine(e.ToString());
    }
    Console.WriteLine("Program end");
}

protected static void BuildWorkbook(string filename)
{
    using (SpreadsheetDocument xl = SpreadsheetDocument.Create(filename, SpreadsheetDocumentType.Workbook))
    {
        WorkbookPart wbp = xl.AddWorkbookPart();
        WorksheetPart wsp = wbp.AddNewPart<WorksheetPart>();
        Workbook wb = new Workbook();
        FileVersion fv = new FileVersion();
        fv.ApplicationName = "Microsoft Office Excel";
        Worksheet ws = new Worksheet();
        SheetData sd = new SheetData();

        WorkbookStylesPart wbsp = wbp.AddNewPart<WorkbookStylesPart>();
        wbsp.Stylesheet = CreateStylesheet();
        wbsp.Stylesheet.Save();

        Row r = new Row();
        r.RowIndex = 15;
        Cell c;
        c = new Cell();
        c.DataType = CellValues.String;
        c.StyleIndex = 1;
        c.CellReference = "G15";
        c.CellValue = new CellValue("We have multiple images!");
        r.Append(c);
        sd.Append(r);

        ws.Append(sd);                
        wsp.Worksheet = ws;

        // It happens the resolution for the 3 images are 72 dpi
        // Images are 240 by 180 pixels
        // Adjust as needed

        InsertImage(ws, 0, 0, "cloudstreaks.jpg");
        // 2286000 = 180 (pixels) * 914400 (magic number) / 72 (bitmap resolution)
        InsertImage(ws, 0, 2286000, "crystallisedpavilion.png");
        // 3048000 = 240 (pixels) * 914400 (magic number) / 72 (bitmap resolution)
        InsertImage(ws, 3048000, 0, "dozingcat.jpg");

        wsp.Worksheet.Save();
        Sheets sheets = new Sheets();
        Sheet sheet = new Sheet();
        sheet.Name = "Sheet1";
        sheet.SheetId = 1;
        sheet.Id = wbp.GetIdOfPart(wsp);
        sheets.Append(sheet);
        wb.Append(fv);
        wb.Append(sheets);

        xl.WorkbookPart.Workbook = wb;
        xl.WorkbookPart.Workbook.Save();
        xl.Close();
    }
}

I used the CreateStyleSheet() from this article. I want you to note that the data creation (the single Cell containing the sentence) is now before the image insertion. My approach was originally to model what I see on an Excel worksheet. I would most probably see the image(s) at the top, then the (table of) data below. Hence I modeled the coding to be as such. Apparently, that didn’t work out so well.

[UPDATE: For the CreateStyleSheet() function, it turns out that the NumberFormats class is no longer available in Open XML SDK 2.0. It’s now NumberingFormats. I’ve changed it for the source code for this article (but not for previous code articles)]

Fabrice’s approach was to use a template, then insert images to a particular worksheet. The data sheet was already created (via the template). My approach was to insert images and data in memory, so to speak, before committing the save to the worksheet/workbook parts. Basically, I was trying to create a worksheet out of thin air, add images, add data, and then plug it onto the workbook. Oh well, whatever works then…

Here’s the image insertion function Fabrice sent:

protected static void InsertImage(Worksheet ws, long x, long y, long? width, long? height, string sImagePath)
{
    try
    {
        WorksheetPart wsp = ws.WorksheetPart;
        DrawingsPart dp;
        ImagePart imgp;
        WorksheetDrawing wsd;

        ImagePartType ipt;
        switch (sImagePath.Substring(sImagePath.LastIndexOf('.') + 1).ToLower())
        {
            case "png":
                ipt = ImagePartType.Png;
                break;
            case "jpg":
            case "jpeg":
                ipt = ImagePartType.Jpeg;
                break;
            case "gif":
                ipt = ImagePartType.Gif;
                break;
            default:
                return;
        }

        if (wsp.DrawingsPart == null)
        {
            //----- no drawing part exists, add a new one

            dp = wsp.AddNewPart<DrawingsPart>();
            imgp = dp.AddImagePart(ipt, wsp.GetIdOfPart(dp));
            wsd = new WorksheetDrawing();
        }
        else
        {
            //----- use existing drawing part

            dp = wsp.DrawingsPart;
            imgp = dp.AddImagePart(ipt);
            dp.CreateRelationshipToPart(imgp);
            wsd = dp.WorksheetDrawing;
        }

        using (FileStream fs = new FileStream(sImagePath, FileMode.Open))
        {
            imgp.FeedData(fs);
        }

        int imageNumber = dp.ImageParts.Count<ImagePart>();
        if (imageNumber == 1)
        {
            Drawing drawing = new Drawing();
            drawing.Id = dp.GetIdOfPart(imgp);
            ws.Append(drawing);
        }

        NonVisualDrawingProperties nvdp = new NonVisualDrawingProperties();
        nvdp.Id = new UInt32Value((uint)(1024 + imageNumber));
        nvdp.Name = "Picture " + imageNumber.ToString();
        nvdp.Description = "";
        DocumentFormat.OpenXml.Drawing.PictureLocks picLocks = new DocumentFormat.OpenXml.Drawing.PictureLocks();
        picLocks.NoChangeAspect = true;
        picLocks.NoChangeArrowheads = true;
        NonVisualPictureDrawingProperties nvpdp = new NonVisualPictureDrawingProperties();
        nvpdp.PictureLocks = picLocks;
        NonVisualPictureProperties nvpp = new NonVisualPictureProperties();
        nvpp.NonVisualDrawingProperties = nvdp;
        nvpp.NonVisualPictureDrawingProperties = nvpdp;

        DocumentFormat.OpenXml.Drawing.Stretch stretch = new DocumentFormat.OpenXml.Drawing.Stretch();
        stretch.FillRectangle = new DocumentFormat.OpenXml.Drawing.FillRectangle();

        BlipFill blipFill = new BlipFill();
        DocumentFormat.OpenXml.Drawing.Blip blip = new DocumentFormat.OpenXml.Drawing.Blip();
        blip.Embed = dp.GetIdOfPart(imgp);
        blip.CompressionState = DocumentFormat.OpenXml.Drawing.BlipCompressionValues.Print;
        blipFill.Blip = blip;
        blipFill.SourceRectangle = new DocumentFormat.OpenXml.Drawing.SourceRectangle();
        blipFill.Append(stretch);

        DocumentFormat.OpenXml.Drawing.Transform2D t2d = new DocumentFormat.OpenXml.Drawing.Transform2D();
        DocumentFormat.OpenXml.Drawing.Offset offset = new DocumentFormat.OpenXml.Drawing.Offset();
        offset.X = 0;
        offset.Y = 0;
        t2d.Offset = offset;
        Bitmap bm = new Bitmap(sImagePath);

        DocumentFormat.OpenXml.Drawing.Extents extents = new DocumentFormat.OpenXml.Drawing.Extents();

        if (width == null)
            extents.Cx = (long)bm.Width * (long)((float)914400 / bm.HorizontalResolution);
        else
            extents.Cx = width;

        if (height == null)
            extents.Cy = (long)bm.Height * (long)((float)914400 / bm.VerticalResolution);
        else
            extents.Cy = height;

        bm.Dispose();
        t2d.Extents = extents;
        ShapeProperties sp = new ShapeProperties();
        sp.BlackWhiteMode = DocumentFormat.OpenXml.Drawing.BlackWhiteModeValues.Auto;
        sp.Transform2D = t2d;
        DocumentFormat.OpenXml.Drawing.PresetGeometry prstGeom = new DocumentFormat.OpenXml.Drawing.PresetGeometry();
        prstGeom.Preset = DocumentFormat.OpenXml.Drawing.ShapeTypeValues.Rectangle;
        prstGeom.AdjustValueList = new DocumentFormat.OpenXml.Drawing.AdjustValueList();
        sp.Append(prstGeom);
        sp.Append(new DocumentFormat.OpenXml.Drawing.NoFill());

        DocumentFormat.OpenXml.Drawing.Spreadsheet.Picture picture = new DocumentFormat.OpenXml.Drawing.Spreadsheet.Picture();
        picture.NonVisualPictureProperties = nvpp;
        picture.BlipFill = blipFill;
        picture.ShapeProperties = sp;

        Position pos = new Position();
        pos.X = x;
        pos.Y = y;
        Extent ext = new Extent();
        ext.Cx = extents.Cx;
        ext.Cy = extents.Cy;
        AbsoluteAnchor anchor = new AbsoluteAnchor();
        anchor.Position = pos;
        anchor.Extent = ext;
        anchor.Append(picture);
        anchor.Append(new ClientData());
        wsd.Append(anchor);
        wsd.Save(dp);
    }
    catch (Exception ex)
    {
        throw ex; // or do something more interesting if you want
    }
}

protected static void InsertImage(Worksheet ws, long x, long y, string sImagePath)
{
    InsertImage(ws, x, y, null, null, sImagePath);
}

As of now, it supports only the image formats gif, jpg (jpeg) and png. However, there’s no stopping you from adding support for bmp, tiff, emf and other image formats supported by the ImagePartType enumeration.

Download the source code and the resulting Excel file.

Have fun.

There’s updated material and source code, together with more information on how to work with Open XML. Click here to find out more.

OneCellAnchor might be easier to use than TwoCellAnchor

A reader Kevin emailed me about the use of OneCellAnchor class. This is for coding using Excel Open XML format. The relevant article is about image insertion in Excel. Here’s his comment:

I’ve been using the OneCellAnchor and find it perfect: position by row/column and size by image extent in EMU and best of all, the image will not resize when column widths are set.

If you’re having trouble with figuring out the TwoCellAnchor class properties, you might want to check out OneCellAnchor class instead. Might be easier to work with.

Thanks, Kevin, for that information.

There’s updated material and source code, together with more information on how to work with Open XML. Click here to find out more.