1 and 2d image representations

1 and 2d image representations

[Richard Beare]

Hi all,

I'm writing some image processing software and I'm concerned about my
use of arrays. Obviously there are a number of options. My images are
not all the same size, but they don't change size, so I can use
something like

type Image is array (Postive range <>, Positive range <>) of Pixel;

however this doesn't allow me to take slices, which can be useful.

An array of array accesses makes this possible (obviously in one
direction only).

type Row is array (Positive range <>) of Pixel;
type H_Row is access Row;

type Image is array (Positive range <>) of H_Row;


Alternatively it is possible to represent an image as a linear array
and provide functions to perform the mapping between 1 and 2
dimensions.

Is there a sensible way to provide both the 1 and 2 dimensional
views of the image. The linear array can be useful if interfacing
to C code. It also allows every pixel to be checked using a single
loop, rather than nested loops. The other structures are convenient
because they describe an image in a more natural way. Preserving Ada's
range checks on rows would also be an advantage.

Can anyone comment on the overhead of using a linear array and
functions to map from two dimensions to one (and vice versa).

Any advice appreciated.

-- 

Richard Beare
rbeare@eleceng.adelaide.edu.au

Re: 1 and 2d image representations

[Alan E & Carmel J Brain]

Richard Beare wrote:

> I'm writing some image processing software and I'm concerned about my
> use of arrays. 

> Alternatively it is possible to represent an image as a linear array
> and provide functions to perform the mapping between 1 and 2
> dimensions.
> 
> Is there a sensible way to provide both the 1 and 2 dimensional
> views of the image.

Sounds like a job for Representation clauses and Unchecked Conversion,
at first sight.

> Can anyone comment on the overhead of using a linear array and
> functions to map from two dimensions to one (and vice versa).

If performance is a big issue, then Unchecked Conversion really could be
the way to go. On many systems, the overhead is negligible. Trouble is,
of course, you can, depending on the compiler, optimise away all the
good things regarding boundary checking that Ada provides. It still
won't let you go outside the maximum size of the array, but internally,
it could.

-- 
aebrain@dynamite.com.au     <> <>    How doth the little Crocodile
| Alan & Carmel Brain|      xxxxx       Improve his shining tail?
| Canberra Australia |  xxxxxHxHxxxxxx _MMMMMMMMM_MMMMMMMMM
 abrain@cs.adfa.oz.au  o OO*O^^^^O*OO o oo     oo oo     oo  
                    By pulling MAERKLIN Wagons, in 1/220 Scale

Re: 1 and 2d image representations

[Samuel T. Harris]

Alan E & Carmel J Brain wrote:
> 
> Richard Beare wrote:
> 
> > I'm writing some image processing software and I'm concerned about my
> > use of arrays.
> 
> > Alternatively it is possible to represent an image as a linear array
> > and provide functions to perform the mapping between 1 and 2
> > dimensions.
> >
> > Is there a sensible way to provide both the 1 and 2 dimensional
> > views of the image.
> 
> Sounds like a job for Representation clauses and Unchecked Conversion,
> at first sight.
> 
> > Can anyone comment on the overhead of using a linear array and
> > functions to map from two dimensions to one (and vice versa).
> 
> If performance is a big issue, then Unchecked Conversion really could be
> the way to go. On many systems, the overhead is negligible. Trouble is,
> of course, you can, depending on the compiler, optimise away all the
> good things regarding boundary checking that Ada provides. It still
> won't let you go outside the maximum size of the array, but internally,
> it could.
> 

Even "negligible" overhead of unchecked_conversion on a large image
array can add up fast. As an alternative, whenever unchecked_conversion
can be used, one can also use a address representation clause to force
the destination object to reside "on top of" the source object thus
eliminating the need for unchecked_conversion. For example ...

type pixel is record
  red, green, blue : natural;
end record;

type image_2d is array (positive range <>, positive range <>) of pixel;

type image_1d is array (positive range <>) of pixel;

...

picture_2d : image_2d(1..100,1..100);

picture_1d : image_1d(1..picture_2d'length(1)*picture_2d'length(2));
for picture_1d'address use picture_2d'address; -- Ada 95
-- for picture_1d use at picture_2d'address; -- Ada 83

This provides dual functionality without ANY overhead costs
associated with unchecked_conversion. However, this is STATIC.
Dynamic associations can be made "on-the-fly" by declaring
picture_1d within a local declare block so it lives only
as long as required.

-- 
Samuel T. Harris, Senior Engineer
Hughes Training, Inc. - Houston Operations
2224 Bay Area Blvd. Houston, TX 77058-2099
"If you can make it, We can fake it!"

Re: 1 and 2d image representations

[Matthew Heaney]

In article <34556F0F.62B5@dynamite.com.au>, aebrain@dynamite.com.au wrote:


>If performance is a big issue, then Unchecked Conversion really could be
>the way to go.

In practice, you can reduce the overhead to zero by making careful use of
attributes when iterating over an array, for example

for Index in O'Range loop
   ... O (Index) ...
end loop;

There is no range check here, because Index is in the index subtype of O,
and therefore no check is necessary.

--------------------------------------------------------------------
Matthew Heaney
Software Development Consultant
<mailto:matthew_heaney@acm.org>
(818) 985-1271