16bit half float in Pascal/Delphi

Floating point numbers with 16 bits of precision are used mostly in computer graphics. They are also called half precision floating point numbers (as having half the bits of single precision 32bit floats). There’s one sign bit, five bit exponent, and ten bits for mantissa. Half floats are not really meant to be used for arithmetic computations due to the limited precision (and no support in common CPUs/FPUs).

Half floats first appeared in early 2000s as samples in images and textures. Floats provide higher dynamic range than what is available with regular 8bit or 16bit integer samples. On the other hand, commonly used single and double precision floats have much higher memory cost per pixel. Half floats have more reasonable memory requirements and their precision is adequate for many usages in imaging.

16bit float formats have been supported by ATI and NVidia GPUs for many years. I’m not sure about other IHVs but at least Direct3D 10 capable GPUs should all support it.

Read on if your interested how to convert between half and single precision floats (Object Pascal code).

Continue reading

Deskewing Scanned Documents

Check out updates and new versions of Deskew tool.

Some time ago I wrote a simple command line tool for deskewing scanned documents called Deskew. Technically, it’s a rotation since angles are preserved and skew transformation doesn’t do that. However, deskewing is commonly used term in this context.

Deskewing some smart paper

My approach is fairly common for this problem – rotation angle is first determined using Hough transform and then the image is rotated accordingly. Classical Hough transform is able identify lines in the image and it was later extended to allow detection of any arbitrary shapes.

Lines of text can be thought of as horizontal lines in the image. In a skewed scanned document all the lines will be rotated by some small angle. We can start with the equation of the line y = k · x + q. Since we’re interested in the angle, we can rewrite it as y = (sin(α) / cos(α)) · x + q. Finally, we can rearrange it as y · cos(α) − x · sin(α) = d. Now every point [x, y] in the image can have infinite number of lines going through it, where each is defined by two parameters: angle α and distance from the origin d.

We want to consider lines only for certain points of input image. Ideally, that would be the base lines on which the “text is sitting”. Simple way of determining these points is to check for black pixels which have white pixels just below them. Now for each of the classified points, we determine parameters α and d for all the lines that go through them. To get some finite number of lines, we calculate d for angles α from a certain range (I use angle step of 0.1 degrees). We want to find a line that intersects as many classified points as possible – an accumulator is used to store “votes” for each calculated line. For each point that is believed to be on the text base line, we add one vote for each line that intersects it. At the end, we find the top lines that have the most votes. Ideally, these are the base lines of all lines of text in the document. Finally, we get the rotation angle by averaging angle α of the top lines and rotate the whole image accordingly.

Important part is that one: “check for black pixels which have white pixels just below”. What’s black and white is determined by comparing value of the current pixel against some given threshold. For images where background is plain white and the text is black it’s easy just to use 0.5 as the threshold. But when the background/foreground distinction is not so sharp calculating the threshold adaptively based on the current image can be very useful. Deskew supports both adaptive threshold calculation as well as specifying constant threshold as command line parameter.

Deskewing some math exercise

Implementation is written in Object Pascal and uses Imaging library for reading and writing various image file formats. There are precompiled binaries for a few platforms, others be built from sources using Free Pascal compiler. Archive also contains few test images.

  Deskew v1.25
» 4.3 MiB - 9,673 hits - January 5, 2011 (last update May 22, 2018)
Command line tool for deskewing scanned documents. Binaries for several platforms, test images, and Object Pascal source code included.

Lego Space

I was a big fan of early 90s Lego Space sets when I was a boy. It was a time of M-Trons, Blacktrons, Space Police, Ice Planet, and others. Unfortunately, Lego was very expensive compared to local wages back then so I didn’t get many of them, let alone some big ones.

Much later, in 2008, I stumbled upon small Lego exhibition made by some local fans. There was a really huge M-Tron base and it got me thinking about buying few of those larger Space sets I wanted years ago. Well, after about two-month eBay shopping spree I had all M-Tron sets – together with about 60 others (and some individual parts orders from Bricklink). I became a nightmare for local post women with all these international packages coming nearly every other day. My best buy was probably Blacktron Message Intercept Base with original box for less than £20 from eBay UK.

These days I don’t have time for Lego anymore, but hopefully this will change some day. And some larger building space would be nice too!

My latest creation is Ice Planet’s Deep Freeze Defender rebuilt as a M-Tron ship. Unfortunately, it was quite damaged during moving to a different house so I’ll have to do some repairs.

Check out my Brickshelf gallery and current set collection.

PasJpeg2000 Update in Progress

I’m currently rewriting much of a Jpeg 2000 for Pascal library. There is a new IO class responsible for decoding and encoding of Jpeg 2000 files instead of only VCL TBitmap descendant. It’s cross platform and with only Delphi/FPC RTL dependencies. VCL and LCL TGraphic classes will be built using this IO class but it can be used independently as well (Imaging library will use it too).

New features of Jpeg 2000 for Pascal will be CMYK colorspace support and also indexed/palettized images support (yes, it’s possible to have image using palette in Jpeg 2000). These features as well as proper alpha channel definitions are patched into OpenJpeg library. Its team is not very active in incorporating larger patches into their code, so patches will probably always be additional step for people who want to recompile OpenJpeg themselves for use with PasJpeg2000.

You can follow the progress of the new version in SVN repository here: branch v120.

Ugly Images of Disabled Menu Items in Delphi

Ever used 32bit images stored in TImageList in your Delphi application? Toolbars and some other VCL controls have DisabledImages property which is automatically used to get images for disabled toolbar buttons. But what about menu components? They don’t have this property and drawing of disabled images is handled by TImageList with original enabled images (TMainMenu.Images property). And the results are really abysmal. How can this be fixed?

One way is to override DoDraw method of TImageList and change the code that draws disabled images. You can do regular RGB to grayscale conversion here or let  Windows draw it for you in grayscale with nearly no work on your part. You can do this by using ImageList_DrawIndirect with ILS_SATURATE parameter. Note that this works only on Windows XP and newer and for 32bit images only. For older targets or color depths doing your own RGB->grayscale conversion is an option (good idea would probably be to cache converted grayscale images somewhere so they won’t need to be converted on every draw call).

Here’s the code of DoDraw method using  ILS_SATURATE:

type
// Descendant of regular TImageList
TSIImageList = class(TImageList)
protected
  procedure DoDraw(Index: Integer; Canvas: TCanvas; X, Y: Integer;
    Style: Cardinal; Enabled: Boolean = True); override;
end;

procedure TSIImageList.DoDraw(Index: Integer; Canvas: TCanvas; X, Y: Integer;
  Style: Cardinal; Enabled: Boolean);
var
  Options: TImageListDrawParams;

  function GetRGBColor(Value: TColor): Cardinal;
  begin
    Result := ColorToRGB(Value);
    case Result of
      clNone: Result := CLR_NONE;
      clDefault: Result := CLR_DEFAULT;
    end;
  end;

begin
  if Enabled or (ColorDepth <> cd32Bit) then
    inherited
  else if HandleAllocated then
  begin
    FillChar(Options, SizeOf(Options), 0);
    Options.cbSize := SizeOf(Options);
    Options.himl := Self.Handle;
    Options.i := Index;
    Options.hdcDst := Canvas.Handle;
    Options.x := X;
    Options.y := Y;
    Options.cx := 0;
    Options.cy := 0;
    Options.xBitmap := 0;
    Options.yBitmap := 0;
    Options.rgbBk := GetRGBColor(BkColor);
    Options.rgbFg := GetRGBColor(BlendColor);
    Options.fStyle := Style;
    Options.fState := ILS_SATURATE; // Grayscale for 32bit images

    ImageList_DrawIndirect(@Options);
  end;
end;

Important note: For ILS_SATURATE to work correctly source image files must be 32bit with proper alpha channel data, setting color depth of TImageList to 32bit is not enough! If you don’t see any images drawn this is probably the cause: 8/24bit image is loaded from file and then inserted into 32bit TImageList. As there is no alpha channel data in source image it is drawn as fully transparent so you don’t see anything.

http://msdn.microsoft.com/en-us/library/bb761537(VS.85).aspx

HoMaM 2 and Arena remakes

My favorite game from Heroes of Might and Magic series is the second one. I guess it’s mainly because of its graphics. I like these nicely done 2D sprites much more than renders of 3D models from HoMaM 3.

Today you can play original DOS version of  HoMaM 2 in DosBox. It wasn’t the case few years ago when DosBox wasn’t able to run SVGA games. There’s also Windows version of HoMaM 2 executables in Heroes Of Might And Magic 2 Gold (expansion disk included). However, neither of these two options take advantage of today’s high resolution monitors. Map view will always be stretched from it’s original 640×480 resolution.

Several years ago, I stumbled upon Free Heroes II project. It’s a GPL cross-platform (SDL based) implementation of Heroes of the Might and Magic II engine. It’s been steadily progressing over the years and fortunately hasn’t died like many other remakes of older games. Today, “standard game” mode is playable as well as hot seat multiplayer. Very nice feature of Free Heroes II is that map view is not stretched to higher resolutions. Instead, you can see larger portion of a map without the need for a lot of scrolling around. Let’s hope we’ll see version 1.0 in near future.

Free Heroes 2

Another game I’d like to see remade is the first The Elder Scrolls game Arena. There hasn’t been any known attempt at remake Arena – unlike its sequel Daggerfall (though all past remakes failed the latest one, DaggerXL, remains very promising). No description of Arena file formats is available on the Internet either (with few exceptions of raw images or formats shared by more Bethesda games) – again unlike Daggerfall where almost everything is described in detail.

I was pleasantly surprised few months ago when I found out about WinArena. It was originally Arena resource extractor and converter (textures, maps, sounds, sprites, …) with 3D engine capable of  displaying Arena maps added later. Unfortunately there are only two versions you can find on the net and the latest is dated December 2005 – so it’s long since dead.

3D engine uses software rendering in 256 color mode like original Arena (it supports higher resolutions though). According to the author, many of the effects in the game are based on palette manipulation tricks so it wouldn’t be possible to get the exact Arena look using standard hardware accelerated 3D API like Direct3D or OpenGL.

What’s best on WinArena is that full source code is provided. And since it handles most if not all Arena file formats, getting their description is just a matter of going through the code. I’d also love the possibility to revisit all the main maps in the game so maybe I’ll modify it a little bit (WinArena currently starts at the beginning of actual Arena gameplay – in the prison like most TES games do).

You can get latest version of WinArena at TESNexus.

WinArena

Just before publishing this post I also found Python port of Elder Scrolls: Arena which also seems inactive at the moment (there’s some resource extraction Python code in the project’s repository).

Stats for 2009

I quite like looking at various stats and sometimes even big tables with a lots of numbers. Since I don’t have anything in particular to write about now, I’ll share some of the site stats for 2009.

Downloads

Top download is JPEG 2000 for Pascal package with about 700 downloads. Second place goes to glSOAR terrain renderer with about 200 downloads. Third place is shared between Earth Under Fire shooter and venerable JPEG Ripper tool, both with meager 60 downloads.

Visitors

There have been around 4000 visitors since last March. 42% of them got here from referring sites,  35% used search engine, and 23% is direct traffic.

Referring Pages

Basically all of them are connected to Imaging Library or JPEG 2000 for Pascal (torry.net, delphiplus.org, imaginglib.sf.net, cc.embarcadero.com, etc.). For some reason there’s really a lot of referrals from images.google[.ru|.de|.fr|.com] pointing mostly to screenshots from Ufo: Extraterrestrials and Terrain Rendering stuff. Few links to Earth Under Fire from pascalgamedevelopment.com are in the stats too.

Browsers and OS

Firefox is in the lead with 40% share, IE is second with 25%, third is Opera with 22%, Chrome and Safari have 7% and 2% respectively. Windows is major OS here with 91%, Linux and Mac OS X have about 4% each. There’s also one visit from Wii and one from PS3.

Search Engine Keywords

Most common keywords refer to these topics: Terrain rendering, JPEG 2000 for Delphi and Pascal, Ufo: Extraterrestrials, DirectX 11 for Delphi, and Daggerfall. You can find more or less information about these topics at this site.

Some keywords were very common too even though I wouldn’t think they’d be so popular:

  • APNG  (mostly coupled with Delphi) – As far as I know my Imaging is only library for Pascal and Delphi that can read and write APNG animated images. That’s probably why Google search for “apng delphi” puts this site at top.
  • Delphi shr operator – Looks like there’s more people surprised that it treats negative values differently than shift right operator in C and some other languages. More on this in this post Shift Right: Delphi vs C.
  • Daggerfall music (“daggerfall gstory music”, “eric heberling” daggerfall”, “robert hood daggerfall”) – Great music indeed, much better than what’s in Morrowind and Oblivion.
  • SOAR terain rendering – here’s my Pascal implementation glSOAR.
  • Modula-2 related (“modula-2 vs c++, vs pascal, vs freepascal, on mac ox, for 8051, …” )

And here are some uniques searches:

  • “ancientlich” – My favorite monster in Daggerfall as well, checkout bestiary at UESP (top of the Undead section!).
  • “UFO old programming language” – that must be COBOL!
  • “ufo enemy ripped png picture” – anyone has these?
  • “directx 11 radeon x1950” – sadly no, otherwise I’d put it back in my PC right away.
  • “mng vs apng” – basically MNG is much more capable but harder to implement, more VS info here.
  • “john the ripper directx 11” – is this some of kind of a game or what?
  • “mac os 7.5 emulator” – check out Basilisk .
  • “midi format daggerfall” – It’s HMI (Human machine interfaces MIDI music file), WinAmp can play and convert that (and other old game MIDI formats as well).
  • “a price drop for gpu in 2010” – there better be one.
  • “earth on fire from space” – let’s hope not anytime soon.
  • “gulfar vivek”, “how is galfar doing?”, “large galfar image” – ???

Imaging in C++ Builder

I tried compiling Imaging in C++ Builder (it uses Delphi compiler to generate .obj file which C++ linker can link and also generates C++ header for Pascal unit) few years ago. It didn’t work – there was internal compiler error, I think right in ImagingTypes unit.

Few days ago I tried C++ Builder 2010 and was pleasantly surprised. It worked! I tried just the library core for now (ImagingTypes, Imaging, ImagingFormats, Pascal only file handlers, etc.) and it works without problems. I’m not sure which C++ Builder version is required for successful compile though. Versions 6 and 2006 stopped with internal error, 2010 worked, and there are 2 other versions between.

Anyway, I’ll try to check out most of the library until the 2010 trial expires for me. Hmm, I’m wondering how many people use C++ Builder for C++ development – I’ve never did something serious in it, basically just to get object files usable by Delphi – so I have no idea if it’s ok.

PS: Another C++ Builder related news – patch for OpenJpeg library to get it compiling in BCB is posted here.

PasJpeg2000 News

JPEG 2000 for Pascal project is based on OpenJpeg library. For a very long time there was a bug that caused alpha (fourth and subsequent image channels) channel to be saved with all the samples having the value of 0.5 (128 for 8bit channels). This buggy behavior also depended on compiler settings – optimization level in case of GCC. You could use at most O1 in Windows and Linux, and only O0 in Mac OS X. Bug was also present when compiling with C++ Builder (to get object files usable in Delphi) but only when irreversible DWT transformation was enabled in OpenJpeg during encoding (it wasn’t before, but working versions of both PasJpeg2000 and Imaging use it now when lossy compression is selected by user to get smaller files).
You can read more about it in this news group post. Basically it was all fixed by changing a condition in one if statement to prevent accessing the fourth element of a three element array.

So what can you expect in the next version of PasJpeg2000 library?
Higher GCC optimization levels should make it a lot faster when using Free Pascal (particularly in Mac OS X where O0 was used). Irreversible DWT transformation produces smaller lossy files than current PasJpeg2000 version and with optional MCT (multicomponent transform – basically RGB>YCbCr) you get even smaller ones. There’s now also a patch that enables OpenJpeg to get palettes from JP2 files so indexed JPEG 2000 images could be supported too. And finally, there are some bug fixes (wrong reconstruction of subsampled files, …).

Shift Right: Delphi vs C

Few weeks ago I converted a little function from C language to Delphi. I kept getting completely wrong results all the time even though I was sure the C to Pascal conversion was right (it was really just few lines). After some desperate time, I just tried replacing SHR operator by normal DIV (as A SHR 1 = A DIV 2 and so on). To my surprise, I immediately got the right results. Can Delphi’s (I didn’t test it in Free Pascal) SHR operator behave differently than C’s >> operator?

It does in fact. SHR treats its first operand as unsigned value even though it is a variable of signed type whereas >> takes the sign bit into account. In the function I converted the operand for right shift was often negative and Delphi’s SHR just ignored the value of the sign bit.

A Bit of Code

int a, b1, b2;
a = -512;
b1 = a >> 1;
b2 = a / 2;

After running this C code both b1 and b2 have a value of -256.

var A, B1, B2: Integer;
A := -512;
B1 := A shr 1;
B2 := A div 2;

This Delphi code however yields different result: B2 is -256 as expected but B1 has a value of 2147483392.

A Bit of Assembler

Assembler output of C code:

Unit1.cpp.22: b1 = a >> 1;
mov eax,[ebp-$0c]
sar eax,1
mov [ebp-$10],eax
Unit1.cpp.23: b2 = a / 2;
mov edx,[ebp-$0c]
sar edx,1
jns $00401bb9
adc edx,$00
mov [ebp-$14],edx

Assembler output of Delphi code:

Unit1.pas.371: B1 := A shr 1;
mov eax,[ebp-$0c]
shr eax,1
mov [ebp-$1c],eax
Unit1.pas.373: B2 := A div 2;
mov eax,[ebp-$0c]
sar eax,1
jns $00565315
adc eax,$00
mov [ebp-$20],eax

As you can see, asm output of C and Delphi divisions is identical. What differs is asm for shift right operator. Delphi uses shr instruction whereas C uses sar instruction. The difference: shr does logical shift and sar does arithmetic one.

The SHR instruction clears the most significant bit (see Figure 6-7 in the Intel Architecture Software Developer’s Manual, Volume 1); the SAR instruction sets or clears the most significant bit to correspond to the sign (most significant bit) of the original value in the destination operand.

Quoted from: http://faydoc.tripod.com/cpu/shr.htm