Computer Sciences Commons^™

Document Binarization With Automatic Parameter Tuning, Nicholas Howe

Computer Science: Faculty Publications

Document analysis systems often begin with binarization as a first processing stage. Although numerous techniques for binarization have been proposed, the results produced can vary in quality and often prove sensitive to the settings of one or more control parameters. This paper examines a promising approach to binarization based upon simple principles, and shows that its success depends most significantly upon the values of two key parameters. It further describes an automatic technique for setting these parameters in a manner that tunes them to the individual image, yielding a final binarization algorithm that can cut total error by one-third with …

A 2-Chain Can Interlock With An Open 10-Chain, Bin Lu, Joseph O'Rourke, Jianyuan K. Zhong

Computer Science: Faculty Publications

Abstract. It is an open problem, posed in [3], to determine the minimal k such that an open flexible k-chain can interlock with a flexible 2-chain. It was first established in [5] that there is an open 16-chain in a trapezoid frame that achieves interlocking. This was subsequently improved in [6] to establish interlocking between a 2-chain and an open 11-chain. Here we improve that result once more, establishing interlocking between a 2-chain and a 10-chain. We present arguments that indicate that 10 is likely the minimum.

Part-Structured Inkball Models For One-Shot Handwritten Word Spotting, Nicholas Howe

Computer Science: Faculty Publications

Many document collections of historical interest are handwritten and lack transcripts. Scholars need tools for high-quality information retrieval in such environments, preferably without the burden of extensive system training. This paper presents a novel approach to word spotting designed for manuscripts or degraded print that requires minimal initial training. It can infer a generative word appearance model from a single instance, and then use the model to retrieve similar words from arbitrary documents. An approximation to the retrieval statistic runs efficiently on graphics processing hardware. Tested on two standard data sets, the method compares favorably with prior results.

Bipolar Quantum Logic Gates And Quantum Cellular Combinatorics – A Logical Extension To Quantum Entanglement, Wen-Ran Zhang

Computer Science: Faculty Publications

Based on bipolar dynamic logic (BDL) and bipolar quantum linear algebra (BQLA) this work introduces bipolar quantum logic gates and quantum cellular combinatorics with a logical interpretation to quantum entanglement. It is shown that: 1) BDL leads to logically definable causality and generic particle-antiparticle bipolar quantum entanglement; 2) BQLA makes composite atom-atom bipolar quantum entanglement reachable. Certain logical equivalence is identified between the new interpretation and established ones. A logical reversibility theorem is presented for ubiquitous quantum computing. Physical reversibility is briefly discussed. It is shown that a bipolar matrix can be either a modular generalization of a quantum logic …

Script-Based Story Matching For Cyberbullying Prevention, Jamie Macbeth, Hanna Adeyema, Henry Lieberman, Christopher Fry

Computer Science: Faculty Publications

While the Internet and social media help keep today’s youth better connected to their friends, family, and community, the same media are also the form of expression for an array of harmful social behaviors, such as cyberbullying and cyber-harassment. In this paper we present work in progress to develop intelligent interfaces to social media that use commonsense knowledge bases and automated narrative analyses of text communications between users to trigger selective interventions and prevent negative outcomes. While other approaches seek merely to classify the overall topic of the text, we try to match stories to finer-grained “scripts” that represent stereotypical …

Rigidity Analysis Of Protein Biological Assemblies And Periodic Crystal Structures, Filip Jagodzinski, Pamela Clark, Jessica Grant, Tiffany Liu, Samantha Monastra, Ileana Streinu

Computer Science: Faculty Publications

Background: We initiate in silico rigidity-theoretical studies of biological assemblies and small crystals for protein structures. The goal is to determine if, and how, the interactions among neighboring cells and subchains affect the flexibility of a molecule in its crystallized state. We use experimental X-ray crystallography data from the Protein Data Bank (PDB). The analysis relies on an effcient graph-based algorithm. Computational experiments were performed using new protein rigidity analysis tools available in the new release of our KINARI-Web server http:// kinari.cs.umass.edu. Results: We provide two types of results: on biological assemblies and on crystals. We found that when only …

Towards Accurate Modeling Of Noncovalent Interactions For Protein Rigidity Analysis, Naomi Fox, Ileana Streinu

Computer Science: Faculty Publications

Background: Protein rigidity analysis is an efficient computational method for extracting flexibility information from static, X-ray crystallography protein data. Atoms and bonds are modeled as a mechanical structure and analyzed with a fast graph-based algorithm, producing a decomposition of the flexible molecule into interconnected rigid clusters. The result depends critically on noncovalent atomic interactions, primarily on how hydrogen bonds and hydrophobic interactions are computed and modeled. Ongoing research points to the stringent need for benchmarking rigidity analysis software systems, towards the goal of increasing their accuracy and validating their results, either against each other and against biologically relevant (functional) parameters. …

Balancing Human And Machine Contributions In Human Computation Systems, R. Jordan Crouser, Alvitta Ottley, Remco Chang

Computer Science: Faculty Publications

Many interesting and successful human computation systems leverage the complementary computational strengths of both humans and machines to solve these problems. In this chapter, we examine Human Computation as a type of Human-Computer Collaboration—collaboration involving at least one human and at least one computational agent. We discuss recent advances in the open area of function allocation, and explore how to balance the contributions of humans and machines in computational systems. We then explore how human-computer collaborative strategies can be used to solve problems that are difficult or computationally infeasible for computers or humans alone.

Predicting Application Performance Using Supervised Learning On Communication Features, Nikhil Jain, Abhinav Bhatele, Michael P. Robson, Todd Gamblin, Laxmikant V. Kale

Computer Science: Faculty Publications

Task mapping on torus networks has traditionally focused on either reducing the maximum dilation or average number of hops per byte for messages in an application. These metrics make simplified assumptions about the cause of network congestion, and do not provide accurate correlation with execution time. Hence, these metrics cannot be used to reasonably predict or compare application performance for different mappings. In this paper, we attempt to model the performance of an application using communication data, such as the communication graph and network hardware counters. We use supervised learning algorithms, such as randomized decision trees, to correlate performance with …

An Affordance-Based Framework For Human Computation And Human-Computer Collaboration, R. Jordan Crouser, Remco Chang

Computer Science: Faculty Publications

Visual Analytics is “the science of analytical reasoning facilitated by visual interactive interfaces” [70]. The goal of this field is to develop tools and methodologies for approaching problems whose size and complexity render them intractable without the close coupling of both human and machine analysis. Researchers have explored this coupling in many venues: VAST, Vis, InfoVis, CHI, KDD, IUI, and more. While there have been myriad promising examples of human-computer collaboration, there exists no common language for comparing systems or describing the benefits afforded by designing for such collaboration. We argue that this area would benefit significantly from consensus about …

Interface Design For Unmanned Vehicle Supervision Through Hybrid Cognitive Task Analysis, Jamie C. Macbeth, M. L. Cummings, Luca F. Bertuccelli, Amit Surana

Computer Science: Faculty Publications

While there is currently significant interest in developing Unmanned Aerial Systems (UASs) that can be supervised by a single operator, the majority of these systems focus on Intelligence, Surveillance, and Reconnaissance (ISR) domains. One domain that has received significantly less attention is the use of multiple UASs to insert or extract supplies or people. To this end, MAVIES (Multi-Autonomous Vehicle Insertion-Extraction System) was developed to allow a single operator the ability to supervise a primary cargo Unmanned Aerial Vehicle (UAV) along with multiple scouting UAVs. This paper will detail the development of the design requirements generated through a Hybrid Cognitive …

Using Variable-Rate Alerting To Counter Boredom In Human Supervisory Control, Armen A. Mkrtchyan, Jamie C. Macbeth, Erin T. Solovey, Jason C. Ryan, M. L. Cummings

Computer Science: Faculty Publications

A low task load, long duration experiment was conducted to evaluate the impact of cyclical attention switching strategies on operator performance in supervisory domains. The impetus for such a study stems from the lack of prior work to improve human-system performance in low task load supervisory domains through the use of design interventions. In this study, a design intervention in the form of auditory alerts is introduced and the effects of the alerts are examined. The test bed consists of a video game-like simulation environment, which allows a single opera-tor the ability to supervise multiple unmanned vehicles. Each participant in …

String-Wrapped Rotating Disks, Joseph O'Rourke

Computer Science: Faculty Publications

Let the centers of a finite number of disjoint, closed disks be pinned to the plane, but with each free to rotate about its center. Given an arrangement of such disks with each labeled + or -, we investigate the question of whether they can be all wrapped by a single loop of string so that, when the string is taut and circulates, it rotates by friction all the ⊕-disks counterclockwise and all the ⊖-disks clockwise, without any string-rubbing conflicts. We show that although this is not always possible, natural disk-separation conditions guarantee a solution. We also characterize the hexagonal …

Towards Sequence-Based Dna Flexibility Analysis, Emily Flynn, Filip Jagodzinski, Ileana Streinu

Computer Science: Faculty Publications

In this poster, we present an extension to our freely available KINARI-Web server to identify rigid and flexible regions of nucleic acids and protein-nucleic acid complexes contained in the Protein Data Bank (PDB). The goal is to explore the effect of DNA and RNA on the rigidity and stability of these structures. We also propose an approach for determining DNA rigidity based solely on sequence. Currently, only the rigidity of DNA molecules whose structures have been deposited in the PDB (approx. <4,000 files) can be analyzed. Once fine-tuned and validated, this new coordinate-free method for investigating DNA flexibility could be applied to the more than 135 million sequences in GenBank, and to nanostructure design.

Towards Biophysical Validation Of Constraint Modeling For Rigidity Analysis Of Proteins, Filip Jagodzinski, Ileana Streinu

Computer Science: Faculty Publications

Proteins are dynamic molecules, and understanding how they flex and bend provides fundamental insights to their functions. Methods such as molecular dynamics are computationally expensive, and can simulate protein motions on limited timescales. Rigidity analysis is an alternative method, in which a protein structure is analyzed to infer which portions of the molecule are flexible. To perform rigidity analysis, a model is first constructed in which various inter-atomic stabilizing interactions are modeled according to their strength. No detailed study has been conducted as to what is the most plausible, chemically validated modeling scheme. All previous implementations have relied on heuristics, …

Understanding Visualization By Understanding Individual Users, Caroline Ziemkiewicz, Alvitta Ottley, R. Jordan Crouser, Krysta Chauncey, Sara L. Su, Remco Chang

Computer Science: Faculty Publications

No abstract provided.

Priming Locus Of Control To Affect Performance, Alvitta Ottley, R. Jordan Crouser, Caroline Ziemkiewicz, Remco Chang

Computer Science: Faculty Publications

Recent research suggests that the personality trait Locus of Control (LOC) can be a reliable predictor of performance when learn- ing a new visualization tool. While these results are compelling and have direct implications to visualization design, the relation- ship between a user’s LOC measure and their performance is not well understood. We hypothesize that there is a dependent relation- ship between LOC and performance; specifically, a person’s orientation on the LOC scale directly influences their performance when learning new visualizations. To test this hypothesis, we conduct an experiment with 300 subjects using Amazon’s Mechanical Turk. We adapt techniques from …

Body-And-Cad Geometric Constraint Systems, Kirk Haller, Audrey Lee-St.John, Meera Sitharam, Ileana Streinu, Neil White

Computer Science: Faculty Publications

Motivated by constraint-based CAD software, we develop the foundation for the rigidity theory of a very general model: the body-and-cad structure, composed of rigid bodies in 3D constrained by pairwise coincidence, angular and distance constraints. We identify 21 relevant geometric constraints and develop the corresponding infinitesimal rigidity theory for these structures. The classical body-and-bar rigidity model can be viewed as a body-and-cad structure that uses only one constraint from this new class. As a consequence, we identify a new, necessary, but not sufficient, counting condition for minimal rigidity of body-and-cad structures: nested sparsity. This is a slight generalization of the …

Massively Distributed Authorship Of Academic Papers, Bill Tomlinson, Joel Ross, Paul Andre, Eric P.S. Baumer, Donald J. Patterson, Joseph Corneli, Martin Mahaux, Syavash Nobarany, Marco Lazzari, Birgit Penzenstadler, Andrew W. Torrance, David J. Callele, Gary M. Olson, Six Silberman, Marcus Ständer, Fabio Romancini Palamedi, Albert Ali Salah, Eric Morrill, Xavier Franch, Florian Mueller, Joseph Kaye, Rebecca W. Black, Marisa L. Cohn, Patrick C. Shih, Johanna Brewer, Nitesh Goyal, Pirjo Näkki, Jeff Huang, Nilufar Baghaei, Craig Saper

Computer Science: Faculty Publications

Wiki-like or crowdsourcing models of collaboration can provide a number of benefits to academic work. These techniques may engage expertise from different disciplines, and potentially increase productivity. This paper presents a model of massively distributed collaborative authorship of academic papers. This model, developed by a collective of thirty authors, identifies key tools and techniques that would be necessary or useful to the writing process. The process of collaboratively writing this paper was used to discover, negotiate, and document issues in massively authored scholarship. Our work provides the first extensive discussion of the experiential aspects of large-scale collaborative research.

Indy R&D: Doing Hci Research Off The Beaten Path, Amanda Williams, Johanna Brewer

Computer Science: Faculty Publications

This panel discusses independent research and development in HCI. We focus on possible models for Indy R&D operations, supporting infrastructures, practical methods, and taking advantage of academic skills in the transition. Panel participants have experience in several different models of funding, conducting, and disseminating results from independent research. We will provide the audience with practical tips to help them decide if Indy R&D is right for them, and if so, help them do it. © 2012 Authors.

Using Rigidity Analysis To Probe Mutation-Induced Structural Changes In Proteins, Filip Jagodzinski, Jeanne Hardy, Ileana Streinu

Computer Science: Faculty Publications

Predicting the effect of a single amino acid substitution on the stability of a protein structure is a fundamental task in macromolecular modeling. It has relevance to drug design and understanding of disease-causing protein variants. We present KINARI-Mutagen, a web server for performing in silico mutation experiments on protein structures from the Protein Data Bank. Our rigidity-theoretical approach permits fast evaluation of the effects of mutations that may not be easy to perform in vitro, because it is not always possible to express a protein with a specific amino acid substitution. We use KINARI-Mutagen to identify critical residues, and we …

Mixed-Initiative Strategies For Real-Time Scheduling Of Multiple Unmanned Vehicles, Andrew S. Clare, Jamie Macbeth, Mary L. Cummings

Computer Science: Faculty Publications

Advances in autonomy have made it possible to invert the typical operator-to-unmanned vehicle ratio so that a single operator can now control multiple heterogeneous Unmanned Vehicles (UVs). Real-time scheduling and task assignment for multiple UVs in uncertain environments will require the computational ability of optimization algorithms combined with the judgment and adaptability of human supervisors through mixed-initiative systems. The goal of this paper is to analyze the interactions between operators and scheduling algorithms in two human- in-the-loop multiple UV control experiments. The impact of real-time operator modifications to the objective function of an optimization algorithm for multi-UV scheduling is described. …

Unfolding Prismatoids As Convex Patches: Counterexamples And Positive Results, Joseph O'Rourke

Computer Science: Faculty Publications

We address the unsolved problem of unfolding prismatoids in a new context, viewing a “topless prismatoid” as a convex patch—a polyhedral subset of the surface of a convex polyhedron homeomorphic to a disk. We show that several natural strategies for unfolding a prismatoid can fail, but obtain a positive result for “petal unfolding” topless prismatoids. We also show that the natural extension to a convex patch consisting of a face of a polyhedron and all its incident faces, does not always have a nonoverlapping petal unfolding. However, we obtain a positive result by excluding the problematical patches. This then leads …

Source Unfoldings Of Convex Polyhedra Via Certain Closed Curves, Jin-Ichi Itoh, Joseph O'Rourke, Costin Vîlcu

Computer Science: Faculty Publications

Abstract. We extend the notion of a source unfolding of a convex polyhedron P to be based on a closed polygonal curve Q in a particular class rather than based on a point. The class requires that Q “lives on a cone” to both sides; it includes simple, closed quasigeodesics. Cutting a particular subset of the cut locus of Q (in P) leads to a non-overlapping unfolding of the polyhedron. This gives a new general method to unfold the surface of any convex polyhedron to a simple, planar polygon

Outerplanar Graphs And Delaunay Triangulations, Ashraful Alam, Igor Rivin, Ileana Streinu

Computer Science: Faculty Publications

Dillencourt [1] showed that all maximal outerplanar graphs can be realized as Delaunay triangulations of points in convex position. In this note, we give two new, alternate proofs. © 2012 Springer-Verlag.

Two Visualization Tools For Analyzing Agent-Based Simulations In Political Science, R. Jordan Crouser, Daniel Kee, Dong Jeong, Remco Chang

Computer Science: Faculty Publications

Agent-based modeling has become a key technique for modeling and simulating dynamic, complicated behaviors in the social and political sciences. Although many robust toolkits for developing and running these simulations exist, systems that support analysis of their results are few and tend to be overly general. So, social scientists have had difficulty interpreting the results of their increasingly complex simulations. To help bridge this gap between data generation and interpretation, researchers collaborated with political science analysts to design two tools for interactive data exploration and domain-specific data analysis. Testing by the analysts validated that these tools provided an efficient framework …

Π/2-Angle Yao Graphs Are Spanners, Prosenjit Bose, Mirela Damian, Karim Douïeb, Joseph O'Rourke, Ben Seamone, Michiel Smid, Stefanie Wuhrer

Computer Science: Faculty Publications

We show that the Yao graph Y₄ in the L₂ metric is a spanner with stretch factor 8(29+23√ 2). Enroute to this, we also show that the Yao graph Y^∞₄ in the L_∞ metric is a planar spanner with stretch factor 8.

Beyond Spacetime Geometry – The Death Of Philosophy And Its Quantum Reincarnation, Wen-Ran Zhang

Computer Science: Faculty Publications

Contrary to the “end” and “death” assertions on philosophy, this paper predicts an equilibrium-based and harmony-centered scientific reincarnation of philosophy. Logically, the reincarnation is backed by a formal system and a background independent geometry that transcends spacetime. Physically, it is supported by definable quantum causality and bipolar logical unifications of matter and antimatter, particle and wave, big bang and black hole, relativity and quantum entanglement. Philosophically, it is distinguished from Western metaphysics and dialectics as well as the Dao of Laozi. It is named a quantum reincarnation for its central claim that YinYang bipolar quantum entanglement is the source of …

Yin Yang Bipolar Atom - An Eastern Road Toward Quantum Gravity, Wen-Ran Zhang

Computer Science: Faculty Publications

Based on bipolar dynamic logic and bipolar quantum linear algebra, a causal theory of YinYang bipolar atom is introduced in a completely background independent geometry that transcends spacetime. The causal theory leads to an equilibrium-based super symmetrical quantum cosmology of negative-positive energies. It is contended that the new theory has opened an Eastern road toward quantum gravity with bipolar logical unifications of particle and wave, matter and antimatter, relativity and quantum entanglement. Information recovery after a black hole is discussed. It is shown that not only can the new theory be applied in physical worlds but also in logical, mental, …

Multi- Autonomous Vehicle Insertion-Extraction System (Mavies), Jamie C. Macbeth, Manal Habib, Armen Mkrtchyan, Missy Cummings

Computer Science: Faculty Publications

MAVIES (Multi-Autonomous Vehicle Insertion-Extraction System) is the culmination of a year-long multi-stakeholder e ort between UTRC and the Humans and Automation Lab at MIT to design a human inter- face for insertion and extraction missions with multiple UAVs and option- ally piloted rotorcraft. The design process is a successful application of the Hybrid Cognitive Task Analysis (hCTA) process that tracks dozens of tasks, decision-making processes and their associated situation aware- ness requirements to determine the proper allocation of responsibilities between the human operator and the automated mission planner.

This paper discusses the various accomplishments through several phases of a disciplined …