>> We'll turn it over to Alex Pinkney now.
So, to introduce the next guest, he's [INDISTINCT] familiar group here at DocEng with the University
of Nottingham.
And just like there's a steering committee and a program committee for DocEng, this is
nice because with Alex here, we have a member of the program committee to join Matthew and
Steven Bagley and myself on the steering committee of the people who bag on David Brailsford
behind his back.
So, it's a kind of analogous to the conference in general and this would be our last talk
in the afternoon.
>> PINKNEY: All right.
Thanks Steve.
Okay.
So hopefully, the title will become apparent as I go into talk because it's very long.
Okay.
As we all know, I'm sure, electronic documents are essentially--in fact, they are ubiquitous
nowadays.
There's loads of devices that you can do them on, I've seen a few iPads around, people who've
got kindles, you can view things on your mobile phone.
Many of these are battery powered.
Oh, Sorry.
Okay.
So, many of these devices are now a battery powered so--and also, unlike the--ten years
ago, Microsoft brought out a tablet PC; never really caught on iPads, really, you see them
everywhere nowadays.
So, we can really broadly categorize documents into two formats.
There's PDF-like documents, there's HTML-like documents.
So, HTML documents tend to--well, their appearance is very much dependent on the rendering device,
whereas PDF documents are essentially render independent every--any PDF document will pay
the same regardless of what it's rendered on, an HTML document can look vastly different
depending on what device you do it on, or what program you're using to view it.
Consequently, PDF documents have very fixed layouts and there's really no way of making
them flowable with the current paradigm.
An HTML documents can be fit into any screen size and that's fine, but another consequence
of this is that, HTML documents look bad and it's difficult to impart a good typography
on them and PDF documents can look very good.
So, these two document paradigms existed for the last 20 years or so, and as Joe Morelock
was saying yesterday, it's time for a new format or something has got to change because
HTML is--it doesn't work very well, it doesn't look nice.
PDF, although it looks nice, you're stuck with one fixed size document.
So, why don't we just improve HTML renderers?
Well, we could.
But, typesetting is complex.
The Line Breaking Algorithm developed by Knuth Plass runs in polynomial time and the actual
algorithm used by Tech is even more complex than the generic, Knuth Plass one.
So, this is very slow to run the fly, so if you have your kindle and you want to use the
Knuth Plass to break the lines, it's going to--it's going to be slow.
And you may have used Adobe InDesign and have edited some text and quite--it's quite notable
how--if you're asked to re-calculate hyphenation point to cylinder, it's quite slow.
It's not a quick process.
So currently, eBook readers will use this "late" processing.
So, rather than the document being compiled, all the hard works done beforehand, we've
now moved the hard work to the view time of the document.
So, we're basically--all the work is now being done at run time and
that's not ideal because as I said before, these devices are battery powered.
It's going to run your battery out.
So, what can we do instead of this?
Well, we should probably take a lesson from history.
So until around 30 years ago, newspapers were still being hand-typeset and as Fabio was
saying, there's galleys.
So, I'm using the term galleys slightly differently to Fabio.
He was using it as the actual contents area.
When I use the term galley, I'm specifically referring to some text as being set into this
area and is fixed.
So, in any case, newspaper text could be set into long galleys so essentially, effectively
one long column.
This could be easily broken between lines to fit into the final newspaper layout.
So, an article could be continued on another page or another column on the same page.
So, it's simple to flow effectively flow this text into other places without needing to
expensively re-typeset it.
So, if we do pre-render the document text into galleys like this and have each line
independently rendable, it makes layout very simple.
We can just lay the text out line by line and if we run out of space or if the--we can
either move to another--the text can be paginated to a new page or if the content space is wide
enough, we can layout a text in multiple columns.
This still doesn't quite work, however.
It only fits on a very limited subsets of screen sizes.
Now, as the page width increases, which is along the bottom here, well, as the width
gets to--the width of one galley, we can then fit in one column.
Now this graph is showing the extra white space that is being inserted on the page to
fit two columns then.
So, as we get to--as we get from--so, the width--we've got--the page is the width of
one galley.
As we increase it, the extra white space goes up and then, we get [INDISTINCT] as we increase
the page width.
So--well, we thought well, why not embed several galley renderings into the document so we
can embed, say five or six different width galleys into the document, all of the same
content.
And readability studies have suggested that around 30 to 80 characters per line is a sensible
amount and, you know, I can still follow it to that point.
So, at layout time, we can choose the most appropriate galley width which can be based
on some function of the screen width.
If we want to change the point size, we can just scale a small galley up to create a larger
point size or scale a large galley down to reduce the point size.
And layout of view time now is linear and that is based on the number of lines on the
page [INDISTINCT] it's not the number of words, or the number of letters so it's very, very
simple.
And we've now shifted over "Heavy Lifting" for the document back to the compile time.
So, it's pretty much trivial to render the document on the device now.
So, here's just a visual example of how a very short document could be rendered into
three different galley widths.
So, there's a narrow one here, slightly wider one, and even wider one.
So, each of these gray boxes can wrap into line of text, we can just lay these lines
out.
You don't need--obviously you choose the most appropriate one of the three to display depending
on how wide your page is or how wide your screen is.
So, we need some methods of choosing which galley width to render.
Now, we decided that we would like to penalize extra white space on the page but try to favor
fewer columns.
So, if five columns--five narrow columns will fit on the page with the same amount of extra
wide spaces as three wider columns, we'd rather have the three wider columns.
So, our penalty is fairly simple, it's essentially the white space--the extra white space required
to be inserted, multiplied by the square root of the number of columns.
This is just an operated choice, it's a factor which is small than linear so, hopefully,
if the factor is linear or larger, we'd--this sort of pattern would tend to wander off upwards.
Now, if we--well, okay.
I'll explain what this line is showing.
This particular line is showing the penalty for a galley which is 15 m wide at varying
page widths.
So, if we insert for more galleys which is slightly wider well, we can overlay these
penalties.
And the way we choose the galleys is to simply pick the smallest penalty at any given point.
Okay, so this graph is in the paper, it's--hopefully, this should explain how I created this graph.
Essentially, we've just picked the lowest point of the upper graph and displayed on
this low graph here.
And the color--the color matches up with the 15, 18, 21, and 24 m column width.
So, as we increase the page size, we'll flip between the galley renderings, and the number
of columns will change at each of these transition points.
So, within these colored bars, we'll just be adding extra white space but, other transitions
will flip to a new number of columns.
So, how do we implement this?
Well, currently we are using PDF as a container, and it runs inside ACROBAT with a custom plug-in.
The reason we're doing this is because at Nottingham, we've got pre-existing tools for
creating modular PDF.
My [INDISTINCT] Steve Bagley has written a [INDISTINCT] of tools known as--what's called
COG PDF, he has presented it at Dochenge several times before which we just use to encapsulate
the document component so the lines of the lines of the galleys.
I have to modify this to embed the paragraph structure within the document so that we can
always keep track of which line belongs to which paragraph, so we know where to insert
extra space.
And if the page slides changes we know where--we know roughly where to continue to--just laying
the document if we're on a second page.
So, that current plug-in just lays out the lines according to the page size and the paragraph
structure which is embedded in the document.
So, here's a few examples, now this is an iPhone size screen.
We can drag the window slightly bigger into a kindle size.
You could see it's chosen a wider column.
This is how it might look in an iPAD.
It splits into two columns.
If you turn the iPAD landscape, we've now got three columns.
We can make the screen look bigger, so this is approaching a PC size screen.
Slightly bigger again, well, it's chosen a wider column variant, a bit bigger well, if
you decided that these--the more narrow columns is more appropriate here.
So--yeah.
The actual metric, the penalty we've created may not be the best, we can work on it.
But it's just--it's a preview concept really.
So, to extend this, we may be able to not treat the galleys as totally concrete, we
may have to tweak the justifications slightly.
So, we can include hints which can be passed to the renderer to change the word spacing,
the letter spacing, or even the glyph width to some extent.
Also, currently the system doesn't really allow tight phases to be altered but then
neither the PDF's, and neither the actual real books.
So--but we could potentially render it in multiple typefaces spaces.
Obviously, it had to be a limited selection but, if it was needed for accessibility for
example, it wouldn't be a problem.
And also, it may turn out to be wise for us to tailor documents to specific device profiles,
so we could provide image different resolutions or an appropriate range of galley width renderings.
And obviously, we could look at more exhaustic layout options than just laying out texting
columns.
So, we could allow images or figures to be span of multiple columns.
We can allow arbitry layout with--using something like Adobe's CSS regent model, or we could
use any of the examples we've seen yesterday and today as long as they're not too costly
because then we lose the benefit of pre-rendering our lines.
And obviously, we need to implement this in a really big platform because at present--well,
it's very nice having it run on ACROBAT on a PC but it's not very practical or useful.
So, in summary--well, the system allows us to shift all the hard work from the viewing
device back to the document and compilation time.
But, we still got referability, and obviously unlike an HTML based, e-book the author and
publisher can see every rendering of their document, so, that is high quality control
for them.
And really, we're trying to work towards a truly portable document format.
Thank you very much.
>> So, there's a really good review paper a couple of years ago and it mentioned a paper
by Hirschberg and Lemor, which gives a linear time algorithm implementation of the take
line breaking algorithm.
Given that, and the fact that the CPU's on even the smallest, cheapest devices are getting
much faster, and almost all the time is spent doing the graphic layout rather than the computing
and the positions, I think you need to keep going with your research.
I think you need to think a bit bigger before you get settled down too much in this area.
Like, I think you need to think way over this.
>> PINKNEY: Okay.
>> It's not really a question.
>> PINKNEY: Yes, that's what I was going to say.
I haven't actually read that paper, I mean, I should probably should now.
But, yeah, I'll take your feedback on both, thanks.
>> So, you compared the PDF model to the HTML model but, I think there's a model in between,
it's called SVG.
With SVG you can render line by line.
You can switch between two--so, it looks like it could...
>> PINKNEY: Well, you can, but if you want to work out good places for line breaks it's
still as expensive as the HTML model >> I understood that you do your line break
beforehand, right?
>> PINKNEY: Yes, the line breaking hyphenation, you can insert ligatures were required.
You can curtain things properly.
>> Yes, so you did that on the server.
>> PINKNEY: Well, yeah.
When the documents are compiled, yes.
>> Yes.
So, you can do that processing on the server produce SVG that's pre-rendered, and then
just render the SVG >> PINKNEY: Well, I can.
That's another way of doing it but, I mean, we've done it in PDF, there's no particular
reason for that just because everything...
>> Yeah, yes a practical reason...
>> PINKNEY: ...well, we can do it in SVG.
But, I don't think the model--the galley based model has really been exploited before or
not in this way as far as I'm aware.
>> Thank you.
>> Okay.
Any other questions for the speaker?
All right, let's give him a hand.