Organizing digital photograph collections according to events such as holiday gatherings or vacations is a common practice among photographers. To support photographers in this task, we present similarity-based methods to cluster digital photos by time and image content. The approach is general, unsupervised, and makes minimal assumptions regarding the structure or statistics of the photo collection. We present several variants of an automatic unsupervised algorithm to partition a collection of digital photographs based either on temporal similarity alone, or on temporal and content-based similarity. First, inter-photo similarity is quantified at multiple temporal scales to identify likely event clusters. Second, the final clusters are determined according to one of three clustering goodness criteria. The clustering criteria trade off computational complexity and performance. We also describe a supervised clustering method based on learning vector quantization. Finally, we review the results of an experimental evaluation of the proposed algorithms and existing approaches on two test collections.

Parallel changes are a basic fact of modern software development. Where previously we looked at prima facie interference, here we investigate a less direct form that we call semantic interference. We reduce the forms of semantic interference that we are interested in to overlapping def-use pairs. Using program slicing and data flow analysis, we present algorithms for detecting semantic interference for both concurrent changes (allowed in optimistic version management systems) and sequential parallel changes (supported in pessimistic version management systems), and for changes that are both immediate and distant in time. We provide these algorithms for changes that are additions, showing that interference caused by deletions can be detected by considering the two sets of changes in reverse-time order.

Large video collections present a unique set of challenges to the search system designer. Text transcripts do not always provide an accurate index to the visual content, and the performance of visually based semantic extraction techniques is often inadequate for search tasks. The searcher must be relied upon to provide detailed judgment of the relevance of specific video segments. We describe a video search system that facilitates this user task by efficiently presenting search results in semantically meaningful units to simplify exploration of query results and query reformulation. We employ a story segmentation system and supporting user interface elements to effectively present query results at the story level. The system was tested in the 2004 TRECVID interactive search evaluations with very positive results.

A common problem with teleconferences is awkward turn-taking - particularly 'collisions,' whereby multiple parties inadvertently speak over each other due to communication delays. We propose a model for teleconference discussions including the effects of delays, and describe tools that can improve the quality of those interactions. We describe an interface to gently provide latency awareness, and to give advanced notice of 'incoming speech' to help participants avoid collisions. This is possible when codec latencies are significant, or when a low bandwidth side channel or out-of-band signaling is available with lower latency than the primary video channel. We report on results of simulations, and of experiments carried out with transpacific meetings, that demonstrate these tools can improve the quality of teleconference discussions.

The FXPAL photo application automatically organizes digital photo collections based on date, event, person, or place.

A convenient representation of a video segment is a single keyframe. Keyframes are widely used in applications such as non-linear browsing and video editing. With existing methods of keyframe selection, similar video segments result in very similar keyframes, with the drawback that actual differences between the segments may be obscured. We present methods for keyframe selection based on two criteria: capturing the similarity to the represented segment, and preserving the differences from other segment keyframes, so that different segments will have visually distinct representations. We present two discriminative keyframe selection methods, and an example of experimental results.

This paper presents an information-driven online video composition system. The composition work handled by the system includes dynamically setting multiple pan/tilt/zoom (PTZ) cameras to proper poses and selecting the best close-up view for passive viewers. The main idea of the composition system is to maximize captured video information with limited cameras. Unlike video composition based on heuristic rules, our video composition is formulated as a process of minimizing distortions between ideal signals (i.e. signals with infinite spatial-temporal resolution) and displayed signals. The formulation is consistent with many well-known empirical approaches widely used in previous systems and may provide analytical explanations to those approaches. Moreover, it provides a novel approach for studying video composition tasks systematically. The composition system allows each user to select a personal close-up view. It manages PTZ cameras and a video switcher based on both signal characteristics and users' view selections. Additionally, it can automate the video composition process based on past users' view-selections when immediate selections are not available. We demonstrate the performance of this system with real meetings.

We present a search interface for large video collections with time-aligned text transcripts. The system is designed for users such as intelligence analysts that need to quickly find video clips relevant to a topic expressed in text and images. A key component of the system is a powerful and flexible user interface that incorporates dynamic visualizations of the underlying multimedia objects. The interface displays search results in ranked sets of story keyframe collages, and lets users explore the shots in a story. By adapting the keyframe collages based on query relevance and indicating which portions of the video have already been explored, we enable users to quickly find relevant sections. We tested our system as part of the NIST TRECVID interactive search evaluation, and found that our user interface enabled users to find more relevant results within the allotted time than those of many systems employing more sophisticated analysis techniques.

Presentation of FXPAL experiments in the 2004 TREC Video Retrieval Evaluations (TRECVID 2004). FXPAL participated in the shot boundary determination task, and the interactive search task.

Proactive contextual information systems help people locate information by automatically suggesting potentially relevant resources based on their current tasks or interests. Such systems are becoming increasingly popular, but designing user interfaces that effectively communicate recommended information is a challenge: the interface must be unobtrusive, yet communicate enough information at the right time to provide value to the user. In this paper we describe our experience with the FXPAL Bar, a proactive information system designed to provide contextual access to corporate and personal resources. In particular, we present three features designed to communicate proactive recommendations more effectively: translucent recommendation windows increase the user's awareness of particularly highly-ranked recommendations, query term highlighting communicates the relationship between a recommended document and the user's current context, and a novel recommendation digest function allows users to return to the most relevant previously recommended resources. We present empirical evidence supporting our design decisions and relate lessons learned for other designers of contextual recommendation systems.

For some years, our group at FX Palo Alto Laboratory has been developing technologies to support meeting recording, collaboration, and videoconferencing. This paper presents several systems that use video as an active interface, allowing remote devices and information to be accessed "through the screen." For example, SPEC enables collaborative and automatic camera control through an active video window. The NoteLook system allows a user to grab an image from a computer display, annotate it with digital ink, then drag it to that or a different display. The ePIC system facilitates natural control of multi-display and multi-device presentation spaces, while the iLight system allows remote users to "draw" with light on a local object. All our systems serve as platforms for researching more sophisticated algorithms to support additional functionality and ease of use.

In this paper, we compare several recent approaches to video segmentation using pairwise similarity. We first review and contrast the approaches within the common framework of similarity analysis and kernel correlation. We then combine these approaches with non-parametric supervised classification for shot boundary detection. Finally, we discuss comparative experimental results using the 2002 TRECVID shot boundary detection test collection.

In this paper, we describe the YeTi information sharing system that has been designed to foster community building through informal digital content sharing. The YeTi system is a general information parsing, hosting and distribution infrastructure, with interfaces designed for individual and public content reading. In this paper we describe the YeTi public display interface, with a particular focus on tools we have designed to provide lightweight awareness of others' interactions with and interest in posted content. Our tools augment content with metadata that reflect people's reading of content - captured video clips of who's reading and interacting with content, tools to allow people to leave explicit freehand annotations about content, and a visualization of the content access history to show when content is interacted with. Results from an initial evaluation are presented and discussed.

As the size of the typical personal digital photo collection reaches well into the thousands or photos, advanced tools to manage these large collections are more and more necessary. In this demonstration, we present a semi-automatic approach that opportunistically takes advantage of the current state-of-the-art technology in face detection and recognition and combines it with user interface techniques to facilitate the task of labeling people in photos. We show how we use an accurate face detector to automatically extract faces from photos. Instead of having a less accurate face recognizer classify faces, we use it to sort faces by their similarity to a face model. We demonstrate our photo application that uses the extracted faces as UI proxies for actions on the underlying photos along with the sorting strategy to identify candidate faces for quick and easy face labeling.

We developed a novel technique for creating visually pleasing collages from photo regions. The technique is called "stained glass" because the resulting collage with irregular shapes is reminiscent of a stained glass window. The collages reuse photos in novel ways to present photos with faces that can be printed, included in Web pages, or shared via email. The poster describes the requirements for creating stained glass visualizations from photos of faces, our approach for creating face stained glass, and techniques used to improve the aesthetics and flexibility of the stained glass generation. Early user feedback with face stained glass have been very positive.

We present an installation that allows distributed internet participants to "draw" on a public scene using light. The iLight system is a camera/projector system designed for remote collaboration. Using a familiar digital drawing interface, remote users "draw" on a live video image of a real-life object or scene. Graphics drawn by the user are then projected onto the scene, where they are visible in the camera image. Because camera distortions are corrected and the video is aligned with the image canvas, drawn graphics appear exactly where desired. Thus the remote users may harmlessly mark a physical object to serve their own their artistic and/or expressive needs. We also describe how local participants may interact with remote users through the projected images. Besides the intrinsic "neat factor" of action at a distance, this installation serves as an experiment in how multiple users from different locales and cultures can create a social space that interacts with a physical one, as well as raising issues of free expression in a non-destructive context.

With digital still cameras, users can easily collect thousands of photos. We have created a photo management application with the goal of making photo organization and browsing simple and quick, even for very large collections. A particular concern is the management of photos depicting people. We present a semi-automatic approach designed to facilitate the task of labeling photos with people that opportunistically takes advantage of the strengths of current state-of-the-art technology in face detection and recognition. In particular, an accurate face detector is used to automatically extract faces from photos while the less accurate face recognizer is used not to classify the detected faces, but to sort faces by their similarity to a chosen model. This sorting is used to present candidate faces within a user interface designed for quick and easy face labeling. We present results of a simulation of the usage model that demonstrate the improved ease that is achieved by our method.

In this demonstration, we are going to illustrate how to give a presentation using multiple displays connected to the Internet.

ePic is an integrated presentation authoring and playback system that makes it easy to use a wide range of devices installed in one or multiple multimedia venues.

Information sharing, computation and social interaction are main features of the Web that has enabled online communities to abound and flourish. However, this trend has not been coupled with the development of cues and browsing mechanisms for the social space. On the flip side, active contributors to social spaces (i.e., Web communities) lack the means to present a public face to visitors that can be important for social organizations. Social browsers that combine social visualization and tools can enable newcomers and visitors to view and explore information and patterns. We present two social browsers for two Web communities. The CHIplace People browser provides an abstract graphical view of the CHIplace community based on the self-described work roles of its membership. The Portkey eTree browser uses a life-like tree ecosystem metaphor to reflect the people, activities and discussions occurring on the Portkey Web site.

The preservation of literary hypertexts presents significant challenges if we are to ensure continued access to them as the underlying technology changes. Not only does such an effort involve standard digital preservation problems of representing and refreshing metadata, any constituent media types, and structure; hypertext preservation poses additional dimensions that arise from the work's on-screen appearance, its interactive behavior, and the ways a reader's interaction with the work is recorded. In this paper, we describe aspects of preservation introduced by literary hypertexts such as the need to reproduce their modes of interactivity and their means of capturing and using records of reading. We then suggest strategies for addressing the pragmatic dimensions of hypertext preservation and discuss their status within existing digital preservation schemes. Finally, we examine the possible roles various stakeholders within and outside of the hypertext community might assume, including several social and legal issues that stem from preservation.

A novel linguistically advanced text summarization system is described for reducing the minimum size of highly readable variable-sized summaries of digitized text documents produced by text summarization methods that use discourse analysis to rank sentences for in-clusion in the final summary. The basic algorithm used in FXPAL's PALSUMM text summarization system combines text structure methods that preserve readability and correct reference resolution with statistical methods to reduce overall summary length while promoting the inclusion of important material.

In this paper, we describe how the LIDAS System (Linguistic Discourse Analysis System), a discourse parser built as an implementation of the Unified Linguistic Discourse Model (U-LDM) uses information from sentential syntax and semantics along with lexical semantic information to build the Open Right Discourse Parse Tree (DPT) that serves as a representation of the structure of the discourse (Polanyi et al., 2004; Thione 2004a,b). More specifically, we discuss how discourse segmentation, sentence-level discourse parsing, and text-level discourse parsing depend on the relationship between sentential syntax and discourse. Specific discourse rules that use syntactic information are used to identify possible attachment points and attachment relations for each Basic Discourse Unit to the DPT.

In this paper, we introduce LiveTree, a core component of LIDAS, the Linguistic Discourse Analysis System for automatic discourse parsing with the Unified Linguistic Discourse Model. LiveTree is an integrated workbench for supervised and unsupervised creation, storage and manipulation of the discourse structure of text documents under the U-LDM. The LiveTree environment provides tools for manual and automatic U-LDM segmentation and discourse parsing. Document management, grammar testing, manipulation of discourse structures and creation and editing of discourse relations are also supported.

This paper presents a method for creating highly condensed video summaries called Stained-Glass visualizations. These are especially suitable for small displays on mobile devices. A morphological grouping technique is described for finding 3D regions of high activity or motion from a video embedded in x-y-t space. These regions determine areas in the keyframes, which can be subsumed in a more general geometric framework of germs and supports: germs are the areas of interest, and supports give the context. Algorithms for packing and laying out the germs are provided. Gaps between the germs are filled using a Voronoi-based method. Irregular shapes emerge, and the result looks like stained glass.

Using a machine to assist remote environment management can save people's time, effort, and traveling cost. This paper proposes a trainable mobile robot system, which allows people to watch a remote site through a set of cameras installed on the robot, drive the platform around, and control remote devices using mouse or pen based gestures performed in video windows. Furthermore, the robot can learn device operations when it is being used by humans. After being used for a while, the robot can automatically select device control interfaces, or launch a pre-defined operation sequence based on its sensory inputs.

Many conference rooms are now equipped with multiple multi-media devices, such as plasma displays and surrounding speakers, to enhance presentation quality. However, most existing presentation authoring tools are based on the one-display-and-one-speaker assumption, which makes it difficult to organize and playback a presentation dispatched to multiple devices, thus hinders users from taking full advantage of additional multimedia devices. In this paper, we propose and implement a tool to facilitate authoring and playback of a multi-channel presentation in a media devices distributed environment. The tool, named PreAuthor, provides an intuitive and visual way to author a multi-channel presentation by dragging and dropping "hyper-slides" on corresponding visual representations of various devices. PreAuthor supports "hyper-slide" synchronization among various output devices during preview and playback. It also offers multiple options for the presenter to view the presentation in a rendered image sequence, live video, 3D VRML model, or real environment.

For some years, our group at FX Palo Alto Laboratory has been developing technologies to support meeting recording, collaboration, and videoconferencing. This paper presents a few of our more interesting research directions. Many of our systems use a video image as an interface, allowing devices and information to be accessed "through the screen." For example, SPEC enables hybrid collaborative and automatic camera control through an active video window. The NoteLook system allows a user to grab an image from a computer display, annotate it with digital ink, then drag it to that or a different display, while automatically generating timestamps for later video review. The ePIC system allows natural use and control of multi-display and multi-device presentation spaces, and the iLight system allows remote users to "draw" with light on a local object. All our systems serve as platforms for researching more sophisticated algorithms that will hopefully support additional advanced functions and ease of use.

This paper presents a system designed to support note taking by students on wirelessly connected PDAs in a classroom. The system leverages the devices' wireless connectivity to allow students to share their notes in real time and quickly reuse words from their fellow note takers. In addition, presentation material such as Powerpoint slides is also extracted when presented by the instructor, giving students further means for reusing words. We describe the system and report our findings on an initial user study where the system was used for four months during a graduate level course.

FX Palo Alto Laboratory provides multimedia and information technology research for the Fuji Xerox corporation based in Tokyo, Japan. FXPAL's mission is to help Fuji Xerox with a digital information technology infrastructure to support services in Fuji Xerox's Open Office Frontier. Our research spans interactive media, immersive conferencing, social computing, mobile and adaptive computing, natural language inquiry, and emerging technologies such as quantum computing and bioinformatics. Our research methods combine determining user needs, inventing new technologies, building prototype systems, informing professional communities, and transferring technology to Fuji Xerox. The physical distance between our laboratory and our parent company makes it natural for us to research problems with collaborations across time zones and cultures. To address these problems, to test our ideas, and to prepare for technology transfers, we actively create prototype systems for interactive media, immersive conferencing, and social and mobile computing. We also foster collaboration with our Japanese colleagues through a combination of face-to-face visits and both synchronous and asynchronous remote communication.

We introduced detail-on-demand video as a simple type of hypervideo that allows users to watch short video segments and to follow hyperlinks to see additional detail. Such video lets users quickly access desired information without having to view the entire contents linearly. A challenge for presenting this type of video is to provide users with the appropriate affordances to understand the hypervideo structure and to navigate it effectively. Another challenge is to give authors tools that allow them to create good detail-on-demand video. Guided by user feedback, we iterated designs for a detail-on-demand video player. We also conducted two user studies to gain insight into people's understanding of hypervideo and to improve the user interface. We found that the interface design was tightly coupled to understanding hypervideo structure and that different designs greatly affected what parts of the video people accessed. The studies also suggested new guidelines for hypervideo authoring.

This article describes two years of experience with a research prototype for personalizing shared workplace devices such as projectors, public displays, and multi-function copiers. The system combines users' networked resources-or "personal information clouds"—with device-specific user interfaces for performing common device tasks. We developed and compared personal interfaces that are embedded (i.e., integrated or co-located with the shared device) and portable (i.e., accessible via personal devices such as mobile phones and PDAs). Our experience indicates that a little personalization can go a long way toward improving user friendliness, efficiency, and capabilities of shared document devices, helping them "weave themselves into the fabric of everyday life". We also gained important insights into subtle differences between embedded and portable approaches to ubiquitous computing systems.

In this paper we present recent developments in discourse theory and parsing under the Linguistic Discourse Model framework, a semantic theory of discourse structure. We give a novel approach to the problems of discourse segmentation based on discourse semantics and sketch a limited but robust approach to symbolic discourse parsing based on syntactic, semantic and lexical rules. To demonstrate the utilioty of the system in a real application, we briefly describe the architecture of the PALSUMM System, a symbolic smmarization system being developed at FX Palo Alto Laboratory that uses discourse structures constructed usding the theory otlined to summarize written English texts.

It is challenging to browse multimedia on mobile devices with small displays. We present MiniMedia Surfer, a prototype application for interactively searching a multimedia collection for video segments of interest. Transparent layers are used to support browsing subtasks: keyword query, exploration of results through keyframes, and playback of video. This layered interface smoothly blends the key tasks of the browsing process and deals with the small screen size. During exploration, the user can adjust the transparency levels of the layers using pen gestures. Details of the video segments are displayed in an expandable timeline that supports gestural interaction.

The Plasma Posters are large screen, digital, interactive posterboards designed for informal content sharing within teams, groups, organizations and communities. Leveraging the fact that the physical world is often used as a canvas for asynchronous information exchange via paper fliers and posters, the Plasma Posters provide a platform for sharing interactive digital content in public places. People serendipitously encounter multimedia content usually only encountered from the desktop, while going about their daily business. In this paper we describe the Plasma Poster interface in detail, and offer and overview of the underlying information authoring, parsing, storage, distribution and publishing infrastructure, the Plasma Poster Network. We report qualitative and quantitative data collected over 14 months of use that demonstrate the Plasma Posters have become an integral part of information sharing within our organization. We conclude the paper by reflecting on the patterns of adoption, and speculate on factors that have contributed to the system's success. Finally we briefly describe three other installations of the Plasma Poster Network and new interfaces that have been designed.

Collaborative note taking enables students in a class to take notes on their PDAs and share them with their "study group" in real-time. Students receive instructor's slides on their PDAs as they are displayed by the instructor. As the individual members of the group take notes pertaining to the slide being presented, their notes are automatically sent to all members of the group. In addition, to reduce their typing, students can use text they receive from other students and from the instructors slides to construct their notes. This system has been used in actual practice for a graduate level course on wireless mobile computing. In developing this system, special attention has been paid to the task of inputting text on PDAs, efficient use of the screen real estate, dynamics among students, privacy and ease of use issues.

In this paper, we present a framework for analyzing video using self-similarity. Video scenes are located by analyzing inter-frame similarity matrices. The approach is flexible to the choice of both feature parametrization and similarity measure and it is robust because the data is used to model itself. We present the approach and its application to shot boundary detection.

Our physical environment is increasingly filled with multimedia content on situated, community public displays. We are designing methods for people to post and acquire digital information to and from public digital displays, and to modify and annotate previously posted content to create publicly observable threads. We support in-the-moment and on-site "person-to-place-to-people-to-persons" content interaction, annotation, augmentation and publication. We draw design inspiration from field work observations of how people remove, modify and mark up paper postings. We present our initial designs in this arena, and some initial user reactions.

With the acceleration of technological development we are reaching the point where our systems and their user interfaces become to some degree outdated 'legacy systems' as soon as they are released. This raises the question of how can we maintain, extend, override, and adapt these systems while preserving what people depend on in them? In this paper we describe an approach for dynamically restructuring user interfaces into a set of communicating processes that 1) provide methods for changing their appearance, behavior, and state; and 2) report their proposed state changes so that other processes may override their actions in updating themselves to a new state. We do this for both new and wrapped legacy user interface components, thereby allowing us to repurpose user interfaces for our evolving needs. We describe how this approach has been successfully used in rapidly creating and deploying interfaces that repurpose content for new appearances and behaviors.

Blurring the boundary between the digital and physical in social activity spaces helps blend - and motivate - online and face-to-face community participation. This paper discusses two experimental installations of large screen displays at conferences - CHI 2002 and CSCW 2002. The displays offered a window in the conference arena onto online community information.

People routinely rely on physical and electronic systems to remind themselves of details regarding personal and organizational contacts. These systems include rolodexes, directories and contact databases. In order to access details regarding contacts, users must typically shift their attention from tasks they are performing to the contact system itself in order to manually look-up contacts. This paper presents an approach for automatically retrieving contacts based on users' current context. Results are presented to users in a manner that does not disrupt their tasks, but which allows them to access contact details with a single interaction. The approach promotes the discovery of new contacts that users may not have found otherwise and supports serendipity.

This edited volume brings together projects funded by, or related to, the European i3 initiative. Projects address the design, development and use of rich, digital information spaces for collocated and distributed collaboration.

Public and situated display technologies have an important impact on individual and social behaviour and present us with particular interesting new design considerations and challenges. While there is a growing body of research exploring these design considerations and social impacts this work remains somewhat disparate, making it difficult to assimilate in a coherent manner. This book brings together the perspective of key researchers in the area of public and situated display technology. The chapters detail research representing the social, technical and interactional aspects of public and sitauted display technologies. The underlying concern common to these chapters is how these displays can be best designed for collaboration, coordination, community building and mobility.

The sharing of digital materials within online communities has increased significantly in recent years. Our work focuses on promoting community information sharing in public spaces using large screen, interactive, digital poster boards called the Plasma Posters. In this chapter we first describe our fieldwork-led, iterative design process, and elaborate a number of design guidelines that resulted. Following this, the design and development of the Plasma Posters themselves and the underlying network infrastructure is discussed. Finally, we present results from qualitative and quantitative evaluations over the course of a ten-month deployment of three Plasma Posters within our own organization, a software research community made up of technologists and designers. We conclude with observations regarding ergonomic, social and other factors that were raised during the design and deployment and offer reflections on factors in the success of this deployment.

We describe a novel interface for presenting interactive content on public digital bulletin boards. Inspired by paper fliers on physical bulletin boards, posted content is displayed using 3D virtual fliers attached to a virtual corkboard by virtual pushpins. Fliers appear in different orientations, creating an attractive, informal look, and have autonomous behaviors like fluttering in the wind. Passers-by can rotate, move and fold fliers; they can also interact with fliers' live content. Flier content is streamed from a server and represented by the system on large screen displays using a real-time cloth simulation algorithm. We describe our prototype, and offer the results of an initial evaluative user study.

We present similarity-based methods to cluster digital photos by time and image content. The approach is general, unsupervised, and makes minimal assumptions regarding the structure or statistics of the photo collection. We present results for the algorithm based solely on temporal similarity, and jointly on temporal and content-based similarity. We also describe a supervised algorithm based on learning vector quantization. Finally, we include experimental results for the proposed algorithms and several competing approaches on two test collections.

We present a system that allows remote and local participants to control devices in a meeting environment using mouse or pen based gestures "through" video windows. Unlike state-of-the-art device control interfaces that require interaction with text commands, buttons, or other artificial symbols, our approach allows users to interact with devices through live video of the environment. This naturally extends our video supported pan/tilt/zoom (PTZ) camera control system, by allowing gestures in video windows to control not only PTZ cameras, but also other devices visible in video images. For example, an authorized meeting participant can show a presentation on a screen by dragging the file on a personal laptop and dropping it on the video image of the presentation screen. This paper presents the system architecture, implementation tradeoffs, and various meeting control scenarios.