A Frame over an n-dimensional array is a specified n-dimensional hyper-rectangular shape
that can have its anchor dynamically placed at a position within
the array, where the frame's anchor is a specified point relative to the coordinate system
of the shape. The hyper-rectangle of the underlying array covered by the shape when anchored
at a position, is called the frame's current window. For example, if A is a 10x10x10 array,
and F is a frame with a 4x4x4 shape and an anchor of (0,2,-2),
then if F is placed is at coordinate (0,0,0) of A, its window is the sub-array
A[0..3][-2..1][2..5]
and if F is placed at coordinate (5,5,5) of a, then its window is the sub-array
A[5..8][3..6][7..10].
Note carefully, that (a) the anchor need not be in the window's boundary, and (b) in both
examples the window is not entirely within A. Conceptually
when a frame is placed at coordinate c within A, it is the anchor an that is being
placed at that coordinate, and therefore the origin of the shape is being placed at
c−an. When the window is not within the boundary of A then the
current boundary effect is used to fill in the values outside of A's boundary,
so that a frame in any position is effectively an array of a given shape.
The type and scale of a frame are that of its underlying array. The kind of a frame
is the same as its underlying array except that it is PLAIN_KIND if its window's
outer dimension does not match that of an RGB_KIND or RGBA_KIND array, or if
its window's innermost dimension does not match that of a COMPLEX_KIND array.
This class has the full complement of conventional class primitives save that reading
and writing are not available as a frame is intrinsically short lived.
Frames, along with Arrays and Slices, are considered array forms that are modeled
in Mylib by the class AForm. These three separate classes all model a rectangular lattice of
values in n-dimensions and hence many of the routines in the Mylib library operate on
AForms as opposed to a specific one of the three types. The major purpose of
a frame is to allow a user to apply an operation or a routine to a small, dynamically-positioned
rectangular sub-region of an array and its implicit boundary as determined by the
current boundary effect. A frame should never be too big. Unlike a slice it consumes an
amount of memory proportional to its shape's size! In effect a frame is a smallish slice
that can be moved around and need not be within the underlying array's boundary.
As an example, one may want the entropy around every point in an array within a small region.
To do so one can ask for the Histogram at each point within the frame's window and then ask
for its entropy. Suppose A is a UINT8_TYPE array, then the code below realizes the
example:
Frame *f;
Histogram *h;
Indx_Type p;
double ent;
h = Make_Histogram(UVAL,256,VALU(1),VALU(0));
f = Make_Frame(A,Coord3(5,5,5),Coord3(2,2,2));
Place_Frame(f,0);
for (p = 0; p < A->size; p++)
{ Histagain_Array(h,f,0);
ent = Histogram_Entropy(h);
// ... do something with ent = the entropy in a 5x5x5 shape about p
Move_Frame_Forward(f);
}
Free_Frame(f);
Free_Histogram(h);
As another example,
the Frame class was used to realize the Convolver class that performs brute-force convolutions
of a region with a specified filter of the same shape.
A Frame maintains a current position that is an index into its underlying array along with
auxiliary information so that one can efficiently more the frame forward and backward across
the elements of an array. While the window of a frame need not lie in the array, its current
position must be an index inside the range of the array.
A frame is created with Make_Frame, and its shape, anchor, current position/index, and
coordinate (int the underlying array) for the current position can be retrieved with
Frame_Shape, Frame_Anchor, Frame_Index, and Frame_Coordinate. Note that a frame is
an opaque object, i.e. unlike say an Array, you cannot directly access any of its fields.
As mentioned previously a frame is an AForm and as such it is guaranteed to have
an underlying array, kind, size, and shape which can be fetched with
AForm_Array, AForm_Kind, AForm_Kind, and AForm_Shape. Moreover, you
can ask if an array form is a slice via AForm_Class or Is_Slice.
One can set the current position, increase it by 1, decrease it by 1, and ask if the
window for the current position lies entirely within the boundaries of the underlying
array with Place_Frame, Move_Frame_Forward, Move_Frame_Backward, and Frame_Within_Array.
All the routines are O(1) expected time except for Place_Frame which take time proportional
to the dimensionality of the frame.
While many routines in Mylib operate directly on a frame, there will be occasions where
one needs to work directly with the values in the current window in order to compute something
not realized in the library.
There are two ways to get the values in the current window of a frame. The simplist
is to call Frame_Values that returns a
void
pointer to a vector holding the elements of the window. For example, the code fragment
below computes the sum of the elements in the window of a frame F whose underlying array
is of INT32_TYPE
int i, sum, *data;
sum = 0;
data = (int32 *) Frame_Values(F);
for (i = 0; i < AForm_Size(F); i++)
sum += data[i];
// sum = the sum of the values in F's current window
Note that the number of elements in the window is obtained with AForm_Size(F). While
not important for the example above, the elements of the current window are laid out in
data exactly as if the window were a small array.
While Frame_Values above is as efficient as it can be, it has to compute boundary elements
when the current window is not within the underlying array and it has to fill a vector
holding all the current window's elements. Hence it takes time proportional to the size of
the window.
To attain more efficiency, please note that when the frame's window is completely within
the array then the elements of the window are all in the array at a fixed offsets from the
current position.
The key is that the offsets are the same, regardless of the movement or position of the
frame. Frame_Offsets returns a pointer to this pre-computed offset vector for any given
frame. The vector of offsets depends on the shape of the window and the shape of the underlying
array, but it is computed once when the frame is created, and thereafter remains fixed.
So a much more efficient template for computing the sum in the example would be:
Offs_Type *offs = Frame_Offsets(F);
sum = 0;
if (Frame_Within_Array(F))
{ data = (int *) AINT32(AForm_Array(F))) + Frame_Index(F);
for (i = 0; i < AForm_Size(F); i++)
sum += data[offs[i]];
}
else
{ data = (int32 *) Frame_Values(F);
for (i = 0; i < AForm_Size(F); i++)
sum += data[i];
}
The efficiency is due to (a) the fact that most of the time, a frame is completely inside
its array (e.g. for a 512 x 512 x 512 array and a 11 x 11 x 11 window with an anchor in its
center, if you place the frame at every position in the array, then the window is not inside
the array only .216% of the time), and (b) only O(1) time is spent getting ready for the summation
loop in the case the window is in the frame, whereas, when Frame_Values is called it has
to compute boundary elements as well as fill in a vector of size AForm_Size(F).
The trade off is that twice as much code is required, so employing this optimization depends on
how critical the time for a computation is. All the routines in Mylib that compute on
AForms optimize their handling of Frames in this way.
Finally, one can create an Array, say A, that has the shape and values of the current window
of a frame with Make_Array_From_Frame. Frame_Array fills in the Array_Bundle passed to
it so that it is functionally equivalent to A, albeit the bundle can only be used in a read
only fashion and is invalid as soon as any change is made to the frame. The data field
of the returned bundle points at the vector returned by a call to Frame_Values.
Routine Documentation
Return true if and only if the frame's window is currently entirely within the underlying
array.
Return an untyped pointer to a vector that contains the values of the current window of f.
The vector belongs to the frame and is reused by it as needed. The values in the vector
are only good until the next call to Frame_Values. The number of elements in the vector
is equal to the size of the shape of f, i.e. AForm_Size(f), and the order of elements
is the same as if the window were an array and this was its data vector.
Return a vector of offsets relative to the current position of all the elements in the
underlying array. This vector is computed once upon creation of the f and all this routine
does is return a pointer to it. The offsets only make sense when the window is inside the
boundary of the array. Please see the example in the detailed description above for how
this vector of offsets can be used to realize efficient computations over frames.
The number of elements in the vector
is equal to the size of the shape of f, i.e. AForm_Size(f), and the order of offsets
is the same as if the window were an array and this was its data vector.
Generate an array whose shape and value is that modeled by the current window of the
frame f. The array has the kind (as returned by AForm_Kind), type, and scale
of the frame.