Qatar Foundation Annual Research Forum Volume 2013 Issue 1

In embedded real-time communication and multimedia processing applications, the manipulation of large amounts of data has a major effect on both power consumption and performance of the system. Due to the significant amount of data transfers between the processing units and the large and energy consuming off-chip memories, these applications are often called data-dominated or data-intensive. Providing sufficient bandwidth to sustain fast and energy-efficient program execution is a challenge for system designers: due to the growing gap of speed between processors and memories, the performance of the whole VLSI system will mainly depend on the memory subsystem, when memory is unable to provide data and instructions at the pace required by the processor. This effect is, sometimes, referred in the literature as the memory wall problem. At system level, the power cost can be reduced by introducing an optimized custom memory hierarchy that exploits the temporal data locality. Hierarchical memory organizations reduce energy consumption by exploiting the non-uniformity of memory accesses: the reduction can be achieved by assigning the frequently-accessed data to low hierarchy levels, a problem being how to optimally assign the data to the memory layers. This hierarchical assignment diminishes the dynamic energy consumption of the memory subsystem - which expands due to memory accesses. Moreover, it diminishes the static energy consumption as well, since this decreases monotonically with the memory size. Moreover, within a given memory hierarchy level, power can be reduced by memory banking - whose principle is to divide the address space in several smaller blocks, and to map these blocks to physical memory banks that can be independently enabled and disabled. Memory partitioning is also a performance-oriented optimization strategy, because of the reduced latency due to accessing smaller memory blocks. Arbitrarily fine partitioning is prevented since an excessively large number of small banks is area inefficient, imposing a severe wiring overhead -- which increases communication power and decreases performance. This presentation will introduce an electronic design automation (EDA) methodology for the design of hierarchical memory architectures in embedded data-intensive applications, mainly in the area of multidimensional signal processing. The input of this memory management framework is the behavioral specifications of the applications, that are assumed to be procedural and affine. Figure 1 shows an illustrative example of behavioral specification with 6 nested loops. This framework employs a formal model operating with integral polyhedra, using techniques specific to the data-dependence analysis employed in modern compilers. Different from previous works, three optimization problems - the data assignment to the memory layers (on-chip scratch-pad memory and off-chip DRAM), the mapping of multidimensional signals to the physical memories, and the banking of the on-chip memory (see Figure 2) - are addressed in a consistent way, based on the same formal model. The main design target is the reduction of the static and dynamic energy consumption in the memory subsystem, but the same formal model and algorithmic principles can be applied for the reduction of the overall time of access to memories, or combinations of these design goals.

Line and word segmentation is a key-step in any document image analysis system. It can be used for instance in handwriting recognition when separating words before their recognition. Line segmentation can also serve as a prior step before extracting the geometric characteristics of lines which are unique to each writer. Text line and word segmentation is not an easy task because of the following problems: 1) text lines do not all have the same direction in the handwritten text; 2) text lines are not always horizontal which makes their separation more difficult; 3) characters may overlap between successive text lines; 4) it is often confusing to distinguish between inter and intra word distances. In our method, line segmentation is done by using a smoothed version of the handwritten document which makes it possible to detect the main line components using a subsequent thresholding algorithm. The connected components of the resulting image are then assigned to a separate label which represents a line component. Then, each text region which intersects only with one line component is assigned to the same label of that line component. The Voronoi diagram of the image thus obtained is then computed in order to label the remaining text pixels. Word segmentation is performed by computing a generalized Chamfer distance in which the horizontal distance is slightly favored. This distance is subsequently smoothed in order to reflect the distances between word components and neglect the distance to dots and diacritics. Word segmentation is then performed by thresholding the distance thus obtained. The threshold depends on the characteristics of the handwriting. We have therefore computed several features in order to predict it, including: the sum of maximum distances within each line component, the number of connected components within the document and the average width and height of lines. The optimal threshold is then obtained by training a linear regression of those features on a training set of about 100 documents. This method achieved the best performance on the ICFHR Handwriting Segmentation Contest dataset reaching a matching score of 97.4% on line segmentation and 91% on word segmentation. The method has also been tested on the QUWI Arabic dataset reaching 97.1% on line segmentation and 49.6% on word segmentation. The relatively low performance of word segmentation in Arabic script is due to the fact that words are very close to each other with respect to English script. The proposed method tackles most of the problems of line and word segmentation and achieves high segmentation results. It can however be improved by combining it with a handwriting recognizer which will eliminates words which are not recognized.

Attenuators are extensively employed as an amplitude control circuit in communication and radar systems. Flatness, attenuation range, and bandwidth are typical specifications for attenuators. Most attenuators in previous studies rely on the basic topologies of the Pi-, T-, and distributed attenuators. The performance of the Pi- and T-attenuators, however, is affected substantially by the switch performance of transistors, and it is hard to obtain optimum flatness, attenuation range, and bandwidth with these attenuators. The conventional distributed attenuator also demands a large chip area for large attenuation ranges. We report the design of a new microwave/millimeter-wave CMOS attenuator. A design method is proposed and implemented in the attenuator to improve its flatness, attenuation range, and bandwidth. It is recognized that the Pi- and T-attenuators at a certain attenuation state inherently has the insertion-loss slope increasing as the frequency is increased. This response is owing to the off-capacitance of the series transistors. On the other hand, the distributed attenuators can be designed to have the opposite insertion-loss slope by shortening the transmission lines. The reason is that short transmission lines causes the center frequency be shifted higher. The proposed design method utilizes the two opposite insertion-loss slopes and is implemented for the Pi-, T-and distributed attenuators in a cascade connection. Over 10-67 GHz, the measured results exhibit attenuation flatness of 6.8 dB and attenuation range of 32-42 dB.

We propose a multimedia-based learning system to teach children with intellectual disabilities (ID) basic concepts in Science, Math and daily living tasks. The tutorials' pedagogical development is based on Mayer's Cognitive Learning Model combined with Skinner's Behaviorist Operant Conditioning Model. Two types of Arabic tutorials are proposed: (1) Statically generated tutorials, which are pre-designed by special needs instructors, and developed by animation experts. (2) Dynamically generated tutorials, which are developed using natural language processing and ontology building. Dynamic tutorials are generated by processing Arabic text, and using machine learning to query the Google engine and generate multimedia elements, which are automatically updated into an ontology system and are hence used to construct a customized tutorial. Both types of tutorials have shown considerable improvements in the learning process and allowed children with ID to enhance their cognitive skills and become more motivated and proactive in the classroom.

This paper presents a robust real-time vision framework that detects and tracks vehicles from stationary traffic cameras with certain regions of interest. The framework enables intelligent transportation and road safety applications such as road-occupancy characterization, congestion detection, traffic flow computation, and pedestrian tracking. It consists of three main modules:1) detection, 2) tracking, and 3) data association. To this end, vehicles are first detected using Haar-like features. In the second phase, a light-weight appearance-based model is built using random projections to keep track of the detected vehicles. The data association module fuses new detections and existing targets for accurate tracking. The practical value of the proposed framework is demonstrated with evaluation involving several real-world experiments and variety of challenges.

We will present an overview and in-progress report of a QNRF-sponsored project for research in the effects of using program visualization in teaching and learning computational thinking. Computers and computing have made possible incredible leaps of innovation and imagination in solving critical problems such as finding a cure for diseases, predicting a hurricane's path, or landing a spaceship on the moon. The modern economic conditions of countries around the world are increasingly related to their ability to adapt to the digital revolution. This, in turn, drives the need for educated individuals who can bring the power of computing-supported problem solving to an increasingly expanded field of career paths. It is no longer sufficient to wait until students are in college to introduce computational thinking. All of today's students will go on to live in a world that is heavily influenced by computing, and many of these students will work in fields that involve or are influenced by computing. They must begin to work with algorithmic problem solving and computational methods and tools in K-12. Many courses taught in K-12 (for example, math and science) teach problem solving and logical thinking skills. Computational thinking embodies these skills and brings them to bear on problems in other fields and on problems that lie at the intersection of these fields. In the same way that learning to read opens a gateway to learning a multitude of knowledge, learning to program opens a gateway to learning all things computational. Alice is a programming environment designed to enable novice programmers in creating 3-D virtual worlds, including animations and games. In Alice, 3-D models of objects (e.g., people, animals and vehicles) populate a virtual world and students use a drag and drop editor to manipulate the movement and activities of these objects. Alice for the Middle East - "Alice ME" is a research project funded by Qatar National Research Fund (QNRF) under their National Priorities Research Program (NPRP) that aims to modify the well-known Alice introductory programming software to be internationally and culturally relevant for the Middle East. In this project, we are working on developing new 3D models that provide animation objects encountered in daily lives (animals, buildings, clothing, vehicles, etc.) as well as artifacts that reflect and respect the heritage of Qatari culture. The new models will provide characters and images that enable students to create animations that tell the stories of local culture, thereby supporting the QNV 2030 aspiration for maintaining a balance between modernizations and preserving traditions. We are also working with local schools to develop an ICT curriculum centered on using Alice to help students learn computational thinking. We are also designing workshops to train teachers in using Alice and delivering this curriculum.

Translation of named entities (NEs) is important for NLP applications such as Machine Translation (MT) and Cross-lingual Information Retrieval. For MT, named entities are major subset of the out-of-vocabulary terms. Due to their diversity, they cannot always be found in parallel corpora, dictionaries or gazetteers. Thus, state-of-the-art MT systems need to handle NEs in specific ways: (i) direct translation which results in missing many out of vocabulary terms and (ii) blind transliteration of out of vocabulary terms which does not necessarily contribute to translation adequacy and may actually create noisy contexts for the language model and the decoder. For example, in the sentence "Dudley North visits North London", the MT system is expected to transliterate "North" in the former case, and translate "North" in the latter. In this work, we present a classification-based framework, that enables MT system to automate the decision of translation vs. transliteration for different categories of NEs. We model the decision as a binary classification at the token level: each token within a named-entity gets a decision label to be translated or transliterated. Training the classifier requires a set of NEs with token-level decision labels. For this purpose, we automatically construct a set of bilingual lexicon of NEs paired with the translation/transliteration decisions from two different domains: We heuristically extract and label parallel NEs from a large word aligned news parallel corpus and we use a lexicon of bilingual NEs collected from Arabic and Wikipedia titles. Then, we designed a procedure to clean up the noisy Arabic NE spans by part-of-speech verification, and heuristically filtering impossible items (e.g. verbs). For training, the data is automatically annotated using a variant of edit distance measuring the similarity between an English word and its Arabic transliteration. For test set, we manually reviewed the labels and fixed the incorrect ones. As part of our project, this bilingual corpus of named entities has been released to the research community. Using Support Vector Machines, we trained the classifier using a set of token-based, contextual and semantic features of the NEs. We evaluated our classifier both in the limited news and diverse Wikipedia domains, and achieved promising accuracy of 89.1%. To study the utility of using our classifier on an English to Arabic statistical MT system, we deployed it as a pre-translation component to the MT system. We automatically located the NEs in the source language sentences and used the classifier to find those which should be transliterated. For such terms, we offer the transliterated form as an option to the decoder. The impact of adding the classifier to the SMT pipeline resulted in a major reduction of out of vocabulary terms and a modest improvement of the BLEU score. This research is supported by the Qatar National Research Fund (a member of the Qatar Foundation) through grants NPRP-09-1140-1-177 and YSREP-1-018-1-004. The statements made herein are solely the responsibility of the authors.

There are many cities where urbanization occurs at a faster rate than that of communication infrastructure deployment. Mobile users with sophisticated devices are often dissatisfied with this lag in infrastructure deployment; their Internet connection is via opportunistic open Access Points for short durations, or via weak, unreliable, and costly 3G connections. With increased demands on network infrastructure, we believe that opportunistic networking, where user mobility is exploited to increase capacity and augment Internet reachability, can play an active role as a complimentary technology to improve user experience, particularly with delay insensitive data. Opportunistic forwarding solutions were mainly designed using a set of assumptions that have grown in complexity, rendering them unusable outside their intended environment. Figure 1 categorizes sample state-of-the-art opportunistic forwarding solutions based on their assumption complexity. Most of these solutions however are not designed for large scale urban environments. In this work, we believe to be the first to exploit the space syntax paradigm to better guide forwarding decisions in large scale urban environments. Space syntax, initially proposed in the field of architecture to model natural mobility patterns by analyzing spacial configurations, offers a set of measurable metrics that quantify the effect of road maps and architectural configurations on natural movement. By interacting with the pre-built static environment, space syntax predicts natural movement patterns in a given area. Our goal is to leverage space syntax concepts to create efficient opportunistic forwarding distributed solutions for large scale urban environments. We address two communication themes: (1) Mobile-to-Infrastructure: We propose a set of space syntax based algorithms that adapt to a spectrum of simplistic assumptions in urban environments. As depicted in Figure 1, our goal is to gain performance improvement across the spectrum, within each assumption category, when compared to other state-of-the-art solutions. We adopt a data driven approach to evaluate the space syntax based forwarding algorithms we propose, within each of three assumption categories, based on large scale mobility traces capturing vehicle mobility. Overall, our results show that our space syntax based algorithms perform more efficiently within each assumption category. (2) Infrastructure-to-Mobile: We propose a new algorithm, Select&Spray, which leverages space syntax, and enables data transfers to mobile destinations reached directly through the infrastructure or opportunistically via other nodes. This architecture consists of: (i) a select engine that identifies a subset of directly connected nodes with a higher probability to forward messages to destinations, and (ii) a spray engine residing on mobile devices that guide the opportunistic dissemination of messages towards destination devices. We evaluate our algorithm using several mobility traces. Our results show that Select&Spray is more efficient in guiding messages towards their destinations. It helps extend the reach in data dissemination to more than 20% of the interested destinations within very short delays, and successfully reaches almost 90% of the destinations in less than 5 minutes.

The use of more effective processing tools such as advanced video codecs in wireless sensor networks (WSNs) has enabled widespread adoption of video-based WSNs for monitoring and surveillance applications. Considering that in video-based WSN applications large amounts of energy resources are required for both compression and transmission of video content, optimizing the energy consumption is of paramount importance. There is a trade-off between the encoding complexity and compression performance in the sense that high compression efficiency comes at the expense of increased encoding complexity. On the other hand, there is a direct relationship between coding complexity and energy consumption. Since the nodes in a video sensor network (VSN) share the same wireless medium, there is also an issue with fairness of bandwidth allocation per each node. Nevertheless, the fairness of resource allocation (encoding and transmission energy) for nodes placed at different locations in VSNs has a significant effect on energy consumption. In our study, our objective is to maximize the lifetime of the network by reducing the consumption of the node with the maximum energy usage. Our research focuses on VSNs with linear topology where the nth node relays its data through the nth-1 node, and the node closest to the sink relays information from all the other nodes. In our approach, we analyze the relation between the fairness of nodes' resource allocation, video quality and VSNs' energy consumption to propose an algorithm for adjusting the coding parameters and fairness ratio of each node such that energy consumption is balanced. Our results show that by allocating higher fairness ratios to the closest nodes to the sink, we reduce the maximum energy consumption and achieve a more balanced energy usuge. For instance, in the case of a VSN with six nodes, by allocating the fairness ratios between 0.17 to 0.3 to the closer nodes to the sink, the maximum energy consumption is reduced by 11.28%, with standard deviation of nodes' energy consumption (STDen) of 0.09W compared to 0.25W achieved by the maximum fairness scheme.