Tip:
Highlight text to annotate it
X
>> 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.