Representing image data

Representing image data

[Kenneth Almquist]

I've been working on the design of an image decoding library.  The
basic idea is that the library will examine the first few bytes of
an image, determine the format, and call the appropriate decoder,
so that an application using the library can read images without
writing code for each image format it wants to handle.

I'm looking for suggestions on what the Ada interface to the
library should look like--and in particular how the image contents
should be provided to the application using the library.  The current
design has a C interface with no type checking on the image data.

What follows is the C language interface presented in Ada syntax.
The data for each pixel consists of one or more samples.  There are
a fair number of possibilities, because both the meaning of the
samples and the number of bits per sample can vary.  The possibilities
for the meanings of the samples are:

    Imd.W - white (greyscale) sample
    Imd.WA - white + alpha (transparency) samples
    Imd.RGB - red + green + blue samples (color image)
    Imd.RGBA - RGB + alpha samples
    Imd.CMYK - C + M + Y + K samples (color printer separation)
    Imd.Unknown - one or more samples whose meaning is not known
                  by the library.

Any of the previous possibilities may be combined with Imd.Mapped.
If Imd.Mapped is set, there is one sample per pixel representing
an index into a color map.  Each entry in the color map will contain
one or more sample values, in one of the formats listed above.

The size of the samples can be one of:

    Imd.Size_1BE
    Imd.Size_8
    Imd.Size_16

Imd.Size_8 means that samples are 8 bits.  The corresponding Ada type
is Interfaces.Unsigned_8 or equivalent.  Imd.Size_16 means 16 bit
samples, stored in Interfaces.Unsigned_16 or equivalent.  Imd.Size_1BE
means one bit samples, packed into Unsigned_8 quantities in big endian
order (high order bit first).  Imd.Size_1BE is only used when there is
one sample per pixel; it is intended to allow bit maps to be represented
compactly.

If a color map is used, then the size of the samples in the color map
also needs to be specified.  The possiblities are:

    Imd.Map_Size_8
    Imd.Map_Size_16

In the C language interface, all of the above constants have the type
Interfaces.Unsigned_16, and can be combined using the "+" or "or"
operators.  For example, mapped RGB color with 8 bit sample sizes can
be specified as

    Imd.RGB or Imd.Mapped or Imd.Size_8 or Imd.Map_Size_8

Most applications would use only a few of the possible output formats.
The library contains conversions to:
    - convert mapped data to unmapped data
    - convert greyscale to RGB.
    - convert CMYK to RGB (but not very accurately).
    - add or discard the alpha channel.
    - convert sample sizes to 8 or 16 bits.
So the library can convert any image to (Imd.RGB or Imd.Size_8) except
for images where the meanings of the samples are unknown.

One additional variation is that the image can be decoded one row at a
time, or in one piece.  A row is represented as a sequence of pixel
values, in left to right order.  An image is represented as a sequence
of rows, in top to bottom order.  If the sample format is Imd.Size_1BE,
then each row will be padded if necessary to make the size a multiple
of 8, so that each row will start on a byte boundary.

After processing the image header, the steps for decoding an image are:

    -- Set the output type.
    -- The variable Decoder is a pointer to the decoder structure.
    if Imd.Set_Output_Format(Decoder, Imd.RGB or Imd.Mapped or
                              Imd.Size_8 or Imd.Map_Size_8) = False then
	Ada.Text_IO.Put_Line("Cannot convert to mapped RGB format");
        raise ...;
    end if;

    -- Read the map (only do this for mapped output).
    declare
        type Map_Type is ...;
        type Map_Ptr is access all Map_Type;
    begin
        -- Allocate space for map.  The Sizeof_Map routine calculates
        -- the correct size.
        Map_Ptr := malloc(Imd.Sizeof_Map(Decoder));
        if Map_Ptr = null then raise Storage_Error; end if;

	-- Get the map.
        Imd.Get_Map(Decoder, Map_Ptr.all'Address);
        if Decoder.Error /= 0 then raise ...; end if;
        ...
    end;

    -- Read the entire image at once.
    declare
        type Image_Array is ...;
        type Image_Ptr is access all Image_Array;
    begin
	-- Allocate space for the image.  Imd.Sizeof_Image calculates
	-- the correct size.
        Image_Ptr := malloc(Imd.Sizeof_Image(Decoder));
        if Map_Ptr = null then raise Storage_Error; end if;

        -- Read the image.
        Imd.Get_Image(Decoder, Image_Ptr.all'Address);
        if Decoder.Error /= 0 then raise ...; end if;
        ...
    end;

If the application wants to read one row at a time, it uses something like:

    -- Read the image, one row at a time.
    if Imd.Start_Output(Decoder) = False then
	Ada.Text_IO.Put_Line("Cannot decode image");
        raise ...;
    end if;

    for Row_Number in 1 .. Decoder.Height loop
        declare
            type Row is ...;
            package Row_Acc is new System.Address_To_Access_Conversions(Row);
            Row_Ptr : Row_Acc.Object_Ptr;
        begin
            -- Read one row.  Read_Row returns a pointer to the
            -- row, which is stored in a block of memory allocated
            -- by the library.
            Row_Ptr := Row_Acc.To_Pointer(Imd.Read_Row(Decoder));
            ...
        end;
    end loop;
    -- Check for error.  We could have done this inside the loop.
    if Decoder.Error /= 0 then raise ...; end if;

For Imd.RGB + Imd.Size_8 output, the Row type could be declared as

    type Primary is (Red, Green, Blue);
    type Pixel is array (Primary) of Interfaces.Unsigned_8;
    type Row is array(1 .. Decoder.Width) of Pixel;

But in C you would probably do the equivalent of

    type Row is array (Natural) of Interfaces.Unsigned_8;

Thanks for any ideas.
		                Kenneth Almquist

Re: Representing image data

[Gautier]

Kenneth Almquist wrote:

> I've been working on the design of an image decoding library.  The
> basic idea is that the library will examine the first few bytes of
> an image, determine the format, and call the appropriate decoder,
> so that an application using the library can read images without
> writing code for each image format it wants to handle.

How common are the formats' encodings ? JPEG, PNG, BMP, GIF, TGA, PPM... ?
Compressed ? With/without loss ? Not compressed ?
There are various libraries, full Ada (at least for BMP, GIF, TGA & PPM) 
or bindings, which support these usual formats. Could be a good starting 
point, and you also could use them for the "back-end" jobs.

HTH
_________________________________________________________
Gautier's Ada programming -- http://sf.net/users/gdemont/
NB: For a direct answer, e-mail address on the Web site!

Re: Representing image data

[Srini -]

a good starting point might be ImageMagick. There is an Ada binding
even though somewhat dormant.

HTH
On Mar 10, 9:16 pm, Gautier <gaut...@fakeaddress.nil> wrote:
> Kenneth Almquist wrote:
> > I've been working on the design of an image decoding library.  The
> > basic idea is that the library will examine the first few bytes of
> > an image, determine the format, and call the appropriate decoder,
> > so that an application using the library can read images without
> > writing code for each image format it wants to handle.
>
> How common are the formats' encodings ? JPEG, PNG, BMP, GIF, TGA, PPM... ?
> Compressed ? With/without loss ? Not compressed ?
> There are various libraries, full Ada (at least for BMP, GIF, TGA & PPM)
> or bindings, which support these usual formats. Could be a good starting
> point, and you also could use them for the "back-end" jobs.
>
> HTH
> _________________________________________________________
> Gautier's Ada programming --http://sf.net/users/gdemont/
> NB: For a direct answer, e-mail address on the Web site!

Re: Representing image data

[Dmitry A. Kazakov]

On Tue, 10 Mar 2009 21:26:29 GMT, Kenneth Almquist wrote:

> I've been working on the design of an image decoding library.  The
> basic idea is that the library will examine the first few bytes of
> an image, determine the format, and call the appropriate decoder,
> so that an application using the library can read images without
> writing code for each image format it wants to handle.
> 
> I'm looking for suggestions on what the Ada interface to the
> library should look like--and in particular how the image contents
> should be provided to the application using the library.  The current
> design has a C interface with no type checking on the image data.

What sort of applications have you in mind? Digital filtration? Pattern
recognition? Scene analysis? Rendering? 3D simulation? ... Depending on the
application image representation format may vary.

In any case there should be no "malloc" stuff as in your example.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Representing image data

[Brian Drummond]

On Wed, 11 Mar 2009 10:00:27 +0100, "Dmitry A. Kazakov"
<mailbox@dmitry-kazakov.de> wrote:

>On Tue, 10 Mar 2009 21:26:29 GMT, Kenneth Almquist wrote:
>
>> I've been working on the design of an image decoding library.  The
>> basic idea is that the library will examine the first few bytes of
>> an image, determine the format, and call the appropriate decoder,
>> so that an application using the library can read images without
>> writing code for each image format it wants to handle.
>> 
>> I'm looking for suggestions on what the Ada interface to the
>> library should look like--and in particular how the image contents
>> should be provided to the application using the library.  The current
>> design has a C interface with no type checking on the image data.
>
>What sort of applications have you in mind? Digital filtration? Pattern
>recognition? Scene analysis? Rendering? 3D simulation? ... Depending on the
>application image representation format may vary.
>
>In any case there should be no "malloc" stuff as in your example.

I would suggest ditto on the access types. And on most of the "if ... null then
raise ..." These are a consequence of trying to replicate C in Ada instead of
actually using the language.

>>    declare
>>        type Image_Array is ...;
>>        type Image_Ptr is access all Image_Array;
          -- declares a type rather than a variable, surely?
>>    begin
>>        Image_Ptr := malloc(Imd.Sizeof_Image(Decoder));
>>        if Map_Ptr = null then raise Storage_Error; end if;
...
>>        Imd.Get_Image(Decoder, Image_Ptr.all'Address);

I have been using the following style. I'm posting it here (a) to point the OP
away from writing C in Ada and (b) on the age-old Usenet principle that the best
way to elicit a smart answer is to post a dumb one...

    declare
        type Image_Array is ...;
        Image : Image_Array(1 to Imd.Sizeof_Image(Decoder));
	-- The image size is unknown until runtime, but cannot vary within 
	-- this declare...begin...end block
        -- a real solution is 2D? but 2D arrays were not C's strong point
        -- as Dmitry says, image representation format may vary.
    begin
	-- Space is already allocated or exception raised by this point

        -- Read the image.
        Imd.Get_Image(Decoder, Image);	-- Image is an OUT parameter

        -- Process the image
        for i in Image'range loop
            -- process each Image(i)
        end loop
    end;

This won't work for very large images (like 1GB) with Gnat on its standard
settings (if the stack size is exceeded it'll just raise Storage_Error).
There are apparently means of setting its stack space allocation but I haven't
had any luck with them.

You can explicitly set the stack size for any task other than the main task, but
creating a task just to set stack size would be absurd, so I resorted to a
pointer...

    declare
        type Image_Array is ...;
        type Image_Ptr is access all Image_Array;
        Image_P : Image_Ptr := new Image_Array(1 to Imd.Sizeof_Image(Decoder));
        Image : Image_Array renames Image_P.all;
        -- now the loop body need never know about the pointer.
        -- It works without change whether or not you use a pointer.
    begin
        -- Read the image.
        Imd.Get_Image(Decoder, Image);	-- Image is an OUT parameter
        -- Process the image

	-- in my application, this scope was the end of the main program.
        -- Other cases may need to free(Image_P) here?
    end;

If there are better ways of accomplishing this I'm interested to hear them.

- Brian

Re: Representing image data

[sjw]

On Mar 11, 3:45 pm, Brian Drummond <brian_drumm...@btconnect.com>
wrote:

> You can explicitly set the stack size for any task other than the main task, but
> creating a task just to set stack size would be absurd, so I resorted to a
> pointer...

If you need a larger stack for some reason that can't be obviated by
using dynamic object allocation then creating an appropriate task is
the obvious way ... I needed to call an XML processing library that
needed >0.5 MB stack, using a task was the only way I could think of.
Worked a treat.

Re: Representing image data

[Kenneth Almquist]

Thanks for the responses.

> What sort of applications have you in mind?

Ideally, any application that uses raster image data.  The idea behind
row-at-a-time mode is that the application will read the data in each
row and store it in a format appropriate for the application.

The ability to read an entire image at once is based on the assumption
that the result will in a useable format for a lot of applications,
but that may be more true in C, where we are concerned with binary
compatibility rather than logical compatibility between types.

> There are various libraries, full Ada (at least for BMP, GIF, TGA & PPM) 
> or bindings, which support these usual formats.

I found ImageMagick, which Srini mentioned, and found two more libraries
listed on www.adapower.com.  Any suggestions of where else to look?

With ImageMagick the only way to change the pixel format is to
recompile the library, so the interface doesn't have to deal with
multiple pixel formats.  It uses Interfaces.C.Pointers to enable the
interface to return a pointer to an array of pixels; a solution that
the documentation acknowledges isn't very good.

PNG-IO, which reads PNG files, has functions to access the sample values:

    function Pixel_Value(F : PNG_File; R, C : Coordinate) return Natural;
    function   Red_Value(F : PNG_File; R, C : Coordinate) return Natural;
    function Green_Value(F : PNG_File; R, C : Coordinate) return Natural;
    function  Blue_Value(F : PNG_File; R, C : Coordinate) return Natural;
    function Alpha_Value(F : PNG_File; R, C : Coordinate) return Natural;

These functions are inlined, but require a fair amount of computation
because their behavior depends on the attributes of the image, which
have to be checked every call.

Open-image has declarations for the various pixel types, which seems
to be a workable approach, but I have to think about it some more.

			    Kenneth Almquist

Re: Representing image data

[tmoran]

CLAW (which is for Windows) uses children of a root tagged type for
the different pixel representations. Thus
    type VGA_DIBitmap_Type (Height, Width : Claw.Int) is
        new Basic_DIBitmap_Type (Height, Width) with record ...
and
    type RGB555_DIBitmap_Type (Height, Width : Claw.Int) is
        new Basic_DIBitmap_Type (Height, Width) with record ...
with appropriate procedures for Windows system calls.

Writing takes a classwide parameter so it can write any format,
and Read is a function returning a classwide type.

If the application is always dealing with one kind - 24 bit RGB, say,
then it can be written to efficiently deal with only that.  If it
must handle several kinds it can use the same mechanism to make
a routine that efficiently does something with 24 bit RGB bitmaps,
another routine if it's a 555 RGB bitmap, etc and let dispatching
call the right one.  So what code to use for different kinds of pixels
is decided at the bitmap level, not again and again for each pixel.

Re: Representing image data

[Randy Brukardt]

"Gautier" <gautier@fakeaddress.nil> wrote in message 
news:49b71100$1_6@news.bluewin.ch...
> Kenneth Almquist wrote:
>> I've been working on the design of an image decoding library.  The
>> basic idea is that the library will examine the first few bytes of
>> an image, determine the format, and call the appropriate decoder,
>> so that an application using the library can read images without
>> writing code for each image format it wants to handle.
>
> How common are the formats' encodings ? JPEG, PNG, BMP, GIF, TGA, PPM... ?
> Compressed ? With/without loss ? Not compressed ?
> There are various libraries, full Ada (at least for BMP, GIF, TGA & PPM) 
> or bindings, which support these usual formats. Could be a good starting 
> point, and you also could use them for the "back-end" jobs.

I agree. Claw has a package ("Claw.Bitmaps") for handling Windows bitmaps, 
which seem to cover roughly the same ground as the OP said. I'm not sure 
off-hand which half of Claw that is in; it might only be in the commercial 
version. My recollection was that it was rugged job, but that mainly 
happened because we wanted it to be a set of type extensions (one for each 
major format), and mapping that to an existing format *and* remaining 
portable to many different Ada compilers was a lot of fun. (I think we 
pulled it off, though.)

                                 Randy.

Re: Representing image data

[Brian Drummond]

On Wed, 11 Mar 2009 13:12:38 -0700 (PDT), sjw <simon.j.wright@mac.com> wrote:

>On Mar 11, 3:45�pm, Brian Drummond <brian_drumm...@btconnect.com>
>wrote:
>
>> You can explicitly set the stack size for any task other than the main task, but
>> creating a task just to set stack size would be absurd, so I resorted to a
>> pointer...
>
>If you need a larger stack for some reason that can't be obviated by
>using dynamic object allocation then creating an appropriate task is
>the obvious way ... I needed to call an XML processing library that
>needed >0.5 MB stack, using a task was the only way I could think of.
>Worked a treat.

Thanks. Good to know I wasn't completely crazy for contemplating it, 
though in this specific case I think it would have been overkill.

- Brian

Re: Representing image data

[Kenneth Almquist]

Here is my latest version of the row-at-a-time interface.

First, sample values are best thought of as integer types rather than
modular types, so we shouldn't use the Unsigned types from the
Interfaces package even though they have the right type.  Instead,
we declare:

    type Sample_8 is range 0 .. 2**8 - 1;
    type Sample_16 is range 0 .. 2**16 - 1;

The size of these types defaults to 8 and 16, respectively, so no
size clauses are necessary.  An application could use these types
in to represent sample values throughout the application, or could
perform type conversions on the individual samples.

To make fetching rows type safe, we declare a generic package for
each possible type.  For example, to read an RGB image with 8 bits
per sample, one could write:

    declare
        package Rows is new Imd.RGB_8(Decoder);
        Row : Rows.Row_Ptr;
    begin
        for Row_Number in 1 .. Decoder.Height loop
            Rows.Get_Row(Row);
            for Column_Number in Row.all'Range loop
                Store_Pixel(Row_Number, Column_Number,
                            Row.all(Column_Number).Red,
                            Row.all(Column_Number).Green,
                            Row.all(Column_Number).Blue);
            end loop;
        end loop;
    end;

The Store_Pixel routine is a stand-in for whatever processing the
application wants to do on the pixel values.  This code ignores the
problem of error handling.

The Get_Row procedure produces a pointer to the next row.  It would
be possible to make it produce the contents of the row rather than
a pointer, but there doesn't seem to be a strong case for doing that.
The application code would be marginally simpler because the references
to "Row.all" would change to "Row".  It would also be marginally slower
because of the extra copying.

The Imd.RGB_8 package is defined an implemented as follows:

    generic
        Decoder : Decoder_State;
    package Imd.RGB_8 is

        -- Elaborating an instantation of this package will initialize
        -- the decoding of the image sample data.
        pragma Elaborate_Body;

        type Pixel is record
            Red : Sample_8;
            Green : Sample_8;
            Blue : Sample_8;
        end record;
        pragma Pack(Pixel);

        type Row_Array is array (Integer range 1 .. Decoder.Width) of Pixel;
        type Row_Ptr is access all Row_Array;

        -- Get_Row - Get the next row.  Each call to Get_Row generates a
        -- new row and returns a pointer to the row.  If an error occurs,
        -- Get_Row will set the error flag in the Decoder structure and
        -- continue processing, producing row data that may not be meaningful.
        procedure Get_Row(Row : out Row_Ptr);
        pragma Inline(Get_Row);

    end Imd.RGB_8;


    -- generic
    --    Decoder : Decoder_State;
    package body Imd.RGB_8 is

        function Imd_Read_Row(Decoder : Decoder_State) return Row_Ptr;
        pragma Import(C, Imd_Read_Row, "imd_read_row");

        procedure Imd_Start_Read(Decoder : Decoder_State);
        pragma Import(C, Imd_Start_Read, "imd_start_read");

        procedure Get_Row(Row : out Row_Ptr) is
        begin
            Row := Imd_Read_Row(Decoder);
        end Get_Row;

    begin
        Imd.Set_Output_Format(Decoder, RGB + Size_8);
        Imd_Start_Read(Decoder);
    end Imd.RGB_8;

We have to define a separate generic package for each pixel format
and sample size.  If the meaning of the samples is not known, the
package to use is Imd.Any_8 or Imd.Any_16, which defines the pixel
type as:

        type Pixel is array (Integer range 1 .. Decoder.Samples_Per_Pixel)
            of Sample_16;
        pragma Pack(Pixel);

This package could be used for any image type.

For mapped data, two generic instantiations are required

    declare
        package Map_Def is new Imd.Map_RGB_16(Decoder)
        package Rows is new Imd.Map_8(Decoder);
        Map : Map_Def.Map_Ptr;
        Row : Rows.Row_Ptr;
    begin
        Map_Def.Get_Map(Map);
        [loop through rows here]
    end;

Using two generic instantiations reduces the number of generic packages
required.  The first defines the type of the map, and the second
defines the type of the pixel samples that refer to the entries in
the map.

This scheme requires about 28 generic packages.
				    Kenneth Almquist