A Compressive Sensing And Swarm Optimization Algorithm For

A compressive sensing and swarm optimization algorithm for 4W1H in the Intelligent Space Leon F. Palafox Hashimoto Laboratory M2 37-086946

Outline • Introduction – Intelligent Space – Compressive Sensing – Swarm Intelligence • Particle Swarm Optimization

• • • • • •

Motivation Algorithm Description Hardware Description Results Conclusions Future Work

05/11/09

2

Introduction Intelligent Space •

Intelligent Space (ISpace) is a space that has ubiquitous distributed sensory intelligence and actuators for manipulating the space and providing useful services.

•

It can be regarded as a system that is able to support humans, i.e. users of the space, in various ways.

05/11/09

3

Introduction Compressive Sensing •

In almost all the applications when sampling we must follow Shannon/Nyquist theorem that requires sampling rate at least twice the message signal bandwidth in order to achieve exact recovery.

05/11/09

4

Introduction Compressive Sensing

PICTURE

N samples (ALL measurements are taken)

ORTHOGONALIZITION

Full set of projections is found

SORTING

K largest coefficients selected N-K coef. dumped

CODING

Straightforward decoding

Only K coefficients are coded

K<
EXAUSTIVE SEARCH

Signal Reconstruction PICTURE

05/11/09

CODING

(1) Underdetermined system M
5

Introduction Compressive Sensing

• Compressed sensing is new method to capture and represent compressible signals at the rate well below Nyquist’s rate. – Employs nonadaptive linear projections (random measurement matrix) – Preserves the signal structure (length of the sparse vectors is conserved) – Reconstructs the signal from the projections using optimization process (L1 norm)

05/11/09

6

Introduction Compressive Sensing y

Φ

S

Ψ

=

y

Θ

S

=

x (a)

N K-sparse

(b)

(a) Compressive sensing measurement process with a random Gaussian measurement matrix and discrete cosine transform (DCT) matrix . The vector of coefficients s is sparse with K = 4. Φ (phi, measurement matrix) Ψ (psi, orthonormal basis) Θ (theta, Compressed Sensing reconstruction matrix)

(b) Measurement process

05/11/09

7

Introduction Compressive Sensing •

M measurements, y, random measurements matrix, Φ, and basis Ψ, are used to reconstruct compressible signal x (length) N or equivalently its sparse coefficient vector s.

•

Since M
•

Signal reconstruction algorithm aims to find signal’s sparse coefficient vector in the (N-M)-dimensional translated null space H=N(Θ)+s. – L1 norm (adding absolute values of all elements) can exactly recover K sparse signals and closely approximate compressible signals with high probability

05/11/09

8

Introduction Swarm Intelligence • Is a type of artificial intelligence based on the collective behavior of decentralized, self-organized systems. • The expression was introduced by Gerardo Beni and Jing Wang in 1989, in the context of cellular robotic systems

05/11/09

9

Introduction Particle Swarm Optimization • Is a population based stochastic optimization technique developed in 1995, inspired by social behavior of bird flocking or fish schooling. • PSO shares many similarities with evolutionary computation techniques such as Genetic Algorithms (GA). – The system is initialized with a population of random solutions and searches for optima by updating generations.

• It has no evolution operators such as crossover and mutation. – In PSO, the potential solutions, called particles, follow the current optimum particles. 05/11/09

10

Introduction Particle Swarm Optimization •

Each particle keeps track of its coordinates in the problem space which are associated with the best solution (fitness) it has achieved so far. – Another "best" value that is tracked by the particle swarm optimizer is the best value, obtained so far by any particle in the neighbors of the particle. – When a particle takes all the population as its topological neighbors, the best value is a global best.

•

The particle swarm optimization concept consists of, at each time step, changing the velocity of (accelerating) each particle toward its best locations (local version of PSO). • Acceleration is weighted by a random term, with separate random numbers being generated for acceleration toward the best locations.

05/11/09

11

Motivation • There is currently in the ISpace some background on people activity detection. • The most advance work in this topic is called 4W1H • • • • • 05/11/09

Who When What Where How 12

Motivation • These kind of algorithms require 2 things: – High number of sensors – High number of measurements

• It poses some problems – High computational complexity – Processing RAW data that may be not necessary – It has to be done as close as real time as possible. 05/11/09

13

Motivation

• Compressive Sensing addresses the problem of having to deal with a large amount of Data. • Particle Swarm Optimization is a good tool to match current activities to activities that have been learned before.

05/11/09

14

Hardware Description

• In order to obtain data a set of sensors must be used. • Due to time constraints, currently only an accelerationgyroscopic sensor is going to be used. • It must be able to recognize simple movements from the arm.

05/11/09

15

Algorithm Description

WHERE

Sparse Manifold Conversion

PSO

WHO

WHAT

Acceleromete r

Random Sampler

MASTER MATRIX SET WHEN

Sampler

HOW

Identification Algorithm

05/11/09

16

Algorithm Description • The data is sampled from the sensors using a preset measurement matrix that proved to be successful with the control data. – It is one of the objectives to create a Matrix that can handle all kind of data.

• In the sampler the data is redirected to one of the 5 income matrices.

05/11/09

Sparse Manifold Conversion

Acceleromete r

Random Sampler

Sampler

17

Algorithm Description • After the data has been retrieved, we will use PSO to find which of our current space solution best matches with the income data.

WHERE

PSO

WHO

WHAT

• Each Master Matrix will contain information on given movements, people, actions, and any other available recognition pattern.

MASTER MATRIX SET WHEN

HOW

Identification Algorithm

05/11/09

18

Preliminary Results • When capturing the signal, we present two possibilities. – Capture the signal without transforming the signal – Capturing the signal with previous Fourier transformation.

• Each possibility had some good points and down points. – To much noise at the exit. – Some parts of the signal where not projected in the output 05/11/09

19

Preliminary Results

05/11/09

Original Signal

Reconstruction

N=4001

K=256 20

Preliminary Results

80

60

60 50

40 20

40

0 ­20

30

­40 20

­60 ­80

10

­100 ­120

0

500

05/11/09

1000

1500

2000

2500

3000

3500

4000

4500

0

0

500

1000

1500

2000

2500

3000

3500

Original Signal

Reconstruction

N=4001

K=256

4000

4500

21

80

300

60 200

40 20

100

0 ­20

0

­40 ­100

­60 ­80

­200

­100 ­120

0

500

05/11/09

1000

1500

2000

2500

3000

3500

4000

4500

­300

0

500

1000

1500

2000

2500

Original Signal

Reconstruction

N=4001

K=1024

3000

3500

4000

4500

22

Conclusions • The system presented a good reconstruction in the field of frequency, yet in the field of time it show to be a noisy signal. • According to the results, we proved the algorithm can be applied to certain signals. But filtering needs to be done. • The sampling part of the algorithm may not need to be as complex as compressive sensing since the signals are not that complex themselves. 05/11/09

23

Future Work • Tuning and testing of different source signals for different mappings. • Giving a full justification to the CS solution. • Implementing the Identification part of the algorithm. • Implement the recognition matrices and see which parameters are to be set. 05/11/09

24

05/11/09

25