so my first ever computer video i think
it was my first ever one my first ever
computer file video was on digital
images and really what i was talking
about was how we represented image in
memory but a little bit of that was
about multi-dimensional arrays because
images are multi-dimensional arrays now
obviously a lot of my research is around
deep learning we actually see
multi-dimensional arrays quite a lot in
deep learning and they can get four or
five and more dimensional depending on
what kind of data you're looking at
um and so what i wanted to talk about
today was the kind of nifty way
we represent these
in the computer because of course memory
is we don't represent memory in a
multi-dimensional array it's just linear
address space so how do we map from five
dimensions down to one very very quickly
so that we can perform all this very
very fast deep learning on it
if you use any kind of numerical library
so for example numpy or matlab or r or
any of the tensor libraries like
tensorflow or pi torch they have
multi-dimensional arrays in them so
pytorch you calls them tensors tend to
flow chords and tensors and they are the
kind of the building block of your deep
network they represent the data that
you're passing around and these tensors
are often quite large and multiple they
have multiple dimensions right so maybe
five dimensions or four dimensions is
quite common because these are actually
represented in memory as a linear array
we have to decide how to actually index
them quite quickly and the whole point
of these libraries is they're really
really fast right no one's going to be
able to train a deep network if you're
spending ages copying array bits around
and moving things around it has to be
super quick let's start with a really
basic definition of a two-dimensional
array right which is kind of going back
to our first video and talking about an
image right so i'm going to talk about
images because that's what i'd spend
most of my time doing actually it
doesn't really matter what data you're
representing right it's just a
multi-dimensional array so let's imagine
that we have an image which is currently
gray scale right so it's a little box
and it has this is y and this is x and
let's say it's 100 pixels by 100 pixels
a quick sub in my head suggests to me
that there's probably 10 000 pixels in
this image and each one has some value
now we don't actually store in ram 100
by 100 that doesn't make sense we store
a 1 by 10 000 array and we have to make
sure that when we want a specific pixel
we jump to the right point so what we
need to define is a few items so we're
going to define a size of the array
right and that's going to be 100 by 100.
i'm starting on the right we'll see
later as i add more dimensions all right
so if i'm going to run out of space
um and then we have an offset which is
going to be
zero now that offset is where do we
start in our memory space now you might
change the offset if you're doing
certain operations we're not going to
talk about them at the moment so we're
just going to keep that at zero and then
we have our stride i mentioned this in
my original video what we use is
something called a stride which is the
width of a row of an image bearing in
mind any padding and that depends on the
file format the stride represents how
far we have to go in memory to get to
the next one of a certain dimension
right so in this case to go from one x
to the next x
is just one pixel across right so that's
going to be a stride of one to get from
one row to the next row we have to go
100 pixels along and wrap around to the
next one and so that's going to be a
stride of 100 so suppose we want to find
the fourth row
in this image what we would do is we
would do four times by the y stride and
that would give us the index
into the fourth row in terms of memory
it's just going along a long list to the
right point so this list is one long
list and we're jumping to the correct
position for that row and then we can
read the x values off the way i've
written this here is kind of general so
we can add a dimension to this so let's
imagine we no longer have just one
grayscale channel we have three channels
for rg and b right now i'm going to
represent this
as additional channels forming another
dimension at the back here so this is
our g and b so we have three of these in
this direction so this is our sort of
channel dimension you could say it's z
but if we're going to add more
dimensions let's not run out of letters
too quickly so to do this what we have
to do is we have to add another entry
into our size and another entry into our
stride so to go from one row to the next
is moving 100 pixels but to go from one
image to the next or one channel to the
next is going to be a hundred times 100
pixels which is 10 000. so that's our
stride for this next dimension along
and the size in this dimension is going
to be three
and that makes sense obviously i've just
added three dimensions because i've
added them behind like this i've sort of
messed it up i'm going to have to
reallocate memory and this is going to
sort of get reset as it were so our
offset is still zero but our new origin
point is this one here and we're moving
this way i just think it's easier to see
them coming this way rather than i mean
this this hour's pointing the wrong way
but we won't dwell on it so y x and then
either z or channel or whatever it is
you want so offset is still zero so this
is going to be here right so this is the
very origin of our data and as we move
along in memory we're going to go down
through this first image then we're
going to go to the next image we're
going to go down through this image into
the next image and down through this
image all the way to the end suppose we
want to find out what the index for some
row in the middle channel is what we
have to do is we have to do so this is
the first index
into the channel so it's 1 times 10 000
plus your row times 100 plus your x
times one and that will give you the
exact point in memory in linear memory
for the pixel on the second plane we're
going to run out of space i tried not to
but it's going to happen right so let's
imagine we want to add another dimension
right so now we don't have a xy image
which has three channels we have a
number of xy images that have three
channels but they're all represented in
the same place in memory they each have
their location so
we'll get we'll get some drawing going
and this is going to be the next one
well that's just bad uh
and then i'm in this way like this and
it comes off the screen
we know what we will ignore this one
because it's off the page and we're not
going to be able to draw properly on it
so we're going to start our offset here
now this is our new offset but this is
our position in memory of the first
pixel in all of our data right and this
is the next dimension going this way and
then you've got the channel dimension
and then you've got the x and y
dimensions going this way
we need bigger paper right for all my
dimensions i'm gonna have to add another
stride and another size in here so this
happens to be three as well so we're
gonna add another size of three to go
through each of these dimensions is ten
thousand and there are three of them so
it's going to be ten thousand times
three it's thirty thousand we're going
to need to jump between each of these
indexes in this dimension so this is
going to be 30 000 like this so now if
we want to jump to this one we go 0 1 2
in that dimension times 30 000 plus
whichever channel we want times ten
thousand plus the y and the x and we can
go right to exactly where we want but
the thing to remember is that this is
always when it's declared this way
always just one long line in memory now
we can fiddle about with a stride in the
offset and stuff and do clever things
that'll be perhaps for another time so
we'll add another dimension right so now
we're in five dimensions now i don't
like to think i don't know how to
visualize five dimensions i just think
of it as
groups of groups of groups you know
because that's how i see it in my mind
because that's just how it is in memory
so now we're going to add another one i
should have added fewer dimensions it
would have taken me less time to draw
maybe i can get this one more square
than the one before still a little
square
right so now this is our next dimension
coming down this way so this is now five
dimensional now i haven't got room for
my stride but this stride is going to be
30 000 times by another three which is
90 000 so i'm just going to put 90k in
here and the size is going to be 2 in
this dimension right and the offset is
now
this position here right which is the
beginning of all of our data i'm just
coming this direction that's why you
could add more dimensions in sort of any
direction if you wanted to now so if i
want to go down in this dimension i'm
going to have to do 0 1 times by 90 000
plus 1 times 30 000 and so on and i can
jump straight to the exact position i
want in memory now this is actually
surprising there's a few things about
this that make it very very quick the
first is that actually
each plane of data so each image channel
is actually contiguous in memory almost
all the time there are things you can do
with offsets and strides and so on to
mess around with that property but for
the sake of argument if this is
contiguous in memory copying to and from
it very very quick doing operations on
these channels very very quick so you
can say to let's say some layer in a
convolutional network you can say do me
a matrix multiplication on this little
bit here through all these channels and
it will go off and it will do that and
it can look in the correct place in
memory based on all of these values
right so we don't have to copy that
anywhere else and process it we can just
use this thing and just look into it
which is a super neat way of looking
into this kind of size of data and you
can have as many um
dimensions as you want it really makes
no difference it's just about how many
entries you have in the size and the
stride lists and basically which one you
multiply by what dimension and so on
and then so all that you do when you're
increasing the bit depth is giving more
different increments in between that's
yes that's exactly right it's unlikely
that you would use it to um show even
brighter red because
usually 255 would mean as as red as you
could get let's say so you would just
have a finer range of colors in between