Boston University - ECE Department

Next-Generation Methods for Image
Sequence Analysis, Processing, and Transmission

Associate Professor Janusz Konrad
Visual Information Processing Laboratory

This research concentrates on advanced processing of image sequences with the
goals of more accurate analysis (e.g., segmentation), extraction of qualitatively new information (e.g., occlusion and newly-exposed areas), and advanced compression.

In one of the thrusts, the focus is on spatio-temporal video segmentation. While typical approaches to such an analysis consider two image frames at a time, we perform this analysis jointly over multiple frames. The segmentation process is three-dimensional (3-D); we search for a volume carved out by each moving object in the image sequence domain, or "object tunnel'', a new space-time concept. We pose the problem in variational framework by using only motion information (no intensity edges). The resulting formulation can be viewed as volume competition, a 3-D generalization of region competition. We parameterize the unknown surface to be estimated, but rather than using an active-surface approach, we embed it into a higher-dimensional function and apply the level-set methodology. We develop a range of models, from simple ones for the detection of moving objects over static background (no motion models used), through more advanced ones that exploit separate motion models for objects and background, to advanced models explicitly accounting for occlusion effects that lead to "occlusion volumes'', another new space-time concept. Since in the latter case multiple volumes are sought, we develop computational framework around multiphase variant of the level-set method. Testing on a wide range of dynamic image data shows not only significant improvements that the new approach provides, but also demonstrates a new way dynamic images can be visualized.

Above: Two frames from a 30-frame image sequence, and extracted object tunnel.

Another thrust of this research concentrates on new-generation compression methods for dynamic imagery. It is widely believed in the research community today that the next significant video coding gains will come from a joint compression of multiple video frames, such as offered by 3D wavelet coding. We have been studying the behavior of video data subject to various 3-D (x-y-t) transformations. On one hand, we have developed a multiple-frame characterization of linear motion in the discrete cosine transform (DCT) domain. An extension of the fundamental result in Fourier domain, this outcome permits a better understanding of spectral composition of 3D-DT-transformed
video data. Based on this, we have developed 3D DCT coefficient scanning patterns that are more efficient than scans used to date, and lead to efficient 3D transform-based video coding. The 3D DCT coder we developed outperforms MPEG-2 by a wide margin and is only slightly inferior to MPEG-4 but enjoys significantly lower computational complexity. We have also developed new motion models for 3D wavelet-based video coders. Our triangular-mesh motion models use new mesh topology and provide a modest increase of performance with no additional complexity, while our scalable spline-based models show a markedly improved performance (+1dB) over block-based models when evaluated with respect to spatial scalability performance.

Image Processing and Compression for 3-D Hologram-Like
Visual Communications of the Future

Associate Professor Janusz Konrad

This research focuses on enhancement, view generation and compression algorithms for automultiscopic 3-D displays, i.e., displays that do not require glasses while providing multiple perspectives (multiple views) to the viewer (look-around). Such displays have recently been introduced on the market and hold a great promise for the future of 3-D visual communications.

Next-generation display systems will support depth in order to invoke a "being there" experience. This can be achieved by presenting two views on a 3-D stereoscopic display (anaglyph, polarized, shuttered, autostereoscopic). Our research in this project is stimulated by a new generation of advanced automultiscopic (multiview, no glasses) 3-D displays that have been recently introduced on the market, such as monitors from Stereographics Corp. and 4-D Vision GmbH (currently X3D Corp.). The current work concentrates on optimal multiplexing of views in order to invoke as natural 3-D perception as possible. One of the issues is anti-alias pre-filtering of each view. Since individual views are sampled irregularly during multiplexing, it is unclear how to design and implement optimal anti-alias filters.

Figure 1: Magnitude response of anti-alias filter designed
using spatial-domain 2-D lattice approximation

In one approach, we use 2-D lattice approximations and derive anti-alias filter specifications from these specifications. Application of filters designed according to these specifications leads to a reduction in aliasing and improved 3-D perception. In a more recent development, we have developed a unique approach to accurately calculating the spectrum of irregularly-sampled finite-support 2-D signals. This spectrum consists of periodic replications of the underlying continuous-signal spectrum but with frequency-dependent gains. Since these gains directly affect the degree of aliasing due to the performed multiplexing, we select spectral replications with highest gains and analyze their equal-energy partition in search of ideal anti-alias filter specifications. Filters designed according to these new specifications lead to improved image quality, due to image-adapted bandwidth, while maintaining anti-alias properties of the lattice-based approximations.

Figure 2: Magnitude response of anti-alias filter
designed using equal-energy spectrum partitioning

As new automultiscopic displays begin to deliver acceptable 3-D experience, difficulties arise with data generation and delivery. In order to take full advantage of such displays, multiple views (as many as 10-15) need to be generated, but typical acquisition systems use 2-3, perhaps 5, cameras. The issue is of intermediate view reconstruction (generation) which is a difficult, ill-posed problem. Once all the views are generated they may need to be delivered remotely via a communications channel and thus compression may be needed. We are currently working on both problems with the ultimate goal of posing and solving a joint problem of view reconstruction and compression.

Our work establishes the theoretical foundations of two complementary sensornet architectures for indoor location detection. In the first architecture, the emphasis is on the robustness of the system, where the goal is to provide deterministic guarantees on the system's performance in the case of sensors faults or failures. This architecture addresses a key issue in modern sensor network deployment, and localization systems in particular, by enabling robustness without resorting to approaches that may be too sensitive to fluctuations in indoor environments, namely channel modeling, trilateration, or experimental signal mapping. In the second architecture, we resort to statistical optimization techniques to maximize the system's resolution. This architecture treats signal strength and other observations on which location determination is based as random. As a result, it can accommodate the highly variable nature of the signal landscape in indoor environments. Extensive simulation and experimentation demonstrates that it can more accurately determine location than earlier deterministic systems. The experiments are performed using sensor nodes donated by Intel Corp.

In parallel with our theoretical investigations, we have started deploying a testbed of motes on the ceilings of the 4th floor of the Photonics Building at Boston University. We are making use of Deluge to program the motes over the air. However, Deluge provides limited network-monitoring capabilities, either during firmware reprogramming or while the system is in a steady-state. Therefore, two of our undergraduate students have developed a toolkit, called Network Observation System (NOSY), that allows monitoring a sensor network over the air. NOSY provides the following ca

pabilities: 1) Watch the progress of image injections into a network 2) Vary the frequency at which motes sends back information 3) Send individual commands to nodes (e.g., reboot).Our toolkit has been made publicly available for download.

Above: Resolution of the robust location detection system, as measured on the 4th floor of the Photonics Building at Boston University. Crossed circles represent transmitters and plain circles represent locatable points. (IEEE Journal Selected Areas on Communications, 2004)

High-performance networks, such as ESnet, rely on advanced control-plane protocols such as RIP, OSPF, BGP, RSVP, and MPLS, to support efficient data packet forwarding over the network. Despite their extreme importance, these control-plane protocols are vulnerable to various forms of instability, such as delayed convergence, persistent route oscillations, thrashing, and deadlocks. The goal of this project is to develop a unified theoretical framework to understand and address these stability issues. Accordingly, a program of research will be developed, centering on the following objectives: identify the different forms of instab

ility that control-plane protocols may exhibit; determine the fundamental, theoretical causes of instability; estimate, using analysis and simulation, the likelihood of occurrence of instability phenomena in control-plane protocols as a function of network and protocol parameters; prevent instability in control-plane protocols, through the development of new algorithmic and graph-theoretic methodologies. The results of this research will have direct bearing on the design of robust and reliable control-plane protocols for UltraScience Net and other next generation DOE networks.

Our research focuses on developing solutions to the problem of data reconciliation (also known as data synchronization) in heterogeneous networks consisting both of fixed hosts, such as PCs and servers, and mobile hosts, such as PDAs, laptops, and other carry-on devices. A salient feature of such networks is that mobile hosts are only intermittently connected to the rest of the network. This feature calls for the development of efficient synchronization protocols to allow the dissemination and reconciliation of data (e.g., files, routing tables, databases etc.) shared between different hosts. Such synchronization protocols must be carefully designed, as mobile devices have often limited bandwidth, memory, CPU, and energy resources available for maintaining data consistency.

As part of this research, we are developing both theoretical foundations as well as implementations of new synchronization protocols for heterogeneous, mobile networks. Our methods represent a fundamental departure from the current state-of-the-art in terms of scalability, reliability, and mathematical sophistication. In particular, based on

recent coding-theoretic advances, we have developed and implemented a new synchronization middleware for PDA synchronization, called CPIsync. CPIsync can achieve orders-of-magnitude improvement in terms of communication, latency, and battery usage, compared to the commercially available HotSync protocol currently used by Palm OS-based PDAs. We have also built several prototypes that demonstrate
the use of CPIsync as a middleware platform for a number of different Personal Information Management (PIM) applications, such as memopads and calendars.

Above: Memo text entry in our fast-synchronizing memopad (SyncMemo) developed on Palm and Ipaq Personal Digital Assistants.

This project is concerned with the development of novel signal processing technology to assist in the analysis of brain to muscle communications. Such communications are of interest from a medical point of view in the context of neurological pathologies that may arise as a consequence of Parkinson’s disease, stroke, etc. An Electromyographic (EMG) signal is acquired via indwelling sensors or non-invasive skin-surface sensors. The EMG signal acquired this way consists of overlapping communication signals from the brain to different bundles of muscle fibers. The communication signals are not known a-priori and their appearance in the EMG signal is influenced considerably by factors such as sensor movement during data acquisition.

To address the complexities in analyzing the EMG signal, we are developing signal processing algorithms that utilize sophisticated computational concepts from computer science in general and artificial intelligence in particular to amplify the effectiveness of traditional techniques from the traditional areas of digital and statistical signal processing.

The following figure illustrates the result of applying our current system to an EMG signal. Specifically, the EMG signal in this case was separated by the system into 7 communication signals. When the 7 communication signals are subtracted from the original EMG signal the resultant residue is also included in the figure.

This research is conducted in collaboration with the NeuroMuscular Research Center at Boston University.

With a vision for architecting the next generation video-based sensor networks capable of real-time "superresolution imaging" using a large distributed network of poor-resolution wireless cameras, this project introduces new paradigms for distributed sampling and video coding that lie in the frontier of signal processing and network
information theory. The new data-acquisition, compression, and inference methods developed in this project are expected to influence the architecture and evolution of large-scale wireless sensor networks and advance the state-of-the-art in applications requiring active monitoring of telemetry data such as surveillance, homeland security, intelligent transportation, and environmental monitoring.

This project 1) studies fundamental performance limits and constructive approaches for integrating poor device precision and large-scale deployment with distributed sampling and compression using new results in nonharmonic Fourier analysis, dithered sampling, and Wyner-Ziv coding and 2) develops new real-time distributed video-coding architectures that are amenable to flexible distribution of processing complexity and sensing resolution and are robust to information loss and correlation uncertainty. A novel "bit-conservation" principle is introduced for characterizing the tradeoffs between sensor precision and sensor density in distributed sampling.

The research effort is complemented by an educational effort to train young engineers to become skilled in the design and development of distributed information systems through 1) curriculum development, with

a new course on distributed information processing and communication having an emphasis on raw-research and project development, 2) the compilation of a corpus of striking toy research puzzles illustrating fundamental concepts in distributed signal processing and network information theory integrated into the undergraduate and graduate curricula, and 3) the creation of a new introductory graduate-level text-book on information theory in distributed signal processing.

Distributed networks are envisioned in such diverse applications as building safety, environmental monitoring, power systems, manufacturing as well as military and space applications. Our research is focused on as to how to make decisions under uncertainty, which arises from spatially distributed dynamic information when sharing distributed data is limited by networking constraints. Several projects underway in our laboratory and are focused along two fundamental directions: One direction involves representing, modeling, aggregation of distributed information. A second direction involves understanding energy, throughput scaling and stability with network size.

Distributed tracking in Multi-hop Sensor Networks
This project deals with distributed tracking of a target via networked sensors. The networked sensors communicate with each other by means of a multi-hop protocol over a communication network. In the linear setting MMSE-optimal solution is Kalman filtering when measurements are available centrally, but new methods are required to account for communication constraints. We have developed optimal energy efficient in-network processing algorithms to deal with arbitrary network topology and non-ideal channel conditions. Our techniques differ from existing techniques in two important aspects: a) there is no designated leader/fusion node and each sensor attempts to optimally track the system trajectory based on its local observations and time- dependent information available from other sensors in the network; b) the message computation at each sensor is structurally identical.

Sensor Selection for Target Tracking & Multi-target Locationing in Limited Sensing Range
The previous project dealt with cooperation between information bearing sensors. However, often it is unclear which sensors have the most relavant information. This project deals with dynamic selection of information bearing sensors. Sensed information typically undergoes power-law decay with distance. Consequently, sensors that are close to the target have most of the information. As the target moves the collection of sensors with relevant information also changes. If the measurements were centrally available this problem is straightforward. However, if data is distributed the question arises as to how sensors cooperate to activate the best subset among them. Small subsets lead to lower energy expenditure but at the cost of higher inaccuracy. Another question that we address is the optimal handoff policy for sensing from one subset to another as a target moves. Another aspect of this research is sensor selection.

Reliable Tracking with Unreliable Communication Links
Many sensing/communication devices in sensor networks operate in a wireless ad-hoc environment, which is prone to packet losses. For instance, two directional sensors are generally required to locate a target on a plane but if packets are lost from any sensors is it possible to still track a moving target? This project deals with such issues and our goal is to understand how packet losses impact target tracking and as to how to overcome the impact of packet losses.

Macroscopic Effects of Local Interactions in Ad-Hoc Wireless Networks
Wireless networks are interference limited, i.e., simultaneous transmission by many users limits the throughput capacity of the network. The development of distributed protocols that use local information to overcome the effect of interference has been an active topic of research. Carrier Sensing Multiple-Access (CSMA), rate adaptation and power control have been some of the widely studied distributed protocols in wireless networks. The main focus of our project is to understand the impact of these distributed adaptation mechanisms on the global network stability. We have shown in theory and through simulation that standard ad-hoc policies such as rate adaptation and CSMA can lead to phase transition behavior. Here, a network may have no evidence of unstable behavior until a new node enters the network or some node gets greedy and decides to transmit at a higher rate --- at which point the network may suddenly be brought down.

Wireless ad-hoc networks: Strategies and Scaling laws for the fixed SNR regime
This project deals with throughput scaling for large wireless networks in a fixed SNR regime. This scenario is motivated from many practical considerations. First, wireless networks are significantly interference limited as opposed to power. Second, at reasonable power levels and practical attenuation levels, the geographical area can be sufficiently large and still sustain a fixed SNR between any two nodes in the area. Nevertheless, recent research on scaling laws for wireless networks have mainly considered two regimes: fixed area networks in poor scattering regime and extended area networks in low-SNR regime. In contrast to multi-hop protocols, which are optimal for these two regimes, we have shown that co-operative strategies lead to significantly better throughput and transport capacity in fixed-SNR rich-scattering regime. For a fixed SNR regime, our strategy is composed of opportunistic local collaboration for interference cancellation together with exploitation of diversity and rate gains in a rich scattering environment which results in a throughput scaling of O(n2/3) bit-meters/sec for an n node wireless network.

Randomized Sequential Algorithms for Data Aggregation in Sensor Networks
Many in-network processing algorithms in sensor networks involve standard computations such sums, averages, max, min, etc. Energy efficient, scalable and asynchronous algorithms in non- ideal ad-hoc communication environment are of great interest. We consider in-network processing via local message passing. The considered setting involves a set of sensors each of which can communicate with a subset of other sensors. There is no designated fusion center; instead sensors exchange messages on the associated communication graph to obtain a global estimate. We propose an asynchronous distributed algorithm based on local fusion between neighboring sensors. The algorithm differs from other related schemes such as gossip algorithms in that after each local fusion one of the associated sensors ceases its activity until it is re-activated by reception of messages from a neighboring sensor. This leads to exponential gains in energy expenditure over existing local ad-hoc messaging algorithms such as gossip and belief propagation algorithms. In particular we show that energy expenditure per node scales as O(log(n)) for an n- node network for several different network topologies.