Activity Report – 2005 ISR-Lisbon Associate Laboratory

Associate Laboratory – Institute for Systems and Robotics – ISR - Lisbon

Thematic Area D: Signal Processing for Communications Networks and Multimedia

Activity Report

2005

To be included in the LA Activity Report of 2005

Some of the elements are to be introduced in FCT web page as the report of the Plurianual Project

and to be used in the LA synthesis report [2002-2005]

All the report is to be done in English

1 – DESCRIPTION OF SCIENTIFIC ACTIVITIES IN 2005

Action 1.  Signal Processing for Wireless Communications Radio Systems

a)  Blind Source Separation

Consider a linear, instantaneous mixture of a finite number of uncorrelated sources. We face the problem of estimating the unknown mixture matrix. It is well known that, using only second order statistics, this matrix can only be identified up to a residual orthogonal factor.This constitutes an example of an “intrinsic” ambiguity which occur in many other deterministic estimation problems and prevents a direct application of standard benchmarking tools such as the Cramér-Rao bound (because the Fisher information matrix will be singular). It is intuitive that, to compare the intrinsic performance of given identification algorithms (estimators), one whould conduct the analysis in the quotient space of mixing matrices, which is obtained after the ambiguity is quotiented out. This demands an extension of the Cramér-Rao bound (CRB) to parameter spaces which are more generic than the usual Euclidean ones, e.g., they do not possess a vector space structure. We carried out such a generalization for Riemannian parameter spaces. Our Intrinsic Variance Lower Bound (IVLB) coincides with the CRB in the Euclidean case, and can be used for parameter spaces with curvature such as the Lie group of orthogonal matrices or for more abstract spaces such as the Grassmann spaces.

b)  Space Time Coding

We addressed the problem of point-to-point wireless communication in which both the receiver and transmitter are equipped with multiple-antennas. We considered the challenging noncoherent setup, that is, the space-time matrix channel is unknown at both the transmitter and receiver sides. In fact, contrary to most available approaches, we don’t even assume a probabilistic prior for the channel: we model it as an unknown deterministic parameter. Moreover, the Gaussian observation noise is allowed any correlation structure (albeit assumed known at both sides).

The receiver implements a Generalized Likelihood Ratio Test (GLRT) detector: (i) this consists in a bank of parallel processors; (ii) each processor is matched to one codeword of the finite codebook employed by the transmitter; (iii) each processor computes the likelihood of the observation assuming the presence of its associated codeword and the channel replaced by its maximum-likelihood estimate; (iv) the processor exhibiting the highest likelihood determines the codeword selected by the receiver. For this architecture, we conducted a theoretical analysis of the probability of error. This is exploited as a figure of merit to design optimal codebooks and translates into solving a high-dimensional, nonlinear optimization problem which we tackle into phases. Phase I constructs a sub-optimal codebook by solving a nearby convex relaxation of the original optimization problem. Phase II refines this sub-optimal codebook through an iterative algorithm which evolves in the Riemannian space defined by the power constraints imposed at the transmitted side.

Our codebooks outperform the other constructions available in the literature, both for the high and low snr regimes.

Action 2.  Underwater Acoustics

The growing interest in ocean exploration and the recent development of autonomous surface vehicles and submarines that perform inspection tasks in cooperation require efficient and robust data communication systems. Digital communication using acoustic modems is the method of choice for exchanging data among distant or highly mobile equipment used in various underwater activities. However, achieving efficient communication in this environment is challenging due to severe distortions that affect the transmitted signals as they undergo multiple reflections and refractions in their propagation path. Attempts to overcome these impairments in high data rate coherent modems haven't been entirely satisfactory, thus hampering their widespread adoption.

Research on underwater communication systems focused on exploiting intrinsic properties of acoustic wave propagation in the ocean to mitigate the effects of multipath or improve the robustness of signal detection and demodulation. Some effort was also devoted in adapting techniques developed for wireless radio systems to ocean environments.

a)  Multicarrier communications:

Previous work on underwater communication using OFDM addressed MIMO equalization as a means of compensating for the severe intersymbol interference introduced by the channel, which makes simpler cyclic-prefix-based schemes impractical. However, the need for an equalizer makes it unclear whether this approach is advantageous relative to single-carrier communication. Moreover, Doppler compensation with multicarrier signaling is significantly more complex than its single-carrier counterpart. At this point, there is a need for real data from sea tests to effectively assess the practical feasibility of underwater OFDM. Such data was gathered in a previous mission at sea, but was found to be of very limited use due to the poor quality of the acquisition equipment. As a result, the focus on high-rate communications in severely dispersive channels shifted back to single-carrier communications during 2005, and little work was done on the topic of underwater OFDM communication other than completion of pending project reports. It is expected that much higher quality experimental OFDM data can be gathered during missions at sea in 2006. Still, this line of research will only play a minor role in future activities.

b)  Physics-based signal processing:

Time-reversed focusing by using multiple transmit/receive elements was proposed as a means of reducing the effects of intersymbol interference in digital communication signals, including OFDM-modulated waveforms. This feedback process takes advantage of the reciprocity of the propagation medium, and achieves transparent multipath compensation without detailed knowledge of the environment.

Work during 2005 characterized the focusing performance of time-reversal arrays with randomly-spaced elements. Randomly-spaced arrays in free space are known to allow substantial savings in the number of sensors relative to uniform arrays, with only a minor performance degradation. The situation was shown to be similar in a simple underwater waveguide, but attaining the element count where significant savings can be achieved through nonuniform sensor placement (on the order of 100 sensors) is arguably still prohibitively expensive. Work in this area also addressed the analysis of real data collected in time reversal experiments at sea. This confirmed that the practical performance of time reversal is often surprisingly good, sometimes providing reasonable intersymbol interference compensation with extremely sparse arrays. Receiver architectures combining spatial processing through passive time reversal, followed by equalization, were examined.

c)  Software-defined radio:

As part of this research effort, a prototype underwater acoustic digital communication system is being developed. The system is based on the software-defined-radio approach, whereby digital signal processing is used as high as possible in the frequency conversion chain to create highly flexible emitters and the receivers.

Completion of this activity has been marred by a shortage of manpower. At this point, the hardware architecture has been specified, and the components that make up the core functionality (DSP board, A/D and D/A converter boards) have been procured. The basic software functionality for a real-time single-carrier modem has been completed. This includes packet generation (framing), error-correction coding, equalization and timing and carrier recovery, which allow the modem to be fully demonstrated with file I/O. Hardware development resumed late in 2005, and is expected to produce two alternative solutions for conversion between passband and baseband. One is a custom-built daughtercard based on upconverter and downconverter ASICS from Analog Devices. The other hardware solution is implemented directly inside an FPGA on the A/D and D/A converter card. Work on this project will cease upon termination of the ongoing tasks, which will result in a basic working prototype.

d)  Future Work:

Work on underwater MIMO communication will focus on adaptive equalization algorithms and transmit diversity strategies that can cope with highly dispersive channels that exhibit partially coherent responses. Regarding time-reversed communication, future work will address low complexity equalization approaches for passive receivers, where focusing is performed synthetically. In particular, low complexity multichannel combining strategies inspired on basic time reversal are sought, which can compensate for the degradation in focusing performance due to channel variations. On a more theoretical level, receiver parametrization and adaptation algorithms based on physical propagation models will be investigated.

Action 3.  Acquisition of 3D Models of Real Environments

The so-called factorization methods recover 3D rigid structure by factorizing an observation matrix that collects 2D projections of features. These methods became popular due to their robustness—they use a large number of views, which constrains adequately the solution—and computational simplicity—the large number of unknowns is computed through an SVD, avoiding non-linear optimization. However, they require that all the entries of the observation matrix are known. This is unlikely to happen in practice, due to self-occlusion and limited field of view. Also, when processing long videos, regions that become occluded often appear again later. Current factorization methods process these as new regions, leading to less accurate estimates of 3D structure.

1.  We developed a global factorization method that infers complete 3D models directly from the 2D projections in the entire set of available video frames. Our method decides whether a region that has become visible is a region that was seen before, or a previously unseen region, in a global way, by seeking the simplest rigid object that describes well the set of observations. This global approach increases the accuracy of the estimates of the 3D shape of the scene and the 3D motion of the camera.

2.  Within this framework another fundamental problem in the path of generating 3D models from video is the development of reliable image based tracking and matching processes, together with observer motion estimation capabilities. In other words, before compleating the observation matrix and factorize it one has to construct it in such a way that all coordinates of the same point lie on one column. One contribution was done by formalizing the image point matching for multiple views at once. Assuming rigidity as prior knowledge, we seek the point association among several images that contributes to the “most rigid” scene reconstruction. The formulation results from the extension of previous matching methods using permutation matrices. Essentially, the previous technique was extended to assginment tensors, insetad of assignement matrices. This results in a linear program as before which can be solved efficiently. Of course, usually, overcoming one problem turns explicit many other problems, and here the issue is the huge dimensionality of the resulting optimization problem. Fortunately there is a lot of structure in the model and very efficient decompositions can be exploited to solve it very efficiently.

The majority of current approaches to image motion analysis starts by computing image motion (e.g., optical flow, feature point correspondes) as a previous step. In general, solving this step turns out to be the key to the success of those approaches. We believe it is worth attempting to avoid that intermediate step, by formulating the anaylsis problems directly from the image intensities. For example, the majority of the approaches to the automatic recovery of a panoramic image from a set of partial views are suboptimal in the sense that the input images are aligned, or registered, by matching pointwise features across images, e.g., consecutive frames of a video clip. These approaches lead to propagation errors that may be very severe, particularly when dealing with videos that show the same region at disjoint time intervals. Rather, we use a generative model for the partial views of the panorama and develop an optimization algorithm to compute, in an efficient way, the Maximum Likelihood estimate of all the unknowns involved: the parameters describing the alignment of all the images and the panorama itself , i.e., our method determines the panorama that best matches the entire set of partial views.

As well as for image registration, the problem of inferring 3D orientation of a camera from video sequences has been mostly addressed by first computing correspondences of image features. This intermediate step is the main bottleneck of those approaches. We developed a new 3D orientation estimation method for urban (indoor and outdoor) environments, which avoids correspondences between frames. The scene property exploited by our method is that many edges are oriented along three orthogonal directions; this is the recently introduced Manhattan world (MW) assumption. We build a probabilistic sequential orientation estimation method, based on an MW likelihood model, which, by exploiting the strucure of the problem (the definition of equivalence classes of equiprojective orientations; the introduction of a new small rotation model, formalizing the fact that the camera moves smoothly; and the decoupling of elevation and twist angle estimation from that of the compass angle), allows a drastic reduction of the search space for each orientation estimate.

2 – HUMAN RESOURCES IN 2005

PhD researchers (staff) - 5 (from which 0 foreign)

PhD researchers (Post-Doctoral fellows) – 0 (from which xx foreign)

PhD students - 2 (from which 1 foreign)

MSc students – 1 (from which 0 foreign)

Engineers – 0 (from which 0foreign)

Technicians -

3 – INDICATORS IN 2005

A - Publications
Books (author)
Books (editor)
Books (chapters in books)
Papers in international journals / 2
Papers in national journals / 1
B - Comunications
In international conferences / 6
In national conferences
C- Reports / 3
D – Organization of Seminars and Conferences / 12
E – Advanced Training
Ph.D Thesis
M.Sc Thesis / 1
Others
F - Models
G – Software Applications
H - Pilot Instalations
I - Laboratory Prototypes
J - Patents
K - Awards / 3
L – Invited Oral Presentations

4 – DESCRIPTION OF INDICATORS IN 2005

A - 1) BOOKS (author)

A - 2) BOOKS (EDITOR)

A-3) CHAPTERS IN BOOKS

A -4) IN INTERNATIONAL JOURNALS

[1] A. Martins, P. Aguiar, and M. Figueiredo, Orientation in Manhattan: Equiprojective Classes and Sequential Estimation. In IEEE Trans. on Pattern Analysys and Machine Intelligence, vol. 27, no. 5, 2005.