Mid Term Presentation

大学院輪講資料

2009 年 05 月 8 日

A compressive sensing and swarm optimization algorithm for 4W1H in the ISpace 修士 2 年 電気工学専攻 橋本研究室

37086946

Palafox Novack Leon Felipe

Abstract

observation focus has been limited to human and robot [3][4],

The 4W1H technique has been a subject of study in the

but there are a lot of objects in our living environment. In

ISpace, presenting multiple problems that had to be solved

order to offer the appropriate services using the objects, not

individually in order to improve performance and number

only the physical information of object but also the object’s

of sensors. The current paper presents a proposed

information that is occurred by interaction with human. Such

algorithm that makes use of sensing and processing tools

the information cannot be written beforehand and provided

compressive sensing and swarm optimization to pose a

only by observation. In other words the relations among

feasible solution to this problem.

humans and objects are important. Thus, 4W1H is used to determine this

1.

information.

Introduction

Advances in networking computing, sensor technology

and

robotics allow us to create more convenient environments for humans In that context the Intelligent Space (iSpace) concept was proposed. iSpace is a space that has distributed

sensory

intelligence

and

ubiquitous

actuators

for

manipulating the space and providing useful services [1]. It can be regarded as a system that is able to support humans, i.e. users of the space, in various ways. Actuators provide services both physical and informative to humans in the space,

Fig. 1.

whereas sensors are used for observing the space and

Diagram of the iSpace and the different kind of sensors and actuators that may interact within.

gathering information.[2] The ISpace is conformed of a set of sensors and actuators,

Whenever we have a problem that requires a high number

such as robots, that are aimed at tracking and interacting with

of sensors like in the ISpace, we will have to deal with high

the elements involved. (Figure 1). The ISpace consists of three functions,

sampling speed, transmission and computational complexity observing”,

problems, as each sensor in the network adds a degree of

“understanding”, and “acting”. The “Observing” function is the

complexity and posses a higher load to the main processing

most important one, because it will deliver the information to

server.

know what kind of services is required. Conventionally,

Compressive Sensing is a recently developed technique that

[1]

copes with the issue of high sampling rate based in the fact that

As well we are going to describe some of the basic principles

not all sampled data is used whenever doing variable

of 4W1H to determine how the algorithm might be able to

measurements [5]. It randomly samples the input of data and

solve the posed problem.

the entire computational load is deal with afterwards, its greatest advantage is that it resumes a very complex sampling

Compressive Sensing

problem into a L1 minimization problem, the problem of

The term compressive sensing was first used in 2004, when

finding the best possible answer for the sampled set of data.

Donoho published his paper with an extensive explanation on

Swarm Intelligence is a field that originated in copying and

its properties, along with all the mathematical demonstrations.

implementing the way large groups of animals, such as ants,

[5]

birds or fish behave. It consists now in a number of techniques

In traditional data sampling Finding signal representation in

that allows us to optimize or to control more effectively

an orthonormal basis (Fourier, etc.) is computationally

systems, without the need of bulky computer systems. As well

intensive since all must be found and sorted in order to find K

they are widely used for optimization algorithms, being its most

significant coefficients.

widely used the Particle Swarm Optimization (PSO).

Nyquist Theorem defines that for a successful sampling of

These two algorithms attack both sampling rate problems as

any signal, the sampling frequency must be at least twice to

well as data recognition for very high amounts of data. In

avoid such effects as aliasing, which prevents us to actually

consequence they present both reasonable solutions to work

know where is the fundamental frequency of the work signal,

with in the intelligent space.

compressive sensing is a novel way in which we sample at k

This paper will be organized in the following way. First we

rate where :

will present a short introduction to the compressive sensing and

K<
the swarm intelligence algorithms, focusing specially in the

Where N is the size of the original signal.

PSO. Afterwards we will do a description of the available

It uses the basic principle that almost every signal is sparse

hardware as well as the underlying problem and past solutions.

when linearly transformed to some other mathematical

A proposed algorithm will be explained along with its

space.(Figure 2) A clear example of this is how a sinusoidal

fundamental variables as well as actual implementation and

signal has a sparse representation when transformed in to the

possible areas of enhancement. Experiment design and current

Fourier Domain being only clearly relevant the coefficients

results will be analyzed next and finally a word on the future

that represents the fundamental frequencies of the signals we

work and current conclusions will be in order.

are using. A number of transformations can be used to obtain these sparse representations, such as wavelets or curvelets. Or

2.

complexity may arise depending in the signal and we would

Basic Concepts and theory

To develop Compressive sensing theories requires a vast

need to use algorithms that create our own defined manifold in

mathematical background, but for understanding and applying

which we will have the desired properties.

the basis of it advanced linear algebra and calculus are enough tools to start using it. PSO is an example of linear programming and how can we optimize problems of similitude and optimization by reaching local and global bests for an objective function.

[2]

Fig. 3.

Diagram of the compressive sensing sampling matrix

According to each set of data a different reconstruction may need to be used, there is currently a lot of work being done in determining different reconstruction parameters [6][7], but as of this moment there is some powerful applications already Fig. 2.

Different signals in the Fourier domain

being developed.[8] One of the current applications developed int the field is the

The sparse signals themselves have the property that if

one described in [8] in which a single pixel camera was

multiplied by a random matrix, it gets a set of data that can

developed in order to fasten the data flux of information in a

latter be reconstructed via L1 Minimization. (Figure 3). This

image sensing architecture.(Figure 4)

random matrix is called measurement sampling matrix which have to hold to mathematical properties like incoherence or restrictive isometry, it has been proven that these properties are present in random matrices, which can vary depending on the application.

L1 norm (adding absolute values of all elements) can exactly recover K sparse signals and closely approximate compressible signals with high probability

Fig. 4.

Diagram of the compressive sensing sampling matrix

Compressive sensing problem then becomes a 2 step

Is because of these properties that CS might prove to be a

problems, first, to define whether the data can be sparse in

good solution in order to sample data from a high number of

some given space and second, to define the reconstruction

sensors and at the same time being able to interpret that data

parameters.

having enough information, if not for an exact representation at leas for recognition.

Swarm Intelligence Insects and animal groups usually have complex behaviours as a herd that might be as well product of a higher controller [3]

organism that observes and monitors the current structure of the system, such as the perfect deltas birds describe when they flight, or the way ants are able to detect the shortest way to some food source after some tries. But the truth is that these outcomes are the result of small interactions between these animals, and each agent of the system does not have more than few and simple instructions, such as “gather”, or “maintain distance”.[9] This order obtained through the fact of a set of small patterns delivered by relatively simple organisms is called stigmergy A number of algorithms have spawned from these simple

Fig. 5.

Diagram of the compressive sensing sampling matrix

principles, being the one of interest Particle Swarm Optimization.

The particle swarm optimization concept consists of, at each time step, changing the velocity (accelerating) each particle

Particle Swarm Optimization

toward its pbest and gbest (global version). Acceleration is

Particle swarm optimization has roots in two main

weighted by a random term, with separate random numbers

component methodologies. Perhaps more obvious are its ties to

being generated for acceleration toward pbest and gbest.

artificial life (A-life) in general, and to bird flocking, fish

Finally we will have a mapping space that had a local

schooling, and swarming theory in particular. It is also related,

optimum, which each particle can reach, and a global optimum,

however, to evolutionary computation, and has ties to both

that all the particles are reaching to aim. (Figure 5)

genetic algorithms and evolutionary programming. Particle swarm optimization is similar to a genetic algorithm

Description of 4W1H

[2] in that the system is initialized with a population of random

It is thought that the relation between the human and the

solutions. It is unlike a genetic algorithm, however, in that each

object is described by observing the use history of the object.

potential solution is also assigned a randomized velocity, and

The use history of the object is observed by focusing on the

the potential solutions, called particles, are then “flown”

object’s movement which is caused when it is used by human.

through hyperspace. [10]

The name, the size, the color, and the shape etc. of the object

Each particle keeps track of its coordinates in hyperspace

are information given beforehand, and are information given

which are associated with the best solution (fitness) it has

beforehand. On the other hand, there is information which

achieved so far. (The value of that fitness is also stored.) This

occurs only after a person uses the thing, such as the use

value is called pbest. Another “best” value is also tracked. The

history or the movement history. Such information is vast, and

“global” version of the particle swarm optimizer keeps track of

considering the cost it is not realistic to describe the use

the overall best value, and its location, obtained thus far by any

history information on a lot of objects that exist in the space.

particle in the population; this is called gbest.

Therefore, it is necessary that the object's information is written automatically without human intention when the object is used by human. [11] We try to describe human-object relations based on the

[4]

following use history of the object (4W1H).

be experimented leaving the identification part of the

・ Where: the position of the object

architecture for future work, as well as some detailed work in

・ Who: the user of the object

the manifold creation. Currently we are going to rely in

・ What: ID of the object

wavelet sparse signals and Fourier sparse signals such as

・ When: the time of the object used

sinusoidal or signals with deep contrast, such as sudden

・ How: the way of the object used

movements or curve movements of the acceleration sensor. Which are inherent when reaching and object or suddenly

3.

moving one’s arm.

Hardware Description

The system used for the implementation of the algorithm

The reason for this is that curve movements have a sparse

consists currently in a set of acceleration and gyroscopic

decomposition in the frequency field, being most of this

sensors, which allows us to detect and categorize the

curves that represent as sinusoidal signals and sudden

movements a human arms performs when handling certain

movements have a very distinctive wavelet transform, due to

objects.

the wavelet sensitivity of sudden changes in the signal that will be of use when having to deal with the sudden changes of

This system is able to detect a 3D acceleration as well as to

the system.

detect pitch and yaw of the current object, giving us enough information to know direction and inclination of the arm at specific moments. (Figure 6) To detect the human location it will be of some need some kind of special recognition system, such as the one we currently have in Hashimoto Laboratory, in the current work, that system is not yet implemented, but for sure it will be sued to detect location of the human using some object.

MTx

Fig. 7.

Diagram of the compressive sensing sampling matrix

The system will randomly sample an income signal from the ZPS

sensors, this random sampling will be done taking into account Z

Y

the basic architecture for CS in which a random matrix is X

created in the sampler. This matrix has to have some coherence depending in the kind of signal to be sampled.

Fig. 6.

The sampler will be in charge of detecting whether or not

Diagram of the compressive sensing sampling matrix

the income signal has a sparse representation in the given 4.

manifold, yet in the current experiments we know before hand

Proposed Algorithm

that they present sparsity in the frequency space, so we

The proposed algorithm is pictured in figure 7, but due to

directly input the signal into the sampler.

sometime constrains, only the sampling part of the system will

The sampled signal will be divided according to its income

[5]

to five matrices, what, who, when, where and how, each matrix

movements as well as arm inclinations, doing this we might be

will hold information for each sensing until a given size is

able to infer some information related to the person activity by

determined, this size will be given according to a set of Master

that precise moment.

Matrices.

Some basic movements are curved movements such as arm

The Master Matrices will have the fundamental information

trajectories and sudden movements such as when the arm

of each variable 4W1H, and using PSO we will obtain which of

reaches for a key or for a switch and then it comes back to its

the input matrices is the closest one to the master matrices so to

initial state.

define each of the 4W1H.

These movements as it was stated before will be used for

This approach will be able to detect wether the current input

some basic testing, first we will sample the data from those

is registered into the system or not, and furthermore, if the input

movements and see whether or not can it be sampled

is entirely a new matrix, the system may be able to learn this

following CS sampling parameters, and afterwards we will try

new input for future use, thus making the algorithm flexible to

to reconstruct the signal so it can be latter processed by the

different work spaces.

main processing computer. The original size of this signal is N=4001 which

Variable Analysis In the income matrices, a set of variables is needed in order

corresponds to 10 seconds of sampling, this was done to prove

to define how the matrices are going to behave as well as it size

whether a high frequency of the signal could get precise results

and rank.

for a very low frequency of sampling.

The variables are defined by the sensor at hand, currently

The size of the sample was of 256 random samples for the

this work is not yet done, but each matrix will have to be

original signal, which we expect will be sufficient for

composed of signals that define each specific matrix’

reconstructing the most important information of the original

•

When: Timer and calendar system

signal, we also expected it will prove a good signal for

•

Who: ID tags, able to identify the current user of the

recognition afterwards. The Fourier discrete transform was used in order to obtain

system. • •

What: ID and acceleration tags that are able to identify

the frequency representation, as well as to do the inverse

the current object.

transform afterwards.

Where:

Localization

sensors

depending

on

All the experiments where produced in Matlab, and timed in

the

order to prove its real time possibilities

complexity level of the system. •

6.

How; A set of sensors to detect which way the system is

Results

used, such as acceleration sensors. 5.

The obtained results where both satisfactory and proved the

Experiments Design

In order to define whether the algorithm is useful or not, a set

feasibility of the system, yet further work needs to be done in

of experiments needed to be designed. Since the current time

implementing the sampling and the later signal reconstruction.

constrain did not allow for more complex experiments, some

The input signal transformation gave us the insight of this

simple identifications were used to evaluate the system

movements actually being of very low frequencies, thus the

feasibility and try to evaluate how processing speeds behave

sampling parameter used might be adequate.

with highly complex sets of data.. In the current system, we are able to measure simple arm

[6]

frequency elements shoed in figure 7 affects heavily the way the signal looks in the output, the original signal being a simple sinusoidal signal, the output is a very noisy signal that might use some filtering. So a new element must be added in order to make the system entirely reliable and fully operational.

Fig. 7.

Diagram of the compressive sensing sampling matrix

In the other hand, when doing the reconstruction, we found this high data size had a lot of troubles processing in a relatively fast computer, with more than 4GB of RAM, the computer took around 1 minute to process the entire set of data, which might prove to be not as useful as thought in real time.

Fig. 7.

Diagram of the compressive sensing sampling matrix

When doing the reconstruction, we found that with the 256 samples, we where able to get a very precise representation of

7.

the signal in the sparse field, which proves the algorithm

The results prove that the system although limited might

Future Work

prove to present some interesting researching topics as well as

feasibility in a digital sampler.

the ability to latter define some in house algorithms in order to customize CS using to the needs of human behaviour sampling. The systems need to be completed and the Identification algorithm needs to be implemented in real time to be able to provide some experimentation in order to prove the feasibility of the algorithm. Further experiments require to be done in order to fully exhibit the power and weakness of the algorithm in different situations and environments. As well, the second part of the algorithm needs to be tested and implemented; all the system variables are to be tuned according the different situations that may be presented. Fig. 7.

As well the necessary sensors for the array are to be defined

Diagram of the compressive sensing sampling matrix

and programmed into the algorithm to provide the data we are looking to obtain., as well as a Real Time implementation in

Yet, when trying to transform the data back, we see, all that

[7]

[5]

order to do some demonstrations and power of the algorithm.

Donoho, D.L., "Compressed sensing," Information Theory, IEEE Transactions on , vol.52, no.4, pp.1289-1306, April 2006

[6]

8.

Conclusions

Figueiredo, M.A.T.; Nowak, R.D.; Wright, S.J., "Gradient Projection for Sparse Reconstruction: Application to Compressed Sensing and Other

A new algorithm in the ISpace in order to implement 4W1H

Inverse Problems," Selected Topics in Signal Processing, IEEE Journal of , vol.1, no.4, pp.586-597, Dec. 2007

was presented. This algorithm uses the recently developed [7]

technique of compressive sensing for addressing the problem of

Rauhut, H.; Schnass, K.; Vandergheynst, P., "Compressed Sensing and Redundant Dictionaries," Information Theory, IEEE Transactions on ,

high frequency sampling.

vol.54, no.5, pp.2210-2219, May 2008

As well it uses Swarm Intelligence algorithm Particle Swarm

[8]

K.F.; Baraniuk, R.G., "Single-Pixel Imaging via Compressive Sampling,"

Optimization in order to compare input matrices, that define

Signal Processing Magazine, IEEE , vol.25, no.2, pp.83-91, March 2008

variables such as user activity, location and identification, to [9]

some stored matrices in order to define the current user activity

[10] Kennedy, J.; Eberhart, R., "Particle swarm optimization," Neural Networks, 1995. Proceedings., IEEE International Conference on , vol.4,

This technique is an improvement over the current 4W1H

no., pp.1942-1948 vol.4, Nov/Dec 1995

techniques which although well implemented lacked the

[11] Kouhei Kawaji, Kazuki Yokoi, Mihoko Niitsuma, Hideki Hashimoto,

capability of learning new actions or presenting some

"Observation System of Human-Object Relations in Intelligent Space", 6th IEEE Int. Conf. on Industrial Informatics, pp.1475-1480, 2008.

intelligent response to some given actions. The experimentation part of the algorithm proved to be successful to certain degree, yet, some work and tuning needs to be done in order to leave the algorithm fully operational to future work.

References

J.-H. Lee and H. Hashimoto, "Intelligent space - concept and contents," Advanced Robotics, vol. 16, no. 3, pp. 265-280, 2002.

[2]

Brscic, D.; Hashimoto, H., "Tracking of Humans Inside Intelligent Space using Static and Mobile Sensors," Industrial Electronics Society, 2007. IECON 2007. 33rd Annual Conference of the IEEE , vol., no., pp.10-15, 5-8 Nov. 2007

[3]

Takeshi Sasaki; Hideki Hashimoto, "Human Observation Based Mobile Robot Navigation in Intelligent Space," Intelligent Robots and Systems, 2006 IEEE/RSJ International Conference on , vol., no., pp.1044-1049, Oct. 2006

[4]

Y. Toshima, N. Ando and H. Hashimoto,

Information Display

System

using Active Projector in Intelligent Space -Integration of distributed devices based on RT-Middleware,

Kennedy J and Eberhart RC “Swarm Intelligence”. Morgan Kaufmann Publishers 2001

in the Intelligent Space.

[1]

Duarte, M.F.; Davenport, M.A.; Takhar, D.; Laska, J.N.; Ting Sun; Kelly,

The 12th

on Artificial Life and Robotics (AROB'07),

International Symposium

pp. 183-186, 2007.

[8]