Using Space Effectively: 2D II
From CS 294-10 Visualization Sp10
Lecture on Mar 1, 2010
- A general cartographic labeling algorithm, Edmondson, Marks & Shieber (pdf)
- A survey of automated layout techniques for information presentations, Lok and Feiner (pdf)
- Dynamic space management for user interfaces, Bell & Feiner (pdf)
- Rendering effective routemaps, Agrawala & Stolte (pdf)
- Artistic resizing, Dragicevic et al. (pdf)
- Adaptive grid-based document layout, Jacobs et al. (acm)
- Map labeling bibliography
RyanGreenberg - Feb 27, 2010 07:13:52 pm
I thought the Edmondson, Marks, and Shieber article was quite clear in its explanation. As I was reading I thought of a couple of advantages to their approach to this problem. First, their system compartmentalizes most of the domain-specific knowledge (what makes a good label) in the rating procedure. Although they noted some overlapping uses of domain knowledge (e.g. the algorithm suggesting possible label position tries to avoid obvious bad positions), the compartmentalization makes optimization easier. Another advantage of this approach is that it can be easily modified to accomodate different preferences for labeling (e.g. based on culture). If people in some regions think that labels on the left or below point features are better, no problem--we can just change the rating procedure to reflect that.
I'm not familiar with the simulated annealing algorithm presented here. Does anyone have a concise explanation for why a worse labeling is undone with P = 1.0-exp(-deltaE/T) instead of just undone (page 3, step d)?
Jeffrey Patzer - Mar 01, 2010 10:42:18 am
I found Lok and Stevens' discussion of "Automated Layout Techniques for Information Presentations" quite interesting. The idea that you can create a system that replicates what a graphic designer commonly does is extremely powerful. While I think that the graphic designer's job is not in danger, the idea that the currently complicated techniques could become simple techniques allows the average user to create more effective layouts. I think after reading about the various layout systems and that most layouts require to be reduced to spatial layouts, I am surprised to see that some of these techniques have not been applied to OS window layout systems. To be more precise, considering that windows on my computer all have a spatial relationship it would seem logical to include an option to automatically tile the windows. Something kind of like what aligns icons on my desktop, except that it allows me to automatically arrange the windows open on my screen. While windows does provide a basic functionality for this by dragging windows to the edge of the screen, I think it might be even more useful to provide a higher level function.
Arpad Kovacs - Mar 01, 2010 02:39:50 pm
I found the Edmondson, Marks & Shieber paper about label placement optimalization techniques very useful. It effectively casts label placement as a constaint satisfaction problem, where the constraints are aesthetic principles such as minimizing feature overlap, finding the optimal orientation and distance, resulting in maximum readability and usability.
I found the point-positioning metrics such as the recommendations to place labels above, to the right of, and with horizontally-aligned baselines to their respective points to be very interesting. However, I am curious whether the suggestion to place labels to the right only holds in countries that read left-to-right, and not in cultures that read right-to-left (eg Arabic nations and Israel).
Another concern is how the LineOver overlap metric can be applied in maps such as Google Maps, where the text is embedded within a street (eg the entire text overlaps with a line). In this case, it seems that the contrast between the text and line must also be taken into account, rather than just the placement.
Jon Barron - Mar 01, 2010 05:09:00 pm
Cartographic Labeling: I spent some time as an undergrad considering this problem and gave up when I realized it was basically np-hard, so I appreciate how difficult what they're trying to do here is. This does indeed seem like the framework that I would expect the "ultimate solution" to be within, as they say, though it's strange that they spend so much time dismissing simulating annealing methods only to use simulated annealing themselves. You've got to admire the effort that went into crafting some of these metrics (swath lines?!). My only questions are: what were people doing before this paper, and what did people do after this paper? Seems like a pretty definitive work.
Automated Layout: This paper is a huge letdown after the first one. Almost zero algorithmic content, and no empirical comparison between algorithms.
Dynamic Space Management: This paper seems to have one very clever idea at its core, that of keeping track of contiguous sections of empty space, and explicitly calculating the chunks of empty space that are created when an object is added. The rest of the paper seems very strange, and might just be a ad hoc approximation to the simulated annealing technique in the first paper, or might be a weird recreation of depth first search. Certainly, it could benefit from being rephrased in a search or optimization framework. What's the cost function that is being optimized?
Zev Winkelman - Mar 05, 2010 03:24:46 pm
Edmondson and Christensen: Found this algorithm to be very interesting, especially as continue to work with more and more 'crowded' visualizations. I considered using it to place labels on close or overlapping lines in an xy line chart, but decided against it as the appropriate technique.
Bell and Feiner: Made me think of the feature in osx (and other os's too now - I don't use it though, and I don't know the name of the feature either) which zooms out on all open windows and arranges them neatly.
Agrawala and Stolte: While traveling once I was given one of these computer-generated-to-look-like-a-hand-drawn-map maps, but the distances on the roads were not labeled despite their distortion. I can assure you that without those labels, my ability to navigate using that map was severely impaired. I thought the intersection detection was the most interesting piece of this paper.
Dragicevic, Chatty, Thevenin, and Vinot: I had fun imagining the inter/intra departmental effects this paper could have as graphic designers and programmers battle it out for who should be doing what. Have not worked in such an environment myself. Are the lines well drawn or blurry ? Contentious ?
Akshay Kannan - Mar 06, 2010 12:09:19 pm
Having had to struggle with many labeling issues with Tableau, I realize the difficulty with writing an effective labeling algorithm, and I enjoyed the paper on this. Like most traditional AI problems, depth-first search is not the optimal approach. Some of the other methods discussed in this paper, such as force-directed labeling and simulated annealing, are shown to be more effective strategies. Especially in crowded layouts in which labels need to be placed as effectively as possible, I liked the idea of minimizing feature overlap in order to allow text to be readable even when it needs to overlap features of the map. Also, in terms of optimization, while a highly-effective algorithm may not be necessary for a one-time procedure such as labeling an atlas, a fast algorithm would be especially effective for a tool such as Google Earth to dynamically generate maps for users. The Lok and Feiner paper on automated UI placement seemed to be a powerful approach along similar lines. Automatic UI design is definitely a very powerful, although it seems as though in the foreseeable future there will always be a need for human designers.
Stephen Chu - Mar 07, 2010 06:35:51 pm
Cartographic labeling: Reading this made me wonder how Google labels efficiently and optimally with Google Maps. They seem to have at least partially solved the problems of flexibility and selectivity that are mentioned in the paper's summary. Flexibility: Rotating the view in street view curves the street labels to be more aligned with the road. Selectivity: Labels are filtered and selected automatically when zooming in and out).
Layout survey: This paper mentions that visualization techniques can borrow from NLP and computational biology algorithms. I never realized before this class how closely linked HCI is to AI.
Ebby Amirebrahimi - Mar 08, 2010 02:33:08 am
Edmondson, Christiensen: i've always thought automated labeling is a much harder problem than it would seem initially, and it is very frustrating to deal with. Most of the time, I'm tempted to not worry about it and just have the user suffer. However, it was very nice to see this Cartographic Labeling algorithm hashed out. It certainly is a very tricky problem and I enjoyed seeing their various approaches to the problem followed by a solution that seems to account for all the annoying tidbits necessary for good labeling.
Bell & Feiner: I enjoyed the topic, as I feel like too many UI's do a poor job of presenting multiple sets of information on a screen. Their algorithm seems fairly similar to the windowing systems used in osx and Windows. I definitely think there could be more improvement in this area though. I feel like UIs work better when they give a sense of depth, which is why I find osx easier to use than Windows, which takes a more 2d approach to the display on windows on the screen. However, I'm not sure if that's true for everyone, since I've spoken to many who can't stand the messy collection of windows that accumulate on a typical osx desktop.
Mason Smith - Mar 08, 2010 12:50:21 pm
Bell & Feiner: For what the paper tries to accomplish, I think the algorithms presented are appropriate. For interactive visualizations, for instance, that present lots of data in relatively small chunks, this seems like a great idea. However, some of the use cases the paper presents seem contrived. The window manager, in particular, strikes me as impractical for a number of reasons. The envisioned user in the paper relies on managing lots of smaller windows, which is out of step with what most computer users actually do. Even in nominally MDI applications (MS Office, etc.), open documents need to be relatively large to merit being open, obviating the need for advanced layout. Modern (tiling and non-tiling) windowing systems accept this inevitability and employ virtual desktops/workspaces to handle the more typical use case of a few large windows, rather than many small ones.
Kerstin Keller - Mar 08, 2010 01:42:03 pm
In class we talked about the fisheye and other zooming techniques and everybody thought it was a bad idea. But I wonder if a technique like that could improve google maps for example. I often find myself wanting to zoom into a certain area, say the bay area. I then start on the map of the US, zoom in a little, have to center the map to where I want to zoom in further. If there was like a fisheye magnifying glass tool which you can look where the the right area is, that allowed you to then zoom into the just magnified area, I think that would be an useful application.
Prahalika Reddy - Mar 10, 2010 04:55:55 am
There were several topics in this lecture that I found very interesting...
The idea of nomograms is quite fascinating to me. I've never learned about them before, but I think it's pretty cool to be able to do a mathematical calculation just by drawing a line, based on how the visualization was drawn. It makes the entire problem (whatever problem the visualization was trying to calculate) much easier on the user.
Also displayed in the "graphical calculations" portion of this lecture was the famous french train schedule. We've seen it before several times as a good example of a visualization, but I actually really dislike this schedule. To me, it's very confusing and drawn very poorly. However, I assume it was very good for its time since it was effective in showing the pattern of the trains, but as an actual visualization, I think it's very busy and hard to read.
The zooming video we watched was also very interesting. It was pretty cool to see how much and how little some things change at such huge distances. I thought it was especially interesting to see that when the distance jumps were smaller (from a 10^1 box to and 10^2 box), there was a greater change in what we could see than when the distance jumps were bigger (like from a 10^6 box to a 10^7 box).
The last part of the lecture, distortions, was also very informational. I don't really like distortions in any visualizations. I think there's usually a better way to convey the same information (such as shading or color). Especially on a map, it's very hard to even distinguish what the base image is (like in the US map shown in class). In addition, using distortions to showcase a specific portion of a visualization also doesn't seem very effective, since everything on the border is usually unreadable.
Priyanka Reddy - Mar 10, 2010 08:42:45 am
I had been curious about how expose on macs worked, but hadn't really thought too much about it. The Bell and Feiner paper gave me good insights on how it might work, although arguably expose is a much simpler version of what they're trying to do. One thing I found interesting in the paper is their idea of allowing empty spaces to be overlapping. I don't think it's something that people immediately think to do, but after you hear about it, you can see that it makes sense to do it this way.
I think the idea for Excentric labels is a good one. It allows for extensive labeling of the information that the user is most interested in without cluttering the graph. However, one feature I think is necessary when labeling is done this way is the ability to free a certain set of labels even after the mouse moves away. In my experience using Firebug, I've found this to be a necessary feature.
Jonathan Yen - Mar 11, 2010 05:39:13 pm
The Dynamic Space Management for User Interfaces paper was pretty interesting, and in general, I think the whole concept of allocation and arrangement of elements on the screen dynamically has quite a bit more to be explored. The readings brought to mind the Expose feature that's currently present in Mac OS X, which is a really neat way of trying to sort through the multiple applications and windows that one has on their computer. I'd be interested to know if there's a way to just automatically create an aesthetically pleasing user interface without much human intervention. It'd require that the computer would need to know how to visualize negative space and for the computer to "see" the interplay of different elements on the screen.
Shimul - Mar 15, 2010 03:58:22 am
The reading on cartographic labeling was interesting. Flatness/closeness/length etc are useful features to worry about while labeling a figure/map. The article on space management seemed a little vague to me. I find it hard to understand how exactly the algorithms for effective space management work. The applications for the technology seem interesting though. From lecture, I like the concept of parallel coordinates - they seem to be a very effective way of representing multi-dimensional datasets. The video on zooming was nicely done - it was a good watch despite its ancient feel. Interactive zooming is a good way to show perspective while displaying data whose dimension varies over a broad spectrum.
Boaz Avital - Mar 15, 2010 02:11:45 pm
It shows how complex visualizations can be when something as seemingly simple as label placement has to be handled with artificial intelligence techniques. It seems to me that the most difficult part of solving a problem like this is accurately defining the problem and quantitatively measuring what makes a good or bad label position. There are so many factors that they found to go into it, it seems like quite a mental exercise.
A window manager that moves windows around using overlap-avoidance, while perhaps useful, seems like a poor interface in terms of usability. I doubt people will be able to predict just where the windows will go if you overlap, and so every time you drag a window to overlap another window it will take you a few extra seconds to locate the new position of the automatically moved windows.